Introduction to logic and proofs; propositional logic, propositional equivalences, predicates and quantifiers. Set theory; set operations, finite and infinite sets. Relations and functions; properties of binary relations, equivalence relations, partial orderings, chains and antichains. Counting; the pigeonhole principle, permutations and combinations, generating functions. Computability; languages and grammars, finite-state machines, language recognition. Graphs; planar, weighted and directed graphs, trails, paths and circuits, Euler paths and circuits, Hamilton paths and circuits, the travelling salesman problem. Trees; spanning and binary trees, algorithms for trees and graphs. Algorithms; complexity of algorithms, properties of integer numbers, primes and greatest common divisors, mathematical induction and recursion, discrete arithmetic functions.
On completion of 2ΚΠ02, students will be able to explain and apply the basic methods of discrete (noncontinuous) mathematics in Computer Science and Informatics. They will be able to use these methods in subsequent courses in the design and analysis of algorithms, computability theory, software engineering and computer systems. In particular, students will be able to
Mandatory written exams at the end of the semester.