Fakulta informačních technologií VUT v Brně

Detail předmětu

Diskrétní matematika

IDM Ak. rok 2019/2020 zimní semestr 5 kreditů

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.

Garant předmětu

Zástupce garanta předmětu

Jazyk výuky

česky

Zakončení

zápočet+zkouška (písemná)

Rozsah

26 hod. přednášky, 26 hod. cvičení

Bodové hodnocení

60 zkouška, 30 půlsemestrální test, 10 projekty

Zajišťuje ústav

Přednášející

Cvičící

Čejka Rudolf, Ing. (CVT FIT VUT)
Fuchs Petr, RNDr., Ph.D. (UMAT FEKT VUT)
Havlena Vojtěch, Ing. (UITS FIT VUT)
Hliněná Dana, doc. RNDr., Ph.D. (UMAT FEKT VUT)
Holík Lukáš, Mgr., Ph.D. (UITS FIT VUT)
Lengál Ondřej, Ing., Ph.D. (UITS FIT VUT)
Vážanová Gabriela V., Mgr. (FEKT VUT)

Získané dovednosti, znalosti a kompetence z předmětu

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.

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.

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.





Požadované prerekvizitní znalosti a dovednosti

Středoškolská matematika.

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

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.

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. Binární operace a jejich vlastnosti.
  5. Algebry s jednou operaci, zejména grupy. Kongruence a morfismy.
  6. Algebry se dvěma operacemi, svazy jako algebry.
  7. Booleovy algebry.
  8. Výroková logika. Syntax a sémantika.
  9. Predikátová logika. Syntax a sémantika.
  10. Praktické užití výrokové a predikátové logiky v důkazech. Techniky důkazů a jejich ilustrace.
  11. Základní pojmy teorie grafů. Izomorfismus grafů. Stromy a jejich vlastnosti. Sledy, tahy a Eulerovské grafy.
  12. Hledání nejkratší cesty. Dijkstrův algoritmus. Problém minimální kostry. Algoritmy Kruskala a Jarníka. Rovinné grafy.
  13. Orientované grafy, toky v sítích, hledání maximálního toku, aplikace.

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.

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ů).

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ů.

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

Rozvrh

DenTypTýdnyMístn.OdDoPSKSkupInfo
Popoč. labvýuky D0207 08:0009:50 1BIB 2BIA 2BIB xx Hliněná
Popoč. labvýuky D0207 14:0015:50 1BIB 2BIA 2BIB xx Holík
Popoč. labvýuky D0207 16:0017:50 1BIB 2BIA 2BIB xx Holík
Popoč. labvýuky A113 18:0019:50 1BIB 2BIA 2BIB xx Holík
Útpřednáškavýuky D0206 D105 08:0009:50 1BIB 2BIA 2BIB xx Hliněná
Útpoč. labvýuky A113 08:0009:50 1BIA 2BIA 2BIB xx Havlena
Útpoč. labvýuky T8/322 11:0012:50 1BIB 2BIA 2BIB xx Fuchs
Útpřednáškavýuky D0206 D105 13:0014:50 1BIA 2BIA 2BIB xx Hliněná
Útpoč. labvýuky D0207 16:0017:50 2BIA 2BIB xx Lengál
Stpoč. labvýuky T8/503 07:0008:50 1BIA 2BIA 2BIB xx Vážanová
Stpoč. labvýuky T8/322 13:0014:50 1BIB 2BIA 2BIB xx Fuchs
Stpoč. labvýuky A113 16:0017:50 1BIA 2BIA 2BIB xx Hliněná
Čtpoč. labvýuky T8/522 13:0014:50 1BIA 2BIA 2BIB xx Fuchs
Čtpoč. labvýuky A113 18:0019:50 1BIA 2BIA 2BIB xx Lengál
poč. labvýuky T8/522 07:0008:50 1BIA 2BIA 2BIB xx Vážanová
poč. labvýuky D0207 14:0015:50 1BIB 2BIA 2BIB xx Havlena
zkouška2019-10-18 D0206 D105 E104 E105 E112 17:0020:50 1BIA 1BIB 2BIA 2BIB 1. písemka
zkouška2019-11-29 D0206 D105 E104 E105 E112 17:0020:50 1BIA 1BIB 2BIA 2BIB 2. písemka

Zařazení předmětu ve studijních plánech

  • Program BIT, 1. ročník, povinný
  • Program IT-BC-3, obor BIT, 1. ročník, povinný
Nahoru