Název:

Diskrétní matematika

Zkratka:IDM
Ak.rok:2019/2020
Semestr:zimní
Studijní plán:
ProgramObor/
specializace
RočníkPovinnost
BIT-1.povinný
IT-BC-3BIT1.povinný
Vyučovací jazyk:čeština
Kredity:5 kreditů
Ukončení:zápočet+zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvič.lab. cvič.poč. cvič.jiná
Rozsah:2626000
 zkouškatestycvičenílaboratořeostatní
Body:60300010
Garant:Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Zástupce garanta:Holík Lukáš, Mgr., Ph.D. (UITS)
Přednášející:Fuchs Petr, RNDr., Ph.D. (UMAT)
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Holík Lukáš, Mgr., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)
Cvičící:Fuchs Petr, RNDr., Ph.D. (UMAT)
Havlena Vojtěch, Ing. (UITS)
Hliněná Dana, doc. RNDr., Ph.D. (UMAT)
Holík Lukáš, Mgr., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)
Vážanová Gabriela V., Mgr. (FEKT)
Fakulta:Fakulta elektrotechniky a komunikačních technologií VUT v Brně
Pracoviště:Ústav matematiky FEKT VUT v Brně
Nahrazuje:
Diskrétní matematika (IDA), UMAT
Rozvrh:
DenVýukaTýdenMístnostOdDoPSKSkupiny
Popoč. lab - HliněnávýukyD0207 08:0009:501BIB 2BIA 2BIB xx
Popoč. lab - HolíkvýukyD0207 14:0015:501BIB 2BIA 2BIB xx
Popoč. lab - HolíkvýukyD0207 16:0017:501BIB 2BIA 2BIB xx
Popoč. lab - HolíkvýukyA113 18:0019:501BIB 2BIA 2BIB xx
Útpřednáška - HliněnávýukyD0206 D105 08:0009:501BIB 2BIA 2BIB xx
Útpoč. lab - HavlenavýukyA113 08:0009:501BIA 2BIA 2BIB xx
Útpoč. lab - FuchsvýukyT8/322 11:0012:501BIB 2BIA 2BIB xx
Útpřednáška - HliněnávýukyD0206 D105 13:0014:501BIA 2BIA 2BIB xx
Útpoč. lab - LengálvýukyD0207 16:0017:502BIA 2BIB xx
Stpoč. lab - VážanovávýukyT8/503 07:0008:501BIA 2BIA 2BIB xx
Stpoč. lab - FuchsvýukyT8/522 13:0014:501BIB 2BIA 2BIB xx
Stpoč. lab - HliněnávýukyA113 16:0017:501BIA 2BIA 2BIB xx
Čtpoč. lab - FuchsvýukyT8/522 13:0014:501BIA 2BIA 2BIB xx
Čtpoč. lab - LengálvýukyA113 18:0019:501BIA 2BIA 2BIB xx
poč. lab - VážanovávýukyT8/522 07:0008:501BIA 2BIA 2BIB xx
poč. lab - HavlenavýukyD0207 14:0015:501BIB 2BIA 2BIB xx
zkouška - 1. písemka2019-10-18D0206 D105 E104 E105 E112 17:0020:50
zkouška - 2. písemka2019-11-29D0206 D105 E104 E105 E112 17:0020:50
 
Cíle předmětu:
  Předmět poskytuje základní znalosti z matematiky potřebné pro řadu navazujících předmětů. Studenti se seznámí s elementárními poznatky z algebry a diskrétní matematiky, s důrazem na matematické struktury, které jsou potřebné pro pozdější aplikace v informatice.
Anotace:
  Množina, relace a zobrazení. Ekvivalence a rozklady. Uspořádání. Struktury s jednou a dvěma operacemi. Svazy a Boolovy algebry. Výroková a predikátová logika. Základní pojmy teorie grafů. Souvislost grafů. Podgrafy a morfismy grafů. Problém rovinnosti. Stromy a jejich vlastnosti. Základní grafové algoritmy. Orientované grafy, toky v sítích.
Požadované prerekvizitní znalosti a dovednosti:
  Středoškolská matematika.
Získané dovednosti, znalosti a kompetence:
  Studenti získají schopnost orientace v základních diskrétních matematických strukturách a schopnost porozumět logické struktuře matematického textu. Budou schopni vysvětlit matematické struktury a budou umět přesně formulovat vlastní tvrzení a jejich důkazy.
Proč je předmět vyučován:
  Matematika a matematické myšlení jsou historickým základem informatiky, a jsou jádrem většiny současného pokroku v informatice. 

Diskrétní matematika se soustřeďuje na porozumění objektům a jevům reálného světa, které jsou pro informatiku nejzásadnější.
Jedná se o koncepty jako množina (např. soubor dat, aktérů),
relace a graf (např. vztahy mezi daty, popis komunikace) a operace nad prvky množiny (zejména aritmetické operace a jejich zobecnění).
Matematická logika pak dává efektivní nástroje pro strukturované a jasné vyjadřovaní, argumentaci a odvozovaní, a je hlavním principem, na kterém stojí "myšlení počítačů".   

Obecně, diskrétní matematika učí základům abstrakce -- jak vystihnou aspekty reálného světa důležité pro řešení problému a jak s nimi pracovat. Poskytuje univerzální jazyk, kterým o těchto aspektech dokážeme výstižně a efektivně komunikovat, a který pomáhá strukturovat myšlení do přesně vymezených pojmů a vztahů. Tato efektivita a přesnost je nezbytná při návrhu a vývoji rozsáhlých a komplikovaných IT systémů, a pro vývoj souvisejících inovací. 

Aparát diskrétní matematiky například poskytuje základní nástroje potřebné k vyjádření, co program dělá; jak na vstupu závisí výstup, nebo množství potřebných zdrojů; jak jsou organizována data v datových strukturách a co reprezentují; jak program komunikuje s okolím; co znamená, že program funguje správně. Podobné aplikace diskrétní matematiky a jejího jazyka v informatice jsou všudypřítomné.
Dá se říci, že programátor/informatik bez matematiky je jako klavírista bez znalosti not. Může mít úspěšnou kariéru pokud má talent, ale jeho možnosti jsou omezené, zejména pokud se jedná o řešení komplikovaných problémů.

Protože naším cílem je hlavně naučit studenty matematicky myslet a systematicky se vyjadřovat, klademe velký důraz právě na nácvik použití matematiky a matematického myšlení k řešení problémů -- stejně jako se programování člověk naučí jen programováním, i ke zvládnutí matematiky je nezbytné matematiku dělat vlastníma rukama.





Osnova přednášek:
 
  1. Formální jazyk matematiky. Intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Kombinatorické vlastnosti množin. Princip inkluze a exkluze. 
  2. Binární relace a zobrazení, jejich skládání a vlastnosti. Reflexivní, symetrický a tranzitivní uzávěr. Ekvivalence a rozklady. Uspořádání, zvláště svazové. Hasseovské diagramy.
  3. Posloupnosti a rekurentní vztahy.
  4. Základní pojmy teorie grafů. Izomorfismus grafů. Stromy a jejich vlastnosti. Sledy, tahy a Eulerovské grafy.
  5. Hledání nejkratší cesty. Dijkstrův algoritmus. Problém minimální kostry. Algoritmy Kruskala a Jarníka. Rovinné grafy.
  6. Orientované grafy, toky v sítích, hledání maximálního toku, aplikace.
  7. Výroková logika. Syntax a sémantika.
  8. Predikátová logika. Syntax a sémantika.
  9. Praktické užití výrokové a predikátové logiky v důkazech. Techniky důkazů a jejich ilustrace.
  10. Binární operace a jejich vlastnosti.
  11. Algebry s jednou operaci, zejména grupy. Kongruence a morfismy.
  12. Algebry se dvěma operacemi, svazy jako algebry.
  13. Booleovy algebry.
Osnova numerických cvičení:
 Příklady probírané na cvičeních jsou voleny tak, aby vhodným způsobem doplňovaly přednášky.
Literatura referenční:
 
  • Anderson I., A First Course in Discrete Mathematics, Springer-Verlag, London 2001.
  • Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004.
  • Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002.
  • Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992.
  • Kolman B., Busby R. C., Ross S. C., Discrete Mathematical Structures, Pearson Education, Hong-Kong 2001.
  • Klazar M., Kratochvíl J, Loebl M., Matoušek J. Thomas R., Valtr P., Topics in Discrete Mathematics, Springer-Verlag, Berlin 2006.
  • Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2007.
  • Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008.
  • O'Donnell, J., Hall C., Page R., Discrete Mathematics Using a Computer, Springer-Verlag, London 2006.
  • Sochor, A., Klasická matematická logika, Karolinum, Praha 2001.
Literatura studijní:
 
  • Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2007.
  • Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008.
  • Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010.
  • Kovár, M.,  Diskrétní matematika, FEKT VUT, Brno, 2013
Kontrolovaná výuka:
  
  • Znalosti studentů jsou ověřovány na cvičeních, vypracováním a obhajobou dvou domácích úloh, každá po 5 bodech, vypracováním dvou půlsemestrálních zkoušek, každá po 15 bodech, a závěrečnou zkouškou za 60 bodů.
  • Pokud se student nemůže cvičení z vážného důvodu (například pro nemoc) zúčastnit a tento důvod doloží v souladu s Článkem 55 Studijního a zkušebního řádu VUT, může se cvičení se stejným tématem zúčastnit s jinou skupinou (na což dotyčného cvičícího upozorní). 
  • Hranice pro úspěšnou zkoušku podle pravidel ECTS je 50 bodů.
Průběžná kontrola studia:
  
  • Ohodnocení dvou domácích úloh vypracovaných ve skupinách (max 10 bodů).
  • Ohodnocení dvou půlsemestrálních zkoušek (max 30 bodů).
Podmínky zápočtu:
  Získání alespoň 10 bodů z půlsemestrálních zkoušek. Pokud bude odhaleno plagiátorství nebo nedovolená spolupráce na projektu, zápočet nebude udělen a dále bude zváženo zahájení disciplinárního řízení.
 

Vaše IPv4 adresa: 34.229.126.29