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.