IB110 Introduction to Informatics

Faculty of Informatics
Autumn 2017
Extent and Intensity
2/2/0. 4 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Mgr. Ondřej Nečas (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Tue 14:00–15:50 B410
  • Timetable of Seminar Groups:
IB110/01: Wed 14:00–15:50 B410, I. Černá
Prerequisites
! IB102 Automata and Grammars && ! IB005 Formal languages and Automata
none
Course Enrolment Limitations
The course is only offered to the students of the study fields the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
The main objectives of the course is to acquaint students with the concepts, ideas, methods, and results fundamental to computer science. It is not specifically about computer technology, nor is it about computer programming. At the end of the course students should understand basics of theoretical computer science, algorithmics, and computational complexity.
Learning outcomes
After enrolling the course students are able:
- understandt the concept of algorithms,
- explain the Church - Turing hypothesis and the formal definition of the algorithm as a Turing machine,
- design simple finite automaton and Turing machine,
- explain the concept of nondeterminism,
- differentiate between recursive and nonrecursive problems,
- identify basic recursive and nonrecursive problems,
- explain the concept of computational complexity,
- identify basic polynomially solvable and hard problems.
Syllabus
  • Algorithmic problem and the algorithm that solves it. The structure of algorithms, the data they manipulate, their correctness and efficiency (mainly time efficiency). Inherent limitations of effectively executable algorithms, inefficiency and intractability. Complexity classes, the P vs NP problem. Noncomputability and undecidability.
Literature
    required literature
  • HROMKOVIČ, Juraj. Sedem divov informatiky. Ružomberok: Verbum, 2012, xi, 336. ISBN 9788080849580. info
    not specified
  • HAREL, David and Yishai A FELDMAN. Algorithmics :the spirit of computing. 3rd ed. Harlow: Addison-Wesley, 2004, xviii, 514. ISBN 0-321-11784-0. info
Teaching methods
lectures and seminars Lectures give a theoretical background which is consequently applied in seminars to specific problems and tasks
Assessment methods
Lectures and seminars with tests during the term. Final written test.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/podzim2017/IB110/index.qwarp
The course is also listed under the following terms Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2018, Autumn 2019, Spring 2020, Spring 2021, Spring 2022, Spring 2023, Spring 2024, Spring 2025.
  • Enrolment Statistics (Autumn 2017, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2017/IB110