LaTeX (carte)/Algoritmi și pseudocod

LaTeX are o serie de pachete ce pot ajuta la formatarea algoritmilor, codului și "pseudocodului". Aceste pachete oferă îmbunătățiri stilistice pentru un stil uniform (typewriter), astfel încât construcții de genul buclelor sau structurilor de decizie sunt separate vizual de restul textului.

Redactarea algoritmilor

Formatarea cu ajutorul pachetului algorithmic

Mediul algorithmic oferă un număr de structuri populare pentru modele de algoritmi. Comanda \begin{algorithmic} poate lua ca argument opțional un întreg pozitiv, care, dacă este prezent, va face ca numerotarea liniilor să apară la multipli ai acelui întreg. Spre exemplu, \begin{algorithmic}[5] va intra în mediul algorithmic și va numerota fiecare a cincea linie.

Iată un exemplu de redactare a unui algoritm elementar cu ajutorul pachetului algorithmic (amintiți-vă să adăugați declarația \usepackage{algorithmic} în preambulul documentului):

\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}

Fișierul sursă LaTeX poate fi scris într-un format familiar programatorilor astfel încât să fie ușor de citit. Asta nu va afecta, totuși, aspectul final al documentului.

Pachetul algorithmic oferă mai multe structuri, detaliate mai jos.

Declarații pe o singură linie

\STATE <text>

O declarație simplă, spre exemplu, pentru setarea unei variabile. De exemplu:

\begin{algorithmic}
\STATE i=0
\end{algorithmic}

va produce
i = 0

Declarații if

Există trei forme ale acestei structuri:

\IF{<condiție>} <text> \ENDIF

\IF{<condiție>} <text> \ELSE <text> \ENDIF

\IF{<condiție>} <text> \ELSIF{<condiție>} <text> \ELSE <text> \ENDIF

A treia formă acceptă oricâte ramuri \ELSIF{} este necesar.

Bucle for

Sunt două forme posibile:

\FOR{<condiție>} <text> \ENDFOR

\FORALL{<condiție>} <text> \ENDFOR

O buclă "for" tradițională. Metoda iterației este de obicei descrisă în primul argument, de exemplu:

\FOR{$i = 1$ \TO 10} 
\STATE $i \gets i + 1$
\ENDFOR

Bucle while

\WHILE{<condiție>} <text> \ENDWHILE

Repetă până la îndeplinirea unei condiții

\REPEAT <text> \UNTIL{<condiție>}

Bucle infinite

\LOOP <text> \ENDLOOP

Precondiție

\REQUIRE <text>

Postcondiție

\ENSURE <text>

Returnarea de variabile

\RETURN <text>

Tipărirea variabilelor

\PRINT <text>

Este inclusă aici deoarece este utilizată atât de des încât se consideră a fi o operație de sine stătătoare.

Comentarii

\COMMENT{<text>}

Notați că nu puteți folosi \COMMENT ca prima declarație a oricărei structuri închise, de genul \IF..\ENDIF, \FOR..\ENDFOR, \FORALL..\ENDFORALL, \WHILE..\ENDWHILE și \begin{algorithmic}..\end{algorithmic}. Se va raporta o eroare de genul "Something's wrong--perhaps a missing \item" (care nu prea are sens). Sunt două soluții posibile:

1. Folosiți \STATE \COMMENT{<text>}.
2. Utilizați argumente opționale în aceste structuri închise. Spre exemplu, \WHILE[<comentariu-text>]{<condiție>}. Pentru a folosi comenzi matematice în textul din comentarii, înlocuiți $..$ cu \ensuremath{..}

Compatibilitatea cu hyperref

Din cauza unei erori de programare, pachetul algorithmic nu este compatibil cu hyperref. O soluție ar fi pachetul algorithmic-fix. Copiați codul găsit pe pagina Web indicată mai devreme într-un fișier numit algorithmic-fix.sty și includeți-l cu \usepackage{algorithmic,algorithmic-fix}. Totuși, dacă acest truc eșuează, încercați \usepackage{hyperref} înainte de \usepackage{algorithmic}. În cazul acesta, s-ar putea să nu mai aveți defel nevoie de algorithmic-fix.sty.

Redenumiri: algoritm în procedură, necesită/asigură (require/ensure) în input/output

\floatname{algorithm}{Procedură}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

Mediul algorithm

Este deseori util ca algoritmul produs de algorithmic să fie "mutat" în punctul optim al documentului pentru a evita împărțirea lui pe pagini separate. Mediul algorithm are grijă de asta și de alte câteva lucruri. Includeți-l adăugând
\usepackage{algorithm} în preambulul documentului. Acest mediu se folosește în felul următor:

\begin{algorithm}
 \caption{<titlul algoritmului>}
 \label{<eticheta pentru trimiterile ulterioare din document>}
 \begin{algorithmic}
  <mediul algorithmic>
 \end{algorithmic}
\end{algorithm}

Numerotarea algoritmilor

Sistemul implicit de numerotare pentru pachetul algorithm constă în numărarea secvențială a algoritmilor. Acest lucru în general nu este de dorit, mai ales în documente mari, în care numerotarea după capitole este mai potrivită. Numărarea algoritmilor poate fi influențată de furnizarea numelui părții din document în care se recomandă a se face numerotarea. Valorile legale pentru această opțiune sunt: parte, capitol, secțiune, subsecțiune, subsubsecțiune sau nimic (implicit). Spre exemplu:

\usepackage[chapter]{algorithm}

Lista algoritmilor

Când folosiți figuri sau tabele, puteți adăuga o listă a acestora aproape de Cuprins; pachetul algorithm oferă o comandă similară. Dați comanda

\listofalgorithms

oriunde în document, iar LaTeX va tipări o listă a mediilor "algorithm" din document, cu pagina și titlul corespunzătoare.

Un exemplu din manual

Acesta este un exemplu luat din manual (manualul oficial, p.7)

\begin{algorithm}                      % începutul mediului 'algorithm'
\caption{Calculați $y = x^n$}          % titlul algoritmului
\label{alg1}                           % etichetă pentru comenzile \ref{} ulterioare
\begin{algorithmic}                    % începutul mediului 'algorithmic'
\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}

Vezi mai multe informații despre toate comenzile posibile la pagina proiectului

http://developer.berlios.de/docman/?group_id=3442

Manualul oficial este situat pe pagina

http://developer.berlios.de/docman/display_doc.php?docid=800&group_id=3442

Formatarea cu pachetul program

Pachetul program oferă macrouri pentru tipărirea algoritmilor. Fiecare linie este setată în modul matematic, astfel că întreaga indentare și spațiere se face automat. Notația |nume_variabilă| poate fi utilizată în textul normal, expresii matematice sau programe pentru a indica un nume de variabilă. Scrieți \origbar pentru o obține un simbol normal | într-un program. Comenzile \A, \B, \P, \Q, \R, \S, \T și \Z scriu litera aldină corespunzătoare, următorul obiect fiind scris la indice (spre exemplu, \S1 devine {\bf S$_1$} etc). Derivatele merg normal, de exemplu \S''.

Iată un exemplu de redactare a unui algoritm de bază cu ajutorul pachetului program (amintiți-vă să adăugați declarația \usepackage{program} în preambulul documentului):

\begin{program}
\mbox{O procedură rapidă de ridicare la putere:}
\BEGIN %
  \FOR i:=1 \TO 10 \STEP 1 \DO
     |expt|(2,i); \\ |newline|() \OD %
\rcomment{Acest text va fi aliniat la dreapta}
\WHERE
\PROC |expt|(x,n) \BODY
          z:=1;
          \DO \IF n=0 \THEN \EXIT \FI;
             \DO \IF |odd|(n) \THEN \EXIT \FI;
\COMMENT{Acesta este un comentariu};
                n:=n/2; x:=x*x \OD;
             \{ n>0 \};
             n:=n-1; z:=z*x \OD;
          |print|(z) \ENDPROC
\END
\end{program}

Comenzile \( și \) sunt redefinite pentru a scrie un algoritm într-o minipagină, astfel ca un algoritm să poată apare sub forma unei singure căsuțe într-o formulă. Spre exemplu, pentru a declara că un sistem particular de acțiune este echivalent unei bucle WHILE, puteți scrie:

\[
\( \ACTIONS A:
        A \EQ \IF \B{} \THEN \S{}; \CALL A
                       \ELSE \CALL Z \FI \QE
   \ENDACTIONS \)
\EQT
\( \WHILE \B{} \DO \S{} \OD \)
\]

Structurile condiționale și buclele lui 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}

Bucle cu ieșiri multiple:

\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}

Un exemplu de inginerie inversă (reverse engineering), generarea codului sursă din executabil.

Iată programul inițial:

\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}

Iar aici este versiunea transformată și corectată:

\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}

Pachetul oferă o macrocomandă pentru afișarea unei mulțimi, de genul: \set{x \in N | x > 0}.

Liniile pot fi numerotate prin setarea \NumberProgramstrue și dezactivarea numerotării cu \NumberProgramsfalse

Formatarea codului sursă cu pachetul listings

(Vezi pagina de referință a pachetului listings pentru mai multe informații.)

Puteți găsi un manual de referință complet la adresa http://tug.ctan.org/tex-archive/macros/latex/contrib/listings/listings.pdf

Iată un exemplu de bază pentru cod din limbajul de programare Pascal:

\documentclass{article}
\usepackage{listings}    % includeți pachetul listings
\begin{document}
\lstset{language=Pascal} % setați limbajul (puteți seta limbajul pentru fiecare bloc de cod)
% începutul unui bloc de cod:
\begin{lstlisting}[frame=single]
for i:=maxint to 0 do
begin
{ do nothing }
end;
Write(Case sensitive or insensitive);
Write(Pascal keywords: for, while, if, else, and, etc.);
\end{lstlisting}

\end{document}

Referințe

• Manualul oficial al pachetelor pentru algoritmi (algorithm și algorithmic), Rogério Brito (2009), http://www.ctan.org/get/macros/latex/contrib/algorithms/algorithms.pdf