Introduction à l'algorithmique

1. Architecture de Von Neumann

Un ordinateur est un ensemble de circuits électroniques permettant de manipuler des informations qu’on appelle des données et capable de faire « tourner » des programmes, c’est-à-dire une suite ou séquence d’instructions programmées à l’avance et qu’il va dérouler du début à la fin dans le but d’obtenir des résultats. Pour comprendre comment un ordinateur peut dérouler un programme, il faut étudier un peu plus en détail son fonctionnement.

C’est Von Neumann qui a défini en 1944 l’architecture des ordinateurs modernes encore largement utilisée aujourd’hui (avec des variantes cependant). L’architecture de Von Neumann (issue des travaux de Turing dont il sera question plus loin) décompose l’ordinateur en quatre parties distinctes :

Von Neumann, père des ordinateurs actuels

Les instructions du programme sont présentes dans la mémoire. L’unité de contrôle va prendre la première instruction du programme et l’exécuter. Si l’instruction est par exemple d’additionner deux nombres, elle va demander à l’UAL de prendre ces deux nombres en mémoire et de les additionner et éventuellement de placer le résultat dans une nouvelle case. Puis l’UC passe à l’instruction suivante. Si elle consiste à afficher ce résultat, alors l’UC va lire le contenu de la mémoire à l’adresse où est placé le résultat, puis va envoyer le résultat via le composant d’E/S adéquat. Et ainsi de suite. Au final le déroulement d’un programme au sein de l’ordinateur est le suivant :

Si vous ouvrez le capot de votre ordinateur, vous y verrez une grande quantité de cartes, composants, câbles, et même des organes mécaniques (lecteurs de disques durs, CD et DVD). Un programme que vous allez écrire et dérouler ne s’exécute pourtant que dans un seul endroit : le microprocesseur. Le microprocesseur de votre ordinateur est une puce facilement reconnaissable car c’est souvent la plus grosse, celle qui dispose du plus de pattes et est généralement...

1. Programmer, c’est un art

Pour obtenir un résultat donné, il faut généralement suivre une méthode, une certaine logique. Sauf à être un grand pâtissier dont la science des mélanges des ingrédients est innée (ou le fruit d’une longue pratique), vous n’obtiendrez jamais un délicieux gâteau au chocolat même si vous disposez des meilleurs ingrédients et accessoires de cuisson, si vous ne connaissez pas les bonnes proportions, l’ordre dans lesquels ajouter les ingrédients, le temps de cuisson, la température : bref, la recette.

Il en est de même de la programmation. Il existe plusieurs langages de programmation très simples, extrêmement simples parfois, qui peuvent donner un temps l’illusion que vous savez programmer. En entreprise même, certains employés sont bombardés développeurs pour leurs quelques connaissances confuses de Visual Basic, de Delphi ou de Windev. Le résultat risque d’être catastrophique. Les publicités sont alléchantes mais trompeuses. Les bons programmeurs, y compris les autodidactes, ont tous à un moment ou un autre eu affaire avec les algorithmes, car il existe en programmation une multitude de moyens d’arriver à un résultat, mais très peu pour obtenir le meilleur résultat possible, ce qui explique pourquoi beaucoup de programmes ayant la même fonction, se ressemblent (au niveau de la programmation) alors que ce ne sont pas les mêmes programmeurs qui les ont développés. Les débutants qui se lancent dans des projets de programmation audacieux se retrouvent parfois bloqués, ne maîtrisant pas une technique particulière de logique de programmation. Certains abandonnent, d’autres trouvent un moyen de contournement.

Les derniers liront peut-être un livre d’algorithmique comme celui-ci, qui à défaut de donner une solution complète à leur problème, leur fournira les bases et les techniques pour avancer.

Les ordinateurs personnels du début des années 1980 étaient tous livrés soit avec un langage BASIC inclus directement dans la machine (en ROM), soit sur une cartouche, cassette ou disquette annexe. Le Basic de Microsoft (Qbasic, Quickbasic) était livré avec le DOS du PC. Les Amstrad avaient le basic Locomotive, les Atari ST l’Atari Basic et surtout le GFA Basic, un langage de grande classe, etc. Une génération complète d’utilisateurs s’est lancée dans la programmation à l’aide de ces langages et de la documentation fournie qui bien souvent incluait non seulement les références du langage mais aussi les méthodes de base de programmation. Avec plus ou moins de succès. Le résultat était souvent un infâme bidouillage, mais qui marchait.

Or le but n’est pas que le programme fonctionne, mais qu’il fonctionne vite et bien, bref le mieux possible. Le meilleur ordinateur au monde et le meilleur langage au monde ne vous y aideront pas.

2. Définition : l’algorithme est une recette

Avez-vous déjà eu l’occasion de programmer un magnétoscope (en voie de disparition) ou un enregistreur de DVD (aussi) ? Qu’avez-vous fait la première fois que vous avez allumé votre poste de télévision pour régler la réception des chaînes ? Nul doute que vous avez ouvert le mode d’emploi et suivi la séquence d’instructions indiquée : appuyer sur la touche Menu de la télécommande, se déplacer sur Enregistrement et appuyer sur OK, se déplacer sur une ligne puis indiquer la chaîne, l’heure, etc.

Avez-vous déjà eu l’occasion de faire la cuisine ? Pour un gâteau, vous êtes-vous lancé directement ou avez-vous ouvert un livre pour récupérer la liste et la quantité de chaque ingrédient, pour suivre la recette : faites fondre le chocolat et le beurre dans une casserole à feu doux, retirez la casserole du feu, incorporez les jaunes d’œuf, puis le sucre et la farine, battez les œufs en neige puis incorporez doucement dans le mélange, etc.

Dans les deux cas, félicitations ! Vous avez déroulé votre premier algorithme !

Une définition simple d’un algorithme : c’est une suite d’instructions qui, quand elles sont exécutées correctement aboutissent au résultat attendu. C’est un énoncé dans un langage clair, bien défini et ordonné qui permet de résoudre un problème, le plus souvent par calcul. Cette définition est à rapprocher du fonctionnement de la machine de Turing qui avant l’apparition de l’ordinateur utilisait cette démarche pour résoudre de nombreux problèmes. L’algorithme est donc une recette pour qu’un ordinateur puisse donner un résultat donné....

1. Quel langage ?

Il existe plusieurs centaines de langages de programmation si on tient compte de toutes les variantes possibles d’un même langage. Comme vous avez pu le lire au début de ce chapitre, l’ordinateur ne comprend nativement qu’un seul langage, le langage machine. Croyez-vous vraiment que vous allez implémenter le programme de lancer de dé directement en binaire (ou même en hexadécimal) ? Le choix du langage mérite une petite démonstration. On a coutume dans le milieu de l’informatique, de tester un langage en lui faisant afficher un message pour dire bonjour, en l’occurrence le fameux "Hello world!". Voici comment afficher ce texte dans divers langages :

En assembleur x86 sous DOS

Cseg segment 
assume cs:cseg, ds:cseg 
org 100h 
main proc 
jmp debut 
mess db 'Hello world!$' 
debut: 
mov dx, offset mess 
mov ah, 9 
int 21h 
ret 
main endp 
cseg ends 
end main 

En shell Unix

echo "Hello world!" 

En Basic originel

10 PRINT "Hello world!"  
20 END 

En COBOL

IDENTIFICATION DIVISION. 
PROGRAM-ID. HELLO-WORLD. 
ENVIRONMENT DIVISION. 
DATA DIVISION. 
PROCEDURE DIVISION. 
DISPLAY "Hello world!". 
STOP RUN. 

En langage C

#include <stdio.h> 
 
int main(int argc, char **argv) 
{ 
    printf("Hello world!\n"); 
    return 0; 
} 

En langage C++

#include <iostream> 
 
int main() 
{ 
    std::cout << "Hello world!" << std::endl; 
    return 0; 
} 

En PHP

<?php 
print ("Hello world!"); 
?> 

En Java

public class HelloWorld { 
    public static void main(String[] args) { 
        System.out.println("Hello world!"); 
    } 
} 

En Visual Basic

Sub Main() 
  MsgBox("Hello world!") 
End Sub 

En Pascal

program Bonjour; 
begin 
  WriteLn('Hello world!'); 
end. 

2. Classifications des langages

Que remarquez-vous ? Il y a autant de syntaxes différentes qu’il existe de langages. Cependant vous constatez que les langages C, C++, Java ou PHP ont de nombreuses ressemblances, alors que l’assembleur ou le COBOL semblent sortis d’ouvrages de science-fiction. C’est que les premiers ont quelques liens familiaux tandis que les autres sont radicalement opposés.