Algoritmi e Principi dell'Informatica

Docente: Davide Martinenghi
Esercitatore: Gabriele Paveri Fontana

Avvisi

• Il testo e le soluzioni dell'appello del 4 settembre 2024 sono disponibili qui.
• Il testo e le soluzioni dell'appello del 13 luglio 2024 sono disponibili qui.
• Il testo e le soluzioni dell'appello del 20 giugno 2024 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.
• Eserciziario: Algoritmi e Principi dell'Informatica: esercizi risolti e commentati. A. Barenghi, D. Martinenghi, M. Pradella, M. Rossi. Esculapio, 2024, Seconda Edizione.
• Slide delle lezioni (potenzialmente aggiornate di volta in volta).
  • Introduzione al corso
  • Linguaggi formali e automi a stati finiti
  • Automi a pila
  • Introduzione alla logica
  • Macchine di Turing
  • Non-determinismo
  • Grammatiche formali
  • Espressioni regolari
  • Logica per descrivere linguaggi e proprietà
  • Computabilità
  • Complessità del calcolo
  • Concetti di base di complessità degli algoritmi
  • Strutture dati
  • Alberi e grafi
  • Argomenti avanzati
  • Applicazioni, curiosità e conclusioni (slide facoltative)
• 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

Esame

Scritto con eventuale discussione orale esclusivamente su richiesta del docente.

Calendario (provvisorio)