Docente

Prof. Aggr. Claudio Mirolo claudio.mirolo@uniud.it http://www.dimi.uniud.it/claudio/

Crediti

12 CFU

Finalità

Obiettivi del corso
Il corso introduce i fondamenti culturali e metodologici della programmazione e si propone di mettere lo studente in condizione di cogliere pienamente la natura di questa attività, stimolando inoltre un atteggiamento critico nei confronti degli strumenti utilizzati.
Al termine del corso lo studente dovrebbe aver acquisito le competenze di base e le capacità operative necessarie al fine di progettare, organizzare e formalizzare programmi di piccole dimensioni, sviluppati secondo i paradigmi funzionale e object-oriented. Dovrebbe inoltre essere in grado di analizzare la struttura logica di un programma al fine di verificarne la correttezza in relazione alle specifiche.

Organizzazione del corso
Il percorso didattico muove dalla discussione di esempi e articola la propria riflessione sui principali processi di astrazione che consentono di gestire la complessità dei problemi affrontati in ambito informatico: l’astrazione procedurale, l’astrazione sui dati e l’astrazione sullo stato, mettendo in rilievo il ruolo preminente delle capacità organizzative del pensiero rispetto alle caratteristiche specifiche dei linguaggi di programmazione.
L’approccio seguito è di tipo functional-first (IEEE-CS/ACM Computing Curricula 2001): gli esempi relativi all’astrazione procedurale e sui dati sono affrontati applicando il paradigma di programmazione funzionale, per passare infine al paradigma imperativo e ai rudimenti di quello object-oriented nell’ultima parte del corso che tratta l’astrazione sullo stato.

Prerequisiti
Conoscenze matematiche di base, del livello acquisito nella scuola superiore.

Programma

Parte I - Astrazione procedurale (linguaggio Scheme)
Algoritmi basati sul calcolo di espressioni numeriche e non numeriche. Approccio funzionale: procedure come astrazione di espressioni. Costrutti di scelta binaria (if) e multipla (cond). Valori numerici, booleani, caratteri e stringhe. Procedure ricorsive. Definizioni ricorsive ben fondate. Modello di valutazione per sostituzione e riduzione. Costrutto let. Ricorsione generale e ricorsione di coda (tail recursion). Verfica della correttezza dei programmi ricorsivi attraverso dimostrazioni per induzione. Ricorsione ad albero e complessità computazionale. Procedure con argomenti e/o valori procedurali.
Parte II - Astrazione sui dati (linguaggio Scheme)
Introduzione all’astrazione sui dati attraverso semplici strutture. Strutture dati di base: coppie, liste e procedure che operano sulle liste. Liste ordinate e algoritmi di ricerca. Algoritmi di ordinamento e confronto dei costi computazionali. Specifica astratta di una struttura dati e varietà delle scelte realizzative. Strutture dati dal punto di vista dell’utilizzatore (protocollo) e dal punto di vista dell’implementatore (comportamento). Strutture dati notevoli: pile, code, alberi e relative applicazioni. Alberi binari: alberi di valutazione delle espressioni, alberi binari di ricerca. Schemi di visita di alberi: visita anticipata, posticipata e simmetrica.
Parte III - Astrazione sullo stato (linguaggi Scheme e Java)
Concetto di stato e paradigma imperativo. Principali comandi e costrutti imperativi del linguaggio Java. Array (vettori, matrici) e operazioni sugli array. Rivisitazione di strutture di dati elementari attraverso il paradigma imperativo. Tecniche di memoization e programmazione dinamica. Paradigmi funzionale e imperativo a confronto. Astrazione sullo stato: concetti di classe, oggetto, costruttore e metodo. Realizzazione di strutture dinamiche in Java: pile, code e alberi. Programmi iterativi: correttezza e terminazione. Concetti di asserzione, invariante dell’iterazione e funzione di terminazione.
Concetti ricorrenti: Astrazione procedurale; modello computazionale; schema ricorsivo; ricorsione di coda; ricorsione ad albero; schema imperativo; iterazione; algoritmo; complessità computazionale; precondizioni e postcondizioni (specifiche); invariante; terminazione; astrazione sui dati; astrazione sullo stato; schema orientato agli oggetti; protocollo; istanza (oggetto); incapsulamento dei dati; organizzazione modulare.

Bibliografia

- Max Hailperin, Barbara Kaiser, Karl Knight, "Concrete Abstractions: An Introduction to Computer Science Using Scheme" - Brooks/Cole Publishing Company, 1999 (ISBN: 0-534-95211-9)
http://gustavus.edu/+max/concrete-abstractions-pdfs/index.html
- Walter Savitch, Frank M. Carrano, "Programmazione con Java", Prentice-Hall, 2010 (Edizione italiana; ISBN: 9788871926148)
- Appunti tratti dalle lezioni; esempi ed esercizi pubblicati sulle pagine web del corso

Modalità d'esame

L’esame di Programmazione prevede due prove di accertamento, che si svolgono al termine dei due periodi didattici in cui è articolato il corso, una prova di Laboratorio e una prova orale. All’orale sono ammessi gli studenti che hanno conseguito una valutazione complessiva di almeno 15 punti su 30 nelle prove di accertamento e che hanno inoltre superato la prova di Laboratorio. La discussione orale è opzionale per valutazioni delle prove di accertamento comprese fra 20 e 28 punti. La prova di Laboratorio e la prova orale, nel caso quest’ultima venga sostenuta, concorrono alla valutazione finale nei termini di una media pesata. Durante le prove scritte è consentito consultare libri e appunti.
La valutazione di ciascuna delle prove di accertamento viene espressa nei seguenti livelli qualitativi: ottimo, buono, discreto, sufficiente, quasi sufficiente, insufficiente (la valutazione di una singola prova non pregiudica di per se l’ammissione all’orale). La valutazione complessiva delle prove di accertamento o dei recuperi che vertono sull’intero programma viene espressa con un punteggio da 18 a 30, se sufficiente; da 15 a 17, se consente di sostenere la prova orale; insufficiente altrimenti.
Il primo appello scritto di Programmazione consiste normalmente nello svolgimento della seconda prova di accertamento. A partire dal secondo appello sono invece previste unicamente prove scritte di recupero, che vertono sull’intero programma del corso, rivolte a coloro che non abbiano potuto partecipare alle prove di accertamento o vi abbiano conseguito una valutazione insufficiente per l’ammissione all’orale, o che comunque desiderino migliorare il profitto. Indipendentemente dalla valutazione, le prove scritte di recupero non consentono l’esonero dalla discussione orale. Nel caso lo studente si cimenti in più di una prova resta valida la migliore valutazione conseguita.
Quando tutte le prove richieste (prove scritte, prova di laboratorio, eventuale prova orale) sono state sostenute, ai fini della registrazione dell’esame, che avviene per via elettronica, è necessario che lo studente confermi personalmente l’accettazione della valutazione finale conseguita presentandosi a una delle sessioni di orali previste dal calendario ufficiale pubblicato a cura della Facoltà. In mancanza di un tale assenso esplicito, non si procederà alla verbalizzazione e quindi il superamento dell’esame non potrà essere certificato da parte della segreteria studenti. 

Ulteriori informazioni sul corso e sulle lezioni, in particolare gli esempi discussi in classe e i temi d’esame, sono resi disponibili attraverso le pagine del corso all’indirizzo:
http://www.dimi.uniud.it/claudio/teaching/programmazione/