ZALG - Základy algoritmizace

Mnou zpáchané podklady pro cvičení. Všechny programy jsou napsané pro Free Pascal. Stránky předmětu jsou u přednášejícího Ing. Miroslava Viriuse, CSc.

Zdrojové kódy pro příklady ze cvičení

• Binání vyhledávací strom - object_tree.pas
• Hanojské věže - hanoj.pas
• Řešení problému osmi dam - damy.pas
• K demonstraci vyhledávání nejkratší cesty v grafu použijeme úlohu ze 47. ročníku matematické olympiády - tunely.
• Vyhodnocení aritmetického výrazu pomocí rozděl a panuj (vyraz.pas). Implemetnace sybolického derivátoru (deriv.tgz) v C++ pomocí stromu a rekurzivního sestupu v něm.

Semestrální práce
Semestrální práce by měla při odevzdání obsahovat:

• zdrojový kód funkčního programu (měl by fungovat na jakákoli smysluplná data)
• připravená vstupní testovací data
• stručno a strozumitelnou dokumentaci (popis implementace)

Při odevzdávání očekávám, že svůj program předvedete na testovacích datech a také ukážete, že se orientujete v odevzdáveném programu.

Dokumentace

S dokumentací to nepřehánějte. Pokud bude obsahovat vše potřebné, tak platí - čím kratší, tím lepší. Dokumentace by měla sloužit k tomu, aby se v programu rychle zorientoval někdo cizí. Není tedy smyslem psát "tahle funkce dělá to a to", protože to je vidět přímo z kódu.

Určitě by měla obsahovat:

• stručný popis použitých datových struktur
• jaký problém úloha představuje (typicky půjde o nějaký grafový) a jaký algoritmus program používá pro jeho řešení (stačí název, pokud jde o standardní algoritmus)
• asymptotická časová složitost algoritmu
• popis významu základních procedur (dvou až tří), jen pro orientaci

Dokumentace stačí v elektronické podobě, preferovaný formát je čistý text bez formátování, v případě potřeby složitějších zápisů LaTeX, PostScript, PDF.

Zadání

Jako semestrální práce je akceptovatelná implementace konkrétního algoritmu probíraného v rámci předmětu. Algoritmus by pokud možno neměl být úplně triviální.

Příkladem zadání mohou být některé problémy ze soutěže v programování, které obsahují grafový problém (hledání nejkratší cesty, kostry, atd. atd.). Výběr najdete v ACMTasks.txt. Další příklady ze soutěže (musíte mezi nimi najít ty grafové) naleznete v archívech, např. v Zurichu, ve Valladolidu nebo i u nás v Praze (některé dokonce v češtině).

Samozřejmě není nutné, aby semestrální práce měla formu zadání ze soutěže, jde o procvičení algoritmu a jeho implementace.