PROGRAMMA DI MATEMATICA DISCRETA II (A.A. 2008/09) (Prof. Fabio Di Franco)
Matrice di adiacenza di un grafo e relazione con l’esistenza di cammini fra vertici. Proprietà dei gradi dei vertici. Grafi planari e relative proprietà. Applicazioni della teoria dei grafi: problema dell’handshaking e problema del postino cinese. Disegni e 2-disegni. Piani proiettivi. Il problema degli ufficiali di Eulero e i quadrati greco-latini. Insiemi dotati di operazione, monoidi, gruppi. Il gruppo degli elementi simmetrizzabili di un monoide. Relazioni di equivalenza compatibili con una operazione ed operazioni nell’insieme delle classi di congruenza. Complessità di un algoritmo. Numero d’oro e successione di Fibonacci.
Complessità dell’algoritmo Euclideo. Potenze di un elemento di un gruppo. Teorema di Eulero- Fermat e Piccolo Teorema di Fermat. Costruzione di quadrati greco-latini di ordine dispari.
Sistemi crittografici: il sistema di Cesare, il sistema di Vigenère, il sistema one-time pad.
Sistemi crittografici a chiave pubblica: il sistema RSA. Algoritmo dell’esponenziazione modulare. Il test di primalità di Rabin-Miller.
Libri di testo:
Appunti del corso (disponibili online)
Alberto Facchini “Algebra e Matematica Discreta” Ed. Decibel-Zanichelli
