ECTS - University of Pisa
Cosa è un algoritmo e cosa è un modello di calcolo. Saper caratterizzare i dati da elaborare strutturandoli nel modo più opportuno al fine di agevolarne l'uso da parte degli algoritmi. Conoscere le strutture dati e le tecniche fondamentali per il progetto di algoritmi (di base). Conoscere le tecniche di valutazione della complessità e le limitazioni inerenti dei problemi da risolvere. Caratterizzare i problemi indecidibili ed esponenziali. Conoscere il linguaggio C e saper realizzare con esso gli algoritmi e le strutture dati viste in classe.
The goal is to introduce (basic) algorithms and data structures to solve problems on sequences, lists, trees and graphs, in efficient time and/or space. We will also deal with techniques for evaluating the complexity of algorithms and problems. Finally, we will experiment these algorithmic techniques by implementing some of them using the C language.
Lo studente sarà valutato sulla base della capacità dimostrata di discutere e mettere in pratica i principali argomenti presentati durante il corso.
Metodi:
The student will be assessed on her/his demonstrated ability to discuss and put into practice the main topics presented during the course.
Methods:
Saper progettare e realizzare in un linguaggio imperativo (es. C) algoritmi corretti ed efficienti attraverso l'uso di strutture dati e tecniche algoritmiche di base. Saper valutare la complessità di un algoritmo in tempo e spazio, al caso pessimo e al caso medio, e secondo la complessità ammortizzata. Saper valutare le limitazioni inerenti del calcolo.
The student who completes the course successfully will be able to (i) design and implement correct, efficient algorithms in imperative language (eg C) using the basic algorithmic data structures and techniques; (ii) evaluate the complexity of an algorithm in time and space, at the worst case and in the average case, and according to the amortized complexity; and (iii) assess the inherent limitations of the calculation.
Lo studente saprà realizzare in un linguaggio imperativo (es. linguaggio C) gli algoritmi e le strutture dati viste in classe. Lo studente saprà inoltre stimare la bontà (leggi, efficienza in tempo e spazio) di un sofwtare sulla base delle caratteristiche progettuali salienti, prescindendo dunque dalla macchina, dal linguaggio di sviluppo o dal sistema operativo sul quale il software viene eseguito. Allo stesso modo, saprà stimare le prestazioni degli algoritmi prima di arrivare alla fase di programmazione, debugging e profiling, mediante l'uso di modelli matematici opportuni.
The student will be able to implement the algorithms and data structures presented during the course in an imperative language (eg C language). The student will also be able to estimate the time and space complexity of the proposed algorithms.
Conoscenza di un linguaggio di programmazione imperativo, preferibilmente il linguaggio C (che utilizzeremo per le nostre esercitazioni di laboratorio). Dimestichezza con l'uso dei puntatori e della ricorsione.
Nozioni matematiche: proprietà e limiti di funzioni, sommatorie, numeri di Fibonacci, permutazioni, coefficienti binomiali, aritmetica modulare, numeri primi, metodi di dimostrazione (per induzione, per assurdo, per casi).
Prerequisiti per il Laboratorio:
Knowledge of an imperative programming language, preferably the language C (which we will use for our lab exercises). Ability to use pointers and recursion.
Mathematical notions: properties and limits of functions, summations, Fibonacci numbers, permutations, binomial coefficients, modular arithmetic, , proof methods (by induction, by contradiction, by contraposition, by case).
Prerequisites for the Laboratory:
Lezioni: frontali
Attività didattiche:
Frequenza delle lezioni: consigliata
Metodi di insegnamento:
Delivery: face to face
Learning activities:
Attendance: Advised
Teaching methods:
L'obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche (di base) che consentano allo studente la risoluzione di problemi su sequenze, liste, alberi e grafi, in modo efficiente in tempo e/o spazio. Si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo.
Il corso prevede una intensa attività di laboratorio che porterà gli studenti a sperimentare in linguaggio C le nozioni e le tecniche algoritmiche apprese in classe.
PROGRAMMA
Short introduction to computational issues: decidability and tractability (P, NP, NPC, EXP-TIME). Computational complexity: computation model, input and output size, decision tree, lower and upper bounds, worst and avarage case. Divide-et-impera; recurrence relations, fundamental theorem. Algorithms on static/dinamic sequences: search and sorting. Stable marrigies problem and maximum sum subsequence. Dynamic Programming: LCS, Partition and Backpack. Combination and permutation generation. Greedy: Huffman and Backpack. Self-adjusting data structures: MTF, Amortized and competitive analyis. Trees representation and visit. Dictionaries: AVL, hash tables, trie. Randomized data structures: Skip List. Randomized Algorithms: Quicksort, Karp-Rabin. Graphs: representation and visit (DFS e BFS), DAG and topological sorting.
Per il laboratorio, un testo fra:
For the laboratory activities:
L'esame consiste di tre prove:
The exam consists of three tests:
A written test with exercises designed to evaluate the theoretical notions and the problem solving skills of the student.
A laboratory test that verifies the student's ability to implement basic algorithms in C, solving simple problems on arrays, lists, trees, and graphs.
An oral exam on the course program.
http://didawiki.di.unipi.it/doku.php/informatica/all-b/start
http://didawiki.di.unipi.it/doku.php/informatica/all-b/start
Sistema di Autovalutazione per il laboratorio: http://algo1617.dijkstra.di.unipi.it/
Sistema di Autovalutazione per il laboratorio: http://algo1617.dijkstra.di.unipi.it/
