Unit  Credits  Academic sector  Period  Academic staff 

ALGORITMI AVANZATI  4  INGINF/05INFORMATION PROCESSING SYSTEMS  1st Semester 
Roberto Posenato

COMPLESSITÀ  4  INGINF/05INFORMATION PROCESSING SYSTEMS  1st Semester 
Roberto Posenato

INTELLIGENZA ARTIFICIALE  4  INGINF/05INFORMATION PROCESSING SYSTEMS  1st Semester 
Maria Paola Bonacina

Module: ALGORITMI AVANZATI

The goal of this course is to introduce some advanced paradigms for algorithms development and analysis in order to determine good approximate solutions for hard optimization problems.
Module: COMPLESSITÀ

The goal of this module is to introduce students to computational complexity theory in general, to the NPcompleteness theory in detail and to computational analysis of problems with respect to their approximability.
Module: INTELLIGENZA ARTIFICIALE

The class presents the main techniques for problem solving, based on the central paradigm of symbolic representation. The objective is to provide the students with the ability to design, apply and evaluate algorithms for difficult problems, meaning that their mechanical solution captures aspects of artificial intelligence or computational rationality.
Module: ALGORITMI AVANZATI

Main concepts recall about computational problems: definition, instances, encoding, precise and approximate models. Optimization computational problem.
Main concepts recall about algorithms: computational resources, input encoding, input size/cost, computational time. Worst and average analysis. Computational time and growth order.
Computational time vs. hardware improvements: main relations. Efficient algorithms and tractable problems.
Divide et impera paradigm
Definition and application to some problems.
Greedy paradigm
Definition and application to some problems. Matroids and greedy algorithms.
Backtracking technique
Definition and application to some problems.
Branch & Bound technique
Definition and application to some problems.
Dynamic programming paradigm
Definition and application to some problems.
Memoization and Dynamic programming.
Local search technique
Definition and application to some problems.
Approximations algorithms
Definition and some application examples.
Simulated annealing.
Tabu search.
Probabilistic algorithms
Definition and few application examples.
Numerical probabilistic algorithms, Monte Carlo algorithms and Las Vegas algorithms. Examples: Buffon's needle, Pattern Matching and Universal hashing.
Module: COMPLESSITÀ

Introduction.
Computational model concept, computational resource, efficient algorithm and tractable problem.
Computational models
Turing Machine (MdT). MdT extension: multitape MdT (kMdT). MdT and languages: the difference between accepting and deciding a language.
Random Access Machine (RAM) computational model. Computation time considering uniform cost criterion or logarithmic cost one.
Time Complexity
Computational class TIME(). Theorem about polynomial relation between kMdT computations and MdT ones (sketch of proof).
Theorem about simulation cost of a MdT by a RAM.
Theorem about simulation cost of a RAM program by a MdT.
Sequential Computation Thesis and its consequences.
Linear Speedup Theorem and its consequences.
P Computational Class.
Problems in P: PATH, MAX FLOW, PERFECT MATCHING.
Extension of MdT: nondeterministic MdT (NMdT).
Time resource for kNMdT. NTIME() computational class. Relation between NMdT and MdT.
NP Computational Class.
An alternative characterization of NP: polynomial verifiers.
EXP Computation Class.
Space Complexity.
Space complexity concept. MdT with I/O. Computational Classes: SPACE() and NSPACE().
Compression Theorem.
Computational Classes: L and NL.
Example of problems: PALINDROME ∈ L and PATH ∈ NL.
Theorems about relations between space and time for a MdT with I/O. Relations between complexity classes.
Proper function concept and example of proper functions.
Borodin Gap Theorem.
Reachability method.
Theorem about spacetime classes: NTIME(f(n)) ⊆ SPACE(f(n)), NSPACE(f(n)) ⊆ TIME(k(log n+f(n))).
Universal MdT. The Hf set. Lemma 1 and 2 for time hierarchy theorem.
Time Hierarchy Theorem: strict and nostrict versions. P ⊂ EXP Corollary.
Space Hierarchy Theorem. L ⊂ PSPACE Corollary. Savitch Theorem. SPACE(f(n))=SPACE(f(n)^2) corollary. PSPACE=NPSPACE Corollary.
Reductions and completeness.
Reduction concept and logarithmic space reduction.
HAMILTON PATH ≤log SAT, PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.
Language completeness concept.
Closure concept with respect to reduction. Class reduction of L, NL, P, NP, PSPACE and EXP.
Computation Table concept.
Theorem about Pcompleteness of CIRCUIT VALUE problem.
Cook Theorem: an alternative proof.
Gadget concept and completeness proof of: INDEPENDENT SET, CLIQUE, VERTEX COVER and others.
Module: INTELLIGENZA ARTIFICIALE

Problem solving as search in a state space; uninformed search procedures; informed search procedures and heuristic search. Constraint problem solving. Knowledge representation: use of propositional logic and firstorder logic; normal forms; equality. Algorithms for satisfiability (SAT). Theorem proving: resolution and rewriting.
Module: ALGORITMI AVANZATI

The examination consists of a written test (at the same time as the other two module tests) that lasts 1 hour (all tests together last 3 hours). The grade in this module is worth 1/3 of the grade in the Algorithms examination.
Module: COMPLESSITÀ

The examination consists of a written test (at the same time as the other two module tests) that lasts 1 hour (all tests together last 3 hours). The grade in this module is worth 1/3 of the grade in the Algorithms examination.
Module: INTELLIGENZA ARTIFICIALE

The grade in Artificial Intelligence is worth 1/3 of the grade in the Algorithms exam, and it is determined by the grade in a written test.
Author  Title  Publisher  Year  ISBN  Note 
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani  Algorithms (Edizione 1)  McGrawHill Higher Education  2007  9780073523408  Testo secondario 
Alan Bertossi  Algoritmi e strutture dati (Edizione 1)  UTET  2000  8877506113  Testo secondario 
T. Cormen, C. Leiserson, R. Rivest, C. Stein  Introduzione agli Algoritmi e Strutture Dati (Edizione 2)  McGrawHill  2005  8838662517  Testo consigliato per la prima parte del corso 
Steven S. Skiena  The Algorithm Design Manual (Edizione 2)  Springer  2008  9781848000698  Testo secondario per il corso ma ottimo come manuale di riferimento per un'ampia classe di problemi. 
Christos H. Papadimitriou  Computational complexity  Addison Wesley  1994  0201530821  testo principale 
Stuart Russell, Peter Norvig  Artificial Intelligence: A Modern Approach (Edizione 2)  Prentice Hall  2003  0137903952  Testo adottato 
Judea Pearl  Heuristics: Intelligent search strategies for computer problem solving (Edizione 1)  Addison Wesley  1985  02010559  Testo complementare 
Stuart Russell, Peter Norvig  Intelligenza artificiale: Un approccio moderno (Edizione 2)  Pearson Education Italia  2005  88719222  Traduzione italiana del testo adottato 
ChinLiang Chang, Richard CharTung Lee  Symbolic Logic and Mechanical Theorem Proving (Edizione 1)  Academic Press  1973  0121703509  Testo complementare 