mercoledì 21 aprile 2010
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)
Archivio blog
-
▼
2010
(45)
-
▼
aprile
(12)
- Lezione del 28/04/2010
- Aggiornamento raccolta esercizi
- Lezione del 26/04/2010
- Lezione del 21/04/2010
- Ufficio oggetti smarriti
- Lezione del 15/04/2010
- Nuova versione della raccolta esercizi
- Lezione del 14/04/2010
- Lezione del 12/04/2010
- Nuova versione raccolta esercizi
- Lezione del 7/4/2010
- Lezione del 31/3/2010
-
▼
aprile
(12)
Post
Nessun commento:
Posta un commento