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.

Dekompozice: styl a poznamka o uziti naseho specialniho pripadu Union-Findu.

Suffixove stromy: stylistika a odkaz na clanek o BWT.

Q-Heapy: pacifikace slohu a sazby.

Kapitola o RAMech: stylisticke ladeni a odkazy na literaturu.

Boruvkuv a Jarnikuv algoritmus: stylisticke korektury a odkazy na literaturu.

Minimalni kostry: drobne stylisticke upravy.

Byl jsem tady. Ispell.

Stylisticka revize kapitoly o GHT.

Drobne stylisticke zmeny a lepsi rozbor casove slozitosti prihradkove
struktury.

Doladeno povidani o scalingu a prehled variant Dinicova algoritmu.
Tim by az na obrazky mely byt kapitoly o tocich hotove.

Revize analyzy Dinicova algoritmu a obrazku okolo.

Revize prvni pulky Dinicova algoritmu. Jen kosmeticke zmeny.

Par poznamek v uvodu.

Odstraneni mrtveho kodu.

Doplnen dukaz Koenigovy vety a rozsiren uvodni odstavec.

Korektury a novy obrazek. Kapitolu o parovanich jsem presunul az na konec,
protoze v ni budou potreba rezy, ale jeste na jeji zmeny nedoslo.

Nove obrazky do kapitoly o kostrach a spousta kosmetickych vylepseni tamtez.

Pridany dva obrazky. Druhy mi vrr pri saveovani znicilo, takze od nej
existuje jen EPS.

Na web generuje 2in1 cele knizky, ne booklet.

Nove soubory na web.

Rozdeleni obrazku na dva.

Presli jsme na stranky formatu A5. K tomu se poji spousta drobnych
zmen v umisteni obrazku do textu.