Jak sepisovat domácí úkoly

V prvním ročníku na MFF UK se mnozí z vás poprvé setkají s potřebou sepsat matematický důkaz. Jedním z hlavních "skrytých" úkolů diskrétní matematiky je vás tomuto umění naučit.

První krok je dokázat vytvořit něco, co bude skutečně matematickým důkazem. K tomu je slušný návod v sekci Jak řešit Matematického korespondenčního semináře. Druhý krok je naučit se navíc důkaz sepsat tak, aby pro čtenáře nebylo příliš obtížné ho pochopit.

Ovládnutí této dovednosti zabere dlouhé roky a často vyžaduje hlubší porozumění látce. Musíte totiž nejen vyřešit příklad, ale i najít všechny body, v nichž by mohlo být vaše řešení špatně pochopeno. Proto se zde omezíme na seznam několika rad, které vám umožní vyhnout se nejčastějším začátečnickým chybám.

• Komentujte, co děláte. Často se stává, že student podlehne dojmu, že jediný způsob, jak sepsat formální důkaz, je napsat pouze sérii úprav rovností, nerovností a logických formulí, a že jakmile použijí češtinu (či jiný lidsky srozumitelný jazyk), je jejich řešení nutně nedostatečně formální. To ale rozhodně není pravda. Naopak řešení obsahující pouze matematické výrazy bývá často na hraně pochopitelnosti.
• Napište, které techniky při řešení použijete, než tak učiníte. Pokud se rozhodnete, že použijete například matematickou indukci, v řešení by to mělo být zřetelně napsáno, a to i v případě, že jsme ji dělali na posledním cvičení a vám přijde, že je absolutně vyloučené, aby příklad někdo řešil jakkoli jinak.
• Speciálně, u důkazu sporem nezapomeňte napsat, že provádíte důkaz sporem. Dobrá úvodní formulace je Pro spor předpokládejme, že máme x takové, že....
• Pokud mluvíte o nějakých objektech (dominových kostkách, kuličkách, grafech,...), nepoužívejte k jejich označení zájmena. Nebojte se zavést nové proměnné a objekty si označit písmenky. Řešení nepochopitelných kvůli neznačení se najde vždy mnoho, kdežto zavést tolik nového značení, že bude řešení kvůli tomu nepřehledné, téměř není možné (nebo alespoň ne neúmyslně. Nesnažte se mě prosím vyvést z omylu.)
• Pokud sami sebe nepovažujete za pokročilého v sepisování řešení, pište řešení na počítači. Vyhnete se tím řešení, které je plné škrtanců.
• Pokud je úkolen vymyslet algoritmus, nezapomeňte:
  • Dokázat, že je algoritmus korektní, není-li to zcela zřejmé.
  • Tvrdíte-li něco o jeho časové (či prostorové) složitosti toto tvrzení dokázat.
  • Tvrdíte-li, že je vámi nalezený algoritmus optimální, dokázat, že nemůže existovat rychlejší/prostorově úspornější.