INF133 Programovací techniky

Obchodně podnikatelská fakulta v Karviné
zima 2007
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 nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
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
Předmět je ukončen zkouškou, která se skládá z teoretické části (testu) a praktické části u počítače. Obsahem bude látka probíraná během celého semestru.
U testu se jedná o 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 zima 1990, zima 1991, zima 1992, zima 1993, zima 1994, zima 1995, zima 1996, zima 1997, zima 1998, zima 1999, zima 2000, zima 2001, zima 2002, zima 2003, zima 2004, zima 2005, zima 2006, léto 2008.