LaTeX/Алгоритми
LaTeX има неколико пакета за алгоритме у форми "pseudocode". Они обезбеђују стилизована побољшања преко уједначеног стила (тојест., у typewriter фонту) тако да петље или кондиционали буду визуалоно одвојени од осталог текста . За typesetting real код, куцан у правом програмском језику, погледајте listings пакет описан у Листирање изворног кода.
Подешавање typesetting коришћењем algorithmic пакета
[уреди]algorithmic пакет користи другачији сет команди од algorithmicx пакета. ово није компатибилно са revtex4-1. Основне команде су:
\STATE <text>
\IF{<condition>} \STATE{<text>} \ELSE \STATE{<text>} \ENDIF
\FOR{<condition>} \STATE{<text>} \ENDFOR
\FOR{<condition> \TO <condition> } \STATE{<text>} \ENDFOR
\FORALL{<condition>} \STATE{<text>} \ENDFOR
\WHILE{<condition>} \STATE{<text>} \ENDWHILE
\REPEAT \STATE{<text>} \UNTIL{<condition>}
\LOOP \STATE{<text>} \ENDLOOP
\REQUIRE <text>
\ENSURE <text>
\RETURN <text>
\PRINT <text>
\COMMENT{<text>}
\AND, \OR, \XOR, \NOT, \TO, \TRUE, \FALSE
Комплента документација се налази на [2]. Већина команди је слична algorithmicx еквивалентима, али са другачијим наглашавањем.
algorithms bundle пакет на ctan repository, dated 2009-08-24, описује algorithmic окружење (за typesetting алгоритма) као и algorithm floating wrapper (погледајте below) који је дизајниран да обмота окружење алготитма.
algorithmic пакет се препоручује за IEEE journals јер је део њиховог уобичајеног стила.[1]
Подешавање typesetting копришћењем algorithm2e пакета
[уреди]algorithm2e пакет (прво објављен 1995., а поселдње унапређење добио јануара 2013. како се наводи на v5.0 manual) омогућава typesetting алготитма са доста могућности прилагођавања. Као algorithmic пакет, овај пакет такође није компатибилан са Revtex-4.1.[2]
За разлику од algorithmic, algorithm2e омогућава релативно велики број опција прилагођавања за изглед алгоритма које задовољавају потребе корисника. CTAN-manual обезбеђује разумљиву листу примера и сет котрола.
Уобичајено, употреба између \begin{algorithm} и \end{algorithm} била би
1. Постављање сета кључних речи (to typeset as functions/operators), котроле изгледа, наслова, текста у заглављу (који се појављује пре главних корака алгоритма на пример.: Input,Output)
2. Писање главних корака алгоритма, где се сваки корак завршава са \;
Можемо пронаћи аналогију са latex-преамбулом пре но што почнемо сам документ.
Пакет се учитава као
\usepackage[]{algorithm2e}
једноставан пример, узет из v4.01 упутства, је
\begin{algorithm}[H]
\KwData{this text}
\KwResult{how to write algorithm with \LaTeX2e }
initialization\;
\While{not at end of this document}{
read current\;
\eIf{understand}{
go to next section\;
current section becomes this one\;
}{
go back to the beginning of current section\;
}
}
\caption{How to write algorithms}
\end{algorithm}
Који прави
Више информација су у приручнику приложеном на ctan website.
Подешавање typesetting копришћењем algorithmicx пакета
[уреди]algorithmicx пакет обезбеђује доста конструката за дизајн алгоритма. Поставите \usepackage{algpseudocode} у преабмули да бисте користили алгоритамско окружење за писање алготитамског псеудокода (\begin{algorithmic}...\end{algorithmic}). Можда бисте желели да користите (\usepackage{algorithm}) да обухватите код алготитма у алгоритамско окружење (\begin{algorithm}...\end{algorithm}) да направите floating окружење са нумерисаним алгоритмима.
Команди \begin{algorithmic} може се доделити ппоизвољни аргумент позитивног интиџера, који ако задат проузрокује да се линије набрајања јављају на садржатељу тог интиџера. нпр. \begin{algorithmic}[5] ће ући у алгоритамско оружење и побројати сваку пету линију.
Испод је пример typesetting елементарног алгоритма коришћењем algorithmicx пакета (не заборавите да убаците и \usepackage{algpseudocode} исказ у преамбули вашег документа):
\begin{algorithmic}
\If {$i\geq maxval$}
\State $i\gets 0$
\Else
\If {$i+k\leq maxval$}
\State $i\gets i+k$
\EndIf
\EndIf
\end{algorithmic}
LaTeX извор се може писати у форми ознатој свим програмерима тако да буде лако читљив. Ово ипак неће утицати на финални изглед документа.
Основне команде имају следећу синтаксу:
Исказ (\Исказ са косом цртом пребацује у нови ред, и може се такође користити испред осталих команди)
\State $x\gets <value>$
Три форме if-исказа:
\If{<condition>} <text> \EndIf
\If{<condition>} <text> \Else <text> \EndIf
\If{<condition>} <text> \ElsIf{<condition>} <text> \Else <text> \EndIf
Трећа форма прихвата онолико \ElsIf{} клаузула колико је потребно. Обратите пажњу да се користи \ElsIf а не \ElseIf.
Петље:
\For{<condition>} <text> \EndFor
\ForAll{<condition>} <text> \EndFor
\While{<condition>} <text> \EndWhile
\Repeat <text> \Until{<condition>}
\Loop <text> \EndLoop
Pre- and postcondition:
\Require <text>
\Ensure <text>
Функције
\Function{<name>}{<params>} <body> \EndFunction
\Return <text>
\Call{<name>}{<params>}
Ова команда ће се обично користити у комбинацији са \State командом на овај начин:
\Function{Increment}{$a$}
\State $a \gets a+1$
\State \Return $a$
\EndFunction
Коментари:
\Comment{<text>}
Корисницима које су се пребацили са старог algorithmic пакета: коментари се могу налазити било где; нема ограничења као у старом algorithmic пакету.
Преименовање: algorithm to procedure, require/ensure to input/output
[уреди]\floatname{algorithm}{Procedure}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
Прилагодљиви блокови алгоритма
[уреди]algorithmicx пакет Вам омогућава да дефинишете ваша сопствена окружења.
Да бисте дефинисали почетак са почетном командом и крај са крајњом командом, користите,
\algblock[<block>]{<start>}{<end>}
Ово дефинише две команде \<start> и \<end> које немају параметре. Текст приказан је \textbf{<start>} и \textbf{<end>}.
Са \algblockdefx можете поставти текст као аутпут користећи почетак и крај команде и бројеве параметара за ове команде. У тексту н-ти параметар се референцира са #n.
\algblockdefx[<block>]{<start>}{<end>}
[<startparamcount>][<default value>]{<start text>}
[<endparamcount>][<default value>]{<end text>}
Пример:
\algblock[Name]{Start}{End}
\algblockdefx[NAME]{START}{END}%
[2][Unknown]{Start #1(#2)}%
{Ending}
\algblockdefx[NAME]{}{OTHEREND}%
[1]{Until (#1)}
\begin{algorithmic}
\Start
\Start
\START[One]{x}
\END
\START{0}
\OTHEREND{\texttt{True}}
\End
\Start
\End
\End
\end{algorithmic}
Напреднија прилагођавања и остали конструкти су описани у algorithmicx приручнику: http://mirror.ctan.org/macros/latex/contrib/algorithmicx/algorithmicx.pdf
algorithm окружење
[уреди]Често је корисно за алгоритме направљене са algorithmic да буду "floated" до оптималне тачке
у документу да би се избегло њихово раздвајање по страници .Окружење algorithm омогућава ово и још неколико корисних особина. Укључите је додајући
\usepackage{algorithm}
у преамбулу документа. У њега се улази са
\begin{algorithm}
\caption{<your caption for this algorithm>}
\label{<your label for references later in your document>}
\begin{algorithmic}
<algorithmic environment>
\end{algorithmic}
\end{algorithm}
Набрајање алгоритма
[уреди]Основни систем набрајања за algorithm пакет је да набрајате алгоритме секвенцијално. Ово често није пожељно, посебно у великом документу где се набраја по поглављима. На набрајање алгоритма се може утицати тако што се додели компонента име документа у којој је набрајање препоручено. Легалне вредности за ову опцију су: part, chapter, section, subsection, subsubsection or nothing (default). На пример:
\usepackage[chapter]{algorithm}
Листа алгоритма
[уреди]Када користите фигуре или табеле, можете их убацити у листу сличну садржају; algorithm пакет омогућава сличну команду. Само ставите
\listofalgorithms
било где у документу, и LaTeX ће штампати листу "алгоритамских" окружења у докуметну са одговарајућом страницом и насловом.
Пример из приручника
[уреди]Овај пример је узет из (official manual, p.14)
\begin{algorithm} % enter the algorithm environment
\caption{Calculate $y = x^n$} % give the algorithm a caption
\label{alg1} % and a label for \ref{} commands later in the document
\begin{algorithmic} % enter the algorithmic environment
\REQUIRE $n \geq 0 \vee x \neq 0$
\ENSURE $y = x^n$
\STATE $y \Leftarrow 1$
\IF{$n < 0$}
\STATE $X \Leftarrow 1 / x$
\STATE $N \Leftarrow -n$
\ELSE
\STATE $X \Leftarrow x$
\STATE $N \Leftarrow n$
\ENDIF
\WHILE{$N \neq 0$}
\IF{$N$ is even}
\STATE $X \Leftarrow X \times X$
\STATE $N \Leftarrow N / 2$
\ELSE[$N$ is odd]
\STATE $y \Leftarrow y \times X$
\STATE $N \Leftarrow N - 1$
\ENDIF
\ENDWHILE
\end{algorithmic}
\end{algorithm}
- Званични приручник се налази на
- http://mirrors.ctan.org/macros/latex/contrib/algorithms/algorithms.pdf
Подешавање typesetting коришћењем program пакета
[уреди]Пакет program обезбеђује macros за typesetting aлгоритма. Свака линија је подешена у math моду, тако да су раyмаци и наглашавања аутоматски одрађени . |variable_name| може бити коришћена и у нормалном тексту, математичким експресијама или програмима да нагласи име варијабле. Кoристите \origbar да бисте добили нормални | симбол у програму. Команде \A, \B, \P, \Q, \R, \S, \T и \Z могу се слагати и са болдованим словом следећег објекта као подскрипта (eg \S1 typesets {\bf S$_1$} etc). Основни раде нормално, eg \S‘‘.
Испод је пример typesetting основног алгоритма користећи program пакет (не заборавите да додате \usepackage{program} исказ у преамбули документа):
\begin{program}
\mbox{A fast exponentiation procedure:}
\BEGIN \\ %
\FOR i:=1 \TO 10 \STEP 1 \DO
|expt|(2,i); \\ |newline|() \OD %
\rcomment{This text will be set flush to the right margin}
\WHERE
\PROC |expt|(x,n) \BODY
z:=1;
\DO \IF n=0 \THEN \EXIT \FI;
\DO \IF |odd|(n) \THEN \EXIT \FI;
\COMMENT{This is a comment statement};
n:=n/2; x:=x*x \OD;
\{ n>0 \};
n:=n-1; z:=z*x \OD;
|print|(z) \ENDPROC
\END
\end{program}
Команде \( and \) су редефинисане да би се алгоритам представио у виду мале странице, тако да се може приказти као један прозор или у формули. На пример, да би изказали да је одређени систем акција еквивалентан WHILE петљи можете писати:
\[
\( \ACTIONS A:
A \EQ \IF \B{} \THEN \S{}; \CALL A
\ELSE \CALL Z \FI \QE
\ENDACTIONS \)
\EQT
\( \WHILE \B{} \DO \S{} \OD \)
\]
Dijkstra кондиционали и петље:
\begin{program}
\IF x = 1 \AR y:=y+1
\BAR x = 2 \AR y:=y^2
\utdots
\BAR x = n \AR y:=\displaystyle\sum_{i=1}^n y_i \FI
\DO 2 \origbar x \AND x>0 \AR x:= x/2
\BAR \NOT 2 \origbar x \AR x:= \modbar{x+3} \OD
\end{program}
Петље са више излаза:
\begin{program}
\DO \DO \IF \B1 \THEN \EXIT \FI;
\S1;
\IF \B2 \THEN \EXIT(2) \FI \OD;
\IF \B1 \THEN \EXIT \FI \OD
\end{program}
Пример обратног инжењеринга.
Ово је оригинални програм:
\begin{program}
\VAR \seq{m := 0, p := 0, |last| := `` ''};
\ACTIONS |prog|:
|prog| \ACTIONEQ %
\seq{|line| := `` '', m := 0, i := 1};
\CALL |inhere| \ENDACTION
l \ACTIONEQ %
i := i+1;
\IF (i=(n+1)) \THEN \CALL |alldone| \FI ;
m := 1;
\IF |item|[i] \neq |last|
\THEN |write|(|line|); |line| := `` ''; m := 0;
\CALL |inhere| \FI ;
\CALL |more| \ENDACTION
|inhere| \ACTIONEQ %
p := |number|[i]; |line| := |item|[i];
|line| := |line| \concat `` '' \concat p;
\CALL |more| \ENDACTION
|more| \ACTIONEQ %
\IF (m=1) \THEN p := |number|[i];
|line| := |line| \concat ``, '' \concat p \FI ;
|last| := |item|[i];
\CALL l \ENDACTION
|alldone| \ACTIONEQ |write|(|line|); \CALL Z \ENDACTION \ENDACTIONS \END
\end{program}
А ово тренсформисана, преправљена верзија:
\begin{program}
\seq{|line| := `` '', i := 1};
\WHILE i \neq n+1 \DO
|line| := |item|[i] \concat `` '' \concat |number|[i];
i := i+1;
\WHILE i \neq n+1 \AND |item|[i] = |item|[i-1] \DO
|line| := |line| \concat ``, '' \concat |number|[i]);
i := i+1 \OD ;
|write|(|line|) \OD
\end{program}
Пакет такође обезбеђује macro за typesetting сет као овај: \set{x \in N | x > 0}.
Линије се могу набрајати постављајући \NumberProgramstrue и искључењем набрајања \NumberProgramsfalse
Референце
[уреди]- Званични приручник за algorithms пакет, Rogério Brito (2009), http://mirrors.ctan.org/macros/latex/contrib/algorithms/algorithms.pdf