Domande Orale Bernasconi

YmirYmir Posts: 183
Per aiutarci potremmo raccogliere qua le domande...

Appello dell'estate 2014.
Domande a uno che allo scritto aveva 24:
- Parlare del quicksort, scenario al caso ottimo e al caso pessimo, relazione di ricorrenza compresa
- Versione randomizzata del quicksort: quanti passi fa?
- Spiega come ordinare in tempo lineare un array di n elementi con elementi che hanno al massimo valore n^2, usando radix sort e counting sort in un certo modo
- Dimostrare che gli alberi AVL hanno altezza logaritmica
- Come si fa la cancellazione in un albero binario di ricerca?
- Dimostrare che il problema dell'arresto è un problema indecidibile
- Trovare il limite inferiore al problema della ricerca in un array ordinato

Domande a uno che allo scritto aveva 26:
- Dimostrare il teorema fondamentale delle ricorrenze
- Come risolvere con la programmazione dinamica il problema della massima sottosequenza comune?
- Che caratteristica hanno i problemi che si ris olvono con la programmazione dinamica? e col divide et impera?
- Cosa vuol dire che un algoritmo ha complessità pseudopolinomiale? un esempio?

Comments

  • BeagleGBeagleG Posts: 16
    nel mio caso chiese :
    dimostrare il limite inferiore di un algoritmo per confronti per il sorting ovvero che non può ordinare meglio di n lg n
    alberi di Fibonacci
    ordinamento topologico
    problema della fermata
    differenza tra alberi AVL e tab.HASH quando conviene uno oppure l'altro



  • NokiNoki Posts: 5
    Nel mio orale (media 26,5 dai compitini):
    - Problema della Edit Distance, parlarne e risolverlo
    - Studio del caso medio di QuickSort
    - Algoritmo per l'ordinamento topografico e dimostrazione della correttezza
  • bongi23bongi23 Posts: 38
    Io arrivavo con 30 al secondo scritto della sessione estiva, le domande furono le seguenti:
    - Dimostrazione del master theorem
    - Cicli hamiltoniani
    - Parlare in generale delle classi di complessità P ed NP
    Se non ricordo male mi chiese anche qualcosa sugli heap e sulla complessità pseudopolinomiale.
  • YmirYmir Posts: 183
    edited June 2016
    (materiale non mio)
    S2ePNn1.jpg
    zEQGNmp.jpg
  • YmirYmir Posts: 183
    Cito
    -Limite inferiore ordinamento per confronti
    -Parli dell'heap sort
    -Dimostrazione complessità al caso medio inserimento/modifica nelle tabelle hash con indirizzamento aperto
    -Esempio di Algo su grafi che usa una PQ (Dijkstra)
    -Dimostrare che la CLIQUE è NP-Completo
    -Analisi al caso medio del QuickSort
    -Dimostrare che il problema dell'arresto non esiste (è indecidibile)
    -Ordinamento DAG, come si calcola.
    -Algoritmo di Kruskal: cos'è, correttezza e complessità.
    -Esempio di problema in cui il greedy invece non dà l'ottimo->prob. Zaino: complessità pseudopolinomiale (spiegare perché). La relativa versione decisionale (sì o no) è in NP-Completo, esibire certificato polinomiale.
    -Dimostrare teorema fondamentale delle ricorrenze.
    -Dimostrazione altezza logaritmica alberi AVL
    -Come si fa cancellazione in un AVL
    -Esempio di problema in cui non è necessario leggere tutto l'input-> Ricerca binaria: dimostrare che è ottima.
    -Dimostrazione correttezza algoritmo di Dijkstra (dire quali sono i passi della dimostrazione e iniziarla. E parte finale)
    -Esempio di problema NP-Completo e cosa significa.
  • Bit_0IBit_0I Posts: 1
    edited July 5
    Orale del 05/07/17 voto dello scritto 26

    Le domande sono state:
    - Spiegare il funzionamento dell'algoritmo RandomSelect( ) per la ricerca dell'elem di rango i e analisi di complessità al caso ottimo, medio e pessimo;
    - Analisi di complessità del Build-max-heap e HeapSort con dimostrazione;
    - È possibile ordinare un array di dim n in tempo lineare, dove l'elem di valore massimo è n^4? Motivare la risposta;
    - Dimostrare che la ricerca SENZA successo in un OPEN-HASH è 1/(1-α) al caso medio;
    - Dimostrazione ricerca CON successo in un OPEN-HASH al caso medio;
    - Come si risolve il problema della Clique riferito all'esercizio 5 dell'appello del 03/07/17;
    - Parlare di SAT e dimostrare che è un problema NP - completo.
Sign In or Register to comment.