Instructors: Dr. Pavel Tumarkin
Type:
Seminar
Orgunit:
Course Name Abbreviation:
Discrete Mathematics
Credits:
7.50
Min.  Max. participants:
  
Partial Grades: Final Grade
Official Course Description:
This course is open to anyone with interest and some experience in mathematics (for others, 110100 General Mathematics and Computational Science is recommended). We also suppose that students have some experience in programming.
Discrete mathematics has various applications to cryptography and to computer science. In Perspectives of mathematics in Fall semester some overview of these topics (such as public key codes, fast multiplication some ideas of Logic) will be given.
Discrete mathematics methods and ideas have different type of organization and usually are not presented in usual courses (which are deal with continuous mathematics). It is better to say about combinatorial way of thinking (which is close to Olympiad mathematics).
The course has following targets:
1. To develop ideas and methods of combinatorics.
2. Relations with computer science.
3. Mathematical logic.
Topics are: Combinatorics, graph theory, complexity theory and computer algebra, formal langages, mathematical logic.
The mathematical logic is one of most basic subjects for mathematical thinking (more important then calculus). However, most of Logic books are difficult to read, most of their space is used to teach programming on Turing machine and other ugly objects.
In our time because students are familiar with programming, it became possible to teach logic much more effectively. Important parts of and ideas of Logic in fact was described in the Computer Science course. Instead of teaching of Turing machine and other type of formal languages it is possible to show relations between Logic and Computer Science (without loosing of exactness!). We suppose to cover: Minsky machine, Algorithmicaly unsolvability, Goedel theorem, Impossibility to express Truth in any formal Langage.
