Introduction
============

Ce cours est une introduction à l'algorithmique pour les informaticiens.
Il convient pour commencer de proposer une définition de ce qu'est un
algorithme :

.. glossary::

   algorithme 
       méthode permettant de résoudre un problème de manière systématique
   
Cette définition montre bien que les algorithmes ne sont pas spécifiques à
l'informatique ; on peut par exemple citer :

* la méthode consistant à *poser* une addition
  pour calculer la somme de deux nombres arbitrairement grands ;
* les instructions données par un GPS pour atteindre une destination ;
* une recette de cuisine pour réaliser une tarte aux pommes

comme des exemples d'algorithmes.

Ce qui distingue un algorithme
d'une autre méthode de résolution de problèmes,
c'est le caractère *systématique* de son exécution.
En d'autres termes,
un algorithme ne doit demander aucune initiative
à celui ou celle qui l'exécute.
Ceci explique l'importance de l'algorithmique en informatique :
un ordinateur n'étant capable d'aucune initiative,
il ne peut exécuter une tâche que si on lui fournit strictement
un algorithme pour le faire.
Tout programme informatique a donc, par définition,
la structure d'un algorithme.

.. index:: Python

Afin de pouvoir être exécuté de manière systématique,
un algorithme doit absolument éviter l'ambiguïté.
Or les langues naturelles, comme le français,
sont intrinsèquement ambiguës.
Il est donc indispensable d'écrire les algorithmes dans un langage formel,
dont la sémantique est précisément définie.
Dans ce cours, nous utiliserons le langage `Python 3`_.
Tout en étant relativement lisible et facile à écrire,
Python est un vrai langage de programmation ;
tous les exemples du cours sont donc exécutables directement par un ordinateur (sous réserve que Python y soit installé, évidemment).
Cependant, ce cours ne vise *pas* à être un cours de programmation en Python ;
il n'aborde pas toutes les spécificités de ce langage,
et les notions présentées restent valables
dans la majorité des autres langages de programmation\ [#limites_python]_.

.. index:: capacité

Le caractère systématique ne signifie pas pour autant
que l'exécutant de l'algorithme ne doit rien savoir faire *a priori*.
Au contraire, tout algorithme présuppose un certain nombre de **capacités**.
Dans les exemples ci-dessus :

* poser une addition suppose de connaître ses tables d'additions ;
* suivre un GPS suppose de savoir conduire,
  de connaître sa droite et sa gauche,
  ainsi que le code de la route ;
* suivre une recette de cuisine suppose de savoir peser, couper, verser...
  les ingrédients.


Les algorithmes pour l'informatique doivent donc s'appuyer
sur ce que « sait faire » l'ordinateur.
En pratique, ces capacités dépendent
du langage et de l'environnement de programmation utilisés.
Dans ce cours, c'est donc un sous-ensemble du langage Python
qui déterminera les capacités initiales de l'ordinateur,
au dessus desquelles nous construirons nos algorithmes (et qui seront décrites au chapitre `variables`:doc:).


.. rubric:: Notes de bas de page

.. _Python 3: http://python.org/

.. [#limites_python] Dans certains cas,
   nous éviterons même d'utiliser certaines fonctionnalités de Python,
   afin de mieux mettre en avant certaines notions algorithmiques.