## Discrete Mathematics and Graphs - BE5B01DMG - AY 21/22

Czech Technical University in PragueFaculty of Electrical Engineering

Bachelor Degree in Electrical Engineering and Computer Science

Academic Year 2021/2022

### Announcements:

- Students who received the assessments here (with points from Midterm+Homeworks)

### Information on the Exams:

- Exam Modalities
- Exam period: January 10, 2022 - February 13, 2022
- Dates for the written exams:
- Wednesday 5 January, 16:00-18:00, T2:C2-82
- Monday 17 January, 9:00-11:00, T2:C3-51
- Friday 21 January, 9:00-11:00, T2:C3-51
- Thursday 27 January, 9:00-11:00, T2:C3-51
- Monday 7 February, 9:00-11:00, T2:C3-51

- Dates for the (optional) oral exams:
- Friday 7 January
- Friday 21 January
- Friday 28 January
- Friday 11 February

### Contents and Materials:

Many thanks to Prof. Marie Demlova for generously sharing her notes with us.__Chapter 1__. Logic

Propositional logic, predicate logic, quantifiers, interpretation.

Materials: Lect1, Ex1, Lect2, Ex2 (also see Section 2.3 here).__Chapter 2__. Sets

Functions, operations on sets, countable and uncountable sets, equivalence relations, partial orders.

Materials: Lect3, Ex3, Lect4, Ex4.__Chapter 3__. Arithmetic

Euclid algorithms, Diophantine equations, relation modulo n, operations on Zn.

Materials: Lect5, Ex5, Lect6, Ex6.__Chapter 4__. Algebraic structures

Semigroups, groups, Lagrange theorem, order of an element, the Euler function, rings and fields.

Materials: Lect7, Ex7, Lect8, Ex8, Lect9, Ex9.__Chapter 5__. Combinatorics

Combinations, variations, dispositions, Pascal triangle.

Materials: Lect10, Ex10.__Chapter 6__. Graphs

Graphs and directed graphs, walks, reachable vertices, Euler and Hamiltonian graphs, strong connectivity, spanning trees.

Materials: Lect11, Ex11, Lect12, Ex12, Lect13, Ex13.

### References:

- L.N. Childs,
*A Concrete Introduction to Higher Algebra*, Springer. - R. Johnsonbaugh,
*Discrete Mathematics*, Prentice Hall. - K. Rosen,
*Discrete Mathematics and Its Applications*, McGraw-Hill.