91251 - Languages and Algorithms for Artificial Intelligence

Academic Year 2022/2023

  • Docente: Ugo Dal Lago
  • Credits: 12
  • SSD: ING-INF/05
  • Language: English
  • Moduli: Simone Martini (Modulo 1) Maurizio Gabbrielli (Modulo 2) Ugo Dal Lago (Modulo 3) Alexis Ghyselen (Modulo 4)
  • Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2) Traditional lectures (Modulo 3) Traditional lectures (Modulo 4)
  • Campus: Bologna
  • Corso: Second cycle degree programme (LM) in Artificial Intelligence (cod. 9063)

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.

Module 4

Programming and learning paradigm, and the languages for inference. Introduction to the language Scheme/Racket and its probabilistic extensions Church/Gamble. Generative models as probabilistic programs. Bayesian programming in Church/Gamble. Learning as conditional inference. Inference algorithms (rejection sampling and Metropolis Hastings). Operational semantics and inference by evaluation. Time permitting, an overview of differentiable programming.

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.

Module 4

N. D. Goodman, J. B. Tenenbaum, and The ProbMods Contributors (2016). Probabilistic Models of Cognition (1st ed.). (available at http://v1.probmods.org/index.html)

Jan-Willem van de Meent, Brooks Paige, Hongseok Yang, Frank Wood, An introduction to probabilistic programming (available at https://arxiv.org/abs/1809.10756 ).

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 preliminari test will be offered in early November 2022.

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

See the website of Alexis Ghyselen