.

Programmazione 2

Corso di Laurea Triennale in Informatica
Dipartimento di Matematica e Informatica



Presentazione

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. In connessione alle strutture dati saranno dati i concetti di base relativi alla complessità computazionale.
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.

Link al Contest Management System

Orario delle lezioni

Le lezioni del corso di Programmazione 2 avranno inizio martedì 8 marzo 2016. Gli appuntamenti settimanali seguiranno il seguente calendario

Martedì 10:00 – 13:00 Aula 3

Giovedì 10:00 – 13:00 Aula 3

Modalità d'esame

Le modalità d'esame verranno definite nel corso della prima lezione e verranno in seguito inserite all'interno di questa sezione.

Calendario d'esami

Sessione Riservata ai Fuori Corso

05 aprile 2019

Seconda Sessione

24 giugno 2019
16 luglio 2019

Terza Sessione

02 settembre 2019
17 settembre 2019

Sessione Riservata ai Fuori Corso

5 novembre 2019

Esercizi

All'interno del Contest Management System è possibile trovare svariati esercizi sugli argomenti trattati a lezione. Il sistema permette l'autovalutazione della prova.



Competizione

La competizione di programmazione si svolge nel corso del periodo didattico relativo al secondo semestre
Ulteriori informazioni possono essere reperite in questa pagina





Programma del corso

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,

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.

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

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.

Grafi

Definizione di Grafo, Inserimento di un nodo, inserimento di un arco, Rappresentazione con matrici di adiacenza e con liste di adiacenza, Visita in ampiezza e visita in profondità, Aciclicità di un Grafo, Ordinamento Topologico, Componenti connesse e componenti fortemente connesse.

Libro di testo

Fondamenti di programmazione in C++
Autore: Luis Joyanes Aguilar
Casa editrice: McGraw-Hill
Anno: 2007


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++
Autore: Scott Meyers
Casa editrice: Addison-Wesley
Anno: 2005

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 della piattaforma Java ed esempi di codice esaurienti. La descrizione articolata di ogni tema rende chiaro cosa fare, cosa non fare e perché.

More Effective C++
Autore: Scott Meyers
Casa editrice: Addison-Wesley
Anno: 1996

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 della piattaforma Java ed esempi di codice esaurienti. La descrizione articolata di ogni tema rende chiaro cosa fare, cosa non fare e perché.



Ultimi Avvisi



Diario delle Lezioni

Martedì 05 marzo 2019

Prima Lezione. Presentazione del corso e delle modalità d'esame. Lezione di verifica delle competenze di programmazione, prototipi delle funzioni, Passaggio di parametri a una funzione, Argomenti di default, visibilità di una funzione, Concetto e uso di funzioni di libreria, Sovraccaricamento delle funzioni, Template di funzioni.
[Codici svolti a lezione]

Giovedì 07 marzo 2019

Funzioni in linea (inline), Ricorsione, variabili e modificatori di visibilità. Array, Inizializzazione di un array. Inizializzazione lineare e inizializzazione logaritmica. Array di caratteri e stringhe di testo, Array multidimensionali, Passaggio di vettori come parametri, Ricerca nei vettori, natural merge di due array. Riferimenti, Puntatori, Puntatori null, Puntatore a puntatore, Puntatori e array, Array di puntatori, Puntatori a stringhe, Aritmetica dei puntatori, Puntatori a funzioni, Array di funzioni;
[Codici svolti a lezione]

Martedì 12 marzo 2019

Elementi di Complessità, confronto tra le classi di funzioni, esempi ed applicazioni. Ordinamento per inserimento, Ordinamento per selezione, analisi degli algoritmi di ricerca. Introduzione alla ricorsione e alle procedure ricorsive. Funzioni ricorsive, Confronto tra ricorsione e iterazione, Esempi di utilizzo della ricorsione, InsertionSort e SelectionSort ricorsivi, Ricorsione lineare di coda e ricorsione doppia. La risoluzione del Problema di Fibonacci.
[Codici svolti a lezione]

Giovedì 14 marzo 2019

Algoritmo ricorsivo per la risoluzione del gioco delle torri di Hanoi. Altri algoritmi ricorsivi. Algoritmi di ordinamento Ricorsivi. Algoritmo MergeSort.
[Codici svolti a lezione]

Giovedì 21 marzo 2019

Analisi dell'algoritmo MergeSort, partizionamento di un array, algoritmo ricorsivo QuickSort. Selezione dell'i-esimo elemento utilizzando una procedura ricorsiva. Algoritmo per il calcolo delle permutazioni di un array.
[Codici svolti a lezione]

Martedì 26 marzo 2019

Classi e oggetti, Definizione di una classe, Costruttori, Distruttori, Overloading di funzioni membro. Implementazione di un insieme attraverso un ArraySet dinamico. Itratore degli elementi di un insieme.
[Codici svolti a lezione]

Giovedì 28 marzo 2019

Classi e oggetti, Definizione di una classe, Costruttori, Distruttori. Costruttori statici, casi di studio.
[Codici svolti a lezione]

Martedì 2 aprile 2019

Costruttori Builder definiti internamente ad una classe. Implementazione di una lista utilizzando un array. Inserimento, cancellazione e ricerca.
[Codici svolti a lezione]

Giovedì 4 aprile 2019

Implementazione di liste singolarmente linkeate e doppiamente linkate attraverso l'uso dei puntatori. Interatore della lista uso di una sentinella nell'implementazione di una lista.
[Codici svolti a lezione]

Martedì 9 aprile 2019

Implementazione di liste singolarmente linkeate e doppiamente linkate attraverso l'uso di una sentinella nell'implementazione.
[Codici svolti a lezione]

Giovedì 11 aprile 2019

Risoluzione di un esercizio d'esame: somma e moltiplicazione di polinomi. Liste circolari e loro implementazione
[Codici svolti a lezione]

Martedì 30 aprile 2019

Code e pile. Implementazione attraverso l'utilizzo di array e liste. Implementazione di una coda attraverso l'utilizzo di due pile.
[Codici svolti a lezione]

Giovedì 2 maggio 2019

Introduzione alla struttura dati albero, caratteristiche e proprietà. Alberi posizionali. Alberi Binari e Alberi Binari di Ricerca: operazioni di inserimento, ricerca e cancellazione, minimo, massimo, successore e predecessore. Visite inorder, preorder e postorder.

Martedì 7 maggio 2019

Implementazione di un Albero Binario di Ricerca. Implementazione delle visite di un BST, procedura per il minimo, il massimo, il successore e il predecessore. Procedure iterative e ricorsive per la gestione degli Alberi. Iteratore di un BST.
[Codici svolti a lezione]

Martedì 14 maggio 2019

Implementazione dell'operazione di cancellazione di un albero binario di ricerca. Calcolo della profondità di un nodo, calcolod ell'altezza dell'albero, calcolo del peso di un nodo, calcolo del rango di un nodo. Altre operazioni importanti con gli Alberi Binari di Ricerca.
[Codici svolti a lezione]

Giovedì 16 maggio 2019

Esercitazione con gli alberi binari di ricerca: risoluzione di alcuni esercizi da svolgere all'esame. Natural Fill in un albero binario di ricerca.
[Codici svolti a lezione]

Martedì 21 maggio 2019

Introduzione alla struttura dati Grafo, caratteristiche e proprietà: nodi e vertici, direzionalità di un grafo, cammini e cammini semplici, cicli, connessione, aciclicità. Componenti connesse e componenti fortemente connesse.
[Codici svolti a lezione]

Giovedì 23 maggio 2019

Visita di un grafo. Visita BFS e sue proprietà: albero BFS, cammini minimi, colorazione dei nodi. Implementazione della visita BFS, stampa del cammino minimo. Introduzione alla visita DFS
[Codici svolti a lezione]

Martedì 28 maggio 2019

Visita DFS e proprietà. Implementazione della visita DFS e del test di aciclicità. Stampa del cammino BFS. Ordinamento Topologico di un grafo e sua implementazione.

Giovedì 30 maggio 2019

Algoritmo per il calcolo delle componenti fortemente connesse di un grafo e sua implementazione.

Martedì 4 Giugno 2019

Eserciztazione in aula su esercizi d'esame.

Giovedì 6 Giugno 2019

Eserciztazione in aula su esercizi d'esame.