Accueil - Boutique - Contact - Assistance
Zone de recherche

Altas Auteurs Recherche thématique Dictionnaire
 

ALGORITHMIQUE

Page précédente Page suivante

3.  Les problèmes algorithmiques du traitement de l'information

•  Méthodes de tri

Le problème du tri consiste, étant donné une suite x = (x1, x2, ..., xn) d'éléments d'un ensemble totalement ordonné – par exemple N ou R –, à déterminer une permutation σ de 1, ..., n telle que :

soit triée, c'est-à-dire que :
(Il est clairement équivalent de déterminer la suite triée y ou la permutation triante σ.)

L'algorithme de tri par échanges consécutifs, TEC, est conceptuellement le plus simple. Il consiste en (n − 1) phases successives :

La première phase (j = n) propage ainsi le maximum de x1, x2, ..., xn en dernière position ; la phase suivante j = (n − 1) amène le deuxième plus grand élément de la suite originale en position (n − 1)..., et à l'issue de l'algorithme, la suite x1, x2, ..., xn se retrouve triée. Le placement d'un maximum partiel s'effectue par propagation de ce maximum vers la droite selon le schéma :
Par exemple, avec n = 5 et la valeur initiale x = (5, 3, 9, 4, 2), la suite des valeurs de x obtenues est :

La c […]

… pour nos abonnés, l'article se prolonge sur 10 pages… Offre essai 7 jours

Thématique

Classification thématique de cet article :

Retour en haut

Autres références

« ALGORITHMIQUE » est également traité dans :

CALCUL, mathématique

Écrit par :  Philippe FLAJOLET

Dans le chapitre "Calculabilité et algorithmique"  : …  de vérifier tant la correction que la terminaison de tout programme. Le calcul a ses limites ! *L'algorithmique s'attache à l'élaboration d'algorithmes efficaces pour résoudre les problèmes reconnus comme calculables. Cette discipline s'organise selon quelques grands principes généraux. Par exemple, pour traiter efficacement des problèmes de… Lire la suite
ITÉRATION, mathématique

Écrit par :  Jean-Paul DELAHAYE,  Universalis

… cycle d'ordre 3, alors elle possède un cycle d'ordre n pour tout entier n > 1. *En algorithmique et en informatique, l'itération est une structure de contrôle essentielle offerte sous des formes diverses par tous les langages de programmation évolués et permettant de demander à un programme d'opérer un traitement répétitif sur… Lire la suite
KOLMOGOROV ANDREÏ NIKOLAÏEVITCH (1903-1987)

Écrit par :  Jean-Luc VERLEY

Dans le chapitre "Mathématiques appliquées"  : …  expérimentaux (loi des 4/5). Kolmogorov donnera une suite importante à ce travail en 1962. Enfin *Kolmogorov a fait d'importantes recherches en algorithmique. Ce sujet qui n'intéressait jusqu'alors que les logiciens (constructivistes) fit un immense bond en avant avec l'informatique et la théorie de l'information ; les outils comme l'entropie ou… Lire la suite
LOGIQUE MATHÉMATIQUE

Écrit par :  Daniel ANDLER, Roger MARTIN

Dans le chapitre "Effectivité, décidabilité"  : …  La notion de méthode effective de calcul, ou encore d'*algorithme, accompagne les mathématiques depuis les origines. Soit (Pi)i∈I une famille de problèmes formulés en termes mathématiques, telle que, pour chaque i de I, le problème Pi admette une réponse Ri… Lire la suite
NUMÉRIQUE ANALYSE

Écrit par :  Jean-Louis OVAERT, Jean-Luc VERLEY

Dans le chapitre "Concepts et méthodes de l'analyse numérique"  : …  à des intégrales, utilisation de lois continues en probabilité et en statistique. L'aspect *algorithmique. C'est une des originalités essentielles du point de vue numérique en analyse. On ne s'intéresse pas seulement à l'existence de suites d'approximation d'un nombre ou d'une fonction mais à la recherche d'algorithmes, c'est-à-dire de… Lire la suite
OPÉRATIONNELLE RECHERCHE

Écrit par :  Georges CULLMANN

Dans le chapitre "La théorie des graphes"  : …  graphes). Ses algorithmes sont de puissants auxiliaires pour l'analyste. D'abord parce que *l'algorithme, prescription détaillée des opérations à réaliser pour obtenir avec certitude la solution d'un type de problème, peut être confié à l'ordinateur ; ensuite parce que la manifestation fondamentale de l'organisation chez l'homme étant l'… Lire la suite
PROGRAMMATION

Écrit par :  Jean-François MONIN

Dans le chapitre "Structures de contrôle et structures de données, systèmes de types"  : …  autre élément important en programmation se trouve dans la structuration des données à manipuler. L'*algorithmique (science de la conception d'algorithmes) repose pour une bonne part sur la définition de structures de données efficaces et adaptées au problème ciblé. Les données élémentaires sont représentées par des mots mémoire de taille fixe :… Lire la suite
RÉCURSIVITÉ, logique mathématique

Écrit par :  Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE

Dans le chapitre "Définition logique"  : …  si sa fonction caractéristique est récursive. Intuitivement, cela signifie qu'il existe un *algorithme permettant de décider si un élément quelconque de Np appartient ou non à X. Ainsi, les ensembles finis, l'ensemble des nombres premiers, l'ensemble des nombres qui sont somme de deux nombres premiers impairs… Lire la suite
RÉELS NOMBRES

Écrit par :  Jean DHOMBRES

Dans le chapitre "Des calculs numériques"  : …  de même que l'inégalité stricte S < T. 2e temps : mise en place d'un processus *algorithmique de dichotomie avec un jeu quasiment algébrique sur les proportions. Par exemple, pour établir que l'inégalité S > T est impossible, Archimède inscrit un carré dans le cercle, puis divise en deux chaque arc sous-tendu, obtenant… Lire la suite

Afficher la liste complète (9 références)

Retour en haut

Médias

Médias de cet article dans l'Encyclopædia Universalis :

Algorithmes de calcul de π Arbre binaire Échelle de complexité

Retour en haut

Voir aussi

Retour en haut

Accueil - Contact - À propos
Consulter les articles d'Encyclopædia Universalis : 0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Consulter les articles d'Encyclopædia Britannica.
© 2012, Encyclopædia Universalis France S.A. Tous droits de propriété industrielle et intellectuelle réservés.

chargement du média