FI:I018 Výpočetní složitost II

I018 Výpočetní složitost II

Faculty of Informatics
Spring 1997

Extent and Intensity

2/0. 2 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).

Teacher(s)

prof. RNDr. Ivana Černá, CSc. (lecturer)

Guaranteed by

Contact Person: prof. RNDr. Ivana Černá, CSc.

Prerequisites

Before enrolling this course the students should go through I005 Formal Languages and Automata I. I012 Complexity is recommended.

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

Syllabus

Computers can be described as a series of communication processes on many levels. Communication complexity is the mathematical theory of such communication processes. It is also often used as an abstract model of other aspects of computation. This lecture begins with simple models of communication and leads up to state-of-the-art theoretical results and aplications.
PART ONE: Two party communication complexity. Basic protocol models. Lower bounds (Fooling set method, Rank method, Tiling method, comparison of methods). One-way communication complexity.
PART TWO: Other models of communication. Nondeterministic and randomized communications. The communication complexity of relations. Multiparty communications. Variable partition models.
PART THREE: Applications. Networks, communication and VLSI. Decision trees and data structures. Boolean circuit depth. Time and space. Further topics.

Language of instruction

Czech

Teacher's information

http://www.fi.muni.cz/usr/cerna/i018.html

The course is also listed under the following terms Spring 1996, Spring 1999, Autumn 2000.