VSFS:B_Prg Programming - Course Information
B_Prg Programming
University of Finance and AdministrationSummer 2008
- Extent and Intensity
- 2/3. 6 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- Mgr. Alan Eckhardt (seminar tutor)
doc. RNDr. Pavel Töpfer, CSc. (seminar tutor) - Guaranteed by
- prof. RNDr. Ondřej Čepek, Ph.D.
Department of Computer Science and Mathematics – Departments – University of Finance and Administration
Contact Person: Lenka Bažantová - Timetable of Seminar Groups
- B_Prg/cAPH: Mon 9:30–10:15 E303PC, Mon 10:30–11:14 E303PC, Mon 11:15–12:00 E303PC, P. Töpfer
B_Prg/pAPH: Mon 8:00–8:44 E307, Mon 8:45–9:29 E307, P. Töpfer
B_Prg/vA21PH: Fri 22. 2. 13:45–15:15 E303PC, Fri 7. 3. 12:00–13:30 E303PC, Fri 28. 3. 13:45–15:15 E303PC, Fri 11. 4. 12:00–13:30 E303PC, 13:45–15:15 E303PC, Fri 25. 4. 15:30–17:00 E303PC, 17:15–18:45 E303PC, A. Eckhardt
B_Prg/vA22PH: Fri 22. 2. 12:00–13:30 E303PC, Fri 7. 3. 13:45–15:15 E303PC, Fri 28. 3. 12:00–13:30 E303PC, Fri 11. 4. 15:30–17:00 E303PC, 17:15–18:45 E303PC, Fri 25. 4. 12:00–13:30 E303PC, 13:45–15:15 E303PC, A. Eckhardt - Prerequisites (in Czech)
- 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.
- Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Applied Informatics (programme VSFS, B-INF) (2)
- Course objectives (in Czech)
- 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í.
- Syllabus (in Czech)
- 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í.
- Literature
- 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
- Assessment methods (in Czech)
- 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).
- Language of instruction
- Czech
- Further comments (probably available only in Czech)
- Information on the extent and intensity of the course: 14hodin/semestr.
- Teacher's information
- http://ksvi.mff.cuni.cz/~topfer/vsfs/
- Enrolment Statistics (Summer 2008, recent)
- Permalink: https://is.vsfs.cz/course/vsfs/summer2008/B_Prg