IV022 Návrh a verifikace algoritmů
Rozvrh
Osnova
- Programy jako transformátory predikátů. Nejslabší vstupní podmínka (wp), vlastnosti transformátorů, správnost algoritmu.
- Programovací jazyk GCL. Syntaxe, definice sémantiky pomocí transformátorů predikátů, SKIP, ABORT, vícenásobné přiřazení, sekvence, alternativa, cyklus.
- Programátorská logika. Zákon sekvence, zákon alternativy, zákon cyklu, vektorové proměnné.
- Návrh algoritmů. Principy a strategie pro návrh založené na programátorské logice, zákon současného návrhu a verifikace.
- Příklady aplikace metodologie na návrh konkrétních algoritmů. Návrh efektivních algoritmů, vyhledávání a třídění.
Požadavky na absolvování předmětu
Předmět je zakončen písemnou zkouškou. Použití literatury a poznámek není při písemce povoleno. Znalosti a dovednosti, které je potřeba zvládnout, jsou uvedeny v katalogu předmětů. Za písemku je možné získat 20 bodů, k absolvování předmětu zkouškou stačí zpravidla polovina. Každá písemka je ovšem jinak obtížná, proto nelze uvést generickou hodnotu. U každé písemky je vždy uveden konkrétní počet bodů pro jednotlivá hodnocení.Doporučená literatura
- starší text k přednášce (dostupný pouze z domény .muni.cz)
- Dijkstra, Edsger W. - Feijen, W. H. J. A method of programming. Wokingham : Addison-Wesley Publishing Company, 1998.
- Kaldewaij, A. (Anne). Programming : the derivation of algorithms. New York : Prentice Hall, 1990.
- Gries, David. The Science of Programming . New York : Springer-Verlag, 1981.