Salta al contenuto principale della pagina

PROGETTAZIONE E ANALISI DI ALGORITMI

CODICE 65896
ANNO ACCADEMICO 2022/2023
CFU
  • 9 cfu al 3° anno di 8719 INGEGNERIA INFORMATICA (L-8) - GENOVA
  • SETTORE SCIENTIFICO DISCIPLINARE ING-INF/05
    LINGUA Italiano
    SEDE
  • GENOVA
  • PERIODO 1° Semestre

    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, eventualmente erogate in modalità online.

    PROGRAMMA/CONTENUTO

    Progettazione ed analisi di algoritmi

    • Introduzione: definizione di algoritmo; aspetti fondamentali nella soluzione di problemi mediante algoritmi; tipologie di problemi e strategie di soluzione; specifica degli algoritmi mediante diagrammi di flusso e pseudocodifica; sintassi e semantica relative alle convenzioni di pseudocodifica.
       
    • Strutture dati fondamentali: strutture lineari (array, stringhe, pile, code e liste); grafi (definizioni fondamentali e strutture dati); alberi (definizioni fondamentali e strutture dati); insiemi, dizionari e mappe  (definizioni fondamentali).
       
    • Elementi di base: efficienza degli algoritmi, risorse computazionali e modello RAM; notazione asintotica (proprietà e classi fondamentali); tipologie di analisi di algoritmi (caso pessimo, ottimo e medio); limiti inferiori nell'analisi di algoritmi e ottimalità; efficienza ammortizzata.
       
    • Strategia "Forza Bruta": metodologia ed esempi di analisi di algoritmi non ricorsivi (ricerca del massimo, unicità degli elementi e moltiplicazione fra matrici). Algoritmi di ordinamento elementare su vettori (Selection Sort); ricerca sequenzale su vettori; insiemi, dizionari e mappe con array dinamici e liste linkate; ricerca all'interno di stringhe (string matching).
       
    • Strategia "Dividi e conquista": metodologia di analisi di algoritmi ricorsivi; teorema dell'esperto (Master Theorem). Algoritmi di ordinamento su vettori (Merge Sort e Quick Sort); limiti inferiori per gli algoritmi di ordinamento basati su confronti; alberi binari (definizione, calcolo dell'altezza, visite); analisi sintattica di linguaggi formali (definizione di linguaggio, grammatiche context-free, automi a pila); parsing ricorsivo top-down.
       
    • Strategia "Diminuisci e conquista": algoritmo di Euclide; algoritmi di ordinamento su vettori (Insertion Sort e Shell Sort); visita di grafi non diretti in profondità e in ampiezza; componenti connesse su grafi non diretti; visita in profondità e in ampiezza su grafi diretti; ordinamento topologico; componenti fortemente connesse; ricerca binaria nei vettori, potenze di interi e matrici; alberi binari di ricerca (BST - Binary Search Tree).
       
    • Strategia "Trasforma e conquista": struttura dati heap; utilizzo degli heap per l'ordinamento di vettori (Heap Sort); utilizzo degli heap per la gestione di code di priorità; confronto sperimentale fra ordinamenti asintoticamente ottimi; metodo di Horner per il calcolo di polinomi; insiemi disgiunti e problemi "Union-Find"; BST bilanciati: 2-3 alberi e alberi LLRB;  tries. 
       
    • Strategia "Compromesso spazio-tempo": ordinamento di vettori in tempo lineare (Counting Sort); tabelle ad indirizzamento diretto, tabelle hash (separate chaining); funzioni hash;
       
    • Strategia "Greedy" (golosa): algoritmi di Prim e Kruskal per il minimo albero ricoprente (MST - Minimum Spanning Tree), algoritmo di Dijkstra per la ricerca di cammini minimi; codici di Huffman per la compressione dei dati.

    Programmazione orientata agli oggetti (riferimenti al libro di testo Core Java I e II)

    • Introduzione e ripasso su oggetti e classi (Core Java I - Cap. 4) ed ereditarietà (Core Java  I - Cap. 5), libreria "legacy" per la lettura e la scrittura di file di testo
       
    • Interfacce, espressioni lambda e classi interne (Core Java I - Cap. 6); gestione delle stringhe, gestione della memoria, misurazione delle prestazioni.
       
    • Progettazione orientata agli oggetti: UML (class diagram, sequence diagram, state diagram);
       
    • Eccezioni e logging (Core Java I - Cap. 7), rilascio di applicazioni Java (Core Java I - Cap. 13)
       
    • Programmazione generica (Core Java I - Cap. 8), Java collection framework (Core Java I - Cap. 9)
       
    • Introduzione ai Design Pattern (creazionali, strutturali e comportamentali); definizione dei pattern (Factory Method, Iterator, Composite, Decorator, Interpreter, Visitor, Observer)
       
    • Utilizzo degli stream (Core Java II - Cap. 1) e gestione I/O (Core Java II - Cap. 2)

    TESTI/BIBLIOGRAFIA

    T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein ‐ Introduzione agli algoritmi e strutture dati ‐ 3a Edizione ‐ McGraw ‐ Hill;

    R. Sedgewick ‐ Algorithms ‐ 4th edition ‐  Addison Wesley

    A. Levitin ‐ Introduction to The Design and Analysis of Algorithms ‐ 2nd edition ‐ Addison ‐ Wesley;

    S. Skiena ‐ The Algorithm Design Manual ‐ 2nd edition – Springer;

    Cay Horstmann - Core Java (Vol. 1 e 2) - Prentice Hall

    DOCENTI E COMMISSIONI

    LEZIONI

    Orari delle lezioni

    L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.

    ESAMI

    MODALITA' D'ESAME

    Progetto durante il corso (1 progetti, massimo 10 punti), Prova orale (massimo 20 punti).

    Qualora le lezioni si svolgessero online, il progetto viene comunque assegnato e  l'esame orale viene svolto in modalità telematica.

    MODALITA' DI ACCERTAMENTO

    Capacità di impostare la soluzione a problemi computazionali per via algoritmica implementando la soluzione con il linguaggio di programmazione Java;
    capacità di analizzarne la correttezza e la complessità delle soluzioni trovate per via analitica.Capacità di impostare la soluzione a problemi computazionali per via algoritmica e, analizzarne la correttezza e la complessità per via analitica.