Jak sepsat řešení teoretické úlohy?

Co musí řešení obsahovat?

Řešení teoretické úlohy musí typicky obsahovat následující části (ne nutně odděleně).

Popis algoritmu

Dodejte nám přesný postup, kterým lze vyřešit zadání (tedy algoritmus). Nemusíte vše rozebírat do malých detailů (např. načtení vstupu do pole), důležité části však musí být řádně popsány. Popis musí být primárně ve větách, avšak můžete dodat i (pseudo)kód.

Důkaz správnosti

Je potřeba dokázat, že algoritmus skončí a že vrátí správný výsledek v každém případě.

Nejdůležitější kontrola, kterou můžete na svém důkazu provést, je, jestli váš důkaz přesvědčí vás, tedy, že jste si na jeho základě jisti, že algoritmus vždy dá správný výsledek.

Můžete využít důkazové techniky jako důkaz sporem nebo indukcí. Často také můžete dokázat, že se nějaká vlastnost v každém kroce programu sníží, anebo zůstane stejná, čímž se velmi dobře dokazuje, že algoritmus skončí.

Pokud použijete nějaký dobře známý algoritmus, není třeba dokazovat jeho správnost, za podmínky, že mu rozumíte.

Důkaz časové a prostorové složitosti

Pokud nevíte, co je složitost algoritmu, přečtěte si naši kuchařku o složitosti algoritmu.

Složitost můžete dokazovat již v průběhu popisování fungování vašeho algoritmu. Pokud například řeknete, že algoritmus projde a sečte všechna čísla na vstupu, můžete rovnou napsat, že toto má složitost O(N), kde N je počet čísel na vstupu (protože každé číslo projde jednou, popř. konstantně-krát).

Příklad řešení

Úloha: Maximum. Na vstupu máte N čísel. Na výstup vypište největší z nich.

Řešení: Budeme postupně procházet všechna čísla a ukládat si to aktuálně nejvyšší nalezené číslo, označme si jej X. Na samotném začátku bude nejvyšší nalezené číslo X rovno  − ∞. V momentě, kdy potkáme vyšší číslo, uložíme jej jako nové X.

Na konci bude v X skutečně nejvyšší číslo ze vstupu, protože kdyby tam nebylo (tedy existovalo by na vstupu číslo vyšší než X), znamenalo by to, že jsme nějaké číslo ze vstupu neprošli (tedy to, které je vyšší než X), což ale určitě není pravda.

Protože projdeme každé číslo právě jednou, je asymptotická časová složitost O(N). A protože nepotřebujeme čísla ze vstupu držet v paměti, bude prostorová složitost O(1).

Jak řešení odevzdávat?

Můžete odevzdat cokoli v pdf (včetně naskenovaného ručně psaného řešení) nebo v prostém textu. Jinak doporučujeme naučit se TeX (popř. LaTeX), což je jazyk určený na sazbu textu a matematiky.

Často kladené dotazy

Můžu použít nějaký známý algoritmus?

Ano, můžete, ale musíte mu rozumět. Nezapomeňte zmínit jeho složitost, ale nemusíte dokazovat jeho správnost. Pokud se jedná o nějaký relativně komplikovaný nebo méně známý algoritmus, měli byste také ideálně dodat i zdroj.

V jakých jazycích mohu odevzdávat řešení?

Preferujeme řešení v češtině, můžete však odevzdávat i řešení ve slovenštině nebo angličtině. Jiné jazyky pouze po předchozí domluvě.