Algoritmi e Principi dell' Informatica (086067)
Aule e orari
- Martedì dalle 10:15 alle 13:15 - Aula 5.0.3 (Esercitazione)
- Mercoledì dalle 14:15 alle 17:15 - Aula 2.1.4 (Lezione)
- Giovedì dalle 8:15 alle 10:15 - Aula 5.0.1 (Lezione)
Contatti
Docente: Alessandro Barenghi (alessandro.barenghi -at- polimi.it)
Esercitatore: Achille Frigeri (achille.frigeri -at- polimi.it)
Registrazioni
Slides lezione
Testi di riferimento
Materiale di supporto
Slides lezione
Slides Informatica Teorica
- Introduzione al corso: Slides (rev.1-2024)
- Modelli e linguaggi: Slides (rev.0-2024)
- Automi a stati finiti: Slides (rev.0-2024)
- Automi a pila Slides (rev.0-2024)
- Macchina di Turing Slides (rev.0-2024)
- Non determinismo Slides (rev.0-2024)
- Grammatiche Slides (rev.1-2024)
- Teoria della computazione Slides (rev.4-2024)
- Logica Slides (rev.1-2024)
Slides Algoritmi
- Complessità del calcolo: Slides (rev.0-2024)
- Analisi di complessità algoritmica Slides (rev.1-2023)
- Strutture dati - 1 - Liste, pile, code, hash tables Slides (rev.2-2023)
- Strutture dati - 2 - Alberi Slides (rev.0-2023)
- Strutture dati - 3 - Heap e grafi Slides (rev.1-2022)
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)
- Alessandro Barenghi, Davide Martinenghi, Matteo Pradella, Matteo Rossi, Algoritmi e Principi dell'Informatica: esercizi risolti e commentati, Editore: Società Editrice Esculapio, Anno edizione: 2023, ISBN: 978-88-9385-347-7
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
È disponibile un eserciziario, per entrambi i moduli:
- Eserciziario: Algoritmi e Principi dell'Informatica: esercizi risolti e commentati. A. Barenghi, D. Martinenghi, M. Pradella, M. Rossi. Esculapio, 2023 Errata Corrige
Materiale di supporto
Registrazioni A.A. 2020-2021
| 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 |
| 11/5 | E | 1 | Esercizi su stima di complessità del calcolo | link | |
| 12/5 | E | 2 | Esercizi su stima di complessità del calcolo | link | |
| 13/5 | L | Tutte | Strategie di ordinamento, ordinamento per inserimento, limite inferiore di complessità dell'ordinamento, Mergesort, Quicksort. | link | Slides |
| 13/5 | L | Tutte | Strategie di ordinamento, ordinamento per inserimento, limite inferiore di complessità dell'ordinamento, Mergesort, Quicksort. | link | Slides |
| 14/5 | L | Tutte | Analisi di complessità di Quicksort. Ordinamento per conteggio. Analisi di strutture dati: pila, coda | link | Slides ordinamento Slides strutture dati |
| 18/5 | E | 1 | Esercizi su stima di complessità del calcolo e algoritmi di ordinamento | link | |
| 19/5 | E | 2 | Esercizi su stima di complessità del calcolo e algoritmi di ordinamento | link | |
| 20/5 | L | Tutte | Strutture dati lineari, tabelle di hash | link | Slides strutture dati |
| 21/5 | L | Tutte | Efficienza delle tabelle di hash, alberi, alberi rosso-neri | link | Slides strutture dati Slides strutture dati - 2 |
| 25/5 | E | Tutte | Esercizi su algoritmi di ordinamento e alberi binari di ricerca | link | |
| 26/5 | E | Tutte | Esercizi su tabelle di hash, alberi binari di ricerca, alberi rosso-neri | link | |
| 27/5 | L | Tutte | Cancellazione da alberi rosso-neri, Mucchi | link | Slides alberi Slides heap |
| 28/5 | L | Tutte | Heapsort, Grafi | link | Slides |
| 1/6 | E | Tutte | Esercizi su heap e grafi | link | |
| 3/6 | E | Tutte | Esercizi di ricapitolazione | link | |
| 4/6 | L | Tutte | Seminario su dynamic programming e teoria della complessità | link | Slides, Cormen Cap. 15 |