91251 - Languages and Algorithms for Artificial Intelligence

Learning outcomes

At the end of the course, the student has an understanding of the main linguistic and algorithmic techniques used in the context of AI, including the main aspects related to functional, logic and constraint programming, with their theoretical foundations and practical applications. The student has an understanding of the basic principles of distributed models and algorithms, consensus problems, and large-scale algorithms for the analysis of big data.

Course contents

Module 1

Abstract machines. Python machine. Programming in Python: names and visibility, functions, immutable and mutable objects, basic data types (numbers, strings, tuples, lists, dictionaries) and their use in the solution of problems. Classes and objects. Methods and inheritance. Exceptions. Introduction to the library NumPy and its N-dimensional array objects.

Module 2

Introduction to mathematical logic. Unification. Resolution.
Introduction to logic programming. Prolog languages.
Constraint logic programming and concurrent constraint programming. Constraint programming. The language MiniZinc.

Module 3

Rudiments of Computability and Complexity Theory. Undecidability, polynomial time computability, and NP-completeness. Between the feasible and the unfeasible. A Formal Learning Model: PAC Learning. Learning via Uniform Convergence. The Bias-Complexity Tradeoff.
The VC-Dimension.

Readings/Bibliography

Module 1

John V. Guttag. Introduction to Computation and Programming Using Python. Third Edition: With Application to Computational Modeling and Understanding Data. MIT Press, 2021. https://mitpress.mit.edu/books/introduction-computation-and-programming-using-python-third-edition

Module 2

Dirk van Dalen. Logic and structure. 4th edition, Springer.

K. Doets. From Logic to Logic Programming. The Mit Press.

Russell, Norvig. Artificial Intelligence: A Modern Approach (any edition). Pearson.

Module 3

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

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

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

Teaching methods

Theoretical and practical class lectures. 

Module 1

Formal in-class lectures. Autonomous work on guided programming exercises (outside the scheduled class times), using the Moodle platform for the course.  Lectures (24 hours) will be concentrated at the beginning of the semester (before end of Oct). As it concerns the teaching methods of this course unit, all students must attend Modules 1 and 2 on Health and Safety online

Assessment methods

Written and/or oral examinations at the end of each module.
Possible project work. Module 1 will be assessed through a mandatory Python programming test, with automatic correction, using the Moodle programming platform for the course. A sufficient test is required to sit to any examination of the other modules. A preliminary test could be offered in early November.

Teaching tools

Lectures. Practical exercises.

Office hours

See the website of Ugo Dal Lago

See the website of Simone Martini

See the website of Maurizio Gabbrielli