457-0519/01 – Diskrétní matematika (DIM)

Garantující katedraKatedra aplikované matematikyKredity6
Garant předmětuRNDr. Michael Kubesa, Ph.D.Garant verze předmětuRNDr. Michael Kubesa, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinný
Ročník2Semestrzimní
Jazyk výukyčeština
Rok zavedení2003/2004Rok zrušení2009/2010
Určeno pro fakultyFEIUrčeno pro typy studiabakalářské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
CER365 doc. Ing. Martin Čermák, Ph.D.
HOR33 doc. Ing. David Horák, Ph.D.
KAB002 Ing. Pavla Hrušková, Ph.D.
KOV16 doc. Mgr. Petr Kovář, Ph.D.
KUB59 RNDr. Michael Kubesa, Ph.D.
KUP055 Ing. Tomáš Kupka
VLA04 Ing. Oldřich Vlach, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 10+10

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

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. 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. Zhusta budou také připomenuty praktické motivace vedoucí k těmto definicím. 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 exaktně dokázána. Zde je nutné dodržet princip přiměřenosti! Po absolvování přednášky by tedy student měl umět: - reprodukovat, parafrázovat, 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ů, - experimentovat při výběru vhodné metody řešení, - přezkoumat správnost výběru metody řešení, - nacházet více metod řešení a tyto porovnávat a kriticky vyhodnocovat, - přenášet či přenést metodu řešení jedné úlohy na úlohy jiné.

Vyučovací metody

Přednášky
Individuální konzultace
Cvičení (v učebně)
Projekt

Anotace

Předmět seznamuje studenta se základy teorie množin a základními konstrukcemi diskrétní matematiky v oblasti kombinatoriky a teorie grafů. (Slovo "diskrétní" je v názvu míněno jako opak "spojitého".)

Povinná literatura:

P.Hliněný, Diskrétní matematika pro studenty informatiky, elektronický učební text, 2004, zde. J.Matoušek, J.Nešetřil. Kapitoly z diskrétní matematiky, Karolinum Praha 2000. (Konkrétně: Kapitoly 1,2 a kousek z 9 pro Část I přednášky. Kapitoly 3,4,5 pro Část II přednášky.) 10 výtisků knihy je v knihovně VŠB, ale prodejna skript ji neprodává. Knihu by mělo být možné koupit v knihkupectví Profesio v centru Ostravy, Hollarova ulice naproti ČSOB.

Doporučená literatura:

L.Kučera, Kombinatorické Algoritmy, SNTL, Praha, 1983.

Forma způsobu ověření studijních výsledků a další požadavky na studenta

Průběžná kontrola studia: Semestrální písemky. 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 třeba čas zhruba od 2 do 10 minut. Během písemek není možné 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Ě. Na konci vezme cvičící každému body z "nejlepších" osmi písemek a jejich součet vynásobí koeficientem 1,25. To je celkový počet bodů za semestrální písemky (maximum je 20 bodů). Témata písemek budou vždy vyvěšena na stránkách diskrétní matematiky, minimálně týden před písemkou. Zkouška. Ke zkoušce můžete jít, pokud máte nárok na zápočet. Hlavní součástí zkoušky je písemná práce zhruba na 75 minut. Na písemné zkoušce můžete získat až 60 bodů. Během zkoušky můžete používat také jedinou stranu A4 rukou psaných poznámek. Na tomto "zlegalizovaném taháku" mohou být definice, věty, vztahy. ALE NE ŘEŠENÉ PŘÍKLADY!!! Podmínky udělení zápočtu: Získat během semestru alespoň 10 bodů a samostatný referát musí být PŘIJAT.

E-learning

Další požadavky na studenta

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Přednášky: Čá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í, eqivalence, 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 a jeho aplikace. 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.) Aktuální průběh přednášek a promítané přednášky a jiné dokumenty. Cvičení: Procvičení učiva z přednášek v dané chronologii. Projekty: Vypracování jednoho samostatného písemného referátu, který se skládá z části kombinatorické a části, týkající se teorie grafů. Každá ze dvou částí bude hodnocena buď 0, 5 nebo 10 bodů, tedy stylem NE/TÉMĚŘ SPRÁVNĚ/ZCELA SPRÁVNĚ. Projekty naleznete na stránkách Petra Kováře. Někteří z vás NENAPSALI na odevzdaný projekt své JMÉNO. Tedy NENÍ v Katisu uveden jeho VÝSLEDEK. Proto se musí zmínění hříšníci dostavit osobně za opravujícím!

Podmínky absolvování předmětu

Kombinovaná forma (platnost od: 1960/1961 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodůMax. počet pokusů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51 3
        Zkouška Zkouška 70  0 3
        Zápočet Zápočet 30 (30) 10 1
                Zápočtová písemka Písemka 20  0 1
                Projekt Projekt 10  0 1
Rozsah povinné účasti:

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2009/2010 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2005/2006 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2005/2006 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2005/2006 (N2646) Informační technologie (1103T021) Počítačová matematika K čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2004/2005 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2004/2005 (N2646) Informační technologie (1103T021) Počítačová matematika K čeština Ostrava 1 povinný stu. plán
2003/2004 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2003/2004 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2003/2004 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2003/2004 (N2646) Informační technologie (1103T021) Počítačová matematika K čeština Ostrava 1 povinný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku

Hodnocení Výuky



2009/2010 zimní