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 |
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, 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.
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).
Qualora le lezioni si svolgessero online, i progetti vengono comunque assegnati; la prova pratica e l'esame orale vengono svolti 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.