V části 6b cvičení se přejde na látku dokazování algoritmů.

Obecná náplň cvičení

Proč je třeba algoritmy dokazovat, jak si vůbec algoritmy zapisovat nějak nezávisle na programovacím jazyce a přitom dostatečně blízce programům a podobně...

• Je třeba procvičit symbolický formální zápis algoritmů z přednášky. Studenti musí umět běžné algoritmy rozepsat do elementárních kroků a přehledně procedurálně zapsat nezávisle na programovacím jazyce.
• Zkusí se pár krátkých příkladů, na kterých je vidět, proč je nutné i krátké a jednoduše vypadající algoritmy ověřovat a dokazovat.
• Mohou se podrobněji rozebrat ukázkové příklady důkazů algoritmů z přednášky, zmíní se také otázka, zda se vůbec algoritmus zastaví (problém s "while" cykly).

Možné ukázky chybných a správných algoritmů k procvičení:

• Vrcholové pokrytí je podmnožina X vrcholů grafu taková, že každá hrana má aspoň jeden vrchol v X. Zkusme hledat nejmenší vrcholové pokrytí v grafu následujícím hladovým algoritmem
  • Bereme vždy vrchol (či jeden z několika), který má největší stupeň v podgrafu dosud nepokrytých hran.

Kde je chyba? Najděte graf, na kterém tento postup selže (stačí už 7 vrcholů a 6 hran...). A jak lze vrcholové pokrytí vlastně řešit? Bohužel je to NP-úplný problém, avšak existují krásné algoritmy řešící otázku, zda graf má vrcholové pokrytí o <=k vrcholech pro konstatní (malé) k.

• ...