Laboratorio di Algoritmi e Strutture Dati
Laurea in Ingegneria e Scienze Informatiche, Università di Bologna, AA 2023/2024
Avvisi
Salta al programma e libri di testo
- 28/3/2024
- Sono disponibili alcuni alcuni esercizi extra richiesti da alcuni studenti del corso.
- 6/2/2024
- 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 (Classe A, Classe B), corso di laurea in Ingegneria e Scienze Informatiche, AA 2023/2024, Università di Bologna.
Il modulo di teoria è tenuto dai prof. Luciano Margara (classe A) e Vittorio Maniezzo (classe B).
I moduli di laboratorio sono tenuti dai prof. Moreno Marzolla e Chiara Ceccarini.
I tutor per il laboratorio sono:
Prerequisiti
Per seguire in modo proficuo il laboratorio di Algoritmi e Strutture Dati è necessario avere una buona conoscenza del linguaggio C: occorre saper usare un compilatore/ambiente di sviluppo a propria scelta per scrivere programmi di media complessità. In pratica, è necessario aver seguito il corso di Programmazione e superato il relativo esame.
Come si svolge il laboratorio
All'inizio di ogni laboratorio il docente farà una breve introduzione (20-30 minuti al massimo) sull'argomento trattato e i problemi da risolvere. Gli esercizi riguarderanno 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 programmi parzialmente implementati 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, lavorando individualmente o in gruppo. Il docente e i tutor saranno a disposizione per fornire suggerimenti e aiutare a risolvere i problemi.
Nei giorni successivi il laboratorio verranno fornite delle possibili soluzioni. Si tenga presente che in generale non esiste una unica soluzione "corretta", per cui soluzioni alternative sono benvenute (purché corrette ed efficienti).
Il docente utilizzerà il compilatore gcc in ambiente Linux, ma gli esercizi possono essere svolti con qualunque ambiente di sviluppo che supporti lo standard C89/C90 (ANSI C), ad esempio, Code::Blocks, Xcode, MS Visual Studio, ecc.
Personalmente consiglio l'uso di un compilatore a riga di comando:
- In ambiente Windows si può usare MinGW-w64, che è già installato sulle macchine del laboratorio 2.2.
- In ambiente MacOSX si può usare Xcode e tramite questo installare i Command Line Tools che includono un compilatore a riga di comando (il comando gcc in realtà invoca il compilatore clang, che comunque è un ottimo compilatore paragonabile a gcc).
- Come editor si possono usare jEdit (multipiattaforma Linux/Windows/MaxOSX) oppure Notepad++ (solo per Windows, già installato sulle macchine del laboratorio 2.2).
- Uno dei problemi più insidiosi della programmazione in C riguarda l'uso corretto della memoria (evitare memory leak, evitare accessi out-of-bound agli array, assegnare un valore alle variabili prima di usarle, ecc.). In ambiente Unix esiste il programma valgrind che è in grado di rilevare una ampia gamma di errori; purtroppo tale software non è disponibile per Windows. Una alternativa sembra essere Dr. Memory, che è libero e gratuito per Windows, Linux, e MacOSX. Tuttavia non l'ho mai usato per cui non posso garantire.
A causa dell'enorme varietà di combinazioni di sistema operativo/ambiente di sviluppo, è impossibile fornire assistenza alla configurazione del software. Come scritto sopra, non si impone l'uso di un ambiente di sviluppo specifico, ma si assume che gli studenti sappiano usare il proprio sistema secondo i requisiti del corso. È comunque disponibile una guida alla configurazione di Code::Blocks, Visual Studio e uso della riga di comando a cura del docente e dei tutor.
Lbri
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford
Stein, Introduzione
agli Algoritmi e Strutture Dati 3/ed, McGraw-Hill,
2010, ISBN: 9788838665158.
Libro adottato nel modulo di teoria; in laboratorio implementeremo alcuni degli algoritmi descritti qui. -
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 manuale di riferimento del linguaggio C scritto da chi ha inventato il linguaggio. Può essere sostituito con qualunque libro di programmazione C sia stato adottato nel corso di Programmazione. -
M. Marzolla, Programmazione: breve guida di stile
Lo studio di questa dispensa è obbligatorio: contiene alcune regole a cui attenersi per la scrittura di codice C, in particolare per i progetti finali. - Guida alla configurazione di Code::Blocks, Visual Studio e uso della riga di comando, a cura di Nicolas Farabegoli, Filippo Benvenuti, Michele Monti, Moreno Marzolla.
Altri testi di consultazione
I libri seguenti non sono necessari per il corso, ma potrebbero interessare chi vuole approfondire.
-
Jeff Erickson, Algorithms (liberamente
scaricabile)
Copre gli argomenti di teoria. È più accessibile rispetto al Cormen et al., ed è ricco di aneddoti che rendono la lettura piacevole. Liberamente scaricabile in formato PDF dalla pagina Web dell'autore. -
Pat Morin, Open Data Structures (liberamente
scaricabile)
Un altro libro valido disponibile gratuitamente. -
Jon Bentley, Programming Pearls, 2nd edition,
Addison-Wesley, 2000, ISBN 0-201-65788-0.
Non è un libro di testo vero e proprio, ma una raccolta di articoli che l'autore ha scritto per una rubrica sulla rivista Communications of the ACM. Il libro spazia argomenti diversi (testing e debugging, problemi di ordinamento e ricerca, strutture avanzate, ecc.) con uno stile informale e prendendo spunto da esperienze pratiche dell'autore. Lo consiglio a tutti coloro che sono interessati a questo corso. -
Steve McConnell, Code Complete: A
Practical Handbook of Software Construction, Second
Edition, Microsoft Press 2004, ISBN 978-0735619678 [online
su archive.org]
Libro consigliatissimo che contiene una trattazione approfondita delle buone pratiche di programmazione. Non fa riferimento ad un linguaggio in particolare, anche se presenta frammenti di codice in C/Java e Visual Basic. -
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 assegnato in un corso di Algoritmi e Strutture Dati da me tenuto anni fa. Sebbene gli esercizi non siano rappresentativi di quelli proposti all'esame di questo corso, metto a disposizione la dispensa nella speranza che possa essere utile. 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
- Alcuni problemi algoritmici interessanti tratti da competizioni internazionali: onlinejudge.org
Orario dei laboratori
| Lab Classe A | Giovedì 15:00—18:00, lab 2.2 + aula 2.11 |
|---|---|
| Lab Classe B | Venerdì 09:00—12:00, lab 2.2 |
Modalità d'esame
Salta al calendario delle lezioni
L'esame del modulo di laboratorio consiste nello svolgimento di un un esercizio in cui si richiede la progettazione e realizzazione di un algoritmo in linguaggio C (standard ANSI C/C89/C90, sono essenzialmente la stessa cosa). Non saranno accettati programmi scritti in C99.
A titolo di esempio si può prendere visione di un progetto di anni precedenti. Non c'è alcuna garanzia che il tipo di progetto o il livello di difficoltà rimangano gli stessi.
La specifica del progetto viene resa disponibile alla fine del corso sulla piattaforma Virtuale. La specifica resta la stessa per tutto l'Anno Accademico corrente (2023/2024).
Il progetto va svolto individualmente. I programmi potranno essere consegnati in qualunque momento, fino a circa 10 giorni prima di ciascuna prova scritta.
Non viene assegnato un voto, ma la consegna di un progetto corretto è condizione necessaria per accedere alla prova scritta. Una volta ottenuta una valutazione positiva del progetto, è possibile presentarsi ad uno qualunque degli appelli scritti, anche in anni accademici successivi; infatti i progetti valutati positivamente non scadono e quindi non vanno riconsegnati.
Nel caso di progetto insufficiente sarà possibile modificare il codice e riconsegnare. In caso di riconsegna non è garantito che la correzione venga effettuata in tempo per l'ammissione all'appello immediatamente successivo.
Tutte le consegne verranno confrontate tra loro mediante software antiplagio. Indici di similarità troppo elevati comporteranno l'annullamento della consegna e l'assegnazione di un nuovo progetto, con specifiche diverse, da svolgere da zero. L'annullamento riguarderà entrambi gli estremi della copiatura (cioè sia chi copia, sia chi fa copiare).
Materiale didattico
Nota: Il materiale didattico non sostituisce né i libri di testo né la frequenza di lezioni e laboratori. Il materiale verrà aggiornato periodicamente.
| Data | Classe A (prof. Margara) [Virtuale classe A] | Data | Classe B (prof. Maniezzo) [Virtuale classe B] |
|---|---|---|---|
| 22/2 15:00 |
|
23/2 09:00 |
|
| 29/2 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe A]. Il test non è obbligatorio e non viene valutato ai fini dell'esame; serve a voi per avere un riscontro immediato sulla correttezza delle soluzioni, a me per capire quante persone stanno provando gli esercizi. |
1/3 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe B]. Il test non è obbligatorio e non viene valutato ai fini dell'esame; serve a voi per avere un riscontro immediato sulla correttezza delle soluzioni, a me per capire quante persone stanno provando gli esercizi. |
| 7/3 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe A] |
8/3 09:00 | La lezione non si è tenuta a causa di uno sciopero del personale di portineria. |
| 14/3 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe A] |
15/3 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe B] |
| 21/3 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe A] |
22/3 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe B] |
| 27/3 | No lezione (Pasqua) | 28/3 | No lezione (Pasqua) |
| 4/4 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe A] |
5/4 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe B] |
| 11/4 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe A] |
12/4 | No lezione (Lab occupato da Olimpiadi del Problem Solving) |
| 18/4 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe A] |
19/4 | Lezione annullata a causa di impegni istituzionali della docente. |
| 25/4 | No lezione (ponte 25 Aprile) | 26/4 | No lezione (ponte 25 Aprile) |
| Fogli bianchi | Fogli bianchi |
Esercizi extra
I seguenti esercizi sono stati richiesti da alcuni studenti.
