PROGRAMMAZIONE II E LABORATORIO A - E
Modulo PROGRAMMAZIONE II

Anno accademico 2022/2023 - Docente: ALESSANDRO ORTIS

Risultati di apprendimento attesi

Il corso di Programmazione 2 ha lo scopo di introdurre il paradigma della programmazione oggetti (OOP) e fornire le competenze per la risoluzione di semplici problemi attraverso l'utilizzo della definizione di classi e gli strumenti della OOP, utilizzando il linguaggio C++. In particolare il corso parte dall'introduzione del concetto di astrazione, per poi illustrare i meccanismi di progettazione e implementazione di sistemi di oggetti interagenti mediante la definizione di classi. 

 

Obiettivi formativi generali dell'insegnamento in termini di risultati di apprendimento attesi.

 

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.

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.

 Modalità di svolgimento dell'insegnamento

L'insegnamento sarà 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 avrà a disposizione ulteriori ore di lezione frontale da svolgere con un tutor didattico, durante le quali avrà la possibilità di perfezionare la propria preparazione o colmare eventuali lacune.

Modalità di svolgimento dell'insegnamento

L'insegnamento sarà 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 avrà a disposizione ulteriori ore di lezione frontale da svolgere con un tutor didattico, durante le quali avrà la possibilità di perfezionare la propria preparazione o colmare eventuali lacune. Inoltre lo studente avrà a disposizione una piattaforma di apprendimento attraverso la quale sarà 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

Lo studente che accede al corso di Programmazione II dovrà conoscere i fondamenti della programmazione e del paradigma di programmazione imperativa. per poter sostenere l'esame è obbligatorio aver già superato l'esame di Programmazione I.

Frequenza lezioni

La frequenza delle lezioni non è obbligatoria ma è fortemente consigliata.

Contenuti del corso

Elementi di programmazione in C++

  • Namespace, oggetti stringa, valori di default per i parametri di funzioni, reference;
  • Standard input e standard output in C++ (cout, cin, cerr, controllo errori di interpretazione dell’input);
  • Input e output su file in C++ (fstream);

La programmazione ad oggetti:

  • Classi e oggetti: funzioni membro, metodi set, get e predicati, costruttori e distruttori standard, overloading e overriding di funzioni membro, overloading di funzioni, 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, template di classi.
  • Sovraccaricamento degli operatori: Sovraccaricamento degli operatori unari e binari, conversione di dati e operatori di conversione di tipi.

Cenni sulla complessità: notazioni asintotiche. Complessità di un problema computazionale, limite superiore, alcuni semplici casi di esempio sul calcolo del limite superiore del tempo di esecuzione.

Algoritmi di ordinamento che sfruttano il concetto di ricorsione:

  • Merge Sort
  • Quick Sort  
Implementazione di strutture dati dinamiche sfruttando la OOP in C++
  • Liste: Implementazione di un insieme mediante liste, liste ordinate e liste non ordinate; operazioni con le liste: inserimento, cancellazione e ricerca.
  • Pile e code: Implementazione di pile e code mediante OOP.
  • Alberi: Gli alberi, struttura di un albero binario, alberi binari di ricerca ed operazioni base: inserimento, ricerca e cancellazione, visite preorder, postorder e inorder.
  • 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 visita in profondità.


Esercitazioni: Risoluzione guidata di specifici problemi che hanno lo scopo di sfruttare i concetti e le tecniche discusse a lezione.


Testi di riferimento

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é.

Programmazione del corso

 ArgomentiRiferimenti testi
1Introduzione alla OOPTesto 1 e dispense
2Introduzione a C++Testo 1 e dispense
3Costrutti del linguaggio C++ (es. array, puntatori e riferimenti, allocazione dinamica della memoria)Testo 1
4Classi e oggettiTesto 1
5TemplateTesto 1
6Introduzione alla complessità computazionaleTesti 1-2
7Ordinamento e ricercaTesti 1-2
8RicorsioneTesto 1
9Classi derivateTesto 1
10Sovraccaricamento degli operatoriTesto 1
11ListeTesti 1-2
12Pile e CodeTesti 1-2
13AlberiTesti 1-2
14GrafiTesto 2 e dispense

Verifica dell'apprendimento

Modalità di verifica dell'apprendimento

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 a risposta multipla su tutto il programma didattico.
  • Seconda prova pratica: gli studenti che superano la prima prova potranno accedere alla prova di laboratorio. Durante la seconda prova, gli studenti riceveranno la descrizione di un problema da risolvere mediante l'implementazione di un codice in un tempo commisurato alla difficoltà della prova (tipicamente 2/3 ore).
  • Terza prova orale: dopo la scadenza della consegna della soluzione, gli studenti che consegnano una soluzione funzionante dovranno svolgere la prova orale. Durante la prova orale verranno posti dei quesiti riguardanti le scelte implementative effettuate durante la seconda prova, nonché dei quesiti sui contenuti del corso.

Esempi di domande e/o esercizi frequenti

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 ?