Výuka

V letním semestru 2022/23 vyučuji tyto předměty:


Programování 2 pro matematiky (NMIN112)

Podmínky pro získání zápočtu:

Zápočet není vstupní podmínkou ke zkoušce.

Úlohy v ReCodExu

Pro získání zápočtu je potřeba mít na konci semestru alespoň 70% z celkového počtu vypsaných bodů za praktické úlohy (bonusové úlohy se do celkového počtu nepočítají, můžete si jimi tedy přilepšit).

Autor řešení musí být schopen na cvičení vysvětlit svůj program.

Úkoly se budou odevzdávat pomocí systému ReCodEx https://recodex.mff.cuni.cz/

Všechny úlohy jsou samostatná práce! Můžete se samozřejmě o úlohách bavit mezi sebou, ale řešení musí vypracovat každý sám.

Písemné (teoretické) úlohy

Pro získání zápočtu je potřeba mít na konci semestru alespoň 70% z celkového počtu vypsaných bodů za teoretické úlohy (bonusové úlohy se do celkového počtu nepočítají).

Domácí úkoly psané "na papír" spočívají většinou v návrhu a slovním popisu efektivního algoritmu.

Úkoly se budou odevzdávat pomocí systému Postal Owl https://kam.mff.cuni.cz/owl/

Praktický zápočtový test u počítačů

Bude se jednat o úlohu zadanou v ReCodExu v podobném rozsahu jako úlohy zadávané v průběhu semestru. Pro úspěšné složení testu bude potřeba získat v ReCodExu plný počet bodů. Hodnotí se nejen funkčnost vytvořeného programu, ale i to, jak je program navržen a naprogramován. Není při tom vyžadována (časová) optimalizace algoritmu. Stačí, nejsou-li ani algorimus ani jeho implementace "vysloveně hloupé". Vzhledem k omezenému času se nepožaduje, aby byl program komentován (i když komentáře vytvářené současně s programemem vám mohou práci na programu podstatně zjednodušit i zrychlit).

Student musí být schopen vysvětlit svůj program.

Zápočtový program

Zápočtový program je rozsáhlejší než běžné úlohy v ReCodExu. Jeho účelem je, abyste si vyzkoušeli samostatně navrhnout a vytvořit větší program včetně načítání vstupů od uživatele, ošetření jejich korektnosti, odladění, napsání dokumentace. Téma pro svůj program si vybíráte sami (já ho musím schválit).

Postup, jak vypracovat zápočtový program:

  • vybrat si téma a domluvit se na něm se mnou (do 31. března)
  • poslat krátkou specifikaci (do 14. dubna)
  • napsat samotný program
  • napsat dokumentaci k programu - uživatelskou a programátorskou
  • poslat mi program, dokumentaci a testovací data a domluvit si termín předvedení
  • předvést mi program, ukázat jeho funkce na testovacích datech, popsat jak program pracuje, jaké algoritmy a datové struktury používá. Během předvedení byste měli být schopní program na požádání mírně upravit. (nejlépe do konce zkouškového období, nejpozději do poloviny září)

    Je možné, že s první verzí vašeho programu / dokumentace / testovacích dat / předvedení nebudu spokojená a budete je muset předělat. Proto nenechávejte předvedení až na poslední chvíli, abyste případné úpravy stihli ještě v termínu.

Při výběru témat pro své programy se můžete inspirovat např. na stránkách Martina Mareše: text o zápočtových programech a výběr z témat nebo zde: více témat

O dokumentaci podle Martina Mareše:

Uživatelská dokumentace. To je stručný popis toho, jak se program používá (tedy třeba v jakém formátu se mu zadává vstup a v jakém vydá výstup). Nepište od ní evidentní věci, spíš to, co by bězný uživatel nečekal. Také by tam mělo být řečeno, co vlastně program dělá :)

Programátorská dokumentace. V ní je stručně popsáno, jak program funguje uvnitř. Nemusíte komentovat každý řádek programu, spíš popište celkovou koncepci. Pokud používáte nějaké netriviální algoritmy, je to dobré zmínit. Pokud používáte něco, co jste nevymysleli sami, je na místě citovat zdroje.

Text o dokumentaci k (nejen) zápočtovému programu od doktora Kryla: Jak psát dokumentaci zápočtového programu

Co jsme dělali na cvičení:

1. CVIČENÍ - praktické:

  • podmínky zápočtu
  • hraní si s želvičkami

Látka ze zimního semestru (předmět NMIN111 Programování 1):

  • instalace Pythonu, IDLE, Python jako kalkulačka
  • proměnné a výrazy, operace s čísly, relace a logické spojky
  • programy – příkazy input a print, indentace, komentáře, ladění programu
  • příkazy if (zanořování, elif) a while, ciferný součet, Euklidův algoritmus, test prvočíselnosti
  • zpracování posloupnosti dat, seznamy a operace s nimi, indexování, řezy
  • formátovaný výstup
  • funkce - parametry, return, lokalita proměnných
  • znakové řetězce, N-tice (tuples)
  • generátorová notace seznamů (list comprehension)
  • množiny a slovníky
  • základní informace o třídách a objektech v Pythonu (jen princip, ne syntaxe, bez procvičení)
  • textové soubory
  • výjimky - try-except, raise, assert
  • standardní knihovna (math, copy, array, fractions, random, ...).

2. CVIČENÍ - teoretické:

Složitost

  • Zopakování definice asymptotické složitosti
  • Procvičování pojmu velké O - dokažte následující tvrzení dokažte

Vážení kuliček

  • vážení kuliček (dvouramenná váha - kuličky (3,4,9,12,13?) - jedna trochu jiná)
    • víme, jestli jiná je lehčí nebo těžší
    • víme jenom, že je jiná, a nezajímá nás, jestli lehčí nebo těžší
    • víme jenom, že je jiná, a zajímá nás, jestli lehčí nebo těžší
  • kolik (nejméně) vážení je potřeba k odhalení jiné kuličky?
  • jak přehledně zakreslit možnosti?
  • kroky k zobecnění: Kolik může maximálně být kuliček pro n vážení? Jak by vypadal obecný algoritmus? - na promyšlení (bonusová úloha v Postal Owl)

3. CVIČENÍ - praktické:

Soubory: Knihovny:
  • standardní knihovna (math, copy, array, fractions, random, ...).

Funkce: Generování seznamů:

4. CVIČENÍ - teoretické:

Procvičování určování složitosti různých algoritmů. Řešili jsme např. následující úlohy:

Je zadaná posloupnost:

  • určete, zda obsahuje číslo 7
  • rozhodněte, zda je posloupnost monotónní a jak (konstantní, rostoucí, neklesající, klesající, nerostoucí)
  • najděte maximum / maximum a počet jeho výskytů
  • určete počet čísel bez opakování (v O(n2), O(n) + O(n) paměť, O(n*log n) ), to samé, ale víme, že bude omezený rozsah hodnot (a jak)
  • najděte číslo s maximálním počtem výskytů (omezený rozsah hodnot - v O(n) bez paměti navíc)
  • najděte souvislý úsek s maximalním součtem (v O(n3), O(n2), O(n) - viz Průvodce labyrimtem algoritmů, str. 23)

5. CVIČENÍ - praktické:

Objekty

  • používání objektů
  • vytváření vlastních tříd
  • assert

6. CVIČENÍ - teoretické:

opakování třídících algoritmů z přednášky

  • O(n2) - select sort, insert sort, bubble sort, shake sort
  • O(n*log(n)) - merge sort

7. CVIČENÍ - praktické:

  • knihovna numpy
  • Pokus o návod na instalaci:
    • (pokud používáte jiné prostředí než IDLE, nainstalujte numpy v něm)
    • spusťte příkaz pip install numpy.

      Pokud to nevyšlo, zkuste následující kroky:

    • přesuňte se do složky, kde máte python.exe, (typicky to bývá něco jako C:\Users\Jméno\AppData\Local\Programs\Python\Python37-32)
    • vlezte ještě do podsložky Scripts
    • spusťte příkazový řádek, např. napsáním příkazu cmddo řádky s cestou
    • spusťte příkaz pip install numpy
  • Slidy Martina Mareše: numpy - slidy

8. CVIČENÍ - teoretické:

  • nalezení prvku v setříděné posloupnosti - binární vyhledávání, pořádně a s pseudokódem
  • nalezení prvku v setříděné posloupnosti včetně počtu výskytů
  • určení složitosti operací s maticemi - např. transpozice matice, nalezení maximální hodnoty, největší (rozměry) kladná podmatice

9. CVIČENÍ - praktické:

9. CVIČENÍ - teoretické:

Procvičování látky z přednášky:

  • Halda - operace, heapsort
  • První pokusy se spojovými seznamy

10. CVIČENÍ - praktické:

Lineární spojové seznamy:

  • První pokusy se spojovými seznamy

MatPlotLib - knihovna na kreslení grafů

11. CVIČENÍ - teoretické:

Lineární spojové seznamy:

  • Jednoduché procvičování

Abstraktní datové typy fronta a zásobník

12. CVIČENÍ - praktické:

Procvičování spojových seznamů (obyčejných, necyklických, bezhlavých):

  1. vytvořte čtyři uzly s hodnotami 15, 10, 5, 25 a propojte je do spojového seznamu
  2. projděte vytvořený seznam a vypište hodnoty prvků
  3. projděte vytvořený seznam a změňte hodnotu 10 na hodnotu 100
  4. napište funkci vypis, která dostane jako parametr ukazatel na spojový seznam, a vypíše jeho prvky na jednu řádku, oddělené mezerami. Pokud je seznam prázdný, vypíše "PRAZDNY"
  5. napište funkci, která dostane jako parametr ukazatel na spojový seznam a vrátí součet hodnot prvků
  6. napište funkci, která přidá prvek na začátek seznamu
  7. napište funkci, která přidá prvek na konec seznamu
  8. napište funkci, která načte seznam ze vstupu (čísla oddělená mezerami) a vrátí ukazatel na první prvek

Knihovna TkInter

Pexeso šablona: pexeso_sablona.py

13. CVIČENÍ - teoretické:

Procvičování spojových seznamů s hlavou, cyklických, obousměrných, s dočasnou hlavou

14. CVIČENÍ - praktické:

Procvičování spojových seznamů s hlavou

  • napište funkci, která načte seznam ze vstupu (čísla oddělená mezerami) a vrátí ukazatel na hlavu seznamu
  • naprogramujte funkci, která seznam vypíše
  • naprogramujte funkci, která přidá prvek na začátek seznamu
  • naprogramujte funkci, která přidá prvek na konec seznamu
  • naprogramujte funkci, která zvětší hodnoty všech prvků o 10

Kostra kódu k úloze v ReCodExu: vzor_LSS.py

15. CVIČENÍ - teoretické:

Binární stromy

  • průchody binárním stromem - rekurzivně; pomocí zásobníku, fronty
  • úlohy:
    • určete počet uzlů ve stromě
    • určete počet listů ve stromě
    • určete hloubku stromu (délku nejdelší větve)
    • je strom symetrický podle svislé osy? (tvarem)

16. CVIČENÍ - praktické:

Procvičování binárních stomů

Jelínek

17. CVIČENÍ - teoretické:

Binární vyhledávací stromy

  • vyhledání hodnoty - rekurzivně, while cyklem
  • přidání hodnoty - rekurzivně, while cyklem
  • mazání uzlu - list, jeden následník, dva následnící
  • pojem dokonale vyváženého stromu
  • postavení dokonale vyváženého stromu

18. CVIČENÍ - praktické:

Procvičování rekurzivního generování

  • Napište rekurzivní funkci, která vytiskne pro zadané n "šipku z hvězdiček":
        *
        **
        ***
        ****
        ***
        **
        *
  • Napište rekurzivní funkci, která vypíše všechny možné řetězce délky n nebo kratší z nul a jedniček.
  • Napište rekurzivní funkci, která vypíše všechny možné řetězce délky n z nul, jedniček a dvojek.
  • Napište rekurzivní funkci, která vypíše všechny možné rostoucí posloupnosti délky n z nul, jedniček, dvojek a trojek. Např. pro n = 3:
        
        012
        013
        023
        123
  • Napište rekurzivní funkci, která vypíše všechny možné řetězce délky n z čísel od 0 do 9.

Želví fraktály

19. CVIČENÍ - teoretické:

Grafové algoritmy

  • reprezentace grafu
  • problémy řešitelné prohledáváním grafu do hloubky / do šířky - souvislost grafu, komponenty souvislosti, kostra, acykličnost grafu, bipartitnost, nejkratší cesta (do šířky)
  • topologické uspořádání
  • Dijkstrův algoritmus

20. CVIČENÍ - praktické:

Prezentace Triky s funkcemi

Příklady:

  • Je dán seznam řetězců tvaru "jméno příjmení":
    • Setřiďte je primárně podle příjmení, sekundárně podle jména.
    • Najděte osobu s nejdelším příjmením.
  • Napište generátor, který generuje třetí mocniny do zadaného n.
  • Napište nekonečný generátor sudých čísel.
  • Napište generátor, který dostane dva seznamy a bude generovat jejich kartézský součin. Můžete použít následující seznamy:
    a = ["sedma", "osma", "devítka", "desítka",
         "spodek", "svršek", "král", "eso"]
    b = ["srdce", "listy", "kule", "žaludy"]
  • *Napište generátor, který bude generovat "šipku z hvězdiček" z minulého cvičení.
  • *Napište generátor, který dostane seznam znaků a délku řetězce a bude generovat všechny možné řetězce.

Pokračování procvičování rekurzivního generování:

  • Napište rekurzivní funkci, která vypíše všechny možné rozklady čísla n na součet.
        5 = 1+1+1+1+1
        5 = 1+1+1+2
        5 = 1+1+3
        5 = 1+2+2
        5 = 1+4
        5 = 2+3
        5 = 5
  • Napište rekurzivní funkci, která vypíše všechny možné rozklady čísla n na součet délky k.
  • Napište rekurzivní funkci, která vypíše všechna správná uzávorkování jedním typem závorek, např. pro n=3:
     
        ()()()  
        (())()  
        ()(())  
        (()())  
        ((()))
  • Prohlédněte si funkce v následujícím souboru. Která z nich je efektivnější a proč? rekurze.py
  • Naprogramujte rekurzivní funkci, která spočítá, kolik je všech posloupností 0 a 1 délky n (můžete vyjít předchozího příkladu)
  • Naprogramujte rekurzivní funkci, která vygeneruje všechny posloupnosti 0 a 1 délky n, ve kterých je právě k jedniček
  • Naprogramujte rekurzivní funkci, která vygeneruje všechny posloupnosti 0 a 1 délky n, ve kterých nejsou jedničky za sebou
  • Naprogramujte rekurzivní funkci, která spočítá rozklad čísla na součet k sčítanců (minule bylo to samé, ale bez omezení počtu sčítanců)
  • Mezi zadané číslice doplňte znaménka +, - a * tak, aby výsledek byl roven zadanému číslu k.
    Např:
    "123", k=6: 
    výsledek: "1+2+3", "1*2*3"
    
    "125", k=7:
    výsledek: "1*2+5", "12-5"
    
  • (Microsoft Interview Question) Given a number n, print following pattern without using any loop.
    Input: n = 16
    Output: 16, 11, 6, 1, -4, 1, 6, 11, 16
    
    Input: n = 10
    Output: 10, 5, 0, 5, 10
    

21. CVIČENÍ - teoretické:

Prohledávání do šířky (fronta, nejkratší řešení) a do hloubky (zásobník, rekurze, backtracking):

  • ve čtvercové síti:
    • nejkratší cesta k pokladu (do šířky)
    • nejkratší cesta k pokladu, když můžeme jednou projít zdí
    • nejkratší cesta k pokladu, navíc je v bludišti klíč a zamčené dveře
  • prohledávání stavového prostoru
    • úloha na přelévání vody
    • přeplavení farmáře, kozy, čtyřlístku a vlka na druhý břeh řeky
    • proskákání šachovnice koněm
    • koncovka tic-tac-toe, minimax

22. CVIČENÍ - praktické:

Prohledávání do šířky ve čtvercové síti:

Podobným způsobem vyřešte následující úlohy:

  • Na všechna dostupná políčka napiště, v jaké vzdálenosti od počátečního políčka se nacházejí
  • Najděte nejkratší cestu k pokladu a označte ji hvězdičkami ("*")

Další úlohy:

  • Spočítejte, kolik je v bludišti místností (souvislých oblastí, ze kterých nejde utéci).
  • Spočítejte, kolik má která místnost políček.

23. CVIČENÍ - teoretické:

Dynamické programování:

  • opakování prohledávání stavového prostoru
  • úloha s kouzelnou tramvají (chceme se dostat z bodu 1 do bodu N, pěšky se posuneme o 1 za 1 minutu, kouzelná tramvaj nás odveze ze stavu s do stavu 2*s za 2 minuty) - řešení rozepsáním možností stavového prostoru -> dynamickým programováním
  • nejdelší cesta v orientovaném grafu bez cyklů
  • úloha s mrkví a petrželí (kolik je možností jak osázet 10 záhonků mrkví a petrželí, když nesmíme mít dvě petržele vedle sebe)
  • editační vzdálenost = nejdelší společná podposloupnost

Aritmetické výrazy:

  • zápis aritmetických výrazů v infixu, prefixu, postfixu, stromem
  • vyhodnocení aritmetického výrazu v prefixu, postfixu

Webové technologie (DVPP)

Kurz v rámci celoživotního vzdělávání.

Odkaz na stránky kurzu: Webové technologie.