Základní seznámení s kombinatorikou a teorií grafů.

Základní seznámení s kombinatorikou a teorií grafů.

Obsah přednášek a cvičení:

  1. základy práce s komplexními čísly, princip matematické indukce
  2. binomická a multinomická věta, koeficienty, faktoriál a jeho odhady, jednoduché kombinatorické úlohy (narozeninový problém)
  3. princip inkluze a exkluze a jeho aplikace (počítání prvočísel, úloha o šatnářce, Eulerova funkce)
  4. neorientované grafy a jejich klasifikace, isomorfismus grafů, princip sudosti, skóre grafu (Havel-Hakimi)
  5. souvislost grafu, matice sousednosti a jejích mocniny, prohledávání do hloubky a šířky, nejkratší cesta (Dijsktra, Floyd), Eulerovský tah
  6. stromy, jejich kód a kreslení, isomorfismus stromů, minimální kostra grafu (Prim, Kruskal), rovinné grafy (Euler)

Přednášky a cvičení se nebudou metodicky odlišovat, v obou bude vysvětlována nová látka a zároveň hned procvičována. Konzultace jsou možné po přednášce nebo cvičení, není nutné se na ně přihlašovat. 

Podmínkou získání zápočtu jsou: 

  1. dostatečná docházka (je dovoleno maximálně 4x vynechat)
  2. úspěšné napsání dvou zápočtových testů (minimálně na 50%) s tím, že výsledek jednoho testu je možno vylepšit výsledkem náhradního zápočtového testu
  3. vypracování alespoň 4 domácích úloh (minimálně na 50%, bude detailně ověřeno u ústní části zkoušky)

 

Zkouška bude kombinovaná - písemná a ústní. Ústní zkouška není vázána časově na zkoušku písemnou a student ji absolvuje se v jiný termín, který bude upřesněn.  Ústní část zkoušky bude probíhat v kanceláři vyučujícího (S-211, stará budova, druhé patro). 

 

Písemná část zkoušky: Nezapomeňte si s sebou přinést index! K písemné části budou povoleny Vaše ručně psané poznámky, v rozsahu až 10 papírů formátu A4, dále je možno si s sebou přinést kalkulačku, ne však mobilní telefon, stejně tak ne počítač.

 

Ústní část zkoušky: Ti, kteří uspějí alespoň na 50% v písemném zkouškovém testu postupují ke závěrečné zkoušce ústní. Jejím hlavním smyslem je:

  1. doladění výsledné známky (ta bude navržena pouze na základě výsledků písemné části zkoušky, ústní zkouškou je jí možno maximálně o půl stupně změnit nahoru i dolů)
  2. ověření vypracovaných domácích úloh
  3. zapsání známky společně se zápočtem do indexu 

Při ústní zkoušce budeme diskutovat výsledky písemného testu, případně zápočtových testů a vypracovaných domácích úloh. Budou opět povoleny Vaše ručně psané poznámky, v rozsahu až 10 papírů formátu A4, dále je možno si s sebou přinést kalkulačku a také počítač k demonstraci Vašich řešení. Přineste si s sebou také výtisknuté Vaše řešení domácích úloh, urychlíme tím průběh zkoušky. 

Literatura

  1. část kurzu (kombinatorika) bude probíhat podle skript Ondřeje Pangráce (odkaz zde)
  2. druhá část (teorie grafů) podle skript Petra Kováře (odkaz zde)

K procvičování lze doporučit skripta Michaela Kubesy (odkaz zde) a k procvičování sbírku příkladů Petra Kováře (odkaz zde). Základy o práci s komplexními čísly jsou zde, pár příkladů na matematickou indukci zde.  Dále je doporučena kniha Jiřího Matouška a Jaroslava Nešetřila - Kapitoly z diskrétní matematiky (odkaz k zakoupení zde).