Suffixove stromy: Opravena nesikovna formulace v definici back(v)

S diky Vlastovi Dortovi

Kostry: Opraven preklep v casove slozitosti Jarnikova algoritmu #3

S diky Vlastovi Dortovi

Floyd: Drobne korektury

- U metody Rozdel a panuj byla chybne uvedena 3 rekurzivni volani
  namisto 2.

- V predposlednim odstavci popisu Seidelova algoritmu se scitaji
  hodnoty D', nikoliv D.

S diky Vlastovi Dortovi.

Suffixove stromy: Oprava preklepu

S diky Davidovi Pegrimkovi za upozorneni.

Toky: "m" je rezervovano pro pocet hran

S diky Davidovi Pegrimkovi za upozorneni.

Upravy Makefiles na novou strukturu webovych stranek

Suffixove stromy: Lepsi vyklad Ukkonenova algoritmu

Planarita: Oprava preklepu v poznamce o DFS (stromove, ne dopredne)

Diky Davidovi Pegrimkovi za upozorneni.

Floyd: Oprava preklepu v indexech

Diky Vitovi Cizkovi za upozorneni.

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

Dijkstra: Oprava preklepu v nerovnosti

Diky Vitovi Cizkovi za upozorneni.

Floyd: V Seidelove algoritmu opraveno floor na ceil

Tim padem bylo nutne prohodit sudou a lichou variantu o kus nize.

Slidy k planarite: bugfix

Planarita: Slidy opraveny a prizpusobeny novym terminum

Planarita: Korektury a zmena terminologie

Jeste jedna zmena terminologie: zivost a externost povazujeme za dve
zcela nezavisle vlastnosti. Interni vrcholy jsou tedy vsechny, ktere
nejsou externi. Na tech nekolika mistech, kde je potreba zduraznit,
ze nas zajimaji ne-externi zive, rikame explicitne zive interni.

Argumenty zalozene na uctovani vrcholum, ktere zmizely z vnejsi steny,
nefunguji pro artikulace. Jednoduchym resenim je uctovat zmizelym hranam.

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

Planarita: Zmena terminologie

Interni/externi aktivita byla znacne matouci. Zacal jsem proto interne
aktivnim vrcholum rikat jen interni a externe aktivnim jen externi.
Z neaktivnich se staly pasivni. Jeste budu upravovat.

Sekce o minorove uzavrenych tridach prepsana

Uz vysvetluje, jak funguje odhad hustoty, jen chybi dukaz Maderovy vety.

Prepsana cast o Union-Find

Dukaz odhadu pres log* prepsan, uz je snad citelnejsi. Nepravdiva
poznamka o worst-case slozitosti nahrazena spravnym dolnim odhadem
vcetne odkazu.

Floyd: Oprava preklepiku

Dijkstra: Vylepseni dukazu BFM + odkazy na dalsi haldy

Dijkstra: Drobne opravy

Sazba: Hezci font pro \bb (blackboard bold)

Makefile: automaticky kompilujeme PDF, ne PS

Listecek s erraty vkladany do knizky.

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.