PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Programování pro deskriptivní geometrii II - NMTD104
Anglický název: Computer programming for descriptive geometry II
Zajišťuje: Katedra didaktiky matematiky (32-KDM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2022
Semestr: letní
E-Kredity: 4
Rozsah, examinace: letní s.:2/2, 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í
Garant: doc. RNDr. Pavel Töpfer, CSc.
doc. RNDr. Antonín Slavík, Ph.D.
Vyučující: doc. RNDr. Pavel Töpfer, CSc.
Korekvizity : NMTD103
Neslučitelnost : NMIN112, NMUG104
Záměnnost : NMIN112, NMUG104
Je neslučitelnost pro: NMUG104, NMIN112
Je záměnnost pro: NMUG104
Anotace -
Základní kurz programování pro 1. ročník bakalářského studia. 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 NMTD103 Programování pro deskriptivní geometrii I, na který tento předmět přímo navazuje.
Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (18.05.2022)
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 cvičení,
  • vypracování zápočtového programu.

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. (22.11.2023)
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. (22.11.2023)
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 NMTD103 a NMTD104. 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. Ústní část sestává z diskuze nad písemnou částí a případně z odpovědí na otázky vycházející ze sylabu.

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

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (22.11.2023)
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 NMTD103 Programování pro deskriptivní geometrii I.

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