PRESENTAZIONE

Il corso si propone di introdurre lo studente alla progettazione e all'analisi degli algoritmi. Mediante la presentazione delle principali strutture dati e degli algoritmi ad essi relative lo studente maturerà la comprensione del funzionamento degli algoritmi e delle principali tecniche ad essi collegate.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Il corso introduce le principali strategie di progettazione di algoritmi e gli strumenti per valutarne la correttezza e le prestazioni. L'obiettivo è lo sviluppo della capacità di formalizzare e risolvere problemi per via algoritmica, e della capacità di analisi e valutazione delle soluzioni.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

Il corso introduce le principali strategie di progettazione di algoritmi:

• Forza Bruta: soluzione del problema a partire dalla sua definizione formale
• Dividi e Conquista: approccio che prevede il frazionamento in sottoproblemi (solitamente di eguale diimensione) e la ricombinazione delle soluzionie parziali
• Diminuisci e Conquista: soluzione del problema mediante riduzione iterativa delle dimensioni (di una costante, di un fattore costante o di un fattore variabile)
• Trasforma e Conquista: approccio che prevede la riformulazione del problema in modo da semplificarne la soluzione
• Compremesso Spazio-Tempo: incremento delle prestazioni per lo svolgimento di operazioni mediante utilizzo di overhead in termini di memoria
• Algoritmi Golosi: strumenti di ottimizzazione combinatoria che prevedono l'utilizzo di strategia "greedy" (scelte localmente ottime si rivelano anche globalmente tali)

Complessivamente, l'obiettivo è quello di realizzare una buona conoscenza dei principali algoritmi facenti parte di ogni famiglia, avente come risultato la capacità di impostare la soluzione a problemi computazionali per via algoritmica e analizzarne la correttezza e la complessità per via analitica o empirica.

PREREQUISITI

E' richiesta una buona conoscenza di almeno un linguaggio di programmazione, preferibilmente della famiglia C/C++/Java.

Conoscenze preliminari di calcolo combinatorico, algebra e informatica teorica sono utili per una migliore comprensione del materiale del corso.

MODALITA' DIDATTICHE

Lezioni frontali ed esercitazioni.

PROGRAMMA/CONTENUTO

Modelli per la valutazione degli algoritmi. Strumenti analitici. Strategie per la soluzione di problemi: “Forza Bruta”, “Dividi e Conquista”, “Diminuisci e Conquista”, “Trasforma e Conquista”, “Compromesso spazio ‐ tempo”, “Strategia golosa”. Studio e analisi di algoritmi e strutture dati: ordinamento e ricerca, strutture sequenziali, alberi e heap, tabelle hash, analisi di stringhe e testi. Progettazione e programmazione object-oriented in Java.

TESTI/BIBLIOGRAFIA

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein ‐ Introduzione agli algoritmi e strutture dati ‐ 3a Edizione ‐ McGraw ‐ Hill; A. Levitin ‐ Introduction to The Design and Analysis of Algorithms ‐ 2nd edition ‐ Addison ‐ Wesley; S. Skiena ‐ The Algorithm Design Manual ‐ 2nd edition – Springer; R. Sedgewick ‐ Algorithms in C++ ‐ 3rd edition ‐ Vol 1 ‐ 5 ‐ Addison Wesley

DOCENTI E COMMISSIONI

Commissione d'esame

ARMANDO TACCHELLA (Presidente)

GIUSEPPE CICALA

ENRICO GIUNCHIGLIA

MARCO MARATEA

MASSIMO NARIZZANO

LEZIONI

INIZIO LEZIONI

Settembre 2018

Orari delle lezioni

PROGETTAZIONE E ANALISI DI ALGORITMI

ESAMI

MODALITA' D'ESAME

Progetti durante il corso (2 progetti, massimo 3 punti ciascuno), Prova pratica a calcolatore (massimo 12 punti)  ed esame orale (massimo 12 punti)

MODALITA' DI ACCERTAMENTO

Capacità di impostare la soluzione a problemi computazionali per via algoritmica e, analizzarne la correttezza e la complessità per via analitica.

Calendario appelli