PROGRAMMA DI MATEMATICA DISCRETA (A.A. 2008/09) (Prof. Fabio Di Franco)
Elementi di logica: proposizioni e predicati, operazioni fra predicati. Insiemistica: insiemi ed operazioni fra insiemi, sottoinsiemi, prodotto cartesiano. Relazione fra insiemi. Funzioni:
funzioni iniettive, surgettive, biunivoche, funzione inversa di una biunivoca, composizione di funzioni. Cardinalità di un insieme: cardinalità del numerabile e del continuo. Principio delle scelte multiple. Numero delle funzioni fra insiemi finiti. Numero delle funzioni iniettive e biunivoche fra insiemi finiti. Permutazioni. Determinante di una matrice quadrata. Principio di induzione. Rappresentazione di un numero naturale in base b>1. Divisori e multipli. Massimo comune divisore. Algoritmo Euclideo. Numeri primi e loro proprietà. Teorema di fattorizzazione unica. Disposizioni e combinazioni. Coefficiente binomiale e triangolo di Tartaglia-Pascal. Sviluppo della potenza del binomio. Principio dei cassetti. Principio della somma e di inclusione-esclusione: il problema della segretaria distratta e la funzione di Eulero.
Partizioni, numeri di Stirling, numero delle funzioni surgettive fra insiemi finiti. Relazioni di equivalenza e congruenza modulo n. Grafi. Teorema di Eulero sui cammini ciclici Euleriani.
Numero cromatico. Componenti connesse. Caratterizzazione dei grafi con numero cromatico 2.
Cammini Hamiltoniani e teorema di esistenza nei grafi completi.
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
