Discrete Mathematics (470-2301/02)
Winter Term 2018/2019
Detailed information about this course in Czech language is available on the web page of subject guarantor
doc. Mgr. Petr Kovář, Ph.D.,
Hours of Instruction
|Lecture||Monday||10:45 - 12:15||EB126
|Discussion||Monday||12:30 - 14:00||EB126
|Tuesday||9:00 - 10:30||EA 533
| -- || -- || --
Also at different times, after previous per-email agreement.
Content of the Course
- Introductory lecture (course organization).
Lecture on: Sets and set operations, cartesian product, power set, sequences, their sums and products.
- Arrangements and selections: Lecture is on simple arrangements and selections as permutations, k-permutations and k-combinations.
Further arrangements and selections with repetitions are defined: permutations with repetitions, combinations with repetitions and k-permutations with repetitions.
We state two basic counting principles - the addition principle and the multiplication principle. ALso we mention the method of double counting,
all complemented with simple examples.
- Lecture on probability: motivation problems, sample space, event, probability function, uniform probability, independent events,
conditional probability, random variable, expected values.
- Lecture on proofs: basics of logic, propositions, connectives, quantifiers, different techniques of proofs, principle of mathematical induction.
- Lecture on relations: definition of the term relation, properties of relations, equivalence relation, partial ordering relation, mappings, permutations.
- Inclusion exclusion principle.
- Algorithms for discrete structures.
- First lecture on graph theory, graphs, parity principle, Havel-Hakimi theorem, graph isomorphisms, implementation of graphs.
- Connectivity of graphs, searching through a graph, higher degrees of connectivity.
- Eulerian and hamiltonian graphs.
- Distances in a graph, metric of a graph, distances in a weighted graph, Dijkstra's algorithm.
- Basic properties of trees, rooted trees, isomorphism of trees.
- Graph colorings, drawing a graph in a plane (planar graphs).
- Flow in a network.
Writing of materials in English language is in process.
If you find mistakes in text or results of exercises I would appreciate if you let me know (preferably per email).
- Exercises 01 (on sums, products, sets operations)
- Worksheet 02 (on selections and arrangements without repetition)
Exercises 02 (on selections and arrangements without repetition)
- Worksheet 03 (on selections and arrangements with repetition and on compound arrangements and selections)
Exercises 03 (on selections and arrangements with repetition and on compound arrangements and selections)
- Worksheet 04 (on discrete probability )
Exercises 04 (on discrete probability, independent events, expected values)
- Worksheet 05 (independent events, expected values)
Exercises 05 (on discrete probability, independent events, expected values)
- Worksheet 06 (Proofs by Mathematical induction)
Exercises 06 (on proofs and proofs by Mathematical Induction)
- Worksheet 07 (on relations)
Exercises 07 (on relations)
- Worksheet 08 (Permutations and Inclusion-Eexclusion principle)
Exercises 07 (on relations)
Time Line of the Course for Winter Term 2019
Lectures and Discussions - organized in 14 weeks of the semester
|Discussion||sums, products, sets operations||
|2.||24.09.||Lecture||selections and arrangements without and with repetition||
|Discussion||selections and arrangements without repetition||
|Discussion||Arrangements and selections with repetition ||
|4.||08.10.||Lecture||Probability - Expected values, Proofs - basics of math logic||
|Discussion||Selections with repetition + Probability computations||First test - 3pts
Selections, arrangements without repetition
|5.||15.10.||Lecture||Proofs - Mathematical induction, Dirichlet's principle||
|Discussion||Probability computations, |
|Second test - 2pts
Selections, arrangements with repetition
|6.||22.10.||Lecture||Relations + glimpse to Permutations||
|Discussion||Proofs - Mathematical induction, by computation||Third test - 3pts
Probability computations, Expected values, Independent events
|7.||29.10.||Lecture||Permutations and Inclusion-Exclusion principle
||Examples on Permutations and Inclusion-Exclusion principle,
|Discussion||Relations and their properties||Fourth test - 2pts
on proofs by Math. Induction
|8.||05.11.||Lecture||Introduction to Graph theory||
|Discussion||Inclusion-Exclusion and Dirichlets principls + Graphs||Fifth test - 3pts
on properties of relations and mappings
- Discrete Mathematics and Its Applications, 7-th Edition by Kenneth H. Rosen
- Applied Combinatorics, 6-th Edition by Alan Tucker
- Introduction to Graph Theory, 2-nd Edition by Douglas B. West
grading-scales.pdf (according to overall course score)