Info Esame [Avallone]


Antodonofrio

Membro attivo
Utente Premium
3 Marzo 2015
28
16
3
#1
Esame: Algoritmi e Strutture Dati, Avallone

Informazioni generali: esame da 6CFU non semplicissimo in alcuni punti, ma comunque fattibile. L'esame consta della sola parte orale e un elaborato facoltativo.

Tempo preparazione: ho preparato l'esame in circa tre settimane, mentre scrivevo la tesi, per partecipare al "preappello" di dicembre. Più o meno il tempo è quello, magari un mese per avere una preparazione molto completa.

Libri e appunti utilizzati: slide del corso, libro di testo reperibile sul forum.

Eventuali difficoltà riscontrate e/o osservazioni personali: le difficoltà generali sono legate probabilmente all'accoppiata slide/libro che in certi punti non sono sufficienti. In alcuni punti non viene spiegato come vengano trovati dei particolari tempi di esecuzione/complessità di alcuni algoritmi, ma il risultato è praticamente buttato lì e dato per assodato. Un argomento un po' ostico è la parte sui grafi, in cui bisogna imparare e dimostrare alcuni teoremi. Un altro magari è quello sulle mediane e le statistiche d'ordine. In ogni caso nessun argomento è infattibile.
Un consiglio che posso dare, specialmente per la parte di algoritmi, è vedere su YouTube i video dei vari algoritmi di sorting per vedere come funzionano in generale
Se viene richiesto un algoritmo, infatti, non è richiesto di scriverlo a memoria, ma di capire ad ogni passo quello che succede, quindi risulta necessario avere un disegno mentale di quello che accade.

Modalità d'esame: il prof. chiama uno studente alla volta e dà un foglio. Se si ha un elaborato lo fa esporre, o al pc o stampato, senza però soffermarcisi troppo, data la valenza di un paio di punti massimo. Non è necessario scrivere una tesina, ma si possono anche solo effettuare dei test, magari con i risultati mostrati su dei grafici e spiegarli oralmente. Dopodiché vengono fatte due domande, non necessariamente legate all'elaborato. da rispondere oralmente con l'ausilio di un foglio. Le domande riguardano tutto il programma svolto, senza però chiedere veramente nello specifico.


Alcune domande sentite all'esame:
-Altezza di un albero rossonero
-Inserimento in un albero rossonero con fixup
-proprietà e invariante di un albero rossonero
-analisi sintattica
-BFS + teoremi
-DFS + teoremi
-Ordinamento topologico
-Heapsort e heap
-algoritmi lineari (Counting Sort, Radix Sort e Bucket Sort) e dimostrazione del numero di confronti
-alberi binari di ricerca con algoritmi di inserimento e cancellazione
-Quicksort
-Teorema dell'esperto
-Splay-trees e dimostrazioni dell'analisi ammortizzata (Lemma 1 e 2)
-Tabelle hash (vari tipi di indirizamenti e hashing universale)
 

Seguici su Facebook