PROGRAMMAZIONE II E LABORATORIO M - Z

Anno accademico 2021/2022 - 1° anno - Curriculum Elaborazione Dati e Applicazioni e Curriculum Sistemi e Applicazioni

Docenti

PROGRAMMAZIONE II: Marco Moltisanti
LABORATORIO: Marco Moltisanti

Crediti: 9
SSD: INF/01 - Informatica
Organizzazione didattica: 225 ore d'impegno totale, 153 di studio individuale, 36 di lezione frontale, 24 di esercitazione, 12 di laboratorio
Semestre: 2°

Obiettivi formativi

PROGRAMMAZIONE II
Il corso di Programmazione 2 ha lo scopo di fornire gli strumenti per la risoluzione di semplici problemi connessi all'uso di alcune strutture dati elementari attraverso l'utilizzo della programmazione ad oggetti. In particolare il corso parte dall'introduzione del concetto di modello di dati astratto per poi introdurre ed approfondire diversi modelli dei dati quali: pile, code, liste e alberi e grafi.
1. Conoscenza e capacità di comprensione (knowledge and understanding): l'obiettivo del corso è quello di far acquisire conoscenze che consentano allo studente di comprendere le idee ed i principi che stanno alla base della programmazione orientata agli oggetti; in particolare lo studente acquisirà le conoscenze dei principali costrutti del linguaggio C++ e delle strutture dati di base.
2. Capacità di applicare conoscenza e comprensione (applying knowledge and understanding): lo studente acquisirà le competenze necessarie per utilizzare in modo corretto i concetti legati al polimorfismo, all'ereditarietà e all'uso delle classi. Inoltre, lo studente acquisirà le competenze necessarie ad utilizzare correttamente strutture dati di base quali, liste concatenate, pile, code e alberi binari.
3. Autonomia di giudizio (making judgements): Attraverso esempi concreti di programmazione lo studente sarà in grado di utilizzare autonomamente gli strumenti forniti a lezione.
4. Abilità comunicative (communication skills): lo studente acquisirà le necessarie abilità comunicative e di appropriatezza espressiva nell'ambito della programmazione in C++.
5. Capacità di apprendimento (learning skills): il corso si propone, come obiettivo, di fornire allo studente le necessarie metodologie teoriche e pratiche per poter affrontare e risolvere autonomamente nuove problematiche che dovessero richiedere l'utilizzo della programmazione ad oggetti e delle strutture dati di base.
- Verranno inoltre studiati i principali algoritmi di gestione delle strutture dati. In particolare i principali algoritmi di ordinamento, tra cui bubble sort, insertion sort, quicksort e mergesort.
  Il linguaggio C++ verrà usato come strumento principale per presentare le implementazioni delle strutture dati e degli algoritmi.
  
  Obiettivi formativi generali dell'insegnamento in termini di risultati di apprendimento attesi.
- LABORATORIO
  Il corso di Programmazione 2 ha lo scopo di fornire gli strumenti per la risoluzione di semplici problemi connessi all'uso di alcune strutture dati elementari attraverso l'utilizzo della programmazione ad oggetti. In particolare il corso parte dall'introduzione del concetto di modello di dati astratto per poi introdurre ed approfondire diversi modelli dei dati quali: pile, code, liste e alberi e grafi.
  
  Verranno inoltre studiati i principali algoritmi di gestione delle strutture dati. In particolare i principali algoritmi di ordinamento, tra cui bubble sort, insertion sort, quicksort e mergesort.
  Il linguaggio C++ verrà usato come strumento principale per presentare le implementazioni delle strutture dati e degli algoritmi.
  
  Obiettivi formativi generali dell'insegnamento in termini di risultati di apprendimento attesi.
  
  Conoscenza e capacità di comprensione (knowledge and understanding): l'obiettivo del corso è quello di far acquisire conoscenze che consentano allo studente di comprendere le idee ed i principi che stanno alla base della programmazione orientata agli oggetti; in particolare lo studente acquisirà le conoscenze dei principali costrutti del linguaggio C++ e delle strutture dati di base.
  1. Capacità di applicare conoscenza e comprensione (applying knowledge and understanding): lo studente acquisirà le competenze necessarie per utilizzare in modo corretto i concetti legati al polimorfismo, all'ereditarietà e all'uso delle classi. Inoltre, lo studente acquisirà le competenze necessarie ad utilizzare correttamente strutture dati di base quali, liste concatenate, pile, code e alberi binari.
  2. Autonomia di giudizio (making judgements): Attraverso esempi concreti di programmazione lo studente sarà in grado di utilizzare autonomamente gli strumenti forniti a lezione.
  3. Abilità comunicative (communication skills): lo studente acquisirà le necessarie abilità comunicative e di appropriatezza espressiva nell'ambito della programmazione in C++.
  4. Capacità di apprendimento (learning skills): il corso si propone, come obiettivo, di fornire allo studente le necessarie metodologie teoriche e pratiche per poter affrontare e risolvere autonomamente nuove problematiche che dovessero richiedere l'utilizzo della programmazione ad oggetti e delle strutture dati di base.

Modalità di svolgimento dell'insegnamento

PROGRAMMAZIONE II
L'insegnamento sarà svolto attraverso delle lezioni frontali (per un totale di 72 ore) in cui verranno presentati i contenuti del corso, anche attraverso delle dimostrazioni pratiche di programmazione in aula. Lo studente avrà a disposizione ulteriori ore di lezione frontale da svolgere con un tutor didattico, durante le quali avrà la possibilità di perfezionare la propria preparazione o colmare eventuali lacune. Inoltre lo studente avrà a disposizione una piattaforma di apprendimento attraverso la quale sarà possibile esercitarsi durante le ore di studio e autovalutarsi sui contenuti appresi a lezione. La medesima piattaforma fornisce un valido strumento per la preparazione all'esame.
- LABORATORIO
  L'insegnamento sarà svolto attraverso delle lezioni frontali (per un totale di 72 ore) in cui verranno presentati i contenuti del corso, anche attraverso delle dimostrazioni pratiche di programmazione in aula. Lo studente avrà a disposizione ulteriori ore di lezione frontale da svolgere con un tutor didattico, durante le quali avrà la possibilità di perfezionare la propria preparazione o colmare eventuali lacune. Inoltre lo studente avrà a disposizione una piattaforma di apprendimento attraverso la quale sarà possibile esercitarsi durante le ore di studio e autovalutarsi sui contenuti appresi a lezione. La medesima piattaforma fornisce un valido strumento per la preparazione all'esame.

Prerequisiti richiesti

PROGRAMMAZIONE II
Lo studente che accede al corso di Porgrammazione II dovrà conoscere i fondamenti della programmazione ad oggetti e del paradigma di programmazione imperativa. per poter sostenere l'esame è obbligatorio aver già superato l'esame di Programmazione I
- LABORATORIO
  Lo studente che accede al corso di Porgrammazione II dovrà conoscere i fondamenti della programmazione ad oggetti e del paradigma di programmazione imperativa. per poter sostenere l'esame è obbligatorio aver già superato l'esame di Programmazione I

Frequenza lezioni

PROGRAMMAZIONE II
La frequenza delle lezioni non è obbligatoria ma è fortemente consigliata.
- LABORATORIO
  La frequenza delle lezioni non è obbligatoria ma è fortemente consigliata.

Contenuti del corso

PROGRAMMAZIONE II
Il Programma didatico è diviso nelle seguenti parti:

Parte 1: Cenni di complessità e tecniche ricorsive: applicazione all’ordinamento e alla selezione.
- Cenni di complessità asintotica: Complessità di un problema computazionale, complessità spaziale e temporale, caso pessimo, caso migliore e caso medio, limite superiore, calcolo del limite superiore del tempo di esecuzione, alcuni semplici casi d’esempio.
- Algoritmi elementari di ordinamento e ricerca: Analisi degli algoritmi di ordinamento elementari: ordinamento per selezione, ordinamento per inserimento, ordinamento a bolle. Ricerca sequenziale e binaria nei vettori, analisi degli algoritmi di ricerca.
- Ricorsione ed algoritmi di ordinamento e ricerca basati sulla ricorsione: Funzioni ricorsive, confronto tra ricorsione e iterazione, ricorsione di coda e ricorsione doppia, trasformazione di un algoritmo ricorso in un algoritmo iterativo, esempi di utilizzo della ricorsione, algoritmo Quicksort, algoritmo Mergesort, algoritmi di selezione basati sulla ricorsione.
Parte 2: Programmazione avanzata a oggetti - ripasso ed approfondimento
- Classi e oggetti: funzioni membro, metodi set, get e predicati, costruttori e distruttori standard, overloading e overriding di funzioni membro, altri costruttori.
- Classi derivate: ereditarietà e polimorfismo: Classi derivate, tipi di ereditarietà, distruttori, ereditarietà multipla e composizione, binding, funzioni virtuali, polimorfismo, vantaggi del polimorfismo.
- Template: Genericità, template in C++, template di funzioni, templatedi classi.
- Sovraccaricamento degli operatori: Sovraccaricamento degli operatori unari e binari, sovraccaricamento degli operatori + e - e dell’operatore di assegnamento, sovraccaricamento degli operatori di inserimento, estrazione, new e delete, conversione di dati e operatori di conversione forzata di tipi.
- Implementazione di un insieme mediante array dinamici: Interfaccia per l’implementazione di un insieme, espansione e contrazione di un array, elementi privati ed elementi pubblici, iteratore degli elementi di un insieme.
Parte 3: Strutture dati elementari e loro implementazione in C++
- Liste: Implementazione di un insieme mediante liste, liste ordinate e liste non ordinate; operazioni con le liste: inserimento, cancellazione e ricerca; implementazione standard di una lista ed implementazione mediante sentinelle, liste doppiamente concatenate e liste circolari.
- Pile e code: Concetto e gestione di una pila, operazioni enqueue e dequeue; concetto e gestione di una coda, operazioni push e pop. Implementazione di pile e code mediante liste concatenate e mediante array. Utilizzo di uno stack per la conversione di una procedura ricorsiva in una procedura iterativa.
- Alberi: Gli alberi, alberi binari ed n-ari, alberi posizionali, struttura di un albero binario, alberi di espressione, visita di un albero: preorder, postorder e inorder, implementazione iterativa ed implementazione ricorsiva; alberi binari di ricerca: inserimento, ricerca e cancellazione, iteratore degli elementi di un albero; calcolo della profondità di unnodo, calcolo dell’altezza di un albero.
- Grafi: Definizione di grafo, grafi orientati e non orientati, inserimento di un nodo, rappresentazione con matrici di adiacenza e con liste di adiacenza, inserimento di un arco. Visita in ampiezza e calcolo dei cammini minimi, visita in profonditàe calcolo dei tempi di inizio e fine visita, colorazione dei nodi ed identificazione degli archi, aciclicità di un grafo, calcolo dell’ordinamento topologico, calcolo delle componenti connesse e delle componenti fortemente connesse di un grafo.
Esercitazioni: Risoluzione guidata di specifici problemi.
- LABORATORIO
  Il Programma didatico è diviso nelle seguenti parti:
  
  Parte 1: Cenni di complessità e tecniche ricorsive: applicazione all’ordinamento e alla selezione.
  - Cenni di complessità asintotica: Complessità di un problema computazionale, complessità spaziale e temporale, caso pessimo, caso migliore e caso medio, limite superiore, calcolo del limite superiore del tempo di esecuzione, alcuni semplici casi d’esempio.
  - Algoritmi elementari di ordinamento e ricerca: Analisi degli algoritmi di ordinamento elementari: ordinamento per selezione, ordinamento per inserimento, ordinamento a bolle. Ricerca sequenziale e binaria nei vettori, analisi degli algoritmi di ricerca.
  - Ricorsione ed algoritmi di ordinamento e ricerca basati sulla ricorsione: Funzioni ricorsive, confronto tra ricorsione e iterazione, ricorsione di coda e ricorsione doppia, trasformazione di un algoritmo ricorso in un algoritmo iterativo, esempi di utilizzo della ricorsione, algoritmo Quicksort, algoritmo Mergesort, algoritmi di selezione basati sulla ricorsione.
  Parte 2: Programmazione avanzata a oggetti - ripasso ed approfondimento
  - Classi e oggetti: funzioni membro, metodi set, get e predicati, costruttori e distruttori standard, overloading e overriding di funzioni membro, altri costruttori.
  - Classi derivate: ereditarietà e polimorfismo: Classi derivate, tipi di ereditarietà, distruttori, ereditarietà multipla e composizione, binding, funzioni virtuali, polimorfismo, vantaggi del polimorfismo.
  - Template: Genericità, template in C++, template di funzioni, templatedi classi.
  - Sovraccaricamento degli operatori: Sovraccaricamento degli operatori unari e binari, sovraccaricamento degli operatori + e - e dell’operatore di assegnamento, sovraccaricamento degli operatori di inserimento, estrazione, new e delete, conversione di dati e operatori di conversione forzata di tipi.
  - Implementazione di un insieme mediante array dinamici: Interfaccia per l’implementazione di un insieme, espansione e contrazione di un array, elementi privati ed elementi pubblici, iteratore degli elementi di un insieme.
  Parte 3: Strutture dati elementari e loro implementazione in C++
  - Liste: Implementazione di un insieme mediante liste, liste ordinate e liste non ordinate; operazioni con le liste: inserimento, cancellazione e ricerca; implementazione standard di una lista ed implementazione mediante sentinelle, liste doppiamente concatenate e liste circolari.
  - Pile e code: Concetto e gestione di una pila, operazioni enqueue e dequeue; concetto e gestione di una coda, operazioni push e pop. Implementazione di pile e code mediante liste concatenate e mediante array. Utilizzo di uno stack per la conversione di una procedura ricorsiva in una procedura iterativa.
  - Alberi: Gli alberi, alberi binari ed n-ari, alberi posizionali, struttura di un albero binario, alberi di espressione, visita di un albero: preorder, postorder e inorder, implementazione iterativa ed implementazione ricorsiva; alberi binari di ricerca: inserimento, ricerca e cancellazione, iteratore degli elementi di un albero; calcolo della profondità di unnodo, calcolo dell’altezza di un albero.
  - Grafi: Definizione di grafo, grafi orientati e non orientati, inserimento di un nodo, rappresentazione con matrici di adiacenza e con liste di adiacenza, inserimento di un arco. Visita in ampiezza e calcolo dei cammini minimi, visita in profonditàe calcolo dei tempi di inizio e fine visita, colorazione dei nodi ed identificazione degli archi, aciclicità di un grafo, calcolo dell’ordinamento topologico, calcolo delle componenti connesse e delle componenti fortemente connesse di un grafo.
  Esercitazioni: Risoluzione guidata di specifici problemi.

Testi di riferimento

PROGRAMMAZIONE II
Libro di testo.

Fondamenti di Programmazione in C++
Algoritmi, strutture dati e oggetti
Autore: Luis Joyanes Aguilar
Casa Editrice: McGraw-Hill
sito web del libro

Questo volume introduce ai principi della programmazione scegliendo come linguaggio didattico proprio il C++, nonostante non lo si possa certamente definire tale. Il motivo che ci spinge in questa direzione è il desiderio di ridurre i tempi di formazione del programmatore, facendolo applicare, fin dai primi algoritmi, su un linguaggio professionale realmente utilizzato in grandi suite software.

Introduction to Algorithms

T. H Cormen
C. E. Leiserson
R. L. Rivest
C. Stein
The MIT Press

È il principale testo di riferimento nei corsi di algoritmi in molte università. L’approccio è graduale, i concetti vengono trattati partendo dai più semplici per arrivare, passo dopo passo, a quelli più avanzati; ogni capitolo presenta una classe di algoritmi, le relative tecniche di progettazione, un’area di applicazioni e gli argomenti correlati. Ritenendo importante il concetto di "efficienza", gli autori hanno incluso anche l’analisi dei tempi di esecuzione di ciascun algoritmo. Completa il testo un efficace apparato pedagogico costituito da circa 1000 esercizi e 150 problemi e casi di studio.

Libri consigliati.

Effective C++ e More Effective C++
Algoritmi, strutture dati e oggetti
Autore: Scott Meyers
Casa Editrice: Addison-Wesley
sito dei libri

Il testo è consigliato agli studenti che intendono approfondire il tema della programmazione C++ avanzata. Ogni capitolo del libro è costituito da più "temi" presentati sotto forma di brevi trattazioni indipendenti che forniscono consigli specifici, spiegazioni sulle sottigliezze del C++ ed esempi di codice esaurienti. La descrizione articolata di ogni tema rende chiaro cosa fare, cosa non fare e perché.
- LABORATORIO
  Libro di testo.
  
  Fondamenti di Programmazione in C++
  Algoritmi, strutture dati e oggetti
  Autore: Luis Joyanes Aguilar
  Casa Editrice: McGraw-Hill
  sito web del libro
  
  Questo volume introduce ai principi della programmazione scegliendo come linguaggio didattico proprio il C++, nonostante non lo si possa certamente definire tale. Il motivo che ci spinge in questa direzione è il desiderio di ridurre i tempi di formazione del programmatore, facendolo applicare, fin dai primi algoritmi, su un linguaggio professionale realmente utilizzato in grandi suite software.
  
  Introduction to Algorithms
  
  T. H Cormen
  C. E. Leiserson
  R. L. Rivest
  C. Stein
  The MIT Press
  
  È il principale testo di riferimento nei corsi di algoritmi in molte università. L’approccio è graduale, i concetti vengono trattati partendo dai più semplici per arrivare, passo dopo passo, a quelli più avanzati; ogni capitolo presenta una classe di algoritmi, le relative tecniche di progettazione, un’area di applicazioni e gli argomenti correlati. Ritenendo importante il concetto di "efficienza", gli autori hanno incluso anche l’analisi dei tempi di esecuzione di ciascun algoritmo. Completa il testo un efficace apparato pedagogico costituito da circa 1000 esercizi e 150 problemi e casi di studio.
  
  Libri consigliati.
  
  Effective C++ e More Effective C++
  Algoritmi, strutture dati e oggetti
  Autore: Scott Meyers
  Casa Editrice: Addison-Wesley
  sito dei libri
  
  Il testo è consigliato agli studenti che intendono approfondire il tema della programmazione C++ avanzata. Ogni capitolo del libro è costituito da più "temi" presentati sotto forma di brevi trattazioni indipendenti che forniscono consigli specifici, spiegazioni sulle sottigliezze del C++ ed esempi di codice esaurienti. La descrizione articolata di ogni tema rende chiaro cosa fare, cosa non fare e perché.

Verifica dell'apprendimento

Modalità di verifica dell'apprendimento

PROGRAMMAZIONE II
Modalità di verifica dell'apprendimento
- PROGRAMMAZIONE II
  L'esame si svolgerà in tre prove, la prima scritta, la seconda pratica e la terza orale.
  
  - Prima prova scritta: l'esame scritto consisterà di una serie di quesiti teorici e pratici su tutto il programma didattico. L'esame scritto si svolgerà in presenza, in ottemperanza alle disposizioni delle autorità in relazione alla situazione epidemiologica. Se tali disposizioni non dovessero permettere l'esame in presenza, la prova verrà svolta in modalità remota.
  - Seconda prova pratica: gli studenti che superano la prima prova riceveranno il testo di un problema da risolvere mediante l'implementazione di un progetto software. Il tempo a disposizione per la consegna del progetto sarà di circa 48 ore. I progetti dovranno essere caricati su uno specifico repository github predisposto dai docenti. Gli studenti dovranno utilizzare un account github associato al proprio account istituzionale @studium.unict.it
  - Terza prova orale: dopo la scadenza della consegna del progetto, gli studenti verranno convocati per svolgere la prova orale. Durante la prova orale verranno posti dei quesiti riguardanti le scelte algoritmiche ed implementative del progetto, nonchè dei quesiti sui contenuti del corso.
- LABORATORIO
  L'esame si svolgerà in tre prove, la prima scritta, la seconda pratica e la terza orale.
  
  - Prima prova scritta: l'esame scritto consisterà di una serie di quesiti teorici e pratici su tutto il programma didattico. L'esame scritto si svolgerà in presenza, in ottemperanza alle disposizioni delle autorità in relazione alla situazione epidemiologica. Se tali disposizioni non dovessero permettere l'esame in presenza, la prova verrà svolta in modalità remota.
  - Seconda prova pratica: gli studenti che superano la prima prova riceveranno il testo di un problema da risolvere mediante l'implementazione di un progetto software. Il tempo a disposizione per la consegna del progetto sarà di circa 48 ore. I progetti dovranno essere caricati su uno specifico repository github predisposto dai docenti. Gli studenti dovranno utilizzare un account github associato al proprio account istituzionale @studium.unict.it
  - Terza prova orale: dopo la scadenza della consegna del progetto, gli studenti verranno convocati per svolgere la prova orale. Durante la prova orale verranno posti dei quesiti riguardanti le scelte algoritmiche ed implementative del progetto, nonchè dei quesiti sui contenuti del corso.

Esempi di domande e/o esercizi frequenti

PROGRAMMAZIONE II

I testi degli esercizi svolti in laboratorio in C++ saranno disponibili online, verranno inoltre effettuate delle esercitazioni e simulazioni d'esame durante il corso. Inoltre è consigliato l'utilizzo della piattaforma di apprendimento Coding Contest attraverso la quale sarà possibile esercitarsi durante le ore di studio e autovalutarsi sui contenuti appresi a lezione.

Esempi di domande prova scritta:

Qual è l'output del seguente programma ?

Scegliere la corretta definizione di una funzione virtuale pura

Cosa intendiamo dire quando diciamo che un algorimo X è asintoticamente più efficiente di un altro algoritmo Y ?

LABORATORIO