Jak řešit domácí úkoly

Mnoho matematických domácích úkolů na MFF UK, na rozdíl od úkolů na středních školách, nespočívá ve vypočítání nějaké konkrétní hodnoty. Místo toho po vás bude žádáno vyslovit matematické tvrzení, a pak jej dokázat. Nebo dostanete tvrzení a vaším úkolem jej bude dokázat, případně vyvrátit. S výpočetními příklady se též setkáte, ale i v takovém případě se po vás často bude chtít tento výsledek odůvodnit důkazem.

Jeden z účelů výuky na MFF UK je naučit vás umění tvoření matematických tvrzení a jejich dokazování. To se vybudovává a vylepšuje po celou dobu studia. Nedílnou součástí tohoto umění je hluboké porozumění látce.

Matematický korespondenční seminář tento postup hezky popisuje ve své sekci Jak řešit.

Formulace tvrzení

Pokud chcete formulovat matematické tvrzení, musíte si dát pozor, aby toto tvrzení dávalo smysl a bylo jednoznačně pochopitelné. Zkuste myslet na tyto věci:

• Pokud mluvíte o nějaké věci, jednoznačně ji definujte a označte. Pak se na tuto věc odkazujte jejím označením. Nepoužívejte zájmena, tím výrazně kazíte přehlednost.
• Dejte si pozor na kvantifikaci. Je rozdíl, pokud říkáte něco, co obecně platí o všech věcech daného typu, nebo jen o jedné konkrétní.
• Pokud tvrzení vyžaduje, aby pro jeho platnost byly splněny předpoklady, uveďte je všechny.
• Zkuste tvrzení napsat a pak jej sami po sobě přečíst. Případně jej ukažte někomu jinému. Tím často odhalíte nejasnosti a pomůžete si rozmyslet, zda platí.

Samozřejmě, pokud je vaše tvrzení součástí uceleného textu, můžete využít kontextu z předchozích částí. Naopak, pokud se tvrzení snažíte formulovat jako samostatný celek, třeba větu nebo lemma, všechny důležité věci zopakujte tak, aby se mohlo vytrhnout z kontextu.

Dokazování

První krok při dokazování je vytvořit něco, co bude matematický důkaz. Ten si lze představit jako postup, kdy postupně z tvrzení, která již platí, odvozujete nová tvrzení, než se dostanete k hledanému výsledku.

Pokud si nevíte rady, jak něco dokázat, zkuste si rozmyslet následující:

• Jak jsou věci, se kterými pracujeme, definované? Co z definice vyplývá? Pokud samotná definice odkazuje na jinou definici, co vyplývá z ní?
• Jaké jiné již dokázané věty máme k dispozici a týkají se toho, co chceme dokázat? Umíme splnit všechny jejich předpoklady?
• Co by se stalo, kdyby naopak to, co chceme dokázat, neplatilo?
• Pokud něco dokazujeme o existenci objektu, jak takový objekt najít?
• Pokud naopak chceme vyvrátit, že skupina objektů má nějakou vlastnost, můžeme najít protipříklad -- objekt, který ji nesplňuje?
• Co jsou předpoklady a co se snažíme dokázat? Využili jsme všechny předpoklady, které máme k dispozici?
• Pokud chceme dokázat optimalitu nějakého řešení, ukázali jsme, že lépe to jít nemůže, a to pro libovolné jiné řešení?
• Vyřešili jsme všechny možné případy, které mohou nastat?

Jakmile máte v ruce (nebo v hlavě) matematický důkaz, o kterém jste přesvědčení, že je správně, je další důležitý krok tento důkaz srozumitelně sepsat. Zde platí stejné připomínky jako u formulace tvrzení a navíc myslete na následující:

• Komentujte, jak postupujete, co děláte a proč to děláte. Pokud pouze napíšete matematickou rovnici, kterou pouze upravujete, dokud se nedostanete k výsledku, tak nemusí být vůbec jasné, proč jde ty úpravy udělat. Nebojte se používat slova.
• Okomentujte, které techniky budete používat před tím, než je skutečně v textu použijete. To udělejte vždy, i v případě, že vám osobně je jasné, že to tak musí být. Čtenáři to nemusí být tak jasné, jako vám.
• Pokud něco dokazujete indukcí, napište na začátku podle čeho. Pak na místě, kde použijete indukční předpoklad, o tom napište.
• Pokud při dokazování zavádíte nové proměnné nebo objekty a plánujete o nich mluvit později, označte si je. Je lepší to s označením trochu přehnat, než naopak neznačit nic a pak se utopit v zájmenech a relativních odkazech.
• Před tím, než důkaz napíšete naostro, sepište si jej nejprve někde vedle, třeba i na počítači, a pak si jej několikrát přečtěte. Tím si uvědomíte nejasnosti nebo ošklivé formulace.
• Pokud při důkazu provádíte rozbor případů, nezapomeňte ukázat, že je úplný, tedy byly rozebrány všechny možné případy.
• Pokud se ve svém důkazu opíráte o nějaké tvrzení z přednášky, nemusíte jej znovu dokazovat. Pak si ale dejte pozor, že jste toto tvrzení nepozměnili.

Algoritmy

Může se též stát (a v mnoha předmětech se tak bude dít často), že budete chtít popsat algoritmus.

Když už algoritmus popisujete, mělo by být jasné, jak přesně tento algoritmus funguje. Slovní popis lze použít, ale nemusí být vždy dostatečně jednoznačný. Často tak můžete místo toho algoritmus popsat pseudokódem. Ten naopak nemusí být programovací jazyk, v pseudokódu můžete (a často chcete) používat slova.

Nezapomeňte pro svůj algoritmus dokázat, že je korektní, pokud to není zcela zřejmé z předchozích argumentů.

Jestliže něco tvrdíte o vlastnostech algoritmů, ať už časovou složitost, vždy tyto vlastnosti dokažte. Důkaz se může nacházet v předchozí části textu, pak na něj raději odkažte nebo to alespoň zmiňte.

Když analyzujete složitost algoritmu, zkuste nejprve ukázat složitost dílčích kroků a následně předveďte, jak se tyto kroky zkombinují. Dejte si pozor na to, že některé zdánlivě jednoduché kroky mohou mít netriviálně velkou složitost.

Pokud tvrdíte, že je algoritmus optimální, dokažte, že žádný lepší nemůže existovat. To je ale obecně často těžký úkol, pokud nemáte k dispozici jiné známé dolní odhady.

Pokud byste chtěli více inspirace k tomu, jak popisovat algoritmy, podívejte se na vzorová řešení KSP.