• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Discrete Mathematics

2019/2020
Учебный год
ENG
Обучение ведется на английском языке
7
Кредиты
Кто читает:
Школа бизнес-информатики
Статус:
Курс обязательный
Когда читается:
1-й курс, 3, 4 модуль

Course Syllabus

Abstract

This course covers the basics of mathematical logic, graph theory, combinatorics, and formal language theory. The emphasis is put upon the algorithmic side: mathematical results works as a support for efficient algorithms operating on graphs, strings, and, finally, parsing algorithms for regular expressions and context grammars. The course is actually twofold: besides usual «chalk-and-blackboard» mathematical part, it also includes a practical one, i.e., implementing the algorithms discussed in the course. The students are supposed and encouraged to (but not restricted to) use the Octave (GNU Octave) or the R language. This program of the “Discrete Mathematics” course (first year of study) sets the minimum requirements for knowledge and skills of students and determines the content and types of training sessions and reporting. The program is intended for teachers and training assistants leading this discipline, as well as for students of the HSE and University of London Parallel Degree Programme in Management and Digital Innovation. The "Discrete mathematics" course belongs to the basic part of the professional cycle disciplines of the working curriculum for the 2019-2020 academic year. This program was developed in accordance with the following documents: • The educational standard for the 38.03.05 specialty of the Higher School of Economics (bachelor's level) • The basic curriculum of the Management and Digital Innovation programme approved in 2019. • The working curriculum of the Management and Digital Innovation programme approved in 2019.
Learning Objectives

Learning Objectives

  • Students who successfully complete this course will learn or acquire: • basic concepts and methods of discrete mathematics necessary for further training in the programme and future professional skills • skills of using discrete mathematical methods for formalizing and solving applied problems
  • At the end of this course, the student should: • know basics of discrete mathematics necessary for further study of subsequent disciplines provided for in the basic and operational curricula; • be able to apply the ideas and methods of modern discrete mathematics to solve problems arising at the disciplines which apply this methods; • obtain the skills of applying modern tools of discrete mathematics.
Expected Learning Outcomes

Expected Learning Outcomes

  • Knows the basics of propositional logic; concepts of predicates and quantifiers; the main provisions of the theory of evidence; analyzes methods and strategies of evidence. Applies propositional logic for evidence.
  • Knows the concept of a set; foundations of the algebra of sets and Boolean algebra. Analyzes equivalence and binary relations. Performs operations on sets.
  • Knows sequences and sums; Analyzes inverse functions and composition of functions; Applies the Dirichlet principle.
  • Knows computational theory; principles of divisibility and modular arithmetic; code theory; basics of cryptography. Analyzes Hamming codes. Applies division algorithms and Euclidean algorithm; Chinese remainder theorem; Fermat factorization method.
  • Knows cycles and algorithms for matrices; recursive functions and algorithms; recurrence relations. Applies recursive functions and algorithms; homogeneous and heterogeneous linear recurrence relations; induction and recursion.
  • Knows the main points of graph theory and terminology; basic provisions of networks and flows. Analyzes oriented graphs; The paths of Euler and Hamilton. Applies graphing algorithms to solve problems; tree methods for solving network problems.
  • Knows the basic principles of combinatorics and probability theory; Bayes theorem; Markov chains. Applies the rules of sums and multiplications; combinatorial formulas. Solves probabilistic combinatorics problems.
Course Contents

Course Contents

  • Functions and matrices
    Sequences and sums. Inverse functions and composition of functions. Dirichlet principle. Special functions. Matrices. The power of sets.
  • Number theory and cryptography
    Computational theory. Divisibility and modular arithmetic. Integer representations and algorithms. Elimination of congruencies. Integral solutions of linear equations. Solutions of comparisons. The Chinese remainder theorem. Eratosthenes sieve. Method of separating Fermat multipliers. Fission algorithms and Euclid's algorithm. Chain fractions. Suitable fractions. Theory of codes. Hamming codes. Methods of comparisons. Applications of the theory of numbers: search by image, hashing functions. Cryptography. Simulation of computations.
  • Algorithms and recursion
    Cycles and algorithms for matrices. Complexity of algorithms. Algorithms of sorting. Recursive functions and algorithms. Homogeneous and inhomogeneous linear recurrence relations. Solution of linear recurrence relations. Application of recurrence relations. Finite differences. Factorial polynomials. Summation of differences. Induction and recursion. Mathematical induction. Recursive definitions and structural induction. Recursive algorithms. Efficiency of algorithms.
  • Graphs, directed graphs and trees.
    Graphs and terminology. Representation of graphs and graph isomorphism. Hamiltonian graphs. Oriented graphs. Ways of Euler and Hamilton. Algorithm for constructing a random non-oriented and oriented graph. Matrices of incidence and contiguity. Hypercubes and Gray code. Algebraic properties of graphs. Planar graphs. Coloring graphs. Weighted graphs and algorithms for finding the shortest path. Connectedness in graphs. Worshell's algorithm. Isolation of connectivity components. Euler cycles. Algorithm of Terry. Trees. Properties of trees. Application of trees. Binary search trees. Weighted trees. Spanning trees.
  • Combinatorics and Probability
    Basic combinatorial principles. Combinatorial principle of addition. Rules of the sum and multiplication. Permutations and combinations. Generalized permutations and combinations. Combinatorial formulas. Binomial theorem. Binomial coefficients and identities. Introduction to probability. Expected value and deviation. Introduction to the discrete probability. Probability theory. Bayes theorem. The chains of Markov.
  • Basics: Logic and Evidence
    Statements and logic. Conditional statements. Equivalent statements. Axiomatic systems: inferences and proofs. Completeness in propositional logic. Propositional logic and its application. Simple equivalences. Predicates and quantifiers. Calculus of predicates. Nested quantifiers. Rules of inference. Introduction to the proofs and the main provisions of the theory of proofs. Methods and strategy of evidence. Mathematical induction.
  • Set theory
    The definition of set. Operations on sets. Venn diagrams. The algebra of sets. Unification of sets. Boolean algebra and Boolean functions. Representation of Boolean functions. Functional schemes. Relations and their properties. Equivalence relations. Binary relations. Representation of relations. Equivalence and partial order relations. Inverse relations and composition of relations.
Assessment Elements

Assessment Elements

  • non-blocking Attendance
  • non-blocking Activity at class
  • non-blocking Home work
    Before the exam, if the deadline is missing.
  • non-blocking Test
  • non-blocking Exam
    During the exam for calculations is allowed to use next programs: MS Windows Calculator, MS Excel and Python. During the exam is allowed to use draft and pen for solving of tasks.
Interim Assessment

Interim Assessment

  • Interim assessment (4 module)
    0.25 * Activity at class + 0.2 * Attendance + 0.25 * Home work + 0.3 * Test
Bibliography

Bibliography

Recommended Core Bibliography

  • Conradie, W., & Goranko, V. (2015). Logic and Discrete Mathematics : A Concise Introduction, Solutions Manual. Chichester, West Sussex: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=987020
  • Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108

Recommended Additional Bibliography

  • An introduction to mathematical reasoning : numbers, sets and functions, Eccles, P. J., 2013
  • Colbourn, Charles, Dinitz, Jeffrey. Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications). – 2007. – 1016 pp.
  • Garnier, R., Taylor, J. Discrete mathematics: proofs, structures and applications. – CRC press, 2009. – 847 pp.