Západočeská univerzita v Plzni
Studijní programy a katalog předmětů
pro akademický rok 2024/2025
Západočeská univerzita v Plzni
English
Hledání
FAQ

Předmět: Diskrétní matematika

« Zpět
Název předmětu Diskrétní matematika
Kód předmětu KMA/DMA
Organizační forma výuky Přednáška + Cvičení
Úroveň předmětu Bakalářský
Rok studia 2
Semestr Letní
Počet ECTS kreditů 4
Vyučovací jazyk Čeština
Statut předmětu Povinný, Volitelný
Způsob výuky Kontaktní
Studijní praxe Nejedná se o pracovní stáž
Doporučené volitelné součásti programu Není
Vyučující
  • Šebková Milena, RNDr.
  • Ekstein Jan, RNDr. Ph.D.
  • Teska Jakub, RNDr. Mgr. Ph.D.
  • Holub Přemysl, Doc. RNDr. Ph.D.
  • Čada Roman, Doc. Ing. Ph.D.
  • Kabela Adam, RNDr. Ph.D.
Obsah předmětu
1. Základní pojmy teorie množin. Relace a zobrazení. Kombinatorika. 2. Základní algebraické struktury. Modulární aritmetika. 3. Uspořádání, vlastnosti. Hasseův diagram. 4. Svazy. Distributivní, komplementární svaz. 5. Booleova algebra. Booleovský kalkulus. Direktní součin booleovských algeber, Stoneova věta o reprezentaci. 6. Booleovské funkce. Booleovské polynomy, disjunktivní a konjunktivní normální forma. Minimální forma. 7. Orientované a neorientované grafy. Základní grafové pojmy. Grafové homomorfismy. 8. Souvislost grafu. Stromy a kostry. Eulerovské grafy. Orientované grafy. Slabá a silná souvislost. Acyklické grafy, kondenzace grafu. 9. Maticová reprezentace grafu: matice sousednosti, incidenční matice, Laplaceova matice. Základy algebraické a spektrální teorie grafů. 10. Počet koster grafu. Počty sledů. Aplikace. 11. Ohodnocené grafy. Jemný úvod do algoritmů a výpočetní složitosti. 12. Aplikační úlohy: minimální kostra, vzdálenost a minimální cesta, kritická cesta, úloha čínského pošťáka. 13. Úvod do dalších oblastí: rovinné grafy, hamiltonovské grafy, barvení grafů, toky v sítích, rozsáhlé sítě, kódování, kryptografie.

Studijní aktivity a metody výuky
Skupinová výuka, Přednáška
  • Kontaktní výuka - 52 hodin za semestr
  • Příprava na dílčí test [2-10] - 18 hodin za semestr
  • Příprava na zkoušku [10-60] - 58 hodin za semestr
Předpoklady
Odborné znalosti
formulovat s porozuměním podstatě věci základní pojmy lineární algebry a vysvětlit jejich základní vlastnosti
Odborné dovednosti
aplikovat s porozuměním podstatě věci základní metody a techniky lineární algebry
Obecné způsobilosti
bc. studium: své učení a pracovní činnost si sám plánuje a organizuje,
Výsledky učení
Odborné znalosti
popsat maticový popis grafu a vysvětlit vztahy mezi vlastnostmi grafu a algebraickými vlastnostmi příslušné matice
vysvětlit algoritmické aspekty řešení základních grafových úloh
formulovat základní pojmy z teorie grafů a vysvětlit jejich základní vlastnosti, včetně porozumění souvislostem
vysvětlit základní pojmy z teorie relačních struktur: binární relace, ekvivalence (včetně aplikace na aritmetiku modulo 2), uspořádání a částečného uspořádání, Booleovy algebry a Booleovské polynomy a funkce
Odborné dovednosti
popsat grafovou strukturu pomocí matice včetně porozumění vztahům mezi vlastnostmi grafu a algebraickými vlastnostmi příslušné matice
řešit jednoduché úlohy v aritmetikách modulo k
ovládat pojmy ekvivalence a rozkladu množiny na třídy ekvivalence
navrhnout a formulovat algoritmy řešení základních grafových úloh, analyzovat jejich teoretické a algoritmické vlastnosti, a navržené algoritmy prakticky použít
prakticky použít základy teorie Booleových algeber, včetně vyjádření Booleovského polynomu v konjunktivní a disjunktivní normální formě
Obecné způsobilosti
aktivně využívá získané znalosti a dovednosti při řešení praktických problémů
Vyučovací metody
Odborné znalosti
Cvičení (praktické činnosti),
Přednáška založená na výkladu,
Odborné dovednosti
Přednáška založená na výkladu,
Cvičení (praktické činnosti),
Obecné způsobilosti
Přednáška založená na výkladu,
Cvičení (praktické činnosti),
Hodnotící metody
Odborné znalosti
Kombinovaná zkouška,
Test,
Demonstrace dovedností (praktická činnost),
Odborné dovednosti
Demonstrace dovedností (praktická činnost),
Test,
Kombinovaná zkouška,
Obecné způsobilosti
Test,
Kombinovaná zkouška,
Demonstrace dovedností (praktická činnost),
Doporučená literatura
  • Biggs, Norman L. Discrete Mathematics. Oxford Univ. Press, 2002. ISBN 9780198507178.
  • Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.
  • Gross, Jonathan L.; Yellen, Jay; Anderson, Mark. Graph Theory and Its Applications. Chapman and Hall/CRC, New York, 2018. ISBN 9781482249484.
  • Keller, M.T.; Trotter, W.T. Applied Combinatorics. CreateSpace Independent Publishing Platform. 2017.
  • Kopka, Jan. Svazy a Booleovy algebry. Univerzita J.E.Purkyně v Ústí nad Labem, 1991. ISBN 80-7044-025-2.
  • Matoušek, Jiří; Nešetřil, Jaroslav. Kapitoly z diskrétní matematiky. Čtvrté, upravené a doplněné vydání. 2019. ISBN 978-80-246-1740-4.


Studijní plány, ve kterých se předmět nachází
Fakulta Studijní plán (Verze) Kategorie studijního oboru/specializace Doporučený ročník Doporučený semestr
Fakulta: Fakulta pedagogická Studijní plán (Verze): Informatika se zaměřením na vzdělávání (19) Kategorie: Informatické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Geografie se zaměřením na vzdělávání (19) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Geografie se zaměřením na vzdělávání (18) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Fyzika se zaměřením na vzdělávání (16) Kategorie: Fyzikální obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Informatika se zaměřením na vzdělávání (16) Kategorie: Informatické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Geografie se zaměřením na vzdělávání (16) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Tělesná výchova se zaměřením na vzdělávání (18) Kategorie: Tělesná kultura, tělovýchova a sport 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Matematická studia (18) Kategorie: Matematické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Geografie se zaměřením na vzdělávání (17) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Chemie se zaměřením na vzdělávání (16) Kategorie: Chemické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Informatika se zaměřením na vzdělávání (15) Kategorie: Informatické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Chemie se zaměřením na vzdělávání (18) Kategorie: Chemické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Informatika se zaměřením na vzdělávání (18) Kategorie: Informatické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Hudba se zaměřením na vzdělávání (19) Kategorie: Umění a užité umění 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta aplikovaných věd Studijní plán (Verze): Geomatika (2018) Kategorie: Stavebnictví, geodézie a kartografie 1 Doporučený ročník:1, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Fyzika se zaměřením na vzdělávání (19) Kategorie: Fyzikální obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Biologie se zaměřením na vzdělávání (15) Kategorie: Biologické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Geografie se zaměřením na vzdělávání (1) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Biologie se zaměřením na vzdělávání (18) Kategorie: Biologické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Anglický jazyk se zaměřením na vzdělávání (19) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Chemie se zaměřením na vzdělávání (17) Kategorie: Chemické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Tělesná výchova se zaměřením na vzdělávání (17) Kategorie: Tělesná kultura, tělovýchova a sport 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Biologie se zaměřením na vzdělávání (16) Kategorie: Biologické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Geografie se zaměřením na vzdělávání (15) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Chemie se zaměřením na vzdělávání (19) Kategorie: Chemické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Technická výchova se zaměřením na vzdělávání (18) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Tělesná výchova se zaměřením na vzdělávání (19) Kategorie: Tělesná kultura, tělovýchova a sport 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Matematická studia (19) Kategorie: Matematické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Technická výchova se zaměřením na vzdělávání (17) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Technická výchova se zaměřením na vzdělávání (16) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Matematická studia (17) Kategorie: Matematické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Technická výchova se zaměřením na vzdělávání (19) Kategorie: Pedagogika, učitelství a sociální péče 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Biologie se zaměřením na vzdělávání (17) Kategorie: Biologické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Fyzika se zaměřením na vzdělávání (17) Kategorie: Fyzikální obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Fyzika se zaměřením na vzdělávání (15) Kategorie: Fyzikální obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Biologie se zaměřením na vzdělávání (19) Kategorie: Biologické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Informatika se zaměřením na vzdělávání (17) Kategorie: Informatické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Fakulta: Fakulta pedagogická Studijní plán (Verze): Chemie se zaměřením na vzdělávání (14) Kategorie: Chemické obory 2 Doporučený ročník:2, Doporučený semestr: Letní
Západočeská univerzita v Plzni, data aktuální k: 09.11.2024 23:52. Data byla vytvořena pro akademický rok 2024/2025