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.

Approfondir

Les ingrédients des algorithmes

Gilles Dowek Thierry Viéville Jean-Pierre Archambault Emmanuel Baccelli Benjamin Wack - 21/04/2010

Pour programmer un ordinateur, le plus important ce sont les méthodes mises en œuvre. Découvrez les ingrédients à combiner pour créer ces algorithmes !

Découvrir

Algorithmes, mode d’emploi

Thierry Viéville - 16/01/2009

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.

Découvrir

Quand des algorithmes s’inspirent de la théorie de l’évolution

Marc Schoenauer Joanna Jongwane - 20/06/2008

Comment les algorithmes évolutionnaires trouvent-ils les meilleures solutions à un problème donné ? Marc Schoenauer, l’un des spécialistes du sujet, nous fournit quelques explications.

Découvrir

Qu’est-ce qu’un algorithme ?

Philippe Flajolet Étienne Parizot - 24/02/2004

Un algorithme n’est pas seulement du ressort des mathématiques. Très simplement, c’est une méthode, pour trier des objets, situer des villes sur une carte, multiplier deux nombres, chercher un mot dans le dictionnaire…

Ludique

10 questions sur les algorithmes

Marie-Christine Rousset - 26/04/2007

Pas à pas, explorez l’algorithmique, cette branche des mathématiques qui a permis tant d’avancées en informatique... et a permis aussi de montrer les limites intrinsèques de la résolution informatique de problèmes, ainsi que de comprendre, prédire, et quantifier les performances des algorithmes.

Découvrir

Les facettes du maillage

Étienne Parizot Pascal Frey - 24/02/2004

Pour décrire la forme d’un objet, par exemple un avion, on peut proposer une approximation de sa surface réelle, par la juxtaposition d’une multitude de petites facettes planes, faciles à décrire. C’est ce qu’on appelle un maillage.

Découvrir

À la découverte des automates cellulaires

Nazim Fatès - 16/04/2007

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.

Découvrir

La riche zoologie des automates cellulaires

Marianne Delorme Jacques Mazoyer - 16/04/2007

Les automates cellulaires modélisent des phénomènes variés tels la circulation automobile et la propagation des feux de forêt. De nouvelles techniques d’analyse classent les automates selon une échelle de complexité.

Approfondir

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

Jean-Paul Delahaye - 03/04/2007

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 ?

Approfondir

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

Jean-Paul Delahaye - 15/03/2007

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.

Découvrir

Le plus court chemin

Jean-Michel Hélary - 17/11/2005

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.

Approfondir

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

François Rechenmann - 03/10/2005

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.

Découvrir

Les algorithmes de tri

Marion Videau David Eck - 01/09/2004

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

C'était hier

Alan Turing : du calculable à l’indécidable

Jean-Gabriel Ganascia - 19/02/2004

Peut-on tout calculer ? Toute propriété mathématique est-elle décidable ? Ces questions ont passionné les mathématiciens bien avant les premiers ordinateurs.

C'était hier

Les leçons d’un algorithme délinquant

Jean-Michel Muller - 20/02/2004

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 ?

De la recherche

Le « dilemme du fabricant de tables » ou comment calculer juste

Anita Castiel Vincent Lefèvre Paul Zimmermann - 25/02/2004

Certaines idées reçues sont tenaces, comme la fiabilité attribuée au calcul sur ordinateur, par rapport au calcul à la main par exemple. Calculer sans l’ombre d’une erreur, un jeu d’enfant pour les ordinateurs ? Pas vraiment !

Découvrir

Manipulation informatique des objets géométriques

Étienne Parizot Jean-Daniel Boissonnat - 24/02/2004

Pour traiter informatiquement des objets tridimensionnels, on développe des algorithmes où les objets manipulés ne sont pas directement des nombres, mais plutôt des objets géométriques, des points, des surfaces, des volumes…

De la recherche

Une preuve sur les nombres premiers

Anita Castiel - 24/02/2004

Un ordinateur, c’est avant tout une machine. Est-il alors bien raisonnable de lui confier des démonstrations ? Voici un exemple propre à convaincre les sceptiques.

Découvrir

La programmation par contraintes

Étienne Parizot Sylvain Soliman François Fages - 24/02/2004

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…

Itinéraires

Gérard Huet, d’une frontière à l’autre

Dominique Chouchan - 18/02/2004

Après s’être passionné pour la logique et l’informatique théorique, sa passion pour la culture indienne et le sanskrit conduit Gérard Huet à innover dans le domaine de la linguistique computationnelle.