INF133S Programovací techniky

Obchodně podnikatelská fakulta v Karviné
léto 2009
Rozsah
2/1/0. 5 kr. Ukončení: zk.
Vyučující
Ing. Marek Spišák (přednášející)
Ing. Marek Spišák (cvičící)
Garance
Ing. Marek Spišák
Katedra informatiky a matematiky – Obchodně podnikatelská fakulta v Karviné
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
Cílem předmětu Programovací techniky je seznámení studentů s nejčastěji používanými algoritmy řazení a vyhledávání, s metodami reprezentace dat a s abstraktními typy dat. Rovněž je vysvětlena problematika repředmětivních algoritmů a vhodnost jejich použití.
Osnova
  • Struktura předmětu:
    Úvod do algoritmizace, jazyk zápisu algoritmů
    1. Typy dat a jejich reprezentace
    2. Strukturované typy dat
    3. Abstraktní datové typy - úvod
    4. Abstraktní datové typy, návrh a implementace operací
    5. Repředmětivní algoritmy
    6. Binární stromy - základní operace
    7. Vyvážené binární stromy, AVL stromy
    8. Hromada, B-Strom
    9. Řazení - pokročilé metody
    10. Kontrolní test
    11. Vyhledávání
    12. Prohledávání textů
    13. Metody návrhu programových projektů

    Obsah předmětu:
    1. Úvod do algoritmizace, jazyk zápisu algoritmů. Obecné zásady algoritmizace, definice jazyka pro zápis algoritmů na základě Pascalu, algoritmizace jednoduchých úloh
    2. Typy dat a jejich reprezentace. Standardní primitivní typy dat, běžné funkce pro práci s nimi, definice uživatelských funkcí
    3. Strukturované typy dat. Pole, záznam, množina a soubor - definice a operace
    4. Abstraktní datové typy - úvod. Pojem abstraktní datové typy (ADT), definice základních abstraktních datových typů
    5. Abstraktní datové typy, návrh a implementace operací
    6. Repředmětivní algoritmy. Princip repředměte, převod iteračních algoritmů na repředmětivní a naopak, kritéria vhodnosti použití repředměte, klasické repředmětivní algoritmy (Hanojské věže, 8 dam)
    7. Binární stromy - základní operace. Definice binárních stromů, operace rušení a přidávání, dvojcestné binární stromy
    8. Vyvážené binární stromy, AVL stromy. Vyvažování binárních stromů, rotace, operace přidávání a rušení ve vyvážených stromech, AVL stromy
    9. Hromada, B-Strom
    10. Řazení - základní algoritmy. Řazení polí, algoritmy řazení přímým výběrem, přímým vkládáním, přímou výměnou, analýza účinnosti algoritmů
    11. Řazení - pokročilé metody. Shell sort, quick sort, řazení haldou, metody řazení sekvenčních souborů
    12. Kontrolní test
    13. Vyhledávání. Vyhledávání v neseřazených strukturách, binární vyhledávání, optimalizované vyhledávací algoritmy
    14. Prohledávání textů. Metody prohledávání textů, analýza jejich složitosti
    15. Metody návrhu programových projektů. Dekompozice programových celků, programové prostředky pro koordinaci týmu

    Učebna PC.
Literatura
    povinná literatura
  • WIRTH, N. Algoritmy a štruktúry údajov. Bratislava, ALFA, 1990. ISBN 80-05-00153-3. info
  • HONZÍK, J. M. Programovací techniky. Brno, VUT, 1990. ISBN 80-214-0345-4. info
    doporučená literatura
  • WRÓBLEWSKI, P. Algoritmy Datové struktury a programovací techniky. COMPUTER PRESS, 2004. ISBN 80-251-0343-9. info
Informace učitele
Dosažení alespoň 60 bodů ze 100 možných:
kontrolní test v 10. týdnu: 0 - 50 b.
závěrečný test 0 - 50 b.
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích léto 1991, léto 1992, léto 1993, léto 1994, léto 1995, léto 1996, léto 1997, léto 1998, léto 1999, léto 2000, léto 2001, léto 2002, léto 2003, léto 2004, léto 2005, léto 2006, léto 2007, léto 2008, léto 2010.