Detail předmětu

Základy kombinatorické analýzy

FSI-SKAAk. rok: 2005/2006

Kurz je věnován základům kombinatorické analýzy a je zaměřen
především na problematiku kombinatorických metod. V úvodu kurzu
se studenti seznámí především s elementárními metodami a klasickými
konfiguracemi. V rámci kurzu je dále studována například problematika
rekurentních formulí, vytvořujících funkcí a úvod do Pólyovy enumerační
teorie. Část kurzu je věnována vybraným partiím z teorie grafů.
Teoretické vědomosti získané v kurzu jsou pro studenty základním
předpokladem pro úspěšné řešení kombinatorických úloh z praxe.

Jazyk výuky

čeština

Počet kreditů

3

Garant předmětu

doc. RNDr. Jiří Klaška, Dr.

Zajišťuje ústav

Ústav matematiky (ÚM)

Výsledky učení předmětu

Student získá základní znalosti o kombinatorických výpočeních metodách uvedených v anotaci kurzu, pochopí jejich logickou výstavbu a naučí se řešit kombinatorické úlohy tak,aby byl
schopen využívat získané znalosti a dovednosti v technických problémech.

Prerekvizity

Elementární vědomosti z matematické logiky a teorie množin.

Způsob a kritéria hodnocení

Požadavky na udělení zápočtu: aktivní účast ve cvičeních a klasifikace zápočtové písemky známkou lepší než F (nevyhovující). Výsledná klasifikace A:90-100% (výborně), B: 80-89% (velmi dobře), C: 70-79%(dobře), D: 60-69% (uspokojivě), E: 50-59% (dostatečně), F: 0-49% (nevyhověl).

Učební cíle

Cílem předmětu je seznámit studenty se základními enumeračními
metodami kombinatorické analýzy. Dalším cílem kurzu je naučit
studenty správně metodicky řešit základní typové úlohy a problémy
oboru. Získané dovednosti umožní studentům využívat teoretické
vědomosti při řešení rozmanitých problémů. Úkolem kurzu je
dále rozvíjet logické a abstraktní myšlení studentů.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Účast na cvičeních je kontrolovaná. Výuka probíhá dle týdenních rozvrhů. Stanovení způsobu forem nahrazování zameškané výuky je v kompetenci vedoucího cvičení.

Základní literatura

Hall, M.: Combinatorial Theory, , 0
Riordan, J.: An Introduction to Combinatorial Analysis, , 0
Stanley, R. P.: Enumerative Combinatorics, , 0

Doporučená literatura

Klaška, J.: Kombinatorická analýza, , 0

Zařazení předmětu ve studijních plánech

  • Program B3901-3 bakalářský

    obor B3910-00 , 2. ročník, letní semestr, volitelný (nepovinný)

Typ (způsob) výuky

 

Cvičení

26 hod., povinná

Vyučující / Lektor

doc. RNDr. Jiří Klaška, Dr.

Osnova

1. Základní výpočetní techniky enumerativní kombinatoriky, pravidlo součtu, pravidlo součinu.
2. Permutace, kombinace, binomické koeficienty, binomická věta.
3. Princip inkluze a exkluze.
4. Vlastnosti relací, relace ekvivalence, rozklady, Stirlingova čísla.
5. Uspořádané množiny.
6. Rekurentní formule, řešení rekurentních formulí.
7. Fibonacciho čísla.
8. Vytvořující funkce, formální mocninné řady.
9. Základní vlastnosti grup a cyklických grup.
10. Cyklový index grupy permutací, výpočet orbit, Burnsideovo lemma.
11. Pólyova věta, příklady a cvičení.
12. Úvod do teorie grafů, izomorfizmus grafů, enumerační problémy.
13. Zápočtová písemka, časová rezerva učitele.