97 lines
4.0 KiB
Plaintext
97 lines
4.0 KiB
Plaintext
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.
|
||
|
||
|