Úvod do kombinatoriky a teorie grafů. Důraz je kladen na aktivní
zvládnuti základních pojmů a metod (relace, zobrazení, graf;
přesná formulace matematických tvrzení, řešení příkladů a dokazovaní
jednoduchých tvrzení).
Poslední úprava: T_KAM (06.05.2001)
Introduction to combinatorics and graph theory. We lay stress on active knowledge of basic definitions and methods (relation, mapping, graph, exact formulation of mathematical theorems, problem solving and proofs of simple statements).
Podmínky zakončení předmětu -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (30.09.2020)
Zápočet bude udělen za zisk dostatečného počtu bodů udělovaných průběžně za písemné testy, řešení domácích úloh, aktivitu na hodinách, popř. docházku. Přesné podmínky stanoví cvičící. Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani náhradních domácích úkolů.
Zkouška v paralelce M. Mareše bude ústní s písemnou přípravou a bude pokrývat jak řešení příkladů, tak teorii. V paralelce M. Tancera se zkouška skládá z písemné části s řešením příkladů a ústní části z teorie. Podle epidemiologické situace může být písemná část nahrazena ústní, popřípadě může být zkouška u obou zkoušejících být vedena distančně online.
Poslední úprava: doc. Hans Raj Tiwary, M.Sc., Ph.D. (25.09.2020)
Hans Raj Tiwary:
For passing the tutorial it is necessary to obtain 50% from weekly homeworks.
Due to the nature of requirements, there will not be additional opportunities to pass the tutorial.
It is necessary to pass the tutorial to be able to take the exam for course credit. It is possible to take the final exam remotely.
Literatura -
Poslední úprava: G_I (25.01.2007)
J. Matousek, J. Nesetril: Kapitoly z diskretni matematiky, nakladatelstvi Carolinum, Praha, 2000
Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (22.11.2012)
J. Matousek, J. Nesetril: Invitation to Discrete Mathematics, Oxford University Press, 2008, 2nd edition.
Požadavky ke zkoušce -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (15.10.2018)
Zkouška se skládá z písemné a ústní části. Ústní část proběhne formou diskuse řešení písemné části a případných doplňujících otázek.
Poslední úprava: doc. Hans Raj Tiwary, M.Sc., Ph.D. (25.09.2020)
Hans Raj Tiwary:
There will be a written exam at the end of the semester to test knowledge and understanding of the course material as well as problem solving. The exam will have three parts, one dedicated to each of the above. It is necessary to pass each part in order to pass the exam. There will be three opportunities to take the written exam whose dates will be announced in advance.
Detailed format of the exam can be found on the course webpage.
Sylabus -
Poslední úprava: doc. RNDr. Jiří Fiala, Ph.D. (21.09.2021)
Základní značení, motivační příklady, co je důkaz, důkaz indukcí.
Funkce, relace, ekvivalence. Permutace.
Základní kombinatorické počítání (počet podmnožin, k-prvkových podmnožin, všech zobrazení, prostých
zobrazení, permutací). Binomická věta. Odhady faktoriálu a binomických koeficientů.
Princip inkluze a exkluze a jeho aplikace (šatnářka).
Pravděpodobnostní prostor (nejvýš spočetný, všechny podmnožiny jsou jevy). Nezávislé jevy, podmíněná
pravděpodobnost. Náhodná veličina, distribuční funkce. Střední hodnota a její výpočet. (Základní diskrétní
pravděpodobnostní rozdělení).
Základní pojmy z grafů, cesta/tah/sled, izomorfismus apod.
Charakterizace eulerovských grafů (též orientovaný případ, silná a slabá souvislost).
Stromy (různé charakterizace, existence listu).
Rovinné grafy, Eulerova formule, maximální počet hran.