Unit  Credits  Academic sector  Period  Academic staff 

COMPLESSITÀ  6  INGINF/05INFORMATION PROCESSING SYSTEMS  I semestre 
Margherita Zorzi

ALGORITMI  6  INGINF/05INFORMATION PROCESSING SYSTEMS  II semestre 
Margherita Zorzi

Module: ALGORITMI

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À

In this courses, the relevant notions in complexity theory are introduced. Main themes are the relationship between complexity classes and Npcompleteness theory. The scope of the courses is to give formal instruments useful in the analysis of the difficulty of computational problems.
Module: ALGORITMI

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.
Huffman Codes
Backtracking technique

Definition and application to some problems (main examples: Graham Scan and KnuthMorrisPratt algorithm).
Branch & Bound technique

Definition and application to some problems.
Dynamic programming paradigm

Definition and application to some problems.
Memoization and Dynamic programming.
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.
Local search tecnique

Definition and application to some problems.
Approximations algorithms

Definition and some examples.
Simulated annealing.
Tabù search.
Module: COMPLESSITÀ

This is a condensed version of the program. The detailed program (with useful notes for the students) is available in the pdf file "Diario delle Lezioni"
1)Introduction
Computational models, computational resources, tractable problems and feasible algorithms.
2) Computational models and time complexity classes
Deterministic Turing Machine with 1 and k strings
Class TIME(f(n)).
Relationship between kMdT e 1MdT (theorem).
Random Access Machine.
Simulation theorems TMRAM.
Thesis of sequential calculus.
Linear speedup theorem and consequences.
The class P.
Examples of problems in P.
Non deterministic Turing machine(NTM).
Class NTIME(f(n)).
Relationship between NTM and TM.
The class NP.
Examples of problems in NP.
Characterization of problem in NP with polynomial verifier.
The class EXP.
4)Space complexity
.
Inputoutput TM.
Classes SPACE(f(n)) and NSPACE(f(n)).
Compression Theorem
Classes L e NL.
Examples of problems in L and NL.
Relationship between space and time onf I/O TM
5)Relationship between complexity classes
Proper function.
The reachability method.
Theorems: inclusions between time and space classes. Universal TM.
Lemmata for Time Hierarchy Theorem.
Time Hierarchy Theorem. Corollary P ⊂ EXP.
Space Hierarchy Theorem. Corollary L ⊂ PSPACE.
Gap's Theorem.
Savitch's Theorem with Corollary. Corollary PSPACE=NPSPACE.
6)Reduction and completeness
Reduction and logarithmic reduction.
Examples of reduction: HAMILTON PATH ≤log SAT, PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.
Examples of reduction by generalization.
Property of reduction: reflexivity and transitivity.
CCompleteness for a language.
Closure of a class C with respect to reduction.
L, NL, P, NP, PSPACE and EXP are closed w.r.t ≤log.
Table method. Computational table
CIRCUIT VALUE is Pcomplete.
Cook's theorem.
Examples of NPcomplete problems.
7)Some notions on the complement of non deterministic classes
coC
NP and coNP
Module: ALGORITMI

Written test/ open questions
Module: COMPLESSITÀ

Written test with open questions.
Author  Title  Publisher  Year  ISBN  Note 
Christos H. Papadimitriou  Computational complexity  Addison Wesley  1994  0201530821 