Diskrétní matematika a grafy

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

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

Požadavky:

Nejsou.

Osnova 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í.

Osnova 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í.

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.

Studijní materiály:

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

Poznámka:

Další informace:

https://moodle.fel.cvut.cz/courses/A8B01DMG

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Otevřené elektronické systémy (povinný předmět programu)
• Otevřené elektronické systémy (povinný předmět programu)