Algoritmi e Principi dell'Informatica

Docente: Davide Martinenghi
Esercitatore: Nicolò Felicioni

Avvisi

Il testo e le soluzioni dell'appello del 7 settembre 2023 sono disponibili qui.
Il testo e le soluzioni dell'appello del 7 luglio 2023 sono disponibili qui.
Il testo e le soluzioni dell'appello del 19 giugno 2023 sono disponibili qui.
Il testo e le soluzioni della prima prova in itinere del 21 aprile 2023 sono disponibili qui.

Prova finale

I corsi Algoritmi e Principi dell'Informatica (10 crediti) e Progetto di Algoritmi e Strutture Dati (1 credito di Prova Finale) sono diversi: dovete sostenerli entrambi solo se sono nel vostro piano di studi.
La presentazione del progetto è qui.
Il foglio di specifica del progetto è qui.
La presentazione del prof. Barenghi sugli strumenti di sviluppo è disponibile qui, con i file di esempio. La registrazione della lezione si trova qui.

Materiale

Libri di testo:
- Modulo I: Informatica Teorica. Mandrioli, Spoletini, Informatica teorica (II edizione) De Agostini, 2011.
- Modulo II: Introduzione agli algoritmi e strutture dati. Cormen, Leiserson, Rivest, Stein (versione ridotta per il corso di Algoritmi e Principi dell'Informatica), McGraw-Hill.
- Introduzione agli algoritmi e strutture dati è disponibile nella versione e-book dalla piattaforma VitalSource Bookshelf. Istruzioni per l'accesso fuori rete qui.
Eserciziario: Algoritmi e Principi dell'Informatica: esercizi risolti e commentati. A. Barenghi, D. Martinenghi, M. Pradella, M. Rossi. Esculapio, 2023. Potete consultare l'errata corrige qui.
Slide delle lezioni (potenzialmente aggiornate di volta in volta).
Dispense su logiche MFO e MSO in inglese: pdf.
Vecchio materiale fornito senza garanzie:
- Temi d'esame del corso API dal 2010/2011 in poi: zip.
- Temi d'esame del vecchio corso di Informatica Teorica: zip.
- Un breve ripasso di logica del prim'ordine e un prontuario di logica, con un elenco di errori comuni.
- Note su somme e ricorrenze: pdf.
- Qualche esercizio su logiche MFO e MSO preparato da Matteo Rossi e qualche suo tema d'esame, con esercizi del genere.
- Slide in inglese su MFO e MSO da un sito esterno.
- Esempi di esami di algoritmi da un vecchio corso.
- Esempi di valutazione complessità (cicli), raccolti da Matteo Rossi.
- Esercizi su definizione di algoritmi, raccolti da Matteo Rossi.
Letture consigliate:
- Il calcolatore universale. Da Leibniz a Turing. M. Davis, seconda edizione, Adelphi, 2012.
Registrazione delle lezioni di una precedente edizione.

Ricevimento

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

Esame

Scritto con eventuale discussione orale esclusivamente su richiesta del docente.

Calendario (provvisorio)

Orario	Aula	Argomenti	Materiale extra
21/2/2023 10.15-13.15	2.0.1	Introduzione al corso. Concetto di alfabeto, linguaggio. Automi a stati finiti.
22/2/2023 14.15-17.15	6.0.1	Pumping Lemma. Famiglie di linguaggi e chiusura.
23/2/2023 09.15-11.15	T.1.3	Automi a pila. Proprietà automi a pila.
28/2/2023 10.15-13.15	2.0.1	Macchine di Turing.
1/3/2023 14.15-17.15	6.0.1	Esercitazione.	Slide es. FSA
2/3/2023 09.15-11.15	T.1.3	Esercitazione.	Slide es. PDA
7/3/2023 10.15-13.15	2.0.1	Non determinismo. Grammatiche formali. Grammatiche regolari.
9/3/2023 09.15-11.15	T.1.3	Esercitazione.	Slide es. TM
14/3/2023 10.15-13.15	2.0.1	Grammatiche non contestuali. Grammatiche generali.
15/3/2023 14.15-17.15	6.0.1	Esercitazione.	Slide es. ND
16/3/2023 09.15-11.15	T.1.3	Esercitazione.
21/3/2023 10.15-13.15	2.0.1	Espressioni regolari. Tesi di Church. Enumerazioni.
22/3/2023 14.15-17.15	6.0.1	Macchina di Turing universale. Problemi definibili e calcolabili.
23/3/2023 09.15-11.15	T.1.3	Problemi indecidibili. Diagonalizzazione.
28/3/2023 10.15-13.15	2.0.1	Esercitazione.	Slide es. grammatiche
29/3/2023 14.15-17.15	6.0.1	Semidecidibilità. Teorema di Rice. Riduzione di problemi.	linee guida su decidibilità
30/3/2023 09.15-11.15	T.1.3	Esercitazione.
4/4/2023 10.15-13.15	2.0.1	MFO/MSO. Logica per descrivere proprietà.	dispense su MFO/MSO
5/4/2023 14.15-17.15	6.0.1	Esercitazione.	Slide es. decidibilità
6/4/2023 09.15-11.15	T.1.3	Esercitazione.	Slide es. logica
12/4/2023 14.15-17.15	6.0.1	Introduzione alla complessità del calcolo. Analisi asintotica.
13/4/2023 09.15-11.15	T.1.3	Esercitazione.
18/4/2023 10.15-13.15	2.0.1	Complessità di automi. Accelerazione lineare. Macchina RAM.
21/4/2022 09.30-10.45	n.d.	Prima prova in itinere
26/4/2023 14.15-17.15	6.0.1	Correlazione polinomiale. Algoritmi e pseudocodice. Insertion-sort.
27/4/2023 09.15-11.15	T.1.3	Ricorrenze. Mergesort. Albero di ricorsione. Metodo della sostituzione.
2/5/2023 10.15-13.15	2.0.1	Esercitazione.	Slide es. complessità TM e RAM
9/5/2023 10.15-13.15	2.0.1	Teorema dell'esperto. Heapsort.
10/5/2023 14.15-17.15	6.0.1	Complessità di Heapsort. Quicksort. Counting sort.
11/5/2023 09.15-11.15	T.1.3	Esercitazione.
16/5/2022 10.15-13.15	2.0.1	Pila. Coda. Hashtable.
17/5/2023 14.15-17.15	6.0.1	Tecniche di ispezione. Alberi binari di ricerca.
18/5/2023 09.15-11.15	T.1.3	Esercitazione.	Slide es. complessità e ricorrenze
23/5/2023 10.15-13.15	2.0.1	Alberi rosso-neri. Grafi
24/5/2023 14.15-16.15	6.0.1	Argomenti avanzati
25/5/2023 09.15-11.15	T.1.3	Esercitazione.	Slide es. algoritmi su array
30/5/2023 10.15-11.15	2.0.1	Descrizione della prova finale.
30/5/2023 11.15-13.15	2.0.1	Esercitazione.	Appunti es. su BST
31/5/2023 14.15-17.15	6.0.1	Esercitazione.	Slide es. su BST, Slide es. su hash table, Appunti es. alberi
1/6/2023 09.15-11.15	T.1.3	Esercitazione.	Appunti es. grafi