Laboratorio di Algoritmi e Strutture Dati
Laurea in Ingegneria e Scienze Informatiche, Università di Bologna, AA 2022/2023
Avvisi
Salta al programma e libri di testo
- 16/2/2023
- 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 2022/2023, Università di Bologna.
I tutor per il laboratorio sono:
Il modulo di teoria è tenuto dai prof. Luciano Margara (classe A) e Vittorio Maniezzo (classe B).
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 (istruzioni per l'installazione) o MinGW-w64. MinGW è 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).
- Esistono servizi online tramite i quali è possibile provare la compilazione di programmi con gcc o clang senza necessità di installarli localmente: onlinegdb.com, rextester.com, repl.it. Tuttavia non consiglio l'uso di tali servizi perché offrono funzionalità limitate e non consentono di provare programmi anche mediamente sofisticati.
- 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.
Bibliografia
Per la parte di teoria, il libro già consigliato dai proff. Maniezzo e Margara:
-
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.
Sulla programmazione C va bene quello usato nel corso di Programmazione, oppure il classico "Kernighan e Ritchie":
-
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: chiaro, sintetico e autorevole. Non è però adatto ai principianti assoluti (ma non dovrebbe essere il nostro caso, visto che chi frequenta il corso di algoritmi ha già seguito il corso di programmazione). - Guida alla configurazione di Code::Blocks, Visual Studio e uso della riga di comando, a cura di Nicolas Farabegoli, Filippo Benvenuti, Moreno Marzolla.
Sulle buone pratiche per la scrittura del codice:
-
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. -
Steve McConnell, Code Complete: A
Practical Handbook of Software Construction, Second
Edition, Microsoft Press 2004, ISBN 978-0735619678 [online
su archive.org]
Un libro consigliato a coloro che desiderano una trattazione più 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. -
Brian W. Kernighan, Philip J. Plauger, The Elements of Programming Style 2nd ed.,
MacGraw-Hill, 1978, ISBN 0-07-034207-5 [online su archive.org]
Un libro molto datato, che menziono solo perché viene considerato il punto di riferimento di tutte le guide di programmazione. C'è anche un video di Brian Kernighan che parla di questo argomento.
Altri libri di consultazione
-
Jeff Erickson, Algorithms (liberamente
scaricabile)
Libro molto valido che copre gli argomenti di teoria. È più accessibile rispetto al Cormen, ed è ricco di aneddoti interessanti che rendono la lettura piacevole. Cosa non trascurabile, il libro è liberamente disponibile in formato PDF sulla pagina Web dell'autore. -
Pat Morin, Open Data Structures (liberamente
scaricabile)
Un altro valido libro sugli algoritmi, disponibile gratuitamente. -
Jon Bentley, Programming Pearls, 2nd edition,
Addison-Wesley, 2000, ISBN 0-201-65788-0.
Non è un libro di testo vero e proprio, mauna 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 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 si appassionano a questa materia. -
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 delle lezioni
| Classe B (prof. Maniezzo) | Giovedì 15:00—18:00, lab 2.2 |
|---|---|
| Classe A (prof. Margara) | 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 progetto composto da un esercizio in cui si richiede la progettazione e realizzazione di un algoritmo in linguaggio C (standard ANSI C/C89/C90). Non saranno accettati programmi scritti in C99.
Non verrà assegnato un voto, ma la consegna di un progetto corretto è condizione necessaria per accedere alla prova scritta, anche in anni accademici successivi (i progetti valutati positivamente non scadono).
Le specifiche del progetto vengono assegnate alla fine del corso, e rese disponibili tramite la piattaforma Virtuale. Le specifiche restano valide per tutto l'Anno Accademico corrente (2022/2023).
A titolo di esempio, vengono rese disponibili le specifiche del progetto dell'anno accademico precedente. Non si garantisce che il tipo di progetto o il livello di difficoltà restino gli stessi anche per il presente anno accademico.
Il progetto va svolto individualmente. I programmi potranno essere consegnati in qualunque momento, fino a circa 10 giorni prima di ciascuna prova scritta.
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 B (prof. Maniezzo) [Virtuale classe B] |
Data | Classe A (prof. Margara) [Virtuale classe A] |
|---|---|---|---|
| 23/2 15:00 |
|
24/2 09:00 |
|
| 2/3 15:00 |
Guida alla configurazione di Code::Blocks, Visual Studio e uso della riga di comando
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe B] |
3/3 09:00 |
Guida alla configurazione di Code::Blocks, Visual Studio e uso della riga di comando
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe A] |
| 9/3 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe B] |
10/3 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe A] |
| 16/3 15:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe B] |
17/3 09:00 |
Siete invitati a completare il test di autovalutazione sulla piattaforma "Virtuale" [Virtuale classe A] |
