Subject description - BE5B01DMG

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
BE5B01DMG Discrete Mathematics and Graphs
Roles:P Extent of teaching:3P+1S
Department:13101 Language of teaching:EN
Guarantors:Demlová M. Completion:Z,ZK
Lecturers:Gromada D. Credits:5
Tutors:Gromada D. Semester:Z

Web page:

https://math.fel.cvut.cz/en/people/russotom/Teaching/DMG21-22.html

Anotation:

The aim of the course is to introduce students to fundamentals of Discrete Mathematics with focus on electrical engineering. The content of the course covers fundamentals of propositional and predicate logic, infinite sets with focus on the notion of cardinality of sets, binary relations with focus on equivalences and partial orderings; integers, relation modulo; algebraic structures including Boolean algebras. Further, the course covers basics of the Theory of Graphs.

Study targets:

The goal of the course is to introduce students with the basic notions from discrete mathematics, namely logic, basics of set theory, binary relationsand binary operations; basics from graph theory and combinatorics.

Content:

1. Propositional logic, predicate logic, quantifiers, interpretation
2. Functions, operations on sets, countable and uncountable sets, equivalence relations, partial orders
3. Euclid algorithms, Diophantine equations, relation modulo n, operations on Zn
4. Semigroups, groups, Lagrange theorem, order of an element, the Euler function, rings and fields
5. Combinations, variations, dispositions, Pascal triangle
6. Graphs and directed graphs, walks, reachable vertices, Euler and Hamiltonian graphs, strong connectivity, spanning trees

Course outlines:

1. Foundation of Propositional logic, Boolean calculus
2. Foundation of Predicate logic, quantifiers, interpretation.
3. Sets, cardinality of sets, countable and uncountable sets.
4. Binary relations on a set, equivalence relation, partial order.
5. Integers, Euclid (extended) algorithms.
6. Relation modulo n, congruence classes Zn and operations on Zn.
7. Algebraic operations, semigroups, groups.
8. Sets together with two binary operations, Boolean algebras.
9. Rings of congruence classes Zn, fields Zp.
10. Undirected graphs, trees and spanning trees.
11. Directed graphs, strong connectivity and acyclic graphs.
12. Euler graphs and Hamiltonian graphs, coloring.
13. Combinatorics.

Exercises outline:

1. Foundation of Propositional logic, Boolean calculus
2. Foundation of Predicate logic, quantifiers, interpretation.
3. Sets, cardinality of sets, countable and uncountable sets.
4. Binary relations on a set, equivalence relation, partial order.
5. Integers, Euclid (extended) algorithms.
6. Relation modulo n, congruence classes Zn and operations on Zn.
7. Algebraic operations, semigroups, groups.
8. Sets together with two binary operations, Boolean algebras.
9. Rings of congruence classes Zn, fields Zp.
10. Undirected graphs, trees and spanning trees.
11. Directed graphs, strong connectivity and acyclic graphs.
12. Euler graphs and Hamiltonian graphs, coloring.
13. Combinatorics.

Literature:

[1] Lindsay N. Childs: A Concrete Introduction to Higher Algebra, Springer; 3rd edition (November 26, 2008), ISBN-10: 0387745270
[2] Richard Johnsonbaugh: Discrete Mathematics, Prentice Hall, 4th edition (1997), ISBN 0-13-518242-5

Requirements:

None.

Keywords:

Propositional and predicate logic, sets and their cardinality, binary relations, Euclid's algorithm, rezidual classes, semigroups, groups, undirected and directed graphs, trees, strong connectivity, acyclic graphs, combinatorics.

Subject is included into these academic programs:

Program Branch Role Recommended semester
BPEECS_2018 Common courses P 1
BEECS Common courses P 1


Page updated 27.11.2022 15:51:11, semester: L/2021-2, Z/2022-3, Z/2024-5, L/2022-3, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)