Kate Konczycki

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:

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í:

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í:

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.