456-0511/01 – Introduction to Theoretical Computer Science (UTI)

Gurantor departmentDepartment of Computer ScienceCredits6
Subject guarantordoc. Ing. Zdeněk Sawa, Ph.D.Subject version guarantordoc. Ing. Zdeněk Sawa, Ph.D.
Study levelundergraduate or graduateRequirementCompulsory
Year1Semestersummer
Study languageCzech
Year of introduction1999/2000Year of cancellation2009/2010
Intended for the facultiesFEIIntended for study typesBachelor
Instruction secured by
LoginNameTuitorTeacher giving lectures
CIH053 PhDr. Martina Číhalová, Ph.D.
CIP016 Ing. Nikola Ciprich
SNE10 Mgr. Pavla Dráždilová, Ph.D.
FRY057 Ing. Tomáš Frydrych
KOT06 Ing. Martin Kot, Ph.D.
KUC275 Ing. Štěpán Kuchař, Ph.D.
MEN059 Mgr. Marek Menšík, Ph.D.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
TAK003 Ing. Ondřej Takács
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Part-time Credit and Examination 10+0

Subject aims expressed by acquired skills and competences

The goal is to teach students to work with the basic terms of theoretical computer science, and to use them in programming. Moreover, the subject gives necessary background for further study of computer science at higher levels.

Teaching methods

Lectures
Tutorials
Project work

Summary

The subject is an indroductory course of some basic areas of theoretical computer science. Students get acquainted with essentials of logic, formal languages, automata, and computational complexity, together with some of their applications for solving problems in programming. In particular, students will learn essentials of propositional and predicate logic. They will be able to formalize propositions in terms of these logics and to use some of methods of logical deduction. They will learn about the use of finite automata, regular expressions and context-free grammars in the construction of compilers (in lexical and syntax analysis) and also for searching in text data. Students will learn some basics of the theory of computation and of the complexity theory. They will be able to analyze the computational complexity of algorithms and to use the asymptotic notation. Also the computational complexity of algorithmic problems and complexity classes will be mentioned briefly. Students will learn that some problems are computationally undecidable and how this can be proved.

Compulsory literature:

- Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, 1997. - Kozen, D.: Automata and Computability. Undergraduate Text in Computer Science, Springer Verlag, 1997. - Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison Wesley, 2006. - Huth, M., Ryan, M.: Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2004.

Recommended literature:

- Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993. - Gruska, J.: Foundation of Computing. International Thomson Computer Press, 1997.

Way of continuous check of knowledge in the course of semester

Requirements during a semester: - Two test during a semester (each for 10 points) - A written report, which must be also presented to a tutor (15 points) (topics will be assigned to students at the beginning of a semester). Requirements for a credit: - To get a credit, a student must obtain from two tests and a report together at least 20 points. Exam: - The exam is of a written form. The exam consists of three parts devoted to the following areas: - theory of formal languages and automata - computability and complexity - introduction to logic It is possible to get 65 points for the exam. To pass out the exam it is necessary to get at least 5 points from each of its parts.

E-learning

Other requirements

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: - Basics of propositional and predicate logic. - Analysis of sentences of a natural language in the language of propositional and predicate logic. - Deduction of consequences. Set theoretical / semantic proofs. - Basics of resolution method. - Formal languages - basic notions (an alphabet, a word, a language). Operations on languages. Finite automata. - Construction of finite automata. Nondeterinistic finite automata. - Transformation of nondeterministic finite automata to deterministic. Regular expressions. - Context-free grammar and languages. - Algorithmic problems. Models of computation (Turing machines and RAM machines). - Asymptotic notation. Complexity of algorithms. - Complexity of problems. Complexity classes. Reductions between problems. NP-complete problems. - Algorithmically undecidable problems. Tutorials: - Recalling of basics of the set theory, relations, functions and the graph theory. - Propositional and predicate logic. - Analysis of sentences of a natural language in the language of propositional and predicate logic. - Deduction of consequences. Set theoretical / semantic proofs. - Resolution method. - Operations with languages. - Construction of finite automata. - Transformation of nondeterministic automata to deterministic. - Regular expressions. - Context-free grammars. - Turing machines and RAM machines. - Asymptotic notation. Complexity of algorithms. - Complexity of problems. Complexity classes.

Conditions for subject completion

Full-time form (validity from: 2003/2004 Summer semester, validity until: 2009/2010 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of pointsMax. počet pokusů
Exercises evaluation and Examination Credit and Examination 100 (100) 51 1
        Examination Examination 65 (65) 15 3
                Matematická logika Written examination 22  5
                Jazyky a automaty Written examination 22  5
                Vyčíslitelnost a složitost Written examination 21  5
        Exercises evaluation Credit 35 (35) 20 1
                1. zápočtová písemka Written test 10  0
                2. zápočtová písemka Written test 10  0
                Referát Project 15  0
Mandatory attendence participation:

Show history

Conditions for subject completion and attendance at the exercises within ISP:

Show history

Occurrence in study plans

Academic yearProgrammeBranch/spec.Spec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2009/2010 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2005/2006 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2005/2006 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2005/2006 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2005/2006 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2005/2006 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2004/2005 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2004/2005 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2004/2005 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2003/2004 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2003/2004 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2003/2004 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 1 Compulsory study plan
2003/2004 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2003/2004 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2003/2004 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 1 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner

Assessment of instruction



2009/2010 Summer