|
Même si les algorithmes sont souvent considérés comme étant du ressort exclusif des mathématiques et de l'informatique, leur champ d'application est en réalité beaucoup plus vaste. Un algorithme, 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…
|
|
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.
|
|
Pour décrire la forme d'un objet, par exemple un avion, on est amené à 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 ».
|
|
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écouvrez ce moyen d'investigation des processus auto-reproductifs à travers différents exemples d'automates cellulaires...
|
|
La voiture qui vous précède a avancé d’une longueur, vous avancez pour occuper sa place. Évidemment, vous n’auriez pas pu bouger si elle était restée immobile. La lente progression du train de voitures résulte de la répétition de comportements machinaux adoptés par des milliers d’automobilistes. Comment modéliser la propagation d’un bouchon ? Les automates cellulaires modélisent de tels phénomènes.
|
|
Le problème P = NP est le problème fondamental du calcul mathématique. À partir de quel moment, et sous quelles conditions, un énoncé difficile à démontrer et jugé très probable doit-il être adopté comme nouvel axiome ?
|
|
Les algorithmes de compression de données permettent de classer automatiquement toutes sortes de fichiers (morceaux de musique, textes, images, etc.). Ce « classement » est d'autant plus pertinent que ces algorithmes sont performants. En d'autres termes, meilleurs sont les algorithmes utilisés, plus fines seront les classifications obtenues.
|
|
Il est courant, lorsque l'on cherche à se rendre d'un point à un autre dans un réseau, de chercher le plus court chemin, c'est-à-dire celui dont la distance est la plus petite.
Heureusement, il existe des algorithmes qui évitent d'avoir à calculer tous les trajets possibles. Pour cela, ils mettent en œuvre diverses stratégies. Ce document explique les principales approches utilisées actuellement.
|
|
La comparaison de séquences génomiques et protéiques est de loin la tâche informatique la plus fréquemment exécutée par les biologistes. Des algorithmes sont mis en œuvre pour calculer les meilleurs alignements entre plusieurs séquences. Le fonctionnement de l'un de ces algorithmes est détaillé ici à l'aide d'une applet Java.
|
|
Obtenir un seul résultat pour un calcul donné : à première vue, cela semble une évidence ; c'est en fait un vaste sujet de recherche auquel les chercheurs apportent petit à petit leurs contributions. Une nouvelle étape est franchie aujourd'hui grâce à MPFR, une bibliothèque de calcul multi-précision sur les nombres flottants.
|
|
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.
|
|
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.
|
|
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 ?
|
|
Certaines idées reçues ont la vie dure, en informatique comme ailleurs. L'une d'entre elles porte sur la fiabilité que l'on attribue au calcul sur ordinateur, par rapport au calcul à la main. Calculer sans l'ombre d'une erreur, un jeu d'enfant pour les ordinateurs ? Pas vraiment !
|
|
Dans la vie courante, on a le plus souvent affaire à des objets tridimensionnels. On s'intéresse à leur forme, à leur orientation, etc. Pour les traiter informatiquement, 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…
|
|
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. Il concerne la démonstration formelle d'un algorithme très simple bien connu des arithméticiens, une méthode pour calculer les n premiers nombres premiers.
|
|
Grâce à elle, le programme informatique résolvant un problème peut s'écrire de manière très simple, presque comme on l'énoncerait dans le langage naturel. Il s'agit simplement d'écrire, les unes après les autres, les différentes contraintes que l'on souhaite voir respectées… et l'ordinateur se débrouille tout seul !
|
|
Pour Gérard Huet, ténacité n'est pas synonyme d'enfermement, bien au contraire. Après s'être passionné pour des disciplines aussi abstraites que la logique et l'informatique théorique, sa passion personnelle pour la culture indienne et le sanskrit le conduit à innover dans le domaine de la linguistique computationnelle.
|
thématique :
