Laboratorio di Algoritmi e Strutture Dati
Laurea in Ingegneria e Scienze Informatiche, Università di Bologna, AA 2020/2021
Avvisi
Salta al programma e libri di testo
- 10/3/2021
- Sono disponibili le soluzioni degli esercizi proposti nei laboratori del 4 e 5 marzo. Le soluzioni sono consultabili nella sezione del materiale didattico in fondo a questa pagina.
- 13/01/2021
- Creata questa pagina. Il contenuto è da considerarsi ancora provvisorio.
Descrizione del modulo, programma e libri di testo
Questa è la pagina del modulo di Laboratorio di Algoritmi e Strutture Dati, corso di laurea in Ingegneria e Scienze Informatiche, AA 2020/2021, Università di Bologna.
La parte di teoria è tenuta dai prof. Luciano Margara (classe A) e Vittorio Maniezzo (classe B). I tutor per il laboratorio sono:
- Luca Deluigi
- Nicolas Farabegoli
- Gabriele Graffieti
Prerequisiti
Per seguire in modo proficuo le esercitazioni di laboratorio è necessario saper programmare (ragionevolmente bene) in linguaggio C: bisogna saper scrivere programmi di media lunghezza e sapere usare un compilatore/ambiente di sviluppo a propria scelta. In pratica, è necessario aver seguito il corso di Programmazione (possibilmente avendo anche superato l'esame).
Come si svolge il laboratorio
Le esercitazioni di laboratorio si svolgeranno esclusivamente online. È necessario disporre di un computer su cui è installato l'ambiente di sviluppo che si vuole usare.
Il docente utilizzerà il compilatore gcc in ambiente Linux, ma gli esercizi possono essere svolti con qualunque altro ambiente di programmazione C che supporti lo standard C90 (ANSI C), ad esempio, Code::Blocks, Xcode, MS Visual Studio, ecc.
Le esercitazioni si svolgeranno nel modo seguente: all'inizio di ogni lezione il docente farà una breve introduzione (20-30 minuti al massimo) sull'argomento trattato e i problemi da risolvere. Gli esercizi riguarderanno in generale quanto visto nelle lezioni di teoria (in certi casi potremmo dover anticipare argomenti trattati in lezioni di teoria successive); in ogni caso suggerisco di riguardare quanto fatto in aula prima di ogni laboratorio.
Durante i laboratori verranno forniti degli scheletri di programmi da completare; potranno essere forniti anche dei file di input oppure dei casi di test per verificare la presenza di errori (non la loro assenza!). A questo punto ciascuno completerà i programmi individualmente o in gruppo (purtroppo la modalità online non favorista le interazioni fra studenti che sarebbero molto utili). Il docente e i tutor saranno a disposizione per fornire suggerimenti e aiutare a risolvere i problemi.
Al termine di ogni laboratorio verranno fornite delle possibili soluzioni. Si tenga presente che in generale non esiste una unica soluzione "corretta", per cui soluzioni corrette ed efficienti alternative sono benvenute.
Bibliografia
Il modulo di laboratorio non richiede alcun testo specifico; di seguito vengono suggeriti alcuni libri per chi voglia approfondire.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford
Stein, Introduzione agli
Algoritmi e Strutture Dati 3/ed, McGraw-Hill, 2010, ISBN:
9788838665158
Questo è il libro adottato nei moduli di teoria; in laboratorio implementeremo alcuni degli algoritmi più importanti descritti nel libro.
-
Brian W. Kernighan and Dennis M. Ritchie,
The C Programming Language, Second Edition
Prentice Hall, Inc., 1988.
ISBN 0-13-110362-8 (paperback), 0-13-110370-9 (hardback).
Il libro per eccellenza sul linguaggio C scritto dai suoi inventori: chiaro, sintetico e autorevole. Chiunque sia interessato alla programmazione dovrebbe leggere questo libro come esempio di come andrebbe scritta una buona documentazione tecnica.
Altri libri di consultazione
-
Jeff Erickson, Algorithms
(liberamente scaricabile in formato PDF)
Questo libro copre gli argomenti di teoria che verranno trattati a lezione. Sebbene sia un po' più leggero del Cormen et al, soprattutto per quanto riguarda la parte formale/matematica, è comunque un libro interessante ricco di aneddoti. Cosa non trascurabile, è liberamente disponibile in formato PDF sulla pagina Web dell'autore.
-
Jon Bentley, Programming Pearls, 2nd edition,
Addison-Wesley, 2000, ISBN 0-201-65788-0.
Non è un classico libro di testo sugli algoritmi; il volume nasce infatti come una raccolta di articoli che l'autore ha scritto nel corso degli anni per una rubrica sulla rivista Communications of the ACM. Il libro affronta diversi temi algoritmici e non (testing e debugging, problemi di ordinamento e ricerca, strutture dati avanzate, come ridurre spazio e tempo dei programmi, ecc.), con uno stile informale e prendendo spunto da esperienze pratiche dell'autore. Lo consiglio a tutti coloro che sono appassionati alla materia; anche coloro che non lo sono troveranno comunque molte informazioni utili.
-
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi
e strutture dati 2/ed, McGraw-Hill, 2008, ISBN: 978 88 386
64687 [errata corrige]
Buon libro in italiano sugli algoritmi.
-
Alan A. Bertossi, A. Montresor, Algoritmi e
strutture di dati (terza edizione), CittàStudi, 2014, ISBN:
9788825173956 [Errata Corrige]
Un altro valido libro in italiano sugli algoritmi.
-
Moreno Marzolla, Esercizi di Algoritmi e Strutture
Dati
[odt]
[PDF]
Questa dispensa contiene esercizi (con soluzioni) che ho proposto in passato in un altro corso di algoritmi e strutture dati da me tenuto. Sebbene gli esercizi non siano rappresentativi di quelli proposti dai docenti dei moduli di teoria, ho reso comunque disponibile questa dispensa nella speranza che possa essere utili.
La dispensa Esercizi di Algoritmi e Strutture Dati di Moreno Marzolla è distribuito con Licenza Creative Commons Attribuzione - Condividi allo stesso modo 4.0 Internazionale
Altro materiale
- Corso di Algoritmi e Strutture Dati, prof. Alberto Montresor, Università di Trento
- Free Online Algorithms and Data Structures Books
- Per chi desidera cimentarsi con esercizi più complicati suggerisco Cracking the Coding Interview
- Alcuni problemi algoritmici interessanti tratti da competizioni internazionali: onlinejudge.org
Orario delle lezioni
| Classe A (prof. Margara) | Venerdì 09:00—12:00, Online |
|---|---|
| Classe B (prof. Maniezzo) | Giovedì 15:00—18:00, Online |
Modalità d'esame
Salta al calendario delle lezioni
L'esame del modulo di laboratorio consiste nello svolgimento di un progetto che si compone di norma di 1-2 esercizi (dipende dal grado di difficoltà degli stessi); ciascun esercizio richiede la progettazione e realizzazione in linguaggio C (standard ANSI C/C90) di un algoritmo per risolvere un semplice problema, simile a quelli visti in laboratorio.
Le specifiche del progetto saranno assegnate alla fine del corso, dato che potranno riguardare anche gli ultimi argomenti trattati. Le specifiche resteranno le stesse per tutto l'Anno Accademico corrente (2020/2021).
Non verrà assegnato un voto, ma la consegna di un progetto corretto è condizione necessaria per accedere alla prova scritta. Nel caso di consegna insufficiente (uno o più programmi non funzionanti o gravemente inefficienti) sarà possibile modificare il proprio codice e riconsegnare. Si presti attenzione che in caso di riconsegna non è garantito che la correzione potrà essere effettuata in tempo per l'ammissione all'appello immediatamente successivo.
Tutte le consegne verranno confrontate con quelle già effettuate da altri studenti mediante appositi software antiplagio. Indici di similitudine troppo alti potranno produrre una valutazione insufficiente d'ufficio con conseguente necessità di consegnare un nuovo progetto riscritto da zero.
I programmi dovranno essere consegnati tramite la piattaforma Virtuale. Solo i programmi corretti ed efficienti consegnati almeno 10 giorni lavorativi prima della data di un appello d'esame consentono di sostenere la prova scritta in quell'appello e in tutti i successivi, anche di anni accademici diversi.
Materiale didattico
Nota: Il materiale didattico non sostituisce né i libri di testo né la frequenza di lezioni e laboratori. Il materiale sarà soggetto ad aggiornamenti periodici.
| Data | Classe A (prof. Margara) [Teams gruppo A] [Virtuale gruppo A] |
Classe B (prof. Maniezzo) [Teams gruppo B] [Virtuale gruppo B] |
|---|---|---|
| Gio 25/2 15:00 | Introduzione al corso [ODP] [PDF] vecsum.c Asserzioni e invarianti [ODP] [PDF] [Video parte 1] [Video parte 2] |
|
| Ven 26/2 09:00 | Introduzione al corso [ODP] [PDF] vecsum.c Asserzioni e invarianti [ODP] [PDF] [Video parte 1] [Video parte 2] |
|
| Gio 4/3 15:00 | Breve ripasso del linguaggio C [ODP] [PDF] |
|
| Ven 5/3 09:00 | Breve ripasso del linguaggio C [ODP] [PDF] |
|
| Gio 11/3 15:00 | Osservazioni sul primo laboratorio [ODP] [PDF] |
|
| Ven 12/3 09:00 | Osservazioni sul primo laboratorio [ODP] [PDF] |
|
| Gio 18/3 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo B] |
|
| Ven 19/3 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo A] |
|
| Gio 25/3 15:00 |
Attenzione: il codice è stato leggermente aggiornato
rispetto alla versione inizialmente pubblicata.
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo B] |
|
| Ven 26/3 09:00 |
Attenzione: il codice è stato leggermente aggiornato
rispetto alla versione inizialmente pubblicata.
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo A] |
|
| Gio 1/4 15:00 | No laboratorio (vacanze di Pasqua) | |
| Ven 2/4 09:00 | No laboratorio (vacanze di Pasqua) | |
| Gio 8/4 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo B] |
|
| Ven 9/4 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo A] |
|
| Gio 15/4 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo B] |
|
| Ven 16/4 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo A] |
|
| Gio 22/4 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo B] |
|
| Ven 23/4 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo A] |
|
| Gio 29/4 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo B] |
|
| Ven 30/4 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo A] |
|
| Gio 6/5 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo B] |
|
| Ven 7/5 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale gruppo A] |
