Introduzione agli algoritmi e strutture dati terza edizione pdf

Algoritmi e Strutture Dati Laurea in Informatica per il Management, Università di Bologna, AA 2020/2021

Descrizione del corso, programma e libri di testo

Salta alle modalità d'esame

Questa è la pagina del corso di Algoritmi e Strutture Dati moduli 2/3, corso di laurea in Informatica per il Management, AA 2020/2021, Università di Bologna.

Il modulo 2 è tenuto dal prof. Moreno Marzolla, mentre il modulo 3 è tenuto dal prof. Saverio Giallorenzo.

Programma:

• Complessità ammortizzata degli algoritmi
• Visite di grafi
• Algoritmi divide-et-impera
• Tecniche greedy
• Programmazione dinamica
• Minimum Spanning Tree
• Cammini minimi
• Fondamenti teorici della calcolabilità: macchine di Turing, asserzioni e invarianti

Testo adottato

• 
  Alan A. Bertossi, A. Montresor, Algoritmi e strutture di dati (terza edizione), CittàStudi, 2014, ISBN: 9788825173956 [Errata Corrige]
  

Dispensa di esercizi svolti

Altri testi di consultazione

• 
  Jeff Erickson, Algorithms (liberamente scaricabile in formato PDF)
  Questo libro (in inglese) copre più o meno il programma che svolgeremo a lezione. L'autore lo ha reso liberamente disponibile in formato PDF sulla propria pagina web.
  
• 
  Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati 2/ed, McGraw-Hill, 2008, ISBN: 978 88 386 64687 [errata corrige]
  Questo è un ottimo testo didattico sugli algoritmi e strutture dati, che tratta essenzialmente gli stessi argomenti del libro di Bertossi e Montresor.
  
• 
  Robert Sedgewick, Algoritmi in Java 3/Ed., Pearson. 2003. ISBN 9788871921693
  Questo libro si distingue dagli altri perché descrive gli algoritmi usando Java anziché pseudocodice. Il libro contiene molte figure che facilitano la comprensione degli argomenti. Un limite di questo testo è che tratta gli aspetti legati ai costi asintotici in modo un po' superficiale.
  
• 
  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 è uno dei testi classici sugli algoritmi e le strutture dati. Offre una trattazione approfondita degli argomenti principali ma include molto più materiale rispetto a quanto verrà svolto a lezione. Di conseguenza lo consiglio a coloro che desiderano approfondire gli argomenti, o che cercano un testo autorevole da consultare anche in futuro.
  
• 
  Jon Bentley, Programming Pearls, 2nd edition, Addison-Wesley, 2000, ISBN 0-201-65788-0.
  Questo piccolo libro contiene numerosi esempi tratti da situazioni reali ed esercizi per imparare come sviluppare programmi efficienti. Lo consiglio a tutti coloro che desiderano vedere in che modo le tecniche algoritmiche viste a lezione possono essere usate per risolvere problemi reali.
  

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

Torna in cima alla pagina.

Modalità d'esame

Salta al calendario delle lezioni

L'esame finale consiste in un progetto individuale seguito da un esame orale.

Il progetto include di norma in 4-5 esercizi che richiedono di progettare e realizzare programmi Java efficienti per la risoluzione dei problemi assegnati.

Durante l'anno accademico verranno assegnati tre progetti: uno per la sessione estiva, uno per quella autunnale, e uno per quella invernale. I progetti andranno consegnati indicativamente circa 10 giorni prima del primo appello d'esame di quella sessione (verranno comunicate le date precise di volta in volta). Le specifiche dei progetti saranno rese disponibili circa un mese prima delle scadenze per la consegna.

I progetti sufficienti consentono di sostenere l'orale in uno degli appelli nella sessione d'esami per la quale sono stati consegnati. Ci saranno tre appelli orali nella sessione estiva (giugno/luglio 2021), uno in quella autunnale (settembre 2021) e due per quella invernale (gennaio/febbraio 2022). Nel caso di progetti insufficienti, sarà necessario attendere la sessione d'esami successiva e consegnare le soluzioni dei nuovi progetti che verranno proposti.

L'orale consiste nella discussione dei progetti e in una serie di domande su tutto il programma, in particolar modo gli argomenti di teoria visti a lezione. Potranno essere posti anche dei semplici esercizi sulla complessità o sulle strutture dati da svolgere sul momento. Il voto finale dipenderà in modo preponderante dal risultato della prova orale.

I docenti gestiranno con la massima intransigenza ogni irregolarità. L'esame è un momento ufficiale che va affrontato con la massima serietà. Il voto finale NON è negoziabile (può solo essere rifiutato).

Torna in cima alla pagina.

Calendario delle lezioni

Nota: I lucidi non sostituiscono né il libro di testo né la frequenza alle lezioni. In particolare, studiare su un libro permette di chiarire dettagli che potrebbero essere solo accennati (o mancare del tutto) nei lucidi. I lucidi sono soggetti a modifiche frequenti.

Per approfondire

• Video-esercizio sulle invarianti (soluzione di un esercizio assegnato all'esame di fondamenti di informatica, ing. biomedica; questo argomento viene trattato in modo identico a quanto in questo corso)

Torna in cima alla pagina.