PředmětyPředměty(verze: 867)
Předmět, akademický rok 2019/2020
  
Programování 2 - NMIN112
Anglický název: Programming 2
Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2019
Semestr: letní
E-Kredity: 8
Rozsah, examinace: letní s.:2/4 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.
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 : NMIN111
N//Je neslučitelnost pro: NMIN102
Z//Je záměnnost pro: NMIN102
Anotace -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (17.02.2020)
Základní kurz programování pro 1. ročník bakalářského studia matematických studijních programů. Obsahem kursu je programování v jazyce Python, metody návrhu algoritmů a tvorby programů. Předpokládají se vstupní znalosti v rozsahu předmětu NMIN111 Programování 1, na který tento předmět přímo navazuje.
Podmínky zakončení předmětu
Poslední úprava: doc. Mgr. Petr Kaplický, Ph.D. (30.05.2019)

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. (16.02.2020)
  • Pavel Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vyd. 2007, https://www.prometheus-eknihy.cz/
  • Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů, CZ.NIC Praha 2017, volně ke stažení na http://pruvodce.ucw.cz/
  • Programátorské kuchařky KSP, volně ke stažení na http://ksp.mff.cuni.cz/kucharky/
  • John V. Guttag, Introduction to Computation and Programming Using Python: With Application to Understanding Data, 2nd ed.,, MIT Press, Cambridge, MA 2016
  • Allen B. Downey, Think Python: How to Think Like a Computer Scientist, 2nd ed., O'Reilly Media, Sebastopol, CA 2015

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

Zkouška má povinnou písemnou a nepovinnou ústní část. Požadují se znalosti programovacího jazyka a algoritmů v rozsahu sylabů přednášek NMIN111 a NMIN112. Součástí písemné části zkoušky je vyřešení několika menších úloh, v nichž je úkolem návrh efektivního algoritmu, volba vhodných datových struktur, zapsání algoritmu ve tvaru funkce v Pythonu, odhad časových a paměťových nároků navrženého algoritmu.

K účasti na zkoušce není nutné předchozí získání zápočtu.

Sylabus
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (16.02.2020)
  • algoritmus, časová a paměťová složitost
  • dělitelnost čísel, Eukleidův algoritmus
  • test prvočíselnosti, Eratosthenovo síto
  • rozklad čísla na cifry
  • aritmetika s vyšší přesností („dlouhá čísla“)
  • Hornerovo schéma, poziční číselné soustavy
  • algoritmy vyhledávání v poli (sekvenční, binární, zarážka)
  • třídění čísel v poli - přímé metody, heapsort, mergesort, quicksort
  • složitost problému třídění
  • přihrádkové třídění
  • vnější třídění
  • reprezentace dat v paměti - alokace paměti, garbage collector
  • zásobník, fronta, slovník, halda
  • spojový seznam
  • rekurze – princip, příklady, efektivita
  • binární a obecný strom – reprezentace, průchod, použití
  • notace aritmetického výrazu – vyhodnocení, převody
  • binární vyhledávací strom, princip vyvažování
  • hešovací tabulka
  • reprezentace grafu
  • prohledávání grafu, základní grafové algoritmy
  • prohledávání stavového prostoru do hloubky a do šířky
  • metody zrychlení backtrackingu – ořezávání, heuristiky
  • programování her, algoritmus minimaxu
  • metoda Rozděl a panuj
  • dynamické programování

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

 
Univerzita Karlova | Informační systém UK