Úvod do kombinatoriky a teórie grafov
2021/2022
Cvičenia
Cvičenie č. 1 (14. – 18. februára 2022)
- Precvičená látka: matematická indukcia, úplná matematická indukcia.
- Úlohy na precvičenie: 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).
Cvičenie č. 2 (24. / 28. februára 2022)
- Cvičenie prebieha v časoch:
- v stredu 24. 2. o 9:00 v M-IX,
- v pondelok 28. 2. o 12:20 v M-VI (posunuté o týždeň kvôli rektorskému voľnu).
- Precvičená látka: Dirichletov princíp (základná a frekvenčná forma), optimalizačné kombinatorikcé úlohy.
- Úlohy na precvičenie (dirichletov princíp).
- odporúčané čítanie: oddiel „four basic counting principles” z brualdiho knihy (v štvrtom vydaní má číslo 3.1).
- 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 predmtu.
- Prednáška: pravidlo súčtu a súčinu, variácie s opakovaním.
Cvičenie č. 3
- Cvičenie je odpadnuté kvôli rektorskému voľnu a našej absencii. Ako náhradu máte opakovacie úlohy na doma.
- Precvičená látka: opakovanie stredoškolskej kombinatoriky.
- Úlohy na precvičenie (opakovanie stredoškolskej kombinatoriky).
- 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).
Cvičenie č. 4 (7. – 11. marca 2022)
- Precvičená látka: štandardné kombinatorické konfigurácie: variácie s opakovaním aj bez, kombinácie bez opakovania.
- Úlohy na precvičenie.
- Video s niekoľkými vyriešenými úlohami k cvikám.
Cvičenie č. 5 (14. – 18. marca 2022)
- Precvičená látka: kombinatorické dôkazy binomických identít.
- Úlohy na precvičenie.
- Prednáška: identity a nerovnosti s kombinačnými číslami, úvod do kombinácií bez opakovania
Cvičenie č. 6 (21. – 25. marca 2022)
- Precvičená látka: počítanie súm
- Úlohy na precvičenie.
- Prednáška: polynomická veta, princíp inklúzie a exklúzie
- Text k prednáške viete nájsť v knihe od Matoušek, Nešetřil: Kapitoly z diskrétní matematiky, sekcia 2.4 (str. 69 – 76).
Cvičenie č. 7 (28. marca – 1. apríla 2022)
- Precvičená látka: štandardné kombinatorické konfigurácie 2: kombinácie s opakovaním, permutácie s opakovaním, rôzne úlohy
- Úlohy na precvičenie.
- Rozširujúce čítanie pre záujemcov: kapitola o vytvárajúcich (generujúcich) funkciách z knihy Matouška o Nešetřila (v treťom vydaní má číslo 12).
- V skriptách sekcia 3.6 Kombinácie s opakovaním, permutácia s opakovaním (str. 45 – 47)
- Prednáška: opakovanie pred písomkou. Môžete si pozrieť minuloročnú písomku a jej riešenia.
Cvičenie č. 8 (4. – 8. apríl 2022)
Cvičenie č. 9 (11. – 15. apríl 2022)
- Precvičená látka: asymptotické odhady.
- Úlohy na precvičenie (asymptotika).
- Odporúčané čítanie: oddiel o princípe zapojenia a vypojenia z knihy Matouška a Nešetřila (v treťom vydaní má číslo 3.6).
- Ďalšie odporúčané čítanie: relevantné oddiely kapitoly o
princípe zapojenia a vypojenia z Brualdiho knihy (táto kapitola má v
štvrtom vydaní číslo 6).
- Prednáška: Odhady faktoriálu, základné grafové pojmy, izomorfizmus
Cvičenie č. 10 (20. a 26. apríl 2022)
Cvičenie č. 11 (2. – 6. máj 2022)
Cvičenie č. 12 (9. – 13. máj 2021)