Diskrétní matematika a grafy - A8B01DMG

Kredity 5
Semestry zimní
Zakončení zápočet a zkouška
Jazyk výuky čeština
Rozsah výuky 3P+1S
Anotace
Předmět seznamuje se základy diskrétní matematiky se zaměřením na elektrotechnické obory. Obsah předmětu pokrývá tyto okruhy:
nekonečné množiny s důrazem na pojem mohutnosti množin; binární relace s důrazem na relaci ekvivalence a
uspořádání; celá čísla, relace modulo; základní algebraické struktury včetně konečných těles. Dále se předmět zabývá
grafy a jejich základními vlastnostmi.
\\Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A8B01DMG
Cíle studia
Cílem studia je seznámit studenty se základními pojmy z diskrétní matematiky, které budou moci využít při studiu elektrotechniky.
Osnovy přednášek
1. Množiny, mohutnost množin.
2. Binární relace na množině, relace ekvivalence, uspořádání.
3. Celá čísla, Eukleidův (rozšířený) algoritmus.
4. Relace modulo n, zbytkové třídy a práce s nimi.
5. Algebraické operace, pologrupy grupy.
6. Množiny se dvěma binárními operacemi, booleovské algebry.
7. Okruhy zbytkových tříd, těleso zbytkových tříd nad prvočíslem, polynomy nad těmito tělesy.
8. Galoisova tělesa GF(2^k).
9. Homomorfismy algebraických struktur.
10. Neorientované grafy, orientované grafy, stromy a kostry.
11. Silná souvislost a acyklické grafy, topologické očíslování.
12. Kombinatorika.
13. Asymptotický růst funkcí.
Osnovy cvičení
1. Množiny, mohutnost množin.
2. Binární relace na množině, relace ekvivalence, uspořádání.
3. Celá čísla, Eukleidův (rozšířený) algoritmus.
4. Relace modulo n, zbytkové třídy a práce s nimi.
5. Algebraické operace, pologrupy grupy.
6. Množiny se dvěma binárními operacemi, booleovské algebry.
7. Okruhy zbytkových tříd, těleso zbytkových tříd nad prvočíslem, polynomy nad těmito tělesy.
8. Galoisova tělesa GF(2^k).
9. Homomorfismy algebraických struktur.
10. Neorientované grafy, orientované grafy, stromy a kostry.
11. Silná souvislost a acyklické grafy, topologické očíslování.
12. Kombinatorika.
13. Asymptotický růst funkcí.
Literatura
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
Požadavky
Nejsou.