PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Programování 2 - NMIN102
Anglický název: Programming 2
Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2014 do 2018
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: doc. RNDr. Pavel Töpfer, CSc.
RNDr. Martin Pergel, Ph.D.
Třída: M Bc. FM
M Bc. FM > Povinné
M Bc. FM > 1. ročník
M Bc. MMIB
M Bc. MMIB > Povinné
M Bc. MMIB > 1. ročník
M Bc. MMIT
M Bc. MMIT > Povinné
M Bc. OM
M Bc. OM > Povinné
M Bc. OM > 1. ročník
Kategorizace předmětu: Informatika > Programování
Korekvizity : NMIN101
Neslučitelnost : NPRM045
Záměnnost : NPRM045
Je korekvizitou pro: NMIN201
Je neslučitelnost pro: NPRG030, NMIN161
Ve slož. prerekvizitě: NPRG041
Anotace -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (18.01.2018)
Přednáška pro 1. ročník bakalářského studia matematiky. Obsahem kursu je programování v jazyce Pascal, metody návrhu algoritmů a tvorby programů. Předpokládají se vstupní znalosti v rozsahu předmětu NMIN101 Programování 1, na který tento předmět přímo navazuje.
Podmínky zakončení předmětu
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (11.10.2017)

Předmět je zakončen zápočtem a zkouškou. K získání zápočtu se požaduje:

  • aktivní účast na cvičení spočívající obvykle v řešení úkolů (programů) v termínech stanovených cvičícím (ať už na cvičení nebo doma),
  • vypracování zápočtového programu a jeho odevzdání do termínu stanoveného cvičícím.

Povaha těchto požadavků neumožňuje vypsat opravné termíny. Vyučující stanoví podmínky, za nichž student může nahradit chybějící domácí úkoly nebo opakovaně odevzdat zápočtový program po odstranění nalezených závad.

Zkouška má písemnou a ústní část. Na složení zkoušky má student tři pokusy (jeden řádný a dva opravné termíny).

Literatura
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (30.09.2017)
  • P.Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vyd. 2007
  • N.Wirth: Algorithms + Data Structures = Programs , Prentice Hall Englewood Cliffsů; New Jersey 1975
  • slovenský překlad N. Wirth: Algoritmy a štruktúry údajov, Alfa, Bratislava 1989
  • I.Libicher, P.Töpfer: Od problému k algoritmu a programu, Grada Praha 1992

Požadavky ke zkoušce
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (13.10.2017)

Zkouška zahrnuje učivo z obou semestrů základního kursu programování, tzn. z předmětů NMIN101 a NMIN102. K účasti na zkoušce není nutné předchozí získání zápočtu. Zkouška má písemnou a ústní část.

V písemné části studenti řeší dvě úlohy. V první úloze technického charakteru je úkolem napsat jednoduchý program, proceduru nebo funkci v Pascalu, posuzuje se i syntaktická správnost zápisu. Úlohy jsou zaměřeny na zvládnutí práce s dynamickými datovými strukturami. Druhá úloha je rozsáhlejší, součástí jejího řešení je i přesnější formulace problému na základě obecného slovního zadání. Studenti nemusí programovat detailně celou úlohu, požaduje se návrh efektivního algoritmu, vhodné rozdělení úlohy na menší části, návrh jejich vzájemné komunikace, volba hlavních datových struktur, zapsání nejpodstatnějších částí algoritmu ve formě programu nebo stačí i vhodného pseudokódu a hrubý odhad časových a paměťových nároků výsledného programu.

V ústní části zkoušky se požadují znalosti programovacího jazyka a algoritmů v rozsahu sylabů přednášek NMIN101 a NMIN102. Součástí zkoušky je také rozbor úloh z písemné části zkoušky formou diskuse nad zvolenými řešeními. Předpokládá se schopnost zvážit přednosti a nedostatky různých alternativních způsobů řešení.

Sylabus -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (18.01.2018)
1. Programovací jazyk Pascal
  • modulární programování, unity
  • typ ukazatel, dynamicky alokované proměnné
  • objektové programování

2. Algoritmy a programování

  • halda, heapsort
  • rekurzivní třídění (quicksort, mergesort)
  • přihrádkové třídění (bucketsort, radixsort)
  • dolní odhad složitosti problému třídění
  • hledání k-tého nejmenšího prvku (quickselect)
  • vnější třídění
  • dynamicky alokované proměnné, dynamické datové struktury
  • lineární spojové seznamy a operace s nimi, druhy lineárních spojových seznamů
  • použití lineárních spojových seznamů - zásobník a fronta, dlouhá čísla, polynomy
  • stromy, grafy, průchody stromem a grafem
  • binární vyhledávací stromy, operace, vyvážené stromy
  • aritmetické notace, vyhodnocení aritmetického výrazu
  • dynamické programování
  • programová realizace základních grafových algoritmů (souvislost grafu, Dijkstrův algoritmus, minimální kostra, bipartitnost, topologické třídění)
  • základy objektového programování

Předpokládají se vstupní znalosti v rozsahu předmětu NMIN101 Programování 1.

 
Univerzita Karlova | Informační systém UK