Kombinatorika a grafy 1 — cvičení ZS 2025/26

Stránka cvičení k předmětu Kombinatorika a grafy 1 [NDMI011], kterou přednáší Josef Tkadlec, pro paralelky: pondělí 12:20 v S6 a úterý 15:40 v S6. Obsah cvičení bude pro obě paralelky podobný, ale pondělní bude (alespoň ze začátku) mírně pozadu oproti úterní, protože předchází přednášce.

V případě jakýchkoliv otázek, nejasností, nebo dotazů mě neváhejte kontaktovat e-mailem na adresu miksanik (at) iuuk.mff.cuni.cz nebo osobně na cvičení. Konzultace jsou možné po předchozí domluvě emailem nebo na cvičení.

Na této stránce najdete:

Zápočet

Během semestru bude možné získat alespoň 150 bodů:

Pro získání zápočtu je potřeba získat alespoň 100 bodů. Pokud získáte alespoň 80 bodů z toho alespoň 50 bodů za testy, vyřešením dodatečných úkolů můžeze získat chybějící body.

Domácí úkoly

Na řešení domácích úkolů byste se měli aktivně podílet, nazávisle na tom jestli řešíte domácí úkol samostatně nebo s někým, respektive s něčím. Do řešení uveďte s kým, respektive s čím, jste na řešení spolupracovali a jak spolupráce vypadala. V každém případě je podmínkou, abyste řešení pochopili a sepsali podle vlastních slov. Jako extra motivaci můžu slíbit, že podobné příklady se vyskytnou v testech.

Pokud si s domácím úkolem (případně s nějakým krokem) nevíte rady po jednotkách až nižších desítkách minut přemýšlení, měli byste to konzultovat s někým (spolužákem, mnou, ...) nebo s něčím (knížkou, internetem, ChatGPT, ...). Konzultace nemají žádný vliv na počet získaných bodů, ale musíte je přiznat. Podobně pokud si nejste jistí správností nějakého kroku (je jedno jestli je váš nebo někoho jiného). Je lepší to přiznat (a vyjasnit proč), než-li se tvařit, že tomu rozumíte. Opět tohle nemá vliv na počet získaných bodů, ale musíte je přiznat.

Do bodování domácích úkolů se budu snažit zohlednit vaše vynaložené usilí a kritické myšlení. To samozřejmě budu posuzovat jen podle toho co odevzdáte, tak si na tom prosím dejte záležet. Tedy i za častečně řešení můžete získat plný počet bodů.

O tom, jak sepisovat řešení nejen domácích úkolů, si můžete přečíst na stránce Martina Kouteckého a/nebo na stránkách korespondenčního semináře MKS.

Soubory s domácími úkoly (spolu s termínem odevzdání) se budou postupně zadávaný na Sovičce, kde řešení taky odevzdávejte (nejlépe ve formátu PDF). Každý úkol bude zadán nejpozději v den cvičení, termín odevzdání bude zpravidla příští týden ve čtvrtek. Přístupový token jste obdrželi e-mailem v průběhu prvního týdne–pokud jste ho neobdrželi, napište mi prosím email.

Obsah cvičení

Úterý (Příklady):Plán: Asymptotické odhady (dokončení příkladu 8 z minulého cvičení). Vytvořující funkce.
Datum Souhrn
#1 29.9 – 3.10 Pondělí (Příklady): Organizační věci (zápočet, průběh cvičení, ...). Opakování kombinatorického počítání z předmětu Diskrétní Matematiky: rozmísťování k kuliček do n přihrádek, princip inkluze-exkluze (příklady 1-7, částečné řešení příkladu 7).

Úterý (Příklady): Organizační věci (zápočet, průběh cvičení, ...). Opakování kombinatorického počítání z předmětu Diskrétní Matematiky: rozmísťování k kuliček do n přihrádek, princip inkluze-exkluze (příklady 1-7, částečné řešení příkladu 7). Asymptotické odhady (rozpracovali jsme příklad 9, který dokončíme na příštím cvičení).
#2 6.10 – 10.10 Pondělí (Příklady): Asymptotické odhady (příklad 3 a částečně příklad 1). Hrátky s polynomy (aka příprava na vytvořující funkce) (příklad 4).

Úterý (Příklady): Asymptotické odhady (dokončení příkladu 9 z minulého cvičení). Vytvořující funkce I: hledání v. f. pro zadanou posloupnost, hledání posloupnosti odpovídající dané v. f., základní operace s v. f.(příklady 4a-e, 5a-c).
#3 13.10 – 17.10 Pondělí (Příklady): Plán: Vytvořující funkce (hledání v. f. pro posloupnost, hledání posloupnosti odpovídající v. f., základní operace s v. f., ...).

Úterý (Příklady): Plán: Vytvořující funkce (základní operace s v. f., hledání vzorce pro n-tý člen rekurentně zadané posloupnosti, další aplikace v. f., ...).
#4 20.10 – 25.10 Pondělí (Příklady): Bude zaskakovat Pepa Tkadlec

Úterý (Příklady): Bude zaskakovat Tomáš Hons.

Další příklady na procvičení:

Užitečné odkazy: