Portail:Algorithmique

Une page de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Algorithmique bandeau.jpg
255 articles



Portail Algorithmique
Al-Khwarizmi.jpg

On désigne par algorithmique l’ensemble des activités logiques qui relèvent des algorithmes ; en particulier, en informatique, cette discipline désigne l'ensemble des règles et des techniques qui sont impliquées dans la définition et la conception des algorithmes. Le mot vient du nom du mathématicien Al-Khuwarizmi (latinisé au Moyen Âge en Algoritmi), qui, au IXe siècle écrivit le premier ouvrage systématique sur la solution des équations linéaires et quadratiques. Dans le cas général, l’algorithmique s’effectue au moyen de calculs.

Un algorithme est un processus systématique de résolution, par le calcul, d'un problème permettant de présenter les étapes vers le résultat à une autre personne physique (un autre humain) ou virtuelle (un calculateur). En d'autres termes, un algorithme est un énoncé d’une suite finie et non-ambiguë d’opérations permettant de donner la réponse à un problème. Il décrit formellement une procédure concrète.


Bien que leur classement soit difficile, on peut distinguer plusieurs grand groupes d'algorithmes, sans pour autant tous les classer. En voici quelques-uns :

  • Algorithmes de structures de données
  • Algorithmes de tris
  • Algorithmes de la théorie des graphes
  • Algorithmes géométriques
  • Algorithmes mathématiques
  • Union-find
  • Algorithmes de balayage
Modifier
Article du mois
Federal subjects of Russia (by number).png

Le théorème des quatre couleurs affirme qu'il est possible, en n'utilisant que quatre couleurs différentes, de colorer n'importe quelle carte découpée en régions connexes, de sorte que deux régions adjacentes (ou limitrophes), c'est-à-dire ayant toute une frontière (et non simplement un point) en commun reçoivent toujours deux couleurs distinctes. L'énoncé peut varier et concerner, de manière tout à fait équivalente, la coloration des faces d'un polyèdre, ou des sommets d'un graphe planaire.

Trivialement, chacune des régions doit recevoir une couleur différente si les régions sont deux à deux adjacentes ; c'est le cas par exemple de la Belgique, du Luxembourg, de l'Allemagne et de la France dans une carte politique de l'Europe. D'où la nécessité des quatre couleurs dans le cas général. Par ailleurs, il ne peut exister cinq régions connexes deux à deux adjacentes (c'est la partie facile du théorème de Kuratowski).

Lorsqu'on généralise le problème à un graphe quelconque, il devient NP-complet de déterminer s'il est colorable avec seulement 4 couleurs (et même 3).

Human-go-next.svg
Lire l'article
Saviez vous que ...
Articles

Types d'algorithme[modifier | modifier le code]


Modifier
Portail connexes
Cryptologie

Cryptologie

Informatique théorique

Informatique théorique

Logique

Logique

Mathématiques

Mathématiques

Programmation informatiques

Programmation
informatique

Modifier

Autres portails.

Avertissement