470-2301/01 – Diskrétní matematika (DIM)

Garantující katedraKatedra aplikované matematikyKredity6
Garant předmětudoc. Mgr. Petr Kovář, Ph.D.Garant verze předmětudoc. Mgr. Petr Kovář, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinný
Ročník2Semestrzimní
Odkaz na webhttp://homel.vsb.cz/~kov16/predmety_dm.phpJazyk výukyčeština
Rok zavedení2010/2011Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studiabakalářské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
KOV16 doc. Mgr. Petr Kovář, Ph.D.
KOV74 Mgr. Tereza Kovářová, Ph.D.
KRA568 Ing. Michal Kravčenko
KRB0006 Ing. Matěj Krbeček
KUB59 RNDr. Michael Kubesa, Ph.D.
SIL075 Ing. Adam Silber
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 10+10

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Předmět seznamuje studenty se základními pojmy diskrétní matematiky a teorie grafů, se kterými se nejčastěji pracuje v různých oblastech teoretické a aplikované informatiky. Na přednáškách budou vždy definovány a vysvětleny základní používané pojmy matematické teorie vztahující se k dané kapitole. Do každé kapitoly jsou zařazeny praktické aplikace probírané látky. V dalším budou vymezeny základní a nejdůležitější vlastnosti nadefinovaných pojmů (objektů) ve formě tvrzení, přičemž některá z nich budou dokázána. Důraz je kladen na konstruktivní důkazy. Po absolvování přednášky by tedy student měl umět: - reprodukovat, ekvivalentně přeformulovat, popřípadě zobecnit dané definice, - rozpoznat a odlišovat objekty reálného světa a poznaných matematických teorií, které definici vyhovují, a které ne, - klasifikovat tyto objekty dle předem známých a řádně objasněných vlastností, - shrnout poznatky dané kapitoly. Cvičení by mělo u studenta rozvinout tyto schopnosti: - formulovat úlohu slovy probrané matematické teorie, - aplikovat teoretické poznatky na řešení konkrétních praktických úloh a problémů, - navrhnout více metod řešení a tyto porovnávat a kriticky vyhodnocovat, - přezkoumat správnost výběru metody řešení, - přenášet či přenést metodu řešení jedné úlohy na úlohy jiné.

Vyučovací metody

Přednášky
Individuální konzultace
Cvičení (v učebně)
Projekt

Anotace

Předmět seznamuje studenta se základními pojmy, konstrukcemi a postupy diskrétní matematiky v oblasti kombinatoriky a teorie grafů. (Slovo "diskrétní" je v názvu míněno jako opak "spojitého".)

Povinná literatura:

M.Kubesa, Základy diskrétní matematiky, elektronický učební text, 2011, on-line. P.Kovář, Úvod do teorie grafů, elektronický učební text, 2011, on-line.

Doporučená literatura:

L.Kučera, Kombinatorické Algoritmy, SNTL, Praha, 1983. J.Matoušek, J.Nešetřil. Kapitoly z diskrétní matematiky, Karolinum Praha 2000. (Konkrétně: Kapitoly 1,2 a část kapitoly 9 pro Část I přednášky. Kapitoly 3,4,5 pro Část II přednášky.) 10 výtisků knihy je v knihovně VŠB, ale prodejna skript ji neprodává. Knihu by mělo být možné koupit v knihkupectví Profesio v centru Ostravy, Hollarova ulice naproti ČSOB.

Způsob průběžné kontroly znalostí během semestru

Průběžná kontrola studia: Semestrální písemky. Každý týden v semestru (s výjimkou prvních dvou týdnů) se na cvičeních budou psát krátké zápočtové písemky (deset písemek, každá za 2 nebo za 3 body). Během písemek není možné používat literaturu, ani zápisky. Na konci semestru cvičící sečte body ze čtyř "nejlepších" dvoubodových a čtyř nejlepších tříbodových písemek. Maximum je 20 bodů. Témata písemek jsou vždy vyvěšena na stránkách diskrétní matematiky (resp. garanta předmětu), minimálně týden před písemkou. Na písemky budou zadány příklady obdobné. Samostatný projekt. Bude zadán v druhé půli semestru. Běžný projekt bude obsahovat několik příkladů, přičemž zhruba polovina bude z kombinatoriky a polovina z teorie grafů. Příklady budou hodnoceny buď 0-2 nebo 0-3 body (dle obtížnosti) tak, aby byl celkový maximální součet 10 bodů. Na webu mohou být také uveřejněny projekty pro zájemce, které budou obsahovat dva obtížnější úkoly (kombinatorika + teorie grafů). Každý student má možnost přidělený běžný projekt zaměnit za některý z projektů pro zájemce. Projekt pro zájemce bude mít úkoly hodnoceny 0/3/5 bodů, v případě výjimečně pěkného řešení až 10 bodů. Zkouška. Ke zkoušce můžete student jít, pokud získal zápočet. Hlavní součástí zkoušky je písemná práce zhruba na 75 minut. Na písemné zkoušce můžete získat až 70 bodů. Během zkoušky můžete používat také jedinou stranu A4 rukou psaných poznámek. Na tomto "zlegalizovaném taháku" mohou být definice, věty, vztahy. ALE NE ŘEŠENÉ PŘÍKLADY!!! Podmínky udělení zápočtu: Získat během semestru alespoň 10 bodů a samostatný referát musí být PŘIJAT. Referát bude přijat, pokud bude splňovat formální podmínky, tj. formát, úvodní stranu atd. Přijat může být i projekt, který je obsahově na 0 bodů.

E-learning

Další požadavky na studenta

Žádné další požadavky na studenta nejsou kladeny.

Minimální znalostní požadavky

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Přednášky: Část I - Úvod do diskrétní matematiky Zaměření a cíle diskrétní matematiky. Množiny, prvky a podmnožiny, základní kombinatorické pojmy. Kombinatorické výběry a jejich počet. Konečná pravděpodobnost: Pojem pravděpodobnosti, pravděpodobnostního prostoru a náhodného jevu. Náhodná čísla v počítači. Přirozená čísla a matematická indukce. Pojem matematického důkazu. Počty podmnožin, odvození vzorců pro kombinace a permutace. Aplikace. Formální základy diskrétní matematiky: pojmy relace, zobrazení, ekvivalence, uspořádání, částečné uspořádání. Princip inkluze a exkluze. Algoritmické aspekty: praktická implementace množin, zobrazení a relací. Algoritmy generování a procházení všech základních kombinatorických výběrů. Část II - Úvod do teorie grafů Pojem grafu, jeho souvislost s relacemi. Podgrafy, isomorfizmus, stupně vrcholů. Metody zadání grafu, orientované grafy. Pojem souvislosti grafu, algoritmy procházení do hloubky a do šířky. Vyšší stupně souvislosti (Mengerovy věty). Eulerovské grafy - kreslení jedním tahem, využití, hamiltonovské grafy a jejich využití . Vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty. Metrika grafu a její určení. Stromy a jejich charakterizace, kořenové stromy, isomorfizmus stromů. Kostra grafu, (počet koster), problém minimální kostry. Aplikace problému minimální kostry, klasické algoritmy. Rovinné kreslení grafu, Eulerův vztah a jeho důsledky. Barvení grafů, bipartitní grafy a jejich rozeznávání. Toky v sítích: definice a modelované problémy. Ford-Fulkersonův algoritmus pro nalezení maximálního toku. Další využití algoritmu (párování a systém reprezentantů). Cvičení: Procvičení učiva z přednášek v dané chronologii. Projekty: Vypracování jednoho samostatného písemného projektu, který se skládá z části kombinatorické a části, týkající se teorie grafů.

Podmínky absolvování předmětu

Prezenční forma (platnost od: 2013/2014 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 30 (30) 10
                Projekt DIM Projekt 10  0
                Zápočtová písemka Písemka 20  0
        Zkouška Zkouška 70  21
Rozsah povinné účasti: účast na cvičeních je povinná, jsou akceptovány 2 omluvy účast na přednáškách je předpokládaná

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramOborSpec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2017/2018 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2010/2011 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2010/2011 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2010/2011 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2010/2011 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku
V - ECTS - bc. 2014/2015 prezenční čeština volitelný odborný 401 - Studijní oddělení FEI stu. blok
V - ECTS - bc. 2013/2014 prezenční čeština volitelný odborný 401 - Studijní oddělení FEI stu. blok
V - ECTS - bc. 2012/2013 prezenční čeština volitelný odborný 401 - Studijní oddělení FEI stu. blok