Описание: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.