Discrete Structures

Introduction to  mathematical logic. The concept of statement, operations over statements, truth tables. Introduction to  set theory. Set operations, power set. Methods of proof. Relations and graphs. Functions and cardinality of sets. Types of functions, enumerable and innumerable sets. The concept of operation and algebraic structures. Basic algebraic structures. Boolean algebra and algebra of sets. Axioms and basic theorems of Boolean algebras, order, algebra of sets. Boolean functions and their bases. Propositional calculus. Symbols and formulas concept, the concept of tautology and decidability. Predicate calculus. Symbols, notion of terms and formulas, valid formula. Combinatorics. Basic principles of enumeration, the principle of inclusion exclusion, permutations, combinations, partitions and compositions. Discrete probability. The concept of event, the axioms of probability theory, conditional probability, Bayes formula, random variable and its numerical characteristics. Algorithms and recursion. Recurrent equations. Graph theory. Types of graphs, sub graph types, node degree, connectivity, planarity, coloring, representations of graphs, isomorphism. Trees. Weight graphs. The theory of numbers. Theorem about sharing, Euclidean algorithm, prime factorization, modular numbers, congruencies, Chinese Remainder Theorem. Polynomials over fields. Finite fields. Elements of the theory of codes. Finite state machines. Formal languages and their machines. The complexity of algorithms and problems. Measures of complexity, Turing machine, P and NP problems

Рачунарски факултет Рачунарски факултет 011-33-48-079