| | | corso | | | |
Algoritmi e Strutture Dati I + Laboratorio di Informatica II B
(Corso di Laurea in Informatica (quinquennale))
Codice: | 4I054 | Crediti: | 18 | Semestre: | 2 | Sigla: | AS1 | |
Docente
Linda Pagli
Tel. 0502212735Prerequisiti
Obiettivi di apprendimento
- Definire formalmente la nozione di algoritmo.
- 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à.
Descrizione
Introduzione all'analisi e alla complessità degli algoritmi. Algoritmi
ricorsivi e relazioni di ricorrenza. Algoritmi di ordinamento. Algoritmi
greedy. Strutture dati elementari e avanzate.
Enumerazione e non determinismo. Problemi NP-completi
English Description
Introduction to algorithm analysis and design. Recursive algorithms and
recurrence relations. Sorting. Greedy algorithms.
Elementary and advanced data structures. Enumeration and non-determinism.
NP-complete problems.
Programma
- Analisi di algoritmi e complessità (20 ore)
Dimensione dei dati di un problema. Ordini di grandezza delle funzioni.
Caso pessimo, ottimo e medio. Complessità polinomiale e
superpolinomiale.
Limiti superiori e inferiori della complessità di un problema.
Tecniche per la dimostrazione di limiti inferiori.
Relazioni di ricorrenza: metodi di soluzione e teorema principale.
- Progetto di algoritmi (25 ore)
Divide et impera: Mergesort, Quicksort.
Moltiplicazione rapida.
Ordinamento in tempo lineare.
Algoritmi greedy.
Programmazione dinamica.
- Strutture dati (20 ore)
Strutture di base.
Dizionari. Realizzazione con vettori e tabelle hash.
Code con priorità.
Heap e Heapsort.
Alberi binari di ricerca, alberi bilanciati.
Grafi orientati e non orientati. Realizzazioni e visite in ampiezza e in
profondità.
- Problemi computazionalmente difficili (15 ore)
Problemi decisionali, di ricerca e di ottimizzazione.
Enumerazione e backtracking. Non determinismo.
Classi di complessità. Le classi P e NP. Problemi NP-completi.
Ore lezione: | 75 | Ore esercitazione: | 45 | | | |
Bibliografia
T.H. Cormen, C.E. Leiserson, R.L. Rivest, "Introduzione agli algoritmi",
Jakson Libri, Milano, seconda edizione 1999.
Modalità di esame