Kursuse eesmärk on tutvustada matemaatilist aparatuuri ning õpetada rakendama matemaatilist abstraktsiooni, mida kasutatakse arvutiteaduses, algoritmianalüüsis ja krüptograafias. Kursusel keskendutakse hulgateooria, kombinatoorika, tõenäosusteooria ja graafiteooria elementidele. Põhilised teemad: Loendamine: permutatsioonid, kombinatsioonid, variatsioonid. Matemaatiline induktsioon. Fibonacci arvud. Binoomkordajad ja Pascali kolmnurk. Kombinatoorne tõenäosus. Graafiteooria elemente: puud ja graafid, hamiltoniaan, kahealuselised graafid, Euleri valem. Graafide ja kaartide värvimine, neljavärviprobleem.

This course is designed to introduce students to the techniques, algorithms, and reasoning processes involved in the study of discrete mathematical structures. Students will be introduced to set theory, deductive and inductive reasoning, elementary counting techniques, ordering, functional and equivalence relations, graphs, and trees. The aim is to give them knowledge and skills that would enable to use the basic methods of discrete mathematics in subsequent courses, in the design and analysis of algorithms, computability theory, software engineering, and computer systems.

Aine läbinud üliõpilane:
- oskab põhjendada matemaatiliselt arvuti algoritmides ja süsteemides kasutatavaid põhilisi andmetüüpe ja struktuure;
- kasutab diskreetse matemaatika teadmisi ja meetodeid erialases suhtlemises ja ülesannete lahendamisel;
- kasutab põhilisi loendamisalgoritme rakenduslike probleemide lahendamisel ja tõestab matemaatilisi väiteid induktiivse arvutuskäigu abil;
- tõestab matemaatilisi väiteid induktiivse arvutuskäigu abil,
- selgitab välja graafide ja puude põhiomadused ning kasutab neid mõisteid lihtsate rakenduste modelleerimiseks,
- kasutab matemaatilist teksti analüüsimisel ja aru saamisel.

After completing this course the student:
- can reason mathematically about basic data types and structures (such as numbers, sets, graphs, and trees) used in computer algorithms and systems,
- demonstrates an understanding of the basic concepts of set theory;
- applies fundamental counting algorithms to solve applied problems;
- proves mathematical statements by means of inductive reasoning;
- identifies the basic properties of graphs and trees and uses these concepts to model simple applications;
- communicates mathematical ideas in both written and oral form.

Diskreetne matemaatika – selle tehnikad, algoritmid ja põhistruktuurid (graafikud, puud jne). Praktiliste probleemide lahendamine diskreetse matemaatika meetoditega. Loendamine: permutatsioonid, kombinatsioonid, variatsioonid. Matemaatiline induktsioon. Fibonacci arvud. Binoomkordajad ja Pascali kolmnurk. Kombinatoorne tõenäosus. Graafiteooria elemente: puud ja graafid, hamiltoniaan, kahealuselised graafid, Euleri valem. Graafide ja kaartide värvimine, neljavärviprobleem.

Discrete mathematics - its techniques, algorithms and basic structures (graphs, trees etc). Solving of practical problems with the discrete mathematics methods.Topics to be covered include elementary set theory considering basic definitions and set operations, the power set and Cartesian products basic connectives in propositional logic and their properties with emphasis on some of the methods of proving mathematical results the role of quantifiers in predicate logic and in infinitely large domain sets mathematical induction binary relations and, in particular, the equivalence relation partial order relations basic counting techniques, combinations, permutations binomial coefficients, Pascal’s triangle graph, vertices, edges, paths, cycles Eulerian and Hamiltonian graphs basic definitions and properties of trees planar graphs traveling-salesman problem graph coloring.

-

-

-

-

Course homepage: http://www.cs.ioc.ee/ITKDM/

-