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.1-2024)
  • Analisi di complessità algoritmica Slides (rev.1-2024)
  • Strutture dati - 1 - Liste, pile, code, hash tables Slides (rev.1-2024)
  • Strutture dati - 2 - Alberi Slides (rev.0-2024)
  • Strutture dati - 3 - Heap e grafi Slides (rev.0-2024)

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

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

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