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:
- aktivní práce v hodinách - účast na minimálně 50% praktických cvičeních a minimálně 50% teoretických cvičeních
- na teoretickém cvičení vypracování písemných domácích úkolů (dosažení alespoň 70% z celkového počtu bodů = 37 bodů), pokud byste neměli dostatečný počet bodů, bude možné si body doplnit vyřešením dalších náhradních úloh
- na praktickém cvičení pravidelné řešení domácích úkolů zadávaných v ReCodExu (dosažení alespoň 70% z celkového počtu bodů = 80 bodů), pokud byste neměli dostatečný počet bodů, bude možné si body doplnit vyřešením dalších náhradních úloh
- na konci semestru - praktický zápočtový test u počítačů - test se bude psát na posledním praktickém cvičení, ve zkouškovém období budou vypsány dva opravné termíny
- vypracování zápočtového programu (včetně zpracování písemné dokumentace)
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:- Práce se soubory soubory
- hadani_skore.txt
- Výjimky výjimky
- standardní knihovna (math, copy, array, fractions, random, ...).
Funkce:
- Funkce
- Funkce - příklady na procvičení funkcí: funkce_priklady.txt
- sibenice_kostra.py
- list comprehension - list comprehension
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 jakoC:\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
cmd
do řá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é:
- typové anotace - slidy Martina Mareše: typové anotace - slidy, podrobnější povídání
- vývojové prostředí PyCharm
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ů
- matplotlib_priklady.py
- Dokumentace: matplotlib.org
- Příklad: kostra.py, mapa.png
11. CVIČENÍ - teoretické:
Lineární spojové seznamy:
- Jednoduché procvičování
Abstraktní datové typy fronta a zásobník
- Příklady ze cvičení
- správné uzávorkování - jeden typ závorek, více typů závorek
12. CVIČENÍ - praktické:
Procvičování spojových seznamů (obyčejných, necyklických, bezhlavých):
- vytvořte čtyři uzly s hodnotami 15, 10, 5, 25 a propojte je do spojového seznamu
- projděte vytvořený seznam a vypište hodnoty prvků
- projděte vytvořený seznam a změňte hodnotu 10 na hodnotu 100
- 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"
- napište funkci, která dostane jako parametr ukazatel na spojový seznam a vrátí součet hodnot prvků
- napište funkci, která přidá prvek na začátek seznamu
- napište funkci, která přidá prvek na konec seznamu
- napište funkci, která načte seznam ze vstupu (čísla oddělená mezerami) a vrátí ukazatel na první prvek
Knihovna TkInter
- TkInter vystřihovánky tkinter_vystrihovanky.py
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élkyk
. - 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:
- Hledání dosažitelných políček: projdi.py (šablona) (příklad vstupu)
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.