B_UPg Úvod do programování

Vysoká škola finanční a správní
zima 2007
Rozsah
2/3. 14hodin/semestr. 6 kr. Doporučované ukončení: z. Jiná možná ukončení: zk.
Vyučující
prof. RNDr. Ondřej Čepek, 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_UPg/cAPH: Po 9:30–10:15 E303PC, Po 10:30–11:14 E303PC, Po 11:15–12:00 E303PC, P. Töpfer
B_UPg/pAPH: Po 8:00–8:44 E307, Po 8:45–9:29 E307, P. Töpfer
B_UPg/vA21PH: Pá 12. 10. 12:00–13:30 DELL ROOM E302PC, 13:45–15:15 DELL ROOM E302PC, Pá 26. 10. 15:30–17:00 DELL ROOM E302PC, So 27. 10. 9:45–11:15 DELL ROOM E302PC, Pá 9. 11. 12:00–13:30 DELL ROOM E302PC, 13:45–15:15 DELL ROOM E302PC, So 15. 12. 17:30–19:00 E303PC, O. Čepek
B_UPg/vA22PH: Pá 12. 10. 15:30–17:00 E303PC, 17:15–18:45 E303PC, Pá 26. 10. 17:15–18:45 E303PC, So 27. 10. 11:30–13:00 E303PC, Pá 9. 11. 15:30–17:00 E303PC, 17:15–18:45 E303PC, So 15. 12. 8:00–9:30 E303PC, O. Čepek
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 obě formy studia. Cíl kurzu: Základní kurz programování pro posluchače 1. ročníku bakalářského studia oboru Aplikovaná informatika. Obsahem kursu jsou základy algoritmizace, základní konstrukce programovacího jazyka Pascal, seznámení s vývojem a laděním programů v integrovaném vývojovém prostředí Free Pascal nebo Turbo Pascal a řešení jednoduchých algoritmických úloh.
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). 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í.
Literatura
  • 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
Metody hodnocení
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.
Navazující předměty
Předmět je zařazen také v obdobích léto 2008, zima 2008, léto 2009, zima 2009, léto 2010, zima 2010, léto 2011, zima 2011, léto 2012, zima 2012, zima 2013, zima 2014, zima 2015, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022, zima 2023, zima 2024.