latex与流程图 (pgf&tizk)

  一直觉得在ubuntu下流程图的画法比较伤脑筋,昨天晚上耍了耍latex中的pgf和tizk包,感觉非常不错!值得推荐。

  虽然这个包可以绘制出一些数学的图形,但是我不建议,对于数学方面的图形还是用python提供的库比较好一些。该库提供的语法很简单,但是内容却不少,不过还是比较好掌握的。下面给出我尝试绘制属于我自己的纠删码的图。

  上面这个图的具体代码实现不超过100行,下面你会看到,不过老实说,颜色的配置还是花费了我比较多的时间的,因为latex只提供了6种基本的原色,所以其他颜色只有自己定义了,而且这里曲线的实现不是一个坐标坐标的移动,而是一句话就可以搞定的。多的话就不说了,个人觉得比较简单,具体代码可以看看如下:

\documentclass{article}

\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{arrows, decorations.pathmorphing, backgrounds, positioning, fit, petri, automata}

\definecolor{yellow1}{rgb}{1,0.8,0.2} 

%opening
\begin{document}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
                    semithick]
  \tikzstyle{every state}=[fill=yellow1,draw=none,text=black]

  \node[state] 	       (S) at (-6, 0)              {$S$};
  \node[state]         (xin1) at (-2, 3)           {$X^1_{in}$};
  \node[state]         (xin2) at (-2, 1)		{$X^2_{in}$};
  \node[state]         (xin3) at (-2, -1) 		{$X^3_{in}$};
  \node[state]         (xin4) at (-2, -3)       	{$X^4_{in}$};
  \node[state]         (xout1) at (0, 3)          {$X^1_{out}$};
  \node[state]         (xout2) at (0, 1) 		{$X^2_{out}$};
  \node[state]         (xout3) at (0, -1) 	{$X^3_{out}$};
  \node[state]         (xout4) at (0, -3)       	{$X^4_{out}$};
  \node[state]         (xin5)  at (3, -2) 	{$X^5_{in}$};
  \node[state]         (xout5) at (5, -2) 	{$X^5_{out}$};
  \node[state]         (DC) at (7, 2)       	{$DC$};

  \path (S) edge[bend left=26]              node {$\infty$} (xin1)
            edge[bend left=12]              node {$\infty$} (xin2)
            edge[bend right=12]             node {$\infty$} (xin3)
            edge[bend right=26]             node {$\infty$} (xin4)
        (xin1) edge  node {$\alpha=1$} (xout1)
        (xin2) edge  node {$\alpha=1$} (xout2)
        (xin3) edge  node {$\alpha=1$} (xout3)
        (xin4) edge  node {$\alpha=1$} (xout4)
        (xin5) edge  node {$1$} (xout5);
  \draw[->] (xout1) to[out=-30,in=150] node {$\beta$} (xin5);
  \draw[->] (xout2.east) to[out=-15,in=165] node [below] {$\beta$} (xin5);
  \draw[->] (xout3.east) to[out=0,in=180] node [below] {$\beta$} (xin5.west);
  \draw[->] (xout1) to[out=-5,in=175] node {$\infty$} (DC);
  \draw[->] (xout5) to[out=40, in=-120] node {$\infty$} (DC);
\end{tikzpicture}

\end{document}

  接下来这个图(纠删码毁坏一个节点的图)的绘制过程,是在上个图形的基础之上实现的,具体给出加入的代码(整体的实现算是比较明朗):

\draw[line width=2.5pt,red,-] (-1.7,-2.8)--(-0.3,-3.2);
\draw[line width=2.5pt,red,-] (-1.7,-3.2)--(-0.3,-2.8);

\draw[line width=2.5pt,red,dash pattern=on 6pt off 4pt on 2pt off 4pt,-] (-1,3.8)--(-1,2.5);
\draw[line width=2.5pt,red,dash pattern=on 6pt off 4pt on 2pt off 4pt,-] (-1,2.5) to[out=-10,in=170] (1.2,1.2);
\draw[line width=2.5pt,red,dash pattern=on 6pt off 4pt on 2pt off 4pt,-] (1.2,1.2) to[out=-100,in=80] (0.8,-1.9);

  对于资料,我觉得看中文或者博客,还不如看原版的manualpgf,google之即可得到。

my first beamer ppt

    继完成自己翻译论文排版之后,我第一次用latex beamer完成了自己的ppt,算是比较不错吧。由于时间仓促,所以在内容上不算是非常充足!

    在这次的实现中,我主要的感想有几点:

  1. 一些错误类型,只有自己见得多了,就知道了,特别是一些特殊符号,很容易就报错了;
  2. 好的东西是调出来的,最开始的时候或许排版啥的很不好,但是慢点调,总会有属于自己的模版;
  3. 语言和语言之间很相似,现在站在一个大的整体上看,感觉就是class的声明,接着就是头文件,也就是包,最后就是正文,和其他语言,如C等,都是如出一辙,所以不用害怕,其实也不难。

    要说的只有这些吧。当自己遇到困难的时候,千万别恼怒,要知道,这是你在进步的预兆。可以看看我最后生成的最终版:http://wenku.baidu.com/view/1d70280bb52acfc789ebc9c6.html?st=1

    想了想还是附上自己的代码共享给大家,需要注意,目录需要编译两次才出来。我直接用的是latexpdf **.tex:(图片没有给出,大家可以随便弄两张看看)

\documentclass[cjk,slidestop,mathserif]{beamer}

\usepackage{CJK}
\usepackage{beamerthemesplit} 
\usepackage{graphicx}
\useoutertheme{infolines}

\usetheme{Warsaw}	
\usecolortheme{crane}
\usecolortheme{seagull}

\setbeamertemplate{items}[ball]

\setbeamertemplate{blocks}[rounded][shadow=true]
\setbeamertemplate{navigation symbols}{}%去除底部比较酷的工具条,因为实际应用的很少

\begin{document}
\begin{CJK}{UTF8}{gkai}

\title{博弈论之公平组合游戏}
\author{欧阳梦云}
\institute[HUST]{华中科技大学}
%\date{\today}
\frame{\titlepage}
 
\frame{\tableofcontents}

\section{Introduction}

\subsection{An example}

\begin{frame}
\vspace{12pt}
 \frametitle{An example}\pause
 \begin{example}
  Description:\\
  有21枚石子组成的石堆,两人轮流进行游戏。每次游戏者可以
  取走石堆中不超过3枚的石子。谁取走最后一颗为胜利。
 \end{example}
\pause
$\clubsuit$ 你会先取么? \\

\vspace{36pt}
\pause
Analysis:1,2,3 || 4 || 5,6,7|| 8 ... \\ 

\vspace{18pt}
\pause
Conclude:先走,取一个石子
\end{frame}

\subsection{Background}

\begin{frame}
 \frametitle{应用背景}
 \vspace{12pt}
 博弈论在当今的生活中,几乎每个领域都会或多或少的涉及。
   \begin{itemize}
    \item<1-> 经济学领域中的,一个比较经典的博弈问题就是{\alert{“囚徒困境”}};
    \item<2-> 我们熟知的象棋比赛,电脑游戏;
    \item<3-> 甚至在生物领域,还存在着动物之间的博弈等等。
   \end{itemize}
   \vspace{10pt}
   \begin{table}
        \begin{tabular}{|c|c|c|}
        \hline
        甲乙策略 & 甲沉默 & 甲背叛 \\
        \hline
        乙沉默 & 二人同服刑一年 & 乙服刑10年,甲释放 \\
        \hline
        乙背叛 & 甲服刑10年,乙释放 & 二人同服刑8年 \\
        \hline
        \end {tabular}
    \end {table}
\end{frame}


\subsection{Definition}
\begin{frame}
 \frametitle{公平组合游戏}
 \vspace{16pt}
 公平组合游戏是博弈论的一个子集,它的成立需要如下前提:
 %\pause
 \vspace{6pt}
 \begin{enumerate}
  \item<1-> 两个参与者,游戏局面的状态集合是有限的;
  \item<2-> 在同一个局面下,两操作者可选择的操作集合完全相同,但每步必须得走;
  \item<3-> 无论如何游戏会在有限步内结束,且没有平局;
  \item<4-> 当无法进行操作时游戏结束,此时不能进行操作的一方输。
 \end{enumerate}

\end{frame}

\begin{frame}[label=here]
\vspace{12pt}
 \frametitle{P-position and N-position 定义}
 \begin{definition}
  P-position:后手必胜局面,winning for the Previous player。 \
  \
  \vspace{8pt}
  N-position:先手必胜局面,winning for the Next player。
 \end{definition}
 \vspace{24pt}
 \pause
  上面的例子中已经清晰的给出了这两种状态,\\
  \vspace{6pt}
  P-position就是上面的0,4,8,12... \\
  \vspace{6pt}
  N-position就是例如1,2,3,5...
\end{frame}

\subsection{Algorithm}
\begin{frame}
\vspace{12pt}
 通过上面的例子我们可以归纳出一般解决公平组合游戏的算法:
 \begin{enumerate}
  \item <1->将最终状态标记为P-position;
  \item <2->通过一步可以到达P-position的,都标记为N-position;
  \item <3->找到这样一个position,其所有的选择都只会到达N-position,将其标记为P-position;
  \item <4->如果在第3步中找到了一个P-position,则停止。否则继续第二步。
 \end{enumerate}
 \pause
\pause
\pause
 \pause
 \hyperlink{here}{\beamerbutton{$\blacklozenge$实例}}
 我们需要注意,这个算法是从最后状态分析。\\
 \pause
 \vspace{12pt}
 从算法中,我们也可以看出,P-position和N-position性质: \\
 $\clubsuit$ \color{blue}{所有的最终状态都是P-position;} \\
 \vspace{6pt}
 \pause
 $\clubsuit$ \color{blue}{从每个N-position,至少有一种方法可以到P-position;} \\
 \vspace{6pt}
 \pause
 $\clubsuit$ \color{blue}{每个P-position,每种方法都到达N-position。} \\
\end{frame}

\section{nim游戏}    %section
\subsection{An Typical Example}

\begin{frame}
\frametitle{An Example}
\vspace{12pt}
\begin{example}
Description: \\
现有5堆石子,石子的个数分别是2,3,4,甲乙两个参与者每次从这3堆石子中任选一堆取走石子,\
每次取走至少一个,至多整堆。最后取光者胜利。 
\end{example}
\vspace{16pt}
\pause
\ 问题:利用上面的策略分析依稀,如果你是甲,你会先走么?你该怎么走?

\pause
\pause
Analysis: \\
P-position (0,0,0),如果只有两堆且等量,(0,1,1) or (0,2,2)... \\
\pause
\vspace{12pt}
如果堆的个数增加到100个以上,我们又怎么分析呢? 
\end{frame}

\subsection{Conclude}

\begin{frame}
 \frametitle{Conclude}
 \vspace{12pt}
 \begin{alertblock}{Conclude}
  其实整个问题比较复杂,不过这类问题已经形成了一个有公式的解法,那就是每堆的个数相互“抑或”,\
  例如每堆的个数是$a_{1}$,$a_{2}$,...$a_{n-1}$,$a_{n}$,则 \
  $a_{1}$ $\bigoplus$ $a_{2}$ $\bigoplus$ $a_{3}$ ... $a_{n-1}$ $\bigoplus$ $a_{n} $),\
  
  如果最后的结果是0,代表当前状态为P-position; \\
  非0,代表当前状态为N-position。\\
 \end{alertblock}
 \vspace{6pt}
 这样一来,问题也很简单了。
 \pause
 \vspace{20pt}
 PS:已经有人给出了准确的证明!大家有兴趣的可以看看。

\end{frame}

\section{Sum of Combinatorial Games}
\subsection{mex definition}

\begin{frame}
 \frametitle{mex(minimal excludant)运算}
 \vspace{18pt}
 \begin{definition}
  mex mex运算,就是施加在一个集合上的运算,表示最小的不属于这个集合的非负整数。 
 \end{definition}
 \vspace{8pt}
 例如mex$\{$0,1,2,4$\}$=3,mex$\{$2,3,5$\}$=0。 
 \vspace{12pt}
 \pause
 \begin{alertblock}{引申}
  对于有向无环图,定义关于图的每个顶点的Sprague-Garundy函数g为:g($x$)=mex$\{$g($y$) $\mid$ $y$是$x$的后继$\}$。
 \end{alertblock}

\end{frame}

\subsection{The Sprague Grundy Theorem}
\begin{frame}
\frametitle{SG函数和公平组合游戏}
\vspace{14pt}
 $\bigstar$上面已经给出了SG函数的定义。现在大家应该有很多疑问,为什么会引出SG函数?? \\
 \pause
 \vspace{10pt}
 $\circlearrowleft$其实我们可以将所有的公平组合游戏抽象成一个有起始点的有向五环图,在顶点上有一枚石子,两名选手交替将石子移动,最后无法移动者为败。
 \\
 \pause
 \vspace{8pt}
 $\circlearrowright$这样一来,公平组合游戏中每个局面可以看作图的顶点,而顶点之间的边,即为操作。\
 经过抽象之后,很多问题就可以得到解决了,甚至可以给出所有的必胜操作步骤,以及每一步具体怎么操作。
\end{frame}

\begin{frame}
 \frametitle{SG函数和公平组合游戏}
 \vspace{14pt}
 首先,所有最终节点,也就是没有出边的顶点,SG值为0,因为后继集合是空集。\\
 \pause
 \vspace{6pt}
 其次,对于一个$g(x)=0$的顶点$x$,他的后继$y$都满足$g(y)!=0$。\\
 \vspace{4pt}
 而对于一个$g(x)!=0$的顶点,必定存在一个后继$y$,满足$g(y)=0$。\\
 \vspace{10pt}
 \pause
 \begin{alertblock}{对应到公平组合游戏上}
  结合上面所说道的P-position和N-position的定义以及性质,我们可以看到,顶点$x$所代表的position是P-position \
  当且仅当$g(x)=0$,我们通过计算有向无环图每个顶点的SG值,就可以找到所有的必胜策略了。
 \end{alertblock}

\end{frame}

\begin{frame}
 \frametitle{An example}
  下图给出的是一个SG推倒函数,其中最开始有4个终节点,SG值都为0,接着a点和b点都被给出,上面的是通过推断的。
  \begin{figure}
    \includegraphics[width = 8cm]{sg.jpg}
  \end{figure} 

\end{frame}

\begin{frame}
 \frametitle{Conclude}
 \vspace{10pt}
 \begin{alertblock}{example}
  再给出一种情况,有n堆石子,每次可以从第一堆里去1,2,3颗,可以从第二堆里取奇数颗,第三堆及以后可以取任意颗。
 \end{alertblock}
 \vspace{6pt}
 这个问题我们又怎么解决呢?? \\
\pause
\vspace{10pt}
其实我们可以把这个问题看作3个游戏,每个游戏对应有向无环图的一个顶点,这样一来,有向无环图有3个顶点。 \\
\vspace{4pt}
\pause
也就是进一步将SG函数抽象,\\
\pause
对应的第一个游戏,SG值是$x\%2$($x$是一堆石子的个数);\\
\pause
第二个游戏的SG值是$x\%2$; \\
\pause
第三个游戏对应的是一个$n-2$的nim游戏。
\end{frame}

\begin{frame}
 \frametitle{Conclude}
 \vspace{10pt}
 \begin{alertblock}{example}
  再给出一种情况,有n堆石子,每次可以从第一堆里去1,2,3颗,可以从第二堆里取奇数颗,第三堆及以后可以取任意颗。
 \end{alertblock}
\pause
\vspace{10pt}
 $\cdots$紧接着上面的分析:\\
 \vspace{6pt}
 在求得每个游戏SG值后,然后将所有的异或,也就得到了整体的SG值,这样就可以判断是否有必胜策略了。\\
 \pause
 \vspace{10pt}
 SG函数是让我们遇到看上去很复杂的游戏试图分成若干个子游戏,然后找出最终的SG值,来解决问题。\\
 \vspace{6pt}
 \pause
 当然了,这里的游戏还有很多变型模式,所以SG函数的应用领域就很广泛了。下面就是一个比较好的应用:
\end{frame}

\subsection{Applications}

\begin{frame}
\frametitle{具体应用}
\vspace{12pt}
这里所说的应用主要是在算法上的应用,当然了,博弈还可以用来写象棋程序等。
\begin{alertblock}{problems}
 \begin{enumerate}
  \item[1$\>$]http://acm.hdu.edu.cn/showproblem.php?pid=1907 
  \item[2$\>$]http://acm.hdu.edu.cn/showproblem.php?pid=2509
  \item[3$\>$]http://acm.hdu.edu.cn/showproblem.php?pid=1536
  \item[4$\>$]http://acm.hdu.edu.cn/showproblem.php?pid=1944
 \end{enumerate}

\end{alertblock}
\end{frame}

\frame{
    \frametitle{Questions and answers}
    \begin{figure}
        \includegraphics[width=6cm]{faq.jpg}
    \end{figure}
}
 
\end{CJK}
\end{document}

初试絮叨之beamer

    在正式开始之前,我想吐吐我的肺腑之言。

    最开始接触latex是在去年7月份,当时,觉得这个东西非常神奇,但是很长一段时间,我都只是止步于看资料,做笔记的阶段,以至于后来将这写都抛诸脑后了。前天又开始拿起来是因为想写一个ppt,但是迫于ubuntu12.04的压力,我只得弃office而择“良木”。吸取上次的教训,我这次不仅仅是看资料,而是边看边自己动手尝试,仅仅用半天时间,我就基本可以写出一个不错的演示本,基本语法啥的都掌握了!

    事后,这让我感触很深。“其实任何东西都是我自己想难了,其实当你真正去-动手-学习时,一切都会是那么easy”,这是我在扣扣上写的签名,这里作这么多的赘述,只是想在接下来的学习中,当我遇到困难,当我停滞向前时,我会回过头来翻翻这篇文章,i believe i can!


    latex的基本语法就那些,而且在某种形式上说,各个模版如artical,beamer,report等,很多语法都可以通用,所以当你会了一种之后,其他就显得手到擒来。

    作为一个greenhand,这里我有几个问题还是没有搞的太清楚,虽然写出了一个演示稿。

  1. \useoutertheme{infolines}这个主题的使用,通过测试,个人感觉好像在使用中具体和所使用的theme有关,例如rochester就配合的非常好,但是在warsaw下,就显得有点小小的问题!
  2. only和uncover这两个功能的区别具体还不是很清楚;因为我在一个地方对同一个对象使用的时候,得到的结果都是一样的;
  3. 最后一点也是我最纠结的,我使用的是kile+okular,当我设置了改变颜色,编译运行之后,viewpdf的时候,居然颜色还是之前的,没有什么改变,不知道是okular的原因,还是我的原因!(切换到该文件夹下,用其他pdf工具察看,颜色确实改变了)
  4. 承接第3点,我在能够运行得出pdf的情况下,加了下面的一个frame。我点击编译运行成功之后,再viewpdf的时候,没有生成相应的pdf文件,在output里,我可以看到“!pdfTeX error: /usr/bin/pdflatex (file ./faq.jpg): reading JPEG image failed (no JPEG header found)”,不知道是什么原因。(我后来在命令行里执行,latex *.tex,dvipdf *.dvi,这种情况下,可以得到输出的pdf,用pdf阅读器看,是正常的!!)
    \frame{
        \frametitle{Questions and answers}
        \begin{figure}
            \includegraphics[width=6cm]{faq.jpg}
        \end{figure}
    }

    这是我这次总结得出的几个问题,希望我能在接下来的学习中一一解决,如果有牛人可以指点一下,也是非常好的!

    PS:我学习beamer中使用到的资料

http://wenku.baidu.com/view/848fe465783e0912a2162aa2.html

http://www.math.umbc.edu/~rouben/beamer/quickstart.html

(还下载了一些手册,没来得及看!对与latex,这个网站也不错:http://math.ecnu.edu.cn/~latex/)