Homepage
Výuka
Publikace
 

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

DayTimeRoom
LectureMonday10:45 - 12:15EB126
DiscussionMonday12:30 - 14:00EB126
------

Office hours

DayTimeRoom
Tuesday9:00 - 10:30EA 533
-- -- --

Also at different times, after previous per-email agreement.


Content of the Course

Lectures

  1. Introductory lecture (course organization).
    Lecture on: Sets and set operations, cartesian product, power set, sequences, their sums and products.
    dim_lecture01.pdf
  2. 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.
    dim_lecture02.pdf
  3. Lecture on probability: motivation problems, sample space, event, probability function, uniform probability, independent events, conditional probability, random variable, expected values.
    dim_lecture03.pdf
  4. Lecture on proofs: basics of logic, propositions, connectives, quantifiers, different techniques of proofs, principle of mathematical induction.
    dim_lecture04.pdf
  5. Lecture on relations: definition of the term relation, properties of relations, equivalence relation, partial ordering relation, mappings, permutations.
    dim_lecture05.pdf
  6. Inclusion exclusion principle.
    dim_lecture06.pdf
  7. Algorithms for discrete structures.
    dim_lecture07.pdf
  8. First lecture on graph theory, graphs, parity principle, Havel-Hakimi theorem, graph isomorphisms, implementation of graphs.
    dim_lecture08.pdf
  9. Connectivity of graphs, searching through a graph, higher degrees of connectivity.
    dim_lecture09.pdf
  10. Eulerian and hamiltonian graphs.
    dim_lecture10.pdf
  11. Distances in a graph, metric of a graph, distances in a weighted graph, Dijkstra's algorithm.
    dim_lecture11.pdf
  12. Basic properties of trees, rooted trees, isomorphism of trees.
    dim_lecture12.pdf
  13. Graph colorings, drawing a graph in a plane (planar graphs).
    dim_lecture13.pdf
  14. Flow in a network.
    dim_lecture14.pdf

Discussions

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).

  1. Exercises 01 (on sums, products, sets operations)
    DIM_ex_01.pdf
  2. Worksheet 02 (on selections and arrangements without repetition)
    DIM_ws2018_02.pdf
    Exercises 02 (on selections and arrangements without repetition)
    DIM_ex_02.pdf
  3. Worksheet 03 (on selections and arrangements with repetition and on compound arrangements and selections)
    DIM_ws2018_03.pdf
    Exercises 03 (on selections and arrangements with repetition and on compound arrangements and selections)
    DIM_ex_03.pdf
  4. Worksheet 04 (on discrete probability )
    DIM_ws2018_04.pdf
    Exercises 04 (on discrete probability, independent events, expected values)
    DIM_ex_04_05.pdf
  5. Worksheet 05 (independent events, expected values)
    DIM_ws2018_05.pdf
    Exercises 05 (on discrete probability, independent events, expected values)
    DIM_ex_04_05.pdf
  6. Worksheet 06 (Proofs by Mathematical induction)
    DIM_ws2018_06.pdf
    Exercises 06 (on proofs and proofs by Mathematical Induction)
    DIM_ex_06.pdf
  7. Worksheet 07 (on relations)
    DIM_ws2018_07.pdf
    Exercises 07 (on relations)
    DIM_ex_07.pdf
  8. Worksheet 08 (Permutations and Inclusion-Eexclusion principle)
    DIM_ws2018_08.pdf
    Exercises 07 (on relations)
    DIM_ex_08.pdf


Time Line of the Course for Winter Term 2019

Lectures and Discussions - organized in 14 weeks of the semester

#Date: dd.mm.ContentNotes
1.17.09.LectureIntroductory lecture
Discussionsums, products, sets operations
2.24.09.Lectureselections and arrangements without and with repetition
Discussionselections and arrangements without repetition
3.01.10.LectureDiscrete Probability
DiscussionArrangements and selections with repetition
4.08.10.LectureProbability - Expected values, Proofs - basics of math logic
DiscussionSelections with repetition + Probability computationsFirst test - 3pts
Selections, arrangements without repetition
5.15.10.LectureProofs - Mathematical induction, Dirichlet's principle
DiscussionProbability computations,
Expected values
Second test - 2pts
Selections, arrangements with repetition
6.22.10.LectureRelations + glimpse to Permutations
DiscussionProofs - Mathematical induction, by computationThird test - 3pts
Probability computations, Expected values, Independent events
7.29.10.LecturePermutations and Inclusion-Exclusion principle Examples on Permutations and Inclusion-Exclusion principle,
DiscussionRelations and their propertiesFourth test - 2pts
on proofs by Math. Induction
8.05.11.LectureIntroduction to Graph theory
DiscussionInclusion-Exclusion and Dirichlets principls + GraphsFifth test - 3pts
on properties of relations and mappings
9.12.11.Lecture
DiscussionSixth test
10.19.11.Lecture
DiscussionSevnth test
11.26.11.Lecture
DiscussionEight test
12.03.12.Lecture
DiscussionNinth test
13.10.12.Lecture
DiscussionTenth test
14.17.12.Lecture
Discussion


Sample exams



Recommended texts

  • 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

grading-scales.pdf (according to overall course score)


  Upraveno: 22.01.2018