Detail předmětu

Diskrétní matematika

IDM Ak. rok 2023/2024 zimní semestr 4 kredity

Množina, relace a zobrazení. Ekvivalence a rozklady. Uspořádání. Struktury s jednou a dvěma operacemi. Svazy a Booleovy 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.

Garant předmětu

Koordinátor předmětu

Jazyk výuky

česky, anglicky

Zakončení

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

Rozsah

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

Bodové hodnocení

  • 80 bodů závěrečná zkouška
  • 20 bodů numerická cvičení

Zajišťuje ústav

Přednášející

Cvičící

Stránky předmětu

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. 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 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 vystihnout 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 říct, ž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í

  • Hliněný, P., Úvod do informatiky. Elportál, Brno, 2010.
  • Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2007.
  • Sochor, A., Klasická matematická logika, Karolinum, Praha 2001.

Osnova přednášek

  1. Formální jazyk matematiky. Základní formalismy - věta, důkaz, výroková a predikátová logika.
  2. Intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Princip inkluze a exkluze.
  3. Důkazové techniky.
  4. Binární relace, jejich vlastnosti a skládání.
  5. Reflexivní, symetrický a tranzitivní uzávěr. Ekvivalence a rozklady.
  6. Relace uspořádání, svazy. Hasseovské diagramy. Zobrazení.
  7. Pojem grafu, základní pojmy. Isomorfismus grafů, stromy, cesty a eulerovské grafy.
  8. Grafové algoritmy pro hledání nejkratší cesty a minimální kostry. Rovinné grafy.
  9. Orientované grafy.
  10. Binární operace a jejich vlastnosti.
  11. Algebry s jednou operaci, grupy.
  12. Kongruence a morfismy.
  13. Algebry se dvěma operacemi, svazy jako algebry. 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.

Průběžná kontrola studia

Písemné testy během semestru (pět 4bodových testů). Výuka je povinná. Na přednáškách účast nebude kontrolována, ale znalost probírané látky bude následně na cvičeních vyžadována, neúčast na cvičeních musí být omluvena. Závěrečná písemná zkouška 80 bodů.

Podmínky zápočtu

Podmínka zápočtu je zisk alespoň 8 bodů z písemek během semestru a aktivní práce na cvičení.

Rozvrh

DenTypTýdnyMístn.OdDoKapacitaPSKSkupInfo
Po zkouška 2023-12-18 E104 E105 E112 09:0011:00 předtermín
Po cvičení 2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky A112 09:0010:5064 1BIA 1BIB 2BIA 2BIB xx Tůma
Po zkouška 2024-01-15 D105 T8/T 0.10 T8/T 0.20 T8/T 0.30 10:3012:30 2. termín
Po cvičení 2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky D0207 15:0016:5064 1BIA 1BIB 2BIA 2BIB xx Fuchs
Po cvičení 2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky T8/T 3.02 15:0016:5056 1BIA 1BIB 2BIA 2BIB xx Tůma
Po cvičení 2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky T8/T 3.02 17:0018:5056 1BIA 1BIB 2BIA 2BIB xx Tůma
Út přednáška výuky D0206 D105 08:0009:50470 1BIB 2BIA 2BIB xx 30 - 49 Hliněná
Út cvičení 2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky A112 09:0010:5064 1BIA 1BIB 2BIA 2BIB xx Tůma
Út zkouška 2024-01-30 T8/T 0.10 T8/T 0.20 T8/T 0.30 10:3012:30 3. termín
Út cvičení 2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky A112 11:0012:5064 1BIA 1BIB 2BIA 2BIB xx Tůma
Út přednáška výuky D0206 D105 12:0013:50470 1BIA 2BIA 2BIB xx 10 - 29 Hliněná
Út cvičení 2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky A112 13:0014:5064 1BIA 1BIB 2BIA 2BIB xx Tůma
St zkouška 2024-01-03 D0206 D0207 D105 T8/T 0.10 T8/T 0.20 T8/T 0.30 10:3012:30 1. termín
St cvičení 2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky D0207 14:0015:5064 1BIA 1BIB 2BIA 2BIB xx Hliněná
St cvičení 2., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky D0207 16:0017:5065 1BIA 1BIB 2BIA 2BIB xx Hliněná
Čt cvičení 1., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky A113 10:0011:5064 1BIA 1BIB 2BIA 2BIB xx Hliněná
Čt cvičení 1., 3., 4., 5., 6., 7., 8., 9., 10., 11., 12., 13. výuky T8/T 5.22 13:0014:5050 1BIA 1BIB 2BIA 2BIB xx Fuchs
cvičení 1., 2., 3., 4., 5., 6., 7., 8., 10., 11., 12., 13. výuky D0207 12:0013:5065 1BIA 1BIB 2BIA 2BIB xx Fuchs
cvičení 1., 2., 3., 4., 5., 6., 7., 8., 10., 11., 12., 13. výuky D0207 14:0015:5064 1BIA 1BIB 2BIA 2BIB xx Fuchs

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

Nahoru