Kombinatorika pro bioinformatiky

Přehled odpřednesené látky:

• 4.10. - Binární relace - definice, vlastnosti, funkce, ekvivalence a částečná uspořádání.
• 11.10. - Kombinatorické počítání - počty funkcí a množin, kombinační čísla a jejich vlastnosti.
• 18.10. - Binomická věta (dokončení komb. počítání), Princip inkluze a exkluze a Dirichletův princip (tvrzení a důkazy, bez aplikací)
• 25.10. - Aplikace Principu inkluze a exkluze (šátnářka, surjekce, Eulerova funkce - není na videu, přečtěte si to) a Dirichletova principu
• 1.11. - Úvod do pravděpodobnosti - def. pravděpodobnostního prostoru, nezávislost jevů, podmíněná pravděpodobnost, věta o úplné pravděpodobosti a Bayesova věta
• 8.11. - Náhodné veličiny, střední hodnota a rozptyl, linearita stř. hodnoty, Markovova a Čebyševova nerovnost
• 15.11. - Úvod do teorie grafů - základní pojmy, izomorfismus grafů, podgrafy a indukované podgrafy, souvislost a vzdálenost v grafech, stupeň vrcholu, případně (okrajově) maticové reprezentace grafů
  příklady k úvodní grafové přednášce (v pondělí jsme je udělali všechny, středeční skupina je bude mít až spolu se stromy)
• 22.11. - Stromy a kostry grafů - základní pojmy a vlastnosti stromů, definice kostry grafu, počet koster úplného grafu
• 29.11. - Rovinné grafy - definice a základní vlastnosti, počty hran, vrcholů a stěn, max. počet hran rov. grafu, duální graf
• 6.12. - Barevnost grafů - pojmy barevnost, klikovost a nezávislost grafu a vztahy mezi nimi, d-degenerované grafy, barevnost rovinných grafů
  jiné zpracování věty o pěti barvách
• 13.12. - Platónská tělesa a maticové reprezentace grafů
• 20.12. - Eulerovské grafy verze pro orientované grafy, problém kotouče
• 3.1. - Aplikace grafů na bioinformatické problémy

Textové podklady a záznamy on-line přednášek ze zimního semestru 2020/2021.

• Relace: pdf, video
• Kombinatorické počítání: pdf, video1, video2
• Princip inkluze a exkluze: pdf, video
• Dirichletův princip: pdf, video
• Diskrétní pravděpodobnost: pdf, video1, video2, video3
• Teorie grafů - úvod: pdf, video1, video2
• Stromy a kostry: pdf, video1, video2
• Roviné grafy: pdf, video
• Barevnost grafů: pdf, video
• Platónská tělesa: pdf, video
• Eulerovské grafy: pdf, video
• Aplikace v bioinformatice: pdf, video

Příklady na procvičování (nejen kombinatoriky) lze nalézt ve Sbírce úloh.