Bi2011 Theoretical Fundamentals of Computer Science

Faculty of Science
Autumn 2009
Extent and Intensity
2/2. 4 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
Teacher(s)
RNDr. Miroslav Kubásek, Ph.D. (lecturer)
Guaranteed by
prof. RNDr. Ladislav Dušek, Ph.D.
RECETOX – Faculty of Science
Contact Person: RNDr. Jaroslav Ráček, Ph.D.
Timetable
Thu 9:00–12:50 F01B1/709
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
Main objectives can be summarized as follows:
to understand the fundamentals of logic, graphs, automatons and formal languages;
to expand student abstraction.
Syllabus
  • Number systems
  • Propositional calculus, Boolean algebra
  • Predicate calculus
  • Basic concepts from information theory
  • Eulerian and hamiltonian graphs
  • Skeleton graph, searching for optimal route
  • Finite automata
  • Stack automata
  • Languages and grammars, Chomsky hierarchy
  • Relationship of finite automata and regular languages
  • Relationship of stack automata and context-free languages
  • Basic methods of syntactic analysis for context-free languages
  • Linear bounded automata
  • Turing machines
Literature
  • Fuchs, E.: Diskrétní matematika a Teorie množin pro učitele (CD-ROM). Masarykova univerzita, Brno, 2000.
  • Fuchs, E.: Diskrétní matematika pro učitele. Masarykova univerzita, Brno, 2001.
  • Kolář, J., Štěpánková, O., Chytil, M.: Logika, algebra, grafy. SNTL, Praha, 1989.
  • Molnár, L', Češka, M., Melichar, B.: Gramatiky a jazyky. Alfa, Bratislava, 1987.
  • Štěpán, J.: Formální logika. FIN, Olomouc, 1995.
Teaching methods
lectures, examples
Assessment methods
Lectures, class discussion;
Final written exam.
Language of instruction
Czech
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 2007 - for the purpose of the accreditation, Autumn 2010 - only for the accreditation, Autumn 2007, Autumn 2008, Autumn 2010, Autumn 2011, Autumn 2011 - acreditation, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, autumn 2021.
  • Enrolment Statistics (Autumn 2009, recent)
  • Permalink: https://is.muni.cz/course/sci/autumn2009/Bi2011