B_UPg Introduction to Programming

University of Finance and Administration
Winter 2007
Extent and Intensity
2/3. 6 credit(s). Recommended Type of Completion: z (credit). Other types of completion: zk (examination).
Teacher(s)
prof. RNDr. Ondřej Čepek, Ph.D. (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_UPg/cAPH: Mon 9:30–10:15 E303PC, Mon 10:30–11:14 E303PC, Mon 11:15–12:00 E303PC, P. Töpfer
B_UPg/pAPH: Mon 8:00–8:44 E307, Mon 8:45–9:29 E307, P. Töpfer
B_UPg/vA21PH: Fri 12. 10. 12:00–13:30 DELL ROOM E302PC, 13:45–15:15 DELL ROOM E302PC, Fri 26. 10. 15:30–17:00 DELL ROOM E302PC, Sat 27. 10. 9:45–11:15 DELL ROOM E302PC, Fri 9. 11. 12:00–13:30 DELL ROOM E302PC, 13:45–15:15 DELL ROOM E302PC, Sat 15. 12. 17:30–19:00 E303PC, O. Čepek
B_UPg/vA22PH: Fri 12. 10. 15:30–17:00 E303PC, 17:15–18:45 E303PC, Fri 26. 10. 17:15–18:45 E303PC, Sat 27. 10. 11:30–13:00 E303PC, Fri 9. 11. 15:30–17:00 E303PC, 17:15–18:45 E303PC, Sat 15. 12. 8:00–9:30 E303PC, O. Čepek
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
Course objectives
Basic programming course for first year students of applied informatics. The course covers basics of algorithmization, basic constructs of the Pascal programming language, introduction to development and debugging of computer programmes in the Free Pascal or Turbo Pascal integrated environment, and solutions to simple algorithmic problems.
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). 1. Tvorba programu, postupy a nástroje, programovací jazyk, ladění. Algoritmus, důkaz správnosti, porovnávání kvality algoritmů. Časová a paměťová složitost algoritmů, asymptotická složitost, notace „velké O“. Složitost algoritmu v nejhorším, nejlepším a průměrném případě. Složitost problému. Příklady: - největší společný dělitel – Eukleidův algoritmus - vyhledávání sekvenční x půlení intervalů - třídění (přímý výběr x stromové třídění) - test prvočíselnosti - vyhodnocení polynomu – Hornerovo schéma - poziční číselné soustavy, převody (aplikace Hornerova schématu) - prohledávání do hloubky a do šířky 2. Programovací jazyk – syntaxe x sémantika, norma x implementace. Struktura programu v Pascalu (hlavička, deklarace, tělo). Proměnná, identifikátor, typ. Přehled datových typů. Číselné typy – rozsahy hodnot. Zápis programu – mezery, řádkování, komentáře. Dosazovací příkaz, read, write, inc, dec. První program – vyhodnocení výrazu. Definice konstant. Přehled příkazů v Pascalu. Dosazovací příkaz. Číselné výrazy – operátory, standardní funkce, celočíselné a reálné hodnoty ve výrazu. Vyhodnocování výrazu, priority operátorů. Kompatibilita při dosazování, konverzní funkce (trunc, round). Příklad: ciferný součet. Integrované vývojové prostředí – základní funkce. 3. Podmíněný příkaz, sémantika vnořených if. Složený příkaz begin – end. Cykly while, repeat. Jednoduché a složené podmínky, relace, logické spojky. Algoritmy: Eukleidův algoritmus, prvočíselný rozklad, test prvočíselnosti. Cyklus for, přerušení cyklu break. Inicializované proměnné. 4. Standardní procedury read, write, readln, writeln, formátování výstupu. Aritmetické přetečení, přepínač $Q, zaokrouhlovací chyby. Příkaz case. Typ Boolean, logické výrazy, použití. Příklad: test prvočíselnosti – verze s využitím proměnné boolean. 5. Pole – význam, definice type, indexování polí, konstantní meze, přepínač $R. Algoritmy: Hornerovo schéma, Eratosthenovo síto. Vyhledávání v poli - $B, break, zarážka Vyhledávání v uspořádaném poli – půlení intervalů. Třídění čísel v poli – přímý výběr, přímé zatřiďování, bublinkové třídění. Zásobník a fronta, realizace v poli. 6. Práce s dlouhými čísly v poli. Vícerozměrná pole – př. součin matic. Inicializované proměnné typu pole. Procedury a funkce – význam, lokalita, viditelnost identifikátorů. Předávání parametrů hodnotu a odkazem. Práce v integrovaném prostředí Borland Pascal, resp. FreePascal – ladění programů. 7. Příklad využití pole a tvorby programu – následující permutace. Pseudonáhodná čísla, generátor pseudonáhodných čísel. Příklady použití pseudonáhodných čísel - metoda Monte Carlo. 8. Znaky a znakové řetězce – char, string. Algoritmy: vstup čísla po znacích (Hornerovo schéma), vstup dlouhého čísla. Poziční číselné soustavy, převody (aplikace Hornerova schématu). Algoritmy: převody z/do binární a hexadecimální soustavy. Záznam – použití, příklady (reprezentace polynomu). Inicializované proměnné typu záznam, příkaz with. 9. Textové soubory – operace, použití, formátování výstupu, příklady. 10. Halda, operace na haldě, implementace haldy, heapsort. 11. Modulární programování, unity. Unit CRT. 12. Datové soubory, přímý přístup. Vnější třídění.
Literature
  • P.Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995
  • P.Töpfer: Základy programování v úlohách, Scientia Praha 1997
  • P.Töpfer, D.Töpferová: Programování - Sbírka úloh, Fortuna Praha 1998
  • P.Satrapa: Pascal pro zelenáče, Neokortex Praha 2000
Assessment methods (in Czech)
Předmět je zakončen zápočtem. K získání zápočtu se požaduje vypracování zadaných domácích úkolů: - je třeba pokusit se o samostatné vyřešení všech deseti zadaných domácích úkolů a odevzdat jejich řešení vždy ve stanoveném termínu (jeden úkol týdně) - dále je třeba správně a včas vyřešit alespoň polovinu z těchto úkolů zadávaných na cvičeních v průběhu semestru. Účast na výuce není povinně vyžadována, bude ale pravidelně sledována jako pomocné kritérium. Zápočty se udělují na posledním cvičení v semestru.
Language of instruction
Czech
Follow-Up Courses
Further comments (probably available only in Czech)
Information on the extent and intensity of the course: 14hodin/semestr.
The course is also listed under the following terms Summer 2008, Winter 2008, Summer 2009, Winter 2009, Summer 2010, Winter 2010, Summer 2011, Winter 2011, summer 2012, Winter 2012, Winter 2013, Winter 2014, Winter 2015, Winter 2016, Winter 2017, Winter 2018, Winter 2019, Winter 2020, Winter 2021, Winter 2022, Winter 2023, Winter 2024.
  • Enrolment Statistics (Winter 2007, recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/winter2007/B_UPg