Materiály a odkazy pro studenty předmětu Algoritmické a numerické metody

(obor IŘT - kombinované studium)

Témata přednášek a blokového cvičení

1. LOGIKA

   Výroková logika - výroková formule, ohodnocení formule, tautologie, kontradikce, ekvivalence formulí, převod formule do konjunktivního a (úplného) disjunktivního tvaru, Quin-McCluskeyho metoda nalezení minimálního vyjádření formule v disjunktivním tvaru. Formule v predikátové logice, negace složitějších formulí.

   Stáhnout si můžete moji prezentaci k výrokové logice, základní pojmy výrokové a predikátové logiky, příklady s výsledky k této části přednášky, moji prezentaci s řešenými příklady Quin-McCluskeyho metodou, popis Quin-McCluskeyho metody a seznam ekvivalencí používaných k převodu formule do disjunktivního tvaru.

2. KONEČNÉ AUTOMATY

   Základní pojmy z teorie konečných automatů, příklady konečných automatů, konstrukce konečných automatů pro doplněk, průnik a sjednocení jazyků, algoritmus na minimalizaci konečného automatu. Příklady neregulárních jazyků.

   K tématu konečné automaty jsem připravil prezentaci, skripta a příklady, které doporučuji, abyste si vyřešili.

   Definice Turingova stroje a jednoduché příklady. Definice pojmu algoritmus s použitím pojmu Turingův stroj. Doporučuji wikipedii.

3. ÚVOD DO TEORIE GRAFŮ, GRAFOVÉ ALGORITMY, TOKY V SÍTÍCH

   Úvod do teorie grafů, základní pojmy, Dijkstrův algorimus na hledání nejkratších cest z daného vrcholu, Eulerovské grafy, algoritmus pro nalezení (uzavřeného či otevřeného) Eulerovského tahu, ohodnocené grafy algorimy pro nalezení minimální kostry. Sítě, algoritmus pro nalezení maximálního toku sítí.

   Vše potřebné (dokonce víc než to) naleznete v těchto skriptech nebo zkuste Wikipedii heslo Teorie grafů či Grafové algoritmy. Dále nabízím svoji prezentaci k tématu a doporučuji prezentace s algoritmy pro nalezení minimální kostry, Dijkstrovým algoritmem a algoritmem na hledání maximálního toku sítí. Ty nejsou vhodné k tisku.

4. NUMERICKÉ ŘEŠENÍ ROVNIC

   Separace kořenů, metoda půlení intervalu, metoda regula falsi (sečen), metoda tečen (Newtonova metoda).

   Moje prezentace k tématu včetně jednoduchých příkladů, podrobnější informace naleznete například v zde.

5. NUMERICKÝ VÝPOČET INTEGRÁLU

   Obdélníková, lichoběžníková a Simpsonova metoda.

   Nabizím svoji přednáškovou prezentaci k tématu. případně se podívejte na tyto stránky.

Témata k nastudování

1. JAZYK C A REKURZE

   Základy jazyka C. Například z knížky "Učebnice jazyka C" od Pavla Herouta, nakladatelství Kopp, nebo z internetu, například tady, a to pouze:
   • Použití proměnných typu int, float a char.
   • Základní aritmetické operace.
   • Vstup a výstup pomocí příkazů scanf a printf.
   • Větvení programu pomocí příkazu if.
   • Cykly while a for.
   • Práce s jednorozměrnými a dvourozměrnými poli.
   • Procedury a funkce především k použití v rekurzivních programech.
   Doporučuji stáhnout kompilátor jazyka C DevC++. Je zdarma. Na procvičení zkuste třeba tyto příklady. Dále nabízím svoji prezentaci na téma rekurze.

2. TŘÍDÍCÍ ALGORITMY

   Třídící algoritmy včetně jejich složitosti: insert sort, select sort, bubble sort, heapsort, quicksort. Zápis těchto algoritmů v jazyce C. Viz. například Wikipedia heslo Řadící algoritmus. Funkční kód naleznete v tomto zdrojáku.