Algoritmi e Principi dell' Informatica (086067)


Lezioni

Le lezioni del corso per l'edizione dell'anno corrente saranno in modalità collaborativa tra le sezioni.

Giovedì (9:15-11:15) Aula virtuale
Venerdì (16:15-19:15) Aula virtuale

Aule virtuali

Dal 25 febbraio a 25 marzo: Aula
Dal 26 marzo a 30 aprile: Aula
Dal 6 maggio a 4 giugno: Aula

Esercitazioni

Aggiornamento 05/03 : in seguito all'ordinanza di regione Lombardia, le esercitazioni passano in modalità unicamente online fino ad un auspicato cambiamento per il meglio delle condizioni sanitarie. Di conseguenza, si svolgeranno in un unico turno Martedì (10:15-13:15) unicamente in aula virtuale link

Sarete avvertiti a mezzo e-mail dell'eventuale ritorno all' orario in presenza+streaming.

Contatti

Docente: Alessandro Barenghi (alessandro.barenghi -at- polimi.it)
Esercitatore: Achille Frigeri (achille.frigeri -at- polimi.it)


Registrazioni
Slides lezione
Testi di riferimento
Struttura dell' esame
Materiale di supporto


Registrazioni A.A. 2020-2021


Legame tra grammatiche non contestuali e automi a pila. Costruzione: da grammatica a Macchina di Turing e viceversa. Considerazioni finali sulle grammatiche.

Data L/E Squadra Argomento Registrazione Materiale
25/2 L Tutte Introduzione al corso. Concetto di alfabeto, linguaggio. link Slides 1 - 27 link
26/2 L Tutte Operazioni sui linguaggi. Problema informatico come riconoscimento di stringhe. Problema informatico come traduzione. Automi a stati finiti: introduzione, definizione ed esempi. Linguaggi finiti e il comportamento ciclico degli automi. Il pumping lemma e sue conseguenze. an bn non è riconoscibile da automi a stati finiti. link Slides 27 - 47 link
2/3 E 1 Esercizi su linguaggi e ASF riconoscitori link
3/3 E 2 Esercizi su linguaggi e ASF riconoscitori link link
4/2 L Tutte Famiglie di linguaggi e chiusura rispetto ad operazioni. La famiglia dei Regolari e sue chiusure rispetto intersezione, complemento, unione. Considerazioni generali sulle chiusure dei Regolari. Automi a pila: introduzione, esempi. link Slides 47 - 65 link
5/2 L Tutte Definizione formale degli automi a pila. Proprietà di (non) chiusura: unione e intersezione. Chiusura rispetto al complemento. Introduzione alle Macchine di Turing; definizione. Esempi di Macchine di Turing. link Slides 66 - 79 link
10/3 E 1+2 Esercizi ASF e APD link link
11/3 - Tutte Sospensione per lauree triennali - -
12/3 L Tutte Macchine di Turing, loro definizione. Esempi di Macchine di Turing. Proprietà di chiusura delle macchine di Turing e relazione con le altre famiglie. Varianti di macchine di Turing. Considerazioni finali sulle macchine di Turing. Introduzione al nondeterminismo; automi nondeterministici a stati finiti e a pila. link Slides 80 - 100 link
16/3 E 1+2 Esercizi su Macchine di Turing link link
17/3 L Tutte Esempi e proprietà di automi a stati finiti e a pila nondeterministici. Le macchine di Turing nondeterministiche: descrizione e proprietà. Considerazioni finali sul nondeterminismo. Introduzione alle grammatiche. link Slides 101 - fine link, Slides 1 - 3link
18/3 L Tutte Le grammatiche: definizione ed esempi. Famiglie di grammatiche. Le grammatiche regolari definiscono i linguaggi regolari. Legame tra grammatiche non contestuali e automi a pila. link Slides 3 - 21 link
23/3 E 1+2 Esercizi su Automi non deterministici e Grammatiche link link
25/3 L Tutte Legame tra grammatiche non contestuali e automi a pila. Costruzione: da grammatica a Macchina di Turing e viceversa. Considerazioni finali sulle grammatiche. link Slides 21 - 28 link
26/3 L Tutte Sistemi di pattern. Espressioni regolari. Confronto tra poteri espressivi. Ripasso di logica. Logica per descrivere linguaggi link Slides ripasso logica Slides r.e. Slides logica
30/3 E 1+2 Esercizi su Automi non deterministici e Grammatiche - 2 link link
1/4 L Tutte Riuso di linguaggi già definiti per definirne di nuovi in logica. Logica MFO. Limitazioni di MFO. Logica MSO. link Slides logica
8/4 L Tutte Corrispondenza tra MSO e FSA. Logica per descrivere proprietà. Nozione di problema e di algoritmo. Tesi di Church. link Slides logica Slides computabilità
9/4 L Tutte Enumerazioni. Macchina di Turing universale. Problemi definibili e calcolabili. Problema dell’arresto. link Slides computabilità
13/4 E 1+2 Esercizi su Grammatiche e Logica link link
16/4 L Tutte Problema della totalità di una funzione. Risolvibilità di problemi. Decidibilità e semidecidibilità. Insiemi ricorsivi e ricorsivamente enumerabili. link Slides computabilità

Slides lezione A.A. 2019-2020

Modulo 1

  • Introduzione al corso: Slides (rev.1-2020)
  • Modelli e linguaggi: Slides (rev.1-2020)
  • Automi a stati finiti: Slides (rev.2-2020)
  • Automi a pila Slides (rev.3-2020)
  • Macchina di Turing Slides (rev.2-2020)
  • Non determinismo Slides (rev.1-2020)
  • Grammatiche Slides (rev.3-2020)
  • Teoria della computazione Slides (rev.4-2020)
  • Logica Slides (rev.2-2020)

Modulo 2

  • Complessità del calcolo: Slides (rev.4-2020)
  • Analisi di complessità algoritmica Slides (rev.3-2020)
  • Strutture dati - 1 - Liste, pile, code, hash tables Slides (rev.2-2020)
  • Strutture dati - 2 - Alberi Slides (rev.2-2020)
  • Strutture dati - 3 - Heap e grafi Slides (rev.1-2020)

—-

Testi di riferimento

Per il modulo di Informatica Teorica:

  • Dino Mandrioli, Paola Spoletini; Informatica teorica, CittaStudi, 2011 (La vecchia edizione in inglese del testo non è più stampata, però è disponibile sul sito del primo autore)
  • Mandrioli D., Lavazza L., Morzenti, A., San Pietro P.L., Spoletini P.; Esercizi di Informatica Teorica, III Edizione, Esculapio, 2005

Per il modulo di Algoritmi e strutture dati :

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduzione agli algoritmi e strutture dati (versione ridotta per il corso di Algoritmi e Principi dell'Informatica), McGraw-Hill, ISBN: 1307547389, o alternativamente la versione integrale, in inglese, degli stessi autori Introduction to Algorithms, Third Edition, MIT press

—-

Materiale di supporto

  • Una dispensa riguardante logica monadica del primo e secondo ordine:dispensa.
  • Raccolta di temi d' esame degli anni passati: raccolta

Struttura dell' esame

Le prove d'esame assegnano 33 punti che corrispondono al voto massimo di 30 e lode, tra i due moduli dell' esame stesso. E' necessario ottenere una valutazione sufficiente in entrambi i moduli allo scopo di avere una valutazione positiva. Gli orali sono possibili unicamente su richiesta del docente.