Dipartimento di Informatica e Scienze dell'Informazione

Corso di Algoritmi e Strutture Dati + Laboratorio - a.a. 1999/00

Modalita` di esame

• L'esame consiste di 3 prove: labo (= prova in laboratorio), scritto, orale.
• Scritto e labo sono indipendenti (possono essere superati in sessioni differenti e in un qualunque ordine); per presentarsi all'orale bisogna, invece, aver superato labo e scritto.
• Scritto e labo, una volta superati, rimangono validi fino a febbraio.
• Per motivi organizzativi, sia per lo scritto che per il labo e` necessario PRENOTARSI.
  Sempre per motivi organizzativi, chi si prenota e poi cambia idea, o non puo` presentarsi, deve fare il possibile per avvertire, al piu' presto.

Labo

Non si possono consultare libri, appunti, persone...., tranne le dispense fornite e/o il Kerninghan-Ritchie e/o il Darnell-Margolis (le persone che sono abituate ad usare un altro manuale per il C e vogliono usarlo durante la prova, devono, qualche giorno prima della prova, venire da noi col manuale, cosi' vediamo se e` possibile).

La prova e' organizzata a "passi" o "scalini". Nel testo verra' indicato quali sono gli scalini necessari per raggiungere la sufficienza (15). Il voto massimo della prova e' 30.

Per semplificare la fase di correzione: bisogna usare C (standard) , non C++ o altro.

Scritto

Durante lo scritto non e` permesso consultare libri, appunti, persone,.... (questo perche` gli esercizi sono semplici variazioni di cose viste nel corso).

Orale

1. verificare se eventuali errori allo scritto sono frutto di distrazione e simili, oppure corrispondono ad un effettivo "buco" nella preparazione;
2. verificare la preparazione su argomenti che non hanno trovato posto nello scritto e nel labo.

Provando a precisare il tipo di domande, conviene riferirsi alle dipense.

ATTENZIONE: non e` facile dare una descrizione completa; quello che segue ha solo valore di esempio.

Prima puntata.
Su questa parte, le domande NON sono del tipo:
-- il passaggio dei parametri nelle procedure oppure il for del C
ma piuttosto:
-- prendiamo un esempio e spieghiamo cosa succede.

Seconda puntata - procedure ricorsive
Qui le domande sono del tipo:
-- raccontiamo un po' mergesort, spieghiamo come funziona ( e valutiamo valutiamo la complessita` -- vedi oltre).

Seconda puntata - tipi di dato (incluse: liste, visite alberi, implementazione di insiemi tramite liste, array, tries, alberi di ricerca, hashing).
Qui ci possono essere domande del tipo:
-- definizione di algebra eterogenea ed esempi. spiegazioni,...
-- definizione di alberi k-ari ed esempi. spiegazioni,...
domande del tipo:
-- data questa def. induttiva, qual'e` la successione di insiemi che viene fuori ?
e domande del tipo:
-- spiegare la tecnica di hashing, gli alberi di ricerca,...
-- spiegare la visita in ampiezza / in profondita` di un albero ....

Terza e quarta puntata - Parte di complessita`
Qui ci possono essere:
domande sulla parte "definizioni":
-- def di T(...); def. di di O( ...); ...
e domande del tipo:
-- dato un algoritmo (visto nel corso, o simile) fare i conti di complessita`.

Quarta puntata: tecniche di programmazione.
Qui le domande sono del tipo:
-- spiegare lo schema del divide et impera collegandolo agli esempi visti;
-- spiegare lo schema della programmazione dinamica su un esempio.

Per finire, qualche osservazione generale (sempre sull'orale).
Tranne qualche piccola eccezione (esempio: dimostrazione di correttezza di mergesort, algoritmo per il problema dello zaino, qualche dettaglio sui conti di complessita`) le cose viste sono semplici: non c'e` molto da ricordare o molto da capire. Meglio ancora: sono facili da capire e quindi da ricordare .

Molte cose viste sugli alberi, se ci limitiamo ai "disegni", si possono spiegare ai bambini delle elementari; all'universita` si deve pretendere che si sappia fare il passaggio da "disegno" e formalizzazione. L'analogo vale per il resto; per fare ancora un esempio: a livello intuitivo, O(f) e` l'insieme delle funzioni che "stanno sotto f", pero' se uno si affida a questo, NON riesce a dire che 3n+5 � in O(n); per arrivarci serve la definizione precisa (che poi e` facile); quindi bisogna saperla.
Pero', attenzione a non cadere nell'errore opposto: non serve a niente saper ripetere perfettamente la definizione di O(f) se poi non si sa spiegare, o non si sanno fare degli esempi.