Iscriviti a:
Commenti sul post (Atom)
skip to main |
skip to sidebar
Secondo modulo
Informazioni personali
Argomenti trattati
I grafi e le loro proprietà: Definizioni, visite, componenti connesse, cicli.
Problemi su grafi non pesati: visite BFS e cammini minimi; visitia DFS, ricerca di cicli e ordinamento topologico nei grafi diretti aciclici; componenti connesse e componenti fortemente connesse.
Trattabilità ed intrattabilità dei problemi (P vs NP): Definizioni delle classi P ed NP; riduzioni polinomiali; non determinismo.
Il problema dei cammini minimi su grafi pesati: algoritmi di Dijkstra, Bellmann-Ford e Floyd-Warshall.
Problema del minimo albero coprente su grafi non diretti pesati: algoritmi di Prim e Kruskal.
Problemi su grafi diretti pesati: arborescenza minima e algoritmo di Edmonds; minimo sotto-grafo fortemente connesso, NP-completezza ed approssimazione.
Per maggiori dettagli si consulti le attività' svolte in ogni singola lezione.
Orario lezioni
Giovedì e venerdì dalle 12.30 alle 14.00.
Ricevimento studenti
- Lunedì ore 16.00
Date esami
TBA
Modalita' d'esame
Questo secondo modulo del corso prevede una prova scritta ed una prova orale alla quale potranno accedere solo gli studenti che avranno superato la prova scritta.
Gli studenti del vecchio ordinamento che hanno nel proprio piano di studi l'esame da 6 CFU potranno direttamente verbalizzare il voto ottenuto. Mentre per quelli del nuovo ordinamento il voto complessivo sara' dato dalla media dei voti ottenuti nei due moduli.
Materiale didattico
Etichette
- lezione (42)
- avviso (39)
- esercitazione (13)
- slides (5)
- Errata (1)
- nuovo ordinamento (1)
Post
2 commenti:
salve professore,
può, per cortesia, mettere i riferimenti del libro di Crescenzi riguardo gli argomenti svolti a lezione?
Non è che sia molto semplice individuali.
Grazie
Per quanto riguarda i cenni preliminari della prima lezione direi che il paragrafo 6.1 pag. 199 contiene tutto il necessario. La seconda lezione e parte della terza la ritroviamo tra i paragrafi 6.1.2 (rappresentazione di grafi e complessita' degli operatori di manipolazione) e 6.1.3 (prodotto tra matrici di adiacenza). L'ultimo argomento sul libro e' trattato in modo leggermente diverso in quanto si fornisce un algoritmo piu' efficiente. Per la visita dei grafi vedremo nelle prossime lezioni il paragrafo 7.4 (pag. 262).
Per quanto riguarda gli esercizi della seconda lezione presto li aggiungero' alla lista di esercizi scaricabile dalla "Materiale didattico"
Posta un commento