B9045 - COMPLESSITA' COMPUTAZIONALE E DESCRITTIVA

Conoscenze e abilità da conseguire

Questo corso presenterà un'introduzione alla Teoria della Complessità Computazionale e della Complessità Boreliana e Descrittiva. La Teoria della Complessità Computazionale studia quanto è difficile risolvere un problema algoritmico, in termini della quantità di risorse di calcolo necessarie per la sua decisione tramite un algoritmo. La Complessità Boreliana studia quanto è difficile descrivere un insieme o una funzione sui numeri reali (o un altro spazio topologico) in termini di insiemi aperti (o usando una formula di una certa sintassi), ed altresì quanto è difficile ottenere una classificazione esplicita di una data classe di oggetti matematici. Entrambi questi settori hanno numerose applicazioni a svariate aree della matematica algebra, analisi, matematica discreta), di cui questo corso offrirà una panoramica. Al termine del corso, lo studente avrà familiarità con i concetti fondamentali della Complessità Computazionale e Boreliana, e sarà in grado di usare le competenze acquisite per studiare la complessità di problemi algoritmici e di classificazione.

Contenuti

Il corso fornira' un introduzione alla Complessita' Computazionale, Descrittiva, e Boreliana, ed ai collegamenti tra questi argomenti,

In particolare, il corso trattera' i seguenti argomenti, in questo ordine:

1. Modelli di calcolo (macchine di Turing)
2. Introduzione alla Complessita' Computazionale
3. Sintassi e semantica in logica
4. Introduzione alla Complessita' Descrittiva
5. Descrizione semantica di classi di complessita'
6. Insiemi e funzioni Boreliane
7. Complessita' Boreliana di insiemi e problemi di classificazione

Testi/Bibliografia

Il corso usera' come fonti principali i seguenti testi:

• Sipser, Michael. Introduction to the Theory of Computation
• Arora, Sanjeev; Barak, Boaz, Computational complexity. A modern approach. Cambridge University Press, Cambridge, 2009. xxiv+579
• 
  
• Grohe, Martin, Descriptive complexity, canonisation, and definable graph structure theory. Lecture Notes in Logic, 47. Association for Symbolic Logic, Ithaca, NY; Ca mbridge University Press, Cambridge, 2017
• Gao, Su. Invariant descriptive set theory.
  Pure and Applied Mathematics (Boca Raton), 293. CRC Press, Boca Raton, FL, 2009. xiv+383
• Kechris, Alexander S. Classical descriptive set theory. Graduate Texts in Mathematics, 156. Springer-Verlag, New York, 1995. xviii+402 pp.

Metodi didattici

Il corso consiste in 48 ore di didattica frontale dedicate sia alla teoria che alla discussione di problemi. Inoltre, verranno assegnati regolarmente degli esercizi di pratica da svolgere in autonomia. Questi esercizi permetteranno agli studenti di verificare la comprensione degli argomenti trattati, e fare pratica della loro applicazione per la risoluzione di problemi.

Modalità di verifica e valutazione dell'apprendimento

L'esame consiste in una prova orale, che mira a verificare la comprensione dei concetti fondamentali presentati nel corso, e la capacita' di applicarli nella soluzione di problemi.

Strumenti a supporto della didattica

Sulla piattaforma Virtuale verranno pubblicate:

• per ogni argomento, le sezioni o capitoli dei libri di testo a cui fare riferimento;
• liste di esercizi di pratica, da svolgere in autonomia, con soluzioni;
• un syllabus (lista di argomenti) del corso.

Il ricevimento sarà svolto su appuntamento in presenza o online.

Orario di ricevimento

Consulta il sito web di Martino Lupini