• Lekce 6
  • Úlohy
  • Co jsme dnes probrali

Lekce 6

Úlohy

Z následujících úloh si vyberte tři. Pokud naprogramujete i další, dostanete bonusové bodíky.

Násobky

Vypište všechny násobky tří (do třiceti). Nejdříve všechny do jedné řádky.

Poté program vylepšete tak, aby tiskl vždy nejvýše 4 násobky na jeden řádek.

Hint: Využijte argument end funkce print (koukněte do dokumentace).

Dělitelé

Vypiště všechny dělitele čísla zadaného jako vstup programu.

Rámeček

Nakreslete rámeček. Napište program tak, aby bylo snadné změnit jeho velikost.

Příklad rámečku, který má rozměr vnitřního obdélníku 20 krát 3.

XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX
XX                    XX
XX                    XX
XX                    XX
XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX

Vlajka

Napište program, který nakreslí na obrazovku vlajku.

X
XX
XXX
XXXX
XXXXX

Řešením není opakované volání funkce print, nýbrž vhodné použítý for cyklus.

Zrcadlová vlajka

Napište program, který vypíše zrcadlovou vlajku.

    X
   XX
  XXX
 XXXX
XXXXX

Řešením není opakované volání funkce print, nýbrž vhodné použítý for cyklus.

Co jsme dnes probrali

Úvod do algoritmizace a časové složitosti

• Začali jsme v programech používat cykly, což může zapříčinit to, že program bude moci běžet dlouho
• Snažíme se tedy, aby náš program běžel co nejkratší dobu
• Koukněte se do této složky
  • Najdete tam tři programy, které počítají to stejné (druhé mocniny celých čísel do nějakého čísla)
  • fast.py se zastaví, jakmile $i^2 \geq limit$, tedy po $\sqrt{limit}$ iteracích
  • ok.py sice brzy přestane vypisovat, ale běží dál a provede limit iterací
  • slow.py využívá pole, o kterých jsme si ještě nic neříkali. Toto řešení je pomalé, protože v každé iteraci pole prohledává, což trvá dlouho
• Kdykoli píšeme program, který něco počítá, tak bychom se měli zamyslet nad tím, jak dlouho poběží
• Doba běhu typicky závisí na velikosti vstupu. Tato velikost se běžně značí n.
  • V příkladové úloze to je hodnota limit
  • Pokud bychom počítali průměr čísel, byl by to jejich počet
  • Pokud bychom počítali délku řetězce, byla by to jeho délka
  • Doba běhu ovšem může záviset na více hodnotách, např. zpracování obrázku bude záviset na jeho šířce a výšce
• Nás zajímá to, jak dlouho bude program běžet v závislosti na velikosti vstupu
  • Nejvíce nás zajímá to, jak bude program běžet pro velké vstupy (říkáme tomu nejhorší případ)
• Také se snažíme zjistit, kolik operací program vykoná
• Pojďme analyzovat řešení ok.py
  • Odteď budeme proměnné limit říkat n
  • Na začátku programu...
    • ...vezmeme vstup od uživatele
    • ...převedeme ho na int
  • To jsou 2 operace, které se vykonají vždy
  • Poté máme for cyklus
    • Ten se provede nkrát
    • V něm se vždy (pro každou iteraci cyklu)
      • zvýší hodnota i o jedna
      • vypočte druhá mocnina i
      • provede se porovnání $i^2 < n$
  • To je dalších $3n$ operací
  • Ale tady nekončíme. Kolikrát se provede kód na řádce 4?
    • Provede se $\sqrt{n}$ krát
      • Proč zrovna $\sqrt{n}$ krát
      • Podmínka v ifu je takováto: $i^2 < n$
      • Upravíme na $i < \sqrt{n}$
      • Vidíme, že po $\sqrt{n}$ iteracích začne být $i^2$ větší, než $n$
    • Co se v tomto ifu stane?
      • spočte se $i^2$
      • vytiskne se hodnota $i^2$
    • Celkem tedy $2\sqrt{n}$ operací
  • Sečteno podtrženo to je $3n + 2\sqrt{n} + 2$ operací
  • V teoretické informatice řekneme, že doba běhu našeho algoritmu leží ve třídě $\mathcal{O}(n)$
    • Slovo třída znamená skupina (množina) funkcí. V tomto případě skupina $\mathcal{O}(n)$ značí všechny funkce, které rostou nejvýše tak rychle, jako nějaká lineární funkce.
      • Definice vypadá takhle $$f(n) \in O(g(n)) \iff \exists\ c > 0, n_0 \geq 0 : \forall\ n \geq n_0 : |f(n)| \leq c \cdot |g(n)|$$ - NEMUSÍTE JI ZNÁT
    • Naše funkce do ní rozhodně patří
    • Například naše funkce $3n + 2\sqrt{n} + 2$ roste pomaleji, než $4n$
    • U asymptotické notace můžeme krátit konstanty a zbavovat se pomaleji rostoucí členů
• Více si o složitosti můžete přečíst tady

Analýza fast.py

• Na začátku se provedou dvě operace
  • Načtení vstupu
  • Inicializace proměnné i
• Ve while cyklu se provedou tři operace
  • Umocní se i na druhou
  • Vytiskne se
  • Inkrementuje se proměnná
• Samotný while cyklus se provede nanejvýš $\sqrt{limit}$krát
• Celkově tedy kód provede $3\sqrt{limit} + 2$ operací
  • Náš algoritmus je tedy v $\mathcal{O}(\sqrt{limit})$
  • Dokonce leží i v $\Theta(\sqrt{limit})$

Analýza slow.py

• Na začátku se provedou dvě operace
  • Načtení vstupu
  • Inicializace pole integers
• Poté se provede $limit$ iterací prvního cyklu
  • Každý krok cyklu se provede jedna operace, a to vložení do seznamu
  • Funkce append má amortizovanou časovou složitost $\mathcal{O}(1)$
    • To, co je amortizovaná časová složitost, se dozvíte ve druhém semestru na vysoké škole
• Druhý cyklus také provede $limit$ iterací
  • Každý krok cyklu se provedou dvě operace
    • Operace in zjistí, jestli je j**(1/2) v poli integers
      • Tato operace trvá $\mathcal{O}(limit)$
• Celkový čas druhého cyklu je tedy $\mathcal{O}(limit^2)$
• Celkem tedy náš algoritmus potvrá v nejhorším případě $\mathcal{O}(limit^2)$