Matematica Discreta

📚 Riepilogo del contenuto

Un corso introduttivo di matematica discreta per gli studenti di matematica e informatica. Copre argomenti fondamentali come logica, insiemi, tecniche dimostrative, algoritmi, teoria dei numeri, combinatoria, teoria dei grafi e automi. Il corso mette in risalto il ragionamento matematico e le abilità di risoluzione dei problemi necessarie per studi avanzati in informatica.

Padroneggia la logica e le strutture che formano la base dell'informatica.

Autore: Richard Johnsonbaugh

Ringraziamenti: Revisionisti tra cui Venkata Dinavahi, Matthew Elsey, Christophe Giraud-Carrier, Yevgeniy Kovchegov, Filix Maisch, Tyler McMillen, Christopher Storm, Donald Vestal e Guanghua Zhao. Supporto da parte del personale Pearson: Deirdre Lynch, Jeff Weidenaar, Lauren Morse e altri.

🎯 Obiettivi di apprendimento

1. Eseguire operazioni sugli insiemi, inclusi differenze e complementi, e verificare identità insiemistiche tramite diagrammi di Venn e Teorema 1.1.22.
2. Costruire e valutare tabelle di verità per proposizioni che coinvolgono negazione, disgiunzione e affermazioni condizionali.
3. Applicare regole di inferenza e ragionamento deduttivo per determinare la validità di argomenti logici.
4. Definire e applicare i componenti di un sistema matematico, inclusi assiomi, definizioni e teoremi.
5. Costruire dimostrazioni dirette, dimostrazioni per contraddizione e dimostrazioni per casi per proposizioni algebriche e insiemistiche.
6. Utilizzare il Principio di Induzione Matematica e l'Induzione Forte per dimostrare identità, proprietà di divisibilità e correttezza di algoritmi.
7. Definire e classificare funzioni (iniettive, suriettive, biiettive) e svolgere operazioni come composizione e inversione.
8. Applicare notazioni di sequenze, concatenazione di stringhe e regole ricorsive per modellare insiemi di dati discreti.
9. Analizzare relazioni binarie per proprietà come riflessività, simmetria e transitività utilizzando sia digrafi che rappresentazioni matriciali.
10. Definire un algoritmo e verificarne le sette proprietà fondamentali (Input, Output, Precisione, Determinismo, Finitezza, Correttezza e Generalità).

🔹 Lezione 1: Fondamenti della logica e della teoria degli insiemi

Panoramica: Questa lezione stabilisce i blocchi fondamentali della matematica discreta, concentrandosi sulla manipolazione rigorosa degli insiemi e sulle strutture formali della logica. Gli studenti passeranno dalle operazioni sugli insiemi e dalle identità agli argomenti logici, alla valutazione di proposizioni condizionali e all’analisi di quantificatori annidati. Questi concetti forniscono il quadro essenziale per la progettazione di algoritmi, la teoria dei database e la verifica formale in informatica e ingegneria.

Risultati dell’apprendimento:

• Eseguire operazioni sugli insiemi, incluse differenze e complementi, e verificare identità insiemistiche tramite diagrammi di Venn e Teorema 1.1.22.
• Costruire e valutare tabelle di verità per proposizioni che coinvolgono negazione, disgiunzione e affermazioni condizionali.
• Applicare regole di inferenza e ragionamento deduttivo per determinare la validità di argomenti logici.

🔹 Lezione 2: Tecniche dimostrative matematiche

Panoramica: Questa lezione copre i metodi formali utilizzati per stabilire la validità di affermazioni matematiche e il rigore logico richiesto in informatica e matematica. Gli studenti passeranno dai sistemi matematici fondamentali e dalle dimostrazioni dirette alle tecniche sofisticate come le dimostrazioni per risoluzione, l’induzione matematica (compresa l’induzione forte) e l’applicazione degli invarianti di ciclo nella verifica algoritmica.

Risultati dell’apprendimento:

• Definire e applicare i componenti di un sistema matematico, inclusi assiomi, definizioni e teoremi.
• Costruire dimostrazioni dirette, dimostrazioni per contraddizione e dimostrazioni per casi per proposizioni algebriche e insiemistiche.
• Utilizzare il Principio di Induzione Matematica e l’Induzione Forte per dimostrare identità, proprietà di divisibilità e correttezza algoritmica.

🔹 Lezione 3: Funzioni, sequenze e relazioni

Panoramica: Questa lezione copre le strutture matematiche fondamentali usate per modellare dati e processi in informatica. Procede dalla definizione di funzioni e dei loro diversi tipi (iniettive, suriettive, biiettive) allo studio di sequenze, stringhe e delle proprietà formali delle relazioni binarie. Gli studenti esploreranno applicazioni pratiche come funzioni hash, cifre di controllo ISBN, pianificazione di compiti tramite ordini parziali e la rappresentazione di relazioni attraverso matrici e basi di dati.

Risultati dell’apprendimento:

• Definire e classificare funzioni (iniettive, suriettive, biiettive) e svolgere operazioni come composizione e inversione.
• Applicare notazioni di sequenze, concatenazione di stringhe e regole ricorsive per modellare insiemi di dati discreti.
• Analizzare relazioni binarie per proprietà come riflessività, simmetria e transitività utilizzando sia digrafi che rappresentazioni matriciali.

🔹 Lezione 4: Analisi degli algoritmi e complessità

Panoramica: Questa lezione copre la definizione fondamentale e le proprietà degli algoritmi, la loro implementazione in ricerca e ordinamento (specificamente ricerca testuale e ordinamento per inserimento), e i rigorosi framework matematici usati per analizzarne l’efficienza. Gli studenti esploreranno notazioni asintotiche, tassi di crescita delle funzioni e meccanismi di risoluzione ricorsiva, inclusi strategie divide-et-impera come il rivestimento di scacchiere e sequenze basate su Fibonacci.

Risultati dell’apprendimento:

• Definire un algoritmo e verificarne le sette proprietà fondamentali (Input, Output, Precisione, Determinismo, Finitezza, Correttezza e Generalità).
• Applicare le notazioni Big-O, Omega e Theta per esprimere la complessità temporale e spaziale degli algoritmi.
• Analizzare scenari ottimali, peggiori e medi usando tecniche come dimezzamento ripetuto e ordinamento polinomiale.

🔹 Lezione 5: Introduzione alla teoria dei numeri e alla crittografia

Panoramica: Questa lezione esplora i principi fondamentali della teoria dei numeri, che vanno dalle proprietà basilari di divisori e numeri primi ai complessi algoritmi che stanno alla base delle comunicazioni sicure moderne. Gli studenti padroneggeranno la meccanica matematica del massimo comun divisore (MCD), delle conversioni di base e dell’esponenziazione modulare per comprendere e implementare il sistema crittografico RSA a chiave pubblica.

Risultati dell’apprendimento:

• Definire e applicare i concetti di divisibilità, primalità e Teorema Fondamentale dell’Arithmetic.
• Eseguire conversioni efficienti tra sistemi numerici decimale, binario e esadecimale.
• Eseguire l’Algoritmo Euclideo e la sua forma estesa per trovare MCD e combinazioni lineari (sa + tb).

🔹 Lezione 6: Metodi di conteggio e probabilità discreta

Panoramica: Questa lezione esplora le tecniche fondamentali per contare strutture finite e l’applicazione di queste tecniche alla probabilità discreta. Gli studenti passeranno dai principi basilari di addizione e moltiplicazione a concetti avanzati come numeri di Catalan, numeri di Stirling e Teorema del binomio. La lezione si conclude con il Principio del piccione e le sue varie forme, fornendo un quadro rigoroso per dimostrare l’esistenza di configurazioni specifiche in sistemi discreti.

Risultati dell’apprendimento:

• Applicare i Principi di Addizione, Moltiplicazione e Inclusione-Esclusione per risolvere problemi di conteggio complessi.
• Differenziare e calcolare permutazioni e combinazioni, compresi i casi con oggetti identici e ripetizioni.
• Utilizzare algoritmi generativi per permutazioni e combinazioni in ordine lessicografico.

🔹 Lezione 7: Relazioni di ricorrenza

Panoramica: Questa lezione esplora la teoria e l’applicazione delle relazioni di ricorrenza in matematica e informatica. Gli studenti impareranno a risolvere queste relazioni usando iterazione e equazioni caratteristiche per entrambi i casi omogenei e non omogenei. Inoltre, la lezione dimostra come le relazioni di ricorrenza siano strumenti essenziali per analizzare la complessità temporale di algoritmi ricorsivi come Selection Sort, Binary Search e Merge Sort.

Risultati dell’apprendimento:

• Risolvere relazioni di ricorrenza usando il Metodo dell’Iterazione e le Equazioni Caratteristiche (per radici distinte e uguali).
• Modellare e risolvere problemi matematici classici, inclusi il Torre di Hanoi, la Sequenza di Fibonacci (Rapporto Aureo) e le Derangements.
• Analizzare la complessità temporale nel caso peggiore di algoritmi ricorsivi usando relazioni di ricorrenza.

🔹 Lezione 8: Teoria dei grafi e algoritmi dei cammini minimi

Panoramica: Questa lezione esplora i principi fondamentali della Teoria dei Grafi, che vanno dalle definizioni di base di grafi semplici e pesati fino a soluzioni algoritmiche complesse per cammini minimi e identificazione di cicli. Gli studenti esamineranno proprietà strutturali come planarità, connettività e isomorfismo mentre applicano questi concetti a problemi classici come il problema dei ponti di Königsberg, il Problema del Commesso Viaggiatore (TSP) e il puzzle Instant Insanity.

Risultati dell’apprendimento:

• Definire e distinguere tra tipi di grafi, inclusi semplici, pesati, completi, bipartiti e n-cubi.
• Analizzare la connettività del grafo per identificare cicli di Euler, cicli di Hamilton e determinare cammini minimi usando l’algoritmo di Dijkstra.
• Applicare rappresentazioni matriciali (adiacenza e incidenza) e invarianti grafici per verificare isomorfismi e planarità.

🔹 Lezione 9: Alberi e algoritmi di ricerca

Panoramica: Questa lezione copre le proprietà fondamentali, le caratterizzazioni e le applicazioni degli alberi in informatica e matematica. Gli studenti esploreranno alberi radicati e binari, algoritmi di albero ricoprente (BFS/DFS), tecniche di ottimizzazione come l’algoritmo di Prim per alberi ricoprenti minimi, e framework decisionali come backtracking, ordinamenti a torneo e alberi di gioco con procedura minimax.

Risultati dell’apprendimento:

• Definire e identificare alberi radicati, i loro livelli, altezza e strutture gerarchiche nei sistemi reali.
• Caratterizzare gli alberi in base a connettività, aciclicità e rapporto tra spigoli e vertici.
• Implementare e tracciare algoritmi per alberi ricoprenti (BFS, DFS), alberi ricoprenti minimi (Prim) e costruzione di alberi binari di ricerca.

🔹 Lezione 10: Modelli di rete e ottimizzazione del flusso

Panoramica: Questa lezione copre il modello matematico delle reti di trasporto, concentrandosi su come le risorse (flusso) si muovono attraverso un grafo orientato da una sorgente a una destinazione. Dettaglia le regole di conservazione del flusso, i passi algoritmici per massimizzare la capacità di throughput, il legame tra tagli di rete e capacità di flusso, e l’applicazione di questi principi per risolvere problemi di accoppiamento in grafi bipartiti.

Risultati dell’apprendimento:

• Definire e verificare le proprietà di una rete di trasporto e assegnazioni di flusso valide.
• Eseguire l’Algoritmo del Flusso Massimo (Algoritmo 10.2.4) per trovare il throughput ottimale.
• Applicare il Teorema del Flusso Massimo - Taglio Minimo per dimostrare l’ottimalità del flusso usando partizioni della rete.

🔹 Lezione 11: Algebra booleana e circuiti logici

Panoramica: Questa lezione esplora le fondamenta matematiche della logica digitale, concentrandosi su come l'algebra booleana fornisca un linguaggio formale per progettare e semplificare circuiti combinatori. Gli studenti impareranno a tradurre tra porte logiche, circuiti commutatori e espressioni booleane, applicando infine questi strumenti per sintetizzare funzioni complesse e costruire componenti aritmetici essenziali come sommatori e logica del complemento a due.

Risultati dell’apprendimento:

• Progettare e analizzare circuiti combinatori usando porte logiche standard (AND, OR, NOT) e configurazioni commutatrici.
• Applicare le leggi dell'algebra booleana e il Teorema Duale per dimostrare l'equivalenza di circuiti e semplificare espressioni.
• Sintetizzare funzioni booleane da tabelle di verità in Forma Normale Disgiuntiva (DNF) e Forma Normale Congiuntiva (CNF).

🔹 Lezione 12: Automi, grammatiche e linguaggi formali

Panoramica: Questa lezione esplora le fondamenta matematiche del calcolo, partendo da circuiti sequenziali e macchine a stati finiti che modellano la memoria interna tramite ritardi di unità di tempo. Copre la definizione formale e la classificazione delle grammatiche strutturate in frase (Tipi 1, 2 e 3), l'applicazione della Notazione di Backus (BNF) e l'uso specializzato delle grammatiche di Lindenmayer per la generazione di frattali. Infine, stabilisce il rapporto critico tra automi a stati finiti deterministici e nondeterministici e i linguaggi formali che accettano.

Risultati dell’apprendimento:

• Analizzare e progettare macchine a stati finiti (FSM) e automi (FSA/NFA) usando diagrammi di transizione e funzioni di stato.
• Classificare grammatiche nella gerarchia di Chomsky e derivare stringhe usando regole di produzione e notazione BNF.
• Modellare strutture autosimili come la neve di Koch usando grammatiche di Lindenmayer e regole di sostituzione simultanea.