Appunti degli studenti per corsi ed esami del Prof. Cutello Vincenzo

Il documento di Matematica discreta contiene tutto il programma dall'introduzione della logica proposizionale ai grafi e alberi , con spiegazioni semplici, trucchi per il calcolo ,esercizi ed esempi Parte I: Insiemi e Relazioni: Introduzione alla Logica Proposizionale e agli operatori di base. Il concetto di insieme e le proprietà di base. Insiemi ed operazioni tra di essi. Dimostrazione diretta. Esercizi su Insiemi Famiglie di insiemi. Insieme prodotto. Paradossi. Relazioni binarie e funzioni. Relazioni di Equivalenza. Relazioni d’ordine, Rappresentazione di insiemi finiti Esercizi e Problemi su Relazioni e Famiglie di Insiemi. Il Problema del Hitting Set Caso Studio: Famiglie di insiemi chiuse e la congettura Union-Closed Parte II: Fondamenti di Teoria dei Numeri e metodologie di dimostrazione : Numeri Interi Introduzione e operazioni sui numeri interi. Principio di Induzione. Divisione tra interi. Divisibilità MCD ed Algoritmo di Euclide. Numeri Primi e Coprimi. Criteri di divisibilità. Problemi ed Esercizi Aritmetica Modulare Congruenze. Proprietà delle congruenze. Invarianza rispetto a somma e prodotto: conseguenze ed esercizi Funzione φ di Eulero Definizione e formula generale. Il Teorema di Eulero. Esempi ed esercizi Applicazioni dell’Aritmetica modulare La prova del 9. Codici ISBN e Carte di Credito. Cifrari monoalfabetici a trasposizione Teoria dei numeri e problemi aperti Numeri primi di Mersenne e numeri perfetti. Numeri primi gemelli. La congettura di Goldbach Caso studio: il problema 3x + 1 (Congettura di Collatz) Parte III: calcolo combinatorio e probabilità discrete: Calcolo combinatorio Introduzione. Disposizioni e combinazioni. Permutazioni e Combinazioni. Teorema Binomiale. Il triangolo di Pascal. Combinazioni con ripetizione. Esercizi. Principio dei cassetti (Pigeonhole principle) Probabilità Discrete Introduzione. Formalizzazione Matematica. Assiomi e Proprietà. La regola di Bayes. Problemi d’urna. Esercizi. Variabili casuali. Problemi ed esercizi Caso Studio: Il paradosso di Monty Hall, giochi e paradossi probabilistici. Parte IV: Grafi e Alberi: Introduzione alla Teoria dei Grafi Introduzione: strette di mano e passeggiate su ponti. Definizioni di base. Gradi di un nodo. Classi particolari di grafi: Grafi regolari, Grafi completi, Grafi Bipartiti. Sottografi, Isomorfismi e Omeomorfismi: Definizione di sottografo, Isomorfismi, Omeomorfismi. Percorsi, cammini e cicli. Grafi connessi. Rappresentazione di un grafo. Numero di percorsi tra nodi. Grafi Euleriani ed Hamiltoniani. Grafi pesati. Il problema del commesso viaggiatore. Grafi planari. Colorazione di un grafo. Alberi: definizioni fondamentali e classi particolari di alberi. Casi studio: problemi combinatori su grafi.