Domande Orale Pagli

Di seguito posto alcune domande fatte all'orale dalla Pagli che avevo raccolto chiedendo in giro:

Preappello - maggio 2014
- dimostrazione dell'es. 4 del compito
- dimostrazione dell'altezza logaritmica degli alberi AVL con gli alberi di fibonacci
- complessità pseudopolinomiale
- rotazioni negli alberi avl dopo l'inserimento

Appelli dell'estate 2014
- Quicksort e quickselect con dimostrazioni al caso medio
- Limite inferiore per la selezione (che è n-1) - argomento fuori del programma per alzare il voto
- Alberi AVL e ABR
- Grafi, visite BFS e DFS
- Grafi DAG
- Teorema fondamentale della ricorsione - la dimostrazione è stata chiesta solo come "ultima spiaggia" a chi non sapeva altro
- NP completezza
- Algoritmi di ordinamento (per confronti e in tempo lineare)

Aggiungo il mio orale, che ho fatto nella sessione di gennaio: mi ha chiesto di parlare della classificazione per complessità dei problemi computazionali, e mi ha lasciato parlare molto, fino a dire tutto quello che si era fatto (definizioni di problema computazionale/decisionale/di ottimizzazione, classi EXP, P, NP, NP-C con definizioni, esempi di problemi di quella classe, riduzione polinomiale, teorema di Levin-Cook, ecc). Poi visto che avevo risposto con una certa sicurezza, ed anche perché ero l'ultimo, mi ha chiesto solo la definizione di complessità pseudo-polinomiale, con riferimento in particolare al problema dello zaino, e mi ha alzato di tre voti (partivo da 23).
Sign In or Register to comment.