Blog ENI : Toute la veille numérique !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
💥 1 livre papier acheté 
= la version en ligne automatiquement offerte. Cliquez ici
  1. Livres et vidéos
  2. Algorithmique
  3. Introduction à l'algorithmique
Extrait - Algorithmique Techniques fondamentales de programmation - Exemples en Python (nombreux exercices corrigés) - BTS, DUT informatique (Nouvelle édition)
Extraits du livre
Algorithmique Techniques fondamentales de programmation - Exemples en Python (nombreux exercices corrigés) - BTS, DUT informatique (Nouvelle édition) Revenir à la page d'achat du livre

Introduction à l'algorithmique

Les fondements de l’informatique

1. Architecture de l’ordinateur

L’idée d’une machine pouvant faire plusieurs calculs vient de la machine de Turing. Alan Turing est le mathématicien qui, avec son équipe, a réussi à casser le chiffrement de la machine Enigma pendant la Seconde Guerre mondiale, ce qui a donné une énorme avance stratégique et tactique pour vaincre les Allemands. C’est en 1936 qu’Alan Turing eut cette idée de génie.

Jusqu’alors, toutes les machines étaient créées pour exécuter une seule et unique tâche, un seul calcul. En vulgarisant, une machine qui pouvait résoudre une addition ne pouvait pas résoudre une multiplication. Les machines étaient donc très limitées et leur coût était trop excessif pour pouvoir les utiliser couramment.

La machine de Turing est un concept abstrait qui a donné naissance à l’informatique que nous connaissons actuellement. En résumé, cette machine se compose d’un ruban infini de cases. Chaque case comporte un symbole que la machine connaît. La machine lit les cases les unes après les autres et retient les cases dont elle a besoin pour effectuer le calcul décrit sur plusieurs cases. Il s’agit de la première machine disposant d’une mémoire incorporée permettant de résoudre de multiples problèmes différents.

La machine de Turing n’a jamais été réellement implémentée, notamment à cause du ruban infini représentant la mémoire. Cependant, elle reste le concept de base des ordinateurs.

Nos ordinateurs actuels fonctionnent tous sur l’architecture de Von Neumann. John Von Neumann était un mathématicien et physicien né en 1903, ayant participé à la création des ordinateurs. Il proposa déjà à l’époque que les machines soient composées de quatre modules, comme le montre la figure suivante :

  • L’unité arithmétique et logique qui effectue les opérations : ce sont nos processeurs aujourd’hui.

  • L’unité de contrôle qui séquence les opérations, ce qui est aujourd’hui également intégré à nos processeurs.

  • La mémoire pour stocker les programmes et les entrées, qui est devenue notre RAM et nos disques durs.

  • Les dispositifs d’entrée/sortie pour que l’humain puisse donner les entrées à la machine, les claviers et les écrans principalement aujourd’hui.

images/01RI01V3.png

Schématisation de l’arithmétique de Von Neumann...

L’algorithmique, l’art de programmer

1. L’algorithmie, comment et pourquoi ?

Nous utilisons tous les jours des algorithmes sans même savoir que ce sont des algorithmes. Les premiers algorithmes formalisés remontent à l’Antiquité pour la gestion de l’eau dans les fontaines et depuis nous n’arrêtons pas d’en créer et de les appliquer.

a. Exemples de la vie courante

Indiquer à un ordinateur ce qu’il doit faire, donc lui donner un programme à exécuter, revient à donner à un humain la notice de montage d’un meuble en kit pour construire son étagère ou une recette pour pouvoir déguster une tarte aux pommes.

Nous avons tous connu ce moment de questionnement intense devant une notice de montage. Dans cette notice, nous retrouvons deux parties : l’ensemble des pièces fournies et une suite de schémas pour assembler les pièces. Ce document est en fait semblable à un algorithme et à un programme :

  • La liste des pièces équivaut à l’ensemble des variables : 18 vis, 4 planches rectangulaires, un tournevis…

  • Les schémas représentent les instructions : insérer les vis dans les trous des planches par exemple.

Regardons maintenant une deuxième analogie : la recette de cuisine. Vous aurez besoin d’une pâte brisée, d’un sachet de sucre vanillé, de 30 grammes de beurre et de 6 pommes. Nous pouvons voir la liste des ingrédients comme un ensemble de variables. Après la liste d’ingrédients viennent les étapes de la recette, donc les instructions :

  • mettre la pâte brisée dans un moule à tarte ;

  • éplucher les pommes ;

  • couper les pommes en tranches ;

  • placer les tranches sur la pâte ;

  • faire fondre...

Les langages, la mise en œuvre

1. La programmation

L’ordinateur est un ensemble de composants électroniques qui, au fond, ne comprennent que deux choses : le courant passe ou le courant ne passe pas.

Ainsi le seul langage compris par les composants de la machine, que ce soient le processeur ou les mémoires, est le binaire. Uniquement deux valeurs sont possibles : 1 (le courant passe) et 0 (le courant ne passe pas).

Mais alors, comment communiquer de manière simple avec l’ordinateur ?

Au fur et à mesure du temps, l’informatique a implémenté de nombreuses surcouches au langage binaire pour faciliter la communication avec l’utilisateur : l’encodage du texte pour que l’être humain écrive dans un langage naturel, les systèmes d’exploitation comme Windows, Linux ou macOS… 

Mais ces surcouches ne font qu’une traduction en binaire pour les composants électroniques. Tous vos fichiers numériques sont en fait une suite de 0 et de 1.

Il en va de même pour le développeur. Au début de l’informatique, le développement ressemblait plus à de l’électronique qu’à de l’informatique, puis sont apparues les cartes perforées pour stocker les programmes, puis les langages de programmation.

Les langages de programmation sont les langages de haut niveau qui permettent au développeur d’indiquer à l’ordinateur ce qu’il doit effectuer en appliquant des algorithmes.

Les langages de programmation ont une syntaxe proche du langage humain tout en intégrant les contraintes de la machine. Ils permettent de guider l’exécution d’un programme sans aucune ambiguïté et, donc, assurent le fonctionnement de nos instructions. Dans le cas où le programme ne fait pas ce qu’il devrait faire, le problème vient des instructions. Le problème est toujours entre le clavier et l’écran.

Le premier programme a été inventé avant même que l’ordinateur soit créé. Ada Lovelace, comtesse anglaise née en 1815, développa le premier programme sur un ancêtre de l’ordinateur, la machine analytique de Charles Babbage. Il s’agit...