OBSAH

Desátá lekce se týká dokazování vlastností algoritmů. Nejprve si ukážeme, jak vůbec správně formalizovat zápis algoritmu (otázku, co to přesně je algoritmus, ponecháme stranou a zůstaneme na intuitivní úrovni pochopení). Algoritmus tak pro nás bude konečná posloupnost elementárních kroků, zjednodušená v zápise tzv. řídícími konstrukcemi. K zápisu elementárních kroků budeme používat symbolický zápis (určený pro tento předmět, přitom poměrně kompatibilní s běžnými zvyklostmi jinde) nebo i běžný jazyk; nejdůležitější bude správné strukturování zápisu.

V návaznosti na předchozí si pak ukážeme vlastnosti algoritmů na mnoha malých příkladech a uvedeme si problematiku matematického dokazování vlastností algoritmů. Zmíněny budou i rekurzivní algoritmy.

Odpovědník této lekce se zaměřuje na pochopení procedurálního zápisu jednoduchých algoritmů a na poznání, co daný algoritmus počítá. Na to pak navazují příklady týkající se rekurentních zápisů posloupností, což jsou vlastně jednoduchá matematická vyjádření rekurzivních programů.

Při řešení části z úloh byste si měli opět vzpomenout na matematickou indukci - právě ta vám pomůže si ověřit vaši odpověď, abyste se vyhnuli penalizaci za chyby (třebaže odpovědník stěží může přímo ověřit, zda si svou odpověď dokazujete nebo jen hádáte, záporné body za chyby to statisticky poměrně dobře odhalí).

Diskuse o látce

(Mějte na paměti, že dříve - v době uvedených diskusí - byla látka této lekce jinde, trochu už na začátku a převážně pak v Lekci 8. Některé z diskusí jsou relevantní také pro následující Lekci 11.)

Doplňkové a externí materiály