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

Le esercitazioni si terranno contemporaneamente in presenza e in diretta streaming

  • Squadra 1: Ogni martedì, dalle ore 10:15 alle 13:15, aula B.4.2, streaming link
  • Squadra 2: Ogni mercoledì, dalle ore 14:15 alle 17:15, aula 3.0.2 (EX S.0.5) , streaming link

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à
20/4 L Tutte Teorema di Kleene. Teorema di Rice. Riduzione di problemi. link Slides computabilità
27/4 E 1 Esercizi su Logica e computabilità link
28/4 E 2 Esercizi su computabilità link Slides (con esercizi svolti e aggiuntivi) link
29/4 L Tutte Linee guida sulla decidibilità. Introduzione alla complessità del calcolo. Analisi asintotica. link Slides decidibilità Slides complessità calcolo
30/4 L Tutte Complessità di automi. Accelerazione lineare. Macchina RAM. Ricerca binaria. Criteri di costo. link Slides complessità calcolo
4/5 E 1 Esercizi su computabilità link
5/5 E 2 Esercizi su Logica e computabilità link Slides (con esercizi svolti e aggiuntivi) link
6/5 L Tutte Criterio di costo logaritmico. Teorema di correlazione polinomiale. Introduzione allo pseudocodice. link Slides complessità da slide 35 a fine blocco, Slides pseudocodice fino a slide 5
7/5 L Tutte Analisi di complessità temporale su pseudocodice. Analisi di complessità di procedure ricorsive, teorema dell'esperto. link Slides 5 - 22

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.