Bakalářská státnice - Diskrétní matematika

bc. Informatika

Okruh požadavků Základy matematiky

Tato stránka není kompletní a/nebo může obsahovat chyby!

Uspořádané množiny.

• Zavedení kartézkeho součinu, relace, reflexivní, symetrické, transitivní relace, ekvivalence, funkce, bijekce. (zdroj: Kapitoly z diskrétní matematiky, 1.4.1 - 1.6.3)
• Definice uspořádání a bezprostředního předchůdce. (zdroj: Kapitoly z diskrétní matematiky, 1.7.1)
• Lineární a částečné uspořádání. (zdroj: Kapitoly z diskrétní matematiky, 1.7.1)
• Znázornění uspořádáných množin (Hasseův diagram). (zdroj: Kapitoly z diskrétní matematiky, 1.7.2)
• Isomorfizmus uspořádaných množin. (zdroj: Kapitoly z diskrétní matematiky, 1.7 cv.9)

Množinové systémy, párování, párování v bipartitních grafech (systémy různých reprezentantů).

http://en.wikipedia.org/wiki/Matching

• Zavedení pojmu množinový systém. (zdroj: Skripta Tomáše Vally, str. 21 / Kapitoly z diskrétní matematiky, str. 25)
• Systém různych reprezentantů. (zdroj: Skripta Tomáše Vally, str. 23)
• Incidenční graf množinového systému. (zdroj: Skripta Tomáše Vally, str. 21)
• Hallova věta. (zdroj: Skripta Tomáše Vally, str. 21-23)
• Párování. (zdroj: Skripta Tomáše Vally, str. 21)
• Perfektní párování. (zdroj: Skripta Tomáše Vally, str. 25)
• Tutteova věta. (zdroj: Skripta Tomáše Vally, str. 25)
• Edmondsův algoritmus. (zdroj: Skripta Tomáše Vally, str. 27-31)

Kombinatorické počítání.

• Počet zobrazení z N prvkové do M prvkové množiny (variace (s opakováním)). (zdroj: Kapitoly z diskrétní matematiky, str. 53)
• Počet podmnožin N prvkové množiny. (zdroj: Kapitoly z diskrétní matematiky, str. 54)
• Počet sudých a lichých podmnožin N prvkové množiny. (zdroj: Kapitoly z diskrétní matematiky, str. 55)
• Počet prostých zobrazení z N prvkové do M prvkové množiny (variace bez opakování). (zdroj: Kapitoly z diskrétní matematiky, str. 55)
• Definice permutace, cyklu permutace, faktoriálu. (zdroj: Kapitoly z diskrétní matematiky, str. 56-58)
• Definice binomického koeficientu a symbolu pro množinu všech k-prvkových podmnožin množiny. (zdroj: Kapitoly z diskrétní matematiky, str. 59-60)
• Kolika způsoby můžeme zapsat kladné číslo jako součet kladných čísel (přihrádky). (zdroj: Kapitoly z diskrétní matematiky, str. 61)
• Vlastnosti kombinačních čísel, Pascalův trojuhelník. (zdroj: Kapitoly z diskrétní matematiky, str. 62-63)
• Binomická věta. (zdroj: Kapitoly z diskrétní matematiky, str. 63)
• Multinomická věta. (zdroj: Kapitoly z diskrétní matematiky, str. 65)

Princip inkluze a exkluze.

• Princip inkluze a exkluze. (zdroj: Kapitoly z diskrétní matematiky, str. 82-86)
• Problém šatnářky (aplikace PIE). (zdroj: Kapitoly z diskrétní matematiky, str. 88-90)

Latinské čtverce a projektivní roviny.

• Definice konečné projektivní roviny. (zdroj: Kapitoly z diskrétní matematiky, str. 241)
• Definice řádu projektivní roviny. (zdroj: Kapitoly z diskrétní matematiky, str. 245)
• Vlastnosti projektivních rovin. (zdroj: Kapitoly z diskrétní matematiky, str. 244-245)
• Dualita u projektivních rovin. (zdroj: Kapitoly z diskrétní matematiky, str. 246)
• Definice latinského čtverce. (zdroj: Kapitoly z diskrétní matematiky, str. 253)
• Definice ortogonality latinských čtverců. (zdroj: Kapitoly z diskrétní matematiky, str. 253-254)
• Počet ortogonálních latinských čtverců řádu n. (zdroj: Kapitoly z diskrétní matematiky, str. 254)
• Souvislost existence konečné projektivní roviny a ortogonálních čtverců. (zdroj: Kapitoly z diskrétní matematiky, str. 255)
• Použití projektivních rovin. (zdroj: Kapitoly z diskrétní matematiky, str. 257-258)