PROGRAMMA DI MATEMATICA DISCRETA (A.A. 2009/10) (Prof. Fabio Di Franco)
Elementi di logica: proposizioni e predicati, operazioni fra predicati. Tecniche dimostrative.
Insiemistica: insiemi ed operazioni fra insiemi, sottoinsiemi, insieme delle parti di un insieme.
Prodotto cartesiano. Relazioni fra insiemi. Funzioni: funzioni iniettive, surgettive, biunivoche, funzione inversa di una biunivoca, composizione di funzioni. Cardinalità di un insieme finito.
Principio delle scelte multiple. Permutazioni. Determinante di una matrice quadrata. Numero delle funzioni fra insiemi finiti. Numero delle funzioni iniettive e biunivoche fra insiemi finiti..
Principio di induzione. Algoritmo della divisione fra numeri naturali. Rappresentazione di un numero naturale in base b>1. Divisori e multipli. Massimo comune divisore. Algoritmo Euclideo delle divisioni successive. Numeri primi. Teorema di fattorizzazione unica.
Cardinalità di un insieme infinito, cardinalità del numerabile e del continuo. Disposizioni e combinazioni, semplici e con ripetizione. Coefficiente binomiale e triangolo di Tartaglia- Pascal. Sviluppo della potenza del binomio. Principio dei cassetti. Principio della somma e principio di inclusione-esclusione. Il problema della segretaria distratta. La funzione di Eulero.
Partizioni, numeri di Stirling, numero delle funzioni surgettive fra insiemi finiti. Grafi. Teorema di Eulero sull’esistenza di cammini ciclici Euleriani. Numero cromatico di un grafo.
Componenti connesse di un grafo. Caratterizzazione dei grafi con numero cromatico 2. Grafi orientati. Cammini Hamiltoniani e teorema di esistenza nei grafi completi. Il paradosso del torneo sportivo. Matrice di adiacenza e di incidenza di un grafo. Prodotto righe per colonne di matrici e potenza di una matrice. Teorema sull’esistenza di cammini fra vertici. Proprietà dei gradi dei vertici. Grafi planari e relative proprietà. Formula di Eulero. Teorema di Kuratowsi.
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. Relazioni di equivalenza e classi di equivalenza. Congruenza modulo n. Insiemi dotati di operazione, semigruppi, 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. Leggi di cancellazione. Potenza di un elemento di un gruppo.
Teorema di Lagrange. 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.
Libri di testo:
Appunti del corso (disponibili online)
Alberto Facchini “Algebra e Matematica Discreta” Ed. Decibel-Zanichelli
