Grafi e ottimizzazione
Cammini minimi, alberi, flussi, programmazione lineare e dinamica, euristiche e metaeuristiche.
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.
Albero ricoprente minimo: gli algoritmi di Kruskal e Prim
Come collegare tutti i nodi di una rete al costo minimo: la proprietà del taglio, gli algoritmi di Kruskal con union-find e di Prim con heap, esempi e usi.
Algoritmi greedy: quando la scelta avida è davvero ottima
Algoritmi greedy con esempi: selezione di intervalli, codici di Huffman, scadenze, controesempi e come dimostrare che una scelta avida è davvero ottima.
Algoritmo A*: cercare il percorso con un'euristica ammissibile
A* unisce Dijkstra e una stima della distanza residua: euristiche ammissibili e consistenti, distanza di Manhattan, griglie e compromessi di velocità.
Algoritmo di Dijkstra: cammini minimi con pesi non negativi
Come funziona l'algoritmo di Dijkstra: rilassamento, coda di priorità con heap, perché richiede pesi non negativi e come applicarlo a mappe e reti reali.
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.
Cammini euleriani e problema del postino cinese
Da Königsberg ai giri di raccolta rifiuti: quando esiste un cammino che usa ogni arco una volta, l'algoritmo di Hierholzer e il postino cinese.
Colorazione dei grafi: orari, frequenze e registri senza conflitti
La colorazione dei grafi applicata a orari d'esame, frequenze radio e allocazione dei registri: numero cromatico, greedy, DSatur e limiti pratici.
Commesso viaggiatore: euristiche costruttive e 2-opt
Il commesso viaggiatore in pratica: vicino più prossimo, inserimento, approssimazione con l'albero ricoprente, mossa 2-opt e limiti inferiori.
Componenti fortemente connesse: Kosaraju e Tarjan a confronto
Cosa sono le componenti fortemente connesse di un grafo orientato, come trovarle con Kosaraju e Tarjan e perché il grafo condensato semplifica molto.
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.
Dualità nella programmazione lineare e prezzi ombra
Ogni programma lineare ha un gemello duale: come costruirlo, cosa dicono dualità debole e forte, gli scarti complementari e come leggere i prezzi ombra.
Floyd-Warshall: le distanze minime tra tutte le coppie
Floyd-Warshall calcola le distanze minime tra ogni coppia di vertici con tre cicli annidati: idea, codice, ricostruzione dei percorsi e alternative.
Flusso massimo e taglio minimo: Ford-Fulkerson ed Edmonds-Karp
Reti di flusso, capacità e cammini aumentanti: come funzionano Ford-Fulkerson ed Edmonds-Karp e perché il flusso massimo è uguale al taglio minimo.
Che cos'è un grafo: vertici, archi e tipi principali
Vertici, archi, grado, grafi orientati, pesati e bipartiti: il vocabolario di base della teoria dei grafi spiegato con esempi presi da reti e mappe reali.
Metaeuristiche: simulated annealing, tabu search e genetici
Come uscire dagli ottimi locali: ricerca locale, simulated annealing, tabu search e algoritmi genetici, con esempi, parametri ed errori comuni.
Il metodo del simplesso spiegato senza formule pesanti
Come il simplesso risolve un programma lineare saltando da un vertice all'altro: forma standard, variabili di scarto, tableau, pivot e casi particolari.
Ordinamento topologico: mettere in fila le dipendenze di un DAG
Ordinamento topologico nei grafi orientati aciclici: algoritmo di Kahn, versione con DFS, rilevamento dei cicli e usi in build e pianificazione.
Il problema dello zaino: programmazione dinamica e varianti
Il problema dello zaino 0/1 risolto con la programmazione dinamica: tabella, ricostruzione degli oggetti, memoria ridotta, versione frazionaria e varianti.
Programmazione dinamica: sottoproblemi, memoization e tabelle
I principi della programmazione dinamica: sottostruttura ottima, sottoproblemi sovrapposti, memoization contro tabulazione e un metodo in cinque passi.
Programmazione lineare intera e branch and bound
Variabili intere: perché arrotondare non basta, variabili binarie, rilassamento lineare, branch and bound, piani di taglio e gap di ottimalità.
Programmazione lineare: come modellare un problema reale
Variabili decisionali, funzione obiettivo e vincoli: come tradurre un problema di produzione o di dieta in un modello di programmazione lineare.
Rappresentare un grafo: matrice e liste di adiacenza
Matrice di adiacenza, liste di adiacenza e lista di archi a confronto: memoria occupata, costo delle operazioni e quale scegliere in base al grafo reale.
Visita in ampiezza (BFS): livelli, code e cammini più corti
Come funziona la visita in ampiezza: la coda, i livelli di distanza, i cammini più corti nei grafi non pesati e gli usi pratici, dai labirinti alle reti.
Visita in profondità (DFS): pila, ricorsione e componenti
La visita in profondità spiegata passo passo: ricorsione o pila esplicita, tempi di scoperta e di fine, componenti connesse e ricerca dei cicli nei grafi.