PROGRAMMAZIONE II A - L

INF/01 - 9 CFU - 2° semestre

Docente titolare dell'insegnamento

DARIO CATALANO


Obiettivi formativi

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.

 

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

Prerequisiti richiesti

Programmazione I



Frequenza lezioni

Fortemente Consigliata



Contenuti del corso

Il Programma Diddatico è diviso nelle seguenti tre parti: fondamenti di programmazione C++, Elementi di programmazione ad oggetti, Strutture Dati.

 

PARTE I
Elementi di programmazione C++

Funzioni

Concetto di funzione, Stuttura di una funzione, Prototipi delle funzioni, Passaggio di parametri a una funzione, Argomenti di default, Funzioni in linea (inline), Visibilità, Classi di immagazzinamento, Visibilità di una funzione, Concetto e uso di funzioni di libreria, Sovraccaricamento delle funzioni, Ricorsione, Template di funzioni.

 

Array

Array, Inizializzazione di un array, Array di caratteri e stringhe di testo, Array multidimensionali, Passaggio di vettori come parametri, Ordinamento di vettori, Ricerca nei vettori,

Strutture e unioni

Strutture, Accesso ai campi delle strutture, Strutture annidate, Array di strutture, Utilizzare le strutture come parametri, Funzioni membri di strutture, Unioni, Enumerazioni, typedef.

Puntatori e riferimenti

Riferimenti, Puntatori, Puntatori null, Puntatore a puntatore, Puntatori e array, Array di puntatori, Puntatori a stringhe, Aritmetica dei puntatori, Puntatori costanti e puntatori a costanti, Puntatori come argomenti di funzioni, Puntatori a funzioni, Puntatori a strutture.

Allocazione dinamica della memoria

Gestione dinamica della memoria, L’operatore new, L’operatore delete, Gestione dell’overflow di memoria, Tipi di memoria in C++.

Stringhe

Concetto di stringa, Lettura di stringhe, Array e stringhe come parametri di funzioni, La libreria cstring, Conversione di stringhe in numeri.

Ordinamento e ricerca

Algoritmi di ordinamento elementari, Ordinamento per scambio, Ordinamento per selezione, Ordinamento per inserimento, Ordinamento a bolle, Ordinamento shell, Ricerca sequenziale e binaria nei vettori, Analisi degli algoritmi di ricerca.

Ricorsione

Funzioni ricorsive, Confronto tra ricorsione e iterazione, Esempi di utilizzo della ricorsione, Quicksort.

Flussi e file: libreria standard di I/O

Flussi (stream), La libreria di classi per l’I/O, La classe istream, La classe ostream, Formattazione dell’output, Indicatori di formato, I/O da file, I/O binario, Accesso diretto.

 

PARTE II
Programmazione orientatata agli oggetti

Classi e oggetti

Classi e oggetti, Definizione di una classe, Costruttori, Distruttori, Overloading di funzioni membro. Errori frequenti di programmazione.

Classi derivate: ereditarietà e polimorfismo

Classi derivate, Tipi di ereditarietà, Distruttori, Ereditarietà multipla, Binding, Funzioni virtuali, Polimorfismo, Vantaggi del polimorfismo.

Template

Genericità, Template in C++, Template di funzioni, Template di classi, Modelli di compilazione di template, Template e polimorfismo.

Sovraccaricamento degli operatori

Sovraccaricamento 585 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.

 

 

 

PARTE III
Strutture dati

Liste

Le liste, Operazioni con le liste, Lista doppiamente concatenata, Liste circolari.

Pile e code

Concetto e gestione di una pila, Concetto e gestione di una coda.

Alberi

Gli alberi, Alberi binari, Struttura di un albero binario, Alberi di espressione, Visita di un albero, Albero binario di ricerca.



Testi di riferimento

Le risorse principali messe a disposizione dello studente sono le lezioni frontali, la cui frequenza è fortemente consigliata.

Per seguire meglio le lezioni, vengono messe a disposizione le slides utilizzate per il corso. Le slides non costituiscono un mezzo di studio: forniscono un dettaglio puntuale sugli argomenti trattati a lezione.

 

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.

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


Altro materiale didattico

http://www.dmi.unict.it/catalano/programmazione-ii/



Programmazione del corso

 *ArgomentiRiferimenti testi
1*Funzioni. Arrays. Passaggio di array per riferimento. Esercizi su array: Segmenti di somma massima. Array di caratteri: stringhe. Strutture e Unioni. Puntatori. Puntatori e Array. Puntatori a Funzioni. Gestione dinamica della memoria. Operatori New e Delete. Fondamenti di Programmazione in C++ 
2*Ricorsione. Ricorsione vs Iterazione. Prodotto di interi. Sequenza di Fibonacci. Massimo Comune Divisore: versione ricorsiva e versione iterativa. Torri di Hanoi: soluzione ricorsiva.  
3*Complessità di problemi computazionali. Tempo e Spazio. Tempo polinomiale e tempo esponenziale. Sommatorie notevoli. Intrattabilità di problemi computazionali.  
4*Algoritmi di ordinamento elementari: Ordinamento per scambio, per inserimento, a bolle. Lower bounds per gli algoritmi di ordinamento basati su confronti. Paradigma Divide et Impera. Merge Sort: Implementazione e Analisi. Quicksort. Idee e Implementazione. Analisi del caso migliore e analisi del caso peggiore. Ricerca sequenziale. Ricerca binaria. Complessità della ricerca binaria. 
5*Classi e oggetti. Attributi e metodi. Costruttori e distruttori. Calssi su più files Classi derivate, Tipi di ereditarietà, Distruttori, Ereditarietà multipla, Binding, Funzioni virtuali, Polimorfismo, Vantaggi del polimorfismo. Binding Statico e binding dinamico. Funzioni virtuali. Templates di classi e templates di funzioni 
6*Liste Concatenate. Inserimento, inserimento in testa, inserimento in coda. Ricerca. Rimozione di un elemento. Liste doppiamente concatenate. Inserimento e Cancellazione. Liste circolari. Pile. Implementare Pile con Array. Implementazione con puntatori. 
7*Code. Code implementate con array circolari.  
8*Alberi. Profondità e altezza di un albero. Alberi equilibrati. Visita di Alberi: cenni a visita in ampiezza e profondità. Visita Preorder, Inorder e Postorder. Complessità delle procedure Inorder, Preorder e Postorder. Inserimento, Ricerca, Massimo e Minimo. Cancellazione Implementazione della procedura di Cancellazione. Procedure Trapianta. Successore. Versioni iterative delle procedure inorder, preorder e postorder. 
9*Sovraccaricamento degli operatori 
* Conoscenze minime irrinunciabili per il superamento dell'esame.

N.B. La conoscenza degli argomenti contrassegnati con l'asterisco è condizione necessaria ma non sufficiente per il superamento dell'esame. Rispondere in maniera sufficiente o anche più che sufficiente alle domande su tali argomenti non assicura, pertanto, il superamento dell'esame.


Verifica dell'apprendimento


MODALITÀ DI VERIFICA DELL'APPRENDIMENTO

L'esame consiste di una prova di laboratorio e di una prova orale


PROVE IN ITINERE

Non ci sono prove in itinere


PROVE DI FINE CORSO

Non ci sono prove di fine corso


ESEMPI DI DOMANDE E/O ESERCIZI FREQUENTI

Si consulti la pagina web del docente




Apri in formato Pdf English version