Lecturer(s)


Osička Petr, Mgr. Ph.D.

Kauer Martin, Mgr.

Laštovička Jan, Mgr.

Motyčková Lenka, doc. Ing. CSc.

Kolařík Miroslav, doc. RNDr. Ph.D.

Ježková Lucie, Mgr.

Procházka Pavel, Mgr.

Studnička Jan, Mgr.

Course content

Intorduction to logic (propositions, logical connectives, truth of propositions, introduction to propositional and predicate logic). Introduction to relations and sets (sets, relations, relations to computer sicence, properties of relations, partial orders, equivalences, partition and factor set, binary relations and graphs, functions and their types, bijections, finite, countable and uncountable sets). Natural numbers, number systems, binary representation of numbers. Induction and recursion. Basic combinatorial considerations. Alphabet, string, code, language. Concept of algorithm (intuitive understanding, formalizations, finite automaton as a simple example). Concept of problem (intuitive understanding, formalization, decision problems, undecidable problems). Introduction to complexity of algorithms. Reducibility of problems. Hard problems and how to cope with them. Selected applications.

Learning activities and teaching methods

Lecture, Demonstration

Learning outcomes

The students become familiar with basic concepts of introduction to computer science.
1. Knowledge Describe and comprehense basics of informatics.

Prerequisites

unspecified

Assessment methods and criteria

Oral exam, Written exam
Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam.

Recommended literature


Bělohlávek R. (2008). Úvod do informatiky. Učební text, Katedra informatiky, UP Olomouc.

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. (2001). Introduction to Algorithms. Second Edition.. MIT Press.

Goodaire E. G., Parmenter M. M. (1998). Discrete Mathematics with Graph Theory. PrenticeHall, Inc.

Grimaldi R. (1999). Discrete and Combinatorial Mathematics. An Applied Introduction. 4th ed.. Addison Wesley, Reading, MA.

Gruska J. (1997). Foundations of Computing. International Thompson Computer Press.

Maurer S. B., Ralston A. (1991). Discrete Algorithmic Mathematics. Addison Wesley.

Preparata F. P.. (1973). Introduction to Discrete Structures. For Computer Science and Engineering.. Addison Wesley, Reading, MA.
