Algoritmi e Strutture Dati @ UniBO 2009/2010
Corso di Laurea in Informatica per il Management
Salta al programma del corso
Questa è la pagina web del corso di Algoritmi e Strutture
Dati (Anno Accademico 2009/2010) presso il corso di laurea triennale
in Informatica per il
Management, Università di Bologna. I docenti del corso sono
Moreno
Marzolla e Davide Rossi. È
possibile visitare la scheda
del corso presso il corso di Laurea. Il materiale presente qui di seguito
è disponibile anche nella pagina del corso
presso l'Università di Bologna.
Torna in cima alla pagina.
Salta alle modalità d'esame
Questo è il programma di massima del corso
- Complessità asintotica degli algoritmi
- Strutture dati elementari (Liste, Pile, Code, Alberi...)
- Algoritmi di ordinamento e ricerca
- Alberi di ricerca
- Tabelle Hash
- Tecniche Algoritmiche (divide et impera, algoritmi greedy...)
- Algoritmi su grafi (Spanning tree, cammini minimi, problemi di flusso)
Il programma dettagliato è disponibile nella sezione
contenente i lucidi delle
lezioni.
Testi adottati
- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi
e strutture dati 2/ed, McGraw-Hill, 2008, ISBN: 978 88 386
64687
- Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi,
Giuseppe F. Italiano, Progetto
di Algoritmi e Strutture Dati in Java, McGraw-Hill, 2007,
ISBN: 9788838663741
Altri testi consigliati
Torna in cima alla pagina.
Salta all'orario delle lezioni
L'esame del corso consiste in una prova scritta e un progetto.
L'esame si considera superato se il voto dello scritto risulta ≥18,
e il voto del progetto risulta ≥18. In tal caso, il voto finale
viene calcolato come:
(Voto Progetto)×0.4 + (Voto Scritto)×0.6
Chi lo desidera, può sostenere anche una prova orale
facoltativa, che può comportare un miglioramento o un
peggioramento del voto complessivo calcolato come sopra. È
possibile sostenere l'orale solo se la prova scritta e il progetto
sono entrambi sufficienti (voti ≥18). In casi specifici, il docente
si riserva la possibilità di richiedere obbligatoriamente una
prova orale integrativa allo scritto e al progetto.
Durante il corso vengono effettuate due prove parziali, una a
metà e una alla fine. La media dei voti di entrambe le prove
parziali (purché la media sia ≥18) sostituisce il voto della
prova scritta. Chi non sostiene entrambi i parziali, o riporta un voto
medio inferiore a 18, deve sostenere la prova scritta durante gli
appelli ufficiali d'esame.
Progetto del corso
È disponibile il progetto del corso [Aggiornato 8/9/2010]. Il progetto può
essere svolto singolarmente o in coppia (i progetti svolti in coppia
verranno valutati in modo più stringente rispetto a quelli
svolti singolarmente). Il codice e la relazione possono essere
consegnati in qualsiasi momento; il testo di questo progetto resta
valido per tutto l'anno accademico in corso. Il progetto va
consegnato entro il 28 febbraio 2011.
Risposte a domande frequenti
- Questo è un esame facile?
- No. Ma non è nemmeno impossibile, basta studiare. È
fondamentale esercitarsi il più possibile; a tale proposito
vengono assegnati periodicamente degli esercizi che gli studenti sono
vivamente invitati a svolgere a casa (naturalmente lo svolgimento di
tali esercizi non è obbligatorio). Gli argomenti trattati nel
corso non possono essere padroneggiati in modo passivo, per cui
è fondamentale affiancare lo studio della teoria con lo
svolgimento degil esercizi.
- È sufficiente studiare sui luicidi?
- I lucidi sono fatti per integrare lo studio individuale, e
soprattutto lo studio sul libro di testo. Non sostituiscono in
alcun modo i libri di testo, né costituiscono fonte
"autorevole" di informazione. Sebbene i lucidi vengano preparati con
la massima cura, è possibile che contengano errori o
imprecisioni (chi ne individuasse è pregato di segnalarli al
docente del corso). In nessun caso eventuali errori nelle prove
scritte e/o nei progetti potranno essere giustificati da analoghi
errori presenti nei lucidi del corso.
- Per quanto tempo resta valido lo scritto?
- La prova scritta e il progetto per il corso dell'Anno Accademico
2009/2010 restano validi fino all'ultima sessione d'esami dell'Anno
Accademico 2009/2010 (compresa).
- Posso rifare lo scritto?
- Certamente. Si noti che la consegna dello scritto annulla
automaticamente il voto dello scritto (o dei parziali)
precedente.
- Quando va consegnato il progetto?
- Il progetto per l'anno accademico 2009/2010 va consegnato in
qualsiasi momento, purché tassativamente entro il 28
febbraio 2011. Dopo tale data tutti coloro che non hanno
consegnato il progetto dovranno sostenere nuovamente la prova
scritta.
- Durante lo scritto o il parziale si possono consultare libri o appunti?
- Durante le prove scritte o i parziali non è
consentito consultare libri o appunti. Si tenga però
presente che lo scopo del corso non è quello di imparare
algoritmi a memoria, ma piuttosto imparare a usare le tecniche
spiegate a lezione per risolvere problemi nuovi. Per tale ragione,
verrà sempre allegato al testo dell'esame un formulario contenente alcune
definizioni e formule utili (nota: verrà aggiornato
periodicamente). Il formulario potrà essere liberamente
consultato. Inoltre, le domande tenderanno a richiedere un limitato
sforzo mnemonico, privilegiando ove possibile l'aspetto
creativo
legato ad individuare la soluzione ai problemi proposti, nonché
la correttezza dell'analisi della soluzione proposta (ove
richiesto).
Torna in cima alla pagina.
Salta ai lucidi delle lezioni
Orario del corso di Algoritmi e Strutture Dati, II semestre AA 2009/2010
| Martedì |
15:30—17:30, aula Ercolani 2 |
| Giovedì |
11:30—13:30, aula Ercolani 1 |
Torna in cima alla pagina.
Salta ad altro materiale
I lucidi non sono da considerare come sostitutivi né
dei testi di riferimento né della frequenza alle lezioni, che
costituiscono importanti elementi per una buona preparazione
dell'esame; i lucidi messi a disposizione costituiscono soltanto uno
schema di parte delle lezioni. Non si garantisce la correttezza di
quanto riportato nei lucidi: segnalazioni di errori sono ovviamente
sempre ben gradite.
Copyright notice: I lucidi delle lezioni sono
distribuiti con licenza Creative
Commons attribution-noncommercial-share alike (l'esatta versione
della licenza applicata è indicata nella seconda pagina di
ciascuna serie di lucidi). L'autore dei lucidi è Moreno Marzolla; in alcuni
casi il materiale originario è stato sviluppato da Alberto Montresor che
l'ha reso disponibile
con la medesima licenza.
- 30/09/2009
- Introduzione al corso
[.odp, 1.5 MBs][.pdf, 974.8 KBs] Aggiornato 27/11/2009
- 1/10/2009, 7/10/2009, 8/10/2009
- Stima della complessità asintotica degli algoritmi; le notazioni asintotiche
(Libro di testo: Capitolo 2, escluso: dimostrazione del teorema fondamentale della ricorrenza, sezione 2.7.2 e 2.8).
[.pdf, 396.9 KBs] Aggiornato 29/09/2009
- 21/10/2009, 22/10/2009
- Strutture dati elementari: array, liste, code, alberi; visite di alberi (Libro di testo: Capitolo 3).
[.odp, 103.9 KBs][.pdf, 360.2 KBs] Aggiornato 30/09/2009
- 04/11/2009, 05/11/2009, 11/11/2009
- Algoritmi di Ordinamento (Libro di testo: Capitolo 4; cenni della sezione 4.5.1
Analisi di QuickSort
).
[.odp, 1.4 MBs][.pdf, 967 KBs] Aggiornato 18/11/2009
- 12/11/2009
- Esercizi Aggiornato 25/11/2009
(Bandiera.java,
Intervalli.java).
- 18/11/2009
- Statistiche (Libro di testo: Capitolo 5, esclusa la sezione 5.3
Selezione deterministica
).
[.odp, 237.1 KBs][.pdf, 267.6 KBs] Aggiornato 19/11/2009
- 19/11/2009
- Alberi Binari di Ricerca (Libro di testo: Capitolo 6, escluse sezioni 6.3 e 6.6).
[.odp, 47.3 KBs][.pdf, 219.5 KBs] Aggiornato 05/12/2009
- 25/11/2009
- Alberi bilanciati di Ricerca (Libro di testo: Capitolo 6, escluse sezioni 6.3 e 6.6).
[.odp, 208 KBs][.pdf, 359.3 KBs] Aggiornato 02/12/2009
- 26/11/2009
- Correzione esercizi Aggiornato 26/11/2009
- 02/12/2009, 03/12/2009
- B-Tree, Tabelle hash (Libro di testo: Capitolo 7)
[.odp, 1.5 MBs][.pdf, 1.3 MBs] Aggiornato 05/12/2009
- 09/12/2009
- Code con priorità (Libro di testo: Capitolo 8, esclusa sezione 8.3)
[.odp, 67 KBs][.pdf, 284 KBs] Aggiornato 10/12/2009
- 10/12/2009
- Correzione esercizi Aggiornato 10/12/2009
- 16/12/2009
- Union-find (Libro di testo: Capitolo 9, esclusa sezione 9.4)
[.odp, 52.6 KBs][.pdf, 235.4 KBs] Aggiornato 16/12/2009
- 17/12/2009
- Tecniche Algoritmiche: Divide Et Impera (Libro di testo: Capitolo 10)
[.odp, 301.7 KBs][.pdf, 196 KBs] Aggiornato 17/12/2009
- 16/02/2010
- Presentazione del progetto del corso
- 16/02/2010, 18/02/2010
- Tecniche Algoritmiche: Programmazione Dinamica (Libro di testo: Capitolo 10)
[.odp, 119.1 KBs][.pdf, 317.9 KBs] Aggiornato 23/02/2010
- 23/02/2010
- Tecniche Algoritmiche: Algoritmi greedy (Libro di testo: Capitolo 10)
[.odp, 54.8 KBs][.pdf, 234.2 KBs] Aggiornato 23/02/2010
- 25/02/2010
- Esercizi risolti (CINA.java, ContaInversioni.java, Copiatutto.java) Aggiornato 25/02/2010
- 02/03/2010
- Il problema dello zaino
[.odp, 48.2 KBs][.pdf, 161.4 KBs] Aggiornato 02/03/2010
[Zaino.java]
- 02/03/2010
- Algoritmi su Stringhe (Libro di testo: Capitolo 11, solo le sezioni 11.1, 11.2, 11.3)
[.odp, 140.8 KBs][.pdf, 463.3 KBs] Aggiornato 04/03/2010
- 04/03/2010
- Grafi (Libro di testo: Capitolo 12, esclusa sezione 12.5.2)
[.odp, 961.1 KBs][.pdf, 1.8 MBs] Aggiornato 11/03/2010
- 09/03/2010, 11/03/2010
- Algoritmi di visita di grafi (Libro di testo: Capitolo 12, esclusa sezione 12.5.2)
[.odp, 373.7 KBs][.pdf, 560.8 KBs] Aggiornato 23/03/2010
- 23/03/2010
- Minimo albero ricoprente (Minimum Spanning Tree) (Libro di testo: Capitolo 13, esclusa sezione 13.4)
[.odp, 88.5 KBs][.pdf, 416.6 KBs] Aggiornato 24/03/2010
- 25/03/2010
- Esercizi
(e relative soluzioni)
- 30/03/2010
- Cammini minimi (Libro di testo: Capitolo 14, esclusa sezione 14.4)
[.odp, 736.9 KBs][.pdf, 705.2 KBs] Aggiornato 13/04/2010
- 13/04/2010
- Esercizi
[.odp, 92.3 KBs][.pdf, 352.6 KBs] Aggiornato 16/04/2010
- 15/04/2010
- Rilevazione questionari sulla didattica
Esercizi
- 20/04/2010
- Cenni alle classi di complessità le classi P e NP
[.odp, 85 KBs][.pdf, 196.1 KBs] Aggiornato 20/04/2010
- 22/04/2010
- Esercizi riepilogativi
[.odp, 68.6 KBs][.pdf, 168.7 KBs] Aggiornato 22/04/2010
- Fine delle lezioni del corso
Torna in cima alla pagina.
Salta agli appelli d'esame
Esercizi svolti
Altri siti di interesse
Torna in cima alla pagina.
Appelli d'esame per il corso di Algoritmi e Strutture Dati, AA 2009/2010
|
Parziali |
| I |
Primo parziale: Giovedì 28 gennaio 2010, ore 13:00, aula Ercolani 1
[Testo con soluzioni]
|
| II |
Secondo parziale: Giovedì 20 maggio 2010, ore 10:30, aula Ercolani 2
[Testo con soluzioni]
|
|
Prima Sessione |
| I |
Prova scritta: Lunedì 7 giugno 2010, ore 10:30, aula Ercolani 2
[Testo con soluzioni]
|
| II |
Prova scritta: Giovedì 1 luglio 2010, ore 10:30, aula Ercolani 2
[Testo con soluzioni]
|
|
Seconda Sessione |
| I |
Prova scritta: Lunedì 6 settembre 2010, ore 10:30, aula Ercolani 1
[Testo con soluzioni]
|
| II |
Prova scritta: Lunedì 20 settembre 2010, ore 10:30, aula Ercolani 2
[Testo con soluzioni]
|
|
Terza Sessione |
| I |
Prova scritta: Mercoledì 12 gennaio 2011, ore 10:30, Aula VII Piano - Dipartimento di Matematica, P.zza di Porta S. Donato 5
[Testo con soluzioni]
|
| II |
Prova scritta: Martedì 1 febbraio 2011, ore 10:30, Aula Ercolani 2
[Testo] |
Torna in cima alla pagina.