formations/algo/AlgoApprofondie/cours/apercu.txt

Aperçu des algorithmes fondamentaux
===================================

Les algorithmes sont partout. Absolument partout aujourd'hui.
Il n'est pas un domaine de nos activités qui ne soit liés à tel ou tel algorithme.

Quelques grands thèmes: systèmes cryptographiques, géométrie algorithmique, reconnaissance de motifs, mais aussi les problèmes posés par l’algorithmique parallèle, etc... 

En mathématiques
-----------------

- l'algèbre (étude des structures de données)
- l'arithmétique modulaire (théorie des nombres)
  En mathématiques et plus précisément en théorie algébrique des nombres, 
  l’arithmétique modulaire est un ensemble de méthodes permettant la résolution de problèmes 
  sur les nombres entiers. 
  Ces méthodes dérivent de l’étude du reste obtenu par une division euclidienne.
- la géométrie (affine, algébrique, invariants topologiques...)
- les diagrammes (diagrammes de Venn...)
- les colorisation d'une carte
- comportements stochastiques

En informatique
----------------

- les algorithmes sur la manipulation des structures de données
  Exemple : les algorithmes de tri, de recherche dans un arbre...
- les parcours de graphes (chemins le plus court, voyageur de commerce...)
- la cryptologie (code gray)
- les stratégies de jeux

Tirés du monde réel
--------------------

- les jeux (casse-tête, dominos, échiquiers...)
- énigmes, logique et paradoxes
- problèmes de raisonnements.  Il n'existe pas beaucoup de méthodes
  ou de moyens simples pour traiter et résoudre les énoncés de logique de raisonnement.
- La "marche de l'ivrogne" : processus de progression discrète (pas à pas)
  dont l'étape suivante est lié à l'état présent et pas du tout à la mémoire du passé proche.
  Il revêt seulement un caractère de type probabilité (stochastique) dit markovien.
- algorithmes de colonies de fourmis (chemins optimal pour arriver à la nourriture)

Le voyageur de commerce
~~~~~~~~~~~~~~~~~~~~~~~~

Le problème du voyageur de commerce, consiste en la recherche d’un trajet minimal permettant à un
voyageur de visiter n villes. En règle générale on cherche à minimiser le temps de parcours total ou la
distance totale parcourue.

Il suffit de construire tous les chemins possibles et de calculer leurs longueurs.
Avec ``n`` villes il y a ``(n-1)!/2`` chemins possibles.
Avec 36 villes on trouve : 5166573983193072464833325668761600000000,
si le nombre de villes augmente, ça devient vite rédibitoire.

Résolution par

- algorithme de parcours de graphes
- algorithme glouton
- algorithmes génétiques

Les algorithmes génétiques s’appuient sur un principe de sélection des individus d’une population qui présen-
tent des caractéristiques se rapprochant au mieux de ce que l’on recherche; cette population évoluant par
ailleurs selon des critères d’évolution génétique à choisir. Dans le contexte du problème du voyageur de
commerce, un individu est une tournée, un chemin et une population un ensemble de tournées. Il s’agit
maintenant de dé...nir un critère de sélection ainsi que des règles d’évolution de la population.

- approches métaheuristiques (exemples: colonies de fourmis)

Exemple de résolution

.. raw:: latex

    \begin{algorithm}
    \caption{Algorithme du voyageur de commerce}\label{commerce}
    \begin{algorithmic}[1]

    \BState \emph{Données} : $L$ \Comment{Liste des villes à parcourir avec les distances entre les villes}
    \BState \emph{Données} : $L'$ \Comment{Liste du parcours des villes à effectuer}
    \State \emph{début}
    \BState ...
    \State \emph{fin}

    \end{algorithmic}
    \end{algorithm}

    
Algorithmes gloutons
--------------------

Les algorithmes servant à résoudre les problèmes d’optimisation parcourent en général une
série d’étapes, au cours desquelles ils sont confrontés à un ensemble de possibilités. Un
algorithme glouton fait toujours le choix qui semble le meilleur sur le moment, dans l’espoir
qu’il mènera à la solution optimale globalement.