Programování 2 pro matematiky

• Součet 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!.

• Slidy: NumPy (videozáznam)
• 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.

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

• Příklady použití (videozáznam)
• Dokumentace

• Největší společný dělitel dvou polynomů (funguje Euklidův algoritmus).
• Derivování polynomu.
• Hledání kořene polynomu Newtonovou metodou
• Hledání racionálních kořenů využitím tohoto tvrzení: Pokud je zlomek p/q v základním tvaru kořenem polynomu, pak p je dělitelem nultého koeficientu a q dělitelem nejvyššího koeficientu.
• Po nalezení kořene α můžete polynom vydělit polynomem (x-α) a pokračovat v hledání dalších kořenů.

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

Podívejte se podrobnější informace o zápočtových programech.

• 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
• 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í permutací na množině {1,…,n}
• 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í 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:
  • Nejkratší cesta, ale smíme jednou projít políčkem se zdí.
  • Cesta šachovým jezdcem.
  • 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.)

• se seznamy sousedů
• s maticí sousednosti

Abstraktní popis grafu pomocí třídy:

• se seznamy sousedů
• s maticí sousednosti
• s maticí sousednosti a iterátory
• příklad na použití iterátorů

Podobným způsobem vyřešte následující úlohy:

• Najděte v grafu dva nejvzdálenější vrcholy.
• Najděte všechny vrcholy, které leží na některé z nejkratších cest mezi zadnou dvojicí vrcholů.
• Spočítejte, kolik má neorientovaný graf komponent souvislosti.
• Nalezněte pomocí BFS kostru grafu (tvoří ji ty hrany, které vedly do nově objevených vrcholů).
• Zjistěte, zda je graf bipartitní (ReCodEx).

• ve stromech
• v obecných grafech
• aplikace na počítání hloubky stromu

Podobným způsobem vyřešte následující úlohy:

• Dostanete strom, najděte v něm nejdelší cestu. Pozor, cesty ve stromech mohou vést jak "svisle" (mezi předkem a potomkem) nebo „napříč“ (mezi dvěma různými větvemi).
• Jak se změní předchozí úloha, pokud hrany stromu budou ohodnocené celými čísly a budeme chtít najít cestu s největším součtem hran?
• Dostanete strom, označte co nejvíc vrcholů tak, aby žádné dva označené nebyly spojeny hranou. (Nápověda: Pro každý podstrom spočitejte dvě maxima: jedno pro případ, kdy kořen podstromu je označený, druhé když není.)
• Zjistěte, zda zadaný neorientovaný graf je acyklický. Jak je to pro orientované grafy?
• Naprogramujte hledání mostů podle kapitoly 5.7 v Průvodci labyrintem algoritmů.

• Binární vyhledávání
• Mergesort
• Quicksort
• Quickselect

Další příklady na rozmyšlení:

• Kolik inverzí je v zadané posloupnosti? Prvky x_i a x_j jsou v inverzi, pokud i < j a současně x_i > x_j. Nápověda: Upravte Mergesort. (Též bude v ReCodExu.)
• Napište funkci, která dostane setříděný seznam čísel a najde nejmenší přirozené číslo, které v něm chybí. Seznam nesmíte nijak upravovat a kromě něj smíte použít pouze konstantní množství paměti.
• Hanojské věže

• Rozklad obdélníka 1×n na dílky 1×1 a 1×2
• Rozklad obdélníka 1×n na libovolně velké dílky
  • … co kdybychom zakázali používat dílky 1×1?
  • … co kdyby všechny rozměry dílků musely být liché?
  • … co kdybychom nesměli použít dva stejné dílky vedle sebe?
• Rozklad řetězce na slova ze slovníku
  • Na cvičení jsme používali slovník vygenerovaný ze spelling checkeru aspell příkazem aspell -d cs dump master. Vztahuje se na něj licence GNU GPL (což speciálně znamená, že ve vlastních pokusech ho můžete používat libovolně).
  • Spočítejte, kolik takových rozkladů existuje.
  • Najděte rozklad na nejmenší možný počet slov (dá se předpokládat, že bude smysluplnější než rozklady na spoustu krátkých slov)
  • Také můžeme slovům přiřadit váhy podle toho, jak často se vyskytují v nějakém korpusu textů. Pak chceme hledat rozklad s co největší vahou.