INFORMAZIONI SU

Programmazione e laboratorio

Programma dell'insegnamento - Corso di laurea in Informatica

Docente

  • Prof. Claudio Mirolo

Indirizzo e-mail

claudio.mirolo@uniud.it

Indirizzo Pagina Web Personale

Sito Web http://www.dimi.uniud.it/claudio/

Crediti

12 CFU

Finalità e Obiettivi Formativi

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.

Programma

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.

 

Contenuti del corso

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; protocollo e incapsulamento dei dati; costruttori e metodi. 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.


Seconda parte:
- Spazi vettoriali, dipendenza ed indipendenza lineare, basi e dimensione.
Applicazioni lineari.
- Matrici, somma, prodotto, inversa e determinante di matrici. Relazione tra applicazioni lineari e matrici.
- Sistemi Lineari.
- Autovalori ed autovettori di un'applicazione lineare.
- Spazi Euclidei.

Attività di Laboratorio

Le attività di Laboratorio (circa 36 ore) consistono nello sviluppo e nella sperimentazione di programmi che applicano le tecniche introdotte a lezione. All’inizio di ogni sessione viene presentato un problema, quindi gli studenti progettano e realizzano la soluzione individualmente o collaborando in piccoli gruppi, interagendo se necessario con il docente.

Prerequisiti

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

Bibliografia

Testo di riferimento per la programmazione funzionale:

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

Testo di riferimento per la programmazione imperativa e orientata agli oggetti:

Robert Sedgewick, Kevin Wayne

Introduction to Programming in Java

Addison-Wesley, 2007  (ISBN: 0-321-49805-4)

Inoltre:

Appunti tratti dalle lezioni; esempi ed esercizi disponibili attraverso pagine web del corso.

- Algebra lineare, di S. Lang

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. Alle prove orale e di laboratorio sono ammessi gli studenti che hanno conseguito una valutazione complessiva di almeno 15 punti su 30 nelle prove di accertamento e che hanno inoltre sviluppato il codice che risolve i problemi assegnati nella parte laboratoriale del corso. 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. Durante le prove scritte è consentito consultare libri e appunti. Numerosi esempi di prove scritte e i problemi di laboratorio sono pubblicati attraverso le pagine del corso.

Sono inoltre previste 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 prova orale. Nel caso lo studente si cimenti in più di una prova resta valida la migliore valutazione conseguita.

Gli studenti che abbiano seguito il corso nei due anni precedenti possono eventualmente concordare con il docente un programma d’esame compatibile con quello da loro seguito.

Orario di ricevimento

Il docente riceve su appuntamento da concordare direttamente a lezione o via e-mail.