Algorithms and Data Structures - Teoria (2005/2006)

Course Not running, not visible

To show the organization of the course that includes this module, follow this link * Course organization

Lesson timetable

First four month term for the second and later years
Day Time Type Place Note
Tuesday 8:30 AM - 10:30 AM lesson Lecture Hall A  
Thursday 11:30 AM - 1:30 PM lesson Lecture Hall A  
Second four month term
Day Time Type Place Note
Tuesday 8:30 AM - 10:30 AM lesson Lecture Hall A  
Thursday 10:30 AM - 12:30 PM lesson Lecture Hall A  

Learning outcomes

Nel corso vengono esaminati i concetti di base per la formulazione di soluzioni algoritmiche a problemi concreti. Vengono studiate soluzioni a problemi formulati in termini di strutture matematiche astratte (liste, code, grafi, ...) e vengono descritte metodologie per identificare i problemi astratti che più si addicono allo studio di un problema concreto. Gli algoritmi vengono valutati e confrontati in base alla quantità di risorse che richiedono. Il corso si concentra inoltre sul ruolo che ha lo studio delle strutture di dati nella formulazione e valutazione di nuovi algoritmi.

Syllabus

Il corso viene svolto in 64 ore di lezione frontale, di cui 32 ore nel primo quadrimestre e 32 ore nel secondo quadrimestre. Nelle 64 ore di lezione sono comprese 20 ore di esercitazione durante le quali gli studenti devono risolvere problemi specifici sotto la guida del docente.

Complessità: complessità degli algoritmi, notazione asintotica, metodi di risoluzione delle equazioni di ricorrenza, analisi ammortizzata.

Ordinamento e Selezione: insertion sort, merge sort, heap sort, quick sort, quick sort probabilistico. Studio della complessità degli algoritmi di ordinamento, limite inferiore dell'ordinamento per confronti. Algoritmi lineari, counting sort, radix sort, bucket sort. Algoritmi di selezione, minimo, massimo, selezione in tempo medio lineare, selezione in tempo pessimo lineare.

Strutture dati: Code, pile, liste, heap, alberi binari di ricerca, alberi RB, heap binomiali, insiemi disgiunti, tecniche di estensione di una struttura dati.

Grafi: Definizione e rappresentazione di un grafo, visita in ampiezza, visita in profondità, ordinamento topologico, componenti connesse, alberi di copertura di costo minimo (Prim e Kruskal), cammini minimi a sorgente singola (Dijkstra e Bellman-Ford) e multipla (Floyd-Warshall e Johnson), flusso massimo (Ford-Fulkerson, Karp), matching massimale su grafo bipartito.

Lezione 1:Introduzione al corso, Elementi di complessità.

Lezione 2:Complessità degli algoritmi, Notazione asintotica O(f), Omega(f), e Theta(f).

Lezione 3: Algoritmi ricorsivi, Risoluzione di equazioni di ricorrenza (metodo iterativo, metodo di sostituzione, teorema principale).

Lezione 4: Algoritmi di ordinamento, Insertion sort, merge sort, Studio della complessità, Stabilità e ordinamento in loco.

Lezione 5: Algoritmi di ordinamento: heap sort.

Lezione 6: Algoritmi di ordinamento: quick sort, quick sort probabilistico, Limite inferiore alla complessità di ordinamento per confronti.

Lezione 7:Algoritmi di ordinamento lineari: counting sort, radix sort, bucket sort.

Lezione 8:Algoritmi di Selezione. Tempi medio e peggiore lineari.

Lezione 9: Strutture dati elementari. Stack, code, liste,
Alberi binari di ricerca

Lezione 10:RB-alberi.

Lezione 11: Estensione di una struttura dati. Alberi di intervalli.

Lezione 12:Heap binomiali.

Lezione 13:Strutture per insiemi disgiunti.

Lezione 14:Programmazione dinamica.

Lezione 15:Algoritmi greedy.

Lezione 16:Grafi: definizione e rappresentazione.

Lezione 17:Visita di grafi. BFS, DFS.

Lezione 18: Ordinamento topologico. Componenti connesse.

Lezione 19:Alberi di copertura di costo minimo. Algoritmi di Kruskal e Prim.

Lezione 20:Cammini minimi. Algoritmi di Dijkstra e Bellman-Ford per sorgente singola.

Lezione 21:Cammini minimi. Algoritmi di Floyd-Warshall e Johnson per sorgenti multiple.

Lezione 22:Flusso massimo. Algoritmo di Ford-Fulkerson. Matching massimale su grafo bipartito.

Reference books
Author Title Publisher Year ISBN Note
T. Cromen, C. Leiserson, R. Rivest, C. Stein Introduzione agli Algoritmi e Strutture Dati McGraw Hill 2005

Assessment methods and criteria

L'esame di teoria di algoritmi e strutture dati consiste di una esercitazione scritta di due ore contenente tre esercizi di difficoltà crescente chee cercano di valutare sia le conoscenze acquisite che le capacità di ragionamento nell'ambito della materia. L'esercitazione scritta si intende superata se lo studente ottiene una votazione di almeno 18/30 considerando che ogni esercizio vale 1/3 del punteggio totale.

All'esercitazione scritta lo studente può portare un foglio formato A4 scritto su entrambe le facciate a penna di proprio pugno. Su ogni facciata il foglio deve riportare nome, cognome, e numero di matricola. Non sono imposti limiti ai contenuti del foglio A4.

L'esame di algoritmi e strutture dati è superato a condizione che il candidato ottenga una valutazione positiva anche nel modulo di laboratorio. La votazione proposta sarà la media ponderata tra il risultato della prova di teoria (75%) e della prova di laboratorio (25%). Chi ottiene una valutazione finale di almeno 24/30 può sostenere una prova orale facoltativa. In tal caso il voto finale dell'esame sarà basato puramente sulla prova orale senza tenere in alcun conto l'esito delle prove scritte.

Studying