Academic Year 2019-2020

COMPLEXITY AND INFORMATION THEORY

Teachers:
Carla Piazza
Total Course Credits: 6
Teaching Period: First Period
Teaching Language: Inglese
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 oral. It is possible to present at the exam a relation on a topic in agreement with the professor. In any case after the presentation, the student has to answer to further questions on the course.

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. 

CONTENTS

This course aims at presenting the main results in the fields of computational complexity of algorithms and information theory. 

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