| datum
| téma
|
|---|
| 19. 2. |
Základní aritmetické algoritmy pracující po číslicích:
- 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!.
|
| 26. 2. |
- Slidy: 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.
|
| 4. 3. |
- Vývojové prostředí PyCharm, ladění programů.
- Typová kontrola:
|
| 11. 3. |
Kreslení grafů pomocí knihovny MatPlotLib:
|
| 18. 3. |
Pokračujeme s procvičováním řídkých polynomů a MatPlotLibu.
|
| 25. 3. |
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í (None pro první prvek)
succ_node(self, n): zjištění následníka prvku zadaného referencí (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)
|
| 1. 4. |
Pokračujeme se spojovými seznamy.
|
| 8. 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.
Podívejte se podrobnější informace o zápočtových programech.
|
| 15. 4. |
Rekurzivní generování a počítání:
V podobném stylu zkuste naprogramovat (bez použití itertools a podobných knihoven):
- Generování posloupností 0 a 1 v takovém pořadí, aby se sousední dvě lišily jen na jedné pozici
- 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
()()(), ()(()), (()()), (())(), ((())).
|
| 22. 4. |
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:
- 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.)
|
| 29. 4. |
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).
Připomínám specifikaci zápočtových programů (dodejte do konce dubna).
|
| 6. 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ů
(algoritmus jsme načrtli na cvičení).
|
| 13. 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 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.
|
| 20. 5. |
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.
|