Koná se ve středu v 15:40 v S7. Kontaktovat mě je nejlepší emailem, i když ostatní formy komunikace jsou možné také. Pro komunikaci ohledně předmětu preferuji adresu ads2@vorner.cz, případné osobní zprávy raději na obecnou adresu vorner@vorner.cz.
Konzultace a rady poskytuji většinou po dohodě nebo po emailu. Jiné formy jsou možné též (např. přes SIP).
V případě potíží, žádostí o radu a podobně je třeba nebát se zeptat a hlavně to řešit včas.
K získání zápočtu je třeba splnit dvě podmínky. První z nich je odevzdat alespoň 4 domácí úkoly (samozřejmě tak, abych je uznal ‒ takže dostatečně správně). Domácí úkoly se zadávají na hodině a termín je vždy do začátku další hodiny. Odevzdávejte emailem, prosím.
Druhou podmínkou je zápočtová úloha. Ta sestává z popisu algoritmu, důkazu správnosti a odhadů složitostí. Nepovinnou, ale doporučovanou, součástí je i implementace algoritmu či datové struktury (neboť pomáhá v ujasnění si myšlenek a v objevování chyb).
Téma musí být dostatečně obtížné ‒ např. úlohy KSP s bodovým ohodnocením ≥10 bývají dostatečně obtížné (ty ale je případně potřeba vyřešit ještě před vydáním oficiálního řešení). Dále musí být téma unikátní v rámci cvičení (a kdo dřív přijde, ten bere). Doporučuji si téma rezervovat a domluvit se na něm emailem ‒ pokud přijde hotové řešení, nemám nic proti, ale nikdo neslibuje, že bude dostatečně obtížné či ještě volné.
Aktuálně rozebraná témata jsou:
Procvičovalo se hledání jehly v kupce sena (v řetězcovém pojetí).
Ukázali jsme si vyhledávání pomocí okénkové hashovací funkce. Také jsme si ukázali jak jednu takovou sestrojit ‒ zapsat řetězec jako číslo v soustavě o základu nějakého prvočísla nad nějakým konečným tělesem. Za domácí úkol je vymyslet funkci, která je založená na něčem od základu jiném. Netvrdím, že to jde, sám o ní nevím O:-).
Dnešními hlavními tématy byly hrátky s trií a s algoritmem Aho-Corasick.
Ukázali jsme si několik drobných úprav na různé problémy. Na konci jsme si, mimo jiné, také ukázali, jak to převést na konečný automat a že líná verze převodu vyjde s lepší složitostí (obecně, trocha lenosti datovým strukturám málo kdy vadí).
Proměnné a a b obsahují každá jeden libovolný znak, jsou však různé. Ta menší slova samozřejmě nenásobíme, ale řetězíme za sebe.
Chceme algoritmu, který v zadaném slově objeví nejdelší fibbonaciho slovo. Proměnné a a b si algoritmus volí sám tak, aby slovo vyšlo co nejdelší, ty nejsou zadané.
Po krátké rozcvičce na vyhledávání textu jsme přešli na toky v sítích.
Definovali jsme si, co je to síť, co je to tok a jak v ní nějaký najít pomocí Ford-Fulkersona. Chvíli jsme si s ním hráli a uvažovali, jak je to nepříjemné, že to nemusí skončit.
Nakonec jsme si ukázali vylepšení v podobě Dinitzeho algoritmu.
Představme si mapu. Máme v ní města a železnice mezi nimi. Každá železnice má kapacitu, kolik vagonů denně po ní lze přepravit.
Dále, v některých městech jsou fabriky, které všechny vyrábějí jeden druh zboží. Každá fabrika má maximální výkon, kolik vagonů tohoto zboží dokáže vyprodukovat za den.
V některých jiných městech jsou obchody, které tento druh zboží prodávají. Opět, každý obchod má omezenou kapacitu (např. pokladen), kolik vagonů zboží dokáže prodat za den.
Chceme umět spočítat, jaký je maximální teoretický denní obrat firmy, které jak obchody, tak fabriky patří (počítáno ve vagonech zboží na den) ‒ tedy kolik se toho dá vyrobit, dovézt po železnici a prodat.
Dále jsme procvičovali toky v sítích. Také jsme si ukázali další algoritmus, tentokrát Goldbergův. Důkazy k němu budou na příští přednášce.
Mějme binární číslo s N ciframi. Chceme jej postupně K-krát zvýšit o jedničku. Jedno zvýšení bude trvat nějakých O(N), ale takto drahá zvýšení se nedějí příliš často. Kolik bude trvat jedno zvýšení amortizovaně (jaksi „v průměru“)? Doporučuji najít vhodný potenciál (nějaká vždy nezáporná funkce, která popisuje stav toho čísla, něco, proti čemu půjdou drahé operace „naúčtovat“ a některé jiné levné operace je splatí).
Ještě jednou jsme si hráli s toky v sítích. Ukázali jsme si, jak pomocí nich spočítat k-souvislost grafu. Také jsme si hráli s důkazy goldbergova algoritmu a s potenciálovými odhady.
Udokazujte, jak rychlý bude goldbergův algoritmus na síti s jednotkovými kapacitami.
Po malé rozcvičce na toky (ze které se posléze stal domácí úkol, viz níže) jsme se pustili do fourierovy transformace.
Představme si, že jsme malá začínající firmička. Můžeme dělat libovolnou podmnožinu z projektů P₁…Pn, za každý dostaneme nějakou předem danou odměnu. Ale některé projekty potřebují nějaké vybavení, které nemáme. Každý kus vybavení něco stojí. Pokud ale již jeden druh máme, lze ho použít pro více než jeden projekt (je to spíš nářadí, než spotřební materiál).
Chceme vybrat množinu projektů, které uděláme, tak, aby byl výdělek co největší.
Po úložce na fourierku (která zbyla jako domácí úkol jsme se vrhli na hradla. Ukázali jsme si, co je to hradlová síť, jaké „složitosti“ nás u ní zajímají, a chvíli si hráli se stavěním některých jednoduchých hradlových sítí. Ukázali jsme si jak postavit XOR z NANDů a jak vyrábět vícenásobný OR.
Za úkol je napsat fourierku bez rekurze.
Dnes jsme si celou dobu hráli s hradly. Pro změnu jsme nekoukali na hradla počítající binární funkce, ale komparátory ‒ hradla, co umí porovnávat čísla a případně je prohazovat. Ukazovali jsme si několik sítí na drobné leč neužitečné činnosti (např. výběr maxima). Nakonec jsme si zopakovali algoritmus třídění z přednášky.
Dnešním úkolem je z binárních hradel poskládat násobičku n-bitových čísel. Ale s omezeným „rozpočtem“ ‒ je k dispozici jen O(log n) hladin a O(n²) hradel.
Stále jsme si hráli s hradly. Převáděli jsme sítě na booleovské formule a funkce a zpět. Také jsme zjednodušovali co šlo na hradla nad dvojkovou soustavou s jen 2 vstupy.
Představme si komparátor, který dostane dva číselné vstupy a vydá dva číselné výstupy. Na výstupu jsou stejná čísla, ale „setříděná“ ‒ na jednom výstupu je vždy to menší a na druhém větší.
Chceme implementovat komparátor pomocí binárních hradel nad dvojkovou soustavou. Tedy, vstupy budou reprezentované ne jedním drátem, ale každý n dráty (pro n-bitová čísla). Výstupy obdobně. Samozřejmě jsou k dispozici jen obvyklá hradla (AND, OR a podobně ‒ dva vstupy, jeden výstup).
Napřed jsme si ukázali domácí úkol (a pokreslili jeho výrobou celou tabuli). Tím jsme ukončili hraní s hradly.
Zbytek hodiny jsme probírali geometrické algoritmy. Na příkladu konvexního obalu jsme si ukazovali, jak zametat rovinu. Také jsme si ukázali ještě další algoritmus na konvexní obal a jak spočítat obsah mnohoúleníka.
Představme si, že máme hromadu osových obdélníků (takové, které jsou rovnoběžné s osami). Některé se překrývají, někde v tom jsou nepokryté díry, prostě jakkoliv nasypané na sebe. Úkolem je spočítat obsah plochy pokryté obdélníky ‒ avšak jako jejich sjednocení, pokud se dva obdélníky překrývají, pak ta společná část je počítána jen jednou, ne dvakrát.
Dnešní hodinu jsme si opět hráli s geometrií. Ukázali jsme si domácí úkol ‒ což obsahovalo i vysvětlení, co je to intervalový strom. Poté jsme počítali počet průsečíků množiny úseček a lokalizovali bod v rovině.
Mějme body dvou druhů, třeba červené a modré. A někdo již spočítal konvexní obal červených bodů a konvexní obal modrých bodů. Rádi bychom co nejrychleji spočítali „nediskriminovaný“ konvexní obal (obal všech bodů bez rozdílu barvy).
Na začátku jsme si ukázali, že domácí úkol je jen velmi jednoduchá variace na obvyklý algoritmus pro konvexní obal.
Poté jsme se podívali ještě malinko na geometrii, tentokrát v třech rozměrech. Z této části zbyl domácí úkol.
Ve zbytku hodiny jsme se podívali na převádění problémů jeden na druhý, na složitostní třídy a co to vlastně je to NP-úplné a podobně.
Podívejme se ještě jednou na úlohu o osových obdélnících. Tentokrát si ji ale podáme ve třech rozměrech. V zásadě potřebujeme nějaký rozumě rychlý ekvivalent intervalových stromů ve dvou rozměrech místo jednoho.
Pravděpodobně by mělo jít dosáhnout složitosti O(n·log²n). Pokud se mi to nepodaří vymyslet, tak se tu objeví náhradní domácí úkol.
Dnes jsme pokračovali v převodech a NP (úplnosti, těžkosti). Ukázali jsme si několik problémů, převedli je na něco jiného, či dokázali, že jsou v P.
V dnešní hodině zbyly tři domácí úkoly. Každý si tedy může jeden vybrat a ten splnit. Každý je jeden problém. Má se určit, jestli je NP/NP-úplný/NP-těžký/P/cokoliv takového a dokázat to.