Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Introduzione
• Scopi
• Programma
• Modalita' d'esame
• Bibliografia
• Docente e home page
a.a. 2008-2009
1
Copyright © 2006-2009 by Claudio Salati.
These tutorials have been produced for the course "Algoritmi
Avanzati" (Computer Science) of the University of Ferrara.
They may be used for educational purposes, under the condition that
their source is explicitly acknowledged.
[email protected]
[email protected]
[email protected]
[email protected]
2
Scopi del corso
• Introdurre ai fondamenti della teoria degli algoritmi e delle strutture
dati e all'analisi della complessità computazionale di programmi.
• Familiarizzare lo studente con le principali problematiche e tecniche
relative alla verifica e alla progettazione degli algoritmi.
• Introdurre i metodi di base utilizzati per stabilire la complessità di
programmi e problemi e i criteri utilizzati per scegliere e progettare
strutture dati efficienti.
• Introdurre alcune delle principali strategie per la risoluzione di
problemi tramite algoritmi.
• Presentare un insieme di algoritmi e strutture dati fondamentali.
• Dopo aver superato l'esame si ritiene che lo studente sia in grado di:
• risolvere algoritmicamente problemi classici e scegliere
motivatamente le strutture dati adatte ad ottenere soluzioni
computazionalmente efficienti.
• porre limiti superiori sufficientemente precisi (indipendenti
dall'architettura) alla complessità computazionale di programmi di
media difficoltà.
3
Programma sintetico del corso
• Cosa e' un algoritmo
• Semantica di un programma
• Verifica di correttezza e terminazione
• Programmazione strutturata e progettazione top-down
• Complessita' degli algoritmi e dei problemi
• Searching and sorting
• Strutture dati fondamentali: Liste, Alberi, Grafi, Alberi di ricerca
binaria, Hash table, 2-3 B-Tree
• Gestione dinamica della memoria
• Strategie di progettazione:
• divide&conquer
• greedy method
• semplificazione e trasformazione algebrica
• tecniche di Montecarlo
• differenziazione formale
4
Programma del corso
1
• Introduzione e nozioni preliminari. Problema e algoritmo: dal
problema al programma.
Significato di un programma e sua definizione tramite semantica
assiomatica.
Analisi degli algoritmi: correttezza e terminazione (dimostrazione
formale e semi-formale), complessità nello spazio e nel tempo.
Complessita’ di un problema.
Complessita’ asintotica: definizione di O() e ().
• Nozioni matematiche. Principio di induzione matematica.
Relazioni ricorsive e soluzione di equazioni di ricorrenza del tipo
"divide et impera".
• Programmazione strutturata. Tipi di dati, strutture di dati,
introduzione ai tipi di dati astratti (ADT).
Progettazione top-down e per raffinamenti successivi, differenziazione
formale.
Contratto chiamante-chiamato e sua definizione sintattica e semantica.
Ricorsione.
• Algoritmi di ricerca. Ricerca sequenziale e ricerca binaria.
5
Programma del corso
2
• Algoritmi di ordinamento. Ordinamento interno per confronti:
numero minimo di confronti necessari per ordinare n elementi.
Algoritmi di ordinamento elementari (quadratici): selection-sort,
insertion-sort, bubble-sort.
Algoritmi di ordinamento per confronto ottimi : merge-sort, la struttura
di heap e l'algoritmo heapsort.
Algoritmi di ordinamento non basati sul confronto: radix-sort.
• Strutture dati di base. Liste, Stack, Code e relative operazioni.
Le strutture dati di base come ADT.
Implementazione (array+indici, memoria dinamica+puntatori) e
varianti implementative (liste circolari e non, semplicemente e
doppiamente linkate, con e senza nodo dummy di testate): analisi
delle operazioni, vantaggi e svantaggi di ciascuna variante.
• Programmazione. Modalita' di allocazione delle variabili.
Puntatori e aritmetica degli indirizzi.
La macro assert().
La ricorsione e la sua implementazione tramite stack: utilizzo di uno
stack per l'eliminazione della ricorsione. Esempi di problemi e
6
soluzioni ricorsive e non.
Programma del corso
3
• Gestione dinamica della memoria. L’algoritmo dei boundary-tag.
• Alberi. Concetto di albero e definizioni (altezza di un nodo e di un
albero, profondità e livello di un nodo, altezza dell'albero, alberi n-ari e
binari).
Tecniche di attraversamento (inorder, preorder, postorder).
L’albero come ADT.
Tecniche di rappresentazione in memoria dinamica per alberi n-ari e
binari: figlio-sinistra e fratello-destro, figlio-sinistro e figlio-destro per
alberi binari.
• Alberi binari di ricerca. Operazioni di ricerca, ritrovamento
dell’elemento minimo, successore, predecessore, inserimento e
cancellazione.
Costo delle operazioni.
• Grafi. Grafi orientati e non orientati.
Definizioni e concetti principali (grado, cammino, lunghezza cammino,
...).
Tecniche di rappresentazione.
7
Ordinamento topologico e test di aciclicità.
Programma del corso
4
• Altre strutture dati: Tabelle hash, 2-3BTree, altre rappresentazioni
di insiemi e partizioni (bit map, alberi di Tarjan).
• Tecniche di progetto.
• Divide et impera,
• greedy method,
• semplificazione e trasformazione algebrica,
• tecniche di Montecarlo,
• differenziazione formale.
8
Lista dei principali algoritmi esaminati
• Algoritmo di Euclide per il MCD
• Minimo e massimo di un vettore (diversi metodi)
• Algoritmi di ordinamento: straight selection, straight exchange
(bubblesort), straight insertion, mergesort, heapsort, radix sort,
quicksort
• Ricerca binaria
• Knapsack
• Minimum cost spanning tree (algoritmo di Kruskal)
• Single source - shortest paths (algoritmo di Dijkstra)
• Topological sort di un grafo
• Regola di Horner per il calcolo dei polinomi
• Simulated annealing (cenni)
• Boundary-tag
9
Modalita' di esame
• Esame orale finale.
• Durante le lezioni ci saranno (praticamente sempre) delle
sessioni di esercitazione (di gruppo e individuali), normalmente
legate agli argomenti trattati in quel momento:
la partecipazione con successo a queste esercitazioni potra'
essere considerata come un sostanziale sostitutivo dell'esame.
10
11
Venite
qui che
lo facciamo
insieme
12
Docente
Claudio Salati
• email:
[email protected]
[email protected]
[email protected]
[email protected]
• Telefono: 328-211-7849
• Orario di ricevimento
Sostanzialmente on demand.
• Home page del corso
http://dm.unife.it/~salati
13
Bibliografia
• Le dispense del corso sono disponibili in copia elettronica sul sito:
http://dm.unife.it/~salati.
• Il capitolo sulla gestione dinamica della memoria e' tratto da: F. de
Luigi, C. Salati, Fondamenti di Informatica - Esercitazioni,
Gabriele Corbo Editore.
• Libro di Testo: T.H. Cormen, C.E. Leiserson, R.L. Rivest,
Introduzione agli algoritmi, 2. ed., Jackson Libri, 1999 (CLR):
molto diffuso ma in realta’ non utilizzato in questo corso.
• Per il linguaggio C si fa riferimento a B.W. Kernighan, D.M.
Ritchie, The C Programming Language, 2nd Ed., Prentice-Hall
(traduzione italiana del Gruppo Editoriale Jackson).
• Come riferimento veramente significaytivo vedi:
A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data Structures and
Algorithms, Addison-Wesley.
• Vedi anche: M.T. Goodrich, R. Tamassia, Strutture dati e algoritmi
in Java, 1a ed. it. (4a americana), Zanichelli.
• Di interesse e' il link: http://www.onlynx.it/hi/strumenti/zen.html
14
Riconoscimenti - 1
Le lezioni sono state preparate utilizzando i seguenti riferimenti:
• D.E. Knuth, The art of computer programming, Vol. 1,
Fundamental Algorithms, Addison-Wesley.
– sez. 1, Basic concepts
– sez. 1.2.1, Mathematical Induction
• C.A.R. Hoare, An Axiomatic Basis for Computer Programming,
Communications of the ACM, Vol. 12, No. 10, Dec. 1969.
• N. Wirth, Principi di programmazione strutturata, ISEDI.
– sez. 5, 6, 7
• E. Horowitz, S. Sahni, Fundamentals of data structures,
Computer Science Press.
– sez. 4.8, Doubly Linked Lists and Dynamic Storage Management
– sez. 6.4, Topological Sort
15
Riconoscimenti - 2
Le lezioni sono state preparate utilizzando i seguenti riferimenti:
• E. Horowitz, S. Sahni, Computer algorithms, Computer Science
Press.
– sez. 1.1, What is an Algorithm?
– sez. 1.4, Analyzing Algorithms
– sez. 2.4, Sets and Disjoint Set Union
– sez. 2.6, Hashing
– sez. 3.1, Divide-and-Conquer, The General Method
– sez. 3.2, Binary Search
– sez. 4.1, The Greedy Method, The General Method
– sez. 4.3, Knapsack Problem
– sez. 4.7, Single source shortest paths
– sez. 9.1, Algebraic Simplification and Transformation, The General
Method
– sez. 9.2, Evaluation and Interpolation
16
Riconoscimenti - 3
Le lezioni sono state preparate utilizzando i seguenti riferimenti:
• A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of
computer algorithms, Addison-Wesley.
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
sez. 1.1, Algorithms and their Complexity
sez. 2.1, Data Structures: Lists, Queues, and Stacks
sez. 2.2, Set representations
sez. 2.3, Graphs
sez. 2.4, Trees
sez. 2.5, Recursion
sez. 2.6, Divide-and-Conquer
sez. 2.7, Balancing
sez. 3.3, Sorting by Comparisons
sez. 3.4, Heapsort
sez. 4.4, Binary Search Trees
sez. 4.5, Optimal Binary Search Trees
sez. 4.6, A Simple Disjoint-Set Union Algorithm
sez. 5.1, Minimum-Cost Spanning Tree
sez. 5.10, Single source problems
17
Riferimenti al libro di testo (CLR)
Le lezioni non seguono troppo fedelmente il contenuto del libro di
testo:
• alcuni argomenti trattati a lezione non sono coperti da CLR
• la trattazione matematica e' molto piu' leggera nelle lezioni.
I capitoli citati di seguito sono quelli che coprono, sia pure in ordine
diverso, gli stessi argomenti trattati a lezione:
• cap. 1
• sez. 2.1, fino a pag. 26
• cap. 7
• cap. 9
18