VSFS:B_Prg Programming - Course Information

B_Prg Programming

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