B_Prg Programování

Vysoká škola finanční a správní
léto 2008
Rozsah
2/3. 14hodin/semestr. 6 kr. Ukončení: zk.
Vyučující
Mgr. Alan Eckhardt (cvičící)
doc. RNDr. Pavel Töpfer, CSc. (cvičící)
Garance
prof. RNDr. Ondřej Čepek, Ph.D.
Katedra informatiky a matematiky (FES, KIM) – Katedry – Vysoká škola finanční a správní
Kontaktní osoba: Lenka Bažantová
Rozvrh seminárních/paralelních skupin
B_Prg/cAPH: Po 9:30–10:15 E303PC, Po 10:30–11:14 E303PC, Po 11:15–12:00 E303PC, P. Töpfer
B_Prg/pAPH: Po 8:00–8:44 E307, Po 8:45–9:29 E307, P. Töpfer
B_Prg/vA21PH: Pá 22. 2. 13:45–15:15 E303PC, Pá 7. 3. 12:00–13:30 E303PC, Pá 28. 3. 13:45–15:15 E303PC, Pá 11. 4. 12:00–13:30 E303PC, 13:45–15:15 E303PC, Pá 25. 4. 15:30–17:00 E303PC, 17:15–18:45 E303PC, A. Eckhardt
B_Prg/vA22PH: Pá 22. 2. 12:00–13:30 E303PC, Pá 7. 3. 13:45–15:15 E303PC, Pá 28. 3. 12:00–13:30 E303PC, Pá 11. 4. 15:30–17:00 E303PC, 17:15–18:45 E303PC, Pá 25. 4. 12:00–13:30 E303PC, 13:45–15:15 E303PC, A. Eckhardt
Předpoklady
Výuka bezprostředně navazuje na předmět Úvod do programování ze zimního semestru. Předpokládá se znalost učiva z předmětu Úvod do programování a praktická zručnost při ladění jednoduchých programů v Pascalu na počítači.
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
Anotace je stejná pro všechny formy studia. Cílem kursu je doplnit znalosti složitějších prostředků programovacího jazyka (rekurze, dynamicky alokované proměnné, objekty), rozšířit znalosti algoritmů a programovacích technik a prohloubit praktickou zručnost při návrhu a tvorbě programů. Obsah učiva: Efektivita algoritmů - asymptotická složitost, nejlepší, průměrný a nejhorší případ, konkrétní odhady složitosti jednoduchých algoritmů. Rekurze - přímá a nepřímá rekurze, výhody a nevýhody použití rekurze, rekurzivní formulace algoritmů, efektivita rekurzivních programů a její zvyšování, odstranění rekurze použitím zásobníku. Prohledávání do hloubky a do šířky - backtracking, algoritmus vlny, ořezávání, heuristiky. Metoda rozděl a panuj - princip metody, příklady použití. Třídění dat - třídění přímým výběrem, přímé zatřiďování, bublinkové třídění, quicksort, mergesort, heapsort, přihrádkové třídění, vnější třídění. Hledání k-tého nejmenšího prvku - modifikace quicksortu, pomocí haldy. Staticky a dynamicky alokované proměnné - typ ukazatel, způsoby alokace a uvolňování dynamicky alokovaných proměnných. Lineární spojové seznamy - různé typy seznamů (obousměrné, s hlavou, cyklické), základní operace se seznamy, implementace zásobníku a fronty, práce s dlouhými čísly a polynomy. Stromy - binární stromy, obecné stromy a jejich různé reprezentace, binární vyhledávací stromy a operace s nimi, průchody binárním stromem a jejich souvislost s algebraickými notacemi, prakticky užívané definice vyvážených stromů. Hašování - hašovací tabulka, hašovací funkce, kolize a metody jejich řešení; srovnání různých metod ukládání a vyhledávání dat z hlediska efektivity. Aritmetické výrazy - algoritmy na vyhodnocení výrazu zapsaného v různých notacích (infix, prefix, postfix), převody mezi různými algebraickými notacemi. Grafy - základní grafové pojmy, způsoby reprezentace grafu v programu, programová realizace vybraných grafových algoritmů. Objekty, základní principy objektového programování.
Osnova
  • Tato osnova je určena pro prezenční studium, průběh výuky pro kombinované studium je uveden ve studijních materiálech formou metodického listu (ML). Obsah přednášek: 1. Rekurze, backtracking. 2. Prohledávání do hloubky a do šířky. Složitost algoritmů. 3. Metoda rozděl a panuj. 4. Třídění - algoritmy, složitost. K-tý nejmenší prvek. 5. Dynamicky alokované proměnné. Dynamické datové struktury. 6. Lineární spojové seznamy. 7. Binární stromy. Notace aritmetických výrazů. 8. Vyhledávací stromy. Vyvážené stromy. 9. Obecné stromy. Metody ukládání a vyhledávání dat. Hešování. 10. Grafy - základní pojmy, reprezentace. 11. Implementace základních grafových algoritmů. 12. Objekty a objektové programování.
Literatura
  • P.Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995
  • P.Töpfer, D.Töpferová: Programování - Sbírka úloh, Fortuna 1998
  • P.Satrapa: Pascal pro zelenáče, Neocortex Praha 2001
Metody hodnocení
Výuka předmětu je zakončena zápočtem a zkouškou. K získání zápočtu se požaduje: 1. Vypracování dvou zápočtových programů: samostatně vypracovat a včas ve stanoveném termínu odevzdat dva větší domácí úkoly. Na vypracování každého z nich bude vymezen čas 4-5 týdnů v průběhu semestru. Odevzdává se zdrojový text odladěného programu a dokumentace k programu. 2. Úspěšné absolvování praktického zápočtového testu u počítače: jedna úloha podobného rozsahu a náročnosti, jakou měly domácí úkoly z předmětu Úvod do programování v zimním semestru. Na splnění zápočtového testu má každý tři pokusy, podmínky testu je nutné splnit do ukončení výuky v letním semestru. 3. Účast na cvičeních není povinně vyžadována, bude však pravidelně sledována jako pomocné kritérium. Zkouška má písemnou a ústní část. V písemné části je úkolem napsat proceduru nebo funkci na práci s ukazateli a dynamickými datovými strukturami. U ústní části se požadují znalosti programovacího jazyka, algoritmů a programovacích technik v rozsahu přednášky (viz sylabus uvedený výše).
Informace učitele
http://ksvi.mff.cuni.cz/~topfer/vsfs/
Literatura Prezentace k přednáškám v PowerPointu a ukázkové programy z přednášek i ze cvičení jsou k dispozici na Internetu. Jsou doplňovány průběžně po každé přednášce. Doporučená studijní literatura: P.Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vydání 2007 (učebnice přímo určená pro tento základní kurz, pokrývá převážnou většinu učiva algoritmů, nevykládá syntaxi programovacího jazyka), P.Töpfer, D.Töpferová: Programování - Sbírka úloh, Fortuna 1998 (sbírka jednoduchých i těžších úloh na procvičování), P.Satrapa: Pascal pro zelenáče, Neocortex Praha 2001 (místo ní lze použít jinou učebnici Pascalu).
Předmět je zařazen také v obdobích zima 2007, zima 2008, léto 2009, léto 2010, zima 2010, léto 2011, zima 2011, léto 2012, zima 2012, léto 2013, léto 2014, léto 2015, léto 2016, léto 2017, léto 2018, léto 2019, léto 2020, léto 2021, léto 2022, léto 2023, léto 2024, léto 2025.