PROGETTAZIONE E ANALISI DI ALGORITMI

PROGETTAZIONE E ANALISI DI ALGORITMI

_
iten
Codice
65896
ANNO ACCADEMICO
2020/2021
CFU
9 cfu al 3° anno di 8719 INGEGNERIA INFORMATICA (L-8) GENOVA
SETTORE SCIENTIFICO DISCIPLINARE
ING-INF/05
LINGUA
Italiano
SEDE
GENOVA (INGEGNERIA INFORMATICA )
periodo
1° Semestre
materiale didattico

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.

Modalità 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

Ricevimento: Su appuntamento a richiesta degli studenti.

Commissione d'esame

ARMANDO TACCHELLA (Presidente)

MASSIMO NARIZZANO

MARCO MARATEA

ENRICO GIUNCHIGLIA

LEZIONI

Modalità didattiche

Lezioni frontali ed esercitazioni, eventualmente erogate in modalità online.

INIZIO LEZIONI

21 Settembre 2020

ORARI

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

Vedi anche:

PROGETTAZIONE E ANALISI DI ALGORITMI

ESAMI

Modalità 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).

Qualora le lezioni si svolgessero online, i progetti vengono comunque assegnati; la prova pratica e l'esame orale vengono svolti in modalità telematica.

Modalità 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.