.

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.

Orario delle lezioni

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

Martedì 08:00 – 11:00 Aula 4

Giovedì 15:00 – 18:00 Aula 4

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

Prima Sessione

08 febbraio 2017
28 febbraio 2017

Sessione Riservata ai Fuori Corso

08 maggio 2017

Seconda Sessione

23 giugno 2017
11 luglio 2017

Terza Sessione

14 settembre 2017
28 settembre 2017

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.

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ì 14 marzo 2017

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.

Giovedì 16 marzo 2017

Funzioni in linea (inline), Ricorsione, variabili e modificatori di visibilità. Array, Inizializzazione di un array.

Martedì 21 marzo 2017

Array di caratteri e stringhe di testo, Array multidimensionali, Passaggio di vettori come parametri, Ordinamento di vettori, Ricerca nei vettori, natural merge di due array. Introduzione alla ricorsione e alle procedure ricorsive. Funzioni ricorsive, Confronto tra ricorsione e iterazione, Esempi di utilizzo della ricorsione.

Giovedì 23 marzo 2017

Ancora sulla ricorsione, esempi ed applicazioni, ricorsione lineare di coda e ricorsione doppia. Esercitazione 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;

Martedì 28 marzo 2017

Ordinamento per inserimento, Ordinamento per selezione, analisi degli algoritmi di ricerca,

Giovedì 30 marzo 2017

Algoritmi di ordinamento Ricorsivi, InsertionSort e SelectionSort ricorsivi, Algoritmo MergeSort, analisi degli algoritmi di ordinamento.

Martedì 4 aprile 2017

Partizionamento di un array, algoritmo ricorsivo QuickSort. Selezione dell'i-esimo elemento utilizzando una procedura ricorsiva.

Giovedì 6 aprile 2017

Classi e oggetti, Definizione di una classe, Costruttori, Distruttori. Implementazione di un contatore. Implementazione di un insieme un ArraySet dinamico.

Martedì 11 aprile 2017

Classi e oggetti, Costruttori, Distruttori, Overloading di funzioni membro. Costruttori statici, casi di studio.

Giovedì 20 aprile 2017

Classi e oggetti, Definizione di una classe, Costruttori, Distruttori. Costruttori Builder definiti internamente ad una classe, casi di studio.

Giovedì 27 aprile 2017

Implementazione di una lista utilizzando un array. Implementazione di un insieme attraverso l'uso di liste singolarmente linkate. Inserimento, cancellazione e ricerca.

Martedì 2 maggio 2017

Implementazione di liste doppiamente linkate, uso di sentinella nell'implementazione di una lista.

Giovedì 11 maggio 2017

Code e pile. Implementazione attraverso l'utilizzo di array e liste.