.

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 4

Giovedì 10:00 – 13: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

Sessione Riservata ai Fuori Corso

09 aprile 2018

Seconda Sessione

21 giugno 2018
05 luglio 2018

Terza Sessione

06 settembre 2018
27 settembre 2018

Sessione Riservata ai Fuori Corso

21 novembre 2018

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ì 13 marzo 2018

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ì 15 marzo 2018

Funzioni in linea (inline), Ricorsione, variabili e modificatori di visibilità. 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, 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 costanti e puntatori a costanti, Puntatori come argomenti di funzioni, Puntatori a funzioni;

Martedì 20 marzo 2018

Introduzione alla ricorsione e alle procedure ricorsive. Funzioni ricorsive, Confronto tra ricorsione e iterazione, Esempi di utilizzo della ricorsione, Ricorsione lineare di coda e ricorsione doppia. Esercitazione

Giovedì 22 marzo 2018

Anagramma di una stringa attraverso la ricorsione. Elementi di Complessità, confronto tra le classi di funzioni, esempi ed applicazioni. La risoluzione del Problema di Fibonacci, Natural Merge di due array.

Martedì 27 marzo 2018

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

Giovedì 29 marzo 2018

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

Giovedì 5 aprile 2018

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

Martedì 10 aprile 2018

Classi e oggetti, Definizione di una classe, Costruttori, Distruttori, Overloading di funzioni membro. Implementazione di un insieme un ArraySet dinamico. Costruttori statici, casi di studio.

Giovedì 12 aprile 2018

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

Martedì 17 aprile 2018

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

Giovedì 19 aprile 2018

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