Argomenti
Logica, probabilità, teoria del calcolo, grafi e ottimizzazione: la matematica che sta sotto l'informatica, spiegata alla lavagna.
Matematica discreta
Logica, insiemi, relazioni, induzione, combinatoria e aritmetica modulare con esempi concreti.
Probabilità e statistica
Probabilità, distribuzioni, campioni, test, correlazione e gli errori statistici più comuni.
Teoria del calcolo
Automi, linguaggi formali, macchine di Turing, calcolabilità, complessità e P contro NP.
Grafi e ottimizzazione
Cammini minimi, alberi, flussi, programmazione lineare e dinamica, euristiche e metaeuristiche.
Articoli in evidenza
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.
Campionamento: metodi, dimensione del campione e distorsioni
Campionamento casuale, sistematico, stratificato e a grappoli: quanto deve essere grande il campione e come notare selezione, non risposta e copertura.
Approssimazione con garanzia: quando l'ottimo è NP-difficile
Rapporto di approssimazione, algoritmi con garanzia per copertura di vertici e commesso viaggiatore, schemi per lo zaino e limiti di inapprossimabilità.
Abbinamenti nei grafi bipartiti e problema dell'assegnamento
Come abbinare persone e compiti nel modo migliore: matching massimo con cammini aumentanti, teorema di König, assegnamento pesato e metodo ungherese.
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.
La distribuzione normale e la regola 68-95-99,7
La curva a campana spiegata in pratica: punteggi z, regola 68-95-99,7, calcolo delle code con Python e i casi in cui assumere la normalità è un errore.
La classe NP: verificatori, certificati e non determinismo
Che cosa vuol dire che un problema è in NP: le due definizioni equivalenti con verificatori e macchine non deterministiche, esempi ed equivoci.
Bellman-Ford: cammini minimi con pesi negativi e cicli
Bellman-Ford spiegato: perché ripetere n−1 passate, come scoprire i cicli negativi e dove servono davvero i pesi negativi, dai cambi all'instradamento.
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.
Legge dei grandi numeri e fallacia del giocatore
Cosa garantisce davvero la legge dei grandi numeri, perché il caso non «compensa» le serie negative e come i campioni piccoli producono risultati estremi.
Macchina di Turing: definizione formale, configurazioni, esempi
La macchina di Turing come modello matematico: nastro, testina, funzione di transizione, configurazioni, accettazione e un esempio svolto passo dopo passo.
Distanza di edit: Levenshtein e confronto tra testi
Quanto sono diverse due stringhe: distanza di Levenshtein con la programmazione dinamica, allineamento, sottosequenza comune più lunga e diff.