]>
mj.ucw.cz Git - ga.git/log
Martin Mares [Wed, 9 Jan 2013 00:16:32 +0000 (01:16 +0100)]
Suffixove stromy: Lepsi vyklad Ukkonenova algoritmu
Martin Mares [Sat, 5 Jan 2013 20:11:39 +0000 (21:11 +0100)]
Planarita: Oprava preklepu v poznamce o DFS (stromove, ne dopredne)
Diky Davidovi Pegrimkovi za upozorneni.
Martin Mares [Tue, 31 Jan 2012 08:57:53 +0000 (09:57 +0100)]
Floyd: Oprava preklepu v indexech
Diky Vitovi Cizkovi za upozorneni.
Martin Mares [Tue, 31 Jan 2012 08:57:27 +0000 (09:57 +0100)]
Merge branch 'master' of git+ssh://git.ucw.cz/home/mj/GIT/ga
Martin Mares [Tue, 31 Jan 2012 08:57:03 +0000 (09:57 +0100)]
Dijkstra: Oprava preklepu v nerovnosti
Diky Vitovi Cizkovi za upozorneni.
Martin Mares [Wed, 18 Jan 2012 14:41:28 +0000 (15:41 +0100)]
Floyd: V Seidelove algoritmu opraveno floor na ceil
Tim padem bylo nutne prohodit sudou a lichou variantu o kus nize.
Martin Mares [Tue, 10 Jan 2012 21:46:04 +0000 (22:46 +0100)]
Slidy k planarite: bugfix
Martin Mares [Tue, 3 Jan 2012 21:44:50 +0000 (22:44 +0100)]
Planarita: Slidy opraveny a prizpusobeny novym terminum
Martin Mares [Tue, 3 Jan 2012 21:40:59 +0000 (22:40 +0100)]
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.
Martin Mares [Tue, 3 Jan 2012 19:57:28 +0000 (20:57 +0100)]
Merge branch 'master' of git+ssh://git.ucw.cz/home/mj/GIT/ga
Martin Mares [Tue, 3 Jan 2012 19:56:41 +0000 (20:56 +0100)]
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.
Martin Mares [Tue, 3 Jan 2012 17:00:43 +0000 (18:00 +0100)]
Sekce o minorove uzavrenych tridach prepsana
Uz vysvetluje, jak funguje odhad hustoty, jen chybi dukaz Maderovy vety.
Martin Mares [Tue, 6 Dec 2011 22:28:35 +0000 (23:28 +0100)]
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.
Martin Mares [Mon, 21 Nov 2011 10:19:36 +0000 (11:19 +0100)]
Floyd: Oprava preklepiku
Martin Mares [Wed, 26 Oct 2011 20:08:51 +0000 (22:08 +0200)]
Dijkstra: Vylepseni dukazu BFM + odkazy na dalsi haldy
Martin Mares [Wed, 26 Oct 2011 17:43:55 +0000 (19:43 +0200)]
Dijkstra: Drobne opravy
Martin Mares [Wed, 26 Oct 2011 17:41:04 +0000 (19:41 +0200)]
Sazba: Hezci font pro \bb (blackboard bold)
Martin Mares [Wed, 26 Oct 2011 17:40:51 +0000 (19:40 +0200)]
Makefile: automaticky kompilujeme PDF, ne PS
Martin Mares [Fri, 9 Sep 2011 16:01:58 +0000 (18:01 +0200)]
Listecek s erraty vkladany do knizky.
Tomáš Kuča [Wed, 16 Feb 2011 09:47:19 +0000 (10:47 +0100)]
APSP: Oprava chyby v metode Rozdel a panuj
Martin Mares [Fri, 11 Feb 2011 14:26:35 +0000 (15:26 +0100)]
all.pdf uz obsahuje i nove pripsane kapitoly
Martin Mares [Sun, 30 Jan 2011 22:35:56 +0000 (23:35 +0100)]
SSSP: Kapitola prejmenovana na "Nejkratsi cesty"
Martin Mares [Sun, 30 Jan 2011 22:35:42 +0000 (23:35 +0100)]
APSP: Kapitola prejmenovana na "Transitivni uzavery", prepsan uvod
Martin Mares [Sun, 30 Jan 2011 22:26:07 +0000 (23:26 +0100)]
APSP: Jeste par drobnych uprav
Martin Mares [Sun, 30 Jan 2011 22:20:17 +0000 (23:20 +0100)]
APSP: Korektury a odkazy na literaturu
Martin Mares [Sun, 30 Jan 2011 21:08:52 +0000 (22:08 +0100)]
APSP: Metoda Rozdel a panuj
Tim by kapitola mela byt hotova, tedy az na korektury.
Martin Mares [Fri, 28 Jan 2011 00:04:58 +0000 (01:04 +0100)]
APSP: Seideluv algoritmus
Martin Mares [Thu, 27 Jan 2011 23:33:20 +0000 (00:33 +0100)]
APSP: Prepsana cast o regularnich vyrazech a nasobeni matic
Nyni je snad znaceni o neco prehlednejsi.
Martin Mares [Thu, 20 Jan 2011 23:16:36 +0000 (00:16 +0100)]
APSP: Zminka o efektivnejsich algoritmech na (min,+)-souciny
Martin Mares [Thu, 20 Jan 2011 17:24:54 +0000 (18:24 +0100)]
APSP: Doplneno povidani o (zobecnenem) nasobeni matic
Martin Mares [Sun, 16 Jan 2011 21:45:17 +0000 (22:45 +0100)]
Nova kapitola o APSP: Floyd-Warshall a regularni vyrazy
Martin Mares [Tue, 11 Jan 2011 11:49:31 +0000 (12:49 +0100)]
Planarita: Par slidu k prednasce
Martin Mares [Tue, 2 Nov 2010 10:13:04 +0000 (11:13 +0100)]
Cesty: Oprava preklepu
Martin Mares [Mon, 1 Nov 2010 20:36:59 +0000 (21:36 +0100)]
Cesty: Prvni kolo korektur
Martin Mares [Mon, 1 Nov 2010 20:15:32 +0000 (21:15 +0100)]
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.
Martin Mares [Tue, 26 Oct 2010 20:13:36 +0000 (22:13 +0200)]
Makefile: Changelog zrusen, misto nej pouzijeme Gitweb
Martin Mares [Tue, 26 Oct 2010 20:08:29 +0000 (22:08 +0200)]
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.
Martin Mares [Tue, 26 Oct 2010 20:07:42 +0000 (22:07 +0200)]
Dinic: Drobne upravy sazby, aby se text neroztahoval kvuli obrazkum
Martin Mares [Tue, 26 Oct 2010 19:58:27 +0000 (21:58 +0200)]
Makefile: Opraveno volani Gitu (git log je uz potreba psat zvlast)
Martin Mares [Tue, 26 Oct 2010 19:51:25 +0000 (21:51 +0200)]
Uklid v Makefilech (uz negenerujeme PDFka 2 stranky na 1)
Martin Mares [Tue, 26 Oct 2010 19:51:05 +0000 (21:51 +0200)]
Makra: Kazda stranka ma v paticce cislo verze
Martin Mares [Tue, 26 Oct 2010 19:44:56 +0000 (21:44 +0200)]
Karger-Stein: Opravy drobnych preklepu
Martin Mares [Sun, 17 Oct 2010 11:31:46 +0000 (13:31 +0200)]
Cesty: Algoritmy pro PPSP (obousmerny Dijkstra, A*)
Martin Mares [Sat, 16 Oct 2010 21:16:12 +0000 (23:16 +0200)]
Cesty: Dinicuv algoritmus, potencialy, par odkazu na literaturu
Martin Mares [Sat, 16 Oct 2010 19:47:03 +0000 (21:47 +0200)]
Cesty: HOT Queue (opravena oproti clanku)
Martin Mares [Sat, 16 Oct 2010 16:46:03 +0000 (18:46 +0200)]
Cesty: par prihradkovych datovych struktur, jeste nedopsanych
Martin Mares [Sat, 16 Oct 2010 15:05:27 +0000 (17:05 +0200)]
Prvni cast nove kapitoly o nejkratsich cestach
Martin Mares [Mon, 12 Jul 2010 11:27:13 +0000 (13:27 +0200)]
Kostry: Oprava preklepu v Lemmatu o swapovani
Martin Mares [Tue, 3 Nov 2009 18:15:13 +0000 (19:15 +0100)]
Jeste jedna drobna oprava Kargera-Steina.
Martin Mares [Mon, 2 Nov 2009 09:01:07 +0000 (10:01 +0100)]
Rezy: Opraven odhad casove slozitosti Kargerova-Steinova algoritmu.
Martin Mares [Sun, 25 Oct 2009 21:48:23 +0000 (22:48 +0100)]
Uprava Makefiles, aby uploadovaly PDF misto PostScriptu.
Martin Mares [Sun, 25 Oct 2009 21:47:52 +0000 (22:47 +0100)]
Soucasna verze uz moc neodpovida tistene, takze upravuji titulni stranu a tiraz,
aby to bylo poznat.
Martin Mares [Sun, 25 Oct 2009 17:17:33 +0000 (18:17 +0100)]
Korektury.
Martin Mares [Sun, 25 Oct 2009 16:43:37 +0000 (17:43 +0100)]
Nove pravidlo na tvoreni PDF.
Martin Mares [Sun, 25 Oct 2009 16:40:56 +0000 (17:40 +0100)]
Pridana nova kapitola o randomizovanem hledani minimalniho rezu.
Martin Mares [Tue, 13 Oct 2009 13:06:32 +0000 (15:06 +0200)]
Merge branch 'master' of git+ssh://git.ucw.cz/home/mj/GIT/ga
Martin Mares [Tue, 13 Oct 2009 13:06:16 +0000 (15:06 +0200)]
Opraven preklep v citaci Hopcrofta-Karpa.
Martin Mares [Mon, 12 Jan 2009 21:02:24 +0000 (22:02 +0100)]
Suffixove stromy: drobny uklid v dnesnich zmenach rekurzivniho algoritmu.
Martin Mares [Mon, 12 Jan 2009 20:53:05 +0000 (21:53 +0100)]
"Dalsi vysledky" o kostrach: Lepe vysvetlen randomizovany alg.
Take opraven preklep.
Martin Mares [Mon, 12 Jan 2009 20:46:33 +0000 (21:46 +0100)]
Ukkonenuv algoritmus: Zminena reprezentace referencnich paru pomoci indexu.
Martin Mares [Mon, 12 Jan 2009 20:44:24 +0000 (21:44 +0100)]
Q-haldy: Insert jeste musi aktualizovat C v prvcich ukazujicich
na mista v B, ktera se posunula.
Martin Mares [Mon, 12 Jan 2009 20:43:52 +0000 (21:43 +0100)]
Q-haldy: Jeste jedna zmena formatu vektoru.
Martin Mares [Mon, 12 Jan 2009 20:41:46 +0000 (21:41 +0100)]
Q-haldy: Vektory maji (log k)-bitove polozky misto (log r)-bitovych.
Tim padem nemusime pri zmene "r" menit format vektoru.
Martin Mares [Mon, 12 Jan 2009 20:39:47 +0000 (21:39 +0100)]
Q-haldy: Vysvetleni u kodovani tvaru stromu bylo spatne.
k*log w nemusi byt obecne O(k^2).
Martin Mares [Mon, 12 Jan 2009 20:32:35 +0000 (21:32 +0100)]
Q-haldy: Jeste jedna oprava indexu v Pozorovani o tvaru trie.
Martin Mares [Mon, 12 Jan 2009 20:29:54 +0000 (21:29 +0100)]
Q-haldy: V Pozorovani o tvaru trie je max. index r, nikoliv n.
Martin Mares [Mon, 12 Jan 2009 20:26:21 +0000 (21:26 +0100)]
Kosmeticke zmeny.
Martin Mares [Mon, 12 Jan 2009 20:25:53 +0000 (21:25 +0100)]
Operace Unpack: radeji Cmp s vektorem samych nul, neni treba negovat.
Martin Mares [Mon, 12 Jan 2009 20:23:54 +0000 (21:23 +0100)]
Kostra pro setridene hrany: Precislovavame na 1...m (preklep).
Martin Mares [Mon, 12 Jan 2009 20:23:11 +0000 (21:23 +0100)]
Fredmanuv-Tarjanuv algoritmus: V analyze pocitame za incidentni i vnitrni
hrany, jinak bychom museli slozite osetrovat, ze mohou pri spojeni podkoster
vypanout.
Martin Mares [Mon, 12 Jan 2009 20:21:23 +0000 (21:21 +0100)]
Jarnikuv algoritmus s Fib. haldou: pilujeme formulace.
Martin Mares [Mon, 12 Jan 2009 20:18:50 +0000 (21:18 +0100)]
Minimalni rez: Opraven preklep v dukazu lemmatu o legalnim usporadani.
Taktez lehce vylepsena formulace na zacatku dukazu.
Martin Mares [Mon, 12 Jan 2009 20:11:50 +0000 (21:11 +0100)]
Algoritmus Tri Indu: Oprava preklepu v 10. kroku (s -> t).
Martin Mares [Mon, 12 Jan 2009 17:48:27 +0000 (18:48 +0100)]
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.
Martin Mares [Thu, 23 Oct 2008 11:16:47 +0000 (13:16 +0200)]
Kosmetika: Scaling -> skalovani.
Martin Mares [Thu, 23 Oct 2008 11:14:25 +0000 (13:14 +0200)]
Kosmetika: Ford-Fulkersonuv -> Forduv-Fulkersonuv
Martin Mares [Thu, 23 Oct 2008 11:13:02 +0000 (13:13 +0200)]
Toky: Kosmeticke upravy.
Martin Mares [Thu, 23 Oct 2008 11:08:33 +0000 (13:08 +0200)]
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.
Martin Mares [Thu, 23 Oct 2008 10:49:39 +0000 (12:49 +0200)]
Dinicuv algoritmus: Oprava preklepu.
Martin Mares [Fri, 29 Feb 2008 20:03:04 +0000 (21:03 +0100)]
Merge with git+ssh://git.ucw.cz/home/mj/GIT/ga.git
Martin Mares [Fri, 29 Feb 2008 20:02:58 +0000 (21:02 +0100)]
Opravena chyba v pseudokodu Ukkonenova algoritmu (podminka v bodech 10
a 15 byla prohozena). Diky Martinovi Kupcovi a Milanovi Strakovi za upozorneni.
Martin Mares [Thu, 17 Jan 2008 13:59:56 +0000 (14:59 +0100)]
Opraven preklep v dukazu lemmatu o monotonnim swapovani.
Martin Mares [Thu, 17 Jan 2008 13:59:02 +0000 (14:59 +0100)]
Opraven preklep ve jmene pana Kirchhoffa.
Martin Mares [Mon, 29 Oct 2007 19:54:22 +0000 (20:54 +0100)]
Upraveny uploadovaci skriptiky, aby generovaly changelog od tistene verze.
Martin Mares [Mon, 29 Oct 2007 19:50:52 +0000 (20:50 +0100)]
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.
Martin Mares [Fri, 11 May 2007 15:56:50 +0000 (17:56 +0200)]
Do balicku jsem pridal mjmac.tex, ktery tam omylem chybel.
Martin Mares [Tue, 13 Mar 2007 14:16:18 +0000 (15:16 +0100)]
Na titulni stranu pribyl obrazek, diky, Kubo!
ISBN ma nyni spravnou polohu na strance.
Martin Mares [Tue, 13 Mar 2007 14:15:54 +0000 (15:15 +0100)]
Drobne upravy sazby.
Martin Mares [Mon, 12 Mar 2007 09:35:43 +0000 (10:35 +0100)]
Hura, mame ISBN! :)
Martin Mares [Thu, 8 Mar 2007 18:39:29 +0000 (19:39 +0100)]
Drobne upravy sazby.
Martin Mares [Wed, 7 Mar 2007 18:57:41 +0000 (19:57 +0100)]
Finalni strankovy zlom, titulni strana, obsah a tiraz.
Martin Mares [Wed, 7 Mar 2007 18:56:58 +0000 (19:56 +0100)]
Pribylo jedno snadne cviceni.
Martin Mares [Wed, 7 Mar 2007 18:48:52 +0000 (19:48 +0100)]
Upravy pro finalni sazbu.
Odstranen obrazek radixsortu -- neni dulezity a rozbijel strankovy zlom.
Martin Mares [Wed, 7 Mar 2007 18:47:35 +0000 (19:47 +0100)]
Snad uz finalni verze uvodu, jen drobne upravy.
Martin Mares [Tue, 6 Mar 2007 18:09:32 +0000 (19:09 +0100)]
Alespon hruby odhad na Union-Find.
Martin Mares [Thu, 22 Feb 2007 14:08:06 +0000 (15:08 +0100)]
Pridana zminka o stridavych cestach a Hopcroft-Tarjanove algoritmu.
Martin Mares [Thu, 22 Feb 2007 13:11:20 +0000 (14:11 +0100)]
Ohodnoceni hran by pri hledani rezu mela byt nezaporna.
Martin Mares [Thu, 22 Feb 2007 13:09:27 +0000 (14:09 +0100)]
Opraveno jmeno pani Corasickove a pridan odkaz na jeji clanek.
Martin Mares [Fri, 16 Feb 2007 21:01:17 +0000 (22:01 +0100)]
Pripsan algoritmus tri Indu. Bohuzel se tim dost rozpadla sazba, ale to brzy napravime.
Martin Mares [Tue, 13 Feb 2007 10:35:09 +0000 (11:35 +0100)]
Opraveno par preklepu a formulacnich nepresnosti.