APSP: Oprava chyby v metode Rozdel a panuj

all.pdf uz obsahuje i nove pripsane kapitoly

SSSP: Kapitola prejmenovana na "Nejkratsi cesty"

APSP: Kapitola prejmenovana na "Transitivni uzavery", prepsan uvod

APSP: Jeste par drobnych uprav

APSP: Korektury a odkazy na literaturu

APSP: Metoda Rozdel a panuj

Tim by kapitola mela byt hotova, tedy az na korektury.

APSP: Seideluv algoritmus

APSP: Prepsana cast o regularnich vyrazech a nasobeni matic

Nyni je snad znaceni o neco prehlednejsi.

APSP: Zminka o efektivnejsich algoritmech na (min,+)-souciny

APSP: Doplneno povidani o (zobecnenem) nasobeni matic

Nova kapitola o APSP: Floyd-Warshall a regularni vyrazy

Planarita: Par slidu k prednasce

Cesty: Oprava preklepu

Cesty: Prvni kolo korektur

Haldove operaci pro mazani minima rikejme ExtractMin, ne DeleteMin

ExtractMin je zabehnutejsi nazev a take o neco logictejsi, protoze
naznacuje, ze minimum nejen mazeme, ale take ho pri tom zjistime.

Makefile: Changelog zrusen, misto nej pouzijeme Gitweb

Knizka: Sazba pracovni verze

Na titulni strane upozornujeme, ze se jedna o pracovni verzi.
Rok se doplnuje automaticky podle \the\year.

Kazda kapitola nyni zacina na samostatne strane, aby se sazba
nerozjizdela oproti samostatne stazitelnym kapitolam. Az budeme
jednou sazet dalsi papirove vydani, mozna opet vratim do puvodni
uspornejsi podoby.

Dinic: Drobne upravy sazby, aby se text neroztahoval kvuli obrazkum

Makefile: Opraveno volani Gitu (git log je uz potreba psat zvlast)

Uklid v Makefilech (uz negenerujeme PDFka 2 stranky na 1)

Makra: Kazda stranka ma v paticce cislo verze

Karger-Stein: Opravy drobnych preklepu

Cesty: Algoritmy pro PPSP (obousmerny Dijkstra, A*)

Cesty: Dinicuv algoritmus, potencialy, par odkazu na literaturu

Cesty: HOT Queue (opravena oproti clanku)

Cesty: par prihradkovych datovych struktur, jeste nedopsanych

Prvni cast nove kapitoly o nejkratsich cestach

Kostry: Oprava preklepu v Lemmatu o swapovani

Jeste jedna drobna oprava Kargera-Steina.

Rezy: Opraven odhad casove slozitosti Kargerova-Steinova algoritmu.

Uprava Makefiles, aby uploadovaly PDF misto PostScriptu.

Soucasna verze uz moc neodpovida tistene, takze upravuji titulni stranu a tiraz,
aby to bylo poznat.

Korektury.

Nove pravidlo na tvoreni PDF.

Pridana nova kapitola o randomizovanem hledani minimalniho rezu.

Merge branch 'master' of git+ssh://git.ucw.cz/home/mj/GIT/ga

Opraven preklep v citaci Hopcrofta-Karpa.

Suffixove stromy: drobny uklid v dnesnich zmenach rekurzivniho algoritmu.

"Dalsi vysledky" o kostrach: Lepe vysvetlen randomizovany alg.

Take opraven preklep.

Ukkonenuv algoritmus: Zminena reprezentace referencnich paru pomoci indexu.

Q-haldy: Insert jeste musi aktualizovat C v prvcich ukazujicich
na mista v B, ktera se posunula.

Q-haldy: Jeste jedna zmena formatu vektoru.

Q-haldy: Vektory maji (log k)-bitove polozky misto (log r)-bitovych.

Tim padem nemusime pri zmene "r" menit format vektoru.

Q-haldy: Vysvetleni u kodovani tvaru stromu bylo spatne.

k*log w nemusi byt obecne O(k^2).

Q-haldy: Jeste jedna oprava indexu v Pozorovani o tvaru trie.

Q-haldy: V Pozorovani o tvaru trie je max. index r, nikoliv n.

Kosmeticke zmeny.

Operace Unpack: radeji Cmp s vektorem samych nul, neni treba negovat.

Kostra pro setridene hrany: Precislovavame na 1...m (preklep).

Fredmanuv-Tarjanuv algoritmus: V analyze pocitame za incidentni i vnitrni
hrany, jinak bychom museli slozite osetrovat, ze mohou pri spojeni podkoster
vypanout.

Jarnikuv algoritmus s Fib. haldou: pilujeme formulace.

Minimalni rez: Opraven preklep v dukazu lemmatu o legalnim usporadani.

Taktez lehce vylepsena formulace na zacatku dukazu.

Algoritmus Tri Indu: Oprava preklepu v 10. kroku (s -> t).

Prepsan algoritmus pro rekurzivni konstrukci suffixovych stromu.

V popisu algoritmu bylo nekolik chyb a byl zbytecne slozity. Nahradil
jsem ho tedy jednodussi variantou a chyby snad vymytil. Mimo to jsem
zmenil znaceni x[i] tak, ze se pozice ve slove cisluji od nuly, a x[i:j]
tak, ze j-ty znak jiz do podslova nepatri. Tak zustanou zachovany vsechny
pekne vlastnosti puvodniho znaceni a zmizi problemy s definici slov
na trojicich znaku v rekurzivnim algoritmu.

Kosmetika: Scaling -> skalovani.

Kosmetika: Ford-Fulkersonuv -> Forduv-Fulkersonuv

Toky: Kosmeticke upravy.

Prepsan popis algoritmu pro maximalni parovani v regularnich bip. grafech.

Ted by mel byt srozumitelnejsi; navic jsem prejmenoval Degree Split
na lepe znejici stepeni grafu.

Dinicuv algoritmus: Oprava preklepu.

Merge with git+ssh://git.ucw.cz/home/mj/GIT/ga.git

Opravena chyba v pseudokodu Ukkonenova algoritmu (podminka v bodech 10
a 15 byla prohozena). Diky Martinovi Kupcovi a Milanovi Strakovi za upozorneni.

Opraven preklep v dukazu lemmatu o monotonnim swapovani.

Opraven preklep ve jmene pana Kirchhoffa.

Upraveny uploadovaci skriptiky, aby generovaly changelog od tistene verze.

Opravena formulace algoritmu pro maximalni parovani v regularnich bipartitnich
grafech. Degree Split je nyni definovan nejen pro regularni grafy, ale obecne
pro grafy se vsemi stupni sudymi, predtim se nedal primo pouzit ve splitu
s nasobnostmi. Sudost poctu hran, ktera je pro split potreba, nyni rozebirame
dukladneji, a $n$ definujeme jako velikost partity, nikoliv celeho grafu,
cimz se zbavime +/-1 problemu v odhadech.

U Nagamochiho-Ibarakiho uvadime, ze funguje pro multigrafy.

Mimo to par drobnych typografickych vylepseni a carek ve vetach.

Do balicku jsem pridal mjmac.tex, ktery tam omylem chybel.

Na titulni stranu pribyl obrazek, diky, Kubo!

ISBN ma nyni spravnou polohu na strance.

Drobne upravy sazby.

Hura, mame ISBN! :)

Drobne upravy sazby.

Finalni strankovy zlom, titulni strana, obsah a tiraz.

Pribylo jedno snadne cviceni.

Upravy pro finalni sazbu.

Odstranen obrazek radixsortu -- neni dulezity a rozbijel strankovy zlom.

Snad uz finalni verze uvodu, jen drobne upravy.

Alespon hruby odhad na Union-Find.

Pridana zminka o stridavych cestach a Hopcroft-Tarjanove algoritmu.

Ohodnoceni hran by pri hledani rezu mela byt nezaporna.

Opraveno jmeno pani Corasickove a pridan odkaz na jeji clanek.

Pripsan algoritmus tri Indu. Bohuzel se tim dost rozpadla sazba, ale to brzy napravime.

Opraveno par preklepu a formulacnich nepresnosti.

Degree Split vyzaduje, aby graf mel sudy pocet hran, coz samozrejme
regularni bipartitni grafy splnuji.

Oprava preklepu.

Sjednoceni znaceni kapacit mezi kapitolami 3 a 4.

Sjednoceni jmena U-F problemu.

Drobne opravy okolo DFS a artikulaci.

Drobne opravy a vylepseni formulaci.

Opravena chybka v obrazku.

Toky: oprava preklepu v definici.

Cleanup.

Drobne upravy sazby, sikovnejsi makro na zasazeni obrazku do odstavce.

Hezci obrazky k suffixovym stromum.

Hezci obrazek rezu.

Brouseni, lesteni a zametani kapitoly o dekompozicich.

ChangeLog jiz neobsauje diffstat od kopirovani souboru.

Kapitoly 9 a 10 prohozeny, protoze na sobe zavisi.

Sazba: mezera mezi nadpisem a carou nesmi byt pruzna.

Opravena chyba v mikro/makro-dekompozici stromu: cestovou kompresi musime
provadet na kazdem podstromu zvlast, nestaci ji provest na vstupni strom.
Take uz se objevil obrazek s priklady dekompozic, ze ktereho je videt,
proc je to potreba.

Bibliografie: typo.

Kresleni do roviny: drobne upravy a opravy preklepu.