Programování 2 pro matematiky

Ve školním roce 2020/2021 vedeme společně s Tiborem Rózsou cvičení z matematického Programování 2. Cvičení má dvě části: praktickou ve čtvrtek od 14:00 [v N8, dá-li PES] (tu vedu já) a teoretickou v úterý od 15:40 [v N11, dá-li PES] (vede Tibor).

Teoretické cvičení se zatím koná po Zoomu, odkaz vám měl přijít mailem. Pokud nedorazil, podívejte se do spamu a když tak mi napište.

Pokud chcete cokoliv konzultovat, napište mi prosím e-mail na mares+p2m@kam.mff.cuni.cz a domluvíme se.

K získání zápočtu je potřeba:

Co jsme dělali

datum téma
4. 3. Základní aritmetické algoritmy pracující po číslicích (vzpomínka na základní školu):
  • 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!.
11. 3.
  • 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:
  • Ú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 xi = (xi-1 + xi-2) / 2. Víme-li, že x8=426 a x9=427, kolik je x0 a x1? 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.
18. 3.
25. 3. Kreslení grafů pomocí knihovny MatPlotLib:
1. 4. Pokračujeme s procvičováním řídkých polynomů a MatPlotLibu. Pár dalších příkladů s polynomy, pokud už máte vše hotové:
  • 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ů.
8. 4. Spojové seznamy:

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)
15. 4. Pokračujeme se spojovými seznamy.

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

22. 4. Reprezentace výrazů pomocí stromů:

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.
29. 4. Rekurzivní generování a počítání:

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.
6. 5. Prohledávání do šířky ve čtvercové síti:

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.)
13. 5. Prohledávání grafů do šířky (neboli BFS – breadth-first search):

Abstraktní popis grafu pomocí třídy:

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).
20. 5. Prohledávání grafů do hloubky (DFS – depth-first search):

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ů.
27. 5. Metoda Rozděl a panuj:

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

  • Kolik inverzí je v zadané posloupnosti? Prvky xi a xj jsou v inverzi, pokud i < j a současně xi > xj. 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
3. 6. Dynamické programování:
  • 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.

Odkazy

Stránku spravuje Martin Mareš