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).
Domande Orale Pagli
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