PROGRAMMAZIONE E LABORATORIO

Anno accademico 2020-2021

PROGRAMMAZIONE E LABORATORIO

Docenti:
Claudio Mirolo
Giuseppe Serra
Emanuele Scapin
Anno di corso: 1
Totale crediti: 12
Tipologia: Caratterizzante
Periodo didattico: Annualità
Prerequisiti. Conoscenze matematiche di base, del livello acquisito nella scuola superiore.
Metodi didattici. Lezioni teoriche e attività pratiche di laboratorio.L’approccio seguito è di tipo “functional-first” (IEEE-CS/ACM Computing Curricula 2001).
Modalità di verifica. L’esame prevede due prove scritte di che si svolgono al termine dei due periodi didattici in cui è articolato il corso, una prova pratica di laboratorio e una prova orale.

Le prove sono principalmente volte a verificare le capacità dello studente di capire programmi di piccolo scala e di riuscire a impostare e organizzare soluzioni algoritmiche di semplici problemi.

Altre informazioni. Ulteriore materiale digitale, incluso il codice dei principali programmi discussi, è disponibile attraverso le pagine dedicate al corso:

https://www.dmif.uniud.it/claudio/teaching/programmazione

OBIETTIVI FORMATIVI

Il corso introduce i fondamenti scientifici 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.

L’approccio seguito è di tipo functional-first (IEEE-CS/ACM Computing Curricula 2001); il percorso didattico si articola attorno ai 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.

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, imperativo 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.

Le attività di Laboratorio consistono nel progetto, nello sviluppo e nella sperimentazione di programmi di piccole dimensioni, e hanno lo scopo di stimolare le capacità di organizzazione e lavoro autonomo da parte degli studenti.

Descrittori di Dublino

CAPACITÀ RELATIVE ALLE DISCIPLINE

Lo/la studente/ssa dovrà:

1.1. Conoscenza e capacità di comprensione

– Acquisire le basi della programmazione funzionale e imperativa;

– Acquisire i primi rudimenti della programmazione object-oriented;

– Conoscere sintassi e semantica dei principali costrutti e delle principali strutture dati nei linguaggi Scheme e Java;

– Conoscere le relazioni fra ricorsione e iterazione;

– Conoscere le relazioni fra i concetti di classe e oggetto.

1.2 Capacità di applicare conoscenza e comprensione

– Saper codificare semplici algoritmi ricorsivi e imperativi;

– Saper analizzare la logica di un semplice programma ricorsivo o imperativo per verificarne la correttezza rispetto alle specifiche e per stimarne le prestazioni;

– Saper riconoscere quando è appropriato e saper applicare tecniche di memoization e programmazione dinamica per migliorare le prestazioni di programmi ricorsivi;

– Saper realizzare una classe rispettando il protocollo specificato.

CAPACITÀ TRASVERSALI / SOFT SKILLS

Lo/la studente/ssa dovrà:

2.1 Autonomia di giudizio

– Saper analizzare i problemi al fine di identificare gli aspetti che si prestano ad essere affrontati attraverso programmi, esprimere le specifiche in maniera precisa e scegliere gli strumenti di programmazione adatti allo scopo;

– Saper applicare le proprie conoscenza per capire i processi di elaborazione dell’informazione.

2.2 Abilità comunicative.

– Essere in grado di confrontarsi con i pari al fine di progettare o migliorare la soluzione algoritmica di un problema.

2.3 Capacità di apprendimento

– Essere in grado di attuare sperimentazioni sistematiche di un programma per verificarne la correttezza e per stimarne le prestazioni;

– Essere in grado di orientarsi nell’ambito dei linguaggi di programmazione e di apprendere autonomamente nuovi linguaggi.

CONTENUTI

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. Gli esempi relativi all’astrazione procedurale e sui dati sono affrontati applicando il paradigma di programmazione funzionale, per passare al paradigma imperativo e ai rudimenti di quello object-oriented nell’ultima parte del corso che tratta l’astrazione sullo stato. Le attività di Laboratorio 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.

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 Java) Introduzione all’astrazione sui dati attraverso semplici strutture. Strutture dati di base: liste “funzionali” e procedure che operano sulle liste. 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). Esempi di astrazione sui dati.

​Parte III – Astrazione sullo stato (linguaggio 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. Esempi di astrazione sullo stato. Ricorsione e iterazione: trasformazione di programmi ricorsivi in programmi iterativi utilizzando uno stack. Programmi iterativi: correttezza e terminazione. Concetti di asserzione, invariante dell’iterazione e funzione di terminazione.

TESTI DI RIFERIMENTO

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, 1999 (ISBN: 0534952119), http://gustavus.edu/+max/concrete-abstractions-pdfs/index.htm

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

​Robert Sedgewick & Kevin Wayne, Computer Science: An Interdisciplinary Approach, Addison-Wesley, 2016 (ISBN: 9780134076454)