CdSINFORMATICA
Codice008AA
CFU12
PeriodoSecondo semestre
LinguaItaliano
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.
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.
Le conoscenze dello studente saranno verificate sulla base della sua capapcità di discutere e mettere in pratica i concetti e le tecniche più importanti presentati nel corso.
The student's knowledge will be assessed on her/his demonstrated ability to discuss and put into practice the main topics presented during the course.
Capacità fondamentali nel progetto di algoritmi e strutture dati e nella valutazione degli algoritmi.
Basic skills on algorithm and data structure design and time/space complexity evaluation.
Esame scritto, prova di laboratorio, ed eventuale orale.
Written and programming test, and a possible oral.
Gli studenti saranno in grado di valutare le performance di algoritmi di base prima della loro implementazione direttamente da progetto; di conoscere problemi difficili per cui le scelte algoritmiche di progetto possono influenzare pesantemente il risultato.
Students will be able to evaluate performance of basic algorithms before their implementation, directly from their design. Know some difficult problems and which algorithmic design choices can impact positively or negatively the algorithm design.
Esame scritto, prova di laboratorio, ed eventuale orale.
Written and programming test, and a possible oral.
Fondamenti di matematica e di linguaggio C.
Basics of Maths and C programming.
Matematica Discreta: Serie Numeriche, Principio di induzione, Dimostrazioni per induzione, Sommatorie.
Discrete Mathematics such as Numerical Series, Induction, Proving by Inducion, Sums.
Delivery: face to face
Learning activities:
attending lectures
participation in discussions
individual study
Laboratory work
Attendance: Advised
Teaching methods:
Lectures
laboratory
For details look at the home page of the course.
- Breve introduzione a problemi computazionali, indecidibilità, e trattabilità (P, NP, NPC, EXP-TIME).
- Complessità computazionale: modello di calcolo, dimensione dell'input e dell'output, caso pessimo e caso medio.
- Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
- Divide-et-impera, Relazioni di ricorrenza, Teorema fondamentale.
- Algoritmi per sequenze statiche e dinamiche: ricerca e ordinamento.
- Ordinamento basato su confronti: Insertion sort, Merge-sort, Quick-sort, Heap sort.
- Ordinamento di interi: Counting sort, Radix Sort.
- Ordinamento di stringhe: qsort-based.
- Sottosequenza di somma massima.
- Programmazione dinamica: LCS, Partizione e Zaino
- Algoritmi randomizzati: Quicksort.
- Generazione di combinazioni e permutazioni
- Analisi ammortizzata: doubling di array, contatore binario, k ricerche.
- Dizionari: Alberi bilanciati (Alberi 2-3), Tabelle hash (liste di trabocco e indirizzamento aperto).
- Alberi: rappresentazione e visite.
- Grafi I: rappresentazione e visite (DFS e BFS), DAG e ordinamento topologico.
- Grafi II: Ciclo/cammino euleriano, ciclo hamiltoniano, componenti (fortemente) connesse.
- Grafi III: Minimum Spanning Tree e Shortest Path.
SYLLABUS
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: Knapsack and its variants. Trees representation and visit. Dictionaries: 2-3 trees, hash tables, trie. Randomized Algorithms: Quicksort, QuickSelect. Graphs: representation and visit (DFS e BFS), DAG and topological sorting.
T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.
Altri riferimenti verrano indicati e pubblicati sulla pagina web del corso.
T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.
Further bibliography will be indicated and linked in the home page of the course.
Si segua la pagina web del corso.
Regularly visit the web page
Esame scritto, test di programmazione C, eventuale orale.
Written exams, a C programming test, and possibly an oral.
http://didawiki.di.unipi.it/doku.php/informatica/all-b/start
http://didawiki.di.unipi.it/doku.php/informatica/all-b/start
http://didawiki.di.unipi.it/doku.php/informatica/all-b/start
http://didawiki.di.unipi.it/doku.php/informatica/all-b/start