- Docente: Ugo Dal Lago
- Credits: 6
- SSD: ING-INF/05
- Language: English
- Teaching Mode: Traditional lectures
- Campus: Bologna
- Corso: Second cycle degree programme (LM) in Artificial Intelligence (cod. 9063)
-
from Feb 17, 2025 to Jun 12, 2025
Learning outcomes
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.
Course contents
The course gives some first of all some rudiments of computability and complexity theory: Turing machines, undecidability, polynomial time computability, and NP-completeness. Towards the end of the course, then we give a bird's eye view on computational learning theory: PAC Learning, learning via uniform convergence, the VC-Dimension.
Readings/Bibliography
[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.
Teaching methods
Lectures and exercise sessions.
Assessment methods
The exam is done via EOL, and consists of two parts:
- In the first one, the student will be required to answer five questions about the topics of the course.
- In the second one, the student will be asked to solve three exercises.
Teaching tools
Slides, an exercise book, and some other teaching material will be made available through the Virtuale platform.
Office hours
See the website of Ugo Dal Lago