Algoritmi e Strutture dati a.a. 2013/2014
Informazioni sul corso
Dr Maria Federico
Informazioni docente
• E-mail docente: fdrmra@unife.it
• Ricevimento:
– Mercoledì 15:00-16:00 presso ufficio docenti a contratto (3° piano), Dipartimento di
Matematica e Informatica, Campus scientifico tecnologico Blocco B via Saragat 1
– Su appuntamento (inviare e-mail)
Algoritmi e Strutture dati Informazioni sul corso
Università degli studi di Ferrara Maria Federico
3
Informazioni lezioni
• Martedì, Mercoledì 16:30-18:30
• Giovedì 14:30-17:30 (7 ore a settimana)
• Aula F6
• 1 Ottobre 2013 – 17 Dicembre 2014 (80 ore, 10 CFU per Informatica)
• 1 Ottobre 2013 – 14 Novembre 2014 (48
ore, 6 CFU per Matematica)
Perché un corso di algoritmi e strutture dati?
“Prima dei calcolatori c’erano già gli algoritmi.
Ma adesso che ci sono i calcolatori, ci sono più algoritmi e gli algoritmi sono il cuore del calcolo.”
(Prefazione Introduzione agli algoritmi e strutture dati 3/ed, Cormen et al. 2010)
Lo studio degli algoritmi costituisce la base
dell’informatica perché prima che un computer
esegua qualsiasi attività è necessario fornirgli un
algoritmo che gli indichi esattamente cosa fare
Processo di sviluppo di un programma
1. Specifica funzionale del problema
2. Analisi del problema e definizione di un algoritmo risolutivo
3. Descrizione con diagramma di flusso e/o pseudocodice 4. Traduzione dell’algoritmo in programma in linguaggio di
programmazione ad alto livello 5. Compilazione
6. Esecuzione e Verifica
Cosa studieremo
• Algoritmi = descrizione precisa di una
sequenza di azioni che devono essere eseguite per giungere alla risoluzione di un problema
– Sintesi / disegno / progetto – Analisi dell’efficienza
• Strutture dati = è fondamentale che i dati siano ben organizzati e strutturati in modo che
l’algoritmo li possa elaborare efficientemente
Algoritmi e Strutture dati Informazioni sul corso
Università degli studi di Ferrara Maria Federico
7
Materiale didattico
• Libro di testo
Titolo: Introduzione agli algoritmi e strutture dati 3/ed Autori: Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest, Clifford Stein ISBN: 9788838665158
Pub Date: Giugno 2010
Pagine: 1030
Materiale didattico
• Libro di riferimento
Titolo: Strutture di dati e algoritmi.
Progettazione, analisi e visualizzazione Autori: Pierluigi Crescenzi, Giorgio Gambosi,
Roberto Grossi ISBN: 9788871922737 Pub Date: 2006
Pagine: 384
Algoritmi e Strutture dati Informazioni sul corso
Università degli studi di Ferrara Maria Federico
9
Materiale didattico
• Slide e altro materiale presentato a lezione
– Reperibili sulla pagina del corso
http://www.unife.it/scienze/informatica/insegn amenti/algoritmi-strutture-dati
– Sulla home page del docente
http://algogroup.unimore.it/people/maria/alg
oritmi_2013-2014.html
Propedeuticità
• Istituzioni di matematica
• Programmazione e laboratorio
• Sono consigliati come propedeutici, anche
se non costituiscono prerequisito formale
Algoritmi e Strutture dati Informazioni sul corso
Università degli studi di Ferrara Maria Federico
11
Programma del corso
1. Introduzione al corso [1, 2]
• Definizione di problema, algoritmo,
rappresentazione di algoritmi, sintesi e analisi di algoritmi, strutture dati
2. Complessità computazionale [3, 4-(4.2, 4.6)]
• Analisi asintotica, calcolo complessità
algoritmi iterativi, metodi di risoluzione delle
relazioni di ricorrenza per algoritmi ricorsivi,
classificazione problemi e NP-completezza
(cenni) [34.1, 1 Crescenzi]
Programma del corso
3. Strutture dati statiche [slide; 2.1 Crescenzi]
• Array, record
4. Algoritmi di ordinamento su array
• Iterativi: selection sort, insertion sort, bubble sort
[2 Cormen + 2.2 Crescenzi)]
• Ricorsivi: merge sort, quick sort [4, 7-(7.3); 2.5 Crescenzi]
– Tempo lineare: Counting sort, Radix sort, Bucket sort [8]
5. Algoritmi di ricerca su array [2.4 Crescenzi]
Algoritmi e Strutture dati Informazioni sul corso
Università degli studi di Ferrara Maria Federico
13
Programma del corso
6. Heap e code con priorità [6; 8.1 e 8.2 Crescenzi]
• Operazioni su heap, Heapsort
7. Strutture dati dinamiche [10, appendici B.4 e B.5; 3.1, 7.1, 7.3 Crescenzi]
• Pile, code, liste, grafi, alberi
8. Algoritmi su alberi binari [12-(12.4); 4.1, 5.4 Crescenzi]
• Visita (con generalizzazione ad albero n-
ario), ricerca e modifica per alberi binari di
ricerca
Programma del corso
9. Algoritmi su grafi [*21-(21.4); 22-(22.5), 23, *24-(24.5, 24.6); 7.4, 7.5.1 Crescenzi]
• Visita DFS e BFS, ordinamento topologico, algoritmi di Kruskal, Prim, Dijkstra, Bellman-Ford
10. Hashing [*11]
• Tabelle hash, funzioni hash, indirizzamento diretto e aperto
11. Programmazione dinamica [15-(15.4,15.5)]
12. Algoritmi golosi [16.1, 16.2]
Algoritmi e Strutture dati Informazioni sul corso
Università degli studi di Ferrara Maria Federico
15
