CODICE 65896 ANNO ACCADEMICO 2019/2020 CFU 9 cfu anno 3 INGEGNERIA INFORMATICA 8719 (L-8) - GENOVA SETTORE SCIENTIFICO DISCIPLINARE ING-INF/05 LINGUA Italiano SEDE GENOVA PERIODO 1° Semestre MATERIALE DIDATTICO AULAWEB 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 ARMANDO TACCHELLA Ricevimento: Ogni ora seguente alle ore di lezione oppure su appuntamento. Commissione d'esame ARMANDO TACCHELLA (Presidente) 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 Data appello Orario Luogo Tipologia Note 08/01/2020 10:00 GENOVA Prova pratica 04/02/2020 10:00 GENOVA Prova pratica 15/06/2020 10:00 GENOVA Prova pratica 07/07/2020 10:00 GENOVA Prova pratica 04/09/2020 10:00 GENOVA Prova pratica