PRESENTAZIONE

Nel modulo teorico, il corso presenta i modelli formali di soluzione di problemi mediante calcolatore intesa come trattamento di linguaggi e le relative problematiche di computabilità e complessità. Il corso considera le principali tecniche per la costruzione di algoritmi e strutture dati corrette ed efficienti. Nel modulo di laboratorio vengono esposti strumenti di progettazione e programmazione in un linguaggio orientato agli oggetti finalizzato allo sviluppo di un interprete.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

L’insegnamento è composto da due moduli, dedicati rispettivamente alla teoria della computazione e alla programmazione orientata agli oggetti. Il primo modulo fornisce le basi teoriche sui modelli di computazione per il trattamento dei linguaggi formali (automi, grammatiche, macchina di Turing), introducendo i concetti fondamentali di computabilità e complessità, nonché le principali strategie di progettazione e analisi di algoritmi. Il secondo modulo affronta gli aspetti pratici della progettazione software in C++ (standard 2020), con particolare attenzione alla programmazione orientata agli oggetti, all’uso della libreria standard e ai principi di progettazione (UML, design pattern). Il corso si propone di sviluppare la capacità di formalizzare e risolvere problemi computazionali, progettare soluzioni algoritmiche corrette ed efficienti, e realizzarle attraverso un linguaggio di programmazione moderno e potente.

PREREQUISITI

Per la comprensione degli argomenti del corso è necessaria la conoscenza dei concetti di programmazione procedurale (principali tipi di dato scalari e vettoriali, dichiarazione e utilizzo di variabili, scelte condizionali, iterazioni, definizione di funzioni), della programmazione orientata agli oggetti (definizione di classi e classi generiche) e del linguaggio C++ come forniti dai corsi di Fondamenti di Informatica. E' inoltre consigliabile un'esposizione ai concetti di base di insiemistica, matematica discreta e probabilità.

DOCENTI E COMMISSIONI

ESAMI

MODALITA' D'ESAME

L'esame prevede due prove obbligatorie:

- Prova scritta su teoria della computazione, algoritmi e strutture dati
- Realizzazione di un progetto assegnato dal docente

Al termine del primo semestre è prevista una prova scritta intermedia sulla sola teoria della computazione. Tutte le prove scritte prevedono una o più domande aperte. Il progetto viene assegnato al termine del primo semestre e viene svolto individualmente dagli studenti. Il progetto ha validità annuale, ossia l'esame scritto deve essere svolto entro un anno dalla data di consegna del progetto. Il progetto concorre al voto finale per un quarto (25%) del punteggio complessivo, mentre lo scritto concorre ai tre quarti (75%) del punteggio complessivo (25% la parte di teoria della computazione, 50% algoritmi e strutture dati). 

MODALITA' DI ACCERTAMENTO

Il progetto valuterà la capacità dello studente di mettere in pratica i concetti di teoria della computazione nel contesto di un'applicazione semplice ma realistica (ad esempio, un interprete per un linguaggio di programmazione) progettata e realizzata con il linguaggiop C++.

Lo scritto valuterà la comprensione dello studente dei concetti esposti a lezione mediante lo svolgimento di esercizi che prevedono sia la soluzione di problemi sia la dimostrazione di proprietà relativamente alle soluzioni proposte.