Domande colloquio integrativo
Inviato: 13/06/2023, 10:05
Dopo il passaggio dal vecchio al nuovo ordinamento, ho le domande di due orali con la prof Pisanti di studenti che avevano dato Programmazione 1 e Lab per il riconoscimento di Programazione e Algoritmi.
Colloquio integrativo algoritmi (6CFU)
Argomenti:
* Nozioni di Algoritmo e di Problema.
* Complessità computazionale: caso pessimo e caso medio.
* Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
* Divide-et-impera, relazioni di ricorrenza e teorema principale.
* MergeSort: algoritmo e sua analisi.
* QuickSort: algoritmo e sua analisi
* Dizionari: tabelle hash e alberi binari di ricerca (senza dimostrazioni)
Orale 1:
Dato un algoritmo ricorsivo: [in allegato al post]
- Scrivere la relazione di ricorrenza
- Risolverla con il teorema dell’esperto
Dato un albero:
- dire se è un ABR
- ricercare un elemento
- qual’è il costo massimo della ricerca
- Scrivere il risultato della visita anticipata
Merge Sort
- Spiegare a parole come funziona
- Scrivere la relazione di ricorrenza
- Risolverla con il teorema dell’esperto
- Dire se è ottimo
Limiti inferiori di un problema
- Come si può trovare? (Dimensione, eventi contabili, albero di decisione)
- Dimostrare il limite inferiore per il problema dell’ordinamento [lode]
Tabelle hash
- Cos’è una tabella hash
- Come funziona il concatenamento
Orale 2:
*Costo di uno pseudocodice.
*Algoritmo ricorsivo che trova la dimensione di un albero. (+ Costo)
*Algoritmo ricorsivo che trova il numero delle foglie di un albero. (+Costo)
*Parlare di MergeSort+costo+applicare teorema esperto su T(n).
*Tabelle hash
*Che tipo di ashing abbiamo visto.
*Cosa sono le collisioni.
*Come si trova il limite inferiore.
Colloquio integrativo algoritmi (6CFU)
Argomenti:
* Nozioni di Algoritmo e di Problema.
* Complessità computazionale: caso pessimo e caso medio.
* Limiti del calcolo: albero di decisione, limiti superiori e inferiori.
* Divide-et-impera, relazioni di ricorrenza e teorema principale.
* MergeSort: algoritmo e sua analisi.
* QuickSort: algoritmo e sua analisi
* Dizionari: tabelle hash e alberi binari di ricerca (senza dimostrazioni)
Orale 1:
Dato un algoritmo ricorsivo: [in allegato al post]
- Scrivere la relazione di ricorrenza
- Risolverla con il teorema dell’esperto
Dato un albero:
- dire se è un ABR
- ricercare un elemento
- qual’è il costo massimo della ricerca
- Scrivere il risultato della visita anticipata
Merge Sort
- Spiegare a parole come funziona
- Scrivere la relazione di ricorrenza
- Risolverla con il teorema dell’esperto
- Dire se è ottimo
Limiti inferiori di un problema
- Come si può trovare? (Dimensione, eventi contabili, albero di decisione)
- Dimostrare il limite inferiore per il problema dell’ordinamento [lode]
Tabelle hash
- Cos’è una tabella hash
- Come funziona il concatenamento
Orale 2:
*Costo di uno pseudocodice.
*Algoritmo ricorsivo che trova la dimensione di un albero. (+ Costo)
*Algoritmo ricorsivo che trova il numero delle foglie di un albero. (+Costo)
*Parlare di MergeSort+costo+applicare teorema esperto su T(n).
*Tabelle hash
*Che tipo di ashing abbiamo visto.
*Cosa sono le collisioni.
*Come si trova il limite inferiore.