From f2c8892b32c6ede1e121ef70aac827964c74893f Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 12 Jan 2007 22:45:22 +0100 Subject: [PATCH] Uvodni kapitola; autori zapisku jmenovani tam misto na zacatcich kapitol. --- 1-toky/1-toky.tex | 6 +----- 10-decomp/10-decomp.tex | 2 +- 2-dinic/2-dinic.tex | 2 +- 3-bipcon/3-bipcon.tex | 2 +- 4-ght/4-ght.tex | 2 +- 5-mst/5-mst.tex | 2 +- 6-borjar/6-borjar.tex | 2 +- 7-ram/7-ram.tex | 2 +- 8-qheap/8-qheap.tex | 2 +- 9-suffix/9-suffix.tex | 2 +- all/Makefile | 2 +- ga.bib | 35 ++++++++++++++++++++++++++++++++++- sgr.tex | 2 +- 13 files changed, 46 insertions(+), 17 deletions(-) diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex index 3d5ab0e..63d6f7d 100644 --- a/1-toky/1-toky.tex +++ b/1-toky/1-toky.tex @@ -1,16 +1,12 @@ \input ../sgr.tex -\prednaska{1}{Toky, øezy a Ford-Fulkersonùv algoritmus}{zapsal Radovan ©esták} +\prednaska{1}{Toky, øezy a Ford-Fulkersonùv algoritmus}{} V~této kapitole nadefinujeme toky v~sítích, odvodíme základní vìty o~nich a Ford-Fulkersonùv algoritmus pro hledání maximálního toku. Také uká¾eme, jak na~hledání maximálního toku pøevést problémy týkající se øezù, separátorù a párování. Dal¹í algoritmy budou následovat v~pøí¹tích kapitolách. -\todo{Tady (nebo nìkde poblí¾) by mìly být zavedeny základní znaèky.} - -\todo{Co je $V$, $E$, $m$, $n$, komplementy, multihrany, WLOG souvislost \dots} - \h{Toky v sítích} Intuitivní pohled: sí» je systém propojených potrubí, který pøepravuje tekutinu diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex index b633a7e..03d484d 100644 --- a/10-decomp/10-decomp.tex +++ b/10-decomp/10-decomp.tex @@ -1,6 +1,6 @@ \input ../sgr.tex -\prednaska{10}{Dekompozice stromù}{zapsal Ale¹ ©nupárek} +\prednaska{10}{Dekompozice stromù}{} V~této kapitole uká¾eme nìkolik datových struktur zalo¾ených na~my¹lence dekompozice problému na~dostateènì malé podproblémy, diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index 5e24a11..7d39fc7 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -1,6 +1,6 @@ \input ../sgr.tex -\prednaska{2}{Dinicùv algoritmus a jeho varianty}{zapsal Bernard Lidický} +\prednaska{2}{Dinicùv algoritmus a jeho varianty}{} \h{Dinicùv algoritmus} diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index 81c3f00..49c87f1 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -1,6 +1,6 @@ \input ../sgr.tex -\prednaska{3}{Bipartitní párování a globální k-souvislost}{zapsali Jiøí Peinlich, Michal Kùrka} +\prednaska{3}{Bipartitní párování a globální k-souvislost}{} \>V~minulé kapitole jsme se zabývali aplikacemi tokù na~hledání maximálního párování a minimálního øezu. V~této si pøedvedeme dva algoritmy pro podobné problémy, diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex index bd5b8cf..6e599c6 100644 --- a/4-ght/4-ght.tex +++ b/4-ght/4-ght.tex @@ -11,7 +11,7 @@ \input ../sgr.tex -\prednaska{4}{Gomory-Hu Trees}{zapsal Milan Straka} +\prednaska{4}{Gomory-Hu Trees}{} Cílem této kapitoly je vytvoøit datovou strukturu, která po urèitém pøedzpracování doká¾e rychle konstruovat pro libovolnou dvojici vrcholù v~grafu diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index e0f9364..2f41c3b 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -1,5 +1,5 @@ \input ../sgr.tex -\prednaska{5}{Minimální kostry}{zapsali Martin Kruli¹ \& Petr Su¹il } +\prednaska{5}{Minimální kostry}{} \def\symdiff{\mathop{\Delta}} diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex index e8d0adc..3bd89a3 100644 --- a/6-borjar/6-borjar.tex +++ b/6-borjar/6-borjar.tex @@ -1,6 +1,6 @@ \input ../sgr.tex -\prednaska{6}{Rychlej¹í algoritmy na~minimální kostry}{zapsali Petr ©koda a Tomá¹ Gavenèiak} +\prednaska{6}{Rychlej¹í algoritmy na~minimální kostry}{} \h{Upravená verze Borùvkova algoritmu pro rovinné grafy} diff --git a/7-ram/7-ram.tex b/7-ram/7-ram.tex index f637144..11a1825 100644 --- a/7-ram/7-ram.tex +++ b/7-ram/7-ram.tex @@ -23,7 +23,7 @@ \medskip } -\prednaska{7}{Výpoèetní modely}{zapsal Zdenìk Vilu¹ínský } +\prednaska{7}{Výpoèetní modely}{} \h{Druhy výpoèetních modelù} diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex index 4c0a6db..9d88e93 100644 --- a/8-qheap/8-qheap.tex +++ b/8-qheap/8-qheap.tex @@ -9,7 +9,7 @@ \input ../sgr.tex -\prednaska{8}{Q-Heaps}{zapsal Cyril Strejc} +\prednaska{8}{Q-Heaps}{} V~minulé kapitole jsme zavedli výpoèetní model RAM a nahlédli jsme, ¾e na~nìm mù¾eme snadno simulovat vektorový poèítaè s~vektorovými operacemi pracujícími v~konstantním èase. diff --git a/9-suffix/9-suffix.tex b/9-suffix/9-suffix.tex index 30545e0..5f29710 100644 --- a/9-suffix/9-suffix.tex +++ b/9-suffix/9-suffix.tex @@ -1,6 +1,6 @@ \input ../sgr.tex -\prednaska{9}{Suffixové stromy} {Tomá¹ Mikula \& Jan Král} +\prednaska{9}{Suffixové stromy}{} V~této kapitole popí¹eme jednu datovou strukturu, pomocí které doká¾eme problémy týkající se øetìzcù pøevádìt na grafové problémy a tak je øe¹it v~lineárním èase. diff --git a/all/Makefile b/all/Makefile index 16e69e0..2d70065 100644 --- a/all/Makefile +++ b/all/Makefile @@ -1,5 +1,5 @@ P=ga -X=$(shell for a in 1 2 3 4 5 6 7 8 9 10 ; do echo ../$$a-*/$$a-*.tex ; done) +X=$(shell for a in 0 1 2 3 4 5 6 7 8 9 10 ; do echo ../$$a-*/$$a-*.tex ; done) include ../Makerules diff --git a/ga.bib b/ga.bib index e15b103..43c7e23 100644 --- a/ga.bib +++ b/ga.bib @@ -50,7 +50,7 @@ author = "J. K{\"a}rkk{\"a}inen and P. Sanders", title = "Simple linear work suffix array construction", booktitle = "Proc. 13th International Conference on Automata, Languages and Programming", - publisher = "Springer", + publisher = "Springer Verlag", year = "2003", url = "citeseer.ist.psu.edu/arkk03simple.html" } @@ -297,3 +297,36 @@ publisher = {Elsevier North-Holland, Inc.}, address = {Amsterdam, The Netherlands, The Netherlands}, } + +@book { kapitoly, + author = "Ji\v{r}\'\i{} Matou\v{s}ek and Jaroslav Ne\v{s}et\v{r}il", + title = "{Kapitoly z~diskr\'etn\'\i{} matematiky}", + year = "2002", + publisher = "Karolinum", + address = "Praha" +} + +@book { demel, + author = "Ji\v{r}\'\i{} Demel", + title = "{Grafy a jejich aplikace}", + year = 2002, + publisher = "Academia", + address = "Praha" +} + +@book { schrijver, + author = "Alexander Schrijver", + title = "{Combinatorial Optimization --- Polyhedra and Efficiency}", + series = "Algorithms and Combinatorics", + volume = 24, + year = 2003, + publisher = "Springer Verlag" +} + +@book { kucera, + author = "Lud'ek Ku\v{c}era", + title = "{Kombinatorick\'e algoritmy}", + year = 1989, + publisher = "SNTL", + address = "Praha" +} diff --git a/sgr.tex b/sgr.tex index 03a4f4e..7624d8a 100644 --- a/sgr.tex +++ b/sgr.tex @@ -15,7 +15,7 @@ % Zacatek prednasky {cislo prednasky}{jmeno prednasky}{jmeno zapisovatele} \def\prednaska#1#2#3{% -\line{{\Large\bf #1. #2} \hfil {\it (#3)}} +\line{{\Large\bf #1. #2} \hfil {\it #3}} \medskip \hrule \medskip -- 2.39.5