X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=lib%2Fexamples%2Fbeamerlyxexample1.lyx;h=b4ee35edf3ae499f0f25da244d8ef1e5351d760b;hb=a1add5e8045905bbeb7747e463f5bb95e221346f;hp=cf5482769f4726fc2ec233caee5379a51e90ae23;hpb=86559aa3187e1645aeb1bae869f6ebd9ce626a32;p=lyx.git diff --git a/lib/examples/beamerlyxexample1.lyx b/lib/examples/beamerlyxexample1.lyx index cf5482769f..b4ee35edf3 100644 --- a/lib/examples/beamerlyxexample1.lyx +++ b/lib/examples/beamerlyxexample1.lyx @@ -1,5 +1,5 @@ #LyX 2.1 created this file. For more info see http://www.lyx.org/ -\lyxformat 452 +\lyxformat 474 \begin_document \begin_header \textclass beamer @@ -177,13 +177,16 @@ \use_geometry false \use_package amsmath 2 \use_package amssymb 2 +\use_package cancel 0 \use_package esint 0 \use_package mathdots 1 \use_package mathtools 0 \use_package mhchem 1 +\use_package stackrel 0 +\use_package stmaryrd 0 \use_package undertilde 0 \cite_engine basic -\cite_engine_type numerical +\cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false @@ -246,10 +249,20 @@ ICSI January 30th, 2004 \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Outline \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset CommandInset toc LatexCommand tableofcontents @@ -270,13 +283,10 @@ status collapsed \end_layout -\begin_layout EndFrame - -\end_layout - +\end_deeper \begin_layout Standard \begin_inset ERT -status collapsed +status open \begin_layout Plain Layout @@ -339,10 +349,20 @@ Introduction What are Tournaments? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments Consist of Jousts Between Knights \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Columns \end_layout @@ -577,10 +597,25 @@ In every joust one knight wins. \end_deeper \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments are Complete Directed Graphs \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Columns \end_layout @@ -826,20 +861,35 @@ any two different vertices. \end_deeper \end_deeper -\begin_layout BeginFrame -\begin_inset ERT +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -[<+>] ++ \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments Arise Naturally in Different Situations \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout ExampleBlock \begin_inset Argument 2 status collapsed @@ -930,15 +980,26 @@ It chooses from any two words the one more likely to be in . \end_layout +\end_deeper \end_deeper \begin_layout Subsection What Does ``Finding Paths'' Mean? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout ``Finding Paths'' is Ambiguous \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block \begin_inset Argument 2 status open @@ -1198,19 +1259,11 @@ nointerlineskip \end_layout \begin_layout Overprint - -\end_layout - -\begin_deeper -\begin_layout Standard -\begin_inset ERT -status collapsed +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - - -\backslash -onslide<1,3,5,7,9,11-12> +1,3,5,7,9,11-12 \end_layout \end_inset @@ -1218,6 +1271,7 @@ onslide<1,3,5,7,9,11-12> \end_layout +\begin_deeper \begin_layout Columns \begin_inset Argument 1 status open @@ -1905,15 +1959,13 @@ end{pgfpicture} \end_deeper \end_deeper -\begin_layout Standard -\begin_inset ERT -status collapsed +\end_deeper +\begin_layout Overprint +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - - -\backslash -onslide<2,4,6,8,10> +2,4,6,8,10 \end_layout \end_inset @@ -1921,6 +1973,7 @@ onslide<2,4,6,8,10> \end_layout +\begin_deeper \begin_layout Block \begin_inset Argument 2 status collapsed @@ -1936,16 +1989,6 @@ Variants of Path Finding Problems \begin_deeper \begin_layout Description -\begin_inset Argument 2 -status open - -\begin_layout Plain Layout -Approximation Problem: -\end_layout - -\end_inset - - \begin_inset Argument item:1 status open @@ -1972,6 +2015,16 @@ Problem: Is there a path from \end_inset ? +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +Approximation Problem: +\end_layout + +\end_inset + + \end_layout \begin_layout Description @@ -2102,6 +2155,7 @@ Problem: Construct a path from approximately their distance. \end_layout +\end_deeper \end_deeper \end_deeper \begin_layout Section @@ -2131,7 +2185,11 @@ pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Classes L and NL are Defined via \begin_inset Newline newline \end_inset @@ -2139,6 +2197,12 @@ The Classes L and NL are Defined via Logspace Turing Machines \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -2156,7 +2220,12 @@ begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm} \backslash pgfputat{ \backslash -pgfxy(0,4)}{ +pgfxy(0,4)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} \end_layout @@ -2174,7 +2243,12 @@ uncover<2->{% \backslash pgfputat{ \backslash -pgfxy(0,0.5)}{ +pgfxy(0,0.5)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash tape{}{output tape (write only)}{10690836937182}} \end_layout @@ -2197,7 +2271,12 @@ uncover<3->{% \backslash pgfputat{ \backslash -pgfxy(7,2)}{ +pgfxy(7,2)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash shorttape{work tape (read/write), $O( \backslash @@ -2210,7 +2289,12 @@ log n)$ symbols}{}{42}} \backslash pgfputat{ \backslash -pgfxy(1.75,2.5)}{ +pgfxy(1.75,2.5)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash pgfbox[center,center]{ \backslash @@ -2282,10 +2366,25 @@ end{pgfpicture} \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Logspace Turing Machines Are Quite Powerful \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block \begin_inset Argument 2 status collapsed @@ -2344,20 +2443,45 @@ satisfiability with two literals per clause. \end_layout \end_deeper -\begin_layout BeginFrame -\begin_inset ERT +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout +1 +\end_layout -<1>[label=hierarchy] +\end_inset + + +\begin_inset Argument 3 +status collapsed + +\begin_layout Plain Layout +label=hierarchy \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Complexity Class Hierarchy \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -2741,7 +2865,16 @@ end{pgfpicture} \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Circuit Complexity Classes AC \begin_inset Formula $^{0}$ \end_inset @@ -2761,6 +2894,12 @@ The Circuit Complexity Classes AC Limit the Circuit Depth \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -2969,6 +3108,7 @@ bounded fan-in . \end_layout +\end_deeper \end_deeper \end_deeper \begin_layout AgainFrame @@ -2988,7 +3128,11 @@ hierarchy Standard Complexity Results on Finding Paths \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout All Variants of Finding Paths in Directed Graphs \begin_inset Newline newline \end_inset @@ -2996,6 +3140,12 @@ All Variants of Finding Paths in Directed Graphs Are Equally Difficult \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}$ \end_inset @@ -3053,6 +3203,7 @@ the approximation problem in logspace iff . \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame \begin_inset Argument 1 @@ -3067,7 +3218,11 @@ status collapsed hierarchy \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Finding Paths in Forests and Directed Paths is Easy, \begin_inset Newline newline \end_inset @@ -3075,6 +3230,12 @@ Finding Paths in Forests and Directed Paths is Easy, But Not Trivial \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$ \end_inset @@ -3109,6 +3270,7 @@ But Not Trivial -complete. \end_layout +\end_deeper \begin_layout AgainFrame \begin_inset Argument 1 status collapsed @@ -3130,10 +3292,20 @@ Finding Paths in Tournaments Complexity of: Does a Path Exist? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Definition of the Tournament Reachability Problem \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition Let \color none @@ -3183,10 +3355,25 @@ there exists a path from \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Tournament Reachability Problem is Very Easy \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$ \end_inset @@ -3239,10 +3426,11 @@ easier . \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame \begin_inset Argument 1 -status collapsed +status open \begin_layout Plain Layout 5 @@ -3257,7 +3445,11 @@ hierarchy Complexity of: Construct a Shortest Path \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Finding a Shortest Path Is as Difficult as \begin_inset Newline newline \end_inset @@ -3265,6 +3457,12 @@ Finding a Shortest Path Is as Difficult as the Distance Problem \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition Let \color none @@ -3318,10 +3516,25 @@ the distance of \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Tournament Distance Problem is Hard \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset @@ -3382,7 +3595,16 @@ in logarithmic space, iff . \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Proof That \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset @@ -3390,6 +3612,12 @@ Proof That is NL-complete \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -4678,10 +4906,11 @@ end{pgfpicture} \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame \begin_inset Argument 1 -status collapsed +status open \begin_layout Plain Layout 6 @@ -4696,10 +4925,20 @@ hierarchy Complexity of: Approximating the Shortest Path \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Approximators Compute Paths that Are Nearly As Short As a Shortest Path \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition An \color none @@ -4758,7 +4997,16 @@ a path from \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout There Exists a Logspace Approximation Scheme for \begin_inset Newline newline \end_inset @@ -4766,6 +5014,12 @@ There Exists a Logspace Approximation Scheme for the Tournament Shortest Path Problem \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem There exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ @@ -4816,6 +5070,7 @@ beamergotobutton{More Details}} \end_layout +\end_deeper \begin_layout AgainFrame \begin_inset Argument 1 status collapsed @@ -4829,10 +5084,6 @@ status collapsed hierarchy \end_layout -\begin_layout EndFrame - -\end_layout - \begin_layout Standard \begin_inset Note Note status open @@ -4847,14 +5098,7 @@ fragile \end_inset . - This is not yet supported by LyX, so the frame is created using TeX code. - Note that the -\backslash -begin{frame}[fragile] needs to be preceeded by an -\emph on -EndFrame -\emph default - environment. + LyX has the FragileFrame layout for this. \end_layout \end_inset @@ -4862,42 +5106,12 @@ EndFrame \end_layout -\begin_layout Standard -\begin_inset ERT +\begin_layout FragileFrame +\begin_inset Argument 4 status open \begin_layout Plain Layout - - -\backslash -begin{frame}[fragile] -\end_layout - -\end_inset - - -\end_layout - -\begin_layout Standard -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - - -\backslash -frametitle{ -\end_layout - -\end_inset - Just a frame with a program code listing -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -4905,10 +5119,11 @@ status collapsed \end_layout -\begin_layout Standard +\begin_layout FragileFrame This is some program code: \end_layout +\begin_deeper \begin_layout Standard \begin_inset listings lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4" @@ -4965,22 +5180,7 @@ pass \end_layout -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -end{frame} -\end_layout - -\end_inset - - -\end_layout - +\end_deeper \begin_layout Section* Summary \end_layout @@ -4989,10 +5189,20 @@ Summary Summary \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Summary \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block \begin_inset Argument 2 status collapsed @@ -5145,15 +5355,26 @@ beamergotobutton{More Details}} \end_layout +\end_deeper \end_deeper \begin_layout Subsection* For Further Reading \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout For Further Reading \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status open @@ -5171,7 +5392,6 @@ beamertemplatebookbibitems \end_layout \begin_layout Bibliography -\labelwidthstring References \begin_inset CommandInset bibitem LatexCommand bibitem key "Moon1968" @@ -5232,7 +5452,6 @@ beamertemplatearticlebibitems \end_layout \begin_layout Bibliography -\labelwidthstring References \begin_inset CommandInset bibitem LatexCommand bibitem key "NickelsenT2002" @@ -5279,7 +5498,6 @@ Proc. \end_layout \begin_layout Bibliography -\labelwidthstring References \begin_inset CommandInset bibitem LatexCommand bibitem key "Tantau2004b" @@ -5339,10 +5557,7 @@ newblock In press. \end_layout -\begin_layout EndFrame - -\end_layout - +\end_deeper \begin_layout Standard \start_of_appendix \begin_inset ERT @@ -5368,20 +5583,30 @@ Appendix Graphs With Bounded Independence Number \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 3 status collapsed \begin_layout Plain Layout - -[label=independence] +label=independence \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Definition of Independence Number of a Graph \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition The \color none @@ -5411,7 +5636,16 @@ Tournaments have independence number 1. \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Results for Tournaments also Apply to \begin_inset Newline newline \end_inset @@ -5419,6 +5653,12 @@ The Results for Tournaments also Apply to Graphs With Bounded Independence Number \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem For each \begin_inset space ~ @@ -5530,21 +5770,36 @@ in graphs with independence number at most . \end_layout +\end_deeper \begin_layout Subsection Finding Paths in Undirected Graphs \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout +1-2 +\end_layout + +\end_inset + -<1-2>[label=undirected] +\begin_inset Argument 3 +status collapsed + +\begin_layout Plain Layout +label=undirected \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Complexity of Finding Paths in Undirected Graphs \begin_inset Newline newline \end_inset @@ -5552,6 +5807,12 @@ The Complexity of Finding Paths in Undirected Graphs Is Party Unknown. \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$ \end_inset @@ -5673,25 +5934,36 @@ the approximation problem in logspace iff ?. \end_layout +\end_deeper \end_deeper \begin_layout Subsection The Approximation Scheme is Optimal \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 3 status collapsed \begin_layout Plain Layout - -[label=optimality] +label=optimality \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Approximation Scheme is Optimal \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem Suppose there exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ @@ -5775,9 +6047,6 @@ qedhere \end_layout \end_deeper -\begin_layout EndFrame - -\end_layout - +\end_deeper \end_body \end_document