Vladan Majerech - NTIN061 Algoritmy a datové struktury II
Last Modified: 18.2.2024
Index
zápočtové příklady, odkazy, cvičení 1, cvičení 2, cvičení 3, cvičení 4, cvičení 5, cvičení 6, cvičení 7, cvičení 8, cvičení 9, cvičení 10, cvičení 11, cvičení 12, cvičení 13
Pro získání zápočtu z NTIN061 je potřeba získat (3/5 z možných bodů za domácí úkoly zadávané v průběhu semestru).
Zápočtové příklady
Pokud není uvedeno jinak, počet přidělených bodů rychle klesá v případě použití časově neoptimálních algoritmů. Za odevzdání po termínu je jen poloviční počet bodů. Termín je do počátku cvičení příslušného dne (15:40), odevzdáváme v běžném čitelném formátu (např v těle mailu či v příloze .pdf,.jpg,.png) e-mailem. Příklady s body uvedenými v závorce jsou bonusové, body je možno získat, ale nepočítají se do limitu požadovaných bodů. Domácí úlohy i souhrny cvičení budu nejspíš pravidelně publikovat až po čtvrtečních cvičeních.
| Kód | Body | Termín odevzdání | Zadání |
|---|---|---|---|
| interval | 10 | 19.10.2023 | Je při vypisování intervalu hodnot v binárním vyhledávacím stromu délka absolvovaného sledu (nemáme explicitní next pointery) $\in O(h + r)$, kde $h$ je hloubka stromu a $r$ počet vypsaných hodnot? Přesvědčivě zdůvodněte (v duchu cvičení, procházíme pomocí iterátoru Next())! |
| jehly | 10 | 26.10.2023 | Spočtěte, kolikrát se dané jehly vyskytují v daném seně (podslova v textu). Zajímají mne počty každé jehly zvlášť. |
| podposloupnost | 10 | 2.11.2023 | Spočtěte, kolikrát se daná jehla vyskytne v daném seně (dva řetězce, seno mnohem delší) jako podposloupnost (možnost proložení jinými znaky).Například v BARBARAR je BAR 9 krát. |
| věže | 10 | 9.11.2023 | Máme šachovnici $m\times n$ a na některých políčkách stojí sloupy. Na políčka (bez sloupů) je možno umísťovat věže. Každá věž ohrožuje políčka ve stejné řadě a stejném sloupci, ale pouze k nejbližšímu sloupu v daném směru. Otázkou je, kolik věží je možno rozmístit tak, aby žádná nestála na políčku ohroženém jinou věží. No a na Vás je popsat, jak nalézt odpověď (můžete používat „známé“ algoritmy jako podprogramy). |
| kluby | 10 | 16.11.2023 | Na kolejích jsou různé kluby, koleják může být součástí libovolného počtu klubů. Jste postaveni před úlohu vybrat z každého klubu předsedu a místopředsedu a to tak, aby každý koleják byl vybrán za nejvýš jeden klub a pro něj do právě jedné funkce. |
| porovnání | 10 | 23.11.2023 | Vytvořte co nejmělčí hradlovou síť, která pro n-bitová čísla $a$, $b$ vydá $1$ právě když $a\le b$. |
| souvislost | 10 | 30.11.2023 | Vytvořte co nejmělčí hradlovou síť, která pro matici sousednosti neorientovaného grafu $G$ vydá true, právě, je-li graf $G$ souvislý. |
| mult | 10 | 7.12.2023 | Nastiňte konstrukci hradlové sítě pro vynásobení dvou n-bitových čísel. Řešte nezávisle úlohu zaměřenou na minimalizaci hloubky od úlohy zaměřené na minimalizaci velikosti (odhadněte vždy oba rozměry). (Přesné rozměry nepožaduji, stačí „asymptotický odhad“, nicméně optimalizujte pro $n=2^{16}$). |
| cesty | 10 | 14.12.2023 | Pro dané vrcholy $u$, $v$ v orientovaném grafu nalezněte maximální počet vrcholově disjunktních cest z $u$ do $v$. |
| Hamilton | 10 | Hamiltonovská cesta v grafu, je cesta obsahující všechny vrcholy grafu (právě jednou). Hamiltonovská kružnice je Hamiltonovská cesta, kde navíc z koncového vrcholu vede hrana do počátečního vrcholu cesty. Ukažte, že jak v orientovaných, tak v neorientovaných grafech je (až na polynom) stejně náročné rozhodnout, zda v něm existuje Hamiltonovská cesta, jako to, že v něm existuje Hamiltonovská kružnice. Ukažte, že je stejně náročné (až na polynom) rozhodnout, zda existuje Hamiltonovská cesta, ve všech variantách v závislosti na tom, které koncové vrcholy cesty jsou zadány. Řešte pomocí transformací (tedy nikoli voláním druhého programu polynomiální počet krát). |
| Id studenta | celkem | rozpad bodů |
|---|---|---|
| h | 34 | interval(2), jehly(6), podposloupnost(6), věže(10), kluby(10), porovnání(0), souvislost(0), cesty(0) |
| l | 57 | interval(2), jehly(8/2), podposloupnost(4/2), věže(10/2), kluby(10), porovnání(10), souvislost(6), mult(8), cesty(10) |
| o | 53 | interval(5), jehly(6), podposloupnost(9), věže(10), kluby(10), porovnání(6), mult(7) |
| t | 10 | interval(2), jehly(6/2), podposloupnost(0/2), věže(10/2) |
| y | 14 | interval(4), jehly(6), podposloupnost(3), věže(1) |
| z | 18 | jehly(6), podposloupnost(4), věže(1), kluby(4/2), porovnání(5) |
| Á | 2 | jehly(4/2) |
| Č | 33 | podposloupnost(6), věže(10), kluby(10), mult(7), cesty(0) |
| A | 62 | interval(10), jehly(10), podposloupnost(6), věže(10), kluby(10), porovnání(10), mult(6) |
| B | 68 | interval(10), jehly(8), podposloupnost(10), věže(10), kluby(10), porovnání(10), souvislost(10) |
| C | 62 | interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(5), souvislost(8) |
| D | 67 | interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), souvislost(8) |
| E | 63 | interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), mult(4) |
| F | 66 | interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), porovnání(10), souvislost(10) |
| G | 60 | interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), souvislost(10), cesty(4) |
| H | 65 | interval(10), jehly(6), podposloupnost(9), věže(10), kluby(10), porovnání(10), souvislost(10) |
| I | 62.5 | interval(10), podposloupnost(10), věže(10), kluby(10), souvislost(5+5/2), cesty(10), porovnání(10/2) |
| J | 66 | interval(10), jehly(6), podposloupnost(10), věže(10), kluby(10), porovnání(10), souvislost(10) |
| K | 68.5 | interval(10), jehly(10), podposloupnost(9/2), věže(10), kluby(10), porovnání(5), souvislost(0), mult(9), cesty(10) |
| L | 62 | interval(6), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), souvislost(7) |
| M | 65 | interval(7), jehly(6), podposloupnost(6+2/2), věže(10), kluby(8), porovnání(2), souvislost(7), mult(8), cesty(10) |
| N | 63 | interval(7), jehly(6+4/2), podposloupnost(10), věže(0), kluby(10), porovnání(10), souvislost(10), mult(8) |
| O | 60 | interval(6+4/2), jehly(6+4/2), podposloupnost(6), věže(4+6/2), kluby(10), porovnání(0+10/2), souvislost(0+10/2), mult(5), cesty(4+6/2), Hamilton(2) |
| P | 60 | interval(10), jehly(10), podposloupnost(6), věže(10), kluby(10), porovnání(5), souvislost(9) |
| Q | 61.5 | interval(6), jehly(10), podposloupnost(4), věže(10), kluby(10), porovnání(5), souvislost(5+5/2), mult(9) |
| R | 67 | interval(10), jehly(10), podposloupnost(6+2/2), věže(10), kluby(10), porovnání(10), souvislost(10) |
| S | 69 | interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), souvislost(10) |
| T | 62.5 | interval(10), jehly(10), podposloupnost(9), kluby(10), věže(10), porovnání(10), mult(7/2) |
| U | 64 | interval(4), jehly(6), podposloupnost(9), věže(10), kluby(10), porovnání(5), souvislost(10), cesty(10) |
| V | 60.5 | interval(10), jehly(4+1/2), podposloupnost(9), věže(4), kluby(10), porovnání(5), souvislost(10), mult(8) |
| W | 60 | interval(8), jehly(6), podposloupnost(9), věže(5), kluby(10), porovnání(5), souvislost(8), mult(9) |
| X | 61 | interval(10), jehly(10), podposloupnost(6), věže(10/2), kluby(10), porovnání(10), souvislost(10) |
| Y | 69 | interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnávání(10), souvislost(10) |
| Z | 63 | interval(8), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), souvislost(6) |
| a | 60.5 | interval(8), jehly(6), podposloupnost(6+3/2), věže(10), kluby(10), porovnání(10), souvislost(9) |
| b | 64 | interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), cesty(10/2) |
| c | 69 | interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), souvislost(10) |
| d | 66.5 | interval(10), jehly(6), podposloupnost(3+7/2), věže(10), kluby(4+6/2), porovnání(10), souvislost(10), mult(7) |
| e | 69 | interval(10), jehly(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), souvislost(10) |
| f | 62 | interval(10), jehly(10), podposloupnost(6/2), věže(10), kluby(10), souvislost(9), cesty(10) |
| g | 65 | interval(6), jehly(10), podposloupnost(8/2), věže(10/2), kluby(10), porovnání(10), souvislost(10), cesty(10) |
| i | 63 | interval(2), jehly(6), podposloupnost(8), věže(10/2), kluby(10/2), porovnání(10), souvislost(10), mult(7), cesty(10) |
| j | 67 | interval(6), jehly(6), podposloupnost(6), věže(10), kluby(10), porovnání(10), souvislost(9), cesty(10) |
| k | 68 | interval(10), jehly(6), podposloupnost(9), věže(10), kluby(10), souvislost(4), mult(9), cesty(10) |
| m | 63.5 | interval(5+3/2), jehly(10), podposloupnost(4), věže(10), kluby(10), porovnání(6), souvislost(10), mult(7) |
| n | 64 | interval(5), jehly(10), podposloupnost(10), věže(10), kluby(10), porovnání(10), souvislost(4), cesty(10/2) |
| p | 67.5 | interval(5+5/2), jehly(6), podposloupnost(9), věže(10), kluby(10), souvislost(9), mult(6), cesty(10) |
| q | 61 | interval(8), jehly(10), podposloupnost(9), kluby(10), věže(10), porovnání(10), mult(4) |
| r | 64.5 | interval(8+2/2), jehly(6), podposloupnost(9+2/2), věže(10), kluby(10), porovnání(10), souvislost(10) |
| s | 60 | interval(10), podposloupnost(9), věže(10), kluby(10), porovnání(10), mult(5), cesty(6) |
| u | 64 | interval(6), jehly(6), podposloupnost(6), věže(10), kluby(10), porovnání(10), souvislost(6), cesty(10) |
| v | 69 | interval(10), jehly(4), podposloupnost(10/2), věže(10), kluby(10), porovnání(10), souvislost(10), cesty(10) |
| w | 60 | interval(4+6/2), jehly(4+6/2), podposloupnost(6), věže(1+9/2), kluby(5+5/2), porovnání(10), souvislost(10), mult(7), cesty(0) |
| x | 61 | interval(4), podposloupnost(8+2/2), kluby(4+6/2), porovnání(5), souvislost(10), mult(6), cesty(10), jehly(10/2), věže(10/2), hamilton(0) |
Odkazy na obdobné stránky
Cvičení či materiály k nim Jana Hrice, moje loňská cvičení.
Cvičení 1
Na všech proběhlých cvičeních jsme prodávali datové struktury. Vždy zazněly (kromě jiných) prioritní fronty, vyhledávací stromy, slovníky a struktura na spojování tříd ekvivalence. Vždy byly první prezentované vyhledávací stromy neprodejné, a bylo potřeba vylepšit reklamní kampaň. Vždy jsme řešili možnosti optimalizace vyhodnocování SQL dotazů.
Vždy jsme zmínili rozměry složitosti střední hodnota (průměrná přes pravděpodobnosti vstupu) (php attack problém), randomizovaná (průměr pro jeden vstup přes chování náhodného generátoru) a pro datové struktury i amortizovaná (umožňující spočítat celkový čas za průběh algoritmu, ač některá zavolání mohou mít výrazně větší čas než jiná).
Cvičení 2
Věnovali jsme se vyhledávání v textu. Nejprve jsme si chvíli povídali o vyhledávání na internetu, tedy jak velmi zhruba funguje příprava podkladů pro vyhledávání na internetu a jak zhruba může být dotaz vyhodnocován. Pak jsem zmínil možnost obráceného přístupu, tedy předzpracování sena, což umožňuje následné efektivní vyhledávání libovolných předem neznámých jehel (intelisense, na konci druhého cvičení jsme zmínili Suffix trees ... předzpracování se dá udělat v čase $O(n)$ a vyžaduje $O(n)$ prostoru (s multiplikativní konstantou řekněme 20)).
Nálsedně jsme se věnovali vyhledávání jehly(el) v seně metodou, kdy předzpracujeme jehlu(y).
Následně jsme Knut-Moris-Prat algoritmus víceméně odbyli, víc jsem se věnovali Aho-Corrasick algoritmus, jež je jeho zobecněním a zjednodušení datové struktury pro cestu místo stromu, kde stačí pole čísel je implementační detail. Věnovali jsme se tedy Aho-Corrasic algoritmu, a předvedli jsme si jej na příkladě. Na prvním cvičení jsme odbočili k datové struktuře (písmenkový strom) Trie a zařadili ji v kontextu tržnice datových struktur (paměťová hierarchie!). Řekli jsme si o možnosti reprezentace hran trie ve slovníku, ale i o tradičních metodách pole odkazů. Bavili jsme se o snížování prostorové náročnosti při reprezentaci statické množiny pomocí eliminace vrcholů stupně 1 i pomocí reprezentace ofsetů do jednoho pole s překrývajícími se intervaly hodnot (s nepřekrývajícími se nenilovými odkazy), nerozmysleli jsme si, jak musíme modifikovat vyhledávání, abychom se nezacyklili a lokalizovali jen slova z množiny.
U AC algoritmu jsme se nevěnovali důkazům, toho, že postupujeme správně, nicméně jsme všechny jednotlivé kroky zdůvodnili. Implicitně jsme dokázali složitost vyhledávání i složitost vybudování fail podpůrných pointerů. Co se týče hlášení nalezených jehel, využil jsem příležitost k odbočce k funkcionálně persistentní datové struktuře srůstajících seznamů. Zmínil jsem se o tom, co to je částečná a plná persistence, a zmínil využití částečné persistence v úloze lokalizace bodů v rovině (na druh0m cvičení).
Na obou cvičeních jsem zmínil algoritmus s plovoucí hašovací funkcí (Robin Karp), který umí s velikou pravděpodobností vyloučit pozice, kde se jehla určitě nenachází, s tím, že pozici, kde se jehla nachází nikdy nevyloučí. Existuje i xorovací, shiftovací hashovací funkce, jejíž výpočet i aktualizace bude mít lepší multiplikativní konstantu než standardní modulo polynomiální funkce, tuto funkci jsem ale zatloukal. (Pomocí "zobrist hashing" triku se každému písmenku přiřadí náhodné např. 128 bitové číslo, toto číslo se rotuje podle toho na které pozici se daný znak vyskytuje. Není to polynom o základu $2^k$, vyhledem k cyklickému doplnění bitů nízkých řádů a výsledný hash získáme xorem mezivýsledků. Posunutí slova se projeví rotací hashe celého slova, takže je akualizace v $O(1)$.)
Cvičení 3
Bavili jsme se o dvou algoritmech hledání toků v sítích (na obou cvičeních jsme stihli 4 varianty postupné maximalizace pomocí nějakých toků Ford Fulkerson, Edmonds Karp, Dinic, efektivní implementace Dinicova algoritmu), na prvním cvičení jsme stihli odkrokovat algoritmus vycházející z maxima a postupně zajišťující to, aby šlo o tok, nestihli jsme rozbor složitosti algoritmu. Na druhém cvičení jsme se k algoritmu vycházejícího z maxima a postupně zajišťujícího, že jde o tok, nedostali.
Cvičení 4
Nejprve jsme dokončili druhý algoritmus na hledání toku v síti (rozbor časové složitosti) a vylepšenou heuristiku a vylepšený rozbor složitosi.
Pak jsem se vrátil k Dinicově algoritmu a ukázal jsem jak pro husté vrstevnaté sítě hledat blokující tok efektivněji (v $O(n^2)$ místo $O(m\log n)$ ... algoritmus 3 indů). Ukázal jsem i slíbený příklad na kterém Ford Fulkerson může konvergovat k zanedbatelnému toku oproti tomu, jaký v síti existuje. (Vhodná volba zlepšujících cest kde zbytkové kapacity na dané trojici hran až na pořadí v $i$-tém kroku rovny $0,q^{i+1},q^i$, kde $q>0, 1=q+q^2$ ...).
V krátkém zbytku hodiny jsme začali řešit úlohy na toky v sítích (například na rovnost maximálního toku s minimálním řezem).
Cvičení 5
Páté cvičení mělo kvůli rektorskému dni jen pondělní verzi, na které jsme řešili úlohy na toky v sítích. Kromě svišťů otevírání dolů a dopředné krále.