B_Prg Programování

Vysoká škola finanční a správní
léto 2009
Rozsah
2/2. 14hodin/semestr. 6 kr. Ukončení: zk.
Vyučující
doc. RNDr. Jan Lánský, Ph.D. (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 10:30–11:14 E303PC, Po 11:15–12:00 E303PC, P. Töpfer
B_Prg/pAPH: Po 8:45–9:29 E303PC, Po 9:30–10:15 E303PC, P. Töpfer
B_Prg/vA21PH: Pá 13. 2. 12:00–13:30 DELL ROOM E302PC, Pá 27. 2. 12:00–13:30 DELL ROOM E302PC, 13:45–15:15 DELL ROOM E302PC, Pá 13. 3. 12:00–13:30 DELL ROOM E302PC, 13:45–15:15 DELL ROOM E302PC, Pá 27. 3. 15:30–17:00 DELL ROOM E302PC, 17:15–18:45 DELL ROOM E302PC, J. Lánský
B_Prg/vA22PH: Pá 13. 2. 13:45–15:15 DELL ROOM E302PC, Pá 27. 2. 15:30–17:00 DELL ROOM E302PC, 17:15–18:45 DELL ROOM E302PC, Pá 13. 3. 15:30–17:00 DELL ROOM E302PC, 17:15–18:45 DELL ROOM E302PC, Pá 24. 4. 15:30–17:00 DELL ROOM E302PC, 17:15–18:45 DELL ROOM E302PC, J. Lánský
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.
Pokračování základního kurzu programování ze zimního semestru pro posluchače 1. ročníku bakalářského studia oboru Aplikovaná informatika. Cílem předmětu je doplnit znalosti složitějších prostředků programovacího jazyka (rekurze, dynamicky alokované proměnné), rozšířit znalosti algoritmů a programovacích technik (efektivita algoritmů, třídicí algoritmy, grafové algoritmy, dynamické datové struktury) a prohloubit praktickou zručnost při návrhu a tvorbě programů.
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. Halda, operace na haldě, implementace haldy, heapsort.
  • 2. Modulární programování, unity. Unit CRT.
  • 3. Rekurze - princip, příklady, backtracking.
  • 4. Metoda rozděl a panuj - princip, příklady. Algoritmus quicksort.
  • 5. Prohledávání do hloubky a do šířky. Zrychlení backtrackingu - ořezávání, heuristiky.
  • 6. Dynamicky alokované proměnné. Dynamické datové struktury.
  • 7. Lineární spojové seznamy - operace, druhy seznamů, příklady použití.
  • 8. Binární stromy - reprezentace, průchod. Notace aritmetických výrazů, vyhodnocování, převody.
  • 9. Vyhledávací stromy. Vyvážené stromy. Obecné stromy.
  • 10. Metody ukládání a vyhledávání dat - přehled. Hešování. Třídění - algoritmy, složitost. K-tý nejmenší prvek.
  • 11. Grafy - základní pojmy, reprezentace. Implementace grafových algoritmů.
  • 12. Ukázky řešení úloh.
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. Pravidelná účast na výuce - je nutná minimálně 50% účast na přednáškách a cvičeních.
2. Vypracování dvou zápočtových programů - posluchač musí samostatně vypracovat a 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.
3. Úspěšné absolvování praktického zápočtového testu u počítače - je třeba naprogramovat a odladit jednu úlohu 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ý dva pokusy (na posledních dvou cvičeních).
Zápočty se udělují na posledním cvičení v semestru.
Zkouška má písemnou a ústní část. V písemné části je úkolem napsat proceduru nebo funkci na práci s lineárními spojovými seznamy. 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/
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.
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 2007, léto 2008, zima 2008, 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.