• Lekce 11
  • Úlohy
  • Co jsme dnes probrali

Lekce 11

Úlohy

• Na úlohy máte dva týdny a kus, tedy do 8. 12. 2024.
• Dejte pozor na to, odkud máte číst vstup.

Přestupný rok (3b)

• Napište funkci, která dostane rok a vrátí True, pokud je rok přestupný.
  • Program nemusí číst žádný vstup, stačí opravdu jen implementovat tuto funkci.
• Nastudujte si přesná pravidla.
• Nepoužívejte knihovny.

Pascalův trojúhelník (5b)

• Napište program, který vypíše Pascalův trojúhelník.
• Program bude vyžadovat jeden argument, který určí počet řádků.
• Očekávaný výstup pro python pascal.py 6 je v souboru pascal-exp.txt.
• Těžší verze (+3b): Trojúhelník bude zarovnaný na střed, viz pascal-aligned-exp.txt.
  • Detaily zarovnání se ve vašem řešení mohou drobně lišit.

Pí (7b)

• Napište program, který přibližně určí číslo π.
• Použijte následující metodu:
  • Uvažujme čtverec a jemu vepsaný kruh.
  • Budeme náhodně vybírat body ze čtverce a zjišťovat, zda leží v kruhu.
    • Náhodný bod lze vybrat tak, že si necháme vygenerovat jeho souřadnice x, y jako dvě náhodná čísla z vhodného intervalu.
    • Jestli bod leží v kruhu lze zjistit tak, že pomocí Pythagorovy věty spočítáme vzdálenost od středu kruhu a porovnáme ji s poloměrem kruhu.
    • Musíte rozmyslet, jaký zvolit interval a poloměr kruhu.
  • Poměr počtu bodů v kruhu k celkovému počtu bodů by měl být přibližně stejný jako poměr jejich obsahů, tedy π/4.
• Celkem vygenerujte 1000000 bodů. Při většině pokusů byste měli dostat číslo od 3.139 do 3.144.

Hledání v souborech (8b)

• Jako argument programu dostanete textový řetězec neboli jehlu (hledáme jehlu v kupce sena).
• Napište program, který projde všechny soubory v aktuálním adresáři a pokusí se v nich jehlu vyhledat.
  • Zjistěte, jak pracovat s adresáři.
• Pokud soubor jehlu obsahuje, program vypíše jméno tohoto souboru (a pokračuje dalším souborem).
• Jako volitelný druhý argument může uživatel předat název adresáře, který se má prohledat.
• Očekávaný výstup pro python search.py "0 1" data/ je v souboru search-exp.txt.
• Těžší verze (+3b): Pokud program dostane přepínač -r, prohledá rekurzivně i všechny podadresáře.
  • Přepínač může být umístěn na libovolné pozici v argumentech, například python search.py text -r dir.

Sloupcový graf (10b)

• Na standardním vstupu dostanete několik hodnot, na každém řádku jednu.
• Hodnoty čtěte do té doby, než přijde konec vstupu.
  • Viz sekce Konec vstupu z dnešní lekce.
• Hodnoty vykreslete pomocí sloupcového grafu napsaném v SVG.
  • Hodnota určuje výšku sloupce.
• Výsledné SVG vypište na standardní výstup.
  • Očekáváme, že uživatel přesměruje výstup do souboru.
• V adresáři s daty najdete očekávaný výstup chart-exp.svg pro hodnoty z chart-in.txt.
  • Pochopit formát není příliš složité.
  • Čísla 140 a 120 na začátku určují šířku a výšku celého obrázku.
  • Každý sloupec má hodnoty x a y udávající souřadnice jeho levého dolního rohu (osa y roste dolů) a poté hodnoty width a height určující jeho rozměry.
• SVG soubor si můžete zobrazit ve webovém prohlížeči.

Kalendář (10b)

• Napište program, který vytiskne list kalendáře pro daný měsíc.
• Program bude ovládán argumenty:
  • bez argumentů vypíše aktuální měsíc,
  • s jedním argumentem vypíše měsíc současného roku,
  • se 2 argumenty pak kalendář s daným měsícem a rokem.
• Pro zjištění aktuálního data a dalších potřebných informací použijte například knihovnu datetime.
• Očekávaný výstup pro python calendar.py 5 2021 je v souboru calendar-exp.txt.
• EDIT: Prosím, nepoužívejte knihovnu calendar.

Co jsme dnes probrali

String slice

• V Pythonu je řetězec jen pole znaků.
• I ve stringu můžeme indexovat, můžeme také vytvářet slicy.
• V hranatých závorkách budou dvě čísla oddělená dvojtečkou
  • První index včetně, druhý index kromě
• Pomocí string sliců můžeme krájet stringy a brát z nich určité části
• Pokud nějaké ze dvou indexů vynecháme, Python nám vrátí string až do konce (od začátku)

jmeno = "barbara"

# vytiskne treti pismeno jmena
print(jmeno[2])

# vypise barbar
print(jmeno[0:6])

# vypise bara
print(jmeno[3:])

# vytiskne baba
print(jmeno[:2] + jmeno[3:5])

# Představme si následující vstup:
# jmeno:adam
# jmeno:barbora
# jmeno:david
# jmeno:emma

# Chceme vypsat jen jména za `jmeno:`

for line in vstup:
  print(vstup[6:])

Třídicí (řadící) algoritmy

• Slova "třízení" a "řazení" se používají jako synonyma, avšak nemají stejný význam (my je jako synonyma ale brát budeme)
• Používají se pro řazení neseřazených prvků
  • Umíme třídit nejenom čísla, ale i cokoli jiného, co má definované uspořádání
    • Řetězce (slova) pomocí lexikografického uspořádání (jako ve slovníku)
    • Objekty pomocí jejich klíčů
• Existuje mnoho způsobů, jak třídit

Selection sort

• Česky "třídění přímým výběrem"
• Má časovou složitost $\mathcal{O}(n^2)$
• Opakovaně vybírá nejmenší číslo z dosud nesetříděných čísel a to prohodí s číslem na začátku pole.
• Poté provádíme to stejné na "podpoli", které začíná na indexu 1.
• Tak postupujeme do té chvíle, až se dostaneme na konec pole.

def select_sort(pole):
    nalezene_min = 1

    for i in range(0, len(pole)):
        nalezene_min = i

        # hledame minimum
        for j in range(i + 1, len(pole)):
            # pokud jsme nasli mensi, nez dosud nalezene minimum
            if pole[j] < pole[nalezene_min]:
                # nastavime j jako nove minimum
                nalezene_min = j

        # prohodi pole[i] s pole[nalezene_min]
        pole[i], pole[nalezene_min] = pole[nalezene_min], pole[i]

Intermezzo o matematické indukci

• Jedna z možných důkazových technik
  • Dokazovat můžeme ještě sporem, přímo (a občas nepřímo)
• Nejčastěji se používá tehdy, kdy chceme dokázat, že něco platí pro nějakou množinu čísel (přirozená čísla)
• Základem indukce je tzn. basecase -- dokážeme, že tvrzení platí pro nějaké číslo (většinou jedničku)
  • Stačí jen dosadit
• Poté si řekneme, že tvrzení platí pro nějaké $k$ a tím musí platit i pro $k + 1$
  • Pro matematicky znalé dokazujeme implikaci "platí pro $k$ $\implies$ platí pro $k + 1$".
  • Tomuto říkáme indukční krok
• Dokázali jsme, že tvrzení platí pro $n = 1$, $n = k$ a $n = k + 1$.
  • To ale znamená, že jsme tvrzení dokázali pro všechna čísla
  • Za $k$ můžeme dosadit jedničku (pro kterou víme, že tvrzení platí), $k + 1$ je tedy dva.
    • Poté jakoby "rekurzivně" za $k$ dáme dvojku, $k + 1$ je tedy tři, a tak dále...

Příklad (důkaz časové složitosti SelectSortu):

Algoritmus provede celkem $n + (n-1) + (n-2) + ... + 3 + 2 + 1 = \frac{n(n+1)}{2} \in \mathcal{O}(n^2)$ porovnání.

Tvrzení, které potřebujeme dokázat je:

$$ n + (n-1) + (n-2) + ... + 3 + 2 + 1 = \frac{n(n+1)}{2} $$

Pro $n = 1$:

$$ 1 = \frac{1(1 + 1)}{2} = 1 $$

Levá strana se rovná pravé, tedy pro $n = 1$ platí.

Tvar pro $n = k$ vypadá:

$$ k + (k-1) + (k-2) + ... + 3 + 2 + 1 = \frac{k(k+1)}{2} $$

Nyní provedeme indukční krok $n = k + 1$:

$$ (k + 1) + k + (k-1) + (k-2) + ... + 3 + 2 + 1 = \frac{(k+1)(k+2)}{2} $$

$$ (k + 1) + \frac{k(k+1)}{2} = \frac{(k+1)(k+2)}{2} $$

$$ \frac{k(k+1) + 2(k + 1)}{2} = \frac{(k+1)(k+2)}{2} $$

$$ \frac{(k+1)(k + 2)}{2} = \frac{(k+1)(k+2)}{2} $$

$$ \square $$

Tím jsme tvrzení dokázali indukcí.

Merge sort

• Česky třídění sléváním
• Velmi rychlý a hojně používaný třídící algoritmus
• Běží v čase $\mathcal{O}(n \log n)$
• Nesetříděné pole se postupně dělí na poloviční, čtvrteční, atd.
• Třídí se malé pole (velikosti dva), které se následně slejí do většího
• Toto se opakuje, až dostaneme celé setříděné pole

Counting sort

• Český třídění počítáním
• Jen pro čísla, u kterých víme maximum
• Běží v $\mathcal{O}(n)$