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?
Altre domande:
- 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
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
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.
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.
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.
Domande Orale Bernasconi
Torna a “[ALL] Algoritmica e Laboratorio”
Vai a
- Generale
- ↳ Discussioni
- ↳ Discussions (in english)
- ↳ I rappresentanti rispondono
- ↳ Parliamone
- ↳ Mercatino
- ↳ Tirocini
- ↳ Annunci
- ↳ Announcements (in english)
- ↳ Eventi
- I anno
- ↳ Algebra Lineare
- ↳ Analisi Matematica
- ↳ Fondamenti dell'Informatica
- ↳ Laboratorio I
- ↳ Programmazione e Algoritmica
- II anno
- ↳ Architetture e Sistemi Operativi
- ↳ Calcolo Numerico
- ↳ Calcolo Numerico - Vecchio Ordinamento
- ↳ Laboratorio II
- ↳ Paradigmi di Programmazione
- ↳ Ricerca Operativa
- ↳ Ricerca Operativa - Vecchio Ordinamento
- ↳ Statistica
- ↳ Statistica - Vecchio Ordinamento
- III anno
- ↳ Basi di Dati
- ↳ Basi di Dati - Vecchio Ordinamento
- ↳ Introduzione all'Intelligenza Artificiale
- ↳ Introduzione all'Intelligenza Artificiale - Vecchio Ordinamento
- ↳ Ingegneria del Software
- ↳ Ingegneria del Software - Vecchio Ordinamento
- ↳ Reti e Laboratorio III
- Complementari
- ↳ Algebra
- ↳ Cloud Computing
- ↳ Cloud e Green Computing
- ↳ Computer Grafica
- ↳ Crittografia
- ↳ Elementi di Calcolabilità e Complessità
- ↳ Elementi di Calcolabilità e Complessità - Vecchio Ordinamento
- ↳ Esperienze di programmazione
- ↳ Fisica
- ↳ Fisica - Vecchio Ordinamento
- ↳ Gestione di Reti
- ↳ Green Computing
- ↳ Interazione Uomo-Macchina
- ↳ Laboratorio di Basi di Dati
- ↳ Laboratorio di Web Scraping
- ↳ Sicurezza di Sistemi ICT
- ↳ Sviluppo di Applicazioni Mobili
- ↳ Sviluppo di Applicazioni Web
- ↳ Teoria dell'Informazione
- Vecchio Ordinamento
- ↳ I anno
- ↳ [ALL] Algoritmica e Laboratorio
- ↳ [AM] Analisi matematica
- ↳ [FIS] Fisica
- ↳ [LPP] Logica per la programmazione
- ↳ [MDAL] Matematica discreta e algebra lineare
- ↳ [PRL] Programmazione I e laboratorio
- ↳ II anno
- ↳ [AE] Architettura degli elaboratori
- ↳ [BD] Basi di dati
- ↳ [CPS] Calcolo delle probabilità e statistica
- ↳ [CN] Calcolo numerico
- ↳ [IS] Ingegneria del software
- ↳ [PR2] Programmazione II
- ↳ [RO] Ricerca Operativa
- ↳ [SOL] Sistemi operativi e laboratorio
- ↳ III anno
- ↳ [ECC] Elementi di calcolabili e complessità
- ↳ [PI] Programmazione di interfacce
- ↳ [IIA] Introduzione all'intelligenza artificiale
- ↳ [RCL] Reti di calcolatori e laboratorio
- ↳ Advanced databases
- ↳ Advanced programming
- ↳ Advanced software engineering
- ↳ Algorithm design
- ↳ Algorithm engineering
- ↳ Artificial intelligence fundamentals
- ↳ Bioinformatics
- ↳ Competitive programming and contests
- ↳ Computational mathematics for learning and data analysis
- ↳ Data mining
- ↳ Human language technologies
- ↳ ICT infrastructures
- ↳ ICT risk assessment
- ↳ Information Retrieval
- ↳ Intelligent Systems for pattern recognition
- ↳ Laboratory for innovative software
- ↳ Languages, compilers and interpreters
- ↳ Machine learning
- ↳ Mobile and cyber-physical systems
- ↳ Parallel and distributed systems: paradigms and models
- ↳ Peer to peer systems and blockchains
- ↳ Principles for software composition
- ↳ Smart applications
- ↳ Software validation and verification
- Links
- ↳ HomePage Dipartimento
- ↳ Portale Esami