.

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ì 3 marzo 2020. 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

08 aprile 2020

Seconda Sessione

02 luglio 2020
20 luglio 2020

Terza Sessione

01 settembre 2019
18 settembre 2019

Appunti

Qui sono inseriti gli appunti delle lezioni.

Codici Lezione 3 marzo 2020


Competizione

Il Coding Contest di Programmazione 2, anno accademico 2019/20 partirà il 20 Marzo 2020 e si protrarrà per 10 settimane. Ogni venerdì (alle ore 22:00) saranno pubblicate due prove di programmazione valevoli per la competizione. Le soluzioni alle prove dovranno essere sottomesse entro le ore 22 della domenica successiva. Sarà obbligatorio fare l'upload del codice sorgente realizzato per la generazione dell'output oltre che al file di output stesso. La classifica finale, ottenuta alla fine delle 10 settimane di competizione, sarà unica, valevole per tutti gli studenti di Programmazione 2 dei corsi A-L ed M-Z.
I primi 20 classificati non saranno obbligati a sostenere la prima prova d'esame (prova scritta di laboratorio), ma solo il colloquio orale. Agli studenti classificati nelle prime 10 posizioni, sarà riconosciuta una votazione iniziale (equivalente al voto assegnato in occasione delle prova di laboratorio) di 30/30. A coloro che si saranno classificati tra l'undicesimo e il ventesimo posto sarà riconosciuta una votazione iniziale di 25/30.
Gli studenti ai quali viene assegnato tale bonus potranno comunque scegliere di sostenere la prova scritta di laboratorio. In questo caso il voto ottenuto come bonus del coding contest sarà annullato. Tuttavia se lo studente si presenta alla prova scritta di laboratorio ma non consegna l'elaborato, il voto ottenuto nella competizione sarà ancora valido.
Sarà reso obbligatorio caricare il codice sorgente corrispondente allo output ottenuto per la risoluzione del problema. Sarà possibile caricare un singolo file sorgente in linguaggio C++ con estensione .cpp che includa tutte le costanti e le variabili usate nel programma.





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ì 03 marzo 2020

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]

Martedì 10 marzo 2020 (Online)

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;

Giovedì 12 marzo 2020 (Online)

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.

Martedì 17 marzo 2020 (Online)

Algoritmo ricorsivo per la risoluzione del gioco delle torri di Hanoi. Altri algoritmi ricorsivi. Algoritmi di ordinamento Ricorsivi. Algoritmo MergeSort.