Kursuse eesmärgiks on tutvustada matemaatilist aparatuuri, mida kasutatakse arvutiteaduses ja algoritmianalüüsis ning õpetada rakendama matemaatilist abstraktsiooni ja mudeleid keeruliste ülesannete lahendamiseks. Diskreetse matemaatika kursuse teises osaks keskendutakse eelkõige kombinatoorika ja graafiteooria elementidele ja vähesel määral ka tõenäosusteooria, arvuteooria ja kombinatoorse geomeetria tulemustele, millel on rakendusi krüptograafias, kodeerimisteoorias, lineaarplaneerimises ja arvutatavuse teoorias.

The aim of this course is to provide a base of mathematics needed to solve complex problems in computer science and analysis of algorithms. The second part of Discrete Mathematics concentrates on results and methods, mostly from the areas of combinatorics and graph theory, with a little probability, number theory and combinatorial geometry, that have applications to cryptography, linear programming, coding theory and the theory of computing.

Kursuse tulemusena peaksid kuulajad omandama: a) oskuse aru saada ja kriitiliselt analüüsida matemaatilist teksti, b) kasutada matemaatilist notatsiooni ja meetodit erialases suhtlemises ja ülesannete lahendamisel, c) teadmised ja oskused teiste arvutiteaduse ja infotehnoloogia kursuste läbimiseks.

The course enables the students to: a) read, understand and critically analyze mathematical argument, b) use the notation of mathematics clearly as a means of communication and of problem solving, c) acquire the knowledge and skills needed for the study of other related subjects in computer science and IT.

Loendamine: permutatsioonid, kombinatsioonid, variatsioonid. Matemaatiline induktsioon. Fibonacci arvud. Binoomkordajad ja Pascali kolmnurk. Kombinatoorne tõenäosus. Arvuteooria elemente: täisarvud, jaguvus ja algarvud, modulaararitmeetika, väike Fermat‘ teoreem, kongruents. Graafiteooria elemente: puud ja graafid, hamiltoniaan, kahealuselised graafid, Euleri valem. Kombinatoorne geomeetria. Graafide ja kaartide värvimine, neljavärviprobleem. Rakendused kodeerimisteoorias, keerukusteoorias ja krüptograafias.

Counting: permutations, combinations, and variations. Mathematical induction. Fibonacci numbers and Pascal’s triangle. Combinatorial probability. Elements of number theory: integers, divisors and primes, modular arithmetic and Fermat’s „little“ theorem, congruence. Elements of graph theory: trees and graphs, Hamiltonian, bipartite graphs, Euler’s formula. Combinatorial geometry. Colouring maps and graphs. Four colour theorem. Applications to coding theory, complexity and cryptography.

Eksamil on nii suuline (teooria) kui kirjalik (ülesannete lahendamine) osa. Kodu- ja kontrolltööde tulemusi võidakse arvestada lõpphinde komponendina.

Examination consists of two parts: oral (theory) and written (problem solving). Final ranking may take into account results of homework and tests made during the semester.

Ülesannete lahendamine kodutööna.

Homework: exercises of problem solving.

L. Lovász, J. Pelikan, and K. Vesztergombi. Discrete Mathematics: Elementary and Beyond, Springer, 2003.
K. H. Rosen.Discrete Mathematics and Its Applications, WCB/McGraw Hill, 7th edition, 2012.
R. Graham, D. Knuth, and O. Patashnik. Concrete Mathematics, Addison-Wesley, 1998.
Kursuse veebileht: http://www.cs.ioc.ee/DM2/

-