01ZTGA: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
 
(Není zobrazeno 7 mezilehlých verzí od stejného uživatele.)
Řádka 6: Řádka 6:
 
\pagestyle{empty}
 
\pagestyle{empty}
  
 
+
\title{{\LARGE Základy teorie grafů}\\
 
+
 
+
 
+
 
+
 
+
 
+
\title{{\LARGE Základy Teorie Grafů}\\
+
 
{\large (poznámky z přednášek)}}
 
{\large (poznámky z přednášek)}}
  
Řádka 26: Řádka 19:
 
\listoffigures
 
\listoffigures
  
 +
\input{cast0}
  
 +
\pagestyle{headings}
  
\chapter*{Úvod}
+
\chapter{Standardní kurs teorie grafů}
 +
 +
\input{cast1_kapitola1}
 +
\input{cast1_kapitola2}
 +
\input{cast1_kapitola3}
 +
\input{cast1_kapitola4}
 +
\input{cast1_kapitola5}
 +
\input{cast1_kapitola6}
 +
\input{cast1_kapitola7}
 +
\input{cast1_kapitola8}
 +
\input{cast1_kapitola9}
 +
\input{cast1_kapitola10}
 +
\input{cast1_kapitola11}
 +
\input{cast1_kapitola12}
 +
\input{cast1_kapitola13}
  
\addcontentsline{toc}{chapter}{Úvod}
+
\chapter{Rozšířený kurs teorie grafů}
  
V průběhu přípravy na zkoušku ze Základů teorie grafů jsem si uvědomil,
+
\input{cast2_kapitola1}
že mé zápisky z přednášky jsou natolik kvalitní, že by bylo možné
+
\input{cast2_kapitola2}
je použít jako základ pro docela slušná skripta z tohoto předmětu.
+
\input{cast2_kapitola3}
Ještě před samotnou zkouškou jsem tedy zkusil napsat pár stránek a
+
\input{cast2_kapitola4}
s výsledkem jsem byl natolik spokojen, že jsem s chutí pokračoval
+
dál, pouze s motivací vytvořit něco smysluplného a užitečného. Přesto
+
mám poněkud rozporuplné pocity z následků, které uveřejnění tohoto
+
materiálu může mít.
+
  
Je jasné, že dobré zápisky nelze sestavit na základě nedobrých přednášek.
+
\chapter{Generující funkce}
Skvělé a zajímavé přednášky paní docentky Edity Pelantové je však
+
skoro škoda publikovat tak, aby byly každému snadno a volně dostupné.
+
Student získá určitou jistotu, o kterou se v případě potřeby bude
+
moci opřít, ale po krátkém čase usoudí, že sám si o mnoho lepší poznámky
+
z přednášky neodnese. Je-li student trochu línější, na přednášce se
+
už neukáže. Je pravda, že ve čtvrtém ročníku již velká většina studentů
+
brzy rozpozná kvalitu přednášek a dokáže si jí vážit. Ale vy, kteří
+
jste v pokušení, vězte, že byste přišli opravdu o hodně. I kdybyste
+
na žádné jiné přednášky nechodili, na grafy choďte, protože skutečně
+
stojí za to. A dělejte si zápisky, protože tak se toho nejvíc naučíte
+
:-)
+
  
ZTG se od akademického roku 2005/2006 dělí na dva předměty s odlišnou
+
Do kursu kombinatoriky a teorie grafů tradičně patří také kapitola
náplní. ZTG-B se skládá z 1 přednášky a 1 cvičení týdně. Na přednášce
+
o generujících funkcích, i když v rozsahu naší přednášky se samotné
jsou představeny základní kapitoly z teorie grafů, které pokrývá první
+
teorie grafů dotýká jen okrajově. Budeme se zabývat mocninnými řadami,
část těchto zápisků. Na cvičení jsou pak předmětem studia mimo jiné
+
s jejichž pomocí lze s úspěchem vyřešit zdánlivě velmi složité kombinatorické
algoritmy řešící některé známé grafové úlohy. ZTG-A se skládá ze 2
+
problémy. Tato kapitola pojednává o obyčejných mocninných řadách a
přednášek týdně, přičemž jedna je vždy vedena v době, kdy posluchači
+
exponenciálních generujících funkcích. Neobsahuje výklad Dirichletových
varianty B tohoto předmětu mají zrovna cvičení. Předmětem této přednášky
+
generujících funkcí, které však nebyly součástí zkoušené látky.
jsou některé pokročilejší partie teorie grafů, jako jsou věty z extremální
+
teorie grafů a ramseyovská čísla, dále pak generující funkce a jejich
+
využití demonstrované na velmi pěkných příkladech z oboru kombinatoriky
+
nebo teorie čísel. Tato část přednášky je pokryta ve druhé a třetí
+
kapitole.
+
  
Celý text velmi těsně kopíruje látku vyloženou na přednáškách, některé
+
Základní myšlenkou aplikovanou na problémy v této kapitole je zpravidla
pasáže jsou však mírně modifikovány, aby jejich pochopení nebo návaznost
+
přeformulování kombinatorické úlohy na úlohu nalezení koeficientů
byly (z mého pohledu) přirozenější. Vzhledem k tomu, že existuje kvalitní
+
mocninné řady, jejíž součet (generující funkci) známe. Přitom vždy
a přitom na internetu volně dostupná anglická literatura (dva příklady
+
využíváme jednoznačnost rozvoje funkce do mocninné řady.
jsou uvedeny v seznam použité literatury), opatřil jsem mnoho definic
+
jednotlivých pojmů též jejich anglickým zněním. Důkazy jsou někdy
+
komentovány až příliš, mou snahou však bylo nenechat žádného čtenáře
+
na holičkách. Na druhou stranu však platí, že nejlépe si pamatujeme
+
to, na co přijdeme sami.
+
  
Přeji vám všem, aby vám tyto poznámky byly užitečnou pomůckou při
+
\input{cast3_kapitola1}
studiu a abyste úspěšně složili zkoušky nejen z teorie grafů.
+
\input{cast3_kapitola2}
  
\bigskip{}
+
\begin{thebibliography}{1}
\begin{flushright}Pavel Strachota\end{flushright}
+
\bibitem{pelantova}Edita Pelantová: \emph{Základy teorie grafů}. FJFI ČVUT, přednášky,
 
+
2005.
\pagestyle{headings}
+
\bibitem{tslo}Vladan Majerech: \emph{Úvod do složitosti a NP-úplnosti}. MFF UK,
+
1999.
 +
\bibitem{GTWA}J. A. Bondy, U. S. R. Murty: \emph{Graph Theory With Applications}.
 +
Elsevier Science Publishing, New York, 1982.
 +
\bibitem{GT3}Reinhard Diestel: Graph Theory III (electronic edition 2005). Springer-Verlag
 +
Heidelberg, New York, 2005.
 +
\bibitem{PNLA}Jiří Mikyška: \emph{Pokročilé partie numerické lineární algebry}.
 +
FJFI ČVUT, přednášky, 2005.
 +
\bibitem{TIN}Igor Vajda: \emph{Teorie informace}. Vydavatelství ČVUT, Praha, 2004.
 +
\end{thebibliography}
 
   
 
   
 
\end{document}
 
\end{document}

Aktuální verze z 15. 1. 2012, 23:45

PDF [ znovu generovat, výstup z překladu ] Kompletní WikiSkriptum včetně všech podkapitol.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01ZTGA

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01ZTGAKarel.brinda 15. 1. 201223:45
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:51
Header editovatHlavičkový souborKarel.brinda 15. 1. 201212:34 header.tex
Kapitola0 editovatÚvodKarel.brinda 15. 1. 201212:36 cast0.tex
Kapitola1_1 editovatZákladní pojmyKarel.brinda 15. 1. 201212:46 cast1_kapitola1.tex
Kapitola1_2 editovatSouvislostKarel.brinda 15. 1. 201212:49 cast1_kapitola2.tex
Kapitola1_3 editovatBipartitní grafyKarel.brinda 15. 1. 201212:50 cast1_kapitola3.tex
Kapitola1_4 editovatStromyKubuondr 5. 1. 201909:06 cast1_kapitola4.tex
Kapitola1_5 editovatHledání minimální kostry grafuKarel.brinda 15. 1. 201212:51 cast1_kapitola5.tex
Kapitola1_6 editovatJednotažkyKarel.brinda 15. 1. 201212:53 cast1_kapitola6.tex
Kapitola1_7 editovatHamiltonovské kružnice a grafyKarel.brinda 15. 1. 201213:34 cast1_kapitola7.tex
Kapitola1_8 editovatPárování v grafechKarel.brinda 15. 1. 201213:40 cast1_kapitola8.tex
Kapitola1_9 editovatToky v sítíchKarel.brinda 15. 1. 201213:44 cast1_kapitola9.tex
Kapitola1_10 editovatHranové obarvení grafuKarel.brinda 15. 1. 201213:48 cast1_kapitola10.tex
Kapitola1_11 editovatVrcholové obarvení grafuKarel.brinda 15. 1. 201213:52 cast1_kapitola11.tex
Kapitola1_12 editovatPlanární grafyKarel.brinda 15. 1. 201213:56 cast1_kapitola12.tex
Kapitola1_13 editovatVlastní čísla adjacenční matice grafuKarel.brinda 15. 1. 201213:57 cast1_kapitola13.tex
Kapitola2_1 editovatBrouwerova věta o pevném boděKarel.brinda 15. 1. 201214:11 cast2_kapitola1.tex
Kapitola2_2 editovatPravděpodobnostní důkazy v teorii grafůKarel.brinda 15. 1. 201214:12 cast2_kapitola2.tex
Kapitola2_3 editovatExtremální teorie grafůKarel.brinda 15. 1. 201214:16 cast2_kapitola3.tex
Kapitola2_4 editovatRamseyovská číslaKarel.brinda 15. 1. 201214:18 cast2_kapitola4.tex
Kapitola3_1 editovatObyčejné mocninné řadyKarel.brinda 15. 1. 201214:22 cast3_kapitola1.tex
Kapitola3_2 editovatExponenciální generující funkceKarel.brinda 15. 1. 201214:22 cast3_kapitola2.tex

Zdrojový kód

%\wikiskriptum{01ZTGA}
 
\input{header}
 
\begin{document}
\pagestyle{empty}
 
\title{{\LARGE Základy teorie grafů}\\
{\large (poznámky z přednášek)}}
 
 
\author{Pavel Strachota, FJFI ČVUT}
 
\maketitle
\pagestyle{plain}
 
\tableofcontents{}
 
\listoffigures
 
\input{cast0}
 
\pagestyle{headings}
 
\chapter{Standardní kurs teorie grafů}
 
\input{cast1_kapitola1}
\input{cast1_kapitola2}
\input{cast1_kapitola3}
\input{cast1_kapitola4}
\input{cast1_kapitola5}
\input{cast1_kapitola6}
\input{cast1_kapitola7}
\input{cast1_kapitola8}
\input{cast1_kapitola9}
\input{cast1_kapitola10}
\input{cast1_kapitola11}
\input{cast1_kapitola12}
\input{cast1_kapitola13}
 
\chapter{Rozšířený kurs teorie grafů}
 
\input{cast2_kapitola1}
\input{cast2_kapitola2}
\input{cast2_kapitola3}
\input{cast2_kapitola4}
 
\chapter{Generující funkce}
 
Do kursu kombinatoriky a teorie grafů tradičně patří také kapitola
o generujících funkcích, i když v rozsahu naší přednášky se samotné
teorie grafů dotýká jen okrajově. Budeme se zabývat mocninnými řadami,
s jejichž pomocí lze s úspěchem vyřešit zdánlivě velmi složité kombinatorické
problémy. Tato kapitola pojednává o obyčejných mocninných řadách a
exponenciálních generujících funkcích. Neobsahuje výklad Dirichletových
generujících funkcí, které však nebyly součástí zkoušené látky.
 
Základní myšlenkou aplikovanou na problémy v této kapitole je zpravidla
přeformulování kombinatorické úlohy na úlohu nalezení koeficientů
mocninné řady, jejíž součet (generující funkci) známe. Přitom vždy
využíváme jednoznačnost rozvoje funkce do mocninné řady.
 
\input{cast3_kapitola1}
\input{cast3_kapitola2}
 
\begin{thebibliography}{1}
\bibitem{pelantova}Edita Pelantová: \emph{Základy teorie grafů}. FJFI ČVUT, přednášky,
2005.
\bibitem{tslo}Vladan Majerech: \emph{Úvod do složitosti a NP-úplnosti}. MFF UK,
1999.
\bibitem{GTWA}J. A. Bondy, U. S. R. Murty: \emph{Graph Theory With Applications}.
Elsevier Science Publishing, New York, 1982.
\bibitem{GT3}Reinhard Diestel: Graph Theory III (electronic edition 2005). Springer-Verlag
Heidelberg, New York, 2005.
\bibitem{PNLA}Jiří Mikyška: \emph{Pokročilé partie numerické lineární algebry}.
FJFI ČVUT, přednášky, 2005.
\bibitem{TIN}Igor Vajda: \emph{Teorie informace}. Vydavatelství ČVUT, Praha, 2004.
\end{thebibliography}
 
\end{document}