PředmětyPředměty(verze: 797)
Předmět, akademický rok 2016/2017
   Přihlásit přes CAS
Kombinatorické počítání - NDMI015
Anglický název: Combinatorial Counting
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2015
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. RNDr. Martin Klazar, Dr.
Třída: Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: ()

Kombinatorická enumerace se zabývá počítáním konečných kombinatorických struktur, např. stromů, grafů, posloupností, rozkladů čísel a mnoha dalších. Pracuje s metodami elementárními, jako je počítání bijekcemi, ale i méně elementárními (o to zajímavějšími), jako jsou generující funkce. Generující funkce jsou fascinující technikou, která se používá kromě kombinatoriky i při analýze algoritmů, v teorii pravděpodobnosti a v teorii čísel. V přednášce se podíváme na základní výsledky a postupy kombinatorické enumerace.
Cíl předmětu -
Poslední úprava: T_KAM (20.04.2008)

Studenti se seznámí se základní technikou kombinatorické enumerace, vytvořujícími funkcemi.

Literatura -
Poslední úprava: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)

R.P. Stanley: Enumerative combinatorics I, Wandswort & Brooks, 1986

R.P. Stanley: Enumerative combinatorics II, Cambridge University Press, 1999

Sylabus -
Poslední úprava: ()

1) Úlohy kombinatorické enumerce.

2) Bijekce.

3) Generující funkce.

4) Kompoziční a exponenciální formule.

5) Lagrangeova inverzní formule.

6) Asymptotika.

 
Univerzita Karlova | Informační systém UK