Úvod do kombinatoriky a teórie grafov
2022/2023

Domov Kontakt Pravidlá Študijné materiály Cvičenia Domáce úlohy

Cvičenia

Týždeň č. 1 (13. – 17. februára 2023)

• Precvičená látka: Matematická indukcia, úplná matematická indukcia
• Prednáška: Dirichletov princíp (základná a frekvenčná forma)
• Odporúčané čítanie: oddiel o matematickej indukcii z knihy Matouška a Nešetřila (v treťom vydaní má číslo 1.3), oddiely o Dirichletovom princípe z Brualdiho knihy (v štvrtom vydaní majú čísla 2.1 a 2.2).

Týždeň č. 2 (20. – 24. februára 2023)

• Precvičená látka: Dirichletov princíp (základná a frekvenčná forma), optimalizačné kombinatorikcé úlohy.
• Pre ďalšie precvičovanie Dirichletovho princípu odporúčam knižku: Lev Bukovský, Igor Kluvánek: Dirichletov princíp, Škola mladých matematikov. Je v nej veľa úloh, niektoré aj s riešeniami alebo návodmi.
• Online prednáška z KMS na tému Dirichletov princíp. Pre tento predmet je relevantná len časť do 1:16:30. Nasledujúce úlohy svojou náročnosťou prekračujú rámec tohto predmetu.
• Prednáška: pravidlo súčtu a súčinu, variácie s opakovaním.
• odporúčané čítanie: oddiel „four basic counting principles” z brualdiho knihy (v štvrtom vydaní má číslo 3.1).

Týždeň č. 3 (27. 2. – 3. 3. 2023)

• Precvičená látka: Enumeračné pravidlá
• Odporúčané čítanie: súvisiace oddiely z knihy Matouška a Nešetřila (v treťom vydaní majú čísla 3.1, 3.2 a 3.3).
• Prednáška: variácie s opakovaním, zovšeobecnené pravidlo súčinu, kombinácie bez opakovania (definícia a zopár vlastností).

Týždeň č. 4 (6. – 10. 3. 2023)

• Precvičená látka: štandardné kombinatorické konfigurácie: variácie s opakovaním aj bez, kombinácie bez opakovania, úlohy s kruhom.
• Úlohy na precvičenie.
• Video s niekoľkými vyriešenými úlohami k cvikám.
• Prednáška: kombinácie bez opakovania, kombinačné čísla a ich vlastnosti, binomická veta
• V skriptách si k tomu prečíajte začiatok sekcie 3.5 Kombinácie bez opakovania (str. 39 – 41).

Týždeň č. 5 (13. – 17. 3. 2023)

• Precvičená látka: Kombinatorické dôkazy binomických identít.
• Prednáška: kombinácie bez opakovania, permutácie bez opakovania
• V skriptách sekcia 3.6 Kombinácie s opakovaním, permutácia s opakovaním (str. 45 – 47)

Týždeň č. 6 (20. – 24. marca 2023)

• Precvičená látka: Štandardné kombinatorické konfigurácie (kombinácie s opakovaním, permutácie s opakovaním, rôzne typy enumeračných úloh
• Prednáška: Princíp inklúzie a exklúzie
• Videoprednáška (Pokrýva celé skriptá, aj s príkladmi, o trochu viac ako bolo na prezenčnej prednáške.)

Týždeň č. 7 (27. – 31. marca 2023)

• Precvičená látka: Princíp inkúzie a exklúzie.
• Prednáška: riešenie úloh na PIE a iné kombinatorické konfigurácie.

Týždeň č. 8

• Cvičenia 5. 4. a 13. 4.: Počítanie súm
• Prednáška 5. 4. odpadla

Týždeň č. 9

• Cvičenia 12. 4. a 20. 5.: Asymptotické odhady
• Prednáška: Asymptotické odhady, odhady faktoriálu
• Videoprednáška

Týždeň č. 10 (24. 4. až 28. 4. 2023)

• Precvičená látka: Teória grafov – základné pojmy.
• Prednáška: Základné pojmy teórie grafov

Týždeň č. 11 (2. – 5. máj 2023)

• Precvičená látka: Stromy, bipartitné a eulerovské grafy.
• Prednáška: bipartitné a eulerovské grafy.

Týždeň č. 12 (9. – 13. máj 2021)

• Precvičená látka: teória grafov: súvislosť a planárne grafy
• Úlohy na precvičenie.
• Ďalšie úlohy na precvičenie Pre tento kurz sú relevantné len príklady po príklad s číslom 33.
• HOLOTŇÁK, Ondrej: Zbierka úloh z teórie grafov (diplomová práca) Obsahuje aj riešenia úloh a definície pojmov. Taktiež pokrýva témy aj nad rámec tohto predmetu.