Algoritmi e Principi dell'Informatica

Matteo Pradella (twitter @bzoto, tag #corsoapi)

AVVISI

pagina twitter, #corsoapi

Attenzione! Vi ricordo e segnalo che 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.

1/4/2020: Potrete trovare il materiale aggiornato sul sito BEEP del corso

Obiettivi

L'informatica ha subito un'evoluzione estremamente rapida dai suoi albori ai giorni d'oggi. Cio' ha prodotto notevoli benefici alla qualita' della vita ma ha anche creato problemi legati all'affidabilita' dei sistemi informatici. Spesso infatti le tecniche di progetto adottate si sono rivelate inadeguate alla complessita' dei problemi affrontati. Da piu' parti si e' individuata, tra le cause principali della scarsa affidabilita' dei sistemi informatici, la mancanza di solidi principi teorici su cui basare le tecniche di progettazione. Il corso di algoritmi e principi dell'informatica ha lo scopo di colmare questa lacuna affrontando in maniera sistematica i problemi fondamentali dell'informatica e mettendo in evidenza come un approccio rigoroso e basato sui fondamenti teorici della disciplina abbia grande rilevanza nelle applicazioni pratiche.

Programma (Modulo I - ex Informatica Teorica)

1. I modelli dell'informatica

   • Automi (a stati finiti, a pila, Macchine di Turing)
   • Grammatiche
   • Modelli nondeterministici
   • Uso della logica matematica per modellare sistemi e descriverne proprieta'

2. Teoria della computazione

   • Potenza dei modelli di calcolo
   • Tesi di Church
   • Problemi indecidibili
   • Tecniche di dimostrazione di indecidibilita'

Programma (Modulo II - ex Informatica 3)

1. Teoria della complessita'

   • Nozioni e notazioni fondamentali per l'analisi di complessita'
   • I modelli di calcolo e le relazioni tra le loro complessita' computazionali
     • Definizione di complessita' spaziale e temporale per macchina di Turing deterministica
     • Astrazioni e notazione asintotica
     • Complessita' di automi a stati finiti, a pila e macchina di Turing a nastro singolo Accelerazione lineare
   • La macchina RAM
     • Valutazione di complessita' con criterio del costo costante
     • Il criterio logaritmico
   • Il teorema di correlazione polinomiale
   • Gerarchie di complessita'
   • Cenni all'NP-completezza

2. Strutture dati e algoritmi fondamentali

   • Algoritmi di ricerca e ordinamento
   • Strutture dati elementari (pile, code, liste): rappresentazione, algoritmi di ricerca e gestione
   • Tabelle hash: funzioni di hash, indirizzamento aperto.
   • Alberi e loro gestione
     • Alberi binari
     • Algoritmi di visita e gestione
     • Alberi rosso-neri
   • Grafi, loro rappresentazione e gestione

3. Tecniche avanzate per la progettazione di algoritmi

   • Cenni a backtracking, programmazione dinamica e algoritmi greedy

Testi, appunti e materiale vario

• Testi, Modulo I:

  • D. Mandrioli, P. Spoletini, Informatica Teorica (II edizione), CittàStudi, 2011 (testo ufficiale)
  • La vecchia edizione in inglese del testo non è più stampata, però è disponibile sul sito del primo autore
  • L. Lavazza, A. Morzenti, D. Mandrioli, P. San Pietro, Esercizi di Informatica Teorica (terza edizione), Esculapio (eserciziario)
  • D. Mandrioli, P. Spoletini, Mathematical logic for computer science - an introduction, Esculapio, 2010 (dispensa sulla logica)

• Testo, Modulo II:

  • Cormen T., Leiserson C., Rivest R., Stein C., Introduzione agli algoritmi e strutture dati (c'è una versione ridotta per il corso: Algoritmi e Principi dell'Informatica, ISBN 9781307547382, McGraw-Hill 2020.)

• Appunti, Modulo I:

  • Parte I.
  • Parte II.
  • Parte IIa.
  • Parte III.

• Appunti, Modulo II:

  • Parte IV.
  • Parte V.
  • Parte VI.
  • Parte VII.
  • Argomenti avanzati.

• Altro
  • Dispensa su Logiche MFO/MSO
  • Qualche esercizio su logiche MFO e MSO preparati da Matteo Rossi e qualche suo tema d'esame, con esercizi del genere.
  • Note su somme e ricorrenze.
  • Appunti di ripasso sulla logica preparati da Angelo Morzenti.
  • Applicazione: espressioni regolari.
  • Volete veder funzionare i vostri automi? Vi consiglio di dare una occhiata all'ottimo JFLAP.
  • Le vecchie slide su Reti di Petri.
  • Una curiosa implementazione meccanica della Macchina di Turing (con filmato!).
  • Visualizzazione di strutture dati ed algoritmi (sito del prof. David Galles, USFCA).
  • Interprete dello pseudo-codice visto a lezione e simulatore di RAM entrambi scritti da Loris Nardo in C#
  • Introduzione a JavaScript procedurale, con pagina esempio e codice.

Temi d'esame ed esercizi

• Raccolta di esami di API 2010-2011.
• I prova in itinere 2011-2012.
• II prova in itinere 2011-2012.
• Prova del 20/2/12.
• Prova del 12/7/2012.
• Prova del 10/9/2012.
• Prova del 27/9/2012.
• Prova del 20/11/2012.
• Prova del 8/2/2013.
• Prova del 21/2/2013.
• Prova del 25/6/2013.
• Prova del 11/9/2013.
• Prova del 20/9/2013.
• Prova del 25/11/2013.
• Prova del 14/2/2014 e del Recupero.
• Prova del 4/3/2014.
• Prova del 7/7/2014.
• Prova del 17/7/2014.
• Prova del 2/9/2014.
• Prova del 18/9/2014.
• Prova del 25/11/2014.
• Prova del 13/02/2015.
• Prova del 02/03/2015.
• Prova del 06/07/2015.
• Prova del 16/07/2015.
• Prova del 2/9/2015.
• Prova del 21/9/2015.
• Prova del 03/02/16
• Prova del 25/02/16
• Prova del 30/06/16
• Prova del 01/09/16
• Prova del 15/09/16
• Prova del 26/04/17
• Prova del 27/06/17
• Prova del 14/07/17
• Prova del 29/09/17
• Prova del 17/01/18
• Prova del 14/02/18
• prova del 27/04/2018
• prova del 28/06/2018
• prova del 19/07/2018
• prova del 14/09/2018
• prova del 17/01/2019
• prova del 7/02/2019
• prova del 17/04/19
• prova del 27/06/19
• prova del 12/07/19
• prova del 09/09/19
• prova del 24/01/20
• prova del 18/02/20

Vecchi temi d'esame ed esercizi (Modulo I/Informatica Teorica)

• Raccolta di vecchi esami.
• Esercizi sulle reti di Petri (raccolti da Andrea Mocci).
• I prova 2003-04.
• II prova 2003-04.
• I recupero 2003-04.
• II recupero 2003-04.
• recupero finale 2003-04.
• Testo e soluzioni della I prova 2005.
• Testo e soluzioni della II prova 2005.
• Testo e soluzioni del I recupero 2005.
• Testo e soluzioni del II recupero 2005.
• Testo e soluzioni del III recupero 2005.
• I prova 2005-06.
• II prova 2005-06.
• I recupero 2005-06.
• II recupero 2005-06.
• soluzioni III recupero 2005-2006.
• I prova 2006-07.
• II prova 2007.
• Testo e soluzioni della prova del 17/7/07.
• Testo e soluzioni della prova dell'11/9/07.
• Testo e soluzioni della prova del 13/2/2008.
• I prova 2007-08.
• II prova 2007-08.
• prova del 16/7/2008.
• prova del 8/9/2008.
• prova del 3/2/2009.
• prova del 6/5/2009.
• prova dell'1/7/2009.
• prova del 16/7/2009.
• prova dell'1/9/2009.
• prova del 3/2/2010.
• I prova intermedia Maggio 2010.
• II prova intermedia Giugno 2010.
• prova del 13/7/2010.
• prova del 3/9/2010.
• prova intermedia del 15/11/2010.
• prova intermedia del 4/2/2011
• prova del 4/2/2011 + soluzioni.
• prova del 25/2/2011 e le relative soluzioni.
• prova del 6/7/2011.
• prova dell'8/9/2011.

Vecchi temi d'esame ed esercizi (Modulo II/Informatica 3)

• Esempi di esami di algoritmi da un vecchio corso.
• Esempi di valutazione complessita' (cicli), raccolti da Matteo Rossi.
• Esercizi su definizione di algoritmi, raccolti da Matteo Rossi.

Modalita' di svolgimento delle prove di verifica

Le prove d'esame assegnano 33 punti che corrispondono al voto massimo di 30 e lode. Le prove constano di una verifica scritta. Testi e appunti sono consultabili durante l'esame.

Ricevimento

Martedi ore 16.30 N.B. ricevo senza problemi anche su appuntamento - contattatemi pure via email o datemi un colpo di telefono.

Esercitatore: Achille Frigeri.