COMPLEXITY AND INFORMATION THEORY

Academic Year 2022-2023

Teachers

Carla Piazza

Unit Credits

Teaching Period

First Period

Course Type

Characterizing

Prerequisites. It is useful for the student to be already familiar with the following notions: computational model (e.g., Turing Machines); computability, Church Thesis, Halting Theorem; asymptotic notation; basic data structures (e.g., arrays, lists, trees, graphs). Such knowledge is given inside some courses of the undergraduate course in Computer Science (e.g., Foundations of Computer Science, Algorithms and Data Structures).

Teaching Methods. The course mainly consists of theoretical and practical classes. The e-learning web-page of the course contains all useful information for students.

Verification of Learning. The exam is written and oral. The written test is aimed at evaluating the knowledge acquired on the topics covered. In the oral exam, reasoning skills on topics related to the course are also assessed.

Objectives

Specifics Objectives.

Index:

Complexity Theory

Time and Space complexity on Turing Machines and other classical models

Relationships between complexity classes

Reductions, completeness and instances of languages in the different classes

Non standard computational models: DNA and Quantum Computing

Graph algorithms at the basis of computational complexity: reachability, trace equivalence and bisimulation

Information Theory

Basic Concepts

Entropy and data compression

Mutual Information

Kolmogorov complexity

SKILLS

The student should be able to:

1.1. Knowledge

Formally define the classical models of computation and the time/space complexity classes.

Present some proper members of each studied complexity class.

Present and prove the complexity theory results presented during the course.

Define the DNA and Quantum models of computation and compare them with the classical models.

Describe algorithms on graphs.

Define the standard notions of Information Theory.

Present the classical results on data compression presented during the course.

1.2 Ability of exploiting knowledge

Classify languages in terms of time and space complexity.

Elaborate reductions between languages.

Define and implement algorithms over graphs for variants of the problems analysed in the course.

Model and solve simple problems of Information Theory: data compression and channel coding.

SOFT SKILLS

The student should be able to:

2.1 Judgement autonomy.

Establish whether a problem can be efficiently solved or not.

Elaborate efficient algorithms for solving new problems.

Eventually introduce constraints to make a problem tractable.

Estimate performances of different information and communication systems.

2.2 Comunicative skills.

Motivate the proposed solutions.

Explain which additional conditions could help to solve the problem more efficiently.

Justify the choices of the computational model and data structures.

Explain coding and compression methods and information limits.

2.3 Learning ability.

Find and exploit existing solutions over related problems.

Exploit new instruments for improving the computational complexities.

Identify information, coding and communication problems/solutions.

Texts

C. H. Papadimitriou. Computational Complexity. Addison Wesley. 1995

J. V. Stone. Information Theory – A tutorial Introduction.

T. M. Cover and J. A. Thomas. Elements of Information Theory 2nd Edition. Wiley. 2006

Academic Year 2022-2023