Università degli Studi di Napoli "Parthenope"

Scheda dell'insegnamento

Anno accademico: 
2017/2018
Tipologia di insegnamento: 
Caratterizzante
Tipo di attività: 
Obbligatorio
Corso di afferenza: 
Corso di Laurea triennale (DM 270) in INFORMATICA
Settore disciplinare: 
INFORMATICA (INF/01)
Lingua: 
Italiano
Crediti: 
12
Anno di corso: 
2
Docenti: 
Ciclo: 
Primo Semestre
Ore di attivita' frontale: 
96

Obiettivi

Il corso presenta una introduzione agli algoritmi, ed alle strutture dati basilari per un informatico. Fornisce le metodologie generali e gli strumenti per permettere la corretta progettazione di un algoritmo, e per stimarne la sua complessità computazionale. Il corso fornisce anche i concetti basilari di automi e di linguaggi. Il corso contiene un’ introduzione al linguaggio di C++, utilizzato per l’ implementazione software degli algoritmi nelle attività di Laboratorio che sono parte integrante del corso.

Conoscenza e capacità di comprensione: Lo studente deve dimostrare di conoscere e saper comprendere i fondamenti degli algoritmi e la struttura, con particolare riguardo alla loro complessità computazionale. Lo studente deve inoltre mostrare di conoscere il linguaggio di programmazione C++.

Capacità di applicare conoscenza e comprensione: Lo studente deve dimostrare di saper utilizzare la propria conoscenza acquisita per poter progettare implementare efficacemente gli algoritmi e le tecniche di programmazione studiati. Altresì, dovrà essere in grado di stimare correttamente la complessità computazionale, sia in spazio che in tempo degli algoritmi implementati.

Autonomia di giudizio: Lo studente deve essere in grado di sapere valutare in maniera autonoma le
prestazioni e l’ efficacia di un algoritmo.

Abilità comunicative: Le abilità comunicative dello studente saranno sviluppate nel modo seguente. Lo studente dovrà redigere una relazione di presentazione del progetto d’ esame. Altresì, dovrà essere in grado di illustrare efficacemente il lavoro svolto, in sede di esame orale.

Capacità di apprendimento: Lo studente deve essere in grado di aggiornarsi e approfondire in modo autonomo argomenti di algoritmi e strutture dati, anche accedendo ai testi disponibili nella biblioteca, o utilizzando altre modalità messe a disposizione dalla rete.

Prerequisiti

È necessario avere acquisito le conoscenze e le competenze trasmesse dai corsi di Matematica 1, Programmazione I e Laboratorio di Programmazione 1, Programmazione II e Laboratorio di Programmazione II.

Contenuti

Introduzione al Corso
- Definizione di Algoritmo.
- Complessità Computazionale di un algoritmo.
- Notazioni Asintotiche. Approssimazione di Stirling del Fattoriale
– Ricorrenze. Metodi per la risoluzione delle ricorrenze: Metodo iterativo, Metodo della Sostituzione, Metodo dell’esperto (Teorema Master).
- Algoritmi di Ordinamento Insertion Sort.
- Paradigma di Programmazione Divide et Impera. Esempi: Merge Sort, Quicksort, Randomized Quicksort
- Algoritmi di Ordinamento. Counting Sort, Radix Sort, Bucket Sort. Limite inferiore di complessità degli algoritmi di ordinamento basati su confronto.
- Paradigma di Programmazione Dinamica. Esempi: Parentesizzazione Ottima delle Matrici, Problema della Catena di Montaggio, Longest Common Sequence, Distanza di Editing (cenni). Problema dello Zaino 0-1.
- Paradigma di Programmazione Greedy. Esempi: Selezione delle attività, Shortest Job First, Problema dello Zaino Continuo, Codifica di Huffman
- Paradigma di Programmazione Backtracking. Problema delle 8 Regine.
-Paradigma di Programmazione Branch and Bound.
- Alberi Binari. Alberi Binari Completi. Heap. Heapsort. Coda di Priorità.
- Alberi Binari di Ricerca. Alberi RED Black.
- Grafi. Algoritmi di Visita dei Grafi. Minimum Spanning Tree. Algoritmi di Kruskal e di Prim. Problema dei Cammini Minimi su Grafi Orientati. Algoritmi di Dijkstra e di Bellmann-Ford.
- Hash Tables.
- Introduzione ad Automi e Linguaggi. Automi a Stati Finiti. Linguaggi. Grammatiche Regolari.
- Problemi P e NP. Problemi NP completi. Esempi di Problemi NP Completi
- Macchina di Turing.
Attività di Laboratorio
-Introduzione al linguaggio C++.
- Ereditarietà Multipla in C++. Paradosso del diamante e di Nixon.
- Polimorfismo.
- Standard Template Library (STL). Contenitori: Vector, List, Map. Iteratori, Algoritmi.
- I/O su file: Librerie Ifstream, Ofstream, Fstream.
- Classi e Funzioni Ifstream.
- Implementazione degli Algoritmi e delle Strutture Dati studiati in teoria.

Metodi didattici

Lezioni Frontali

Verifica dell'apprendimento

L’obiettivo della procedura di verifica consiste nel quantificare il livello di raggiungimento degli obiettivi formativi precedentemente indicati.
La procedura di verifica è indicata nella piattaforma di e-learning del Dipartimento di Scienze e Tecnologie. In sintesi, la procedura di verifica prevede una parte scritta ed una orale. La parte scritta prevede in uno svolgimento di una prova scritta in aula e di un progetto software di laboratorio, in C++, da svolgere a casa, riguardante lo svolgimento di una traccia, scelta tra cinque precedentemente assegnate. La parte orale, consiste per metà nella discussione del progetto d’esame per metà all'accertamento dell’acquisizione dei contenuti del corso. Ai fini della valutazione, la prova scritta, il progetto e la parte orale hanno pari rilevanza. Durante il corso è previsto lo svolgimento di due prove intercorso, il cui superamento comporta l’ esonero dallo svolgimento della parte scritta dell’esame.

Testi

T. Cormen, C. Leiserson, R. Rivest, C. Stein: “Introduzione agli algoritmi e strutture dati”, terza edizione, Mc Graw Hill, 2010.
B. Stroustrup: “C++ Linguaggio, libreria standard, principi di Programmazione”, Pearson, 2015.
Le slide di tutte le lezioni sono disponibili sulla piattaforma di e-learning.

Altre informazioni