I017 Structural Complexity

Faculty of Informatics
Spring 2003
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Timetable
Tue 10:00–11:50 B410
Prerequisites
I012 Complexity
The course expands on I012.
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
  • More on complexity classes; their structure and properties. Comparison of various complexity measures.
  • Lower bound techniques.
  • The polynomial hierarchy.
  • Computation that counts.
  • Alternation and games. Games against nature and interactive protocols.
  • Interactive proof systems. Zero-knowledge proofs and transparent proofs. Probabilistic checking of proofs. Interactive program validation.
  • Kolmogorov complexity. Lower bounds proof technique based on Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • Complexity theory retrospective. Edited by Lane A. Hemaspaandra - Alan L. Selman. New York: Springer-Verlag, 1997, xi, 339. ISBN 0387949739. info
  • GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. info
  • BALCÁZAR, José Luis, Josep DÍAZ and Joaquim GABARRÓ. Structural complexity I. Berlín: Springer-Verlag, 1995, xiii, 208. ISBN 3-540-58384-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Assessment methods (in Czech)
Během semestru studenti samostatně řeší zadané problémy. Řešení jsou základem pro určení závěrečného hodnocení.
Language of instruction
Czech
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i017.html
The course is also listed under the following terms Autumn 1995, Autumn 1996, Autumn 1997, Autumn 1998, Spring 2000, Spring 2001, Spring 2002.

I017 Structural Complexity

Faculty of Informatics
Spring 2002
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Timetable
Wed 8:00–9:50 B003
Prerequisites
I012 Complexity
The course expands on I012.
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
  • More on complexity classes; their structure and properties. Comparison of various complexity measures.
  • Lower bound techniques.
  • The polynomial hierarchy.
  • Computation that counts.
  • Alternation and games. Games against nature and interactive protocols.
  • Interactive proof systems. Zero-knowledge proofs and transparent proofs. Probabilistic checking of proofs. Interactive program validation.
  • Kolmogorov complexity. Lower bounds proof technique based on Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • Complexity theory retrospective. Edited by Lane A. Hemaspaandra - Alan L. Selman. New York: Springer-Verlag, 1997, xi, 339. ISBN 0387949739. info
  • GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. info
  • BALCÁZAR, José Luis, Josep DÍAZ and Joaquim GABARRÓ. Structural complexity I. Berlín: Springer-Verlag, 1995, xiii, 208. ISBN 3-540-58384-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Assessment methods (in Czech)
Během semestru studenti samostatně řeší zadané problémy. Řešení jsou základem pro určení závěrečného hodnocení.
Language of instruction
Czech
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i017.html
The course is also listed under the following terms Autumn 1995, Autumn 1996, Autumn 1997, Autumn 1998, Spring 2000, Spring 2001, Spring 2003.

I017 Structural Complexity

Faculty of Informatics
Spring 2001
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Timetable
Tue 8:00–9:50 B411
Prerequisites
I012 Complexity
The course expands on I012.
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
  • More on complexity classes; their structure and properties. Comparison of various complexity measures.
  • Lower bound techniques.
  • The polynomial hierarchy.
  • Computation that counts.
  • Alternation and games. Games against nature and interactive protocols.
  • Interactive proof systems. Zero-knowledge proofs and transparent proofs. Probabilistic checking of proofs. Interactive program validation.
  • Kolmogorov complexity. Lower bounds proof technique based on Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • Complexity theory retrospective. Edited by Lane A. Hemaspaandra - Alan L. Selman. New York: Springer-Verlag, 1997, xi, 339. ISBN 0387949739. info
  • GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. info
  • BALCÁZAR, José Luis, Josep DÍAZ and Joaquim GABARRÓ. Structural complexity I. Berlín: Springer-Verlag, 1995, xiii, 208. ISBN 3-540-58384-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Assessment methods (in Czech)
Během semestru studenti samostatně řeší zadané problémy. Řešení jsou základem pro určení závěrečného hodnocení.
Language of instruction
Czech
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i017.html
The course is also listed under the following terms Autumn 1995, Autumn 1996, Autumn 1997, Autumn 1998, Spring 2000, Spring 2002, Spring 2003.

I017 Structural Complexity

Faculty of Informatics
Spring 2000
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Prerequisites
I012 Complexity
The course expands on I012.
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
  • More on complexity classes; their structure and properties. Comparison of various complexity measures.
  • Lower bound techniques.
  • The polynomial hierarchy.
  • Computation that counts.
  • Alternation and games. Games against nature and interactive protocols.
  • Interactive proof systems. Zero-knowledge proofs and transparent proofs. Probabilistic checking of proofs. Interactive program validation.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • Complexity theory retrospective. Edited by Lane A. Hemaspaandra - Alan L. Selman. New York: Springer-Verlag, 1997, xi, 339. ISBN 0387949739. info
  • GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. info
  • BALCÁZAR, José Luis, Josep DÍAZ and Joaquim GABARRÓ. Structural complexity I. Berlín: Springer-Verlag, 1995, xiii, 208. ISBN 3-540-58384-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Assessment methods (in Czech)
Během semestru studenti samostatně řeší zadané problémy. Řešení jsou základem pro určení závěrečného hodnocení.
Language of instruction
Czech
Further Comments
The course is taught annually.
The course is taught: every week.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i017.html
The course is also listed under the following terms Autumn 1995, Autumn 1996, Autumn 1997, Autumn 1998, Spring 2001, Spring 2002, Spring 2003.

I017 Structural Complexity

Faculty of Informatics
Autumn 1998
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
I012 Complexity
The course expands on I012.
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
  • More on complexity classes; their structure and properties. Comparison of various complexity measures.
  • Lower bound techniques.
  • The polynomial hierarchy.
  • Computation that counts.
  • Alternation and games. Games against nature and interactive protocols.
  • Interactive proof systems. Zero-knowledge proofs and transparent proofs. Probabilistic checking of proofs. Interactive program validation.
Language of instruction
Czech
Further Comments
The course is taught annually.
The course is taught: every week.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i017.html
The course is also listed under the following terms Autumn 1995, Autumn 1996, Autumn 1997, Spring 2000, Spring 2001, Spring 2002, Spring 2003.

I017 Structural Complexity

Faculty of Informatics
Autumn 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
I012 Complexity
The course expands on I012.
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
  • More on complexity classes; their structure and properties. Comparison of various complexity measures.
  • Lower bound techniques.
  • The polynomial hierarchy.
  • Computation that counts.
  • Alternation and games. Games against nature and interactive protocols.
  • Interactive proof systems. Zero-knowledge proofs and transparent proofs. Probabilistic checking of proofs. Interactive program validation.
Language of instruction
Czech
Teacher's information
http://www.fi.muni.cz/usr/cerna/i017.html
The course is also listed under the following terms Autumn 1995, Autumn 1996, Autumn 1998, Spring 2000, Spring 2001, Spring 2002, Spring 2003.

I017 Structural Complexity

Faculty of Informatics
Autumn 1996
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
The course expands on I012.
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
  • More on complexity classes; their structure and properties. Comparison of various complexity measures.
  • Lower bound techniques.
  • The polynomial hierarchy.
  • Computation that counts.
  • Alternation and games. Games against nature and interactive protocols.
  • Interactive proof systems. Zero-knowledge proofs and transparent proofs. Probabilistic checking of proofs. Interactive program validation.
Language of instruction
Czech
Teacher's information
http://www.fi.muni.cz/usr/cerna/i017.html
The course is also listed under the following terms Autumn 1995, Autumn 1997, Autumn 1998, Spring 2000, Spring 2001, Spring 2002, Spring 2003.

I017 Structural Complexity

Faculty of Informatics
Autumn 1995
Extent and Intensity
0/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
The course expands on I012.
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
  • More on complexity classes; their structure and properties. Comparison of various complexity measures.
  • Lower bound techniques.
  • The polynomial hierarchy.
  • Computation that counts.
  • Alternation and games. Games against nature and interactive protocols.
  • Interactive proof systems. Zero-knowledge proofs and transparent proofs. Probabilistic checking of proofs. Interactive program validation.
Language of instruction
Czech
Teacher's information
http://www.fi.muni.cz/usr/cerna/i017.html
The course is also listed under the following terms Autumn 1996, Autumn 1997, Autumn 1998, Spring 2000, Spring 2001, Spring 2002, Spring 2003.
  • Enrolment Statistics (recent)