ALGORITHMS

Obiettivi formativi

Obiettivi generali Acquisire la conoscenza di base delle più note tecniche algoritmiche di progettazione e delle tecniche di valutazione della correttezza e della complessità degli algoritmi. Obiettivi specifici Conoscenza e comprensione: Al termine del corso gli studenti posseggono le conoscenze di base relative a: - tecniche fondamentali di progettazione algoritmica; - analisi della correttezza e della efficienza degli algoritmi; Applicazione di conoscenza e comprensione: Al termine del corso gli studenti sono in grado di: - analizzare le prestazioni di un algoritmo tramite strumenti matematici rigorosi; - analizzare algoritmi e strutture dati - progettare ed analizzare nuovi algoritmi, sfruttando le metodologie presentate durante il corso. Autonomia di giudizio: Lo studente alla fine del corso deve essere in grado di scegliere autonomamente qual è la tecnica algoritmica più adatta da applicare per un determinato problema e valutare tra più soluzioni algoritmiche per un certo problema qual’è da preferirsi. Abilità comunicative: Lo studente acquisirà la capacità di esprimere un’idea algoritmica tramite l’uso di uno pseudocodice. Capacità di apprendimento: Lo studente avrà acquisito la capacità di analizzare un problema, progettare le necessarie strutture dati e un algoritmo corretto ed efficiente che lo risolva.

Canale 1
GIANNI FRANCESCHINI Scheda docente

Programmi - Frequenza - Esami

Programma
Basics: -Basic notations -Asymptotic notations -Worst case analysis -Divide and conquer Sorting and selection: -Heapsort -Mergesort -Quicksort -Sorting in linear time -Selection problems Some data structures: -Basic data structures -Binary Trees -RB-Trees Amortized analysis -Basic amortized analysis -The accounting method -The potential method -Dynamic arrays Some more data structures -B-Trees and the external memory model -Union-find -Fibonacci Heap Graphs and basic graph algorithms -Representations of graphs -BFS and DFS -Topological sorting -Strongly connected components Greedy algorithms -Basics of greedy algorithms -Huffman codes Dynamic programming -Basics of dynamic programming -Rod cutting -Matrix-chain multiplication -Longest common subsequence Minimum spanning trees -Kruskal's algorithm -Prim's algorithm Shortest paths problems -The Bellman-Ford algorithm -Dijkstra's algorithm -The Floyd-Warshall algorithm String algorithms and data structures -String sorting -Tries -Suffix sorting -Suffix trees Programming -The C programming language
Prerequisiti
Nessun prerequisito.
Testi di riferimento
"Introduction to Algorithms" Cormen, Leiserson, Rivest, Stein 3rd edition
Frequenza
Non obbligatoria.
Modalità di esame
Prove intermedie durante il corso. Prova scritta negli appelli.
Bibliografia
Nessuna
Modalità di erogazione
Normali lezioni...
  • Codice insegnamento1049269
  • Anno accademico2025/2026
  • CorsoBioinformatics - Bioinformatica
  • CurriculumCurriculum unico
  • Anno3º anno
  • Semestre2º semestre
  • SSDINF/01
  • CFU6