Sazba pdfTeXem

Překódování do UTF-8

Floyd: Chybejici carka

Priklady minorove uzavrenych trid: Forb(K_1) -> Forb(K_2)

Minorově uzavřené třídy: Typografický detail

Dijkstra: Oprava preklepu

Diky, Jethro.

Dekompozice: Oprava preklepu v analyze Union-Findu

Dijkstra: Oprava preklepu v HOT queues

Floyd: Zmineny pokroky v nasobeni matic

Floyd: Drobné opravy ohledně sledů délky 0

Karger-Stain: Dvě drobné chybky

Floyd: Oprava překlepu

Bipcon: Oprava překlepu

Úpravy uploadovací mašinerie

Od této chvíle jsou časy poslední úpravy kapitol udržovány automaticky.

Dekompozice: Pořádný popis Fredericksonovy clusterizace

Dijkstra: U celociselnych delek lepe popisujeme rozsah okna

Kostry: Opraven popisek obrazku s prikladem swapovani

Suffix: Oprava lemmatu o vnorenych suffixech

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

VEBT: k znaci pocet bitu, tedy log U, nikoliv log log U

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

Dijsktra: Delka hrany, nikoliv jeji kapacita

Toky: Kapacity jsou nezaporne, nikoli nutne kladne

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.