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

Commissione d'esame

ARMANDO TACCHELLA (Presidente)

MARCO MARATEA

MASSIMO NARIZZANO

ENRICO GIUNCHIGLIA (Presidente Supplente)

LEZIONI

INIZIO LEZIONI

https://corsi.unige.it/8719/p/studenti-orario

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.

Calendario appelli