Materiali Didattici

Lezioni & Slides 2023-2024

Parte I: I Mattoni del Calcolare: Iterazione, Ricorsione e Memoria

• Lezione 1 [26/9/23]: Problemi, Macchine e Algoritmi
  • 0ω) Presentazione e Informazioni Pratiche
  • 1a) Introduzione al Pensiero Computazionale
  • 1b) Problemi elementari e pseudocodice
• Lezione 2 [29/9/23]: Indagini su un programma iterativo
  • 2a) Specifiche e Correttezza: asserzioni logiche, precondizioni, postcondizioni, invarianti.
  • 2b) Progettazione di programmi con asserzioni logiche.
  • 2c) Esercitazione 1: Esercizi su iterazione e alcune soluzioni.
• Lezione 3 [3/10/23]: Induzione & Ricorsione.
  • 3a) Iterare è umano, Ricorrere è divino.
  • 3b) Il lato oscuro della ricorsione
• Lezione 4 [6/10/23]: Esecutori e complessità.
  • 4a) Introduzione alla complessità computazionale.
  • 4b) Un esecutore un po' particolare
  • 4c) Esercitazione 2: Esercizi su ricorsione e alcune soluzioni.
• Lezione 5 [10/10/23]: Introduzione ai vettori.
  • 5a) Vettori: generalità e asserzioni logiche sui vettori.
  • 5b) Progetto di programmi base su vettori: ricerca, verifica, max/min
• Lezione 6 [13/10/23]: Introduzione ai vettori.
  • 6a) L'importanza di essere ordinati: ricerca binaria e altri problemi.
  • 6b) Il problema dell'ordinamento I: Ordinamenti Naif
  • 6c) Esercitazione 3: Esercizi su vettori e alcune soluzioni.
• Lezione 7 [17/10/23]: Progettazione di programmi corretti: revisione.
  • 7a) Il problema dell'ordinamento II: Limitazioni Inferiori e un algoritmo ottimo.
  • 7b) Esercitazione 3-bis: Soluzioni di esercizi in vista dell'esonero.
• Lezione 8 [20/10/23]: Primo Esonero e prime perle.
  • 8a) Primo Esonero: Testo e le relative Soluzioni.
  • 8b) Un grande classico: Segmento di somma massima.
  • 8c) Intermezzo: Esercizi di Stile in C.

Parte II: Problemi di Ordinamento, Ricerca, Divide et Impera

• Lezione 9 [24/10/23]: Ideologia Divide et Impera.
  • 9a) Complessità di algoritmi ricorsivi: Equazioni di Ricorrenza
  • 9b) Da mergeSort a quickSort
• Lezione 10 [31/10/23]: Oltre i limiti inferiori.
  • 10a) Complessità del caso medio di quickSort
  • 10b) Ordinamenti "quasi" lineari: countingSort
• Lezione 11 [2/11/23]: Meglio veloci che ottimi.
  • 11a) Ottimizzazioni di mergeSort e quickSort
  • 11b) Esercitazione 4: Esercizi su mergeSort/merge e soluzioni appl. ideologia merge
• Lezione 12 [3/11/23]: Ideologia Divide et Impera.
  • 12a) Alcune problemi risolti con divide et impera: minimo, moltiplicazione, fibonacci veloce
  • 12b) Un assaggio di ricerca su matrici
  • 12c) Esercitazione 5: Esercizi su quicksort/partiziona/k-mediana e soluzioni appl. ideologia partiziona
• Lezione 13 [7/11/23]: Introduzioni alla rappresentazione di Insiemi dinamici
  • 13a) Insiemi Dinamici: generalità e problemi dell'uso di vettori
  • 13b) Esercitazione 5-bis: altre soluzioni di esercizi in vista del II esonero
• Lezione 14 [10/11/23]: Secondo Esonero e altre perle.
  • 14a) Secondo Esonero: Testo e le relative & Soluzioni.
  • 14b) A taste of algorithmic game theory: Matrimoni Stabili.

Parte III: Strutture Dati Dinamiche

• Lezione 15 [14/11/23]: Strutture Dinamiche lineari.
  • 15a) Sequenze e Liste.
  • 15b) Code & Pile.
• Lezione 16 [17/11/23]: Alberi binari (radicati).
  • 16a) Per fare un albero.
  • 16b) Far visita a un albero.
  • 16c) Esercitazione 6: Esercizi su liste/pile/code e alcune soluzioni
• Lezione 17 [21/11/23]: Insiemi Dinamici con Alberi binari.
  • 17a) Alberi Binari di Ricerca (ABR).
  • 17b) Bilanciare un ABR: red & black tree.
• Lezione 18 [22/11/23]: Heap, Code con priorità & heapSort.
  • 18a) Dall'algortimo del torneo a heapSort.
  • 18b) Esercitazione 7: Esercizi su alberi/ABR/heap e alcune soluzioni
• Lezione 19 [28/11/23]: Dietro la ricorsione.
  • 19a) Stack di sistema e implementazione della ricorsione.
  • 19b) Esercitazione 7bis: altre soluzioni di esercizi in vista del III esonero
• Lezione 20 [1/12/23]: Terzo Esonero e Quattro passi con Goedel, Cantor e Turing.
  • 20a) Terzo Esonero: Testo e le relative & Soluzioni.
  • 20b) Quattro passi con Goedel, Cantor e Turing: Problemi decidibili e non.

Parte IV: Grafi

• Lezione 21 [5/12/23]: (Very) Basic Graph Theory.
  • 21a) Introduzione ai grafi e alberi come grafi.
  • 21b) Grafi: rappresentazione in memoria.
• Lezione 22 [12/12/23]: Far visita a un grafo.
  • 22a) Visita in ampiezza e profondità.
  • 22b) Alcune applicazioni delle visite.
• Lezione 23 [15/12/23]: Il problema dei cammini minimi (da sorgente unica).
  • 23a) Il caso dei pesi positivi: algoritmo di Dijkstra.
  • 23b) Il caso generale: algoritmo di Bellman-Ford.
  • 23c) Esercitazione 8: Esercizi su BFS/DFS e alcune soluzioni
• Lezione 24 [19/12/23]: A taste of digraphs I.
  • 24a) Grafi diretti aciclici: ordine topologico.
  • 24b) Esercitazione 9: Esercizi su cammini minimi e alcune soluzioni
• Lezione 25 [22/12/23]: A taste of digraphs II.
  • 25a) Il problema delle componenti fortemente connesse.
  • 25b) Esercitazione 10: Esercizi su grafi diretti e alcune soluzioni
• Lezione 26 [9/1/24]: Un problema da 1 milione di dollari
  • 26a) Complessità dei problemi: le classi P, NP and beyond,
  • 26b) Esercitazione 10bis: altre soluzioni di esercizi in vista del IV esonero
• Lezione 27 [12/1/24]: Quarto Esonero.
  • 27a) Quarto Esonero: Testo e le relative Soluzioni.

Lezioni & Slides 2022-2023

Nota: Le slides 2021-22 verranno revisionate in modo importante in concomitanza con le lezioni durante il corso.
Per avere le lezioni aggiornate, aspettate la pubblicazione dei nuovi materiali.

Lezioni & Slides 2021-2022

Parte I. I Mattoni: Iterazione, Ricorsione e Memoria

• [1/3/22] Lezione 0: Presentazione e Informazioni Pratiche
• [3/3/22] Lezione 1: Problemi, Macchine e Algoritmi
  • 1a) Introduzione al Pensiero Computazionale
  • 1b) Problemi elementari e pseudocodice
• [4/3/22] Lezione 2: Indagini su un programma iterativo
  • 2a) Specifiche e Correttezza: asserzioni logiche, precondizioni, postcondizioni, invarianti.
  • 2b) Complessità: costo computazionale e notazione asintotica.
  • 2c) Esercitazione 1: moltiplicazione egiziana.
• [8/3/22] Lezione 3: Progettare algoritmi e programmi corretti con le asserzioni logiche
• [11/3/22] Lezione 4: Induzione & Ricorsione.
  • 4a) Iterare è umano, Ricorrere è divino.
  • 4b) Il lato oscuro della ricorsione
  • 4c) Esercitazione 2: il problema del massimo fattore primo & partizioni.
• [15/3/22] Lezione 5: Astrazione sulla memoria di un esecutore: vettori.
  • 5a) Un esecutore un po' particolare.
  • 5b) Vettori: introduzione e problemi elementari tipici
• [18/3/22] Lezione 6:
  • 6a) Progettare con asserzioni logiche II: vettori.
  • 6b) L'importanza di essere ordinati: ricerca binaria e altri problemi.
  • 6c) Esercitazione 3: Baricentro & lucchetto.

Parte II. Problemi di Ricerca, Ordinamento e Affini

• [22/3/22] Lezione 7: Con Ordine, per Favore
  • 7a) Ordinamenti Naif
  • 7b) Il problema dell'ordinamento: Limitazioni Inferiori e un algoritmo ottimo.
• [25/3/22] Lezione 8: Primo Esonero e Prime Perle di Programmazione
  • 8a) Primo Esonero: Testo & Soluzioni
  • 8b) Intermezzo: Esercizi di Stile in C.
  • 8c) Un grande classico: Segmento di somma massima.
• [29/3/22] Lezione 9: Ancora su mergeSort:
  • 9a) Analisi di complessità ed Equazioni di Ricorrenza
  • 9b) Ottimizzazioni e versione iterativa.
• [1/4/22] Lezione 10: Meglio veloci che ottimi
  • 10a) quickSort & k-mediana e loro complessità: caso ottimo, pessimo e analisi probabilistica del caso medio.
  • 10b) Partiziona ottimizzate: Lomuto e Hoare.
  • 10c) Esercitazione 4: applicare l'ideologia di merge distanza tra due vettori
• [5/4/22] Lezione 11 Oltre i limiti inferiori dell'ordinamento.
  • 11a) Algoritmi "lineari" di ordinamento: countingSort & radixSort.
  • 11b) Applicare l'ideologia divide et Impera: Moltiplicazione Intera e Fibonacci veloce.
• [8/4/22] Lezione 12: Miscellanea.
  • 12a) Alla scoperta della seconda dimensione: Ricerca su matrici ordinate e finding celebrity.
  • 12b) Generazione e conteggio di strutture combinatorie: combinazioni e partizioni.
  • 12c) Esercitazione 5: quickSort, k-mediana & friends
• [12/4/22] Lezione 13: Quattro passi con Cantor, Godel & Turing
• [22/4/22] Lezione 14: Secondo Esonero e altre perle di programmazione.
  • 14a) Secondo Esonero: Testo & Soluzioni
  • 14b) Un piccolo classico: minimo intero mancante.
  • 14c) Una lezione dal dal Maestro E. W. Dijkstra

Parte III. Strutture Dati per Insiemi Dinamici: Liste, Code, Pile, Alberi, ABR

• [26/4/22] Lezione 15 Introduzione ai Tipi di Dato e alle Strutture Dati
  • 15a) Insiemi Dinamici implementati con vettori.
  • 15b) Sequenze e Liste.
• [29/4/22] Lezione 16 Strutture Dati Lineari
  • 16a) Pile & Code.
  • 16b) Dietro la Ricorsione
  • 16c) Esercitazione 6: Numeri di Cappanacci
• [3/5/22] Lezione 17 Per fare un albero...
  • 17a) Alberi: definizioni e rappresentazioni in memoria.
  • 17b) Alberi: visite e problemi base.
• [6/5/22] Lezione 18 Alberi Binari di Ricerca.
  • 18a) ABR: definizioni, proprietà e operazioni base: ricerca, min/max, succ/pred, inserimento/rimozione.
  • 18b) Esercizi Svolti: Problemi su Alberi e ABR.
  • 18c) Esercitazione 7: Alberi & ABR.
• [10/5/22] Lezione 19 Heap, heapSort & Code con priorità.
  • 19a) Dall'algoritmo del Torneo agli Heap. HeapSort & Code con Priorità.
  • 19b) Esercizi Svolti: Problemi su Liste e Alberi.
• [13/5/22] Lezione 20: Terzo Esonero & ultima perla.
  • 20a) Terzo Esonero: Testo & Soluzioni
  • 20b) A taste of algorithmic game theory: Matrimoni Stabili.

Parte IV. Grafi

• [17/5/22] Lezione 21: introduzione ai Grafi
  • 21a) Basic Graph Theory. Alberi come grafi.
  • 21b) Rappresentazioni in memoria per i grafi.
• [19/5/22] Lezione 22: Fare visita a un Grafo
  • 22a) Visita in ampiezza (BFS): pseudocodice e proprietà. Distanze minime.
  • 22b) Visita in profondità (DFS): pseudocdice e proprietà. Cicli.
  • 22c) Esercitazione 8: bfs & dfs.
• [24/5/22] Lezione 23: Il problema dei cammini minimi.
  • 23a) Caso dei pesi positivi: Algoritmo di Dijkstra e algoritmi golosi.
  • 23b) Caso generale: Algoritmo di Bellman-Ford e Programmazione dinamica.
• [27/5/22] Lezione 24: Un assaggio di grafi orientati
  • 24a) DAG e topological Sort.
  • 24b) Componenti fortemente connesse.
  • 25c) Esercitazione 9: grafi diretti.
• [31/5/22] Lezione 25: Bilanciare un ABR.
  • 25a) Alberi Rosso-Neri.
  • 25b) Esercizi Svolti: Problemi di Riepilogo sui Grafi.
• [7/6/22] Lezione 26
  • 26) Quarto Esonero: Testo & Soluzioni
• [10/6/22] Lezione 27
  • Un problema da 1 milione di dollari: Problemi Facili e Problemi Difficili.

Materiali Didattici 2021

Slides delle lezioni

• Lezione 1: Introduzione: informatica, algortimi, complessità computazionale.
• Lezione 2: Notazione Asintotica.
• Lezione 3: Costo computazionale: prime analisi di algoritmi.
• Lezione 4a: Il Problema della Ricerca.
• Lezione 4b e 5: Ricorsione.
• Lezione 6: Equazioni di Ricorrenza.
• Lezione 7: Esercizi sulla soluzione di Equazioni di Ricorrenza.
• Lezione 8: Algoritmi Naif di Ordinamento.
• Lezione 9: L'algoritmo di ordinamento Mergesort.
  • Soluzione di esercizi su: merge e mergeSort. Per la merge ricorsiva, consultare, volendo, gli "Esercizi di Stile" sotto (in C).
• Lezione 10: L'algoritmo di ordinamento Quicksort.
• Lezione 11: L'algoritmo di ordinamento Heapsort.
  • Animazione di: buildHeap e heapSort.
  • Esercizi lezione 11: Soluzioni esercizi su Heap e Heapsort.
• Lezione 12: Algoritmi di ordinamento lineari.
• Lezione 13: Strutture Dati I: liste semplici e doppie.
• Lezione 14: Strutture Dati II: code e pile.
• Lezione 15: Strutture Dati III(a): alberi.
• Lezione 16: Strutture Dati III(b): visite di alberi.
• Lezione 17: Strutture Dati IV: alberi binari di ricerca.
• Lezione 18: Strutture Dati V: tabelle hash.
• Lezione 19: Strutture DatiI VI: alberi binari di ricerca red-black.
• Lezione 20: Esercizi: Strutture Dati Comparate: ordinamenti su Liste vs Array.
• Lezione 21: Grafi I: Definizioni e Introduzione.
• Lezione 22: Esercizi di Riepilogo I: Equazioni di Ricorrenza, Quicksort, Liste.
• Lezione 23: Grafi II: Visita in profondità (DFS) e in ampiezza (BFS).
• Lezione 24: Esercizi di Riepilogo II: Alberi e Ordinamenti Lineari.
• Lezione 25: Cammini minimi su grafi con pesi positivi: l'algoritmo di Dijkstra.
• Lezione 26: Esercizi di Riepilogo III: Alberi, ABR e Alberi Red-Black.
• Lezione 27: Esercizi di Riepilogo IV: Esercizi su Grafi.
• Lezione 28: Esercizi da Vecchi Scritti I.
• Lezione 29: Il problema della mediana ed esercizi da Vecchi Scritti II.
• Lezione 30: Test di autovalutazione: distanza tra due insiemi di nodi.

• Lezione 31: Fuori Programma: soluzioni compiti primo appello.

Letture

Di seguito vi propongo alcune letture (assolutamente facoltative) su argomenti inerenti al corso
selezionate tra i numerosi scritti prodotti in passato per Informatica Generale, parte di Programmazione C.

• Algoritmi: Problemi, Macchine, Algoritmi
• Ricorsione: Iterare è Umano, Ricorrere è Divino
• Gli esercizi di stile e la nascita di un famoso algoritmo: Esercizi di Stile

-- Ivano Salvo - 2021-02-25