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

1. CVIČENÍ - teoretické:

• podmínky zápočtu
• složitost prakticky - procvičování na jednoduchých úlohách
• pseudokód

2. CVIČENÍ - praktické:

• 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
• příkaz if (zanořování, elif, else), cyklus while (včetně else)
• základní použití cyklů - ciferný součet, Euklidův algoritmus, test prvočíselnosti
• zpracování posloupnosti dat, seznamy a operace s nimi, indexování, řezy
• generátorová notace seznamů (list comprehension)
• formátovaný výstup
• funkce - parametry, return, lokalita proměnných
• znakové řetězce, N-tice (tuples)
• množiny a slovníky
• textové soubory
• standardní knihovna (math, copy, array, fractions, random, ...).
• výjimky - try-except, raise, assert
• základní informace o třídách a objektech v Pythonu (jen princip, bez většího procvičení)
• základní postupy při ladění programů

3. CVIČENÍ - teoretické:

Dokazování či vyvracení tvrzení typu:

• 5n + 13 ∈ O(n)
• n³ ∈ O(n²)
• f ∈ O(g), g ∈ O(h) -> f ∈ O(h)
• f ∈ O(g), h ∈ O(g) -> f+h ∈ O(g)
• f ∈ O(g), h ∈ O(g) -> f*h ∈ O(g)
• f ∈ O(g₁), h ∈ O(g₂) -> f*h ∈ O(g₁*g₂)

Podle definice, nalezením vhodného n0 a C, nebo vhodným protipříkladem.

4. CVIČENÍ - praktické:

• Formátování řetězců (.format()) na w3schools
• Výjimky výjimky
• Objekty - základy objekty

5. 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:

• najděte maximum / maximum a počet jeho výskytů
• rozhodněte, zda je posloupnost monotónní a jak (konstantní, rostoucí, neklesající, klesající, nerostoucí)
• určete největší číslo, které se v posloupnosti neopakuje
• najděte souvislý úsek s maximalním součtem (v O(n³), O(n²), O(n) - viz Průvodce labyrimtem algoritmů, str. 23)

6. CVIČENÍ - praktické:

Objekty, magic methods Kód ze čtvrtečního cvičení (neupravený, nedokonalý, ...):

• osoba.py
• objednavka.py

7. CVIČENÍ - teoretické:

Třídící algoritmy

• select(ion) sort
• insert(ion) sort
• bubble sort
• heap sort

8. CVIČENÍ - praktické:

Dekompozice

• sibenice_kostra.py

9. CVIČENÍ - teoretické:

Abstraktní datové typy fronta, zásobník, halda

• Příklady zásobník, fronta
• správné uzávorkování - jeden typ závorek, více typů závorek
• Halda - operace, heapsort

10. CVIČENÍ - praktické:

Lineární spojové seznamy:

• první pokusy

Knihovna TkInter

• TkInter vystřihovánky tkinter_vystrihovanky.py

11. CVIČENÍ - teoretické:

Lineární spojové seznamy - procvičování základních operací

• vypsání všech hodnot
• nalezení posledního prvku
• vyhledání prvku s danou hodnotou
• přidání prvku na začátek, na konec seznamu
• vytvoření kopie seznamu

12. CVIČENÍ - praktické:

Lineární spojové seznamy:

• procvičování základních operací

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
• Video Martina Mareše: numpy - video

13. CVIČENÍ - teoretické:

Lineární spojové seznamy - další procvičování

• odebrání prvku ze začátku, z konce seznamu
• odebrání daného prvku
• vyhledání prvku s danou hodnotou
• zrušení všech prvků v seznamu s danou hodnotou
• obrácení pořadí prvků v seznamu

14. CVIČENÍ - praktické:

Hra hádání zvířátek s AI

MatPlotLib - knihovna na kreslení grafů

• matplotlib_priklady.py
• Dokumentace: matplotlib.org

16. CVIČENÍ - praktické:

Příklad: jelinek2.0.py

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é posloupnosti délky n z nul, jedniček, dvojek a trojek.
• Napište rekurzivní funkci, která vypíše všechny možné řetězce délky n z čísel od 0 do 9.

17. CVIČENÍ - teoretické:

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

Operace s binárními vyhledávacími stromy

18. 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í:

• Prohlédněte si funkce v následujícím souboru: 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
• 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:

   
      ()()()  
      (())()  
      ()(())  
      (()())  
      ((()))

• 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