CTU FEE Moodle
Discrete Math.& Graphs
B232 - Summer 23/24
Discrete Math.& Graphs - A8B01DMG
| Credits | 5 |
| Semesters | Winter |
| Completion | Assessment + Examination |
| Language of teaching | Czech |
| Extent of teaching | 3P+1S |
Annotation
The course introduces basic notions from discrete mathematics directed to those topics useful for electrical engineering studies. The content of the course covers: infinite sets with emphasis to cardianlity of sets, binary relations with emphasis to equivalence relations and partial ordes'; integers, relation modulo n'; basic algebraic structures (includin finite fields of characteristic 2). Furher the course contains basic notions and their applications from graph theory.
Study targets
The aim of the course is to introduce to students basic notions of discrete mathematics that will be used in their studies.
Course outlines
1. Sets. Cardinality of sets.
2. Binary relalations, equivalence relation, partial order.
3. Integers, Eclid's algorithm and Bezout's theorem
4. Relation modulo n, rezidual classes and operations with them
5. Binary operations, semigroups, groups.
6. Sets with two binary operations, Boolean algebras.
7. Rings of rezidual classes, finite fieldst of rezidual classes over a prime, polynomials
over them.
8. Galois fields GF(2^k).
9. Homomorfisms of algebraic structures.
10. Undirected graphs, directed graphs, trees and spanning trees.
11. Strongly connected and acyclic graphs, topological sort
12.Combinatorics.
13. Asymptotic growth of functions.
2. Binary relalations, equivalence relation, partial order.
3. Integers, Eclid's algorithm and Bezout's theorem
4. Relation modulo n, rezidual classes and operations with them
5. Binary operations, semigroups, groups.
6. Sets with two binary operations, Boolean algebras.
7. Rings of rezidual classes, finite fieldst of rezidual classes over a prime, polynomials
over them.
8. Galois fields GF(2^k).
9. Homomorfisms of algebraic structures.
10. Undirected graphs, directed graphs, trees and spanning trees.
11. Strongly connected and acyclic graphs, topological sort
12.Combinatorics.
13. Asymptotic growth of functions.
Exercises outlines
1. Sets. Cardinality of sets.
2. Binary relalations, equivalence relation, partial order.
3. Integers, Eclid's algorithm and Bezout's theorem
4. Relation modulo n, rezidual classes and operations with them
5. Binary operations, semigroups, groups.
6. Sets with two binary operations, Boolean algebras.
7. Rings of rezidual classes, finite fieldst of rezidual classes over a prime, polynomials
over them.
8. Galois fields GF(2^k).
9. Homomorfisms of algebraic structures.
10. Undirected graphs, directed graphs, trees and spanning trees.
11. Strongly connected and acyclic graphs, topological sort
12.Combinatorics.
13. Asymptotic growth of functions.
2. Binary relalations, equivalence relation, partial order.
3. Integers, Eclid's algorithm and Bezout's theorem
4. Relation modulo n, rezidual classes and operations with them
5. Binary operations, semigroups, groups.
6. Sets with two binary operations, Boolean algebras.
7. Rings of rezidual classes, finite fieldst of rezidual classes over a prime, polynomials
over them.
8. Galois fields GF(2^k).
9. Homomorfisms of algebraic structures.
10. Undirected graphs, directed graphs, trees and spanning trees.
11. Strongly connected and acyclic graphs, topological sort
12.Combinatorics.
13. Asymptotic growth of functions.
Literature
1. Lindsay N. Childs: A Concrete Introduction to Higher Algebra, Springer; 3rd edition (November 26, 2008),
ISBN-10: 0387745270
2. Jiří Demel: Grafy a jejich aplikace, Academia; 2002, ISBN 80-200-0990-6
3. Richard Johnsonbaugh: Discrete Mathematics, Prentice Hall, 4th edition (1997), ISBN 0-13-518242-5
ISBN-10: 0387745270
2. Jiří Demel: Grafy a jejich aplikace, Academia; 2002, ISBN 80-200-0990-6
3. Richard Johnsonbaugh: Discrete Mathematics, Prentice Hall, 4th edition (1997), ISBN 0-13-518242-5
Requirements
None.