PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
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 2022
Semestr: letní
E-Kredity: 8
Rozsah, examinace: letní s.:2/4, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
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
Neslučitelnost : NMTD104, NPRG062
Je neslučitelnost pro: NMIN102, NMTD104, NPRG062
Je záměnnost pro: NMTD104, NMIN102
Ve slož. prerekvizitě: NPRG041, NPRG041, NPRX041
Anotace -
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.
Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (17.02.2020)
Podmínky zakončení předmětu

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

  • aktivní práce na cvičeních,
  • získání alespoň 70% bodů za domácí úkoly zadávané průběžně na teoretickém cvičení,
  • získání alespoň 70% bodů za domácí úkoly zadávané průběžně na praktickém cvičení,
  • úspěšné absolvování závěrečného praktického testu z programování,
  • vypracování zápočtového programu včetně písemné dokumentace.

Povaha těchto požadavků neumožňuje vypsat opravné termíny.

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).

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.01.2024)
Literatura
  • 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

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

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.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (02.05.2020)
Sylabus -
  • 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.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (16.02.2020)
 
Univerzita Karlova | Informační systém UK