Schema della sezione

  •  

    Lezione 1: 30/09/25

    • Introduzione al corso
    • Concetti fondamentali: problema computazionale, algoritmo, modello di calcolo
     

    Lezione 2: 01/10/25

    • Concetti fondamentali: pseudocodice
    • Esempio (trasposta).
    • Concetti fondamentali: taglia dell'istanza, struttura dati.
    • Analisi di algoritmi: complessità e correttezza.
    • Definizione della funzione complessità e analisi asintotica. 
     

    Lezione 3: 02/10/25

    • Ordini di grandezza O-grande, Omega-grande, Theta-grande, o-piccolo.
    • Proprietà degli ordini di grandezza. 
    • Strumenti matematici (parte bassa e alta, sommatorie notevoli).
    • Analisi di complessità: procedimento per provare limiti superiori e inferiori alla complessità.
    • Esempi (PrefixAverages quadratico e lineare).

    Lezione 4: 07/10/25

    • Esercizio simile a R-4.29 del testo.
      Complessità polinomiale vs complessità esponenziale: esempio: RSA.
    • Caveat relativi all'analisi asintotica al caso pessimo.
    • Induzione: tecnica generale; esempio (serie di Gauss).

    Lezione 5: 08/10/25
     
    • Induzione: esempio di induzione fallace (F( n)=0 per ogni n).
    • Analisi di correttezza: approccio generale.
    • Invarianti: definizione; utilizzo di un invariante per provare la correttezza di un ciclo; esempi (arrayMax e arrayFind).
    • Algoritmi ricorsivi: definizione; esempi (MergeSort, linearSum, reveseArray)

    Lezione 6: 09/10/25

    • Albero della Ricorsione: definizione; esempi (MergeSort, linearSum, reveseArray)
    • Gestione della memoria nell'esecuzione di un algoritmo ricorsivo: stack e heap
    • Analisi di complessità di un algoritmo ricorsivo tramite l'Albero della Ricorsione ed esempi (linearSum e reverseArray).
    • Calcolo di potenze: algoritmo power e sua applicazione al calcolo dell'n-esimo numero di Fibonacci (powerFib).
    • Analisi di correttezza di un algoritmo ricorsivo tramite induzione ed esempi (linearSum).

    Lezione 7: 14/10/25

    • Esercizi dalle Slide 48-49, 77, 79 sulle nozioni di base

    Lezione 8: 15/10/25

    • Esercizi dalle Slide 78 (secondo esercizio), 101 (secondo esercizio), 103 sulle nozioni di base

    Lezione 9: 16/10/25

    • Invariante per l'esercizio sulla maggioranza (Slide 103 sulle nozioni di base)

    Materiale: