Algoritmi e strutture dati e Laboratorio

Corso di laurea triennale in INFORMATICA

Docenti: M. Torelli, S. Aguzzoli

Indicazioni sul programma e sulle modalità d'esame

 

Per il      Corso di laurea magistrale in INFORMATICA PER LA COMUNICAZIONE

e il           Corso di laurea triennale in INFORMATICA PER LE TELECOMUNICAZIONI

 

vale lo stesso programma (senza il progetto. Per l’esame, orale, iscriversi via SIFA e poi concordare via mail torelli@dsi.unimi.it data e ora)

ma si possono saltare o dar solo una rapida occhiata ai capitoli o paragrafi relativi a

 

8.4 Bucket sort

9 Statistiche d’ordine

10.3 Realizzazione di puntatori

13 Alberi rosso-neri

18 B-alberi

 

 

 


Indicazioni per l'esame

Si ricorda l'inderogabile necessità di iscriversi all'appello d'esame, presso i terminali del SIFA o via rete, seguendo la procedura informatizzata, entro il termine previsto (attualmente una settimana prima della data dell'appello). Eventuali disguidi vanno fatti presenti alla Segreteria di via Comelico, sempre entro i termini, in modo da provvedere prima della scadenza.

NON RISPONDERO' A MESSAGGI CHE CHIEDONO DI ISCRIVERSI ALL'ESAME A TERMINI SCADUTI.

La data dell'appello indicata è quella del giorno in cui il progetto d'esame viene reso pubblico (tramite pubblicazione in rete). L'esame consiste nella discussione del progetto e nell'esame orale. Non c'è una prova scritta, anche se è capitato che nella maschera d'iscrizione comparisse la dizione "esame scritto" (o anche altre più fantasiose: ignorarle e preoccuparsi solo della data corretta). Il progetto riporterà indicazioni sulle modalità di consegna e le date previste per la discussione e l'orale (in genere alcuni giorni dopo la data di consegna).

L'esame orale e la discussione del progetto devono essere svolti nell'appello cui il progetto si riferisce: non è consentito svolgere un progetto e fare l'orale in un appello successivo.

 Date degli appelli (giorno di pubblicazione del progetto d'esame): si veda il Sito del Coordinamento Didattico.

  


 

Si riportano di seguito alcune indicazioni generali e i principali argomenti effettivamente svolti a lezione negli anni precedenti, seguendo l'ordine del testo [2]). 

 

Si suggerisce per prima cosa di ripassare logaritmi e potenze (§3.2 di [2]): è indispensabile saper calcolare approssimativamente log2 1.000.000. Questo calcolo serve per esempio per stabilire quanti bit occorrono per indirizzare 1MB, o quanto dev'esser grande lo stack per Quicksort. Partire da 210 ≈ 1000 = 103.

E' essenziale capire i concetti importanti (purtroppo non è facile caratterizzare quelli importanti: le lezioni servono soprattutto a quello!). E' necessario aver capito la traccia delle dimostrazioni e l'idea di base dei programmi (utilizzare le figure e gli esempi!). Non è necessario invece memorizzare tutti i passaggi delle dimostrazioni.

I primi 18 capitoli di [2] sono stati svolti quasi integralmente, salvo il capitolo 5, i cui contenuti sono coperti da altri corsi e il capitolo 14, solo accennato. Parti delle appendici A, B e C sono da usare come riferimento: occorre conoscere i risultati ivi riportati, per capire l’analisi di certi algoritmi. Sono state spiegati in dettaglio e sono importanti i §§B.4 e B.5 (si vedano anche gli appunti [6]) e il risultato del "paradosso del compleanno" al §5.4.1. Per la definizione di macchina RAM e RASP e i criteri di costo uniforme e logaritmico è opportuno consultare [1] oppure [5]. Non è richiesta la dimostrazione del paragrafo 4.4, ma l'enunciato del teorema 4.1 dev'essere noto. I risultati degli esercizi 4.4-2 e 4.4-3 sono utili. Si devono conoscere i numeri di Fibonacci e la loro relazione di ricorrenza (si veda il paragrafo 3.2, alla fine).

Si richiama l'attenzione sui paragrafi 6.3 e 6.5, dato che la tecnica di costruzione di uno heap, la relativa complessità e la nozione di "coda con priorità" sembrano sconosciute a molti studenti. Si vedano anche le note [6]. Dell'analisi del caso medio di Quicksort (§ 7.4.2) è richiesto soltanto il risultato, mentre sono importanti le considerazioni dei problemi 7-4 (specialmente il punto c: si consulti eventualmente [3]) e 7-5. Per il capitolo 8, si cerchi di avere chiare le condizioni per le quali gli algoritmi di ordinamento descritti sono effettivamente lineari in n.

Nel capitolo 9, la selezione in tempo lineare nel caso peggiore (§ 9.3) non è richiesta, ma è utile conoscere il risultato. Nel capitolo 10 segnaliamo in particolare il §10.4. Per il capitolo 11, non sono richieste le dimostrazioni dei teoremi 11.2, 11.6 e 11.8 (ma gli enunciati sì), né i §§ 11.3.3 e 11.5. Il paragrafo 12.1 è importante (è evidente sin dal titolo), eppure spesso la definizione di albero di ricerca data all'esame è sbagliata! Del paragrafo 12.4 è richiesta la sola introduzione e il risultato del teorema 12.4. Vanno conosciuti anche i risultati dei problemi 12-2 e 12-4.

Per una comprensione più agevole degli alberi rosso-neri (capitolo 13) si possono considerare gli alberi 2-3-4, come fa [3] oppure guardare insieme i B-alberi al capitolo 18. Si può omettere il §13.4 come pure il capitolo 14 (ma il §14.3 potrebbe fornire suggerimenti per qualche progetto d’esame).

Del capitolo 15 abbiamo svolto solo le prime tre sezioni. La dimostrazione della correttezza dell'algoritmo di Huffman non è richiesta, ma si vedano gli appunti Codici e linguaggi. Il §16.4 e il teorema 16.11 sono importanti: per il teorema, si veda la versione nelle dispense [5] al §12.3 e negli appunti Problemi su insiemi, matroidi e algoritmi ingordi. Abbiamo saltato i §§17.3 e 17.4.2 e il §18.4, come pure i capitoli 19 e 20. Per il capitolo 21 abbiamo saltato il §21.2 mentre è utile conoscere la funzione di Ackermann (§21.4, consultare eventualmente [4]) e il suo impiego nella valutazione della complessità degli algoritmi per insiemi disgiunti, ma non la dimostrazione.

Dei capitoli 22 e 23 è necessario conoscere i concetti principali (come rappresentare i grafi, come si differenzia la visita in ampiezza da quella in profondità, che cos'è un albero di copertura minimo e come costruirlo). Abbiamo accennato all’algoritmo di Dijkstra (§24.4): per capire questi algoritmi è spesso sufficiente esaminare le figure del testo (senza trascurare l’analisi della complessità), si vedano anche gli appunti Una guida alla visita di grafi.

 

Del capitolo 34 del testo abbiamo accennato ai problemi P, NP e NP-completi (si veda l'introduzione, §34.1) ed esemplificato i problemi del § 34.5 (esaminando solo le dimostrazioni più semplici). Anche del capitolo 35 abbiamo visto i primi 3 paragrafi senza le dimostrazioni più complesse.

 


Bibliografia

[1] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, 1974.

[2] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati, McGraw-Hill, II edizione 2005.

[3] R. Sedgewick, Algoritmi in C/C++, Addison-Wesley, 1993 e 2002.

[4] A.J. Kfoury, R.N. Moll, M.A. Arbib, A programming approach to computability, Springer, 1982 oppure

            http://www.dis.uniroma1.it/~ausiello/InfoTeoRMvo/main.pdf

[5] A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi (Dispense del corso), reperibili alla libreria C.L.U.E.D. o presso copisterie e scaricabili da http://homes.dsi.unimi.it/~goldwurm/algo/

[6] M. Torelli, Appunti per il corso di Algoritmi e strutture dati

 


Indicazioni per il progetto e modalità di consegna

Si veda il sito del Laboratorio di Algoritmi e Strutture Dati


 


 Ultima revisione: 10/6/2010