Tutorial Utiliser Daemon Tools pour émuler une image ISO
Par ZebulonBof_27 dans Informatique le 11 Décembre 2008 à 12:34
Bonjour et bienvenue !

Nous allons aujourd’hui détailler les fonctions de daemontools qui est un petit programme servant à émuler des images d’un contenu quelconque provenant d’un CD ou d’un DVD.

Introduction à Daemon Tools :

Tout d’abord, qu’est-ce qu’une image ?

Une image est une copie parfaite d’un CD ou d’un DVD. C’est en général 1 ou 2 fichiers. Si il y a deux fichiers, il y en a un avec les informations du format et l’autre avec le contenu, s’il n’y en a qu’un seul, il s’agit d’un fichier qui contient entièrement votre support CD ou DVD.

Une image se présente souvent avec l’extension .ISO, .NRG pour Nero, (.CUE & .BIN), (.SUB & .CCD) pour clone cd, .IMG, etc. …

Qu’est-ce qu’émuler une image ?

Emuler une image est en fait tout à fait explicite puisque daemontoolz va créer un lecteur virtuel. (Imaginez que vous venez de brancher un second lecteur cd). Une nouvelle lettre apparait donc (exemple G:). Maintenant, daemontools va vous permettre d’ouvrir une image dans ce lecteur virtuel (voyez ici l’image comme un cd qui est mis dans un lecteur cd).

Voici un bref résumé de la manière dont il faut percevoir les choses. En clair l’utilité de Daemon Tools et d’avoir des CD virtuels qui sont les images ISO, BIN, … mais avec l’avantage de ne pas user de supports. Vous pouvez garder l’image sur votre disc dur !

Se procurer et installer Daemon Tools :

Commencez par télécharger le programme (freeware) en question :

Telecharger

Lancez l’installation ! Juste avant la fin de l’installation il va vous demander de redémarrer votre machine. Ce redémarrage est nécessaire puisqu’il va vous configurer le lecteur virtuel. Redémarrez donc, l’installation se termine.

3) Utiliser Daemon Tools pour émuler une image :

Commencez par lancer daemontools :
Si tout se passe bien, une

icône

avec un disque cassé se crée dans votre barre système (en bas à droite de votre écran). Cliquez avec le bouton droit dessus, cette fenêtre apparait :

C’est le menu

Virtual CD/DVD-ROM

qui va nous intéresser pour l’instant

C’est parti ! Alors allons faire un petit tour dans le menu de cette fenêtre :
C’est simple. Si vous voulez émuler une seule image, il suffit d’activer un seul lecteur virtuel et c’est justement à ça que sert ce menu ! Veillez donc à ce que

1 drive

soit coché en cliquant dessus

Vous venez d’activer votre premier lecteur virtuel (si ca n’avait pas été fait par défaut après l’installation). Vous avez deviné que vous pouvez faire l’inverse pour le désactiver j’espère en cliquant sur

Disable

.

Si vous retournez maintenant sur le menu

Virtual CD/DVD-ROM

, vous verrez apparaitre

2 options supplémentaires

:
- Unmount All Drives
Nous allons utiliser le premier. Rendez-vous donc dans :
Vous allez maintenant mettre en place dans Daemon Tools votre image afin qu’il la lise. Pour cela, cliquez sur

Mount Image.

Une fenêtre apparait et vous pouvez visiter tout votre disque dur. Cherchez maintenant après l’emplacement ou se trouve votre image. Pour mon exemple, je vais choisir une image que j’ai créée à partir d’un CD de Nero Burning Rom. Pour créer une image, c’est un autre tutoriel. Quand vous l’avez

sélectionné

, cliquez sur

Ouvrir

!

Et voila, vous venez d’insérer votre cd dans votre lecteur, euuuuhhh pardon, vous venez d’émuler votre image avec Daemon Tools et oui ca donne le même résultat. L’

autorun

se lance comme si c’était un CD ou DVD :

Vous pouvez bien sure

accéder au contenu

de votre image émulée dans votre explorateur Windows simplement comme s’il s’agissait d’explorer un CD. Allez visiter le

Poste de Travail

à la recherche du

lecteur virtuel

que vous avez créé tout à l’heure et qui portera le nom de l’image que vous avez émulé

Et voila, c’est fini. Et quand vous avez envie de changer d’image dans le lecteur virtuel ou bien simplement l’éjecter comme s’il s’agissait d’un CD, vous cliquez sur

Unmount All Drives

qu’on a vu tout à l’heure

Si maintenant vous voulez désactiver un lecteur virtuel, il suffit de faire

disable

comme montré au début

Voila, bon amusement et bonne économie de supports CD et DVD !
votre commentaire
Unpacker un fichier protéger par upx

Par ZebulonBof_27 dans Cours de Cracking le 4 Décembre 2008 à 18:37

Théorie

Bonsoir messieurs-dames, aujourd'hui c'est Manual Unpacking au menu...Alors, qu'est ce que c'est que ce terme bizarre (mais qui claque bien quand on le sort dans une conversation ; - ) ???! La manual Unpacking, c'est le fait de unpacker ( = décompresser) un executable manuellement (executable qui a donc été compressé et / ou crypté par un certain unpacker). Le fait de packer un logiciel (le compresser si vous préferez) permet de réduire notablement la taille de celui-çi, il peut aussi permettre de crypter certaines parties du code.
Dans le cas qui nous interesse, je vais vous expliquer grosso modo comment marche le célèbre Unpacker UPX, comment décompresser manuellement la plupart des logiciels que vous rencontrerez qui seront packé avec UPX, et je vous redirigerais vers la partie Pratique de la section cracking pour étudier la manual Unpacking sur un vrai logiciel (pour ensuite pouvoir le cracker ; - ). Je vous préviens tout de suite, la première lecture de cette partie théorique risque d'être un peu difficile. Mais ne vous inquiétez pas, la partie Pratique vous permettra de comprendre parfaitement toutes les manip à effectuer.

Principe de fonctionnement de UPX

Le principe général d'un packer est de rechercher les redondances (codes répétés plusieurs fois) de codes hexadécimaux dans le fichier à compresser et de les remplacer par un code plus "concis" quand l'opération est possible.
UPX n’a pas un but de protection, mais de compression.Mais vous remarquerez quand même que lorsqu'un programme est packé avec UPX les Strings Data Reference n'apparaissent plus dans Windasm ou Olly, conséquence direct du package... Avouez que c'est embêtant pour cracker un log ; - ) .
Une fois compressé, le packer doit être invisible pour l'exécutable; c'est-à-dire que le fonctionnement principal du log doit être inchangé. Or le logiciel reste illisible tant qu’il n’a pas été décompressé. En fait quand vous packez un programme avec UPX, celui-ci va intégrer une partie de code appelé le Loader et modifier l'Original Entry Point ( offset ou démarre le code du logiciel) vers ce Loader pour que se soit lui qui se charge en premier lors du lancement du log. Le Loader dispose de la routine de "décryptage" pour décompresser le code du log, une fois la routine terminée le log sera complètement décompressé dans la RAM (mémoire vive) et le logiciel fonctionnera comme auparavant, comme si le package avec UPX n'avait jamais eu lieu. Vous constaterez donc le désavantage principal du package : c'est le temps d'execution du logiciel (augmenté par la routine de décryptage) au détriment de la taille de l'.exe (diminué par la compression).

Unpacker manuellement un logiciel compressé avec UPX

Le loader :

La routine du Loader est facilement repérable dans le cas de UPX : Lé début du loader commence par l'instruction PUSHAD et se termine par l'instruction POPAD. Comme je l'ai déjà dit le packer ne doit pas interférer avec le fonctionnement initial du programme, il est donc obligé de sauvegarder la valeur de tous les registres avant son exécution, et de les restaurer une fois qu’il a fini la décompression. La fonction permettant de sauvegarder tous les registres est PUSHAD (il pousse tous les registres dans la pile) , la fonction permettant de les récupérer est POPAD (restaure tous les registres).
Concrètement le Loader se présente donc sous cette forme :

Après l'intruction POPAD il y a toujours un jump vers l'OEP ( Original Entry Point ), pour que vous compreniez bien, cela veut dire que tout de suite après la routine de décompression il ya un jump vers l'OEP (en l'occurence à l'offset 004D7C14) pour donner la main au programme originel pour qu'il s'execute comme si la compression n'avait jamais existée...

Le dump :

On arrive au point essentiel. Une fois la décompression complété, le jump est effectuée et le log se lance normalement. La méthode pour récuperer le programme entierement décompressé est de :

Poser un breakPoint sur le jump vers l'OEP (jump 004D7C14);
Lancer le logiciel jusqu'à ce qu'il break;
Faire un dump, c'est-à-dire faire une copie du programme en mémoire dans un fichier. On peut faire cela facilement avec des logiciels comme ProcDump ou encore LordPE. Le fichier qu'on obtiendra sera le dump du programme compressé.

Correction de l'EP :

A partir de cette étape il y a encore quelques modifications à faire pour que le programme fonctionne. L'EP (Entry Point) du dump doit être modifié, en effet, elle pointe encore vers le Loader; or nous n'avons plus besoin du loader dans le dump. Le but maintenant, c'est de modifier l'adresse de l'EP pour que le programme commence son execution au bon endroit. ProcDump ou encore LordPE vous permettrons également de faire cela. L’entry-point se calcule en faisant la valeur de l’OEP ( en l'occurence à l'offset 004D7C14) moins celle de l’ImageBase... On verra ça plus en profondeur dans la partie pratique...

Reconstruction de l'IAT :

Pour pouvoir rendre le log 100 % fonctionnel, il faut reconstruire l'IAT. Qu'est ce que c'est que ça ????! Me direz vous... Sans rentrer dans les détails, l'IAT comporte 2 tableaux dans lesquels sont repris les dll utilisées ainsi que les adresses en mémoire des fonctions quelles proposent. L' IAT de l'exécutable sur le disque (le programme packé) n'est pas le même qu'en mémoire (le dump). Sur le disque, un des 2 tableaux contient le nom des fonctions, lorsque le loader du système d'exploitation charge le programme en mémoire, il remplace ces noms par les adresses en mémoire des fonctions correspondantes. Donc l'IAT recopié tel quel dans la mémoire n'est plus valide. Il faut donc le reconstruire. Au-dela de la compréhension global du problème (qui peut paraître assez flou au premier abord), la reconstruction de l'iAT est en elle-même assez simple. On utilise pour cela un logiciel comme ImpREC qui se charge de faire cela pour nous.

Placement de l'EP dans la bonne section :

A partir de là, le programme est fonctionnel, vous pourrez le lancez sans problème. Mais si vous voulez manipuler le dump dans un debuggeur comme Olly il faudra faire une petite modif en plus : Les sections du log n'étant plus alignées il vous faudra relancer PE Editor pour replacer l'EP dans la bonne section...

Et voilà, à partir de là, votre programme devrait fonctionner sans problème et vous pourrez manipuler le dump sans problème dans votre debuggeur préféré ; - ).

On récapitule la méthode :

* On trouve l'adresse de l'OEP (situé juste après l'instruction POPAD);
* On dump le programme (en breakant bien sur je jump vers l'OEP);
* On redéfinit l'adresse de l'EP (à l'aide de l'OEP trouvé précédemment);
* On reconstruit l'IAT pour que le log puisse retrouver les adresses des fonctions utilisées (dans les dll) par le log;
* On replace l'EP dans la bonne section pour permettre le break sur l'EP.

Pourquoi ne pas utiliser UPX Shell ?

Je voulais juste rajouter une petite précision qui a son importance. Pourquoi chercher a décompresser manuellement un programme compressé par UPX alors que des logs comme UPX Shell le font automatiquement. Et bien il arrive parfois que la décompression avec ce genre de prog ne se fasse pas correctement. Dans ce cas, il faut tout faire "à la main". D'ailleurs c'est ce qu'il se passera dans la partie Pratique de ce tuto ... De plus, vous êtes pratiquement sur que la décompression se sera bien déroulée. Et entre nous, une fois que vous aurez assimilé la méthode il vous faudra moins de 5 minutes pour unpacker n'importe quel programme ! ; - p

Prérequis

Logiciels necessaires :

Excel Password DiscoveryExcel Password Discovery
LordPE DeluxeLordPE Deluxe
ProcDump v1.62ProcDump v1.62
ImpRECImpREC
OllydbgOllydbg
Stud PEStud PE
UPX Shell (facultatif)
UPXUnpack (facultatif)

But du tuto :
Le but de ce tuto est d'appliquer concrètement les méthodes citées dans le tuto sur le manual unpacking. On va unpacker manuellement le programme Excel Password Recovery pour faire apparaitre les Strings Data Reference.

Excel Password Recovery est un logiciel de brute-forcing pour les fichiers excel protégés par mot de passe ; - ) . Un programme qui peut toujours servir... PS : si vous n'avez pas lu la partie théorique sur le manual unpacking faîtes le en allant ici, sinon vous n'allez rien comprendre : - ).

Unpacker automatiquement le logiciel

De l'organisation ! Bon je commence par un petit point sur l'organisation du travail. Si vous avez un minimum l'habitude de cracker un log passez cette partie. Pour les autres je vous conseille de répartir votre travail comme ceci :

Vous vous rendez à l'adresse ou se trouve le logiciel, vous créez deux dossiers, un nommé crack, l'autre back up. Dans le dossier back up faîtes une copie de uepwdr10l.exe, si vous faîtes une mauvaise manip vous pourrez récupérer l'exe à partir de ce dossier. Copiez également l'exe dans le dossier crack, c'est dans ce dossier que vous ferez les manipulation de unpackage et de crack. Voilà, si vous êtes un peu bordélique essayez de vous organiser comme ceci à chaque fois que vous devez cracker un log.

Test de décompression automatique :

Installez Excel Password Recovery ... Rendez-vous dans le dossier de l'executable (par défault C:\Program Files\Intelore\Excel-Password). Comme d'hab on lance StudPe (clique droit sur l'executable uepwdr10l.exe » Stud PE Analyse ). Dans l'onglet Signature on voit :

Le programme a subit une compression UPX, quel suprise !!!! ; - )

Test avec UPX Shell :

On va d'abord essayer de le décompresser avec un logiciel fait pour ça... Commencons par exemple par UPX Shell (lien pour le télécharger au dessus).Dons installez le, dans l'onglet Ouvrir un fichier cliquez sur le bouton "ouvrir" et aller chercher l'exe. Ensuite, dans l'onglet décompression cliquez sur le bouton :

Nommez l'exe unpacké uepwdr10l_unpack.exe par exemple...si vous le pouvez, car vous remarquez que la décompression ne se fait pas !!!! Bizarre n'est ce pas...

Test avec UPX Unpack :

Bon ba, on va essayer avec UPX Unpack. Installer le, lancez le, sélectionnez l'exe,lancez la décompression.... Vous devez obtenir ceci :

Comme vous le voyez, on dirait que la reconstruction de l'IAT ne s'est pas fait correctement, par conséquent le programme ainsi décompressé est inutilisable !!! Qu'à cela ne tienne, on va se le décompresser manuellement eh eh eh !!

Unpacker manuellement le log

Detection du Loader et Détermination de l'OEP :

On va unpacker le logiciel à l'aide de Olly bdg cette fois-çi (équivalent à Windasm mais plus puissant).Installez le si ce n'est pas déja fait, ouvrez le et importez uepwdr10l.exe à partir de l'onglet File » Open. Si Olly affiche une messageBox validez en appuyant sur le bouton "oui". Il nous faut donc chercher le Loader. Générallement il se trouve tout à la fin. En effet vous remarquez le PUSHAD à l'offset 0053EAB0 et le POPAD à l'offset 0053EC12, suivit d'un jump vers l'offset 004D7C14 (qui correspond donc à l'adresse de l'OEP. Donc notez bien cette offset :

Créer un Dump :

On va charger le logiciel dans la RAM. Pour se faire, rappelez vous la partie théorique : on pose un break sur le jump, en l'occurence à l'adresse 0053EC13 : double-cliquez sur la ligne dans la 2ème colonne pour poser le break (sur .-E9 [...]). La ligne d'offset devrait alors rester en surbrillance. Lancez l'.exe en cliquant sur le bouton "lecture". Le programme break alors.
Maintenant il vous faut installer, LordPE Deluxe... Lancez le et cherchez le programme uepwdr10l.exe dans la listView. Si vous ne le trouvez pas, pas ne panique (ça me le fait aussi sous XP). Dans ce cas téléchargez ProcDump, lancez le et cette fois-çi vous devrez voir apparaître uepwdr10l.exe dans la ListView. Pour info, PorcDump et LordPe sont 2 programmes pratiquement similaires (même interface, même option, ect...); donc quand je vous demanderais d'utiliser LordPe vous pourrez également utiliser ProcDump pour faire la même opération...
Une fois que vous avez trouvé uepwdr10l.exe, faîtes un clic droit dessus » Dump (Full) :

Une nouvelle fenêtre, vous permettant de nommer le dump; appelez le uepwdr10l_decomp.exe. Un message devrait apparaitre pour vous dire que le dump a bien été crée. Vous pouvez essayer de lancer le dump, et vous verrez que ça marche pas, ce qui est normal : - ) . Vous devez donc avoir ceci :

Correction de l'EP :

Toujours dans LorpPe cliquez sur le bouton "PE Editor" et sélectionnez le fichier dumpé, une nouvelle fenêtre s'ouvre; on va pouvoir modifier l'EP a partir de cette fenêtre :

Vous pouvez voir l'adresse de l'EP, et l'adresse de l'image. On va calculer l'OEP. Donc ouvrez la calculatrice windows : Demarrer » executer » commande calc... Onglet affichage » scientifique. Selectionnez également Hex (pour Hexadécimal)...
Calcul de l'OEP = Jump de l'Entry Point (qu'on a noté au début) - Image Base.
Donc OEP = 0013EAB0 - 00400000 = D7C14 = 000D7C14.
Donc remplacez la valeur actuelle de l'Entry Point (0013EAB0) par 000D7C14. Cliquez sur OK vous valider les changements. Vous pouvez fermer Lord PE (ou ProcDump) ansi que Olly.

Reconstruction de l'IAT :

Pour reconstruire l'IAT on va utiliser ImpREC. Donc téléchargez-le, installez le et lancez le. Vous obtenez cette fenêtre :

PS : la fenêtre ci-dessus est représenteé lorsque l'IAT a été reconstruit...
Lancez uepwdr10l.exe normalement (le log décompressé) pour qu'il apparaisse en mémoire, puis lancez ImpREC. Ensuite faîtes comme ceci :
1 - Selectionnez uepwdr10l.exe dans la liste déroulante.
2 - Modifier la valeur de l'OEP par notre EP calculé précédemment (000D7C14).
3 - Cliquez sur le bouton "IAT AutoSearch". Si tout se passe bien, une MessageBox devrait s'afficher.
4 - Cliquez sur le bouton "Get Imports". La liste va se remplir avec les APIs utilisées par le programme.
5 - Cliquez sur le bouton "Fix Dump", sélectionnez le fichier dumpé (uepwdr10l_decomp.exe). ET voilà !!!! Le fichier final sera nommé comme ceci : uepwdr10l_decomp_.exe.

Placement de l'EP dans la bonne section :

Il nous reste une dernière opération pour pouvoir utiliser l'executable décompressé dans un debuggueur comme olly. Pour l'instant si vous essayez de l'ouvrir dans Olly vous obtiendrez ceci :

Pour réaligner les sections il vous faut utiliser impérativement LordPE (cette manipulation ne marche pas avec ProcDump). relancez donc LordPe, puis cliquez sur le bouton " PE Editor" et sélectionnez votre programme dumpé. Cliquez sur "sections" et regardez par rapport au VOffset dans quelle section doit se trouver l'EP :

Je vous rappelle que l'adresse de l'EP est D7C14, donc par rapport au VOffset (correspondant à l'adresse de départ du secteur, la fin du secteur étant désigné par le VOffset du prochain secteur) :
1000 < D7C14 < DA000
L'EP doit donc être situé sur le secteur EPRX. Fermez cette fenêtre et dans la fenêtre précédente remplacez la valeur de BaseOfCode par le VOffset du début de la section dans laquelle se trouve l'EP, c'est-à-dire 1000 dans ce cas...Cliquez ensuite sur Save pour appliquer les changement... vous pouvez fermer Lord Pe.

Maintenant essayez de lancer uepwdr10l_decomp_.exe. Et voilà,le prog se lance normalement, vous pouvez refaire une analyse de l'exe avec Stud Pe pour vous apercevoir que le programme a été programmé avec Borland Delphie v6 à 7, et vous remarquerez également que le fichier dumpé fait environ 1,27 mo ( pour 426 ko pour l'exe original).Allé dîtes le maintenant : "Je suis un fou! Un psychopathe ! Faut pas me résister, je suis dangereux moi !!!"...Un peu de modestie s'il-vous-plais quand même ; - p
Vous pourrez maintenant cracker le log normalement. Ce tuto étant réservé au manual Packing je m'arrête là pour aujourd'hui, mais vous pouvez toujours essayez de cracker Excel Password Recovery si vous vous en sentez capable ; - ) .
Allé ciao, et à bientôt pour un prochain tuto de cracking !!!!

votre commentaire
Les nombres premiers et leur rôle dans la cryptographie moderne

Par ZebulonBof_27 dans Cryptographie le 3 Décembre 2008 à 21:09

Les nombres premiers et leur rôle dans la cryptographie moderne

Les nombres premiers

Définition et conséquences :

Un nombre premier est un entier strictement supérieur à 1, qui admet exactement deux diviseurs distincts.

Si p est un nombre premier alors ses seuls diviseurs sont 1 et p.

(En arithmétique, 1 n'est pas considéré comme un nombre premier pour des raisons de commodité.)

Exemples :

2, 3, 5, 7 et 40390761282604429748980603 sont des nombres premiers

4, 6 1024 et 1947626044289806032 ne sont pas des nombres premiers

A propos de l'ensemble des nombres premiers... :

Il existe une infinité de nombres premiers.

Euclide est l'auteur de la démonstration la plus simple de ce résultat :

Supposons donc choisi un nombre premier p, p > 5, et formons le produit 2 ´3 ´5 ´... ´p, de tous les nombres premiers compris entre 2 et p, puis posons :

N = (2 ´3 ´5 ´... ´p) + 1.

N étant strictement supérieur à 2, N admet un diviseur premier. Soit q ce diviseur.

Or aucun des nombres de la liste 2, 3, 5, ..., p, n'est un diviseur de N car le reste de la division de N par un nombre quelconque de cette liste est toujours 1.

Donc q est strictement supérieur à p.

Donc si on choisi un nombre premier quelconque, on trouve toujours un nombre premier qui lui est strictement supérieur. Il en résulte que le suite des nombres premiers est infinie.

Note : Il existe plusieurs autres démonstrations de ce théorème. Citons celle d'Euler (1737), de Polya (1920), d'Erdös (1938). Aucune n'est plus simple que celle d'Euclide. Celle d'Euler a le mérite de montrer, pour la première fois, que l'Analyse permet de démontrer des résultats sur des nombres entiers. Cette première incursion de l'Analyse dans l'Arithmétique se mua au XIX^e siècle en une véritable invasion pour créer la branche des mathématiques que l'on appelle aujourd'hui la théorie analytique des nombres.

Par ailleurs, les mathématiciens s'intéressent depuis longtemps aux questions suivantes :

La répartition des nombres premiers dans la suite des naturels est-elle régulière ?

Présente-t-elle des particularités intéressantes ?

Ils sont arrivés à la conclusion que cette répartition était plutôt anarchique, que globalement, la proportion des nombres premiers va en décroissant. Plus précisément, si l'on note suivant l'usage p (x) le nombre de nombres premiers inférieurs à un réel x, alors p (x) est un infiniment grand équivalent "au voisinage de l'infini" à x / ln x.

Ce résultat a été démontré par Tchebychev en 1896 à partir de conjectures de Legendre (1785) puis de Gauss.

Les nombres premiers sont une perpétuelle source de recherche pour les savants. Bien que définis de manière simple ils sont l'objet d'analyses théoriques forts complexes et depuis la mise en place d'algorithmes nécessitant des nombres premiers en cryptographie, ils représentent un réel enjeu actuel. Et ce à tel point que de mystérieux mécènes sont prêts à débourser des sommes considérables pour stimuler la recherche dans ce domaine et obtenir des résultats exploitables.

Nombres premiers et cryptographie

Définition

La cryptographie est la science qui cherche à fabriquer des codes secrets, à trouver le code de messages secrets. Aujourd'hui, grâce aux performances de plus en plus élevées des ordinateurs, elle intervient dans tous les domaines de la sécurité militaire mais aussi civile.

Vocabulaire

Le chiffrement consiste à traduire un message donné en langage codé.

Le déchiffrement consiste reconstituer le message initial à partir d'un message codé lorsqu'on connaît le code.

Le décryptage est la recherche d'une méthode qui permet de trouver le code inconnu.

Quelques exemples

Le code dit de Jules César

On remplace une lettre de l'alphabet naturel par la lettre qui la suit dans l'alphabet (A ® B, B ® C, ..., Z ® A, ).

Note : Ce code fut utilisé par l'armée romaine, lors des guerres expansionnistes menées par l'Empire.

Le code Enigma

On dispose d'une clé secrète, facile à retenir, par exemple, MATH, qui fournit la suite (13, 1, 20, 8) obtenue à partir de la position des lettres dans l'alphabet. On code alors le message à envoyer en joutant 13 points à la première lettre du message (transmission en Morse), 1 point à la seconde, 20 à la troisième, 8 à la quatrième, ainsi de suite en recommençant.

Note : Ce type de codage fut utilisé pendant la Seconde Guerre mondiale par l'armée allemande. La machine Enigma avait été conçue en 1923 par l'ingénieur Arthur Scherbius. Son code fut brisé en 1943 grâce aux travaux d'Alan M. Turing et à la construction des célèbres calculateurs Colossus par l'armée britannique.

Cryptographie moderne : le système RSA

Cette méthode a été inventée en 1978 par trois mathématiciens, Rivet, Shamir et Adleman. Elle est originale en ce sens que l'algorithme de chiffrement et la clé sont connus de tous, et cependant une seule personne peut déchiffrer le message.

Elle repose sur les résultats d'arithmétiques suivants que nous admettrons :

Théorème :

Si p et q sont deux nombres premiers distincts, n = pq, h = (p - 1)(q - 1).

Si e est un entier, e Î ]1, h[, et e premier avec h.

Alors, il existe un unique entier d Î ]1, h[ tel que ed º 1 [mod h]

Corollaire :

Si b º a^d [mod n], alors a º b^e [mod n]

Fonctionnement de base du système :

Alice, choisit deux nombres premiers p et q, calcule leur produit n = pq, calcul h = (p - 1)(q - 1) et choisit un entier e Î ]1, h[ et premier avec h.

Puis elle rend publique, dans un annuaire, l'information (Alice : n, e).

1) Comment Bob envoie-t-il un message à Alice ?

Alice à choisi p = 13, q = 17 et e = 5, elle communique alors dans l'annuaire ses deux clés publiques n = pq = 221 et e = 5.

Bob veut envoyer à Alice le message "JE T'AIME"

Il l'écrit d'abord sous la forme (10, 5, 0, 20, 27, 1, 9, 13, 5), en utilisant la position des lettres dans l'alphabet (A est la 1ère lettre, ...) et en posant 0 correspondant à l'espace et 27 à l'apostrophe.

Puis Bob élève chaque nombre de la liste à la puissance e = 5 et en prend le reste dans la division par n = 221.

Message initial                                    Message crypté

(10, 5, 0, 20, 27, 1, 9, 13, 5)     Þ     (108, 31, 0, 141, 40, 1, 42, 13, 31)

Bob transmet alors son "message" crypté à Alice.

2) Comment Alice déchiffre-t-elle le message de Bob ?

Alice, qui est la seule à connaître p et q, calcule le nombre d Î ]1, h[ tel que ed º 1 [mod h]. Ici h = 192 et d = 77.

Alice élève alors chaque nombre du message crypté à la puissance d = 77, en prend le reste dans la division par n = 221 et reconstitue le texte original, grâce au théorème énoncé plus haut et à son corollaire.

Message crypté                                    Message initial

(108, 31, 0, 141, 40, 1, 42, 13, 31)     Þ     (10, 5, 0, 20, 27, 1, 9, 13, 5)

Alice retrouve ainsi le message "JE T'AIME" transmis par Bob.

Quelle sera sa réaction ?

Sûreté du système RSA :

Pour crypter en RSA, on utilise les nombres e et n, qui sont les clés publiques du destinataire du message crypté, sans connaître p et q (seul le destinataire les connaît).

Pour déchiffrer le message, le destinataire calcule d, étant le seul à connaître p et q donc h, et reconstitue le message initial.

Pour décrypter un message il est donc indispensable de retrouver p et q connaissant n et e. Or si pour des nombres premiers p et q de quelques dizaines de chiffres il est facile de décomposer n, l'affaire relève de la gageure pour des nombres premiers d'un millions de chiffres.

Ainsi RSA est-il considéré comme un "système de sécurité absolu" pourvu qu'on utilise des "grands" nombres premiers.

La course à la sécurité passe dès lors par la course aux nombres premiers et on comprend que les armées, les banques et autres grands utilisateurs du système RSA ait besoin de nombres premiers démesurés.

En 1993 le plus grand nombre premier connu était 2^{756 839} - 1 qui s'écrit avec 227832 chiffres.

En 1997 le plus grand nombre premier connu était 2^{2 976 221} - 1.

Vous pouvez consulter le site officiel des "records" de grands nombres premiers en cliquant sur ce lien : Site des records de nombres premiers.

votre commentaire
Cours n°12
Par ZebulonBof_27 dans Algorithmique le 3 Décembre 2008 à 20:42
Partie 12
Notions Complémentaires

« Le danger, avec les ordinateurs, ce n’est pas tellement qu’ils deviennent aussi intelligents que les hommes, mais c’est que nous tombions d’accord avec eux pour les rencontrer à mi-chemin » - Bernard Avishai

Une fois n’est pas coutume, ce chapitre ne sera l’objet d’aucun exercice. Cela ne veut pas dire pour autant que ce qui s’y trouve n’est pas intéressant.

Non mais des fois.

1. Programmation structurée

Petit retour sur une notion très rapidement survolée plus haut : celle de « programmation structurée ». En fait, nous avons jusqu’à présent, tels Monsieur Jourdain, fait de la programmation structurée sans le savoir. Aussi, plutôt qu’expliquer longuement en quoi cela consiste, je préfère prendre le problème par l'autre bout : en quoi cela ne consiste pas.

Dans certains langages (historiquement, ce sont souvent des langages anciens), les lignes de programmation portent des numéros. Et les lignes sont exécutées par la machine dans l’ordre de ces numéros. Jusqu’ici, en soi, pas de problème. Mais l’astuce est que tous ces langages, il existe une instruction de branchement, notée aller à en pseudo-code, instruction qui envoie directement le programme à la ligne spécifiée. Inversement, ce type de langage ne comporte pas d’instructions comme FinTantQue, ou FinSi, qui « ferment » un bloc.

Prenons l’exemple d’une structure « Si … Alors … Sinon »

Programmation Structurée
Si condition Alors
instructions 1
Sinon
instructions 2
FinSi

Programmation non structurée
1000 Si condition Alors Aller En 1200
1100 instruction 1
1110 etc.
1120 etc.
1190 Aller en 1400
1200 instruction 2
1210 etc.
1220 etc.
1400 suite de l’algorithme

Vous voyez le topo : un programme écrit dans ce type de langages se présente comme une suite de branchements emmêlés les uns dans les autres. D’une part, on ne peut pas dire que cela favorise la lisibilité du programme. D’autre part, c’est une source importante d’erreurs, car tôt ou tard on oublie un « aller à », ou on un met un de trop, etc. A fortiori lorsqu’on complique un algorithme existant, cela peut devenir un jungle inextricable.

A l’inverse, la programmation structurée, surtout si l’on prend soin de rationaliser la présentation en mettant des lignes de commentaires et en pratiquant l’indentation, évite des erreurs, et révèle sa structure logique de manière très claire.

Le danger est que si la plupart des langages de programmation utilisés sont structurés, ils offrent tout de même la plupart du temps la possibilité de pratiquer la programmation non structurée. Dans ce cas, les lignes ne sont pas désignées par des numéros, mais certaines peuvent être repérées par des noms (dits « étiquettes ») et on dispose d’une instruction de branchement.

Une règle d’hygiène absolue est de programmer systématiquement de manière structurée, sauf impératif contraire fixé par le langage (ce qui est aujourd'hui de plus en plus rare).

Autrement dit, même quand un langage vous offre une possibilité de faire des entorses à la programmation structurée, il ne faut s’en saisir sous aucun prétexte.

2. Interprétation et compilation

Avec ce paragraphe, on sort un peu de l’algorithmique proprement dite pour entrer dans le domaine plus technique de la réalisation pratique. Ou, si l’on préfère, ces dernières lignes sont l’apothéose, le bouquet final, l’extase ultime, la consécration grandiose, de ce cours.

En toute modestie, bien sûr.

Jusqu’ici, nous avons travaillé sur la première étape de la réalisation d’un programme : la rédaction de l'algorithme.

En fait, si l’algorithme est bien écrit, sans faute logique, l’étape suivante ne doit normalement poser aucun problème conceptuel. Il n'y a plus qu'à effectuer une simple traduction.

A partir de là, le travail du programmeur est virtuellement terminé (en réalité, il reste tout de même une inévitable phase de tests, de corrections, etc., qui s'avère souvent très longue). Mais en tout cas, pour l’ordinateur, c’est là que les ennuis commencent. En effet, aucun ordinateur n’est en soi apte à exécuter les instructions telles qu’elles sont rédigées dans tel ou tel langage ; l’ordinateur, lui, ne comprend qu’un seul langage, qui est un langage codé en binaire (à la rigueur en hexadécimal) et qui s’appelle le langage machine (ou assembleur).

C’est à cela que sert un langage : à vous épargner la programmation en binaire (une pure horreur, vous vous en doutez) et vous permettre de vous faire comprendre de l’ordinateur d’une manière (relativement) lisible.

C’est pourquoi tout langage, à partir d’un programme écrit, doit obligatoirement procéder à une traduction en langage machine pour que ce programme soit exécutable.

Il existe deux stratégies de traduction, ces deux stratégies étant parfois disponibles au sein du même langage.
- le langage traduit les instructions au fur et à mesure qu’elles se présentent. Cela s’appelle la compilation à la volée, ou l’interprétation.
- le langage commence par traduire l’ensemble du programme en langage machine, constituant ainsi un deuxième programme (un deuxième fichier) distinct physiquement et logiquement du premier. Ensuite, et ensuite seulement, il exécute ce second programme. Cela s’appelle la compilation
Il va de soi qu’un langage interprété est plus maniable : on peut exécuter directement son code - et donc le tester - au fur et à mesure qu’on le tape, sans passer à chaque fois par l’étape supplémentaire de la compilation. Mais il va aussi de soi qu’un programme compilé s’exécute beaucoup plus rapidement qu’un programme interprété : le gain est couramment d’un facteur 10, voire 20 ou plus.

Toute application destinée à un usage professionnel (ou même, tout simplement sérieux) est forcément une application compilée.

3. Une logique vicelarde : la programmation récursive

Vous savez comment sont les informaticiens : on ne peut pas leur donner quoi que ce soit sans qu’ils essayent de jouer avec, et le pire, c’est qu’ils y réussissent.

La programmation des fonctions personnalisées a donné lieu à l'essor d’une logique un peu particulière, adaptée en particulier au traitement de certains problèmes mathématiques (ou de jeux) : la programmation récursive. Pour vous expliquer de quoi il retourne, nous allons reprendre un exemple cher à vos cœurs : le calcul d’une factorielle (là, je sentais que j’allais encore me faire des copains).

Rappelez-vous : la formule de calcul de la factorielle d’un nombre n s’écrit :

N ! = 1 x 2 x 3 x … x n

Nous avions programmé cela aussi sec avec une boucle Pour, et roule Raoul. Mais une autre manière de voir les choses, ni plus juste, ni moins juste, serait de dire que quel que soit le nombre n :

n ! = n x (n-1) !

En bon français : la factorielle d’un nombre, c’est ce nombre multiplié par la factorielle du nombre précédent. Encore une fois, c’est une manière ni plus juste ni moins juste de présenter les choses ; c’est simplement une manière différente.

Si l’on doit programmer cela, on peut alors imaginer une fonction Fact, chargée de calculer la factorielle. Cette fonction effectue la multiplication du nombre passé en argument par la factorielle du nombre précédent. Et cette factorielle du nombre précédent va bien entendu être elle-même calculée par la fonction Fact.

Autrement dit, on va créer une fonction qui pour fournir son résultat, va s’appeler elle-même un certain nombre de fois. C’est cela, la récursivité.

Toutefois, il nous manque une chose pour finir : quand ces auto-appels de la fonction Fact vont-ils s’arrêter ? Cela n’aura-t-il donc jamais de fin ? Si, bien sûr, rassure-toi, ô public, la récursivité, ce n’est pas Les Feux de L’Amour. On s’arrête quand on arrive au nombre 1, pour lequel la factorielle est par définition 1.

Cela produit l’écriture suivante, un peu déconcertante certes, mais parfois très pratique :

Fonction Fact (N en Numérique)
Si N = 0 alors
Renvoyer 1
Sinon
Renvoyer Fact(N-1) * N
Finsi
Fin Fonction

Vous remarquerez que le processus récursif remplace en quelque sorte la boucle, c’est-à-dire un processus itératif. Et en plus, avec tous ces nouveaux mots qui riment, vous allez pouvoir écrire de très chouettes poèmes. Vous remarquerez aussi qu’on traite le problème à l’envers : on part du nombre, et on remonte à rebours jusqu’à 1 pour pouvoir calculer la factorielle. Cet effet de rebours est caractéristique de la programmation récursive.

Pour conclure sur la récursivité, trois remarques fondamentales.
- la programmation récursive, pour traiter certains problèmes, est très économique pour le programmeur ; elle permet de faire les choses correctement, en très peu d'instructions.
- en revanche, elle est très dispendieuse de ressources machine. Car à l’exécution, la machine va être obligée de créer autant de variables temporaires que de « tours » de fonction en attente.
- Last but not least, et c’est le gag final, tout problème formulé en termes récursifs peut également être formulé en termes itératifs ! Donc, si la programmation récursive peut faciliter la vie du programmeur, elle n’est jamais indispensable. Mais ça me faisait tant plaisir de vous en parler que je n’ai pas pu résister… Et puis, accessoirement, même si on ne s'en sert pas, en tant qu'informaticien, il faut connaître cette technique sur laquelle on peut toujours tomber un jour ou l'autre.
votre commentaire

Cours n°11

Par ZebulonBof_27 dans Algorithmique le 3 Décembre 2008 à 20:34

Partie 11
Procédures et Fonctions

« L’informatique semble encore chercher la recette miracle qui permettra aux gens d’écrire des programmes corrects sans avoir à réfléchir. Au lieu de cela, nous devons apprendre aux gens comment réfléchir » - Anonyme

1. Fonctions personnalisées

1.1 De quoi s'agit-il ?

Une application, surtout si elle est longue, a toutes les chances de devoir procéder aux mêmes traitements, ou à des traitements similaires, à plusieurs endroits de son déroulement. Par exemple, la saisie d’une réponse par oui ou par non (et le contrôle qu’elle implique), peuvent être répétés dix fois à des moments différents de la même application, pour dix questions différentes.

La manière la plus évidente, mais aussi la moins habile, de programmer ce genre de choses, c'est bien entendu de répéter le code correspondant autant de fois que nécessaire. Apparemment, on ne se casse pas la tête : quand il faut que la machine interroge l'utilisateur, on recopie les lignes de codes voulues en ne changeant que le nécessaire, et roule Raoul. Mais en procédant de cette manière, la pire qui soit, on se prépare des lendemains qui déchantent...

D'abord, parce que si la structure d'un programme écrit de cette manière peut paraître simple, elle est en réalité inutilement lourdingue. Elle contient des répétitions, et pour peu que le programme soit joufflu, il peut devenir parfaitement illisible. Or, le fait d'être facilement modifiable donc lisible, y compris - et surtout - par ceux qui ne l'ont pas écrit est un critère essentiel pour un programme informatique ! Dès que l'on programme non pour soi-même, mais dans le cadre d'une organisation (entreprise ou autre), cette nécessité se fait sentir de manière aiguë. L'ignorer, c'est donc forcément grave.

En plus, à un autre niveau, une telle structure pose des problèmes considérables de maintenance : car en cas de modification du code, il va falloir traquer toutes les apparitions plus ou moins identiques de ce code pour faire convenablement la modification ! Et si l'on en oublie une, patatras, on a laissé un bug.

Il faut donc opter pour une autre stratégie, qui consiste à séparer ce traitement du corps du programme et à regrouper les instructions qui le composent en un module séparé. Il ne restera alors plus qu'à appeler ce groupe d'instructions (qui n'existe donc désormais qu’en un exemplaire unique) à chaque fois qu’on en a besoin. Ainsi, la lisibilité est assurée ; le programme devient modulaire, et il suffit de faire une seule modification au bon endroit, pour que cette modification prenne effet dans la totalité de l’application.

Le corps du programme s’appelle alors la procédure principale, et ces groupes d’instructions auxquels on a recours s’appellent des fonctions et des sous-procédures (nous verrons un peu plus loin la différence entre ces deux termes).

Reprenons un exemple de question à laquelle l’utilisateur doit répondre par oui ou par non.

Mauvaise Structure :

...
Ecrire "Etes-vous marié ?"
Rep1 ← ""
TantQue Rep1 <> "Oui" et Rep1 <> "Non"
Ecrire "Tapez Oui ou Non"
Lire Rep1
FinTantQue
...
Ecrire "Avez-vous des enfants ?"
Rep2 ← ""
TantQue Rep2 <> "Oui" et Rep2 <> "Non"
Ecrire "Tapez Oui ou Non"
Lire Rep2
FinTantQue
...

On le voit bien, il y a là une répétition quasi identique du traitement à accomplir. A chaque fois, on demande une réponse par Oui ou Non, avec contrôle de saisie. La seule chose qui change, c'est le nom de la variable dans laquelle on range la réponse. Alors, il doit bien y avoir un truc.

La solution, on vient de le voir, consiste à isoler les instructions demandant une réponse par Oui ou Non, et à appeler ces instructions à chaque fois que nécessaire. Ainsi, on évite les répétitions inutiles, et on a découpé notre problème en petits morceaux autonomes.

Nous allons donc créer une fonction dont le rôle sera de renvoyer la réponse (oui ou non) de l'utilisateur. Ce mot de "fonction", en l'occurrence, ne doit pas nous surprendre : nous avons étudié précédemment des fonctions fournies avec le langage, et nous avons vu que le but d'une fonction était de renvoyer une valeur. Eh bien, c'est exactement la même chose ici, sauf que c'est nous qui allons créer notre propre fonction, que nous appellerons RepOuiNon :

Fonction RepOuiNon() en caractère
Truc ← ""
TantQue Truc <> "Oui" et Truc <> "Non"
Ecrire "Tapez Oui ou Non"
Lire Truc
FinTantQue
Renvoyer Truc
Fin

On remarque au passage l’apparition d’un nouveau mot-clé : Renvoyer, qui indique quelle valeur doit prendre la fonction lorsqu'elle est utilisée par le programme. Cette valeur renvoyée par la fonction (ici, la valeur de la variable Truc) est en quelque sorte contenue dans le nom de la fonction lui-même, exactement comme c’était le cas dans les fonctions prédéfinies.

Une fonction s'écrit toujours en-dehors de la procédure principale. Selon les langages, cela peut prendre différentes formes. Mais ce qu'il faut comprendre, c'est que ces quelques lignes de codes sont en quelque sorte des satellites, qui existent en dehors du traitement lui-même. Simplement, elles sont à sa disposition, et il pourra y faire appel chaque fois que nécessaire. Si l'on reprend notre exemple, une fois notre fonction RepOuiNon écrite, le programme principal comprendra les lignes :

Bonne structure :

...
Ecrire "Etes-vous marié ?"
Rep1 ← RepOuiNon()
...
Ecrire "Avez-vous des enfants ?"
Rep2 ← RepOuiNon()
...

Et le tour est joué ! On a ainsi évité les répétitions inutiles, et si d'aventure, il y avait un bug dans notre contrôle de saisie, il suffirait de faire une seule correction dans la fonction RepOuiNon pour que ce bug soit éliminé de toute l'application. Elle n'est pas belle, la vie ?

Toutefois, les plus sagaces d'entre vous auront remarqué, tant dans le titre de la fonction que dans chacun des appels, la présence de parenthèses. Celles-ci, dès qu'on déclare ou qu'on appelle une fonction, sont obligatoires. Et si vous avez bien compris tout ce qui précède, vous devez avoir une petite idée de ce qu'on va pouvoir mettre dedans...

1.2 Passage d'arguments

Reprenons l’exemple qui précède et analysons-le. On écrit un message à l'écran, puis on appelle la fonction RepOuiNon pour poser une question ; puis, un peu plus loin, on écrit un autre message à l'écran, et on appelle de nouveau la fonction pour poser la même question, etc. C’est une démarche acceptable, mais qui peut encore être améliorée : puisque avant chaque question, on doit écrire un message, autant que cette écriture du message figure directement dans la fonction appelée. Cela implique deux choses :

lorsqu’on appelle la fonction, on doit lui préciser quel message elle doit afficher avant de lire la réponse
la fonction doit être « prévenue » qu’elle recevra un message, et être capable de le récupérer pour l’afficher.

En langage algorithmique, on dira que le message devient un argument (ou un paramètre) de la fonction. Cela n'est certes pas une découverte pour vous : nous avons longuement utilisé les arguments à propos des fonctions prédéfinies. Eh bien, quitte à construire nos propres fonctions, nous pouvons donc construire nos propres arguments. Voilà comment l’affaire se présente...

La fonction sera dorénavant déclarée comme suit :

Fonction RepOuiNon(Msg en Caractère) en Caractère
Ecrire Msg
Truc ← ""
TantQue Truc <> "Oui" et Truc <> "Non"
Ecrire "Tapez Oui ou Non"
Lire Truc
FinTantQue
Renvoyer Truc
Fin Fonction

Il y a donc maintenant entre les parenthèses une variable, Msg, dont on précise le type, et qui signale à la fonction qu’un argument doit lui être envoyé à chaque appel. Quant à ces appels, justement, ils se simplifieront encore dans la procédure principale, pour devenir :

...
Rep1 ← RepOuiNon("Etes-vous marié ?")
...
Rep2 ← RepOuiNon("Avez-vous des enfants ?")
...

Et voilà le travail.

Une remarque importante : là, on n'a passé qu’un seul argument en entrée. Mais bien entendu, on peut en passer autant qu’on veut, et créer des fonctions avec deux, trois, quatre, etc. arguments ; Simplement, il faut éviter d'être gourmands, et il suffit de passer ce dont on en a besoin, ni plus, ni moins !

Dans le cas que l'on vient de voir, le passage d'un argument à la fonction était élégant, mais pas indispensable. La preuve, cela marchait déjà très bien avec la première version. Mais on peut imaginer des situations où il faut absolument concevoir la fonction de sorte qu'on doive lui transmettre un certain nombre d'arguments si l'on veut qu'elle puisse remplir sa tâche. Prenons, par exemple, toutes les fonctions qui vont effectuer des calculs. Que ceux-ci soient simples ou compliqués, il va bien falloir envoyer à la fonction les valeurs grâce auxquelles elle sera censé produire son résultat (pensez tout bêtement à une fonction sur le modèle d'Excel, telle que celle qui doit calculer une somme ou une moyenne). C'est également vrai des fonctions qui traiteront des chaînes de caractères. Bref, dans 99% des cas, lorsqu'on créera une fonction, celle-ci devra comporter des arguments.

1.3 Deux mots sur l'analyse fonctionnelle

Comme souvent en algorithmique, si l'on s'en tient à la manière dont marche l'outil, tout cela n'est en réalité pas très compliqué. Les fonctions personnalisées se déduisent très logiquement de la manière nous nous avons déjà expérimenté les fonctions prédéfinies.

Le plus difficile, mais aussi le plus important, c'est d'acquérir le réflexe de constituer systématiquement les fonctions adéquates quand on doit traiter un problème donné, et de flairer la bonne manière de découper son algorithme en différentes fonctions pour le rendre léger, lisible et performant.

Cette partie de la réflexion s'appelle d'ailleurs l'analyse fonctionnelle d'un problème, et c'est toujours par elle qu'il faut commencer : en gros, dans un premier temps, on découpe le traitement en modules (algorithmique fonctionnelle), et dans un deuxième temps, on écrit chaque module (algorithmique classique). Cependant, avant d'en venir là, il nous faut découvrir deux autres outils, qui prennent le relais là où les fonctions deviennent incapables de nous aider.

2. Sous-Procédures

2.1 Généralités

Les fonctions, c'est bien, mais dans certains cas, ça ne nous rend guère service.

Il peut en effet arriver que dans un programme, on ait à réaliser des tâches répétitives, mais que ces tâches n'aient pas pour rôle de générer une valeur particulière, ou qu'elles aient pour rôle d'en générer plus d'une à la fois. Vous ne voyez pas de quoi je veux parler ? Prenons deux exemples.

Premier exemple. Imaginons qu'au cours de mon application, j'aie plusieurs fois besoin d'effacer l'écran et de réafficher un bidule comme un petit logo en haut à gauche. On pourrait se dire qu'il faut créer une fonction pour faire cela. Mais quelle serait la valeur renvoyée par la fonction ? Aucune ! Effacer l'écran, ce n'est pas produire un résultat stockable dans une variable, et afficher un logo non plus. Voilà donc une situation ou j'ai besoin de répéter du code, mais où ce code n'a pas comme rôle de produire une valeur.

Deuxième exemple. Au cours de mon application, je dois plusieurs fois faire saisir un tableau d'entiers (mais à chaque fois, un tableau différent). Là encore, on serait tenté d'effectuer toutes ces saisies de tableaux dans une seule fonction. Mais problème, une fonction ne peut renvoyer qu'une seule valeur à la fois. Elle ne peut donc renvoyer un tableau, qui est une série de valeurs distinctes.

Alors, dans ces deux cas, faute de pouvoir traiter l'affaire par une fonction, devra-t-on en rester au code répétitif dont nous venons de dénoncer si vigoureusement les faiblesses ? Mmmmmh ? Vous vous doutez bien que non. Heureusement, tout est prévu, il y a une solution. Et celle-ci consiste à utiliser des sous-procédures.

En fait, les fonctions - que nous avons vues - ne sont finalement qu'un cas particulier des sous-procédures - que nous allons voir : celui où doit être renvoyé vers la procédure appelante une valeur et une seule. Dans tous les autres cas (celui où on ne renvoie aucune valeur, comme celui ou en en renvoie plusieurs), il faut donc avoir recours non à la forme particulière et simplifiée (la fonction), mais à la forme générale (la sous-procédure).

Parlons donc de ce qui est commun aux sous-procédures et aux fonctions, mais aussi de ce qui les différencie. Voici comment se présente une sous-procédure :

Procédure Bidule( ... )
...
Fin Procédure

Dans la procédure principale, l’appel à la sous-procédure Bidule devient quant à lui :

Appeler Bidule(...)

Établissons un premier état des lieux.

Alors qu'une fonction se caractérisait par les mots-clés Fonction ... Fin Fonction, une sous-procédure est identifiée par les mots-clés Procédure ... Fin Procédure. Oui, je sais, c'est un peu trivial comme remarque, mais, bon, on ne sait jamais.
Lorsqu'une fonction était appelée, sa valeur (retournée) était toujours affectée à une variable (ou intégrée dans le calcul d'une expression). L'appel à une procédure, lui, est au contraire toujours une instruction autonome. "Exécute la procédure Bidule" est un ordre qui se suffit à lui-même.
Toute fonction devait, pour cette raison, comporter l'instruction "Renvoyer". Pour la même raison, l'instruction "Renvoyer" n'est jamais utilisée dans une sous-procédure. La fonction est une valeur calculée, qui renvoie son résultat vers la procédure principale. La sous-procédure, elle, est un traitement ; elle ne "vaut" rien.
Même une fois qu'on a bien compris les trois premiers points, on n'est pas complètement au bout de nos peines.

2.2 Le problème des arguments

En effet, il nous reste à examiner ce qui peut bien se trouver dans les parenthèses, à la place des points de suspension, aussi bien dans la déclaration de la sous-procédure que dans l'appel. Vous vous en doutez bien : c'est là que vont se trouver les outils qui vont permettre l'échange d'informations entre la procédure principale et la sous-procédure (en fait, cette dernière phrase est trop restrictive : mieux vaudrait dire : entre la procédure appelante et la procédure appelée. Car une sous-procédure peut très bien en appeler elle-même une autre afin de pouvoir accomplir sa tâche)

De même qu'avec les fonctions, les valeurs qui circulent depuis la procédure (ou la fonction) appelante vers la sous-procédure appelée se nomment des arguments, ou des paramètres en entrée de la sous-procédure. Comme on le voit, qu'il s'agisse des sous-procédure ou des fonctions, ces choses jouant exactement le même rôle (transmettre une information depuis le code donneur d'ordres jusqu'au code sous-traitant), elle portent également le même nom. Unique petite différence, on a précisé cette fois qu'il s'agissait d'arguments, ou de paramètres, en entrée. Pourquoi donc ?

Tout simplement parce que que dans une sous-procédure, on peut être amené à vouloir renvoyer des résultats vers le programme principal ; or, là, à la différence des fonctions, rien n'est prévu : la sous-procédure, en tant que telle, ne "renvoie" rien du tout (comme on vient de le voir, elle est d'ailleurs dépourvue de l'instruction "renvoyer"). Ces résultats que la sous-procédure doit transmettre à la procédure appelante devront donc eux aussi être véhiculés par des paramètres. Mais cette fois, il s'agira de paramètres fonctionnant dans l'autre sens (du sous-traitant vers le donneur d'ordres) : on les appellera donc des paramètres en sortie.

Ceci nous permet de reformuler en d'autres termes la vérité fondamentale apprise un peu plus haut : toute sous-procédure possédant un et un seul paramètre en sortie peut également être écrite sous forme d'une fonction (et entre nous, c'est une formulation préférable car un peu plus facile à comprendre et donc à retenir).

Jusque là, ça va ? Si oui, prenez un cachet d'aspirine et poursuivez la lecture. Si non, prenez un cachet d'aspirine et recommencez depuis le début. Et dans les deux cas, n'oubliez pas le grand verre d'eau pour faire passer l'aspirine.

Il nous reste un détail à examiner, détail qui comme vous vous en doutez bien, a une certaine importance : comment fait-on pour faire comprendre à un langage quels sont les paramètres qui doivent fonctionner en entrée et quels sont ceux qui doivent fonctionner en sortie...

2.3 Comment ça marche tout ça ?

En fait, si je dis qu'un paramètre est "en entrée" ou "en sortie", j'énonce quelque chose à propos de son rôle dans le programme. Je dis ce que je souhaite qu'il fasse, la manière dont je veux qu'il se comporte. Mais les programmes eux-mêmes n'ont cure de mes désirs, et ce n'est pas cette classification qu'ils adoptent. C'est toute la différence entre dire qu'une prise électrique sert à brancher un rasoir ou une cafetière (ce qui caractérise son rôle), et dire qu'elle est en 220 V ou en 110 V (ce qui caractérise son type technique, et qui est l'information qui intéresse l'électricien). A l'image des électriciens, les langages se contrefichent de savoir quel sera le rôle (entrée ou sortie) d'un paramètre. Ce qu'ils exigent, c'est de connaître leur voltage... pardon, le mode de passage de ces paramètres. Il n'en existe que deux :

le passage par valeur
le passage par référence

...Voyons de plus près de quoi il s'agit.

Reprenons l'exemple que nous avons déjà utilisé plus haut, celui de notre fonction RepOuiNon. Comme nous l'avons vu, rien ne nous empêche de réécrire cette fonction sous la forme d'une procédure (puisqu'une fonction n'est qu'un cas particulier de sous-procédure). Nous laisserons pour l"instant de côté la question de savoir comment renvoyer la réponse (contenue dans la variable Truc) vers le programme principal. En revanche, nous allons déclarer que Msg est un paramètre dont la transmission doit se faire par valeur. Cela donnera la chose suivante :

Procédure RepOuiNon(Msg en Caractère par valeur)
Ecrire Msg
Truc ← ""
TantQue Truc <> "Oui" et Truc <> "Non"
Ecrire "Tapez Oui ou Non"
Lire Truc
FinTantQue
??? Comment transmettre Truc à la procédure appelante ???
Fin Procédure

Quant à l'appel à cette sous-procédure, il pourra prendre par exemple cette forme :

M ← "Etes-vous marié ?"
Appeler RepOuiNon(M)

Que va-t-il se passer ?

Lorsque le programme principal arrive sur la première ligne, il affecte la variable M avec le libellé "Êtes-vous marié". La ligne suivante déclenche l'exécution de la sous-procédure. Celle-ci crée aussitôt une variable Msg. Celle-ci ayant été déclarée comme un paramètre passé par valeur, Msg va être affecté avec le même contenu que M. Cela signifie que Msg est dorénavant une copie de M. Les informations qui étaient contenues dans M ont été intégralement recopiées (en double) dans Msg. Cette copie subsistera tout au long de l'exécution de la sous-procédure RepOuiNon et sera détruite à la fin de celle-ci.

Une conséquence essentielle de tout cela est que si d'aventure la sous-procédure RepOuiNon contenait une instruction qui modifiait le contenu de la variable Msg, cela n'aurait aucune espèce de répercussion sur la procédure principale en général, et sur la variable M en particulier. La sous-procédure ne travaillant que sur une copie de la variable qui a été fournie par le programme principal, elle est incapable, même si on le souhaitait, de modifier la valeur de celle-ci. Dit d'une autre manière, dans une procédure, un paramètre passé par valeur ne peut être qu'un paramètre en entrée.

C'est en même temps une limite (aggravée par le fait que les informations ainsi recopiées occupent dorénavant deux fois plus de place en mémoire) et une sécurité : quand on transmet un paramètre par valeur, on est sûr et certain que même en cas de bug dans la sous-procédure, la valeur de la variable transmise ne sera jamais modifiée par erreur (c'est-à-dire écrasée) dans le programme principal.

Admettons à présent que nous déclarions un second paramètre, Truc, en précisant cette fois qu'il sera transmis par référence. Et adoptons pour la procédure l'écriture suivante :

Procédure RepOuiNon(Msg en Caractère par valeur, Truc en Caractère par référence)
Ecrire Msg
Truc ← ""
TantQue Truc <> "Oui" et Truc <> "Non"
Ecrire "Tapez Oui ou Non"
Lire Truc
FinTantQue
Fin Fonction

L'appel à la sous-procédure deviendrait par exemple :

M ← "Etes-vous marié ?"
Appeler RepOuiNon(M, T)
Ecrire "Votre réponse est ", T

Dépiautons le mécanisme de cette nouvelle écriture. En ce qui concerne la première ligne, celle qui affecte la variable M, rien de nouveau sous le soleil. Toutefois, l'appel à la sous-procédure provoque deux effets très différents. Comme on l'a déjà dit, la variable Msg est créée et immédiatement affectée avec une copie du contenu de M, puisqu'on a exigé un passage par valeur. Mais en ce qui concerne Truc, il en va tout autrement. Le fait qu'il s'agisse cette fois d'un passage par référence fait que la variable Truc ne contiendra pas la valeur de T, mais son adresse, c'est-à-dire sa référence.

Dès lors, toute modification de Truc sera immédiatement redirigée, par ricochet en quelque sorte, sur T. Truc n'est pas une variable ordinaire : elle ne contient pas de valeur, mais seulement la référence à une valeur, qui elle, se trouve ailleurs (dans la variable T). Il s'agit donc d'un genre de variable complètement nouveau, et différent de ce que nous avons vu jusque là. Ce type de variable porte un nom : on l'appelle un pointeur. Tous les paramètres passés par référence sont des pointeurs, mais les pointeurs ne se limitent pas aux paramètres passés par référence (même si ce sont les seuls que nous verrons dans le cadre de ce cours). Il faut bien comprendre que ce type de variable étrange est géré directement par les langages : à partir du moment où une variable est considérée comme un pointeur, toute affectation de cette variable se traduit automatiquement par la modification de la variable sur laquelle elle pointe.

Passer un paramètre par référence, cela présente donc deux avantages. Et d'une, on gagne en occupation de place mémoire, puisque le paramètre en question ne recopie pas les informations envoyées par la procédure appelante, mais qu'il se contente d'en noter l'adresse. Et de deux, cela permet d'utiliser ce paramètre tant en lecture (en entrée) qu'en écriture (en sortie), puisque toute modification de la valeur du paramètre aura pour effet de modifier la variable correspondante dans la procédure appelante.

Nous pouvons résumer tout cela par un petit tableau :

	passage par valeur	passage par référence
utilisation en entrée	oui	oui
utilisation en sortie	non	oui

Mais alors, demanderez-vous dans un élan de touchante naïveté, si le passage par référence présente les deux avantages présentés il y a un instant, pourquoi ne pas s'en servir systématiquement ? Pourquoi s'embêter avec les passages par valeur, qui non seulement utilisent de la place en mémoire, mais qui de surcroît nous interdisent d'utiliser la variable comme un paramètre en sortie ?

Eh bien, justement, parce qu'on ne pourra pas utiliser comme paramètre en sortie, et que cet inconvénient se révèle être aussi, éventuellement, un avantage. Disons la chose autrement : c'est une sécurité. C'est la garantie que quel que soit le bug qui pourra affecter la sous-procédure, ce bug ne viendra jamais mettre le foutoir dans les variables du programme principal qu'elle ne doit pas toucher. Voilà pourquoi, lorsqu'on souhaite définir un paramètre dont on sait qu'il fonctionnera exclusivement en entrée, il est sage de le verrouiller, en quelque sorte, en le définissant comme passé par valeur. Et Lycée de Versailles, ne seront définis comme passés par référence que les paramètres dont on a absolument besoin qu'ils soient utilisés en sortie.

3. Variables publiques et privées

Résumons la situation. Nous venons de voir que nous pouvions découper un long traitement comportant éventuellement des redondances (notre application) en différents modules. Et nous avons vu que les informations pouvaient être transmises entre ces modules selon deux modes :

si le module appelé est une fonction, par le retour du résultat
dans tous les cas, par la transmission de paramètres (que ces paramètres soient passés par valeur ou par référence)

En fait, il existe un troisième et dernier moyen d'échanger des informations entre différentes procédures et fonctions : c'est de ne pas avoir besoin de les échanger, en faisant en sorte que ces procédures et fonctions partagent littéralement les mêmes variables. Cela suppose d'avoir recours à des variables particulières, lisibles et utilisables par n'importe quelle procédure ou fonction de l'application.

Par défaut, une variable est déclarée au sein d'une procédure ou d'une fonction. Elle est donc créée avec cette procédure, et disparaît avec elle. Durant tout le temps de son existence, une telle variable n'est visible que par la procédure qui l'a vu naître. Si je crée une variable Toto dans une procédure Bidule, et qu'en cours de route, ma procédure Bidule appelle une sous-procédure Machin, il est hors de question que Machin puisse accéder à Toto, ne serait-ce que pour connaître sa valeur (et ne parlons pas de la modifier). Voilà pourquoi ces variables par défaut sont dites privées, ou locales.

Mais à côté de cela, il est possible de créer des variables qui certes, seront déclarées dans une procédure, mais qui du moment où elles existeront, seront des variables communes à toutes les procédures et fonctions de l'application. Avec de telles variables, le problème de la transmission des valeurs d'une procédure (ou d'une fonction) à l'autre ne se pose même plus : la variable Truc, existant pour toute l'application, est accessible et modifiable depuis n'importe quelle ligne de code de cette application. Plus besoin donc de la transmettre ou de la renvoyer. Une telle variable est alors dite publique, ou globale.

La manière dont la déclaration d'une variable publique doit être faites est évidemment fonction de chaque langage de programmation. En pseudo-code algorithmique, on pourra utiliser le mot-clé Publique :

Variable Publique Toto en Numérique

Alors, pourquoi ne pas rendre toutes les variables publiques, et s'épargner ainsi de fastidieux efforts pour passer des paramètres ? C’est très simple, et c'est toujours la même chose : les variables globales consomment énormément de ressources en mémoire. En conséquence, le principe qui doit présider au choix entre variables publiques et privées doit être celui de l’économie de moyens : on ne déclare comme publiques que les variables qui doivent absolument l’être. Et chaque fois que possible, lorsqu’on crée une sous-procédure, on utilise le passage de paramètres plutôt que des variables publiques.

4. PEUT-ON TOUT FAIRE ?

A cette question, la réponse est bien évidemment : oui, on peut tout faire. Mais c'est précisément la raison pour laquelle on peut vite en arriver à faire aussi absolument n'importe quoi.

N'importe quoi, c'est quoi ? C'est par exemple, comme on vient de le voir, mettre des variables globales partout, sous prétexte que c'est autant de paramètres qu'on n'aura pas à passer.

Mais on peut imaginer d'autres atrocités.

Par exemple, une fonction, dont un des paramètres d'entrée serait passé par référence, et modifié par la fonction. Ce qui signifierait que cette fonction produirait non pas un, mais deux résultats. Autrement dit, que sous des dehors de fonctions, elle se comporterait en réalité comme une sous-procédure.

Ou inversement, on peut concevoir une procédure qui modifierait la valeur d'un paramètre (et d'un seul) passé par référence. Il s'agirait là d'une procédure qui en réalité, serait une fonction. Quoique ce dernier exemple ne soit pas d'une gravité dramatique, il participe de la même logique consistant à embrouiller le code en faisant passer un outil pour un autre, au lieu d'adopter la structure la plus claire et la plus lisible possible.

Enfin, il ne faut pas écarter la possibilité de programmeurs particulièrement vicieux, qui par un savant mélange de paramètres passés par référence, de variables globales, de procédures et de fonctions mal choisies, finiraient par accoucher d'un code absolument illogique, illisible, et dans lequel la chasse à l'erreur relèverait de l'exploit.

Trèfle de plaisanteries : le principe qui doit guider tout programmeur est celui de la solidité et de la clarté du code. Une application bien programmée est une application à l'architecture claire, dont les différents modules font ce qu'ils disent, disent ce qu'il font, et peuvent être testés (ou modifiés) un par un sans perturber le reste de la construction. Il convient donc :

de limiter au minimum l'utilisation des variables globales. Celles-ci doivent être employées avec nos célèbres amis italo-arméniens, c'est-à-dire avec parcimonie et à bon escient.
de regrouper sous forme de modules distincts tous les morceaux de code qui possèdent une certaine unité fonctionnelle (programmation par "blocs"). C'est-à-dire de faire la chasse aux lignes de codes redondantes, ou quasi-redondantes.
de faire de ces modules des fonctions lorsqu'ils renvoient un résultat unique, et des sous-procédures dans tous les autres cas (ce qui implique de ne jamais passer un paramètre par référence à une fonction : soit on n'en a pas besoin, soit on en a besoin, et ce n'est alors plus une fonction).

Respecter ces règles d'hygiène est indispensable si l'on veut qu'une application ressemble à autre chose qu'au palais du facteur Cheval. Car une architecture à laquelle on ne comprend rien, c'est sans doute très poétique, mais il y a des circonstances où l'efficacité est préférable à la poésie. Et, pour ceux qui en douteraient encore, la programmation informatique fait (hélas ?) partie de ces circonstances.

5. Algorithmes fonctionnels

Pour clore ce chapitre, voici quelques mots supplémentaires à propos de la structure générale d’une application. Comme on l'a dit à plusieurs reprises, celle-ci va couramment être formée d’une procédure principale, et de fonctions et de sous-procédures (qui vont au besoin elles-mêmes en appeler d’autres, etc.). L’exemple typique est celui d’un menu, ou d’un sommaire, qui « branche » sur différents traitements, donc différentes sous-procédures.

L’algorithme fonctionnel de l’application est le découpage et/ou la représentation graphique de cette structure générale, ayant comme objectif de faire comprendre d’un seul coup d’œil quelle procédure fait quoi, et quelle procédure appelle quelle autre. L’algorithme fonctionnel est donc en quelque sorte la construction du squelette de l’application. Il se situe à un niveau plus général, plus abstrait, que l’algorithme normal, qui lui, détaille pas à pas les traitements effectués au sein de chaque procédure.

Dans la construction – et la compréhension – d’une application, les deux documents sont indispensables, et constituent deux étapes successives de l’élaboration d’un projet. La troisième – et dernière – étape, consiste à écrire, pour chaque procédure et fonction, l’algorithme détaillé.

Exemple de réalisation d’un algorithme fonctionnel : Le Jeu du Pendu

Vous connaissez tous ce jeu : l’utilisateur doit deviner un mot choisi au hasard par l’ordinateur, en un minimum d’essais. Pour cela, il propose des lettres de l’alphabet. Si la lettre figure dans le mot à trouver, elle s’affiche. Si elle n’y figure pas, le nombre des mauvaises réponses augmente de 1. Au bout de dix mauvaises réponses, la partie est perdue.

Ce petit jeu va nous permettre de mettre en relief les trois étapes de la réalisation d’un algorithme un peu complexe ; bien entendu, on pourrait toujours ignorer ces trois étapes, et se lancer comme un dératé directement dans la gueule du loup, à savoir l’écriture de l’algorithme définitif. Mais, sauf à être particulièrement doué, mieux vaut respecter le canevas qui suit, car les difficultés se résolvent mieux quand on les saucissonne…

Etape 1 : le dictionnaire des données

Le but de cette étape est d’identifier les informations qui seront nécessaires au traitement du problème, et de choisir le type de codage qui sera le plus satisfaisant pour traiter ces informations. C’est un moment essentiel de la réflexion, qu’il ne faut surtout pas prendre à la légère… Or, neuf programmeurs débutants sur dix bâclent cette réflexion, quand ils ne la zappent pas purement et simplement. La punition ne se fait généralement pas attendre longtemps ; l’algorithme étant bâti sur de mauvaises fondations, le programmeur se rend compte tout en l’écrivant que le choix de codage des informations, par exemple, mène à des impasses. La précipitation est donc punie par le fait qu’on est obligé de tout reprendre depuis le début, et qu’on a au total perdu bien davantage de temps qu’on en a cru en gagner…

Donc, avant même d’écrire quoi que ce soit, les questions qu’il faut se poser sont les suivantes :

de quelles informations le programme va-t-il avoir besoin pour venir à bout de sa tâche ?
pour chacune de ces informations, quel est le meilleur codage ? Autrement dit, celui qui sans gaspiller de la place mémoire, permettra d’écrire l’algorithme le plus simple ?

Encore une fois, il ne faut pas hésiter à passer du temps sur ces questions, car certaines erreurs, ou certains oublis, se payent cher par la suite. Et inversement, le temps investi à ce niveau est largement rattrapé au moment du développement proprement dit.

Pour le jeu du pendu, voici la liste des informations dont on va avoir besoin :

une liste de mots (si l’on veut éviter que le programme ne propose toujours le même mot à trouver, ce qui risquerait de devenir assez rapidement lassant…)
le mot à deviner
la lettre proposée par le joueur à chaque tour
le nombre actuel de mauvaises réponses
et enfin, last but not least, l’ensemble des lettres déjà trouvées par le joueur. Cette information est capitale ; le programme en aura besoin au moins pour deux choses : d’une part, pour savoir si le mot entier a été trouvé. D’autre part, pour afficher à chaque tour l’état actuel du mot (je rappelle qu’à chaque tour, les lettres trouvées sont affichées en clair par la machine, les lettres restant à deviner étant remplacées par des tirets).
à cela, on pourrait ajouter une liste comprenant l’ensemble des lettres déjà proposées par le joueur, qu’elles soient correctes ou non ; ceci permettra d’interdire au joueur de proposer à nouveau une lettre précédemment jouée.

Cette liste d’informations n’est peut-être pas exhaustive ; nous aurons vraisemblablement besoin au cours de l’algorithme de quelques variables supplémentaires (des compteurs de boucles, des variables temporaires, etc.). Mais les informations essentielles sont bel et bien là. Se pose maintenant le problème de choisir le mode de codage le plus futé. Si, pour certaines informations, la question va être vite réglée, pour d’autres, il va falloir faire des choix (et si possible, des choix intelligents !). C’est parti, mon kiki :

Pour la liste des mots à trouver, il s’agit d’un ensemble d’informations de type alphanumérique. Ces informations pourraient faire partie du corps de la procédure principale, et être ainsi stockées en mémoire vive, sous la forme d’un tableau de chaînes. Mais ce n’est certainement pas le plus judicieux. Toute cette place occupée risque de peser lourd inutilement, car il n’y a aucun intérêt à stocker l’ensemble des mots en mémoire vive. Et si l’on souhaite enrichir la liste des mots à trouver, on sera obligé de réécrire des lignes de programme… Conclusion, la liste des mots sera bien plus à sa place dans un fichier texte, dans lequel le programme ira piocher un seul mot, celui qu’il faudra trouver. Nous constituerons donc un fichier texte, appelé dico.txt, dans lequel figurera un mot par ligne (par enregistrement).
Le mot à trouver, lui, ne pose aucun problème : il s’agit d’une information simple de type chaîne, qui pourra être stocké dans une variable appelée mot, de type caractère.
De même, la lettre proposée par le joueur est une information simple de type chaîne, qui sera stockée dans une variable appelée lettre, de type caractère.
Le nombre actuel de mauvaises réponses est une information qui pourra être stockée dans une variable numérique de type entier simple appelée MovRep.
L’ensemble des lettres trouvées par le joueur est typiquement une information qui peut faire l’objet de plusieurs choix de codage ; rappelons qu’au moment de l’affichage, nous aurons besoin de savoir pour chaque lettre du mot à deviner si elle a été trouvée ou non. Une première possibilité, immédiate, serait de disposer d’une chaîne de caractères comprenant l’ensemble des lettres précédemment trouvées. Cette solution est loin d’être mauvaise, et on pourrait tout à fait l’adopter. Mais ici, on fera une autre choix, ne serait-ce que pour varier les plaisirs : on va se doter d’un tableau de booléens, comptant autant d’emplacements qu’il y a de lettres dans le mot à deviner. Chaque emplacement du tableau correspondra à une lettre du mot à trouver, et indiquera par sa valeur si la lettre a été découverte ou non (faux, la lettre n’a pas été devinée, vrai, elle l’a été). La correspondance entre les éléments du tableau et le mot à deviner étant immédiate, la programmation de nos boucles en sera facilitée. Nous baptiserons notre tableau de booléens du joli nom de « verif ».
Enfin, l’ensemble des lettres proposées sera stockée sans soucis dans une chaîne de caractères nommée Propos.

Nous avons maintenant suffisamment gambergé pour dresser le tableau final de cette étape, à savoir le dictionnaire des données proprement dit :
.

Nom	Type	Description
Dico.txt	Fichier texte	Liste des mots à deviner
Mot	Caractère	Mot à deviner
Lettre	Caractère	Lettre proposée
MovRep	Entier	Nombre de mauvaises réponses
Verif()	Tableau de Booléens	Lettres précédemment devinées, en correspondance avec Mot
Propos	Caractère	Liste des lettres proposées

Etape 2 : l’algorithme fonctionnel

On peut à présent passer à la réalisation de l’algorithme fonctionnel, c’est-à-dire au découpage de notre problème en blocs logiques. Le but de la manœuvre est multiple :

faciliter la réalisation de l’algorithme définitif en le tronçonnant en plus petits morceaux.
Gagner du temps et de la légèreté en isolant au mieux les sous-procédures et fonctions qui méritent de l’être. Eviter ainsi éventuellement des répétitions multiples de code au cours du programme, répétitions qui ne diffèrent les unes des autres qu'à quelques variantes près.
Permettre une division du travail entre programmeurs, chacun se voyant assigner la programmation de sous-procédures ou de fonctions spécifiques (cet aspect est essentiel dès qu’on quitte le bricolage personnel pour entrer dans le monde de la programmation professionnelle, donc collective).

Dans notre cas précis, un premier bloc se détache : il s’agit de ce qu’on pourrait appeler les préparatifs du jeu (choix du mot à deviner). Puisque le but est de renvoyer une valeur et une seule (le mot choisi par la machine), nous pouvons confier cette tâche à une fonction spécialisée ChoixDuMot (à noter que ce découpage est un choix de lisibilité, et pas une nécessité absolue ; on pourrait tout aussi bien faire cela dans la procédure principale).

Cette procédure principale, justement, va ensuite avoir nécessairement la forme d’une boucle Tantque : en effet , tant que la partie n’est pas finie, on recommence la série des traitements qui représentent un tour de jeu. Mais comment, justement, savoir si la partie est finie ? Elle peut se terminer soit parce que le nombre de mauvaises réponses a atteint 10, soit parce que toutes les lettres du mot ont été trouvées. Le mieux sera donc de confier l’examen de tout cela à une fonction spécialisée, PartieFinie, qui renverra une valeur numérique (0 pour signifier que la partie est en cours, 1 en cas de victoire, 2 en cas de défaite).

Passons maintenant au tour de jeu.

La première chose à faire, c’est d’afficher à l’écran l’état actuel du mot à deviner : un mélange de lettres en clair (celles qui ont été trouvées) et de tirets (correspondant aux lettres non encore trouvées). Tout ceci pourra être pris en charge par une sous-procédure spécialisée, appelée AffichageMot. Quant à l’initialisation des différentes variables, elle pourra être placée, de manière classique, dans la procédure principale elle-même.

Ensuite, on doit procéder à la saisie de la lettre proposée, en veillant à effectuer les contrôles de saisie adéquats. Là encore, une fonction spécialisée, SaisieLettre, sera toute indiquée.

Une fois la proposition faite, il convient de vérifier si elle correspond ou non à une lettre à deviner, et à en tirer les conséquences. Ceci sera fait par une sous-procédure appelée VérifLettre.

Enfin, une fois la partie terminée, on doit afficher les conclusions à l’écran ; on déclare à cet effet une dernière procédure, FinDePartie.

Nous pouvons, dans un algorithme fonctionnel complet, dresser un tableau des différentes procédures et fonctions, exactement comme nous l’avons fait juste avant pour les données (on s’épargnera cette peine dans le cas présent, ce que nous avons écrit ci-dessus suffisant amplement. Mais dans le cas d’une grosse application, un tel travail serait nécessaire et nous épargnerait bien des soucis).

On peut aussi schématiser le fonctionnement de notre application sous forme de blocs, chacun des blocs représentant une fonction ou une sous-procédure :

A ce stade, l’analyse dite fonctionnelle est terminée. Les fondations (solides, espérons-le) sont posées pour finaliser l’application.

Etape 3 : Algorithmes détaillés

Normalement, il ne nous reste plus qu’à traiter chaque procédure isolément. On commencera par les sous-procédures et fonctions, pour terminer par la rédaction de la procédure principale.

votre commentaire