B5026 - INTRODUCTION TO COMPUTABILITY AND COMPLEXITY

Anno Accademico 2024/2025

  • Docente: Ugo Dal Lago
  • Crediti formativi: 6
  • SSD: ING-INF/05
  • Lingua di insegnamento: Inglese
  • Modalità didattica: Convenzionale - Lezioni in presenza
  • Campus: Bologna
  • Corso: Laurea Magistrale in Artificial Intelligence (cod. 9063)

Conoscenze e abilità da conseguire

At the end of the course, the student has an understanding of the theoretical foundations of linguistic and algorithmic techniques used in the context of AI.

Contenuti

Il corso fornisce innanzitutto alcuni rudimenti di teoria della computabilità e della complessità: macchine di Turing, indecidibilità, tempo polinomiale e NP-completezza. Verso la fine del corso, daremo poi una panoramica sulla cosiddetta computational learning theory: PAC Learning, apprendimento tramite convergenza uniforme, VC-Dimension.

Testi/Bibliografia

[1] Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

[2] Michael Kearns, Umesh. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.

[3] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.

Metodi didattici

Lezioni frontali e esercitazioni.

Modalità di verifica e valutazione dell'apprendimento

L'esame viene svolto tramite EOL e si compone di due parti:

  • Nella prima lo studente sarà tenuto a rispondere a cinque domande riguardanti gli argomenti del corso.
  • Nella seconda, allo studente sarà richiesto di risolvere tre esercizi.

Strumenti a supporto della didattica

Le slides, un eserciziario e altro materiale di supporto saranno resi disponibili tramite la piattaforma Virtuale.

Orario di ricevimento

Consulta il sito web di Ugo Dal Lago