| | | corso | | | | |
Algoritmica A
Codice: | AA006 | Crediti: | 9 | Semestre: | 1 | Sigla: | ALG | |
|
Settore disciplinare: | INF/01 - Informatica |
Docente
Paolo Ferragina
Tel. 0502212764Prerequisiti
L’aver seguito i corsi di “Laboratorio di Introduzione alla Programmazione”, “Fondamenti di programmazione”, “Metodologie di Programmazione” e “Linguaggi e metodi della matematica”.
Obiettivi di apprendimento
Definire formalmente la nozione di algoritmo e di modello di calcolo.
Caratterizzare i dati da elaborare, organizzandoli e strutturandoli
nel modo più opportuno al fine di agevolarne l'uso da parte degli
algoritmi. Progettare algoritmi corretti (che risolvono cioè
sempre e solo il problema a cui si è interessati) ed efficienti
(cioè che lo risolvono il più velocemente possibile o
usano il minor spazio di memoria possibile), attraverso l'esame di
diversi paradigmi. Studiare le limitazioni inerenti dei problemi da
risolvere, in particolare di quelli la cui soluzione richiede l'esame di
tutte le possibilità.
Conoscenze. Cosa è un algoritmo e cosa è un modello di calcolo. Saper caratterizzare i dati da elaborare strutturandoli nel modo più opportuno al fine da agevolarne l’uso da parte degli algoritmi. Conoscere le strutture dati e le tecniche fondamentali per il progetto di algoritmi elementari. Conoscere le tecniche di valutazione della complessità di un algoritmo e le limitazioni inerenti dei problemi da risolvere. Conoscere le classi di complessità P, NP, NPC, e le limitazioni del calcolo (indecidibilità).
Capacità. Saper progettare algoritmi corretti (che risolvono cioè sempre e solo il problema a cui si è interessati) ed efficienti (cioè che lo risolvono il più velocemente possibile o usano il minor spazio di memoria possibile), attraverso l’uso di strutture dati e tecniche algoritmiche elementari. Saper valutare la complessità di un algoritmo in tempo e spazio, al caso pessimo e al caso medio. Saper valutare le limitazioni inerenti del calcolo.
Comportamenti. Lo studente saprà essere in grado di valutare la bontà (leggi efficienza in tempo e spazio) di un software sulla base delle sue caratteristiche progettuali salienti, prescindendo dunque dalla macchina, dal Linguaggio di sviluppo o dal Sistema Operativo sul quale il software gira. Allo stesso modo, lo studente saprà essere in grado di effettuare scelte progettuali ragionevoli nella realizzazione di un software, valutando le loro implicazioni sulla prestazioni dello stesso, prima di arrivare alla fase di programmazione, debugging e profiling, mediante l’uso di modelli matematici opportuni. Ciò risulta cruciale per ridurre i tempi e i costi dello sviluppo del software.
Descrizione
Introduzione ai modelli di calcolo, all'analisi e alla
complessità degli algoritmi. Algoritmi ricorsivi e relazioni di
ricorrenza. Algoritmi di ordinamento. Strutture dati elementari e
avanzate. Algoritmi su grafi e stringhe. Enumerazione e non
determinismo. Problemi P, NP, RP, e NP-completi.
English Description
Introduction to the design, analysis and computation complexity of
algorithms and data structures. Basic techniques for the analysis of
algorithms. Design paradigms for efficient algorithms. Definition and
application of main and advanced data structures. Algorithms on graphs
and strings. Complexity of computationally hard problems.
Indicazioni metodologiche
Per conseguire gli obiettivi indicati, sarà necessario:
- organizzare il processo di apprendimento in moduli flessibili, posti in sequenza logica, e di difficoltà crescente;
- partire dal problem solving per arrivare alla proposta di soluzioni algoritmiche efficienti;
- presentare in modo approfondito ogni specifica struttura dati o tecnica algoritmica, confrontandola con quelle elementari viste nei corsi di Laboratorio, così da apprezzare le loro potenzialità;
- partire dalla descrizione di problemi reali per arrivare allo studio della loro complessità inerente, dimostrando così i limiti del calcolo;
Programma
- Analisi di Algoritmi e Complessità
- Introduzione alla complessità di calcolo
- Ordini di grandezza delle funzioni
- Algoritmi ricorsivi e Tecnica divide&conquer
- Esempi su: Numeri di Fibonacci, Calcolo del massimo e minimo, Ricerca Binaria, Mergesort, Moltiplicazione rapida di interi.
- Relazioni di ricorrenza e Teorema Principale
- Limiti inferiori alla complessità
- Progetto di Algoritmi e Strutture Dati
- Code, Pile, Liste e Alberi
- Heap e Heapsort
- Quicksort deterministico e randomizzato
- Ordinamento in tempo lineare: Counting sort, Radix sort, Bucket sort
- Tabelle hash: Liste di concatenazione, Indirizzamento aperto, Hashing Perfetto
- Alberi binari di ricerca
- Alberi delta-bilanciati e AVL: definizione e operazioni di rotazione
- Grafi: rappresentazione, visita DFS e BFS, topological sort
- Classi di Complessità
- Enumerazione e non determinismo: combinazioni e permutazioni
- Classi P, NP, NPC, NP-hard
- Modelli di Calcolo e Calcolabilità
- Indecidibilità e universalità
- Macchina di Turing
Ore lezione: | 36 | Ore esercitazione: | 36 | | | |
Bibliografia
Il corso farà riferimento a due libri di testo, più una serie di appunti disponibili sul sito del corso:
- T. Cormen, C. Leiserson, R. Rivest, "Introduzione agli algoritmi e strutture dati", McGraw-Hill Italia, 2005.
- F. Luccio, La Struttura degli Algoritmi, Boringhieri, 1984.
Modalità di esame
L’esame di Algoritmica consiste di una prova scritta e di una prova orale. Durante la prova scritta gli studenti non possono consultare i propri libri e appunti. L'esame scritto dunque consiste di esercizi e domande teoriche. Durante il corso vengono svolte due verifiche intermedie (compitini). Gli studenti che superano entrambe le verifiche, con una votazione superiore al 18, possono sostenere la prova orale in uno dei due appelli della sessione invernale (Gennaio o Febbraio). Chi avesse riportato la sufficienza in un compitino soltanto potrà recuperare la parte insufficiente in uno degli appelli della sessione invernale. In questi appelli la prova scritta sarà composta da due parti così da consentire il recupero suddetto. Il recupero può essere anche tentato da chi desidera migliorare il voto riportato in un compitino.