IA012 Complexity

Faculty of Informatics
Autumn 2024
Extent and Intensity
2/0/1. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
In-person direct teaching
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Ivana Černá, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 25. 9. to Wed 18. 12. Wed 14:00–15:50 B411
Prerequisites
The course expands on course IB107 Computability and Complexity.
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
there are 29 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Learning outcomes
After enrolling the course students are able to:
- actively work with computational complexity of problems and algorithms,
- analyse upper and lower bounds of computational complexity,
- differentiate between tractable and untractable problems,
- define basic complexity classes and analyze their relationships,
- explain (NP) hardness and prove hardness of computational problems,
- describe limits of determicnistic, nondeterministic, alternating, randomized, and parallel computing paragigms.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
    required literature
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
    recommended literature
  • ARORA, Sanjeev and Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/podzim2024/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023.

IA012 Complexity

Faculty of Informatics
Autumn 2023
Extent and Intensity
2/0/1. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Ivana Černá, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 12:00–13:50 A318
Prerequisites
The course expands on course IB107 Computability and Complexity.
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
there are 49 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Learning outcomes
After enrolling the course students are able to:
- actively work with computational complexity of problems and algorithms,
- analyse upper and lower bounds of computational complexity,
- differentiate between tractable and untractable problems,
- define basic complexity classes and analyze their relationships,
- explain (NP) hardness and prove hardness of computational problems,
- describe limits of determicnistic, nondeterministic, alternating, randomized, and parallel computing paragigms.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
    required literature
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
    recommended literature
  • ARORA, Sanjeev and Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Autumn 2022
Extent and Intensity
2/0/1. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Ivana Černá, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Tue 14:00–15:50 A218
Prerequisites
The course expands on course IB107 Computability and Complexity.
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
there are 49 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Learning outcomes
After enrolling the course students are able to:
- actively work with computational complexity of problems and algorithms,
- analyse upper and lower bounds of computational complexity,
- differentiate between tractable and untractable problems,
- define basic complexity classes and analyze their relationships,
- explain (NP) hardness and prove hardness of computational problems,
- describe limits of determicnistic, nondeterministic, alternating, randomized, and parallel computing paragigms.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
    required literature
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
    recommended literature
  • ARORA, Sanjeev and Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Autumn 2021
Extent and Intensity
2/0/1. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Ivana Černá, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Tue 14. 9. to Tue 7. 12. Tue 14:00–15:50 A218
Prerequisites
The course expands on course IB107 Computability and Complexity.
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
there are 48 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Learning outcomes
After enrolling the course students are able to:
- actively work with computational complexity of problems and algorithms,
- analyse upper and lower bounds of computational complexity,
- differentiate between tractable and untractable problems,
- define basic complexity classes and analyze their relationships,
- explain (NP) hardness and prove hardness of computational problems,
- describe limits of determicnistic, nondeterministic, alternating, randomized, and parallel computing paragigms.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
    required literature
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
    recommended literature
  • ARORA, Sanjeev and Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Autumn 2020
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Ivana Černá, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 14:00–15:50 A218
Prerequisites
The course expands on course IB107 Computability and Complexity.
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
there are 48 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Learning outcomes
After enrolling the course students are able to:
- actively work with computational complexity of problems and algorithms,
- analyse upper and lower bounds of computational complexity,
- differentiate between tractable and untractable problems,
- define basic complexity classes and analyze their relationships,
- explain (NP) hardness and prove hardness of computational problems,
- describe limits of determicnistic, nondeterministic, alternating, randomized, and parallel computing paragigms.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
    required literature
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
    recommended literature
  • ARORA, Sanjeev and Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2019
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Mon 14:00–15:50 D2
Prerequisites
The course expands on course IB107 Computability and Complexity.
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
there are 19 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Learning outcomes
After enrolling the course students are able to:
- actively work with computational complexity of problems and algorithms,
- analyse upper and lower bounds of computational complexity,
- differentiate between tractable and untractable problems,
- define basic complexity classes and analyze their relationships,
- explain (NP) hardness and prove hardness of computational problems,
- describe limits of determicnistic, nondeterministic, alternating, randomized, and parallel computing paragigms.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
    required literature
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
    recommended literature
  • ARORA, Sanjeev and Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2018
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Tue 16:00–17:50 D2
Prerequisites
The course expands on course IB107 Computability and Complexity.
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
there are 19 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Learning outcomes
After enrolling the course students are able to:
- actively work with computational complexity of problems and algorithms,
- analyse upper and lower bounds of computational complexity,
- differentiate between tractable and untractable problems,
- define basic complexity classes and analyze their relationships,
- explain (NP) hardness and prove hardness of computational problems,
- describe limits of determicnistic, nondeterministic, alternating, randomized, and parallel computing paragigms.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
    required literature
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
    recommended literature
  • ARORA, Sanjeev and Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2017
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 10:00–11:50 D2
Prerequisites (in Czech)
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.
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
there are 19 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2014/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2016
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
RNDr. Mária Svoreňová, Ph.D. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 14:00–15:50 D2
Prerequisites (in Czech)
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.
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
there are 19 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2014/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2015
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
RNDr. Nikola Beneš, Ph.D. (assistant)
RNDr. Mária Svoreňová, Ph.D. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 14:00–15:50 D2
Prerequisites (in Czech)
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.
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
there are 18 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2014/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2014
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
RNDr. Nikola Beneš, Ph.D. (lecturer)
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.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Mon 12:00–13:50 B411
Prerequisites
SOUHLAS
The course is in term Spring 2014 open only for students finishing their studies for which the course is compulsory. In term Spring 2015 the course will be open for all interested students.
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
there are 18 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2014/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2013
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
RNDr. Nikola Beneš, Ph.D. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 10:00–11:50 B410
Prerequisites (in Czech)
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost
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
there are 18 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2012/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2012
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 10:00–11:50 B204
Prerequisites (in Czech)
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost
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
there are 22 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2012/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2011
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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
Thu 12:00–13:50 B410
Prerequisites (in Czech)
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost
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
there are 21 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2011/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2010
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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
Thu 12:00–13:50 B410
Prerequisites (in Czech)
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost
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
there are 21 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2010/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2009
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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
Thu 10:00–11:50 B410
Prerequisites (in Czech)
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost
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
there are 18 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2009/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2008
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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
Thu 10:00–11:50 B410
Prerequisites (in Czech)
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost
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
there are 18 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory clasiffies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Assessment methods (in Czech)
V průběhu semsestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2007
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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
Thu 10:00–11:50 B410
Prerequisites (in Czech)
! I017 Structural Complexity
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost
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
there are 6 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory clasiffies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Assessment methods (in Czech)
V průběhu semsestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2006
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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
Thu 10:00–11:50 B410
Prerequisites (in Czech)
! I017 Structural Complexity
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost
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
there are 6 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory clasiffies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Assessment methods (in Czech)
V průběhu semsestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2005
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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
Mon 12:00–13:50 B410
Prerequisites (in Czech)
! I017 Structural Complexity
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost
Course Enrolment Limitations
The course is only offered to the students of the study fields the course is directly associated with.
fields of study / plans the course is directly associated with
there are 6 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory clasiffies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Assessment methods (in Czech)
V průběhu semsestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.
Language of instruction
Czech
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html
The course is also listed under the following terms Spring 2004, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Spring 2004
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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 B410
Prerequisites (in Czech)
! I017 Structural Complexity
Znalost problematiky v rozsahu předmětu IB107 - Vyčíslitelnost a složitost.
Course Enrolment Limitations
The course is only offered to the students of the study fields the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory clasiffies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Assessment methods (in Czech)
Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na průběžné práci v semestru. Přesná specifikace požadavkú viz www stránka předmětu.
Language of instruction
Czech
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html
The course is also listed under the following terms Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Autumn 2019

The course is not taught in Autumn 2019

Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Ivana Černá, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Prerequisites
The course expands on course IB107 Computability and Complexity.
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
there are 48 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory classifies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization. The main goal of the course is to provide a comfortable introduction to moder complexity theory. While choosing the relevant topics, it places premium on choosing topics that have a concrete relationship to algorithmic problems. Students should understand and analyze complexity issues of basic algorithmic problems and compare different computing approaches.
Learning outcomes
After enrolling the course students are able to:
- actively work with computational complexity of problems and algorithms,
- analyse upper and lower bounds of computational complexity,
- differentiate between tractable and untractable problems,
- define basic complexity classes and analyze their relationships,
- explain (NP) hardness and prove hardness of computational problems,
- describe limits of determicnistic, nondeterministic, alternating, randomized, and parallel computing paragigms.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism. closure properties of space complexity classes.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
    required literature
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
    recommended literature
  • ARORA, Sanjeev and Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Teaching methods
Lectures, readings and class discusions. Students are supposed to solve problems on complexity.
Assessment methods
Lectures. Oral exam at the end of the term and individual project during the term.
Language of instruction
Czech
Further Comments
The course is taught annually.
The course is taught: every week.
Teacher's information
https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA012 Complexity

Faculty of Informatics
Autumn 2002

The course is not taught in Autumn 2002

Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
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 (in Czech)
! I017 Structural Complexity
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
there are 6 fields of study the course is directly associated with, display
Course objectives
Theory of computational complexity is about quantitative laws and limitations that govern computing. The course explores the structure of the space of of computable problems and develops techniques to reduce the search for efficient methods for the whole class of algorithmic problems to the search for efficient methods for a few key algorithmic problems. The theory clasiffies problems according to their computational complexity into feasible and unfeasible problems. Finally, the course tries to understand unfeasability can be coped with the help of techniques like randomization, approximation and parallelization.
Syllabus
  • The structure and properties of time complexity classes. Relation between determinism and nondeterminism.
  • The structure and properties of space complexity classes. Relation between determinism and nondeterminism.
  • Unfeasible problems. Hierarchy of complexity classes. Polynomial hierarchy. Relativization. Non-uniform computational complexity.
  • Randomized complexity classes and their structure. Approximative complexity classes and non-approximability.
  • Alternation and games. Interactive protocols and interactive proof systems.
  • Lower bounds techniques. Kolmogorov complexity.
  • Descriptive complexity.
Literature
  • SCHÖNING, Uwe and Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Bookmarks
https://is.muni.cz/ln/tag/FI:IA012!
Assessment methods (in Czech)
Závěrečné hodnocení je založeno na výsledcích písemné zkoušky.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
The course is taught: every week.
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.
  • Enrolment Statistics (recent)