Combinatorics and Graph Theory for teachers - OPBM3M043A

• Title: Kombinatorika a teorie grafů pro učitele
• Guaranteed by: Katedra matematiky a didaktiky matematiky (41-KMDM)
• Faculty: Faculty of Education
• Actual: from 2022
• Semester: summer
• E-Credits: 4
• Examination process: summer s.:
• Hours per week, examination: summer s.:2/1, MC [HT]
• Extent per academic year: 0 [hours]
• Capacity: 55 / 55 (unknown)
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Additional information: https://dl1.cuni.cz/course/view.php?id=3884
• Note: course can be enrolled in outside the study plan; enabled for web enrollment; priority enrollment if the course is part of the study plan
• Guarantor: doc. RNDr. Antonín Jančařík, Ph.D.
• Teacher(s): doc. RNDr. Antonín Jančařík, Ph.D.; Mgr. David Zenkl
• Is interchangeable with: OKBM3M043A

Annotation

English

The aim of the course is to acquaint future teachers with the basic concepts of discrete mathematics - combinatorics and graph theory, including application problems. After completing the course, the student should be able to solve combinatorial problems at the secondary school level (including examples from the Mathematical Olympiad) and apply basic graph algorithms. At the same time, he should be able to use mathematical software to solve these types of problems and to graphically represent graphs. Introduction, Dirichlet's principle Permutation without repetition Combination without repetition Variation without repetition Permutation with repetition Combination with repetition Variation with repetition Discrete probability Dependent and independent phenomena Graphs - basic concepts Graph algorithms I Graph algorithms II

Last update: Jančařík Antonín, doc. RNDr., Ph.D. (07.02.2022)

Czech

Cílem předmětu je seznámit budoucí učitele se základními pojmy diskrétní matematiky - kombinatoriky a teorie grafů, včetně aplikačních úloh. Po absolvování předmětu by měl být student schopen řešit kombinatorické úlohy na úrovni SŠ (včetně příkladů z matematické olympiády) a aplikovat základní grafové algoritmy. Současně by měl být schopen používat matematický software pro řešení uvedených typů úloh a pro grafické znázornění grafů. Úvod, Dirichletův princip Permutace bez opakování Kombinace bez opakování Variace bez opakování Permutace s opakováním Kombinace s opakováním Variace s opakováním Diskrétní pravděpodobnost Závislé a nezávislé jevy Grafy - základní pojmy Grafové algoritmy I Grafové algoritmy II

Last update: Jančařík Antonín, doc. RNDr., Ph.D. (28.09.2019)

Descriptors

Příprava na výuku
Doba očekávané přípravy na 1 hodinu přednášky  15 minut
Doba očekávané přípravy na 1 cvičení                  30 minut
Samostudium literatury (za semestr)                   20 hodin
Plnění průběžných úkolů (za semestr)                  20 hodin

Plnění předmětu
Seminární práce 20 hodin

Last update: Jančařík Antonín, doc. RNDr., Ph.D. (27.01.2022)

Course completion requirements

Student volí ze dvou možných cest plnění:

1. Podmínkou plnění předmětu je průběžná práce v seminářích – zapojení do diskuze, odevzdávání zpětné vazby a průběžné odevzdávání úkolů v LMS Moodle + odevzdání seminární práce zaměřené na grafové algoritmy.

2. Podmínkou plnění je napsání testu z kombinatoriky a diskrétní pravděpodobnosti a odevzdání seminární práce zaměřené na grafové algoritmy.

Last update: Jančařík Antonín, doc. RNDr., Ph.D. (26.01.2025)

Literature

M. Kubesa. Základy diskrétní matemtatiky. Plzeň: UČU, 2011. Dostupné na: http://mi21.vsb.cz/sites/mi21.vsb.cz/files/unit/zaklady_diskretni_matematiky.pdf

T. Roskovec. Kombinatorika na želvách. Praha: MFF UK, neuvedeno. Dostupné na: https://dl1.cuni.cz/pluginfile.php/286411/mod_resource/content/1/%C5%BEelvy.pdf

P. Hliněný. Základy teorie grafů. Brno: MU, 2010. Dostupné na: https://is.muni.cz/do/1499/el/estud/fi/js10/grafy/Grafy-text10.pdf

A. Večerka. Grafy a grafové algoritmy, Olomouc: UP, 2007. Dostupné na: https://phoenix.inf.upol.cz/esf/ucebni/Grafy_a_grafove_algoritmy.pdf

Last update: STEHLIKO (10.09.2019)

Syllabus

V předmětu budou probrána následující témata:

• Dirichletův princip
• Permutace bez opakování
• Kombinace bez opakování
• Variace bez opakování
• Permutace s opakováním
• Kombinace s opakováním
• Variace s opakováním
• Diskrétní pravděpodobnost
• Závislé a nezávislé jevy
• Grafy - základní pojmy
• Grafové algoritmy I
• Grafové algoritmy II

Last update: Jančařík Antonín, doc. RNDr., Ph.D. (27.01.2022)

Learning resources

https://dl1.cuni.cz/course/view.php?id=14939

Last update: Jančařík Antonín, doc. RNDr., Ph.D. (24.02.2023)

Learning outcomes

Proces učení

1. Studující popíše základní principy skupinové práce a zhodnotí svojí práci ve skupině.
2. Studující vyjmenuje základní principy efektivního učení matematice a diskutuje jejich užívání ve vlastní přípravě.
   
3. Studijící aplikuje metody formativního hodnocení a zpětné vazby na svoji aktivitu ve vyučovací hodině.

Výuka kombinatoriky

        1. Studující popíše základní organizační principy využívané při řešení kombinatorických úloh.
        2. Studující představí základní fáze řešení kombinatorických úloh ve výuce dle teorie G. Polya.
        3. Studující aplikuje základní otázky, které mají být při řešení kombinatorických úloh pokládány na konkrétní úloze.

Dirichletův princip

1. Studující vysvětlí Dirichletův princip a ilustruje jeho využití na příkladech z praxe.
2. Studující navrhne různé úlohy využívající Dirichletův princip.

Dirichletův princip

1. Studující vysvětlí Dirichletův princip a ilustruje jeho využití na příkladech z praxe.
2. Studující navrhne různé úlohy využívající Dirichletův princip a analyzuje chyby v řešeních.

Permutace bez opakování

1. Studující odvodí a vysvětlí vzorec pro výpočet permutací bez opakování a aplikuje jej na řešení úloh.
2. Studující vytvoří různé úlohy na permutace bez opakování a představí alternativní řešení týchž úloh.

Kombinace bez opakování

1. Studující formuluje a odůvodní vzorce pro kombinace bez opakování a použije je při modelování konkrétních situací.
2. Studující analyzuje chyby v žákovských řešeních úloh na kombinace bez opakování a navrhne zlepšení.

Variace bez opakování

1. Studující popíše rozdíl mezi variacemi a kombinacemi bez opakování a vysvětlí jejich využití.
2. Studující představí různé metody řešení úloh na variace bez opakování a porovná jejich efektivitu.

Permutace s opakováním

1. Studující definuje permutace s opakováním a vysvětlí, jak se liší od permutací bez opakování.
2. Studující navrhne didakticky vhodné příklady na permutace s opakováním a odhalí případné chyby v řešeních.

Kombinace s opakováním

1. Studující vysvětlí princip kombinací s opakováním a demonstruje jeho použití v praxi.
2. Studující analyzuje řešení úloh na kombinace s opakováním a navrhuje alternativní přístupy.

Variace s opakováním

1. Studující vysvětlí aplikaci variací s opakováním a porovná je s ostatními kombinatorickými metodami.
2. Studující vytvoří úlohy na variace s opakováním a navrhne jejich řešení s různými přístupy.

Diskrétní pravděpodobnost

1. Studující aplikuje základní principy diskrétní pravděpodobnosti na řešení úloh a odůvodní své postupy.
2. Studující analyzuje chyby v řešeních úloh z diskrétní pravděpodobnosti a navrhne správné řešení.

Závislé a nezávislé jevy

1. Studující definuje a odliší závislé a nezávislé jevy a aplikuje tyto koncepty při řešení úloh.
2. Studující prezentuje různé přístupy k řešení úloh týkajících se závislých a nezávislých jevů a porovná jejich výhody.

Grafy - základní pojmy

1. Studující vysvětlí základní pojmy teorie grafů a aplikuje je při modelování problémů.
2. Studující analyzuje chyby v interpretaci grafů a představí správné řešení úloh.

Grafové algoritmy

1. Studující popíše vybrané grafové algoritmy (např. Dijkstrův algoritmus) a vysvětlí jejich aplikace.
2. Studující navrhne a odůvodní různé přístupy k řešení úloh s grafovými algoritmy a analyzuje jejich efektivitu.

Permutace bez opakování

1. Studující odvodí a vysvětlí vzorec pro výpočet permutací bez opakování a aplikuje jej na řešení úloh.
2. Studující vytvoří různé úlohy na permutace bez opakování a představí alternativní řešení týchž úloh.

Kombinace bez opakování

1. Studující formuluje a odůvodní vzorce pro kombinace bez opakování a použije je při modelování konkrétních situací.
2. Studující analyzuje chyby v žákovských řešeních úloh na kombinace bez opakování a navrhne zlepšení.

Variace bez opakování

1. Studující popíše rozdíl mezi variacemi a kombinacemi bez opakování a vysvětlí jejich využití.
2. Studující představí různé metody řešení úloh na variace bez opakování a porovná jejich efektivitu.

Permutace s opakováním

1. Studující definuje permutace s opakováním a vysvětlí, jak se liší od permutací bez opakování.
2. Studující navrhne didakticky vhodné příklady na permutace s opakováním a odhalí případné chyby v řešeních.

Kombinace s opakováním

1. Studující vysvětlí princip kombinací s opakováním a demonstruje jeho použití v praxi.
2. Studující analyzuje řešení úloh na kombinace s opakováním a navrhuje alternativní přístupy.

Variace s opakováním

1. Studující vysvětlí aplikaci variací s opakováním a porovná je s ostatními kombinatorickými metodami.
2. Studující vytvoří úlohy na variace s opakováním a navrhne jejich řešení s různými přístupy.

Diskrétní pravděpodobnost

1. Studující aplikuje základní principy diskrétní pravděpodobnosti na řešení úloh a odůvodní své postupy.
2. Studující vysvětlí základní rozdíly v pojetí pravděpodobnosti v diskrétném a spojitém případě.

Závislé a nezávislé jevy

1. Studující definuje a odliší závislé a nezávislé jevy a aplikuje tyto koncepty při řešení úloh.
2. Studující prezentuje různé přístupy k řešení úloh týkajících se závislých a nezávislých jevů a porovná jejich výhody.

Grafy - základní pojmy

1. Studující vysvětlí základní pojmy teorie grafů a aplikuje je při modelování problémů.
2. Studující popíše úlohy z praxe, pro jejichž matematický model je vhodné využít grafy.

Grafové algoritmy

1. Studující popíše vybrané grafové algoritmy (např. Dijkstrův algoritmus) a vysvětlí jejich aplikace.
2. Studující navrhne a odůvodní různé přístupy k řešení úloh s grafovými algoritmy a analyzuje jejich efektivitu.

 

Last update: Jančařík Antonín, doc. RNDr., Ph.D. (26.01.2025)