Předmět Diskrétní matematika (DIM)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu DIM - Diskrétní matematika, Vysoká škola báňská - Technická univerzita Ostrava (VŠB-TU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Předmět seznamuje studenty se základními pojmy diskrétní matematiky a teorie grafů, se kterými se nejčastěji pracujev 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é.
Osnova
Přednášky:Část I - Úvod do diskrétní matematikyZaměř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 vpočítači.Přirozená čísla a matematická indukce. Pojem matematického důkazu. Počty podmnožin, odvození vzorců pro kombinacea 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šechzá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í seteorie grafů.
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.
Požadavky
Žádné
Garant
doc. Mgr. Petr Kovář, Ph.D.
Vyučující
Ing. Pavla Hrušková, Ph.D.doc. Mgr. Petr Kovář, Ph.D.Mgr. Tereza Kovářová, Ph.D.Ing. Matěj KrbečekRNDr. Michael Kubesa, Ph.D.Ing. Adam Silber