Programování 2 pro matematiky

• Součet, rozdíl a součin (program)
• Porovnáváni (větší/menší/rovno)
• Dělení (jednodušší: dělíme malým číslem)
• Výpočet Eulerova čísla: Σ_n≥0 1/n!.

• Výklad: Třídy a objekty
• Příklad definice třídy. Dodělejte do něj:
  • Naučte každé zvíře slyšet navíc na jméno potvůrka.
  • Doplňte atribut pozice a zařiďte, aby zvíře slyšelo na jméno jenom tehdy, když pozice je doma.
  • Vytvořte odvozenou třídu Pes, jehož metoda ozvi_se na každé druhé zavolání zaštěká a jinak zavrčí.

• Opakování z Programování 1: Výjimky.
• Pokračování tříd a objektů z minula.
• Nadefinujte třídu Rect reprezentující obdélníky v rovině (viz domácí úkol).
• Nadefinujte třídu RoundRect odvozenou od Rect pro obdélníky se zakulacenými rohy (s jednotkovým poloměrem; předpokládejme že délky všech stran jsou alespoň 2). Předefinujte metody, aby dávaly smysl.
• Naučte metodu __eq__, aby vracela False, pokud porovnává s něčím, co není Rect, případně RoundRect. Může se hodit isinstance.
• Nadefinujte třídu Zlomek pro zlomky:
  • Třída má atributy a a b pro čitatele a jmenovatele.
  • Přidejte metody __str__ a __repr__ pro převod na řetězec.
  • Přidejte metody pro aritmetické operátory: __add__, __sub__, __mul__, __truediv__ (operátor /), __neg__ (unární -), __pos__ (unární +).
  • Přidejte metody pro porovnávání: __eq__ (operátor ==), __lt__ (operátor <), __gt__ (operátor >). Pozor na to, že 3/4 se mají rovnat i -6/-8.
  • Při pokusu o vytvoření zlomku s nulovým jmenovatelem nebo dělení nulou vyhlašte výjimku: raise ValueError("Nějaká zpráva").
  • Při vytvoření zlomku a po každé operaci zlomek zkraťte a normalizujte, aby byl jmenovatel kladný.
  • Aritmetika by mohla umět zlomek+int.
  • Co případy int+zlomek? Tady se hodí reverzní metody __radd__ apod., viz dokumentace.

• Vývojové prostředí PyCharm, ladění programů.
• Typová kontrola:
  • Slidy: typové anotace
  • Podrobnější úvod
  • Type-checker MyPy, katalog dalších nástrojů

• Slidy: NumPy
• Instalace NumPy pod Windows:
  • Vlezte si do adresáře, kde máte nainstalovaný Python (typicky to bývá něco jako C:\Users\Jméno\AppData\Local\Programs\Python\Python37-32; kdybyste ho nemohli najít, hledejte, kde na disku máte python.exe).
  • Spusťte python -m pip install numpy.
• Dokumentace k NumPy:
  • Úvod
  • Referenční příručka
  • Lineární algebra
  • Vstup a výstup
• Úkoly (snažte se používat jenom operace s poli, žádné cykly):
  • Vyrobte matici tvaru R×S vyplněnou číslem X.
  • Vyrobte matici tvaru R×S, která má na okrajích jedničky a jinde nuly.
  • Vyrobte matici tvaru R×S, která bude mít v i-tém řádku samá čísla i.
  • Spočítejte determinant 10 matic 10×10 vyplněných náhodnými čísly mezi -1 a 1 (viz np.linalg.det)
  • Uvažujme „průměrovací Fibonacciho čísla“ definovaná rekurentním vztahem x_i = (x_i-1 + x_i-2) / 2. Víme-li, že x₈=426 a x₉=427, kolik je x₀ a x₁? Vyřešte soustavu lineárních rovnic pomocí np.linalg.solve. Pro výrobu matic s jedničkami na posunuté diagonále se hodí np.eye.
  • Pokusy s dělitelností:
    • Vyrobte booleovskou matici, která má na pozici (i,j) True právě tehdy, je-li i dělitelné j.
    • Vyrobte vektor, který pro každé číslo od 1 do N uvádí počet jeho dělitelů.
    • Vyrobte vektor všech prvočísel mezi 1 a N.

• Příklady použití
• Dokumentace

• Jednosměrné s přidáváním na začátek
• Jednosměrné s přidáváním na konec
• Obousměrné s hlavou – asi nejelegantnější řešení

Prohlédněte si vzorové programy a doplňte jak do jednosměrných, tak do obousměrných seznamů funkce pro následující operace:

• find(self, x): nalezení prvku s danou hodnotou (vrátí None, pokud tam žádný není)
• remove_node(self, n): odstranění prvku zadaného referencí (třeba nalezeného předchozí funkcí)
• pred_node(self, n): zjištění předchůdce prvku zadaného referencí (vrátí None pro první prvek)
• succ_node(self, n): zjištění následníka prvku zadaného referencí (vrátí None pro poslední prvek)
• reverse(self): přehází prvky seznamu do opačného pořadí (nevyrábí nové prvky, jen přepojuje odkazy)

• Elementární řešení
• Objektové řešení
• Elegantnější objektové řešení

Rozšiřte některý z ukázkových programů o následující funkce:

• unární operátory (třeba 'N' pro negaci)
• počítání hloubky stromu (vzdálenost mezi kořenem a nejvzdálenějším listem)
• výpis stromu v postfixové notaci
• Řešení předchozích tří úkolů
• načtení výrazu v postfixové notaci a jeho převod na strom
• výpis stromu v infixové notaci (to je ta obvyklá) bez zbytečných závorek
• načtení výrazu v infixové notaci a převod na strom (tohle je trochu těžší)
• proměnné: nový typ listů stromu, který obsahuje jméno proměnné; při vyhodnocování výrazu předáváme slovník, ve kterém jsou proměnným přiřazeny hodnoty.

• Příklad s Fibonacciho čísly a zrychlení uložením mezivýsledků
• Generování posloupností 0 a 1 (několik variant)
• Generování posloupností s daným počtem 1 (několik variant)

V podobném stylu zkuste naprogramovat (bez použití itertools a podobných knihoven):

• Generování posloupností 0 a 1, ve kterých není víc než k jedniček po sobě.
• Generování všech dobře uzávorkovaných posloupností s n levými a n pravými závorkami. Například pro n=3 to jsou ()()(), ()(()), (()()), (())(), ((())).
• Generování permutací na množině {1,…,n}.
• Generování posloupností 0 a 1 v takovém pořadí, aby se sousední dvě lišily jen na jedné pozici. Např. pro n=3 je jeden ze správných výstupů 000, 001, 011, 010, 110, 111, 101, 100.

• Hledání dosažitelných políček (příklad vstupu)
• Výpočet vzdáleností
• Hledání nejkratší cesty

Podobným způsobem vyřešte následující ú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.
• Další variace na hledání nejkratší cesty:
  • Cesta šachovým jezdcem.
  • Nejkratší cesta, ale smíme jednou projít políčkem se zdí.
  • V bludišti jsou dveře a ovladače. Kdykoliv vstoupíte na políčko s ovladačem, otevřou se všechny dveře. Kdykoliv projdete dveřmi, všechny dveře se zavřou. (Tady si chcete přidat další souřadnici nabývající hodnot 0 nebo 1, která kóduje, zda jsou zrovna dveře otevřené.)
  • Cesta kulhavým koněm: to je figurka, která se v sudých tazích pohybuje jako jezdec, v lichých jako král.
  • Autíčku se porouchalo řízení a umí jezdit jenom rovně a zatáčet doprava (stojíte-li na nějakém políčku natočeni směrem nahoru, můžete jet buďto nahoru se zachováním natočení, nebo o políčko doprava s otočením doprava). Je dána počáteční poloha a natočení a pozice servisu, najděte nejkratší cestu do servisu. (Pozor, nejkratší cesta může jedním políčkem projet vícekrát.)