Libri UniversitariZoom 100%

Prof. Nicola Galesi: i libri dei suoi insegnamenti

Scheda docente sul sito dell’ateneo ›
Insegnamenti trovati: 2
Sapienza 2 insegnamenti
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.

Tempo di studio e official info

Tempo consigliato per preparare l’esame: da 3 a 6,5 settimane
Dati verificati il 18/09/2026

Libri indicati per la materia

Scorri di lato: 3 libri
1ª scelta · uno solo tra 3
Arora – Computational ComplexityISBN 9780521424264
Tempo di studio del libro≈ 6,5 settimane
Obbligatorietà
Obbligatorio · uno a scelta tra 3
Adottato in
1 materia
Tipo
Manuale
Pagine
579 pagine
Difficoltà
7,8
Goldreich – Computational ComplexityISBN 9780521884730
Tempo di studio del libro≈ 6,5 settimane
Obbligatorietà
Obbligatorio · uno a scelta tra 3
Adottato in
1 materia
Tipo
Manuale
Pagine
606 pagine
Difficoltà
7,9
Vollmer – Introduction to Circuit ComplexityISBN 9783540643104
Tempo di studio del libro≈ 3 settimane
Obbligatorietà
Obbligatorio · uno a scelta tra 3
Adottato in
1 materia
Tipo
Manuale
Pagine
n.d.
Difficoltà
6,6
Domande possibili all’esame
  1. Che cosa si intende per complessità temporale di un algoritmo e come si esprime con la notazione asintotica?
  2. Quali sono le classi di complessità P e NP e che relazione hanno tra loro?
  3. Che cosa si intende per riducibilità polinomiale tra problemi decisionali?
  4. Come si dimostra che un problema è NP completo?
  5. Quali sono le caratteristiche della classe PSPACE e del suo rapporto con NP?
  6. Che cosa si intende per macchina di Turing non deterministica?
  7. Come si definisce la classe co NP e quale problema rappresenta?
  8. Che cosa si intende per teorema di gerarchia temporale?
  9. Quali problemi di ottimizzazione sono intrattabili e come si affrontano nella pratica?
  10. Che cosa si intende per algoritmo di approssimazione e con quale garanzia di qualità?
  11. Come si studia la complessità in spazio di un algoritmo?
  12. Che cosa si intende per problema di decisione e come si lega ai problemi di ricerca?
  13. Quali sono le proprietà della classe BPP e il ruolo della randomizzazione?
  14. Che cosa si intende per riduzione di Karp e quali esempi classici la illustrano?
  15. Come si caratterizzano i problemi di soddisfacibilità booleana?
  16. Quali sono le implicazioni pratiche della distinzione tra complessità polinomiale ed esponenziale?
  17. Che cosa si intende per complessità di comunicazione e in quali contesti si studia?
  18. Come si dimostra un limite inferiore alla complessità di un problema?
  19. Quali sono le caratteristiche delle funzioni a senso unico e il loro ruolo in crittografia?
  20. 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.

Tempo di studio e official info

Tempo consigliato per preparare l’esame: ≈ 3 settimane
Dati verificati il 19/09/2026

Libri indicati per la materia

Obbligatorietà
Obbligatorio
Adottato in
1 materia
Tipo
Manuale
Pagine
n.d.
Difficoltà
4,1
Domande possibili all’esame
  1. Che cosa si intende per proposizione logica e quali connettivi fondamentali esistono?
  2. Come si costruisce una tavola di verita' per una formula logica?
  3. Che cosa si intende per tautologia, contraddizione e formula soddisfacibile?
  4. Come si dimostra la validita' di un argomento con il metodo della deduzione naturale?
  5. Che cosa si intende per logica dei predicati e quali quantificatori vengono usati?
  6. Come si traduce una frase in linguaggio naturale in una formula della logica dei predicati?
  7. Che cosa si intende per probabilita' discreta nel contesto informatico?
  8. Come si calcola la probabilita' di un evento composto in un algoritmo randomizzato?
  9. Che cosa si intende per variabile aleatoria e valore atteso in un'analisi di complessita'?
  10. Come si usa la disuguaglianza di Markov per stimare una probabilita' di coda?
  11. Che cosa si intende per algoritmo randomizzato e quali vantaggi offre?
  12. Come si analizza il tempo medio di esecuzione di un algoritmo probabilistico?
  13. Quali sono le applicazioni dei metodi probabilistici nella crittografia?
  14. Che cosa si intende per catena di Markov nei modelli informatici?
  15. Come si applica il principio di inclusione-esclusione nel conteggio di eventi?
  16. Che cosa si intende per induzione matematica e come si usa per dimostrare proprieta' dei programmi?
  17. Come si definisce una relazione di equivalenza e quali proprieta' possiede?
  18. Quali strutture algebriche si usano nella teoria dei linguaggi formali?
  19. Che cosa si intende per teoria della decidibilita' e quali problemi sono indecidibili?
  20. 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.