Introduction à l'algorithmique
Les fondements de l’informatique
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éennes), 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 le lui ordonne.
-
La mémoire peut être décrite comme une suite de petites cases numérotées, chaque case pouvant contenir une petite information (petite dans le sens où la taille de chaque case est fixe). Cette information peut être une instruction ou un morceau d’instruction du programme (une instruction peut occuper plusieurs cases) ou une donnée (nombre, caractère, ou morceau de ceux-ci). C’est l’UC qui a comme rôle central de contrôler l’accès à la mémoire pour le programme et les données. Chaque numéro de case est appelé une adresse. Pour accéder à la mémoire, il suffit de connaître son adresse. Les instructions du programme pour l’UC et les données pour l’UAL sont placées dans des zones différentes de la même mémoire physique.
-
Les entrées/sorties ou E/S (I/O en anglais) permettent de communiquer avec le monde extérieur et donc vous : ce peut être un clavier pour entrer les données et un écran pour afficher les résultats. Il permet à l’ordinateur d’être interactif.
![images/chap1001.png](https://www.eni-training.com/download/11aca350-0156-4662-973f-8ccc6f1dffc9/images/chap1001.png?id=AAEAAAD%2f%2f%2f%2f%2fAQAAAAAAAAAMAgAAAE1FbmkuRWRpdGlvbnMuTWVkaWFwbHVzLCBWZXJzaW9uPTEuMC4wLjAsIEN1bHR1cmU9bmV1dHJhbCwgUHVibGljS2V5VG9rZW49bnVsbAUBAAAAJ0VuaS5FZGl0aW9ucy5NZWRpYXBsdXMuQ29tbW9uLldhdGVybWFyawIAAAAHcGlzVGV4dAlwaWR0ZURhdGUBAA0CAAAABgMAAAAwdGVzdCB2Ml84IC0gZmZhNjQzOWQtZDZjYi00NzYxLWJhYTMtZWZkZDNiZDcwMWM25rSq0F7p2IgL)
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 :
-
l’UC extrait une instruction de la mémoire ;
-
analyse l’instruction ;
-
recherche en mémoire les données concernées par l’instruction ;
-
déclenche l’opération adéquate sur l’ALU ou l’E/S ;
-
range le résultat dans la mémoire.
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...
L’algorithmique
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é....
Les langages d’implémentation
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.
a. Haut niveau, bas niveau
Puisqu’il existe des centaines de langages de programmation, lequel choisir pour implémenter vos algorithmes ? Il n’y a pas de réponse simple à cette question. Chaque langage a été généralement conçu pour des usages différents et souvent spécifiques, bien qu’en évoluant la plupart des langages dits de haut niveau soient devenus de plus en plus généralistes. Il existe plusieurs classifications des langages. La plus ancienne dépend de l’affinité du langage par rapport à la machine. On parle alors du niveau du langage. Il est courant de parler d’un langage de bas niveau ou de niveau zéro (0) quand celui-ci nécessite des connaissances approfondies du fonctionnement de votre ordinateur : mécanismes de gestion de la mémoire, instructions du microprocesseur, etc. Un exemple de langage de très bas niveau est le langage machine sous sa forme binaire, ou de le la programmation en assembleur où ces mêmes valeurs binaires sont représentées par des mots (mnémoniques) en anglais. Vu que les programmes sont directement compréhensibles par le matériel, vos programmes seraient alors les plus rapides. Il est tout à fait possible de programmer de grosses applications en assembleur (et notamment des jeux), c’était d’ailleurs très courant jusqu’à l’apparition des machines très rapides où leur vitesse a compensé une plus faible vitesse d’exécution d’un langage plus évolué comme le C, mais avec l’avantage d’une programmation plus simple.
À l’opposé des langages de bas niveau se trouvent les langages de haut niveau. Il n’y a pas d’échelle précise. Vous pourrez trouver dans quelques sources des niveaux allant de 0 à 4, mais les langages évoluant tellement vite, certains langages qui étaient considérés de haut niveau comme le C se sont vus déclassés vers le bas ! Un langage de haut niveau permet de faire une abstraction presque complète du fonctionnement interne de votre ordinateur. Le langage (ou plutôt son compilateur ou son interpréteur) se chargera de convertir vos ordres simples (en apparence) en langage de bas niveau (en langage machine). Ne vous fiez pas aux apparences : l’affichage d’une boîte de dialogue prend une ligne...
Exercices
Exercice 1
Pour convertir un nombre binaire en décimal, doit-on :
-
Ajouter les nombres ?
-
Utiliser les puissances de 2 selon le poids ?
-
Convertir les groupes de 4 bits ?
-
Ajouter les nombres et diviser par 2 ?
Exercice 2
Quelle est la valeur maximale d’un nombre codé en 16 bits sans tenir compte du signe ? Indiquez comment calculer cette valeur et exprimez le résultat en décimal et en hexadécimal.
Exercice 3
Convertissez le nombre décimal 3407 en binaire et en hexadécimal.
Exercice 4
Quel est l’intrus parmi les langages suivants ? Expliquez.
-
PHP
-
Java
-
HTML
-
C++