OBSAH

Jedenáctá 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 rekurzivní algoritmy, pro které je dokazování indukcí "jako dělané".

Samostatné procvičení učiva - odpovědníky

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á nebo jak probíhá. Na to pak navážou i příklady s naznačenými induktivními důkazy rekurzivních programů. Jelikož tyto odpovědníky nejsou lehké a následující lekce předmětu už nemá své procvičení, klidně si část procvičení nechte na poslední týden výuky.

Při řešení mnohých z uvedených ú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.)

Doplňkové a externí materiály