Kombinatorické počítání - NDMI015

• Anglický název: Combinatorial Counting
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2018
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: http://kam.mff.cuni.cz/~klazar/KPOC19.html
• Garant: doc. RNDr. Martin Klazar, Dr.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

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.

angličtina

Poslední úprava: T_KAM (07.05.2001)

Introduction to enumerative combinatorics. Basic techniques (ordinary and exponential generating functions, Lagrange inversion formula, bijective proofs) are explained on a number of concrete examples in which we shall count combinatorial structures of various kinds.

Cíl předmětu

čeština

Poslední úprava: T_KAM (20.04.2008)

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

angličtina

Poslední úprava: T_KAM (20.04.2008)

Students learn the fundamental technique of combinatorial enumeration, which are generating functions.

Podmínky zakončení předmětu

čeština

Poslední úprava: doc. RNDr. Martin Klazar, Dr. (30.04.2020)

Zkouška je ústní, s písemnou přípravou. Konkrétní požadavky jsou/budou na stránce předmětu,

viz stránka vyučujícího.

************************************************************************

Aktualizace v souvislosti s koronavirovou pandemií a návaznými opatřeními na jaře

a v létě r. 2020. Forma zkoušky (kontaktní či distanční) bude určena pro každý

termín zvlášť podle aktuálních okolností, forma a průběh zkoušení bude stanovena při vypsání příslušného termínu v SISu.

Kontaktní zkouška bude písemná s možností ústního dozkoušení. U tohoto předmětu se nicméně jeví pravděpodobnou

kontaktní forma v malých skupinách (<6, <11 lidí?).

angličtina

Poslední úprava: doc. RNDr. Martin Klazar, Dr. (14.05.2020)

Oral exam, with written preparation. Exam question are/will be given on the course page,

see teacher's web page.

************************************************************************

As to situation caused by the current coronavirus pandemia in spring and summer 2020.

Form of exam (contact or distant) will be determined for each term in SIS

according to actual situation. Contact exam will be writen one with possible oral part.

For this course the contact form in small groups (<6, <11 people) appears probable.

Literatura

čeština

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

angličtina

Poslední úprava: T_KAM (20.04.2008)

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

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

Požadavky ke zkoušce

čeština

Poslední úprava: doc. RNDr. Martin Klazar, Dr. (30.04.2020)

Zkouška je ústní, s písemnou přípravou. Konkrétní požadavky jsou/budou na stránce předmětu,

viz stránka vyučujícího.

************************************************************************

Aktualizace v souvislosti s koronavirovou pandemií a návaznými opatřeními na jaře

a v létě r. 2020. Forma zkoušky (kontaktní či distanční) bude určena pro každý

termín zvlášť podle aktuálních okolností, forma a průběh zkoušení bude stanovena při vypsání příslušného termínu v SISu.

Kontaktní zkouška bude písemná s možností ústního dozkoušení. U tohoto předmětu se nicméně jeví pravděpodobnou

kontaktní forma v malých skupinách (<6, <11 lidí?).

angličtina

Poslední úprava: doc. RNDr. Martin Klazar, Dr. (14.05.2020)

Oral exam, with written preparation. Exam question are/will be given on the course page,

see teacher's web page.

************************************************************************

As to situation caused by the current coronavirus pandemia in spring and summer 2020.

Form of exam (contact or distant) will be determined for each term in SIS

according to actual situation. Contact exam will be writen one with possible oral part.

For this course the contact form in small groups (<6, <11 people) appears probable.

Sylabus

čeština

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.

angličtina

Poslední úprava: T_KAM (20.04.2008)

1. Problems of combinatorial enumeration. 2. Bijections. 3. Generating functions. 4. Exponential and composition formula. 5. Lagrange's inversion formula. 6. Asymptotic estimates.