Facoltà: Ingegneria dell'informazione, informatica e statistica
Prof. Nicola Galesi: Computational Complexity
5,4difficoltà
Sapienza · Facoltà: Ingegneria dell'informazione, informatica e statistica · Engineering in Computer Science and Artificial Intelligence - Ingegneria Informatica e Intelligenza Artificiale (LM-32)
Di cosa si tratta: Modelli teorici di computazione e risorse di tempo e spazio, con le classi di complessità L, NL, P, NP, PSPACE, BPP, RP, #P e IP. Al centro stanno il problema P contro NP, la NP-completezza e i problemi intrattabili con risorse limitate, insieme ai risultati principali.
Che cosa si intende per complessità temporale di un algoritmo e come si esprime con la notazione asintotica?
Quali sono le classi di complessità P e NP e che relazione hanno tra loro?
Che cosa si intende per riducibilità polinomiale tra problemi decisionali?
Come si dimostra che un problema è NP completo?
Quali sono le caratteristiche della classe PSPACE e del suo rapporto con NP?
Che cosa si intende per macchina di Turing non deterministica?
Come si definisce la classe co NP e quale problema rappresenta?
Che cosa si intende per teorema di gerarchia temporale?
Quali problemi di ottimizzazione sono intrattabili e come si affrontano nella pratica?
Che cosa si intende per algoritmo di approssimazione e con quale garanzia di qualità?
Come si studia la complessità in spazio di un algoritmo?
Che cosa si intende per problema di decisione e come si lega ai problemi di ricerca?
Quali sono le proprietà della classe BPP e il ruolo della randomizzazione?
Che cosa si intende per riduzione di Karp e quali esempi classici la illustrano?
Come si caratterizzano i problemi di soddisfacibilità booleana?
Quali sono le implicazioni pratiche della distinzione tra complessità polinomiale ed esponenziale?
Che cosa si intende per complessità di comunicazione e in quali contesti si studia?
Come si dimostra un limite inferiore alla complessità di un problema?
Quali sono le caratteristiche delle funzioni a senso unico e il loro ruolo in crittografia?
Come si misura la complessità di Kolmogorov di una stringa?
Domande di esercitazione costruite sul programma ufficiale, non fornite dal docente.
Facoltà: Scienze Matematiche, Fisiche e Naturali
Prof. Nicola Galesi: Logica e Metodi Probabilistici per L'Informatica
4,1difficoltà
Sapienza · Facoltà: Scienze Matematiche, Fisiche e Naturali · Scienze matematiche per l’intelligenza artificiale (L-35)
Di cosa si tratta: Ripasso di logica proposizionale, con sintassi, semantica e formalizzazione delle relazioni. Il corso affronta il problema della soddisfacibilità SAT e della validità TAUT, con l'algoritmo di Davis-Putnam e i SAT-solver basati su algoritmi CDCL. L'insegnamento include anche una parte dedicata ai metodi probabilistici applicati all'informatica.
Che cosa si intende per proposizione logica e quali connettivi fondamentali esistono?
Come si costruisce una tavola di verita' per una formula logica?
Che cosa si intende per tautologia, contraddizione e formula soddisfacibile?
Come si dimostra la validita' di un argomento con il metodo della deduzione naturale?
Che cosa si intende per logica dei predicati e quali quantificatori vengono usati?
Come si traduce una frase in linguaggio naturale in una formula della logica dei predicati?
Che cosa si intende per probabilita' discreta nel contesto informatico?
Come si calcola la probabilita' di un evento composto in un algoritmo randomizzato?
Che cosa si intende per variabile aleatoria e valore atteso in un'analisi di complessita'?
Come si usa la disuguaglianza di Markov per stimare una probabilita' di coda?
Che cosa si intende per algoritmo randomizzato e quali vantaggi offre?
Come si analizza il tempo medio di esecuzione di un algoritmo probabilistico?
Quali sono le applicazioni dei metodi probabilistici nella crittografia?
Che cosa si intende per catena di Markov nei modelli informatici?
Come si applica il principio di inclusione-esclusione nel conteggio di eventi?
Che cosa si intende per induzione matematica e come si usa per dimostrare proprieta' dei programmi?
Come si definisce una relazione di equivalenza e quali proprieta' possiede?
Quali strutture algebriche si usano nella teoria dei linguaggi formali?
Che cosa si intende per teoria della decidibilita' e quali problemi sono indecidibili?
Come si collegano la logica formale e la verifica della correttezza dei programmi?
Domande di esercitazione costruite sul programma ufficiale, non fornite dal docente.
Domande frequenti Libri, programma ed esami del prof. Nicola Galesi a Sapienza
Che libro usa il prof. Nicola Galesi per Computational Complexity a Sapienza?
Per Computational Complexity (Canale unico) indica come obbligatorio: Arora – Computational Complexity, Goldreich – Computational Complexity, Vollmer – Introduction to Circuit Complexity.
Quanto è impegnativo Computational Complexity?
6 CFU, difficoltà stimata 5.4 su 10 rispetto agli esami della stessa area.
Che libro usa il prof. Nicola Galesi per Logica e Metodi Probabilistici per L'Informatica a Sapienza?
Per Logica e Metodi Probabilistici per L'Informatica (Canale unico) indica come obbligatorio: Randomized Algorithms and Probabilistic Analysis, M. Mitznmacher, E..
Quanto è impegnativo Logica e Metodi Probabilistici per L'Informatica?
6 CFU, difficoltà stimata 4.1 su 10 rispetto agli esami della stessa area.
Dove trovo la scheda ufficiale di un esame?
Ogni insegnamento qui sopra ha il link alla scheda ufficiale dell’ateneo: controllala sempre prima di acquistare.
Sei uno studente tra i 18 e i 22 anni?Con Prime Student hai 90 giorni gratis, poi Amazon Prime a soli 2,49 € al mese: consegne veloci e gratuite anche sui libri.Scopri Prime Student ›
Controlla sempre la scheda dell'esame. Le informazioni vengono dalle schede ufficiali degli atenei e possono cambiare o contenere errori: prima di acquistare verifica i testi sulla scheda ufficiale dell'esame (la trovi linkata in ogni esame) e, nel dubbio, chiedi al docente.
Aiutaci a tenerci aggiornati
Il prof ha indicato altri libri, pagine o modifiche? Scrivicelo.
Questo sito usa solo strumenti tecnici (nessun cookie di profilazione). I link ai negozi sono link di affiliazione. Cookie policy · Privacy