Vladan Majerech - NTIN061 Algoritmy a datové struktury II

Last Modified: 27.4.2021

Valid HTML 4.01 Strict

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, odevzdáváme v běžném čitelném formátu (např v těle mailu či v příloze .txt,.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ů.

KódBodyTermín odevzdáníZadání
podposloupnost10do 16.10.2020 10:40 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.
jehly10do 23.10.2020 10:40 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ášť.
věže a sloupy10do 30.10.2020 10:40 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).
kluby10do 6.11.2020 10:40 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.
cesty10do 18.11.2020 14:00 Pro dané vrcholy $u$, $v$ v orientovaném grafu nalezněte maximální počet vrcholově disjunktních cest z $u$ do $v$.
porovnání10do 25.11.2020 14:00 Vytvořte co nejmělčí hradlovou síť, která pro n-bitová čísla $a$, $b$ vydá $1$ právě když $a\le b$.
souvislost10do 9.12.2020 14:00 Vytvořte co nejmělčí hradlovou síť, která pro matici sousednosti neorientovaného grafu $G$ vydá true, právě, je-li graf $G$ souvislý.
Hamilton10do 16.12.2020 14:00 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.
3D věže a kaňky10do 8.1.2021 10:40 Máme prostorovou šachovnici $2\times k\times k$ a na některých políčkách jsou kaňky. Na políčka (bez kaněk) je možno umísťovat věže. Každá věž ohrožuje políčka jejichž dvě ze tří souřadnic jsou shodné s odpovídajícími souřadnicemi věže (bez ohledu na kaňky). Otázkou je, zda je možno rozmístit $2k$ věží tak, aby žádná nestála na políčku ohroženém jinou věží. No a na Vás je rozmyslet si, jak je taková otázka složitá.

Id studentacelkemrozpad bodů
I46podposloupnost(10), jehly(6), věže(10), kluby(10), cesty(10), Hamilton(0)
L35podposloupnost(10/2), jehly(10/2), věže(10/2), kluby(10/2), cesty(10/2), porovnání(10/2), souvislost(10/2)
A70podposloupnost(10), jehly(10), věže(10), kluby(10), cesty(10), porovnání(10), souvislost(10)
B55podposloupnost(10), jehly(0), věže(0), kluby(10), cesty(10), souvislost(10), Hamilton(10), porovnání(10/2)
C76podposloupnost(10), jehly(6), věže(10), kluby(10), cesty(10), porovnání(10), souvislost(10), Hamilton(10)
D64podposloupnost(10), jehly(10), věže(10), kluby(10), cesty(10), porovnání(10), souvislost(4)
E67podposloupnost(10), jehly(9), věže(10), kluby(10), cesty(10), souvislost(10), Hamilton(8)
F64podposloupnost(9), jehly(10), věže(10), kluby(10), cesty(10), porovnání(10/2), souvislost(10)
G64podposloupnost(10), jehly(10), věže(10), kluby(10), cesty(10), porovnání(10), souvislost(4)
H68podposloupnost(6), jehly(8), věže(10), kluby(10), cesty(10), porovnání(10), souvislost(10), Hamilton(4)
J77podposloupnost(7), jehly(10), věže(10), kluby(10), cesty(10), porovnání(10), souvislost(10), Hamilton(10)
K56podposloupnost(8/2), jehly(9), věže(10), kluby(10), cesty(10), porovnání(10), Hamilton(6/2)
M59podposloupnost(9), kluby(10), cesty(10), porovnání(10), souvislost(10), Hamilton(10)
O60jehly(10), věže(10), kluby(10), cesty(10), porovnání(10), souvislost(10), Hamilton(0)

Odkazy na obdobné stránky

Cvičení Jirky Švancary, Miloše Chromého, Michala Oplera, Jakuba Pekárka a rozcestník Jana Hrice, moje loňská cvičení.


Cvičení 1

Na cvičení jsme nejprve prodávali datové struktury (žádné detaily, pouze použití), při té příležitosti jsme si povídali o dimenzích složitosti očekávaná, randomizovaná a amortizovaná.

Pak jsme se zabývali hledáním textu v textu (jehly(jehel) v kupce sena). Snažil jsem se naznačit, že mnohdy bývá užitečnější si předzpracovat seno (google; sufixové stromy ... snad se to ani nedalo nazvat náznak). Trochu jsme si povídali o Knuth-Morris-Pratt algoritmu a k jeho zobecnění Aho-Corasick.

Nedělali jsme žádné důkazy koreknosti, jen jsme nakreslili automat a pověděli jsme si jak jej zkonstruujeme (včetně informace nutné pro hlášení jehel tvořících sufix aktuálně reprezentovaného slova). KMP stačí pole indexů, AC potřebuje obecnější odkazy, jinak je AC rozšířením KMP. Krátce jsme zdůvodnili lineární složitost vyhledávání.

Na konci jsem vzpomenul plovoucí hash algoritmus Rabin-Karp.

Na pátečním cvičení jsme dražili více datových struktur, ale k vyhledávání jehel v seně jsme se nedostali. Budeme se mu věnovat příště.


Cvičení 2

Na pátečním cvičení jsme se věnovali KMP a AC algoritmům a dále jako na středečním cvičení. Na středečním cvičení jsme se co se týče vyhledávání jehly v kupce sena věnovali už jen algoritmu s plovoucí hash funkcí. Pak jsme se věnovali formalizacím souvisejícím s dynamickým programováním resp. určováním dolních odhadů. Věnovali jsme se explicitnímu řešení úlohy s idealizovanými vajíčky a mrakodrapem, odhadování hloubky AVL či RB stromů, trochu povídání o hledání analytického popisu řešení lineárních rekurencí a toho jak efektivně vyhodnotit člen takové posloupnosti s velkým indexem (souvislost s vlastními čísly jsem zatajil).


Cvičení 3

Povídali jsme si o tocích v sítích, řešili jsme více zdrojů a stoků, popsali jsme dva hlavní přístupy (zvětšujeme po tocích až eventuálně nalezneme maximum/začneme z maxima a zajistíme, aby šlo o tok).

Prvnímu přístupu (Ford Fulkerson jsme se věnovali). Prošli jsme si případ iracionálních kapacit, kde nekonverguje k optimálnímu toku, ukázali jsme si, že na racionálních kapacitách pomalu ale jistě problém vyřeší. Ukázali jsme si příklad grafu, kde maximálního giganického toku dosáhneme postupným zvětšováním o 1. Řešili jsme heuristiky, jak lépe zvolit nejkratší cestu a nenalezli jsem síť pro níž zlepšování po co největších skocích nefunguje efektivně, každopádně odhad doby výpočtu stále závisí na kapacitách.

Heuristika zlepšujících cest s nejmenším počtem hran (Edmons Karp) vedla k odhadu složitosti $O(m^2n)$ nezávisle na kapacitách hran. Optimalizace algoritmu pro tuto heuristiku ignoruje hrany nenacházející se na nejkratších cestách, dokud se nezmění délka nejkratší cesty. Aktualizujeme tedy o „blokující tok ve vrstevnaté síti“, což je nazáváno Dinitzův algoritmus $O(mn^2)$. Implementace pomocí pokročilých datových struktur vede pak na $O(mn\log n)$. Je znám algoritmus s asymptotickou složitostí $O(mn)$ s multiplikativními konstantami, které ho pro běžné velikosti grafů činí nepoužitelným.

Ke konci hodiny jsme si hráli s maximálním párováním. Nejprve na bipartitním grafu, pak jsme zmínili existenci algoritmu na nebipartitním grafu.


Cvičení 4

Dále jsme se bavili o tocích v sítích, nejprve jsme zkoušeli pár aplikací (hledání permutace omezené znalostí minim a maxim v některých intervalech převodem přes perfektní párování na toky, hledání co nejvíce hranově disjunktních cest mezi danou dvojicí vrcholů (je potřeba odstranit „víry“, varianta úlohy s věžema).

Pak jsem naznačil hledání toku pomocí škálování celočíselných kapacit (nehledáme tok v původní síti, ale v síti s menšími kapacitami (s větší granularitou), zlepšující toky nepostupují po jedničkách, ale po granularitě. Celkový čas algoritmu pak závisí kromě na $m$ a $n$ i na počtu bitů hrany s největší kapacitou.

Ve zbytku hodiny jsme se věnovali Preflow-push algoritmu. Našli jsme vhodný potenciál omezující počet celkově vykonaných nesaturovaných push (na základě znalosti horního odhadu počtu up a saturovaných push). U druké skupiny jsme stihli vyslovit i heuristiku vedoucí k rozdělení popisu algoritmu do fází podle výšky nejvyššího vrcholu, nenašli jsme ale ještě potenciál na základě něhož by bylo jasné, jak to pomohlo.


Cvičení 5

Dovymysleli jsme potenciál klesající za nesaturovaný push v dlouhé fázi o $K$ a rostoucí dohromady o $mn^2$, čímž jsme dostali celkovou složitost algoritmu $O(n^2(m/K+K))$ s optimální volbou $K=\sqrt{m}$. Pak jsme si hráli s těžkými úohami na minimální řez. (Doly a továrny, minimální izolace toxických krychliček).


Cvičení 6

Na pátečním cvičení jsme si trošku povídali o poupátkovém algoritmu a víc o haldách. Na potenciály už jsme si zvykli, takže nám nedělaly nepřekonatelný problém.

Na středečním cvičení jsme se věnovali hradlovým sítím (o snižování přirozené hloubky na (dvakrát) logaritmickou pomocí skládání funkcí) a o třídících sítích založených na bitonickém a merge třídění.


Cvičení 7

Na pátečním cvičení jsme se věnovali hradlovým sítím (o snižování přirozené hloubky na (dvakrát) logaritmickou pomocí skládání funkcí) a o třídících sítích založených na bitonickém a merge třídění.

Na středečním cvičení jsme dokončili merge slévací obvod a pak jsme si povídali o haldách. Na potenciály už jsme si zvykli, takže nám nedělaly nepřekonatelný problém.


Cvičení 8

Na pátečním cvičení jsme dokončili merge slévací obvod a pak se věnovali Diskrétní Fourierově transformaci. Začali jsme motivací s násobením čísel, kde jsme konvoluci(součin) polynomů počítali modulo vhodné prvočíslo (čímž jsme extrémně snížili výpočetní nároky). Ukázali jsme si že paralelní dosazení odpovídá násobení maticí a při vhodné volbě bodů má matice velice mnoho symetrií umožňující masivní sdílení mezivýsledků, vedoucí k celkovému času dosazení pouze $O(n\log n)$ aritmetických operací (v aritmetice mod P). Zároveň nám maticový zápis poskytl jednoduché zdůvodnění proč k inverzní transformaci stačí násobit inverzní maticí. Zároveň je inverzní matice velice podobná té původní, takže i inverzní transformace funguje v $O(n\log n)$. Na pronásobení $n$ ciferných čísel v čase $O(n\log n)$ (resp. krát $O(\log^2\log n)$ na aritmetické operace) nám tedy stačí umět v nejvýš stejném čase dopočítat přenosy mezi řády. To ale nebude problém.

Po skončení hodiny (nevšiml jsem si) jsme ještě řešili vztah k spojité Fourierově transformaci, kde místo sčítání integrujeme a zvolená komplexní jednotka určuje rychlost s níž rotujeme šroubovnicí původně reálné funkce (Osciloskop). Těžiště projekce u periodické funkce bývá v 0, pokud se netrefíme do násobku periody. Při trefě do násobku periody těžiště do nuly padnout nemusí. Což bývá používáno k detekci významných frekvencí u skoro periodických funkcí. Diskrétní Fourierova transformace v komplexních číslech je aproximací tohoto spojitého výpočtu. Předpokládá dostatečně dlouhý vzorek hodnot funkce (tak aby skok na kraji intervalu neměl moc velký vliv na celkovou chybu). Jednotlivé řádky transformace odpovídají rostoucím rychlostem rotace šroubovnice (opět vzorkovaně).


Cvičení 9

Hráli jsme si především s (rychlou) diskrétní Fourierovou transformací. Koukám, že mne státní svátek natolik vyhodil z rytmu zadávání domácích úkolů, že jsme výrazně off-topic.


Cvičení 10

Povídali jsme si o složitosti, těžkosti a úplnosti, především co se týče NP. Ukázali jsme (na prvním cvičení), že splnitelnost formule je lehká při délce klauzulí nejvýš 2, ale těžká, když omezení na délku nejdelší klauzule zvýšíme aspoň na 3. Příště snad stihneme více transformací. Na druhém cvičení jsme si s variantami SAT nehráli, ukázali jsme ale, že barvení grafu třemi barvami i hledání Hamiltonovské kružnice v grafu s malými stupni vrcholů je NP úplné.


Cvičení 11

Na pátečním cvičení jsme ukázali převody ze SAT na barvení, HK(Plesník) a nezávislou množinu předepsané velikosti, na konci jsme ještě stihli převod z nezávislé množiny na Batoh.

Na středečním cvičení jsme si hráli se SAT (délky klauzulí, počty proměnných), kromě toho jsme si hráli s 1 in 3 SAT. Nehráli jsme si s nezávislou množinou a batohem.


Cvičení 12

Na pátečním cvičení jsme si hráli s 1 in 3 SAT a pak jsme se věnovali aproximacím (VP, OC, Batoh).

Na posledním středečním cvičení jsme dokázali NP-úplnost nezávislé množiny a batohu a věnovali se aproximacím VP a OC. Na aproximaci batohu se nedostalo.


Cvičení 13

Do pátečního rozvruh se vešlo ještě 13. cvičení. Zabývali jsme se v něm RSA (konstrukce klíčů, problému efektivního překladu z abecedy o $2^k$ znacích do abecedy o $M$ znacích jsme se nevěnovali) a otázkou složitosti faktorizace čísel. Naznačil jsem Lenstra elliptic curve metodu a kvadratické síto, upozornil jsem na existenci number field sieve. Snapshoty jsou ve sdíleném google doc dokumentu včetně snadno dohledatelného odkazu na numberfield sieve.