corso

Algoritmica D

Codice:	AA006	Crediti:	9	Semestre:	2	Sigla:	ALG

Settore disciplinare:		INF/01 - Informatica

Docente

Linda Pagli

Tel. 0502212735

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 memoriapossibile), 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 ai modelli di calcolo e 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 P, NP, RP, NP-completi.

English Description

Introduction to the design, analysis and computation complexity of algorithms and data structures. Basic techniques for the analysisof algorithms. Design paradigms for efficient algorithms. Definition and applications of main data structures. Complexity ofcomputationally hard problems. Algorithm engineering and experimentation.

Programma

Analisi di Algoritmi e Complessità
1. Introduzione alla complessità di calcolo [CLR 1]
2. Ordini di grandezza delle funzione [CLR 2]
3. Algoritmi ricorsivi: Numeri di Fibonacci, Ricerca Binaria, Mergesort, Moltiplicazione rapida, Moltiplicazione di matrici.[L 5]
4. Relazioni di ricorrenza [CLR 4]
5. Limiti inferiori alla complessit\`a [L 4.2]
Progetto di Algoritmi e Strutture dei Dati
1. Code, Pile, Heap [CLR 7]
2. Heapsort [CLR 7]
3. Quicksort [CLR 8]
4. Ordinamento in tempo lineare [CLR 9]
5. Tabelle hash [CLR 12]
6. Liste e alberi [H 16]
7. Alberi binari di ricerca [B 8.1, 8.2]
8. Grafi: rappresentazione e visite [CLR 23]
Classi di Complessità
1. Enumerazione e non determinismo [B 17]
2. Classi P, NP, NPC [B 18]
3. Algoritmi randomizzati [B 20]
Modelli di Calcolo e Calcolabilità
1. Indecidibilità e universalità [B 25]
2. Macchina di Turing [B 26]
3. Equivalenza tra modelli di calcolo [dispense]

Bibliografia

[B] A. Bertossi "Algoritmi e Strutture di Dati". Utet 2000.
[CLR] T. H. Cormen, C. E. Leiserson, R. L. Rivest "Introduzione agli algoritmi". Jackson Libri 1999.
[H] C. S. Horstmann "Concetti di informatica e fondamenti di Java 2". Apogeo 2000.
[L] F. Luccio "La struttura degli Algoritmi". Boringhieri 1982.

Modalità di esame

Scritto e orale