IB107 Computability and Complexity

Faculty of Informatics
Autumn 2024
Extent and Intensity
2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Taught in person.
Teacher(s)
prof. RNDr. Jan Strejček, Ph.D. (lecturer)
Mgr. Jakub Balabán (seminar tutor)
RNDr. Martin Jonáš, Ph.D. (seminar tutor)
doc. RNDr. Petr Novotný, Ph.D. (seminar tutor)
Bc. David Dokoupil (assistant)
Bc. Ondřej Huvar (assistant)
RNDr. David Klaška (assistant)
Mgr. Martin Kurečka (assistant)
Bc. Tomáš Macháček (assistant)
RNDr. Vojtěch Suchánek (assistant)
Bc. Jakub Šárník (assistant)
Bc. Adéla Štěpková (assistant)
Guaranteed by
prof. RNDr. Jan Strejček, Ph.D.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Prerequisites (in Czech)
IB005 Formal languages and Automata
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 36 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of the use of computers and the implications that these limitations have for the developent of information technology.
At the end of the course, the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties), and to apply them in some simple cases.
Learning outcomes
After enrolling the course student will be able to:
- use asymptotic notation, both actively and passively;
- explain difference between complexity of an algorithm and of a problem;
- independently decide to which complexity class a given problem belongs;
- do practical decisions based on a complexity classification of a particular problem;
- explain that some problems are not computable, give examples of such problems;
- explain the difference between various classes of not-computable problems;
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable, and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems.
  • Reduction and completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, support sessions, homeworks
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written open-book exam. Student can attend the final exam providing she/he has acquired a given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
The course is taught: every week.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2023
Extent and Intensity
2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Taught in person.
Teacher(s)
prof. RNDr. Jan Strejček, Ph.D. (lecturer)
Mgr. Jakub Balabán (seminar tutor)
RNDr. Martin Jonáš, Ph.D. (seminar tutor)
doc. RNDr. Petr Novotný, Ph.D. (seminar tutor)
Bc. David Dokoupil (assistant)
Bc. Ondřej Huvar (assistant)
RNDr. David Klaška (assistant)
Mgr. Martin Kurečka (assistant)
Bc. Tomáš Macháček (assistant)
RNDr. Vojtěch Suchánek (assistant)
Bc. Jakub Šárník (assistant)
Bc. Adéla Štěpková (assistant)
Guaranteed by
prof. RNDr. Jan Strejček, Ph.D.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 10:00–11:50 D1
  • Timetable of Seminar Groups:
IB107/A: Mon 16:00–16:50 A218, J. Strejček
IB107/02: Thu 16:00–16:50 A218, J. Balabán
IB107/03: Tue 16:00–16:50 A218, M. Jonáš
IB107/04: Tue 17:00–17:50 A218, M. Jonáš
IB107/05: Thu 9:00–9:50 A318, P. Novotný
IB107/06: Mon 17:00–17:50 A218, J. Strejček
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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 60 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties), and to apply them in some simple cases.
Learning outcomes
After enrolling the course student will be able to:
- use asymptotic notation, both actively and passively;
- explain difference between complexity of an algorithm and of a problem;
- independently decide to which complexity class a given problem belongs;
- do practical decisions based on a complexity classification of a particular problem;
- explain that some problems are not computable, give examples of such problems;
- explain the difference between various classes of not-computable problems;
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable, and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems.
  • Reduction and completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, support sessions, homeworks
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written open-book exam. Student can attend the final exam providing she/he has acquired a given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2022
Extent and Intensity
2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Taught in person.
Teacher(s)
prof. RNDr. Jan Strejček, Ph.D. (lecturer)
Mgr. Marek Jankola (seminar tutor)
Bc. Tomáš Macháček (seminar tutor)
doc. RNDr. Petr Novotný, Ph.D. (seminar tutor)
Mgr. Jakub Balabán (assistant)
Bc. Ondřej Huvar (assistant)
RNDr. Martin Jonáš, Ph.D. (assistant)
RNDr. David Klaška (assistant)
Mgr. Martin Kurečka (assistant)
RNDr. Vojtěch Suchánek (assistant)
Guaranteed by
prof. RNDr. Jan Strejček, Ph.D.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 12:00–13:50 D3
  • Timetable of Seminar Groups:
IB107/A: Tue 11:00–11:50 A218, J. Strejček
IB107/01: Mon 12:00–12:50 A319, M. Jankola
IB107/02: Mon 13:00–13:50 A319, M. Jankola
IB107/03: Mon 8:00–8:50 C511, T. Macháček
IB107/04: Mon 9:00–9:50 C511, T. Macháček
IB107/05: Thu 10:00–10:50 C525, P. Novotný
IB107/06: Thu 11:00–11:50 C525, P. Novotný
IB107/07: Tue 10:00–10:50 A218, J. Strejček
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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 60 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties), and to apply them in some simple cases.
Learning outcomes
After enrolling the course student will be able to:
- use asymptotic notation, both actively and passively;
- explain difference between complexity of an algorithm and of a problem;
- independently decide to which complexity class a given problem belongs;
- do practical decisions based on a complexity classification of a particular problem;
- explain that some problems are not computable, give examples of such problems;
- explain the difference between various classes of not-computable problems;
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable, and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems.
  • Reduction and completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, support sessions, homeworks
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written open-book exam. Student can attend the final exam providing she/he has acquired a given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2021
Extent and Intensity
2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Taught in person.
Teacher(s)
prof. RNDr. Jan Strejček, Ph.D. (lecturer)
Mgr. Jakub Balabán (seminar tutor)
RNDr. David Klaška (seminar tutor)
Mgr. Martin Kurečka (seminar tutor)
doc. RNDr. Petr Novotný, Ph.D. (seminar tutor)
RNDr. Samuel Pastva, Ph.D. (seminar tutor)
Bc. Ondřej Huvar (assistant)
Mgr. Marek Jankola (assistant)
Mgr. Juraj Major (assistant)
RNDr. Kristýna Pekárková (assistant)
Guaranteed by
prof. RNDr. Jan Strejček, Ph.D.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Tue 14. 9. to Tue 7. 12. Tue 10:00–11:50 D1
  • Timetable of Seminar Groups:
IB107/A: Mon 13. 9. to Mon 6. 12. Mon 15:00–15:50 A320, J. Strejček
IB107/01: Mon 13. 9. to Mon 6. 12. Mon 14:00–14:50 A320, J. Balabán
IB107/02: Wed 15. 9. to Wed 8. 12. Wed 14:00–14:50 A318, except Wed 10. 11. ; and Wed 10. 11. 14:00–14:50 D1, D. Klaška
IB107/03: Fri 17. 9. to Fri 10. 12. Fri 9:00–9:50 C511, M. Kurečka
IB107/04: Thu 16. 9. to Thu 9. 12. Thu 14:00–14:50 A320, P. Novotný
IB107/05: Thu 16. 9. to Thu 9. 12. Thu 15:00–15:50 A320, P. Novotný
IB107/07: Tue 14. 9. to Tue 7. 12. Tue 12:00–12:50 C525, S. Pastva
IB107/08: Thu 16. 9. to Thu 9. 12. Thu 12:00–12:50 A319, J. Strejček
IB107/09: Thu 16. 9. to Thu 9. 12. Thu 13:00–13:50 A319, J. Strejček
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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 60 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties), and to apply them in some simple cases.
Learning outcomes
After enrolling the course student will be able to:
- use asymptotic notation, both actively and passively;
- explain difference between complexity of an algorithm and of a problem;
- independently decide to which complexity class a given problem belongs;
- do practical decisions based on a complexity classification of a particular problem;
- explain that some problems are not computable, give examples of such problems;
- explain the difference between various classes of not-computable problems;
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, support sessions, homeworks
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2020
Extent and Intensity
2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Taught online.
Teacher(s)
prof. RNDr. Jan Strejček, Ph.D. (lecturer)
Mgr. Marek Jankola (seminar tutor)
doc. RNDr. Petr Novotný, Ph.D. (seminar tutor)
RNDr. Samuel Pastva, Ph.D. (seminar tutor)
Zbyněk Cincibus (assistant)
Mgr. Adam Kabela, Ph.D. (assistant)
Mgr. Juraj Major (assistant)
RNDr. Kristýna Pekárková (assistant)
RNDr. Vojtěch Suchánek (assistant)
Guaranteed by
prof. RNDr. Jan Strejček, Ph.D.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 12:00–13:50 D3
  • Timetable of Seminar Groups:
IB107/A: Mon 11:00–11:50 A218, P. Novotný, J. Strejček
IB107/01: Mon 10:00–10:50 A218, M. Jankola, J. Strejček
IB107/02: Mon 16:00–16:50 A320, M. Jankola, S. Pastva
IB107/03: Wed 16:00–16:50 C525, P. Novotný, S. Pastva
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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 60 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties), and to apply them in some simple cases.
Learning outcomes
After enrolling the course student will be able to:
- use asymptotic notation, both actively and passively;
- explain difference between complexity of an algorithm and of a problem;
- independently decide to which complexity class a given problem belongs;
- do practical decisions based on a complexity classification of a particular problem;
- explain that some problems are not computable, give examples of such problems;
- explain the difference between various classes of not-computable problems;
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, support sessions, homeworks
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2019
Extent and Intensity
2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Daniel Kráľ, Ph.D., DSc. (lecturer)
doc. RNDr. Petr Novotný, Ph.D. (seminar tutor)
RNDr. Samuel Pastva, Ph.D. (seminar tutor)
RNDr. Kristýna Pekárková (assistant)
Guaranteed by
prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 12:00–13:50 D1
  • Timetable of Seminar Groups:
IB107/01: each even Thursday 8:00–9:50 A218, D. Kráľ
IB107/02: each odd Thursday 8:00–9:50 A218, D. Kráľ
IB107/03: each even Tuesday 10:00–11:50 C525, P. Novotný
IB107/04: each odd Tuesday 10:00–11:50 C525, P. Novotný
IB107/05: each even Monday 8:00–9:50 A320, P. Novotný
IB107/06: each odd Monday 8:00–9:50 A320, P. Novotný
IB107/07: each even Monday 10:00–11:50 A319, S. Pastva
IB107/08: each odd Monday 10:00–11:50 A319, S. Pastva
IB107/09: each even Thursday 14:00–15:50 C511, S. Pastva
IB107/10: each odd Thursday 14:00–15:50 C511, S. Pastva
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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 60 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties) and to apply them in some simple cases.
Learning outcomes
After enrolling the course student will be able to: - use asymptotic notation, both actively and passively;
- explain difference between complexity of an algorith and of a problem.;
- independently decid to which complexity class given problem belongs;
- do practical decisions based on a complexity classification of a paticular problem;
- explain that some problems are not computable, give examples of such problems;
- explain the difference between various classes of not-computable problems;
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, support sessions, homeworks
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2018
Extent and Intensity
2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Daniel Kráľ, Ph.D., DSc. (lecturer)
doc. RNDr. Petr Novotný, Ph.D. (seminar tutor)
RNDr. Samuel Pastva, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Fri 10:00–11:50 D1
  • Timetable of Seminar Groups:
IB107/01: each even Thursday 8:00–9:50 A218, D. Kráľ
IB107/02: each odd Thursday 8:00–9:50 A218, D. Kráľ
IB107/03: Mon 17. 9. to Mon 10. 12. each even Monday 8:00–9:50 C416, P. Novotný
IB107/04: Mon 17. 9. to Mon 10. 12. each odd Monday 8:00–9:50 C416, P. Novotný
IB107/05: each even Wednesday 12:00–13:50 A318, P. Novotný
IB107/06: each odd Wednesday 12:00–13:50 A318, P. Novotný
IB107/07: each even Monday 10:00–11:50 C525, S. Pastva
IB107/08: Mon 17. 9. to Mon 10. 12. each odd Monday 10:00–11:50 C525, S. Pastva
IB107/09: each even Monday 12:00–13:50 C525, S. Pastva
IB107/10: Mon 17. 9. to Mon 10. 12. each odd Monday 12:00–13:50 C525, S. Pastva
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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 23 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties) and to apply them in some simple cases.
Learning outcomes
After enrolling the course student will be able to: - use asymptotic notation, both actively and passively;
- explain difference between complexity of an algorith and of a problem.;
- independently decid to which complexity class given problem belongs;
- do practical decisions based on a complexity classification of a paticular problem;
- explain that some problems are not computable, give examples of such problems;
- explain the difference between various classes of not-computable problems;
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, homeworks, drills
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2017
Extent and Intensity
2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
doc. RNDr. Jan Bouda, Ph.D. (lecturer)
doc. Mgr. Mário Ziman, Ph.D. (seminar tutor)
RNDr. Samuel Pastva, Ph.D. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: doc. RNDr. Jan Bouda, Ph.D.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Fri 10:00–11:50 D2
  • Timetable of Seminar Groups:
IB107/01: each even Wednesday 18:00–19:50 B204, J. Bouda
IB107/02: each odd Wednesday 18:00–19:50 B204, M. Ziman
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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 23 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties) and to apply them in some simple cases.
Learning outcomes
After enrolling the course student will be able to: - use asymptotic notation, both actively and passively;
- explain difference between complexity of an algorith and of a problem.;
- independently decid to which complexity class given problem belongs;
- do practical decisions based on a complexity classification of a paticular problem;
- explain that some problems are not computable, give examples of such problems;
- explain the difference between various classes of not-computable problems;
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, homeworks, drills
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2016
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
RNDr. Tomáš Effenberger, Ph.D. (seminar tutor)
Mgr. Bc. Tomáš Janík (seminar tutor)
RNDr. Samuel Pastva, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 14:00–15:50 D2
  • Timetable of Seminar Groups:
IB107/01: Wed 16:00–16:50 B411, S. Pastva
IB107/03: Thu 9:00–9:50 B411, T. Effenberger
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata, Grammars, 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 23 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties) and to apply them in some simple cases.
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, homeworks, drills
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2015
Extent and Intensity
2/2. 4 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
RNDr. Tomáš Effenberger, Ph.D. (seminar tutor)
Mgr. Bc. Tomáš Janík (seminar tutor)
RNDr. Samuel Pastva, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Tue 10:00–11:50 D1
  • Timetable of Seminar Groups:
IB107/T01: Tue 22. 9. to Tue 22. 12. Tue 15:00–16:35 116, T. Janík, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB107/01: Thu 14:00–15:50 B204, S. Pastva
IB107/02: Thu 12:00–13:50 B411, T. Effenberger
IB107/03: Fri 8:00–9:50 C416, S. Pastva
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata, Grammars, 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 23 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties) and to apply them in some simple cases.
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, homeworks, drills
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2014
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
doc. RNDr. Milan Češka, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 10:00–11:50 D2
  • Timetable of Seminar Groups:
IB107/01: Wed 15:00–15:50 C416, M. Češka
IB107/02: Wed 14:00–14:50 C416, M. Češka
IB107/03: Tue 17:00–17:50 B411, M. Češka
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata, Grammars, 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 23 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties) and to apply them in some simple cases.
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, homeworks, drills
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2013
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
doc. RNDr. Milan Češka, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Wed 12:00–13:50 D2
  • Timetable of Seminar Groups:
IB107/01: Thu 12:00–12:50 G330, M. Češka
IB107/02: Thu 13:00–13:50 G330, M. Češka
IB107/03: Tue 17:00–17:50 B411, M. Češka
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata, Grammars, 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 23 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
At the end of the course the students will be able: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties) and to apply them in some simple cases.
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, homeworks, drills
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2012
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
RNDr. Mgr. Jana Dražanová, Ph.D. (seminar tutor)
doc. RNDr. Milan Češka, Ph.D. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 10:00–11:50 D2
  • Timetable of Seminar Groups:
IB107/01: Thu 14:00–14:50 G123, J. Dražanová
IB107/02: Thu 15:00–15:50 G123, J. Dražanová
IB107/03: Thu 16:00–16:50 G123, J. Dražanová
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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 23 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
The main goals are: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties).
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, homeworks, drills
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2011
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
doc. RNDr. Milan Češka, Ph.D. (seminar tutor)
RNDr. Mgr. Jana Dražanová, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Timetable
Thu 9:00–11:50 D2
  • Timetable of Seminar Groups:
IB107/01: Thu 12:00–12:50 G123, M. Češka
IB107/02: Thu 13:00–13:50 G123, M. Češka
IB107/03: Wed 16:00–16:50 G125, J. Dražanová
IB107/04: Wed 17:00–17:50 G125, J. Dražanová
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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 23 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
The main goals are: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties).
Syllabus
  • Algorithms and models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems. Computable functions.
  • Closure properties. Rice theorems.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, homeworks, drills
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2010
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
doc. RNDr. Milan Češka, Ph.D. (seminar tutor)
RNDr. Mgr. Jana Dražanová, Ph.D. (seminar tutor)
RNDr. Jakub Chaloupka, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Timetable
Thu 10:00–11:50 D3
  • Timetable of Seminar Groups:
IB107/01: Mon 13:00–13:50 B204, M. Češka
IB107/02: Wed 10:00–10:50 B011, J. Dražanová
IB107/03: Wed 11:00–11:50 B011, J. Dražanová
IB107/04: Mon 12:00–12:50 B204, M. Češka
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
The main goals are: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties).
Syllabus
  • Problems and algorithms.
  • Algorithms and models of computation. Basic models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems.
  • Closure properties. Post correspondence problem. Selected undecidable problems in the theory of languages.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, homeworks, drills
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2009
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
doc. RNDr. Milan Češka, Ph.D. (seminar tutor)
RNDr. Jakub Chaloupka, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Timetable
Thu 14:00–16:50 A107
  • Timetable of Seminar Groups:
IB107/01: Wed 12:00–12:50 B204, J. Chaloupka
IB107/02: Wed 13:00–13:50 B204, J. Chaloupka
IB107/03: Thu 18:00–18:50 B007, M. Češka
IB107/04: Thu 19:00–19:50 B007, M. Češka
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
The main goals are: to understand basic notions of computability and complexity; to understand the main techniques used to classify problems (reductions, diagonalisation, closure properties).
Syllabus
  • Problems and algorithms.
  • Algorithms and models of computation. Basic models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems.
  • Closure properties. Post correspondence problem. Selected undecidable problems in the theory of languages.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completeness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Teaching methods
lectures, homeworks, drills
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2008
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
RNDr. Jakub Chaloupka, Ph.D. (assistant)
RNDr. Pavel Šimeček, Ph.D. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Timetable
Thu 9:00–11:50 A107
  • Timetable of Seminar Groups:
IB107/01: Tue 17:00–17:50 B204, J. Chaloupka
IB107/02: Tue 18:00–18:50 B204, J. Chaloupka
IB107/04: Mon 12:00–12:50 B011, P. Šimeček
IB107/05: Mon 13:00–13:50 B011, P. Šimeček
Prerequisites (in Czech)
IB005 Formal languages and Automata || IB102 Automata and Grammars
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
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
The main goals are: to understand basic notions of computabillity and complexity; to understand the main techniquies used to classify problems (reductions, diagonalization, closure properties).
Syllabus
  • Problems and algorithms.
  • Algorithms and models of computation. Basic models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems.
  • Closure properties. Post correspondence problem. Selected undecidable problems in the theory of languages.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
  • Non-sequential models of computation. Parallel computational thesis.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Assessment methods
The course has a form of a lecture with a seminar. During the term students are assigned homeworks. The course is concluded by the written exam. Student can attend the final exam providing she/he has acquired given number of points from homeworks.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2007
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
RNDr. Jakub Chaloupka, Ph.D. (assistant)
RNDr. Pavel Šimeček, Ph.D. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Timetable
Thu 10:00–11:50 A107
  • Timetable of Seminar Groups:
IB107/01: Mon 16:00–16:50 B410, J. Chaloupka
IB107/02: Mon 17:00–17:50 B410, J. Chaloupka
IB107/03: Mon 8:00–8:50 B410, P. Šimeček
IB107/04: Mon 9:00–9:50 B410, P. Šimeček
Prerequisites (in Czech)
IB005 Formal languages and Automata
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
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
Syllabus
  • Problems and algorithms.
  • Algorithms and models of computation. Basic models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems.
  • Closure properties. Post correspondence problem. Selected undecidable problems in the theory of languages.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
  • Non-sequential models of computation. Parallel computational thesis.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Assessment methods (in Czech)
Zkouška je písemná a ústní. V případě zadání průběžných testů během semestru, mají tyto podíl nejvýše 30% na závěrečném hodnocení. Pomocné materiály nejsou povoleny.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2006
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
doc. RNDr. Jan Bouda, Ph.D. (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
RNDr. Jakub Chaloupka, Ph.D. (assistant)
Mgr. Pavel Moravec (assistant)
RNDr. Pavel Šimeček, Ph.D. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Timetable
Thu 10:00–11:50 D2
  • Timetable of Seminar Groups:
IB107/01: Wed 14:00–14:50 B007, J. Bouda
IB107/02: Wed 15:00–15:50 B007, J. Bouda
IB107/03: Thu 12:00–12:50 B007, J. Strejček
IB107/04: Thu 13:00–13:50 B007, J. Strejček
Prerequisites (in Czech)
IB005 Formal languages and Automata || I005 Formal Languages and Automata I || I505 Formal Languages and Automata I
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 11 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
Syllabus
  • Problems and algorithms.
  • Algorithms and models of computation. Basic models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems.
  • Closure properties. Post correspondence problem. Selected undecidable problems in the theory of languages.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
  • Non-sequential models of computation. Parallel computational thesis.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Assessment methods (in Czech)
Zkouška je písemná a ústní. V případě zadání průběžných testů během semestru, mají tyto podíl nejvýše 30% na závěrečném hodnocení. Pomocné materiály nejsou povoleny.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2005
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
doc. RNDr. Ivan Kopeček, CSc. (seminar tutor)
doc. Mgr. Jan Obdržálek, PhD. (seminar tutor)
RNDr. Jan Flasar, Ph.D. (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Timetable
Thu 15:00–16:50 D2
  • Timetable of Seminar Groups:
IB107/01: Thu 10:00–10:50 B007, I. Kopeček
IB107/02: Thu 11:00–11:50 B007, J. Obdržálek
IB107/03: Thu 12:00–12:50 B011, J. Obdržálek
IB107/04: Thu 13:00–13:50 B011, J. Obdržálek
Prerequisites (in Czech)
IB005 Formal languages and Automata || I005 Formal Languages and Automata I || I505 Formal Languages and Automata I
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 11 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
Syllabus
  • Problems and algorithms.
  • Algorithms and models of computation. Basic models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems.
  • Closure properties. Post correspondence problem. Selected undecidable problems in the theory of languages.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
  • Non-sequential models of computation. Parallel computational thesis.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Assessment methods (in Czech)
Zkouška je písemná a ústní. V případě zadání průběžných testů během semestru, mají tyto podíl nejvýše 30% na závěrečném hodnocení. Pomocné materiály nejsou povoleny.
Language of instruction
Czech
Follow-Up Courses
Further Comments
Study Materials
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2004
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
Mgr. Jiří Šimša (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Timetable
Thu 9:00–11:50 D2
  • Timetable of Seminar Groups:
IB107/01: each even Thursday 12:00–13:50 B003, J. Šimša
IB107/02: each odd Thursday 12:00–13:50 B003, J. Šimša
IB107/03: each even Thursday 16:00–17:50 A107, J. Strejček
IB107/04: each odd Thursday 16:00–17:50 A107, J. Strejček
Prerequisites (in Czech)
IB005 Formal languages and Automata || I005 Formal Languages and Automata I || I505 Formal Languages and Automata I
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 11 fields of study the course is directly associated with, display
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
Syllabus
  • Problems and algorithms.
  • Algorithms and models of computation. Basic models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems.
  • Closure properties. Post correspondence problem. Selected undecidable problems in the theory of languages.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
  • Non-sequential models of computation. Parallel computational thesis.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Assessment methods (in Czech)
Zkouška je písemná a ústní. V případě zadání průběžných testů během semestru, mají tyto podíl nejvýše 30% na závěrečném hodnocení. Pomocné materiály nejsou povoleny.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2003, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2003
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Timetable
Thu 15:00–17:50 U5
Prerequisites (in Czech)
IB005 Formal languages and Automata || I005 Formal Languages and Automata I || I505 Formal Languages and Automata I
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
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
Syllabus
  • Problems and algorithms.
  • Algorithms and models of computation. Basic models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems.
  • Closure properties. Post correspondence problem. Selected undecidable problems in the theory of languages.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
  • Non-sequential models of computation. Parallel computational thesis.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Assessment methods (in Czech)
Zkouška je písemná a ústní. V případě zadání průběžných testů během semestru, mají tyto podíl nejvýše 30% na závěrečném hodnocení. Pomocné materiály nejsou povoleny.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/brim/IB107
The course is also listed under the following terms Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IB107 Computability and Complexity

Faculty of Informatics
Autumn 2002

The course is not taught in Autumn 2002

Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
Teacher(s)
prof. RNDr. Luboš Brim, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Luboš Brim, CSc.
Prerequisites (in Czech)
IB005 Formal languages and Automata
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
Course objectives
The course introduces basic approaches and methods for classification of problems with respect to their algorithmic solvability. It explores theoretical and practical limits of computers usage and consequences these limitations have for advancing information technologies.
Syllabus
  • Problems and algorithms.
  • Algorithms and models of computation. Basic models of computation. Church thesis.
  • Classification of problems. Decidable, undecidable and partially decidable problems.
  • Closure properties. Post correspondence problem. Selected undecidable problems in the theory of languages.
  • Computational complexity. Feasible and unfeasible problems. Polynomial computational thesis.
  • Reduction a completness in problem classes. Many-one reduction and polynomial reduction. Complete problems with respect to decidability, NP-complete problems. Applications.
  • Non-sequential models of computation. Parallel computational thesis.
Literature
  • KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
  • BOVET, D. and Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
  • KFOURY, A. J., Robert N. MOLL and Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
Language of instruction
Czech
Further Comments
The course is taught annually.
The course is taught: every week.
Listed among pre-requisites of other courses
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.