Homepage
Curriculum vitae
Publikace
Výuka
Kontakt
   

Diskrétní matematika ZS 2010/2011

Toto není stránka aktuálního akademického roku.

Předmět: 470-2301/01: Diskrétní matematika (DIM)
Garant: RNDr. Michael Kubesa, Ph.D.
Rozsah: 6 kreditů (2/2/2)
Akademický rok: 2010/2011

Anotace

Předmět seznamuje studenty se základními pojmy teorie množin a diskrétní matematiky, se kterými se nejčastěji pracuje v různých oblastech teoretické a aplikované informatiky. Cílem je naučit se používat tyto pojmy při exaktní formulaci a řešení praktických úloh.

Slovo "diskrétní" v názvu je míněno jako opak "spojitého"; tj. předmět se zabývá těmi oblastmi matematiky, kde uvažujeme celá čísla a jednotlivé konečné objekty. Diskrétní objekty jsou prezentovány převážně pomocí konečných množin a grafů.

 

Průběh přednášek

K dispozici bude přehled látky probrané v jednotlivých týdnech včetně elektronické prezentace.

Část I - Úvod do diskrétní matematiky

  • Zaměření a cíle diskrétní matematiky. Množiny, prvky a podmnožiny, úvodní kombinatorické pojmy. Kombinace a permutace, vzorce na jejich počet. Výběry prvků s opakováním.
  • Konečná pravděpodobnost, hody mincí a kostkou, náhodné výběry, míchání karet. Pojem pravděpodobnosti, prostoru a jevu. Náhodná čísla v počítači.
  • Přirozená čísla a matematická indukce. Pojem matematického důkazu. Počty podmnožin, důkazy vzorců pro kombinace a permutace.
  • 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í podmnožin a permutací.

Část II - Úvod do teorie grafů

  • Pojem grafu, jeho souvislost s relacemi. Podgrafy, isomorfizmus, stupně vrcholů, indukované podgrafy. Realizace grafu, orientovaný graf.
  • Souvislost grafu, algoritmy procházení do hloubky a do šířky. Vícenásobná souvislost, hranová souvislost. (Mengerova věta.) Eulerovské grafy - kreslení jedním tahem.
  • Vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty. Metrika grafu a její výpočet.
  • Stromy a jejich charakterizace, isomorfizmus stromů. Kořenové stromy. Kostra grafu, (počet koster), problém minimální kostry. Aplikace na hledání minimální kostry, algoritmy Jarníka a Borůvky.
  • Rovinné kreslení grafu, Eulerův vztah. 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. Aplikace na párování a různé reprezentanty.
  • Praktická realizace grafů v počítači, různé způsoby realizace a jejich výhody. Ohodnocení vrcholů a hran. Realizace kořenových stromů a planárních grafů. (Vizualizace grafů včetně nerovinných.)

 

Hodnocení

Účast na přednáškách formálně není povinná, nicméně se vřele doporučuje pro úspěšné zvládnutí studia. Protože každý týden semestru se píší bodované písemky, je účast na cvičeních nutná, ačkoli formálně není povinná. Při případné neúčasti máte možnost sami na webu zjistit, co bylo probráno a na jaké téma se bude další psát písemka.

Zápočtové písemky (20 bodů)

Každý týden v semestru (s výjimkou prvního týdne) se na cvičení bude psát krátká zápočtová písemka (10-11 písemek). K vyřešení bude zhruba 2-10 minut, podle obtížnosti příkladu. Během písemek není možno používat literaturu, ani zápisky. Za každou písemku můžete získat 0/1/2 body - rozuměj NE/TÉMĚŘ SPRÁVNĚ/ZCELA SPRÁVNĚ. Při absenci se písemka hodnotí 0 body.

Na konci semestru se každému vezmou body osmi nejlepších písemek a jejich součet se vynásobí koeficientem 1,25. To bude celkový počet bodů za semestrální písemky.

Témata písemek najdete v tabulce. Alespoň týden předem budou k dispozici také zadání příkladů.

Samostatný referát (10 bodů)

Během semestru budou zveřejněna témata na samostatných písemných referátů. Každý student vypracuje jedno zadání podle čísla, které mu bude přiděleno.
Pro získání zápočtu musíte mít přijatý referát, tj. kromě řešení musí vyhovět i formálním požadavkům. Referát obsahuje dva příklady, z každé části jeden (diskrétní matematika/teorie grafů). Příklady se hodnotí buď za 0, 3 nebo 5 bodů (opět stylem NE/TÉMĚŘ SPRÁVNĚ/ZCELA SPRÁVNĚ). V případě mimořádně kvalitního referátu lze udělit 5 bodů navíc.

Referát má pevně stanovený termín odevzdání, který musíte dodržet. Nenechávejte si práci na poslední chvíli, nepomohou výmluvy na nemoc či jinou mimořádnou událost před termínem odevzdání, neboť referát máte vypracovat s dostatečným předstihem!

Každý musí sepsat svůj referát sám, žádná spolupráce na výsledném textu referátu není dovolena. Na druhou stranu je dovoleno o zadání referátu volně diskutovat se spolužáky i na cvičeních, tedy vše kromě samotného vypracování. Referát odevzdáváte e-mailem nebo na papíře příslušnému vyučujícímu (kontakt je uveden u každého zadání). Cvičící vás může vyzvat k přednesení vašeho referátu během cvičení.

Můžete se podívat na vzorový referát ve formátu pdf: dim_vzorovy_referat.pdf.

ReferátyTermín pro odevzdání
Celá sada zadáníPo 6.12.2009   12:00 hod

Zkouška (70 bodů)

Ke zkoušce můžete jít, jestliže máte nárok na zápočet (máte alespoň 10 bodů a váš referát bude přijat)! 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 vedle vlastní hlavy pouze jednu stranu A4 rukou psaných poznámek.
Na tomto "zlegalizovaném taháku" mohou být definice, věty a vztahy, ale "tahák" nesmí obsahovat řešené příklady .

Data a místnosti zkušebních termínů budou stanoveny koncem semestru.

Můžete se podívat na vzorovou zkouškovou písemku ve formátu pdf: dim_vzorova_pisemka_zk.pdf.

Hromadné konzultace
Místnost K2024.1.2011   od 9:00 do cca 10:30 hod
Místnost K2025.1.2011   od 9:00 do cca 10:30 hod

 

Literatura

  • P. Hliněný. Diskrétní matematika, výukový text (online), FEI VŠB - TUO, 2004.
  • J. Matoušek, J. Nešetřil. Kapitoly z diskrétní matematiky, Karolinum Praha 2000.
    (Kapitoly 1, 2 a kousek z 9 pro Část I přednášky. Kapitoly 3, 4, 5 pro Část II přednášky.)
  • P. Kovář. Cvičení z diskrétní matematiky, výukový text (dim_cviceni.pdf), 2010.
  • 10 výtisků knihy "Kapitoly z diskrétní matematiky" je v knihovně VŠB, prodejna skript ji neprodává. Knihu je možné koupit případně objednat v knihkupectví Profesio v centru Ostravy, Hollarova ulice naproti ČSOB. Vhodné zejména pro studenty s hlubším zájmem o předmět.

Literatura je doporučená, není povinná. Na přednáškách a cvičeních se dozvíte vše co je potřeba znát ke zkoušce.
Rozhodně není potřeba učit se nazpaměť pasáže z knih, látce je třeba rozumět!
Je možné používat i jiné úvodní knihy a skripta pro daný předmět, ovšem pozor: některé detaily na přednášce se mohou lišit od literatury (odchylky v definicích pojmů, které nejsou ustálené) a u zkoušky pak platí to, co bylo na přednášce.

 

Rozvrh

V zimním semestru 2010/2011 jsou přednášky z Diskrétní matematiky pro skupiny LB2IVT02-LB2IVT7, LB2TKT01-LB2TKT05 a LB2VMA01 každé pondělí 12:30-14:00 na C3.
Přednášky v anglickém jazyce pro skupinu LB2IVT01 jsou v úterý 9:00-10:30 na D210.

Toto není stránka aktuálního akademického roku.

Konzultační hodiny

Zastihnete mne nejlépe osobně během konzultačních hodin, případně (po dohodě emailem) on-line přes MS Teams.

Best way to reach me is during my office hours. It is also possible to arrange (ahead via e-mail) an on-line appointment in MS Teams.

DenČasMístnost
Čtvrtek/Thursday9:00-10:00EA536*
Konzultace on-line po předchozí domluvě.

Po předchozí domluvě jsou konzultace možné i v jinou dobu. / Or by appointment.


email
kancelář EA536, tel. 597 325 972
Upraveno: 29.12.2011