Matematica discreta
Logica, insiemi, relazioni, induzione, combinatoria e aritmetica modulare con esempi concreti.
Algoritmo di Euclide esteso e inverso modulare, passo per passo
MCD con l'algoritmo di Euclide, identità di Bézout, algoritmo esteso per l'inverso modulare e teorema cinese del resto, con esempi svolti e codice.
Aritmetica modulare e congruenze: l'aritmetica dell'orologio
Congruenze modulo n, operazioni con i resti, resti negativi nei linguaggi di programmazione, potenze modulari e piccolo teorema di Fermat, con esempi.
Infiniti di misure diverse: numerabilità e diagonale di Cantor
Perché pari e naturali sono «tanti quanti», perché i razionali sono numerabili e i reali no: biiezioni, argomento diagonale di Cantor e conseguenze.
Cifre di controllo: Luhn, ISBN e IBAN spiegati con i resti
Come funzionano le cifre di controllo di carte, ISBN e IBAN: algoritmo di Luhn, pesi modulo 10 e 11, verifica modulo 97 e quali errori intercettano.
Combinazioni con ripetizione: il metodo delle stelle e barre
Contare scelte con elementi ripetuti: il metodo delle stelle e barre, soluzioni intere di un'equazione, vincoli minimi e massimi, anagrammi.
Forme normali CNF e DNF: cosa sono e come si ottengono
Forma normale congiuntiva e disgiuntiva spiegate con esempi: letterali, clausole, come ricavarle da una tavola di verità e perché le usano i SAT solver.
Funzioni iniettive, suriettive e biiettive con esempi
Dominio, codominio e immagine; quando una funzione è iniettiva, suriettiva o biiettiva, come si inverte e perché conta per hash, chiavi e codifiche.
Implicazione, inversa e contronominale: non confonderle mai
Differenza tra implicazione, inversa, contraria e contronominale, condizione necessaria e sufficiente, con esempi presi dal codice e dalla vita reale.
Induzione forte e invarianti di ciclo: dimostrare il codice
Induzione forte, induzione strutturale e invarianti di ciclo: come si usano per dimostrare teoremi e la correttezza di algoritmi iterativi, con esempi.
Il principio di induzione matematica con esempi svolti
Come funziona una dimostrazione per induzione: caso base, ipotesi e passo induttivo, esempi svolti su somme, disuguaglianze e divisibilità, errori tipici.
Insieme delle parti e prodotto cartesiano spiegati bene
Cosa sono l'insieme delle parti e il prodotto cartesiano, perché hanno 2^n e n·m elementi, e come si usano per permessi, configurazioni e test combinatori.
Leggi di De Morgan ed equivalenze logiche per semplificare
Le equivalenze logiche fondamentali, le leggi di De Morgan e come usarle per semplificare condizioni nel codice e nelle query senza cambiarne il senso.
Logica proposizionale: connettivi e tavole di verità spiegati
Cos'è una proposizione, come funzionano negazione, congiunzione, disgiunzione e implicazione, e come costruire una tavola di verità senza errori.
Operazioni tra insiemi: unione, intersezione e differenza
Insiemi, appartenenza e inclusione, unione, intersezione, differenza e complemento spiegati con esempi pratici, diagrammi di Venn e codice Python.
Ordini parziali e diagrammi di Hasse: guida pratica
Cos'è un ordine parziale, come disegnare un diagramma di Hasse, la differenza tra massimale e massimo, ordini totali, reticoli ed esempi informatici.
Permutazioni, disposizioni e combinazioni: quale usare
Quando l'ordine conta e quando no: permutazioni, disposizioni e combinazioni semplici, coefficiente binomiale, triangolo di Tartaglia ed esempi pratici.
Principi di conteggio: regola della somma e del prodotto
Le regole base del calcolo combinatorio: somma, prodotto, complemento e divisione, applicate a password, PIN, codici identificativi e tavoli rotondi.
Il principio dei cassetti: un'idea semplice e sorprendente
Il principio dei cassetti nella forma semplice e generalizzata, con dimostrazioni sorprendenti e applicazioni reali a compressione, hash e checksum.
Principio di inclusione-esclusione: contare senza doppioni
Come contare l'unione di insiemi che si sovrappongono: inclusione-esclusione con due, tre e n insiemi, divisibilità, scombussolamenti e funzione di Eulero.
Relazioni binarie: riflessiva, simmetrica, transitiva
Cos'è una relazione binaria e come riconoscere le proprietà riflessiva, simmetrica, antisimmetrica e transitiva con matrici, grafi ed esempi concreti.
Logica dei predicati: quantificatori, negazione e ordine
Predicati, dominio, quantificatore universale ed esistenziale: come negarli correttamente e perché l'ordine dei quantificatori cambia il significato.
Regole di inferenza: modus ponens, tollens e risoluzione
Le regole di inferenza della logica: modus ponens, modus tollens, sillogismi e risoluzione, con un esempio di deduzione formale costruita passo per passo.
Relazioni di ricorrenza: dalla definizione alla forma chiusa
Cosa sono le relazioni di ricorrenza e come risolverle: sostituzione iterata, equazione caratteristica, torre di Hanoi, Fibonacci e divide et impera.
Relazioni di equivalenza, classi e partizioni di un insieme
Relazioni di equivalenza, classi di equivalenza e partizioni: il legame tra i tre concetti, esempi concreti e la struttura union-find per calcolarle.
Tecniche di dimostrazione: diretta, per assurdo e per casi
Le principali tecniche di dimostrazione in matematica discreta con esempi completi: diretta, per assurdo, per casi, costruttiva e uso dei controesempi.