Visita in ampiezza (DFS) e sue applicazioni nei grafi non diretti: connettività, ricerca di componenti connesse, ricerca di cicli.
Problematiche nella ricerca di cicli in grafi diretti.
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
Nessun commento:
Posta un commento