456-0907/01 – Theory of Computation (TA)

Gurantor departmentDepartment of Computer ScienceCredits10
Subject guarantorprof. RNDr. Petr Jančar, CSc.Subject version guarantorprof. RNDr. Petr Jančar, CSc.
Study levelpostgraduateRequirementChoice-compulsory
YearSemesterwinter + summer
Study languageCzech
Year of introduction1997/1998Year of cancellation2009/2010
Intended for the facultiesFEIIntended for study typesDoctoral
Instruction secured by
LoginNameTuitorTeacher giving lectures
JAN59 prof. RNDr. Petr Jančar, CSc.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+0
Part-time Credit and Examination 2+0

Subject aims expressed by acquired skills and competences

On successful completion of the course, the student - understands the notions from theory of computability and complexity - is able to design algorithms suitable for practical problems - is able to analyse complexity of algorithms and categorize problems according to their complexity - masters design and analysis of approximation, probabilistic and parallel algorithms, - is able by self-study to master and present an advanced topic in theory of algorithms

Teaching methods

Lectures
Individual consultations
Project work

Summary

The course provides an exact basis for the notions of algorithmic computability nad complexity with which the students are familiar on a more or less intuitive level from their master studies. It is devoted to some advanced areas in computability and complexity (like decidability of logical theories, probabilistic algorithms, parallel computation, etc.)

Compulsory literature:

M.Sipser: Introduction to the Theory of Computation, PWS Publ. Comp. 1997 E.Borger: Computability, Complexity, Logic. North-Holland 1989 D.Harel: Algorithmics, The Spirit of Computing, Addison-Wesley1992 Hopcroft, Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley 1979

Recommended literature:

M.Sipser: Introduction to the Theory of Computation, PWS Publ. Comp. 1997 Handbook of theoretical computer science (ed. Leeuwen J.); Vol. A : Algorithms and complexity; North-Holland 1990,

Way of continuous check of knowledge in the course of semester

E-learning

Další požadavky na studenta

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Přednášky: Intuitivní pojem algoritmu a efektivní vyčíslitelné funkce. Různé matematické formalizace těchto pojmů (především Turingovy stroje a částečně rekurzivní funkce). Idea univerzálního algoritmu. Hlavní myšlenky důkazu ekvivalence uvedených matematických formalizací, Churchova teze. Problém zastavení (Halting problem), Postův korespondenční problém a další algoritmicky nerozhodnutelné problémy. Univerzální funkce, Kleeneho věta o normální formě. Rekurzivní a rekurzivně spočetné množiny, Postova věta. Věta o rekurzi, Riceova věta. Rekurzivní převeditelnost. Kreativní množiny. Rozhodnutelnost logických teorií. Časová a prostorová složitost algoritmů a problémů. P-NP problém. NP-úplnost a PSPACE-úplnost. EXPTIME, EXPSPACE, dokazatelně nezvládnutelné problémy. Aproximační algoritmy, pravděpodobnostní algoritmy. Paralelní a distribuované algoritmy. Další témata (např. alternace, krypografie, ...)

Conditions for subject completion

Full-time form (validity from: 1960/1961 Summer semester, validity until: 2008/2009 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (145) 51
        Examination Examination 100  0
        Exercises evaluation Credit 45  0
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2009/2010 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2009/2010 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology K Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2007/2008 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2006/2007 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2005/2006 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2004/2005 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2003/2004 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2002/2003 (P2612) Electrical Engineering and Computer Science (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2001/2002 (P2612) Electrical Engineering and Computer Science (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner