Algorithmes

La notion d'algorithme est très ancienne, bien antérieure à l'invention de l'ordinateur. Mais celui-ci a offert à l'algorithmique un immense domaine d'application, tout en ouvrant sur un grand nombre de nouvelles problématiques de recherche fondamentale. Les avancées en informatique sont intimement liées aux progrès en algorithmique. Le choix des sujets abordés ici doit notamment beaucoup à la collaboration de Philippe Flajolet, chercheur à l'INRIA Rocquencourt.

Facile

Un algorithme pour mettre en rang une équipe de football

Réaliser un alignement, une évidence ? Pas si sûr... Du sport de ballon au sport cérébral, découvrez différentes méthodes pour y parvenir.

Publié le 28/07/2011

Par Jocelyne Erhel

Facile

La programmation par contraintes

Grâce à elle, le programme informatique résolvant un problème peut s’écrire de manière très simple. Il s’agit simplement d’écrire les différentes contraintes que l’on souhaite voir respectées…

Publié le 24/02/2004

Par Étienne Parizot, Sylvain Soliman, François Fages

Intermédiaire

Le plus court chemin

Lorsque l’on cherche à se rendre d’un point à un autre dans un réseau par le plus court chemin, il existe des algorithmes qui évitent d’avoir à calculer tous les trajets possibles.

Publié le 17/11/2005

Par Jean-Michel Hélary

Intermédiaire

Les algorithmes de tri

Tri par sélection, tri par propagation, tri par insertion, tri rapide, tri par fusion... Une animation interactive présente ces différentes méthodes afin de mieux comprendre leurs particularités et de comparer leurs performances.

Publié le 01/09/2004

Par Marion Videau, David Eck

Intermédiaire

Algorithmes, mode d’emploi

Les algorithmes permettent de mécaniser calculs et traitements. Ils sont à la base du moindre programme où se combinent leurs ingrédients. Leur étude révèle les potentiels et les limites de l’informatique.

Publié le 16/01/2009

Par Thierry Viéville

Facile

À la découverte des automates cellulaires

Explorer les relations mathématiques entre les phénomènes observés chez des êtres vivants et des machines, c’est là l’une des possibilités offertes par les automates cellulaires.

Publié le 16/04/2007

Par Nazim Fatès

Intermédiaire

P = NP, un problème à un million de dollars ?

Le problème P = NP est le problème fondamental du calcul mathématique. À partir de quel moment un énoncé difficile à démontrer et jugé très probable doit-il être adopté comme nouvel axiome ?

Publié le 03/04/2007

Par Jean-Paul Delahaye

Facile

Classer musiques, langues, images, textes et génomes

Les algorithmes de compression de données permettent de classer automatiquement toutes sortes de fichiers. Ce « classement » est d’autant plus pertinent que ces algorithmes sont performants.

Publié le 15/03/2007

Par Jean-Paul Delahaye

Intermédiaire

Alignement optimal et comparaison de séquences génomiques et protéiques

La comparaison de séquences génomiques et protéiques est la tâche informatique la plus exécutée par les biologistes. Des algorithmes sont mis en œuvre pour calculer les meilleurs alignements entre plusieurs séquences.

Publié le 03/10/2005

Par François Rechenmann

Facile

Les leçons d’un algorithme délinquant

Pour le sens commun, la machine ne se trompe jamais. Si par malheur un utilisateur pointilleux découvre une erreur dans son calcul sur ordinateur, qui doit-il alors accuser ? Lui, ou la machine ?

Publié le 20/02/2004

Par Jean-Michel Muller