Algoritmi e Strutture Dati
Docente:
Alberto Montresor
alberto.montresor@unitn.it
Home
Introduzione
Informazioni generali
Programma
Lezioni e ricevimento
Regolamento d'esame
Faq
Appelli e iscrizioni
Voti scritti
Materiale didattico
Lucidi e appunti
Lucidi laboratorio
Video lezioni
Software
Compiti
Progetti
Libri di testo
Approfondimenti
Programma del corso
Introduzione
Introduzione [CLRS Cap. 1]
Algoritmi e strutture dati
Potenzialità e limiti degli algoritmi
Algoritmi come tecnologia
Per cominciare [CLRS Cap. 2]
Analisi algoritmi: primi cenni
Modelli computazionali
Insertion Sort
Merge Sort
Analisi degli algoritmi
Notazione asintotica [CLRS Cap 3.1]
Alcuni richiami di analisi [CLRS Cap 3.2]
Ricorrenze [CLRS Cap. 4]
Metodo dell'iterazione
Metodo della sostituzione
Teorema fondamentale delle ricorrenze (Master Theorem)
Analisi ammortizzata [CLRS Cap. 17]
Strutture dati base
Strutture dati elementari [CLRS Cap. 10]
Pile, code, liste
Alberi
Grafi [CLRS Cap. 22.1]
Ordinamento e selezione
Heapsort [CLRS Cap. 6]
Quicksort [CLRS Cap. 7]
Limiti inferiori per l'ordinamento [CLRS Cap. 8.1]
Ordinamento in tempo lineare [CLRS Cap. 8]
Mediane e statistiche d'ordine [CLRS Cap. 9]
Tecniche di programmazione
Divide et impera
Moltiplicazione di interi
Moltiplicazione tra matrici [CLRS Cap. 28.2]
Programmazione dinamica [CLRS Cap. 15]
Distanza fra stringhe di caratteri
Associatività prodotto matrici
Algoritmi greedy [CLRS Cap. 16]
Compressione di huffman
Problema dello zaino frazionario
Problema dello zaino 0-1
Problema del resto
Problema dello scheduling
Selezione delle attività
Backtrack
String matching
Tecniche euristiche
Algoritmo A*
Strutture dati avanzate
Alberi binari ricerca [CLRS Cap. 12]
Alberi RB [CLRS Cap. 13]
Tabelle hash [CLRS Cap. 11]
B-alberi [CLRS Cap. 18]
Strutture dati per insiemi disgiunti [CLRS Cap. 21]
Algoritmi su grafi
Algoritmi su grafi elementari [CLRS Cap. 22]
Visite in ampiezza e profondità
Ordinamento topologico
Componenti fortemente connesse
Alberi di copertura minima [CLRS Cap. 23]
Kruskal
Prim
Cammini minimi con singola sorgente [CLRS Cap. 24]
Bellman-Ford
Cammini minimi su DAG
Dijkstra
Cammini minimi fra tutte le coppie [CLRS Cap. 25]
Floyd-Warshall
Johnson
Problemi di flusso [CLRS Cap. 26]
Ford-Fulkerson
Edmonds-Karp