jeudi 28 août 2014

écrire des algorithmes en Latex

 LaTeX propose de très bons packages pour insérer du code source dans des documents, il propose aussi des  packages pour rédiger des algorithmes, dans un langages de description algorithmic,algorithmicx,algorithm2e et program  . L'intérêt de ces packages est de proposer une langage de description simple et de  gérer automatiquement l'indentation  des algorithmes à partir du balisage, mais hélas aucun n'est traduit en Français.  Pour mes besoins (j'enseigne les mathématiques en DUT informatique) j'ai donc  adapté le package program pour obtenir une mise en page simplifiée d'algorithmes en français  , voici le résultat  :







La grande force du package program.sty  par rapport aux autres outils disponibles dans LaTeX  est sa simplicité d'utilisation. Le balisage utilise des mot-clés naturels  et pas de parenthésage superflu, il est en cela plus pratique à utiliser que les packages algorithm*. Je n'utilise pas toutes les possibilités offertes par ce package  mais seulement les suivantes :
  •  définir une fonction  \FUNCT  ...   \ENDFUNCT
  •  les structures conditionnelles \IF  ... \THEN ... \ELSE ... \FI
  •  les boucles "tant que"   avec \WHILE ... \DO ... \OD
  • les boucles "jusqu'à"  avec \UNTIL ...\DO ...\OD
  • les boucles "pour"   avec \FOR  ...\DO ...\OD  on peut utiliser \FROM,\TO et \STEP  pour décrire  le domaine de valeurs à exécuter
  • on peut faire des variantes pour chaque \FOREACH  ou pour tout \ATEACH
J'ai donc francisé ces mot-clés directement dans le fichier program.sty (que j'ai renommé myprogram.sty ), et j'ai modifié leur apparence pour qu'il apparaissent en gras-souligné. Voici ce que ça donne avec l'exemple suivant suivant qu'on appelle \usepackage{program} ou \usepackage{myprogram}  (après avoir placé myprogram.sty dans votre texmf local puis  avoir reconstruit la base des paquests avec texhash :

avec program.sty
avec myprogram.sty
\begin{program}
\text{fonctions et procédures} 
\FUNCT y=|mafonction|(x)
 \text{instruction}
\ENDFUNCT 
\PROC |maprocedure|
 \text{instruction}
\ENDPROC 

\text{Les conditions}
\IF x>0\THEN\text{instruction}
\ELSE \text{instruction}
\FI 
\IF x>0 
\THEN \text{instruction}
\ELSE \text{instruction}
\FI 
\IF x=0 
\THEN \text{instruction}
\ELSIF x>0 \THEN \text{instruction}
\ELSE \text{instruction}
\FI 

\text{Les boucles} 
\FOREACH x\in L \DO
 \text{instruction}
\OD 
\ATEACH x\in L \DO
 \text{instruction}
\OD <
\FOR x=1\TO n \DO
\text{instruction}
\OD 
\WHILE x>0\DO
\text{instruction}
\OD
\end{program}




Pour être utilisées les commandes qui décrivent l'algorithme doivent être placé dans l'un des environnements  suivant :
  • \begin{program} ....\end{program} 
  • \begin{programbox} ....\end{programbox} 
le deuxième  correspond en fait à un environnement \begin{program} ....\end{program}; encapsulé dans un \begin{minipage}[t]{\textwidth}....\end{minipage} , l'intérêt de "programbox"   est de faciliter l'ajout de boîtes autour d'un algorithme, par exemple avec le package fancybox :
\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\usepackage{amsmath,amssymb,fancybox,myprogram}
\begin{document}

\doublebox{
\begin{programbox}
\FUNCT [Dist,Pred]=|DIJKSTRA|(G,s) 
\text{\bf Initialisations }:
n=\text{nombre de sommets du graphe }G
Pred= \text{tableau des prédécesseurs initialisé à 0}
Dist= \text{tableau des distances initialisé à $+\infty$}
Dist(s)=0
W= \text{matrice des poids des arcs ($\infty$ si l'arc n'existe pas)}
C=\{1,2,\dots,n\}\text{ (liste des sommets restant à traiter)}
\text{\bf Traitements }:
\WHILE C\neq \emptyset\DO 
x=\text{sommet de $C$ le plus proche de $s$}
\text{  retirer le sommet $x$ de la liste $C$}
\FOREACH\ \text{sommet }y\in C\ \DO
 \IF Dist(x) + W(x,y)<Dist(y) 
\THEN \text{modifier $Dist(y)$ et } Pred(y) 
\FI
\OD
\OD
\ENDFUNCT
\end{programbox}
}
\end{document}
tout le contenu de l'algorithme  est considéré comme étant en mode mathématique, c'est très pratique pour moi mais quand on veut  insérer des phrases  en bon français il faut obligatoirement les encapsuler dans dans une commande \text{...}. A noter aussi le caractère "|"  à été redéfinit pour servir de délimiteur  (pour  changer la font des noms de procédure/fonctions) il faut donc utiliser \vert  à la place.

Quelques bugs

    La seule grosse différence avec le package d'origine  est liée à un bug apparu lors de la génération de version html de mes documents . Ce problème est lié  à l'usage de caractères accentués   dans les commentaires  des algorithmes , la présence de é ou è  produisait des effets de bord incompréhensibles au premier abord avec htlatex/tex4ht,  mais que j'ai pu élucider  suite à une discussion sur le groupe fr.comp.text.tex . En fait il s'agissait d'un problème  liée à une redéfinition des commandes \' et \`  (par l'auteur du package program.sty) pour obtenir des guillemets '' et `` ce qui produisait des interférences avec les tabulations qui servent à formater l'algorithme.  J'ai donc supprimé cette partie du code, ainsi qu'une autre qui redéfinissait le ";" et posait des problèmes entre autre avec le package vaucanson-g  (que j'utilise pour dessiner des automates).  Il s'agit des lignes 67 à 93 :
    %%%%%%%%%%%%%%%%%%%partie supprimée  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %%% cette partie provoque des problèmes avec les ; en mode maths       %%%
    %%%  en particulier avec vaucanson-g                                   %%%
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % Set up ";" to add a thick maths space after it when active in math mode:
    %\let\@semicolon=;
    %\catcode`\;=12\relax
    %\mathcode`\;="8000 % Makes ; active in math mode
    %{\catcode`\;=\active \gdef;{\ifmmode\semicolon\;\else\@semicolon\fi}}
    %\mathchardef\semicolon="603B
    %%%%%%%%%%%%%%%%%%%%%partie supprimée  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
    %%%%%%%%%%%%%%%%%%%partie supprimée  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %%% cette partie provoque des problèmes avec les caractères accentués  %%%
    %%% (y compris encapsulé dans \textrm{}) en particulier avec tex4ht    %%%
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % Set up ` so that ``...'' typesets the string in tt (in math mode):
    %\mathcode`\`="8000 % Makes ` active in math mode only.
    %{%\catcode`\'=\active 
    % \catcode`\`=\active
    % \gdef`{\startstring@}
    %}
    %\newif\ifMathsModeStrings \MathsModeStringsfalse
    %\def\startstring@`#1''{\ifMathsModeStrings
    %    \mbox{``}#1\mbox{''}\else
    %    \mbox{``{\tt #1}''}\fi}
    %%%%%%%%%%%%%%%%%%%%%partie supprimée  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
    Un autre bug que vous rencontrerez si vous souhaitez générer des versions html de documents avec htlatex :  vous aurez systématiquement une erreur dès le premier environnement program
    ! Undefined control sequence.
    \gt:tab ...terassignment \gt:tb \tmp:cnt =\ln:tab 
                                                      \space 0//
    l.13 
         
    ? 
    ! Undefined control sequence.
    \n:@stopline: ...p:dim \xdef \locs:tab {\locs:tab 
                                                      \space \pt:int \tmp:dim }\...
    l.13 
    Pour contourner ce problème j'ai modifié l'environnement \begin{programbox} ....\end{programbox} pour qu'il soit interprété comme une formule mathématique, en conséquence htlatex le transformera en image ce qui supprime le problème ! Voici la modification lignes177 à 186
    % - version which puts the whole program in a box.
    \newif\if@programbox \@programboxfalse
    \newenvironment{programbox}%
        {$$\begin{minipage}[t]{\textwidth}%ajout du $$
         \@programboxtrue
         \begin{program}}%
        {\end{program}%
         \@programboxfalse
         \end{minipage}$$%ajout du $$ 
    }
    
    La contrepartie  c'est que toutes les programbox seront transformées par tex4ht en images  ....

    4 commentaires:

    1. Bonjour,

      Bravo pour votre travail sur le fichier program.sty. J'aimerais l'utiliser pour un projet mais mon professeur utilise un autre formalisme. As-tu été loin dans la programmation de packages et si oui, te rappelles-tu de sources intéressantes ?

      Sinon, je ne retrouve pas ton travail sur internet (hormis sur le google drive). L'as-tu mis sur github ? Serait-il possible de proposer des améliorations ?

      Cordialement,

      BICHE Rémi

      RépondreSupprimer
      Réponses
      1. Merci Rémi pour le commentaire, pour être honnête je rappelle que l'origine des modifications du package program.sty vienne d'une discussion que j'avais lancé sur fr.comp.text.tex :
        https://groups.google.com/d/msg/fr.comp.text.tex/H2rcvFHCq0w/QK5z_JwymeIJ
        Il n'est pas sur github, je ne pensais pas que ça intéresserait quelqu'un plus que ça et je ne comptais faire de développement supplémentaires car ça correspond à mes besoins . Mais pourquoi pas le mettre sur github si ça t'intéresse!

        Pour le reste : j'utilise beaucoup LaTex mais, comme beaucoup, je n'ai jamais appris les bases de la programmation en TeX. Pour combler cette lacune j'ai commencé à lire l'excellent livre Apprendre à programmer en TeX . Vraiment formidable ce livre, je comprend mieux certaines choses qui m'étaient complètement obscures quand je "bidouillait" avec myprogram.sty .

        Supprimer
    2. Voilà, c'est disponible sur github (licence GNU V3 comme le package d'origine) :https://github.com/rouxph/myprogram

      RépondreSupprimer
      Réponses
      1. Je te remercie pour les informations, je comprends petit à petit l'esprit du code (A coup d'essais erreur).

        J'ai réussi à afficher un résultat qui me convient mais la méthode n'est pas pratique (ajout de \tab dans le main.tex). Je chercherai à une solution fiable ce week-end si j'en ai le temps.

        Supprimer

    Pour écrire des formules mathématiques vous pouvez utiliser la syntaxe latex en mettant vos formules entre des "dollars" $ \$....\$ $ par exemple :
    - $\sum_{n=1}^\infty {1\over n^2}={\pi^2\over 6}$ s'obtient avec \sum_{n=1}^\infty {1\over n^2}={\pi^2\over 6}
    - $\mathbb R$ s'obtient avec {\mathbb R} et $\mathcal D$ s'obtient avec {\mathcal D}
    - pour les crochets $\langle .,. \rangle$ dans les commentaires utilisez \langle .,. \rangle
    vous pouvez écrire du html dans les commentaires :
    - italique <i> ... </i> gras <b> ... </b>
    - lien <a href="http://adresse "> .... </a>