Mgr. Klára Pešková, Ph.D.

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

Knihovny:

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

---

Funkce:

• Funkce
• Funkce - příklady na procvičení funkcí: funkce_priklady.txt
• sibenice_kostra.py

Generování seznamů:

• 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(n²), 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(n³), O(n²), 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(n²) - 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é:

• 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):

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

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

• hvezdicky
• nuly_jednicky
• rostouci_posloupnosti

Ž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:

• 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