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 :

L’unité arithmétique et logique ou UAL (ALU en anglais) est l’organe de l’ordinateur qui exécute les calculs : additions, soustractions, multiplications, divisions, modulos, gestion des signes (positif, négatif), opérations logiques (booléenne), comparaisons, parfois rotations et décalages de valeurs (toujours dans le cadre d’une logique booléenne). Il existe des UAL spécialisées dans les nombres à virgule flottante, d’autres dans des traitements complexes comme les logarithmes, les inversions, les racines, les vecteurs, les calculs trigonométriques, etc. Certaines documentations lui rajoutent quelques registres (petites cases mémoires intégrées à l’UAL) et lui donnent le nom de processeur (CPU).

L’unité de contrôle ou UC (CU en anglais), à ne pas confondre avec unité centrale, contrôle le séquençage des opérations, autrement dit le déroulement du programme. Elle prend ses instructions dans la mémoire et donne ses ordres à l’UAL. Les résultats retournés peuvent influer sur le séquençage. L’UC passe alors à l’instruction suivante ou à une autre instruction telle que le programme lui ordonne d’effectuer.

La mémoire peut être décrite comme une suite de cases numérotées...

1. Programmer, c’est un art

Pour obtenir un résultat donné, il faut généralement suivre une méthode, une certaine logique. 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 lequel ajouter les ingrédients, le temps de cuisson, la température : bref, la recette. Même les plus grands pâtissiers ont dû apprendre et longuement s’exercer. De même, sans formation de mécanicien ou sans la documentation technique du moteur de votre véhicule, inutile de vous lancer dans une réparation de grande ampleur : c’est la casse assurée.

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 .NET, 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 (souvent peu reluisant). 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 premiers ordinateurs personnels étaient tous livrés...

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 langage machine binaire x86

10111010 00010000 
00000001 10110100 
00001001 11001101 
00100001 00110000 
11100100 11001101 
00010110 10111000 
00000000 01001100 
11001101 00100001 
01001000 01100101 
01101100 01101100 
01101111 00100000 
01010111 01101111 
01110010 01101100 
01100100 00100001 
00100100
 

Soit BA 10 01 B4 09 CD 21 30 E4 CD 16 B8 00 4C CD 21 48 65 6C 6C 6F 20 57 6F 72 6C 64 21 24 en hexadécimal.

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!"); 
    } 
}...