Algoritmi e Strutture dati
a.a. 2012/2013
Informazioni sul corso
Dr Maria Federico
Informazioni docente
• E-mail docente: [email protected]
• Ricevimento:
– Su appuntamento (inviare e-mail)
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
2
Informazioni lezioni
• Lunedì, Martedì, Mercoledì 10:30-13:30
aula INFO2
• 15 Ottobre 2012 – 9 Gennaio 2013
• 88 ore (10 crediti)
• Lezioni teoriche ed esercitazioni
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
3
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
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
4
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
5
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: June 2010
Pagine: 1030
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
6
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
7
Materiale didattico
• Slide e altro materiale presentato a
lezione
– Reperibili sulla pagina del corso
http://
– Inizialmente sulla mia home page (sezione
Didattica)
http://algo.ing.unimo.it/people/maria/index.html
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
8
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
9
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 non ricorsivi, metodi di risoluzione
delle relazioni di ricorrenza per algoritmi
ricorsivi, classificazione problemi e NPcompletezza (cenni) [34.1, 1 Crescenzi]
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
10
Programma del corso
3. Strutture dati statiche [slide; 2.1 Crescenzi]
•
Interi, reali, booleani, caratteri, 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]
•
Ricerca lineare, ricerca binaria
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
11
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), 13.1; 4.1,
5.4 Crescenzi]
•
Visita (con generalizzazione ad albero non
binario), ricerca e modifica per alberi binari
di ricerca, alberi rosso-neri
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
12
Programma del corso
9. Algoritmi su grafi [*21-(21.4); 22, 23, *24-(24.5, 24.6),
*25-(25.4); 7.4, 7.5 Crescenzi]
•
Visita DFS e BFS, ordinamento topologico,
componenti connesse, algoritmi di Kruskal, Prim,
Dijkstra, Bellman-Ford, Floyd-Warshall
10. Hashing [*11]
•
Tabelle hash, funzioni hash, indirizzamento diretto e
aperto
11. Programmazione dinamica [15-(15.5)]
•
Longest common substring (LCS)
12. Algoritmi golosi [16.1, 16.2]
* Le dimostrazioni non sono richieste
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
13
Esame
• Prova scritta
–
–
–
–
–
È obbligatoria l’iscrizione on-line
tramite il sito studiare UNIFE
4 esercizi
Disegno di algoritmi
Analisi di algoritmi
Applicazione di algoritmi visti a lezione
Operazioni su strutture dati
durante la prova scritta NON si possono usare appunti, libri, calcolatrici,
cellulari, etc.
• Prova orale
– Può riguardare qualunque argomento trattato a lezione
– è volto a verificare la padronanza dei concetti e delle
tecniche oggetto dell'insegnamento
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
14
Domande?
Algoritmi e Strutture dati
Informazioni sul corso
Università degli studi di Ferrara
Maria Federico
15