Opakování.

Domácí úkol:

• Je dáno 12 kuliček stejných hmotností až na jednu, která je lehčí nebo těžší než ostatní.
  • Popište postup, jak pomocí 3 vážení na rovnoramenných vahách zjistit, která to je a zda je lehčí či těžší. [4 body]
  • Dokažte, že pro 13 kuliček jsou již potřeba 4 vážení. [3 body]
• Nalezněte sadu co nejméně závaží, se kterou lze navážit libovolný celý počet gramů od 0 do 999.
  • závaží se kladou vždy na jednu misku, vážený předmět na druhou, [2 body]
  • závaží lze pokládat na obě misky. [2 body]
  • Zkuste dokázat, že vaše řešení je optimální. [2 + 2 body]

Algoritmy pro práci s dlouhými čísly.

Úvodní příklady na třídění.

Domácí úkol:

• Popište algoritmus pro binární vyhledávání tak, aby v případě, že se hledané číslo v poli nevyskytuje, nalezlo nejbližší větší číslo. [4 body] Dodejte, prosím, i důkaz jeho správnosti. [3 body]
• Popište program, který pro zadaná čísla a, b, c co nejefektivněji spočte a^b mod c. [3 body]
• Popište program pro celočíselné odmocňování, tj. program, který pro zadané číslo N vrátí dolní celou část druhé odmocniny z N. [3 body]

Písemně je možné úkol odevzdat nejpozději na cvičení 4. 5. 2020, elektronicky do 10. 3. 2020 23:59.

Algoritmy pro třídění.

Domácí úkol:

• Je dáno N čísel v rozsahu 0..N³-1. Sestrojte algoritmus, který je v lineárním čase setřídí. (Hint: Použijte příhrádkové třídění.) [5 bodů]
• „Jak vypadá inverzní funkce k třídění?“ aneb míchání karet: Napište algoritmus, který k zadané posloupnosti vygeneruje její náhodnou permutaci tak, aby všechny permutace byly stejně pravděpodobné. To dokažte. (Lze to v lineárním čase.) [7 bodů]

Písemně je možné úkol odevzdat nejpozději na cvičení 16. 3. 2020, elektronicky do 17. 3. 2020 23:59.

Projděte si prezentaci ke spojovým seznamům.

Domácí úkol:

• V pseudokódu nebo Pythonu popište implementaci následujících operací se spojovými seznamy:
  • určit počet prvků [2 body]
  • nalezení posledního prvku [2 body]
  • vytvoření kopie seznamu [3 body]
  • přidání prvku na dané místo [2 body]
  • slití dvou uspořádaných seznamů do jednoho (merge) [4 body]

Úkol odevzdávejte mailem nejpozději do 31. 3. 2020 23:59.

Přečtěte si kapitolu 10.1 Hanojské věže z knihy Průvodce labyrintem algoritmů (str. 235–237).

Domácí úkol:

Ze cvičení 1–4 na straně 237 si vyberte až 3, každé za 5 bodů.

Úkol odevzdávejte mailem nejpozději do 16. 4. 2020 23:59.

Domácí úkol:

1.   Navrhněte algoritmus, který v čase O(n + m), kde n je počet vrcholů a m počet hran, zjistí, zda zadaný graf je bipartitní. Tak se říká grafům, jejichž vrcholy lze rozdělit na dvě množiny tak, aby koncové vrcholy každé hrany patřily do různých množin. [5 bodů]

2.   Na jisté šachovnici žil kulhavý kůň. To je zvláštní šachová figurka, která v sudých tazích táhne jako jezdec, v lichých jako pěšec. Vymyslete algoritmus, který z jednoho zadaného políčka dokulhá na druhé na nejmenší možný počet tahů. [5 bodů]

3. Mějme souvislý orientovaný graf. Chceme mazat jeho vrcholy jeden po druhém tak, aby graf zůstal stále souvislý. Jak takové pořadí mazání najít? Správnost postupu dokažte. [5 bodů]

K řešení se může hodit znát algoritmy z přednášky. Pokud je řešením varianta některého z těchto standardních algoritmů, nemusíte rozepisovat celý postup v pseudokódu, stačí vysvětlit potřebné úpravy algoritmu. K inspiraci může posloužit také Průvodce labyrintem algoritmů, ze kterého tyto úlohy pocházejí.

Úkol odevzdávejte mailem nejpozději do 29. 4. 2020 23:59.

Vymyslete, jak najít komponenty souvislosti grafu s pomocí jediného spuštění DFS. [3 body]

V orientovaném grafu jsou některé vrcholy obarvené zeleně. Jak zjistit, jestli existuje cyklus obsahující alespoň jeden zelený vrchol? [4 body]

Najděte algoritmy pro tyto grafové problémy. Pokaždé existuje řešení pracující v lineárním čase vzhledem k velikosti grafu.

• Eulerovský tah: Mějme souvislý neorientovaný graf. Chceme ho nakreslit jedním tahem, tedy nalézt posloupnost na sebe navazujících hran, která obsahuje každou hranu grafu právě jednou. [5 bodů]
• Asfaltování: Máme mapu městečka v podobě neorientovaného grafu. Parta asfaltérů umí za jednu směnu vyasfaltovat dvě na sebe navazující ulice. Jak vyasfaltovat každou ulici právě jednou? Jde to pokaždé, když je ulic sudý počet? [5 bodů]

Úkol odevzdávejte mailem nejpozději do 12. 5. 2020 23:59.

1) Spletitý kabel: Mějme dlouhý kabel, z jehož obou konců vystupuje po n drátech. Každý drát na levém konci je propojen s právě jedním na konci druhém a my chceme zjistit, který s kterým. K tomu můžeme používat následující operace: (1) přivéstnapětí na daný drát na levém konci, (2) odpojit napětí z daného drátu na levém konci, (3) změřit napětí na daném drátu na pravém konci. Navrhněte algoritmus, který pomocí těchto operací zjistí, co je s čím propojeno. Snažte se počet operací minimalizovat. [4 body]

2) Šroubky a matičky: Na stole leží n různých šroubků a n matiček. Každá matička pasuje na právě jeden šroub a my chceme zjistit, která na který. Umíme ale pouze porovnávat šroub s matičkou – tím získáme jeden ze tří možných výsledků: matička je příliš velká, příliš malá, nebo správně velká. Nalezněte co nejefektivnější algoritmus. [5 bodů]

3) Náhodná k-tice: Máme-li obrovský soubor a chceme o něm získat alespoň hrubou představu, hodí se prozkoumat náhodnou k-tici řádků. Vymyslete algoritmus, který ji vybere tak, aby všechny k-tice měly stejnou pravděpodobnost. Vstup se celý nevejde do paměti a jeho velikost ani předem neznáme; k-tice se do paměti spolehlivě vejde. Zvládnete to na jediný průchod daty? [4 body]

4) Kopcem nazveme podposloupnost, která nejprve roste a pak klesá. Vymyslete algoritmus, který v zadané posloupnosti nalezne nejdelší kopec. [4 body]

Úvod, opakování

NumPy

• PyCharm
• Anaconda, miniconda

Matplotlib

https://colab.research.google.com/drive/1CRC3q9COgQNopalcZB5xCVFzmr45-HKW