Základy algoritmizace

Jaro 2011

Přednáška

Pondělí, 16:30, posluchárna B-103 (Břehová 7)

Cvičení

Termíny zkoušek


Literatura

Skriptum

Základní doporučenou literaturou je skriptum "Základy algoritmizace", 2. vydání. Oproti prvnímu vydání obsahuje řadu změn, algoritmů a odvození složitosti, které v prvním vydání nebyly, proto nedoporučuji první vydání používat.
Po dobu platnosti nakladatelské smlouvy pro druhé vydání také nebude k dispozici skriptum ve formátu PDF.
Opravy chyb, o nichž ve skriptu vím, najde zde. Pokud najdete další, pošlete mi prosím zprávu.

Výukový program

K přednášce existuje doprovodný program, který předvádí metody třídění a vyvažování binárního stromu (projekt jera).

Předpokládaný obsah přednášky:
Algoritmus -- datové struktury -- metody návrhu algoritmu -- rekurze -- třídění -- použití binárního stromu -- seminumerické algoritmy

15. 2. 2011
  • Přednáška: organizační záležitosti -- algoritmus, časová a paměťová náročnost, metoda shora dolů, popis algoritmu. Příklad: Složitost vyhledání největšího prvku v poli
  • Cvičení: Požadavky na program (příklad softwarové firmy)
    • 21. 2. 2011
  • Přednáška: Datové struktury: Základní datové struktury (proměnná, pole, záznam). Seznam, strom. Obecný strom, m-ární strom, binární vyhledávací strom, dokonalý strom.
  • Cvičení: Metoda shora dolů.
    • 28. 2. 2011
  • Přednáška: Strom -- dokončení. Halda. B-strom, zásobník. Algoritmus volání podprogramu (standardní rámec zásobníku).
  • Cvičení: Implementace stromu.
    • 7. 3. 2011
  • Přednáška:Další datové struktury: Fronta, dvoustranná fronta. Hešová tabulka. Reprezentace matematických struktur pomocí datových struktur (množina, graf). Metody návrhu algoritmů -- rozděl a panuj, hladový algoritmus.
  • Cvičení: Rekurze. Hanojské věže.
    • 14. 3. 2011
  • Přednáška: Metody návrhu algoritmů -- dokončení: Dynamické programování, backtracking, obecné metody prohledávání stavového stromu, metoda Monte Carlo.
  • Cvičení:Euklidův algoritmus. Nejkratší cesta v grafu a podobné úlohy.
    • 21. 3. 2011
  • Přednáška: Metody návrhu algoritmů.
  • Cvičení:Metody návrhu algoritmů (8 dam, nejkratší cesta koněm na šachovnici, případně s překážkami, úloha projít všechna pole šachovnice koněm a na žádné pole se nevrátit, průchod bludištěm, hádanka o vlkovi, koze a zelí apod. )
    • 28. 3. 2011
  • Přednáška:Metody návrhu algoritmů -- dokončení.
  • Cvičení: Metody návrhu algoritmů -- dokončení. Příklad odstraňování rekurze.
    • 4. 4. 2011. Metoda Monte Carlo. Rekurze.
  • Cvičení: Zpracování aritmetického výrazu.
    • 11. 4. 2011
  • Přednáška:Třídění (úvod, jednoduché metody třídění, tShellovo třídění, třídění stromem, třídění haldou, quicksort).
  • Cvičení:Třídění seznamu -- použitelnost různých metod.
    • 18. 4. 2011
  • Přednáška:Třídění -- dokončení (introsort). Hledání mediánu. Vnější třídění. Přihrádkové a lexikografické třídění. Abecední řazení.
  • Cvičení:Třídění seznamu -- použitelnost různých metod.
    • 2. 5. 2011
  • Přednáška:AVL strom. Analýza binárního vyhledávacího stromu.
  • Cvičení: Topologické třídění.

    •  

     

    K této přednášce si lze stáhnout příklady. Zdrojové texty (převážně v Pascalu) jsou zabaleny včetně adresářové struktury.

    Moje domovská stránka    Přednášky a semináře