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

English notes on Ukkonen's algorithm

MST: Vysvětlení \alpha(n)

Upřesnění analýzy víceúrovňových přihrádek

Planarita: Drobné chyby

Opraveno sesazování celé knihy

Poznámka o vlastnostech zobecněných maticových součtů

Floyd: Drobné korektury

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

Floyd: Drobné opravy

Planarita: Obrázky a korektury k novému důkazu

Planarita: Drobnosti

Planarita: Důkaz korektnosti je snad již korektní

TODO: Obrázky

Slidy k rovinnému kreslení mají i anglickou verzi

Intro: Oprava překlepu

TEXINPUTS pro hledání obrázků

Další zapomenuté \epsfbox-y

preprocess: novější Perl chce escapovat chlupaté závorky

Konverze obrázků: teď už je to opravdu PDF :)

Konverze obrázků: krok 2

Konverze obrázků: krok 1

Konverze všech obrázků z EPS do PDF

Dijkstra: Oprava scestného překódování

Randcut: Uvaha o smyckach

Floyd: Překlep

Díky, Anet!

Floyd: V zobecněném Floydovi-Warshallovi nezapomínejme na smyčky

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)