PROGRAMMING 2 & LABORATORY

Anno accademico 2019/2020 - 1° anno - Curriculum Information Technology

Docenti

PROGRAMMING 2: Docente non ancora assegnato
LABORATORY: Docente non ancora assegnato

Crediti: 9
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

PROGRAMMING 2
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 comprensione: comprendere e dimostrare l'implementazione di algoritmi e strutture di dati fondamentali. Comprendere la complessità temporale e spaziale degli algoritmi.
2. Applicazione di conoscenza e comprensione: utilizzare algoritmi fondamentali per l'ordinamento e la ricerca e comprenderne la complessità temporale. Trovare soluzioni algoritmiche ai problemi utilizzando tecniche di risoluzione dei problemi come la divisione e la conquista. Utilizzare strutture di dati chiave come elenchi collegati, pile, code, alberi e grafici.
3. Esprimere giudizi: lo studente sarà in grado di giudicare l'efficacia della sua attuazione e il lavoro del progetto. C
4. Capacità di apprendimento: lo studente sarà in grado di adattare le soluzioni analizzate durante le lezioni ad altri contesti.
LABORATORY
Il laboratorio sarà utilizzato per fornire agli studenti una forte preparazione in C ++, il linguaggio di programmazione OO utilizzato per implementare algoritmi e strutture di dati.

Come risultato del completamento di questo corso, gli studenti
1. Conoscenza e comprensione: comprenderanno le idee e i principi di base della programmazione orientata agli obiettivi. In particolare, gli studenti impareranno le caratteristiche principali di C ++.
2. Applicazione di conoscenza e comprensione: saranno in grado di utilizzare correttamente i concetti fondamentali della programmazione orientata agli oggetti, come classi, oggetti, polimorfismo, eredità.
3. Esprimere giudizi: saranno in grado di giudicare l'efficacia della loro attuazione e il lavoro del loro progetto.
4. Abilità comunicative: acquisiranno le capacità comunicative appropriate relative alla programmazione orientata agli oggetti e al linguaggio di programmazione C ++.
5. Capacità di apprendimento: saranno in grado di adattare le soluzioni analizzate durante le lezioni ad altri contest

Modalità di svolgimento dell'insegnamento

PROGRAMMING 2
L'insegnamento verrà svolto attraverso lezioni frontali (per un totale di 48 ore) durante le quali verranno presentati i contenuti del corso, anche attraverso dimostrazioni pratiche.
LABORATORY
L'insegnamento verrà svolto attraverso lezioni frontali (per un totale di 24 ore) durante le quali verranno presentati i contenuti del corso, anche attraverso dimostrazioni pratiche.

Prerequisiti richiesti

PROGRAMMING 2
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
LABORATORY
Lo studente che accede al corso di Laboratorio di Porgrammazione II dovrà conoscere i fondamenti della programmazione ad oggetti e del paradigma di programmazione imperativa.

Frequenza lezioni

PROGRAMMING 2
La frequenza delle lezioni non è obbligatoria ma è fortemente consigliata.
LABORATORY
La frequenza delle lezioni non è obbligatoria ma è fortemente consigliata.

Contenuti del corso

PROGRAMMING 2
Il Programma didatico è diviso nelle seguenti parti:

Parte 1 (2 CFU): 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 (4 CFU): 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.
LABORATORY
Il Programma didatico è diviso nelle seguenti parti:

Parte Introduttiva (0.5 CFU): Ripasso e approfondimento di concetti ntrodotti nel corso di Programmazione 1
- Array: inizializzazione di un array, array di caratteri e stringhe di testo, array multidimensionali, passaggio di vettori come parametri.
- 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++.
Parte 3 (2.5 CFU): 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.

Testi di riferimento

PROGRAMMING 2
Libro di testo.

Thomas H. Cormen. Charles E. Leiserson. Ronald L. Rivest. Clifford Stein. Introduction to Algorithms. Third Edition. The MIT Press
LABORATORY
Nessun testo di riferimento specifico.

Programmazione del corso

	Argomenti	Riferimenti testi
PROGRAMMING 2
1	Introduction to Algorithms. Iterative sorting algorithms.	Ch. 1-2
2	Recursive Algorithms. Mergesort. Analysis of Algorithms.	Ch. 2-4
3	Asymptotic growth of functions. Divide and Conquer and some examples of Algorithms.	Ch. 3-4
4	Quicksort and basic probabilities,	Ch. 5,7
5	Linked Lists. Elementary Data structures: Stacks, Queues.	Ch. 10.
6	Queues and Trees.	Ch. 10.
7	Graphs and some elementary algorithms on graphs.	Ch. 22
LABORATORY
	Argomenti	Riferimenti testi
1	Array: initialization of an array, array of characters and text strings, multidimensional arrays, vectors as parameters.
2	Pointers and references: References, pointers, null pointers, pointer to pointers, pointers and arrays, pointer arrays, string pointers, pointer arithmetic, constant pointers, pointers as function arguments, function pointers, pointers to structures.
3	Dynamic memory allocation: Dynamic memory management, new operator, delete operator, memory overflow management, C ++ memory types.
4	Classes and objects: member functions, set methods, get and predicates, standard constructors and destructors, overloading and overriding member functions, other constructors.
5	Derived classes: inheritance and polymorphism: Derived classes, inheritance types, destructors, multiple inheritance and composition, bindings, virtual functions, polymorphism, advantages of polymorphism.
6	Template: Genericity, C ++ template, function template, class templated.
7	Overloading of operators: Overloading of unary and binary operators, overloading of operators + and - and of the assignment operator, overloading of the insertion, extraction, new and delete operators, conversion of data and forced conversion of types.

Verifica dell'apprendimento

Modalità di verifica dell'apprendimento

PROGRAMMING 2
Students will work on a programming project in C++ and will discuss it (along with the underlying theoretical concepts) in a final oral exam.
LABORATORY
See information on final exam for Programming Module.

Corso di laurea in

Informatica