Algoritmi e Principi dell'Informatica

Docente: Davide Martinenghi
Esercitatore: Nicolò Felicioni

Avvisi

  • Il testo e le soluzioni dell'appello del 20 gennaio 2022 sono disponibili qui.
  • Il testo e le soluzioni dell'appello del 25 agosto 2021 sono disponibili qui.
  • Il testo e le soluzioni dell'appello del 29 giugno 2021 sono disponibili qui.
  • Il testo e le soluzioni dell'appello del 14 giugno 2021 sono disponibili qui.
  • Note generali

    Il corso si svolgerà in modo coordinato tra le sezioni di Milano. Le lezioni saranno condivise nelle seguenti aule virtuali: Le esercitazioni saranno divise in due squadre (codice persona dispari: martedì, pari: mercoledì), quando in presenza. Si potranno seguire online nell'aula virtuale https://politecnicomilano.webex.com/meet/nicolo.felicioni.

    Prova finale

    Programma del Modulo I (ex Informatica Teorica)

    Programma del Modulo II (ex Informatica 3)

    Materiale

    Ricevimento

    Venerdì 10:30 - 12:30 previo appuntamento via email.

    Esame

    Scritto con eventuale discussione orale esclusivamente su richiesta del docente.

    Nota bene
    Questo è un corso integrato, pertanto se in un appello non si raggiunge la sufficienza complessivamente tra i due moduli, occorre sostenere nuovamente l'esame intero, anche se si era in precedenza raggiunto un punteggio sufficiente in uno dei due moduli.

    Calendario

    Orario Argomenti Video Materiale extra
    25/2/2021 09.15-11.15 Introduzione al corso. Concetto di alfabeto, linguaggio. Lezione 1  
    26/2/2021 16.15-19.15 Automi a stati finiti. Pumping Lemma. Lezione 2  
    2/3/2021 10.15-13.15 Esercitazione. Esercitazione 1: Parte 1, Parte 2 Slide es. FSA
    3/3/2021 14.15-17.15 Esercitazione. Esercitazione 1 Slide es. FSA
    4/3/2021 09.15-11.15 Famiglie di linguaggi e chiusura. Automi a pila. Lezione 3  
    5/3/2021 16.15-19.15 Proprietà automi a pila. Macchine di Turing. Lezione 4  
    9/3/2021 10.15-13.15 Esercitazione. -  
    10/3/2021 14.15-17.15 Esercitazione online. Esercitazione 2 Slide es. PDA, Appunti PDA
    12/3/2021 16.15-19.15 Varianti di macchine di Turing. Non determinismo. Lezione 5  
    16/3/2021 10.15-13.15 Esercitazione online. Esercitazione 3 Slide es. TM, Appunti TM
    17/3/2021 14.15-17.15 Esercitazione. -  
    18/3/2021 09.15-11.15 TM non deterministiche. Grammatiche formali. Lezione 6  
    19/3/2021 16.15-19.15 Grammatiche regolari e non contestuali. Lezione 7  
    23/3/2021 10.15-13.15 Esercitazione online. Esercitazione 4 Slide es. ND, Appunti ND
    24/3/2021 14.15-17.15 Esercitazione. -  
    25/3/2021 09.15-11.15 Grammatiche generali. Lezione 8  
    26/3/2021 16.15-19.15 Espressioni regolari. Ripasso di logica. Logica per descrivere linguaggi. Lezione 9 prontuario di logica, esercizi propedeutici di logica
    30/3/2021 10.15-13.15 Esercitazione online. Esercitazione 5 Slide es. grammatiche, Appunti grammatiche
    31/3/2021 14.15-17.15 Esercitazione. -  
    1/4/2021 09.15-11.15 MFO/MSO. Lezione 10 dispense su MFO/MSO
    7/4/2021 14.15-17.15 Esercitazione online. Esercitazione 6: Parte 1, Parte 2 Appunti esercizi
    8/4/2021 09.15-11.15 Logica per descrivere proprietà. Tesi di Church. Lezione 11  
    9/4/2021 16.15-19.15 Enumerazioni. Macchina di Turing universale. Problemi definibili e calcolabili. Lezione 12  
    13/4/2021 10.15-13.15 Esercitazione online. Esercitazione 7 Slide es. logica, Appunti logica
    14/4/2021 14.15-17.15 Esercitazione. -  
    16/4/2021 16.15-19.15 Problemi indecidibili. Diagonalizzazione. Semidecidibilità. Lezione 13  
    20/4/2021 10.15-12.15 Teorema di Rice. Riduzione di problemi. Lezione 14 linee guida su decidibilità
    27/4/2021 10.15-13.15 Esercitazione. Esercitazione 8 Appunti es. 8
    28/4/2021 14.15-17.15 Esercitazione. Esercitazione 8 Appunti es. 8
    29/4/2021 09.15-11.15 Introduzione alla complessità del calcolo. Analisi asintotica. Lezione 15  
    30/4/2021 16.15-19.15 Complessità di automi. Accelerazione lineare. Macchina RAM. Ricerca binaria. Criteri di costo. Lezione 16  
    4/5/2021 10.15-13.15 Esercitazione. Esercitazione 9 Appunti es. 9
    5/5/2021 14.15-17.15 Esercitazione. -  
    6/5/2021 09.15-11.15 Criterio logaritmico. Classe P. Teorema di correlazione polinomiale. Lezione 17  
    7/5/2021 16.15-19.15 Ricorrenze. Teorema dell'esperto. Lezione 18  
    11/5/2021 10.15-13.15 Esercitazione. Esercitazione 10 Appunti es. 10
    12/5/2021 14.15-17.15 Esercitazione. -  
    13/5/2021 09.15-11.15 Ordinamento: Insert-sort, Mergesort, Quicksort. Lezione 19  
    14/5/2021 16.15-19.15 Complessità di Quicksort. Counting sort. Strutture dati: pila, coda. Lezione 20  
    18/5/2021 10.15-13.15 Esercitazione. Esercitazione 11 Appunti es. 11
    19/5/2021 14.15-17.15 Esercitazione. -  
    20/5/2021 09.15-11.15 Strutture dati lineari, tabelle di hash. Lezione 21  
    21/5/2021 16.15-19.15 Efficienza delle tabelle di hash, alberi, alberi rosso-neri. Lezione 22  
    25/5/2021 10.15-13.15 Esercitazione. Esercitazione 12 Appunti array, appunti hashing
    26/5/2021 14.15-17.15 Esercitazione. -  
    27/5/2021 09.15-11.15 Cancellazione da alberi rosso-neri. Heap. Lezione 23  
    28/5/2021 16.15-19.15 Heapsort, Grafi Lezione 24  
    29/5/2021 09.15-10.15 Descrizione della prova finale. Link Descrizione del progetto
    1/6/2021 10.15-13.15 Esercitazione online. Esercitazione 13 Slide es. BST, Appunti es. 13
    3/6/2021 09.15-11.15 Esercitazione online. Esercitazione 14 Slide es. grafi, Appunti es. 14
    4/6/2021 16.15-19.15 Lezione extra su argomenti avanzati. -