Algoritmi e Strutture Dati—Modulo B
CdL in Informatica per il Management, AA 2011/2012
Università di Bologna
Avvisi
Salta alla descrizione del corso
L'edizione 2011/2012 del corso è terminata. Vai alla pagina dell'edizione 2012/2013.
Descrizione del corso
Questa è la pagina web del corso di Algoritmi e Strutture Dati—Modulo B (11929), corso di laurea in Informatica per il Management, AA 2011/2012, Università di Bologna.
- Il modulo A è tenuto durante il primo ciclo dal prof. Luciano Bononi.
- Il modulo B è tenuto durante il secondo ciclo da Moreno Marzolla.
Questa pagina contiene le informazioni relative al modulo B. Per il modulo A si faccia riferimento alla pagina mantenuta dal prof. Bononi.
Programma e modalità d'esame
Il programma e le modalità d'esame sono disponibili sulla pagina del modulo A
Testo adottato
- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati 2/ed, McGraw-Hill, 2008, ISBN: 978 88 386 64687
Testi di consultazione
- Alan A. Bertossi, A. Montresor, Algoritmi e strutture di dati, CittàStudi, 2010, ISBN: 9788825173567. Questo è un ottimo testo didattico, che copre essenzialmente gli stessi argomenti del testo adottato.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli algoritmi e strutture dati 2/ed, McGraw-Hill, 2005, ISBN: 9788838662515. Si tratta di uno dei testi classici sugli algoritmi che offre una trattazione piuttosto approfondita degli argomenti principali. Questo libro include molto più materiale rispetto a quanto verrà svolto a lezione, e richiede buone basi matematiche per comprendere le dimostrazioni. Questo libro è consigliato a coloro che desiderano approfondire gli argomenti svolti, oppure a chi sia particolarmente appassionato alla materia.
- Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano, Progetto di Algoritmi e Strutture Dati in Java, McGraw-Hill, 2007, ISBN: 9788838663741. Questo libro è il complemento del testo adottato, poiché contiene la descrizione delle implementazioni Java degli algoritmi descritti tramite pseudocodice nel libro di Demetrescu et al. Attenzione: questo volume NON sostituisce il libro di Demetrescu, Finocchi, Italiano, perché non contiene la parte di teoria che vedremo a lezione.
Orario delle lezioni
| Secondo Ciclo | |
|---|---|
| Martedì | 10:30—13:30, aula Ercolani 1 |
| Giovedì | 16:30—18:30, aula Ercolani 1 |
Lucidi delle lezioni
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.
- Materiale prof. Bononi
- 30/09/2011, 7/10/2011
- Introduzione al corso (lucidi prof. Bononi)
[.pdf] - 11/10/2011, 14/10/2011
- 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, 470.3 KBs] Aggiornato 14/10/2011 - 25/11/2012
- Algoritmi di selezione
- 21/02/2012, 23/02/2012
- Hashing (Libro di testo: Capitolo 7)
[.odp, 1.4 MBs][.pdf, 957.6 KBs] Aggiornato 21/02/2012 - 28/02/2012
- Code con priorità (Libro di testo: Capitolo 8, solo sezione 8.1)
[.odp, 44.1 KBs][.pdf, 147.2 KBs] Aggiornato 27/02/2012 - 01/03/2012
- Strutture Union-Find (Libro di testo: Capitolo 9, escluse sezioni 9.3, 9.4)
[.odp, 65.2 KBs][.pdf, 169.3 KBs] Aggiornato 06/03/2012 - 06/03/2012
- Tecniche algoritmiche: Divide et Impera (Libro di testo: Capitolo 10)
[.odp, 293.3 KBs][.pdf, 165.1 KBs] Aggiornato 06/03/2012 - 08/03/2012
- Esercizi
- 13/03/2012
- Tecniche algoritmiche: Programmazione Dinamica (Libro di testo: Capitolo 10)
[.odp, 96.2 KBs][.pdf, 278.4 KBs] Aggiornato 13/03/2012 - 15/03/2012
- Esercizi
- 20/03/2012
- Lezione annullata causa sessione di laurea
- 22/03/2012
- Ulteriori approfondimenti su programmazione dinamica
- 27/03/2012
- Lezione annullata causa impegni istituzionali del docente
- 29/03/2012
- Tecniche algoritmiche: Algoritmi greedy
[.odp, 50.2 KBs][.pdf, 188.2 KBs] Aggiornato 21/03/2012 - 03/04/2012
- Il problema dello zaino
[.odp, 53.4 KBs][.pdf, 114.7 KBs] Aggiornato 02/04/2012 - 05/04/2012
- Vacanze di Pasqua
- 10/04/2012
- Vacanze di Pasqua
- 12/04/2012
- Esercizi
EsercizioConsderiamo l'esercizio numero 2 sopra descritto, che consiste nel determinare il numero massimo di monete necessarie per erogare un resto R (se ciò è possibile). Supponiamo che l'array
Cdi monete sia così definito (in Java):int C[] = {1, 1, 1, 5, 5, 5, 10, 10, 20, 50, 50, 50, 50};Quale è il numero massimo di monete necessario ad erogare un resto pari a:
- 68 (Soluzione: 7)
- 129 (Soluzione: non esiste soluzione)
- 104 Soluzione: ???)
- 53 (Soluzione: ???)
- 17/04/2012
- Grafi (Libro di testo: Capitolo 12, esclusa sezione 12.5.2)
[.odp, 680.4 KBs][.pdf, 500 KBs] Aggiornato 19/04/2012 - 19/04/2012, 24/04/2012
- Algoritmi di visita di grafi (Libro di testo: Capitolo 12, esclusa sezione 12.5.2)
[.odp, 325.7 KBs][.pdf, 339.6 KBs] Aggiornato 24/04/2012 - 26/04/2012
- Esercizi
- 03/05/2012
- Cammini Minimi (Libro di testo: Capitolo 14, escluse sezioni 14.3, 14.4)
[.odp, 709.9 KBs][.pdf, 460.3 KBs] Aggiornato 03/05/2012
Approfondimenti
- Moreno Marzolla, Esercizi di Algoritmi e Strutture
Dati
[odt]
[PDF]
Aggiornato 23/05/2013
Documento distribuito in accordo con la licenza Creative Commons Attribution-ShareAlike 3.0 Unported (CC-BY-SA 3.0)
- Corso di Algoritmi e Strutture Dati, prof. Alberto Montresor, Università di Trento
- Corso di Ingegneria degli Algoritmi, prof. Giuseppe F. Italiano, Università di Roma
Tor Vergata
- The Stony Brook Algorithm Repository
- Programming Pearls
- Codice sorgente della libreria Java ASDlab (in formato .zip, .tar.gz, dal sito di Giuseppe. F. Italiano).
- Free Online Algorithms and Data Structures Books
Esami
Nota: Durante i parziali e le prove scritte è consentito consultare libri e appunti
| Parziali | |
|---|---|
| I | |
| II | Secondo parziale: Lunedì 21 maggio 2011, ore 10:30, aula Ercolani 1 |
| Sessione Estiva | |
| I | Prova scritta: Giovedì 7 giugno 2012, ore 10:30, aula Ercolani 1 [Testo] |
| II | Prova scritta: Martedì 3 luglio 2012, ore 10:30, aula Pincherle, Dip. di Matematica |
| III | Prova scritta: Martedì 24 luglio 2012, ore 10:30, aula Ercolani 1 |
| Sessione Autunnale | |
| I | Prova scritta: Giovedì 13 settembre 2012, ore 10:30, aula G complesso Belmeloro |
| Sessione Invernale | |
| I | Prova scritta: Mercoledì 16 gennaio 2013, ore 10:00, aula Ercolani 2 [Testo] |
| II | La prova verrà recuperata il giorno giovedì 14 febbraio 2013, ore 10:00, Aula Ercolani 1 [Testo] |
