Corsi di Laurea

[AndrewRiot]

- Java Collection Framework (struttura, principali scelte progettuali)
- Algoritmo dinamico LCS
- Heap Binari
- Heap Binomiali (definizione, struttura, funzionamento delle principali operazioni)

[mando86]

L'esame di oggi di tecniche di programmazione si è svolto in maniera differente rispetto alle altre volte, il prof Vento ci ha riuniti nel laboratorio e ci ha assegnato un argomento a testa, gli argomenti erano:

Bellmann-Ford - BTree - Radix Sort -HeapSort - LCS

Per ogni algoritmo ci ha chiesto di scrivere tutto quello che ritenevamo opportuno scrivere per spiegarne al meglio il funzionamento scrivendo possibilmente anche lo pseudocodice, inoltre ha chiesto di identificare l'invariante di ciclo e quindi dimostrare la correttezza dell'algoritmo mediante la stessa, poi ci ha richiesto di scrivere la complessità dell'algoritmo e dimostrare perchè usciva in quel modo. Il prof non ci ha dato un limite di tempo, quando ci sentivamo sicuri andavamo lì e ne discutevamo. Dopo aver letto tutto quello scritto, e quindi aver discusso degli eventuali problemi con lui o con il prof Percannella, si passava ad altre domande, tipo le differenze tra algoritmi golosi e programmazione dinamica, domande sugli alberi rosso-neri, o analisi delle complessità di alcuni algoritmi di ordinamento(best case,worst case, average case).
Per le dimostrazioni non sono richiesti tutti i passaggi nel dettaglio, ma bisogna far capire lo stesso tramite il ragionamento perchè la complessità viene in quel modo, oppure perchè si conserva l'invariante di ciclo durante le iterazioni. Come ha detto il prof Vento alla fine del corso dobbiamo chiederci "perchè?" ad ogni cosa che andiamo a studiare, inoltre consiglio anche di studiarvi bene le formule di ricorrenza scritte nel suo libro.
Al momento non mi viene in mente più niente, eventualmente faccio il commit ....... buono studio!!!!!!!!!!!!

[ichigo]

Che dire! Il mio collega ha espresso quasi tutto.

Posso solo dirvi che la prima fase dell'esame è una preselezione, una sorta di filtro, che serve al professore per capire se sapete ragionare sui concetti basilari e li avete chiari in mente.

Quali sono questi concetti?

Ovviamente dovete sapere come funziona l'algoritmo che vi chiede e che tecnica di programmazione è stata usata (divide et impera, programmazione dinamica, algoritmi golosi) per risolvere il problema.

Poi si passa all'analisi dell'algoritmo
1)Correttezza dell'algoritmo (per cui l'invariante di ciclo e principio di induzione matematica)
Inutile ricordarvi, che, se scrivete un ciclo senza aver prima chiara in mente l'invariante, siete sulla cattiva strada e che il principio di induzione matematica è strumento dimostrativo fondamentale sia per la correttezza che per la progettazione (Quandi studiatelo a fondo, il che non significa solo conoscerlo, ma anche saperlo applicare coscientemente).
2)Complessità Computazionale
Per ogni algoritmo dovete sapere ricavare la formula di ricorrenza ed ovviamente da questa calcolare la complessità computazionale (Il prof. apprezzerà se vi rivedete le formule di ricorrenza che stanno sul suo libro, anche perchè se sapete svolgere quelle il 98% delle ricorrenze che si presentano sugli algoritmi studiati è fatta!). Il professore non pretende che sappiate svolgere tutti i passaggi, ma che abbiate capito come si ricava la formula di ricorrenza associata all'algoritmo e come si giunge alla soluzione, se poi sbagliate un conto è poca cosa.

Se superate questa prima fase, in cui il professore è molto disponibile e non solo vi da tutto il tempo che vi serve ma è disposto anche a darvi qualche aiuto per indirizzarvi sulla retta via , il 50% dell'esame è fatto.

Poi si passa all'orale vero e proprio. Cioè una conversazione con il professore (devo dire anche abbastanza tranquilla) in cui si spazia un pò su tutti i concetti del programma. Qui ovviamente dovrete dimostrare aver capito bene gli argomenti studiati e soprattutto di saperci ragionare!

In media l'esame è durato 3 ore (contando che la durata è influenzata molto dalla parte iniziale).

In bocca al lupo!

[voirottto]

I miei colleghi hanno gia dato un'ottima spiegazione sullo svolgimento dell'esame.
Riporto qui le mie domande:
1) LCS (scritta)
2) quando conviene utilizzare heap binari o binomiali
3) proprietà heap binomiali con alcune dimostrazioni
4) complessità computazionale merge sort con formula di ricorrenza
5) tabellina best-worst-average case dei vari algoritmi di ordinamento non lineari e perchè nella pratica si usa il quick sort

[merlincaf]

- Scritto: LCS (ricorsivo, prog. dinamica, complessità, e correttezza)
- Commento dello scritto
- Domande in generale sulla programmazione dinamica e complessità

Altre domande in questo appello:
- Insertion Sort (implementazione in JAVA, complessità, correttezza)
- Ragionamenti sulla complessità e casi best, worst ed avarage degli algoritmi di ordinamento basati sul confronto e motivazioni
- Definizione di invariante di ciclo

[spyre]

- Bubble sort: pseudocodice, correttezza, complessità
- varie domande sulla complessità e la funzione T(n) e il tempo di esecuzione di un algoritmo
- Algoritmo di kruskal (con dimostrazione della sottostruttura ottima e della scelta golosa)
- Approccio goloso

[vikap]

- Bellman Ford (pseudocodice,correttezza, complessità) e alcune possibili varianti
- Heap Binomiali (definizione, proprietà, funzioni principali)
- Definizione e vantaggi degli alberi RB

[matteop]

- Prim (pseudocodice,correttezza, complessità) e paragone con Kruskal ( esempio di esecuzione di entrambi )
- HeapSort (complessità,pseudocodice), funzione di heapify(funzionamento, precondizione)
- Complessità e casi best, worst ed avarage degli algoritmi di ordinamento
- Counting sort (ipotesi sui dati, principio di funzionamento)

[tolérance]

Salve ragazzi

Vorrei ringraziarvi per i vostri chiarimenti sul svolgimento di questo esame, ho un unico dubbio che vorrei che mi chiarite...per la dimostrazione della correttezza di alcuni algoritmi essenziali che abbiamo visto (esempio BFS) , il prof vuole che ci facciamo le dimostrazioni che stanno nel libro che utilizzano l'induzione matematica per dimostrarli passo passo o cosa?

Grazie mille e buon anno a voi!!

[RumpocaZzZ]

Fatto l'esame col Prof. Vento:
Mi ha fatto scrivere sul foglio tutto quello che sapevo del DFS e del CountingSort ( compresa invariante di ciclo e correttezza ).
Poi mi ha fatto domande molto nel dettaglio di entrambi gli argomenti ( proprietà del DFS, differenza col BFS ecc.. )
Heap

[roberunix]

Il prof vi da tutto il tempo per rispondere a due domande:
le mie: prim e heap.

l'orale vero e proprio dura un oretta e le domande spaziano su tutto (oltre quelle assegnate chieste nel dettagli): correttezza, complessità computazionale o anche ad esempio come funziona la partition del quicksort, confronto di quest'ultimo con heap etc..

fatevi molte domande perchè i prof amano molto pizzicare gli argomenti nei dettagli!

[Oceanic'sixth]

- Heap ( di tutto e di più).

[nontrovonomi]

Domanda scritta su Alberi R&B(teoria + Insert e quindi anche InsertFixup) e algoritmo BFS(quanto tempo vogliamo).

Colloquio orale con Percannella sullo scritto: invarianti, perchè si usano i R&B, perchè la complessità dell'inserimento è O(logn)(vedi invariante Caso 1), funzionamento BFS, esempio, proprietà, complessità.

[gianu1988]

Parte scritta: Counting Sort e RBTreeInsert + InsertFixUp
Parte orale: spiegazione e invarianti di ciclo del Counting Sort, perchè nonostante Counting Sort è lineare si usa più spesso QuickSort, dimostrazione complessita computazionale di un algoritmo date le funzioni Tb(n) e Tw(n) (best e worst case), RBTree in generale (perchè si usano al posto dei BST ecc ecc)...

[mrfree]

Esame con il prof. Percannella:
- LCS
- Kruskal

[kekkolett89]

Orale sostenuto con prof. Percannella

-LCS
-Discorso sulla manutenzione degli RBTree + RBTreeInsert + InsertFixUp

[da`]

ma a memoria d'uomo e di donna, hanno mai chiesto le dimostrazioni di cose strano tipo i lemmi propedeutici al Teorema di Correttezza della ricerca in ampiezza....?

[Oceanic'sixth]

No, tranqui. Fatti bene le domande presenti in questa pagina e tutto dovrebbe filare liscio.

[mercurio]

-Heap Binari
-BTree (In particolare Btree_insert)

Fate attenzione alla complessità computazionale perchè non basta dire che $ T(n)=O(tlog_t(n)) $. La complessità vera è $ T(n)=O(k1*tlog_t(n)) + O(k2*log_t(n)) $ dove k1 e k2 sono due costanti che rappresentano la velocità delle operazioni rispettivamente sulla memoria principale e secondaria. Il secondo contributo non è trascurabile perchè la costante k2 >> k1, visto che le operazioni sulla memoria secondaria sono circa 5 ordini di grandezza più lente rispetto a quelle della memoria principale.

[nghuit]

- Prim
- Radix Sort
- complessità della ricerca nei B-Tree (vedi mercurio)