Algebra Computazionale (DM 509)
Programma del a.a. 2009-2010 per il corso di Laurea in Informatica.
Docente: J. van Bon
- Relazioni. Relazione riflessiva, simmetrica, antisimmetrica, transitiva. Matrice d'incidenza, digrafo. Chiusura riflessiva, simmetrica, transitivo di una relazione. Relazioni di equivalenza. Posets e reticoli. Diagramma di Hasse. Topological sorting.
- Teoria dei grafi. Introduzione e termonologia. Rappresentazioni e isomorfismi. Connessione. Cammino Euleriano e Hamiltoniano. Grafi planari. Colorazioni di grafi. Algoritmo di Dijkstra.
- Teoria degli alberi. Introduzione e applicazioni. Alberi di supporto e alberi di supporto minimali. Depth-first search, Breadth-first search. Algoritmi di Kruskal e Prim.
Testo
K.H. Rosen, Discrete Mathematics and its applications, McGraw-Hill, 1999.
- N.L. Biggs, Discrete Mathematics, Oxford university press, 2002.