Úvod do kombinatoriky a teórie grafov
2024/2025
Cvičenia
V materiáloch k cvičeniam sú zvyčajne niektoré úlohy označené šípkou. Ide o výber dôležitých úloh, ktoré sa prevažne budú riešiť na cvičeniach. Pokiaľ sa nejaké nestihnú, tak je odporúčané, aby ste si ich vyriešili doma.
Týždeň č. 1 (17. 2. – 21. 2. 2025)
- Precvičená látka: Matematická indukcia, úplná matematická indukcia
- Prednáška: Dirichletov princíp (základná a frekvenčná forma), pravidlo súčtu a súčinu
- 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 (24. 2. – 28. 2. 2025)
- Precvičená látka: Dirichletov princíp (základná a frekvenčná forma), optimalizačné kombinatorické ú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: 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 (3. 3. – 7. 3. 2025)
- 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, kombinácie bez opakovania (definícia, počet a zopár vlastností).
Týždeň č. 4 (10. 3. – 14. 3. 2025 )
- Precvičená látka: Štandardné kombinatorické konfigurácie : variácie s opakovaním aj bez, kombinácie bez opakovania, úlohy s kruhom.
- 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čítajte začiatok sekcie 3.5 Kombinácie bez opakovania (str. 39 – 41).
Týždeň č. 5 (17. 3. – 21. 3. 2025)
- Precvičená látka: Kombinatorické dôkazy binomických identít.
- Prednáška: kombinácie s opakovaním, princíp inklúzie a exklúzie
- V skriptách sekcia 3.6 Kombinácie s opakovaním, permutácia s opakovaním (str. 45 – 47)
- Videoprednáška (Pokrýva celé skriptá, aj s príkladmi, o trochu viac ako bolo na prezenčnej prednáške.)
Týždeň č. 6 (24. 3. – 28. 3. 2025)
- Precvičená látka: Počítanie súm
- Prednáška: Riešenie rôznych enumeračných úloh
Týždeň č. 7 (31. 3. – 4. 4. 2025)
- Precvičená látka: Kombinatorické konfigurácie II
- 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).
- Prednáška: Asymptotické odhady
- Videoprednáška
Týždeň č. 8 (7. 4. – 11. 4. 2025)
- Cvičenia: Princíp inklúzie a exklúzie
- Prednáška 9. 4. odpadla (ŠVK)
Týždeň č. 9 (14. 4. – 18. 4. 2025)
- Cvičenia: z týždňa 8
- 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).
- Prednáška: Enumeračné vety a programovanie
Týždeň č. 10 (21. 4. – 25. 4. 2025)
- Precvičená látka: Asymptotické odhady.
- Prednáška: Úvod do teórie grafov