:: wikimiki.org ::
| Tri |
TriEn informatique ou en mathématiques, un algorithme de tri est un algorithme qui permet d'organiser une collection d'objets selon un ordre déterminé. Les objets à trier font donc partie d'un ensemble muni d'une relation d'ordre (de manière générale un ordre total).
Les ordres les plus utilisés sont l’ordre numérique et lexicographique (dictionnaire).
Il est évident que suivant la relation d'ordre considérée, une même collection d’objet peut donner lieu à divers arrangements, pourtant il est possible de définir un algorithme de tri indépendamment de la fonction d’ordre utilisée. Celui-ci ne fera qu'utiliser une certaine fonction d’ordre correspondante à une relation d’ordre qui doit permettre de comparer tout couple d'éléments de la collection.
Classification
La classification des algorithmes de tri est très importante, car elle permet de choisir le type d’algorithme le plus adapté au problème traité, tout en tenant compte des contraintes imposées par celui-ci.
Les principales caractéristiques qui permettent de différencier les algorithmes de tri sont : la complexité algorithmique, les ressources nécessaires et le caractère stable.
Complexité algorithmique
- La complexité algorithmique temporelle dans le pire des cas permet de fixer une borne supérieure du nombre d'opérations qui seront nécessaire à trier un ensemble de n éléments. On utilise pour symboliser cette complexité la notation de Landau : O.
- La complexité algorithmique temporelle en moyenne : c’est le nombre d'opérations élémentaires effectué en moyenne pour trier une collection d’éléments. Elle permet de comparer les algorithmes de tris et donne une bonne idée du temps d'exécution qui sera nécessaire à l’algorithme ; on arrive à l'estimer avec une précision assez importante.
- La complexité algorithmique spatiale (en moyenne ou dans le pire des cas) représente, quant à elle, l’utilisation mémoire que va nécessiter l'algorithme. Celle-ci peut dépendre, comme le temps d'exécution, du nombre de quantités à trier.
Dans la plupart des tris, T(n) = O(n2) bien que pour certains algorithmes, T(n) = O(n·log(n)).
On peut montrer que la complexité temporelle en moyenne et dans le pire des cas d’un algorithme basé sur une fonction de comparaison ne peut pas être meilleur que n·log(n)).
:Le problème du tri consiste, étant donné une suite u = (u1, u2, ..., un) d’éléments d’un ensemble totalement ordonné (par exemple ), à déterminer une permutation σ de 1, ..., n telle que : y = (uσ(1), uσ(2), ..., uσ(n)) soit triée. L'algorithme doit donc être en mesure de fournir toute les possibilités de permutation des termes de la suite, car il est équivalent de fournir la permutation σ que la suite triée y. Si l’on considère que les comparaisons sont les seules opérations élémentaires, le nombre de permutation de n éléments étant n! (factorielle n) et sachant que l’algorithme différencie deux cas à chaque comparaison, il faut que le nombre d’opérations élémentaires h soit tel que : ainsi
Les tris qui ne demandent que n·log(n) comparaisons en moyenne sont dits optimaux.
Pour certains types de données (entiers, chaînes de caractères de taille bornée), il existe cependant des algorithmes plus efficaces au niveau du temps d'exécution, comme le tri comptage ou le tri radix. Ces algorithmes n'utilisent pas la comparaison entre éléments (la borne n·log(n) ne s'applique donc pas pour eux) mais nécessitent des hypothèses sur les objets à trier. Par exemple, le tri comptage et le tri radix s'appliquent à des entiers que l'on sait appartenir à l'ensemble [1, m] avec comme hypothèse supplémentaire pour le tri radix que m soit de la forme 2k.
Caractère en place
Un algorithme est dit en place s'il n'utilise qu'un nombre très limité de variables et qu’il modifie directement le tableau qu’il est en train de trier. Ceci nécessite l’utilisation d'une structure de donnée adaptée (un tableau par exemple). Ce caractère est très important si on ne dispose pas d'une grande quantité de mémoire utilisable.
Caractère stable
Un algorithme est dit stable s'il garde l'ordre relatif des quantités égales pour la relation d'ordre.
Exemple, si on considère la suite d’éléments suivante :
(4, 1) (3, 1) (3, 7) (5, 6)
que l'on tri par rapport à leur première coordonnée (la clé), deux cas sont possibles, quand l’ordre relatif est respecté et quand il ne l'est pas :
(3, 1) (3, 7) (4, 1) (5, 6) (ordre relatif maintenu)
(3, 7) (3, 1) (4, 1) (5, 6) (ordre relatif changé)
Lorsque deux éléments sont égaux pour la relation d'ordre (c’est-à-dire qu'il ont la même clé), l'algorithme de tri conserve l'ordre dans lequel ces deux éléments se trouvaient avant son exécution. Les algorithmes de tri instables peuvent être retravaillés spécifiquement afin de les rendre stable, cependant cela peut être au dépend de la rapidité et/ou peut nécessiter un espace mémoire supplémentaire.
Exemples d'algorithmes de tri
- Tri à bulles : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place ;
- Tri par sélection : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, qui trie sur place ;
- Tri par insertion : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place. C'est le plus rapide et le plus utilisé pour un petit nombre de valeurs à trier ;
- Tri rapide (quick sort) : en moyenne, mais quadratique au pire cas, en place mais pas stable;
- Tri fusion (merge sort) : en moyenne et dans le pire des cas, stable mais pas en place ;
- Tri par tas (heap sort) : toujours environ deux fois plus lent que le tri rapide, c'est-à-dire aux alentours de , il est donc intéressant de l'utiliser si l'on soupçonne que les données à trier seront souvent des cas quadratiques pour le tri rapide;
- Tri comptage : dans certaines conditions c'est un algorithme linéaire, T(n) = O(n), stable mais nécessite l'utilisation d'une seconde liste de même longueur que la liste à trier ;
- Tri par base : c'est aussi un tri linéaire dans certaines conditions (moins restrictives que pour le tri par comptage), T(n) = O(n), stable mais nécessite aussi l'utilisation d'une seconde liste de même longueur que la liste à trier.
Lien externe
- [http://www.herve.name/algo.php Mémoire de synthèse sur les algorithmes de tri]
Tri
-
ja:ソート
ko:정렬 알고리즘
th:อัลกอริทึมการเรียง
Informatique ko:컴퓨터 과학 ja:情報工学 simple:Computer science th:วิทยาการคอมพิวเตอร์ zh-cn:计算机科学 zh-tw:計算機科學
oc:informatica]
Etymologiquement, Le terme informatique désigne l'automatisation du traitement de l'information par une machine (virtuelle ou physique). Dans son acception courante, l'informatique désigne de façon vague l'ensemble des sciences et techniques en rapport de près ou de loin avec l'information et l'ordinateur. Par exemple, l'informatique désigne aussi bien le matériel informatique que la conception et l'administration de la partie immatérielle d'un ordinateur : les logiciels.
La traduction anglaise étymologique serait informatics, mais l' usage tant en français qu'en anglais fait qu'une meilleure traduction serait probablement computer science, bien que ce terme fasse peut-être référence de façon plus explicite à ce que l'on pourrait appeler informatique fondamentale ou informatique scientifique. En anglais les termes distincts suivants sont utilisés :
- L'informatique fondamentale (Computer Science), ce qui ressort de l' épistémologie procédurale, soit notamment de l'étude des algorithmes, et donc indirectement des logiciels et des ordinateurs.
- L'ingénierie informatique (Computer Engineering), ce qui ressort de la fabrication et de l'utilisation du matériel informatique.
- L'ingénierie logicielle (Software Engineering), ce qui ressort de la modélisation et du développement des logiciels; ceci comprend le traitement des données (Data Processing), ce qui est du domaine de la mise en pratique des traitements de données.
- L'évolution des techniques et des technologies reliées à l'informatique (Information Technology).
Des professions aussi diverses que concepteur, développeur, responsable d'exploitation, ingénieur système, technicien de maintenance, matérielle ou logicielle, chercheur en informatique ou directeur d'un centre de calcul, relèvent du domaine de l'informatique. Néanmoins, le terme informaticien désigne le plus souvent ceux qui conçoivent, déploient et mettent en œuvre des solutions.
Étymologie
Le terme informatique a été créé en mars 1962 par Philippe Dreyfus à partir des mots «information» et «automatique». Il donna ce nom à l'entreprise qu'il venait de fonder, la Société d'Informatique Appliquée, sans breveter le mot informatique.
En France, l'usage officiel du mot a été consacré par Charles de Gaulle qui, en Conseil des ministres, a tranché entre «informatique» et «ordinatique», et le mot fut choisi par l'Académie française en 1967 pour désigner cette nouvelle discipline. En juillet 1968, le ministre fédéral de la Recherche scientifique d'Allemagne, Gerhard Stoltenberg, prononça le mot informatik lors d'un discours officiel au sujet de la nécessité d'enseigner cette nouvelle discipline dans les universités de son pays, et c'est ce mot qui servit aussitôt à nommer certains cours dans les universités allemandes. Le mot informatica fit alors son apparition en Italie et en Espagne, de même quinformatics au Royaume-Uni.
Pendant le même mois de mars 1962 Walter F. Bauer inaugura la société américaine Informatics Inc., qui elle breveta son nom et poursuivit toutes les universités qui utilisèrent ce nom pour décrire la nouvelle discipline, les forçant à se rabattre sur computer science, bien que les diplômés qu'elles formaient étaient pour la plupart des praticiens de l'informatique plutôt que des scientifiques au sens propre. L'Association for Computing Machinery, la plus grande association d'informaticiens au monde, approcha même Informatics Inc. afin de pouvoir utiliser le mot informatics pour remplacer l'expression computer machinery, mais l'entreprise déclina l'offre. La société Informatics Inc. cessa ses activités en 1985, achetée par Sterling Software.
Histoire
Voir l'article détaillé : Histoire de l'informatique
Les origines
Depuis des millénaires, l'Homme a créé et utilisé des outils l'aidant à calculer (abaque, boulier, etc.). Les premières machines mécaniques apparaissent entre le XVIIe et le . La première machine à calculer mécanique réalisant les quatre opérations aurait été celle de Wilhelm Schickard au , mise au point notamment pour aider Kepler à établir les tables rudolphines d'astronomie.
En 1642, Blaise Pascal réalisa également une machine à calculer mécanique qui fut pour sa part commercialisée et dont neuf exemplaires existent dans des musées comme celui des Arts et métiers et dans des collections privées (IBM).
La découverte tardive du mécanisme d'Antikhitère montre que les Grecs de l'Antiquité eux-mêmes avaient commencé à réaliser des mécanismes de calcul en dépit de leur réputation de mépris général pour la technique (démentie d'ailleurs par les travaux d'Archimède).
Cependant, il faudra attendre la définition du concept de programmation (illustrée en premier par Joseph Marie Jacquard avec ses métiers à tisser à cartes perforées, suivi de Boole et Ada Lovelace pour ce qui est d'une théorie de la programmation des opérations mathématiques) pour disposer d'une base permettant d'enchaîner des opérations élémentaires de manière automatique.
L'informatique moderne
L'ère des ordinateurs modernes commença avec les développements de l'électronique pendant la Seconde Guerre mondiale, ouvrant la porte à la réalisation concrète de machines opérationnelles. Au même moment, le mathématicien Alan Turing théorise le premier ce qu'est un ordinateur, avec son concept de machine universelle de Turing.
L'informatique est donc un domaine fraichement développé, même s'il trouve ses origines dans l'antiquité (avec la cryptographie) ou dans la machine à calculer de Blaise Pascal, au . Ce n'est qu'à la fin de la Seconde Guerre mondiale qu'elle a été reconnue comme une discipline à part entière et a développé des méthodes, puis une méthodologie qui lui étaient propres.
Son image a été quelque temps surfaite : parce que les premiers à programmer des ordinateurs avaient été des ingénieurs rompus à la technique des équations différentielles (les premiers ordinateurs, scientifiques, étaient beaucoup utilisés à cette fin), des programmeurs sans formation particulière, parfois d'ailleurs issus de la mécanographie, cherchaient volontiers à bénéficier eux aussi de ce label de rocket scientist afin de justifier des salaires rendus confortables par :
- le prix élevé des ordinateurs de l'époque (se chiffrant en ce qui serait des dizaines de millions d'euros aujourd'hui compte-tenu de l'inflation, il reléguait au second plan les considérations de parcimonie sur les salaires) ;
- l'aspect présenté comme peu accessible de leur discipline et un mythe de difficulté mathématique entretenu autour. En fait, les premiers ordinateurs ne se programmaient pas de façon très différente de celle des calculatrices programmables utilisées aujourd'hui dans les lycées et collèges, et maîtrisées par des élèves de quatorze ans mais le domaine était nouveau et l'algorithmique nécéssite un certain degré de concentration associé, peut-être à tort, à la réflexion pure.
L'émergence d'un aspect réellement scientifique dans la programmation elle-même (et non dans les seules applications scientifiques que l'on programme) ne se manifeste qu'avec la série The Art of Computer Programming de Donald Knuth, professeur à l'Université de Stanford, à la fin des années 1960, travail monumental encore inachevé en 2004. Les travaux d'Edsger Dijkstra, Niklaus Wirth et Christopher Strachey procèdent d'une approche également très systématique et elle aussi quantifiée.
On demandait à Donald Knuth dans les années 1980 s'il valait mieux selon lui rattacher l'informatique (computer science) au génie électrique — ce qui est souvent le cas dans les universités américaines — ou à un département de mathématiques. Il répondit : «Je la classerais volontiers entre la plomberie et le dépannage automobile» pour souligner le côté encore artisanal de cette jeune science.
Toutefois, la forte scientificité des trois premiers volumes de son encyclopédie suggère qu'il s'agit là plutôt d'une boutade de sa part. Au demeurant, la maîtrise de langages comme Haskell ou même APL demande un niveau d'abstraction tout de même plus proche de celui des mathématiques que des deux disciplines citées.
La miniaturisation des composants et la réduction des coûts de production, associées à un besoin de plus en plus pressant de traitement des informations de toutes sortes (scientifiques, financières, commerciales...) a entraîné une diffusion de l'informatique dans toutes les couches de l'économie comme de la vie de tous les jours.
Approche fonctionnelle
Comme énoncé ci-dessus, l'informatique est le traitement automatisé de données par un appareil électronique : l'ordinateur ; les germanophones parlent de elektronisch Daten Verarbeitung / EDV (« traitement électronique de données »), les anglophones dinformation technology / IT (« technologies de l'information »), c'est-à-dire :
- données ou informations : in fine, l'ordinateur manipule des nombres (d'où le terme anglais computer, littéralement « calculateur »), mais ces nombres peuvent représenter divers types d'informations :
- des... nombres bien évidemment, dans le cas de calculs scientifiques (flottants) ou comptables (décimal, ou binaire entier)... ;
- un texte, des lettres (caractères), que l'on peut mettre en forme avec un traitement de texte, imprimer, envoyer par courrier électronique... ;
- du dessin vectoriel (CAO, logiciels d'illustration, et de typographie) ;
- des images statiques (photographies) ou animées (vidéo), des hologrammes ;
- des sons, enregistrés (technique du direct to disk) ou bien fabriqués par l'ordinateur (synthétiseur), que ce soient des bruitages, de la musique (cf. musique et informatique) ou de la parole ;
:la conversion de ces informations en suite de nombres pose le problème du format des données, du codage et des formats normalisés (par exemple, représentations des nombres entiers ou à virgule flottante, format ASCII, Unicode, TeX ou RTF et polices PostScript ou TrueType pour les textes, formats bitmap, TIFF, JPEG, PNG, etc. pour les images fixes, formats QuickTime, MPEG pour les vidéos, interface MIDI pour la musique...).
- automatisé : l'utilisateur n'intervient pas, ou peu, dans le traitement des données ; le traitement est défini dans un programme qui se déroule tout seul, l'utilisateur se contente de fournir des paramètres de traitement ; le programme automatique se déroule selon un algorithme, l'établissement de ce programme est le domaine de la programmation.
- traitement : ces données sont :
- créées :
- nombres : acquisition automatique de données d'une expérience avec un ordinateur ;
- texte : taper un texte au clavier ;
- images : dessins réalisés à la souris ou sur une tablette graphique, synthèse d'image (pour présenter un projet – objet fictif en cours de conception –, imagerie médicale, dessin artistique – infographie –, film d'animation ou pixilation) ou numérisation d'une image existante (scanner, appareil photographique numérique) ou d'images animées (caméra numérique, webcam) ;
- sons enregistrés (microphone) ou recréés à partir d'une partition virtuelle (synthétiseur) ou d'un texte (synthèse vocale).
- analysées :
- nombres : l'analyse des nombres relève du domaine concerné (mathématiques, physique, économie...) ;
- texte : rechercher les occurrences de mots dans un texte pour en tirer des statistiques, aide à la correction orthographique et/ou grammaticale, et, plus généralement, traitement automatique des langues (TAL) ;
- images : on peut vouloir identifier un objet (reconnaissance de forme, reconnaissance des caractères ou OCR), ou bien déterminer la surface couverte par une couleur (par exemple pour quantifier une surface recouverte) ;
- sons : analyse spectrale, reconnaissance vocale.
- modifiées :
- nombres : calculs ;
- texte : modification d'un texte existant, traduction automatique dans une autre langue (ou langage de programmation) ;
- images : modification du contraste, de la luminosité, des couleurs, effets spéciaux ;
- sons : application d'effets (réverbération, distorsion, ajustement de la hauteur) ;
::comme il existe, selon les programmes et les besoins, une grande variété de codages possibles pour représenter chaque type d'information, beaucoup de traitements consistent à convertir les données d'un format vers un autre...
- archivées puis restituées :
- les moyens et techniques d'archivage varient en fonction de la durée de conservation souhaitée et des quantités de données en jeu : mémoires électroniques, bandes magnétiques, disques magnétiques ou optiques ;
- les moyens de restitution dépendent de la nature des données : écrans ou imprimantes pour le texte et les images, haut-parleurs ou instruments MIDI pour les sons...
Approche organisationnelle
L'informatique pour l'organisation est un élément d'un système de traitement d'information (les entrées peuvent être des formulaires papier par exemple) et d'automatisation. Depuis Henry Ford, l'automatisation des tâches ayant été identifiée comme un avantage concurrentiel, la question est : que peut-on automatiser ?
Autant il est relativement facile d'automatiser des tâches manuelles, autant il est difficile d'automatiser le travail intellectuel et parfois créatif. L'approche de l'informatique dans une organisation commence donc par l'élucidation des processus, c'est-à-dire modéliser le métier. Après validation, la MOA (Maîtrise d'Ouvrage) fournit les spécifications fonctionnelles de (l'ouvrage) qui vont servir de référence dans la conception pour la MOE (Maîtrise d'œuvre).
Cette conception sera alors effectuée dans le respect d'un Cycle de développement qui définit les rôles et responsabilités de chaque acteur. Ainsi, les échanges entre MOA et MOE ne se résument pas à la maîtrise des chantiers (tenue des délais et des coûts, et validation des livrables), la MOA et la MOE sont garantes (éventuellement responsables sur un plan juridique) de la cohérence des systèmes d'information, et de l'adéquation des solutions informatiques avec les problèmes utilisateurs finaux initialement constatés.
Matériel
Article détaillé : Matériel informatique
On utilise également le terme anglais hardware (littéralement « quincaillerie ») pour désigner le matériel informatique. Il s'agit de tous les composants que l'on peut trouver dans :
1. Les ordinateurs et leurs périphériques : un ordinateur est un ensemble de circuits électroniques permettant de manipuler des données sous forme binaire, représentées par des variations de signal électrique. Il existe différents types d'ordinateurs :
ordinateur 5150 datant de 1981, Système d'exploitation IBM-DOS 2.0]]
- Les micro-ordinateurs.
De bureau ou portables. Ils sont composés d'une unité centrale : un boîtier contenant la carte mère, l'alimentation, des unités de stockage. On y ajoute une console : un écran et un clavier. Divers périphériques peuvent leur être ajoutés, une souris, une imprimante, un scanner..ect;
scanner
- Les stations de travail.
Des micro-ordinateurs particulièrement puissants et chers, utilisés uniquement pour des besoins professionnels pointus (conception assistée par ordinateur). Ce terme était particulièrement en vogue dans les années 1980-1990. Depuis les années 2000, il n'est guère possible de concevoir une station de travail plus puissante qu'un micro-ordinateur haut de gamme ;
- Les mainframes.
Une armoire abrite l'unité centrale et l'alimentation, une ou plusieurs autres les périphériques de stockage (disque dur, sauvegarde) tandis que les moyens de communication et réseau (routeur, hubs, modem) sont dans la même pièce, mais dans des racks séparés. Une console d'administration (écran, clavier, imprimante) est généralement située dans ce même local ;
administration]
- Les PDA (Personal Digital Assistant, encore appelés organiseurs).
Ce sont des ordinateurs de poche proposant des fonctionnalités liées à l'organisation personnelle (agenda, calendrier, carnet d'adresse, etc.). Ils peuvent être reliés à Internet par différents moyens (réseau Wifi, Bluetooth, etc.).
- Et bien d'autres appareils.
Dans le domaine de l'informatique embarquée : téléphone, électroménager, automobile, armements militaires, etc.
Les cartes à puces, ou l'informatique industrielle.
Logiciel
Le logiciel désigne la partie à première vue immatérielle de l'informatique, l'organisation et le traitement de l'information : les programmes. On s'est en effet vite rendu compte que des machines techniquement très avancées pour leur époque, comme la Bull Gamma 60, restaient invendables tant qu'on n'avait pas de programmes à livrer pour les rendre immédiatement opérationnelles. IBM lança entre 1968 et 1973 une sorte d'ancêtre du logiciel libre avec son ordinateur 1130, politique qui assura à celui-ci par effet boule de neige un succès immédiat et planétaire, mais les conclusions d'un procès antitrust lui interdirent de distribuer bénévolement du logiciel.
Le monde des mainframes classe les logiciels en catégories suivantes :
- systèmes d'exploitation ;
- bases de données, comme DB2, Ingres ou Oracle ;
- programmes de communication, comme NCP ou RSCS ;
- moniteurs de télétraitement ;
- systèmes transactionnels, comme CICS ;
- systèmes de temps partagé, utilisés pour le calcul ou le développement ;
- compilateurs traduisant les langages en instructions machine et appels système ;
- tout le reste entrait en une catégorie nommée Logiciels applicatifs.
Plus simplement on distingue généralement trois types de logiciels (par ordre de proximité du matériel) :
- le firmware
- le système d'exploitation
- les logiciels et applications utilisateur (en anglais software)
On classe aussi les logiciels en libre et propriétaire, bien que les deux soient parfois panachés à des degrés divers. Certains ont une fonction bureautique ou multimédia comme par exemple les jeux vidéo. Certains logiciels ont acquis des noms connus de tous.
Le noyau du système d'exploitation crée le lien entre le matériel et le logiciel. Un logiciel, quand il est fourni sous sa forme binaire, serait utilisable uniquement avec un système d'exploitation donné (car il en utilise les services), et ne fonctionnerait que sur un matériel spécifique (car il en utilise le code d'instructions). Une conception plus récente, depuis le milieu de années 1980, consiste à distribuer les logiciels tous binaires confondus, et à les munir d'un système de licences par jetons ou tokens permettant l'usage de N copies simultanées du logiciel sur le réseau, tous matériels confondus. Cette approche est majoritaire dans le monde UNIX.
À l'initiative de Richard Stallman et du GNU, à partir de 1985, une mouvance de programmeurs refuse cette logique propriétaire et ceux-ci se muent en concepteurs inventifs pour se lancer dans le développement d'outils et de bibliothèques système libres compatibles avec le système UNIX. C'est pourtant le projet indépendant Linux, initié par Linus Torvalds, basé sur les travaux et les outils du GNU, qui aboutira dans la création d'un système d'exploitation complet et libre.
Une bonne partie des logiciels actuels fonctionnent dans un environnement graphique pour interagir avec l'utilisateur.
La diversité des systèmes informatiques a fait apparaître une technique visant à combiner le meilleur de chacun de ces univers : l'émulateur.
Il s'agit d'un logiciel permettant de simuler le comportement d'un autre système dans celui que l'on utilise,
- soit pour qu'une machine semble être une autre (voir IBM 1130),
- soit pour simuler le comportement d'un système d'exploitation (par exemple DOS ou Windows sous Linux).
Le terme anglais est software, à l'origine un jeu de mot entre hardware (« quincaillerie », pour désigner le matériel) et l'opposition soft/hard (mou/dur), opposition entre le matériel (le dur) et l'immatériel (le mou). Les traductions françaises matériel et logiciel rendent parfaitement cette opposition et cette complémentarité.
Le logiciel réalise normalement une fonction attendue de ses utilisateurs. Néanmoins, des effets secondaires (parfois nommés par contresens de traduction effets de bord) existent. Parfois même, certains logiciels sont destinés à nuire, comme les virus informatiques, nommés en anglais, par analogie avec software : malware (qu'on pourrait traduire par le néologisme nuisiciel, ou logiciel malveillant).
La création des logiciels
Un projet informatique s'inscrit dans un cycle de développement qui définit les grandes étapes de la réalisation (planification), de la manière dont on passe d'une étape à l'autre (modèle incrémental, en V, en spirale, etc.). Pour les petits projets (ou les petites équipes de développement), cette réflexion est souvent négligée (on se répartit les modules et chacun développe dans son coin). Ceci est une cause fréquente d'erreurs (bogues) et de non-conformité (le produit final n'est pas conforme aux attentes de l'utilisateur). Mais même les énormes projets, avec beaucoup de moyens, sont victimes de cette négligence ; ainsi, l'échec du premier vol d'Ariane 5 fut dû à un problème de logiciel, etc. Un projet peut alors intégrer une approche de la qualité et de la sûreté de fonctionnement des systèmes informatiques afin de contrôler autant que possible le produit final.
Un projet comprend les étapes suivantes :
- l'établissement d'un cahier des charges qui définit les spécifications auxquelles devra répondre le logiciel ;
- la définition de l'environnement d'exécution (architecture informatique) :
- type(s) d'ordinateur sur lequel le logiciel doit fonctionner (station de calcul, ordinateur de bureau, ordinateur portable, assistant personnel, téléphone portable, guichet automatique de banque, ordinateur embarqué dans un véhicule ;
- type et version du(des) système(s) d'exploitation sous-jacent ;
- périphériques nécessaires à l'enregistrement des données et à la restitution des résultats (capacité de stockage, mémoire vive, possibilités graphiques...) ;
- nature des connexions réseau entre les composants (niveau de confidentialité et de fiabilité, performances, protocoles de communication...) ;
- la conception de l'application et de ses constituants, et notamment de l'interactivité entre les modules développés : structure des données partagées, traitement des erreurs générées par un autre module... : c'est le domaine du génie logiciel ;
- la mise en place d'une stratégie de développement :
- répartition des tâches entre les développeurs ou les équipes de développement, qui vont assurer le codage et les tests ;
- le plan de test du logiciel, pour s'assurer qu'il remplit bien la mission pour laquelle il a été écrit, dans toutes les conditions d'utilisation qu'il pourra normalement rencontrer, mais aussi dans des cas limites.
Après chacune de ces phases, on peut avoir une étape de recette, où le client va valider les choix et les propositions du maître d'œuvre.
La phase de programmation consiste à décrire le comportement du logiciel à l'aide d'un langage de programmation. Un compilateur sert alors à transformer ce code écrit dans un langage informatique compréhensible par un humain en un code compréhensible par la machine, le résultat est un exécutable. On peut également, pour certains langages de programmation, utiliser un interpréteur qui exécute un code au fur et à mesure de sa lecture, sans nécessairement créer d'exécutable. Enfin, un intermédiaire consiste à compiler le code écrit vers du bytecode. Il s'agit également d'un format binaire, compréhensible seulement par une machine, mais il est destiné à être exécuté sur une machine virtuelle, un programme qui émule les principales composantes d'une machine réelle. Le principal avantage par rapport au code machine est une portabilité théoriquement accrue (il « suffit » d'implanter la machine virtuelle pour une architecture donnée pour que tous les programmes en bytecode puissent y être exécutés), portabilité qui a fait, après sa lenteur, la réputation de Java. Il convient de noter que ces trois modes d'exécution ne sont nullement incompatibles. Par exemple, OCaml dispose à la fois d'un interpréteur, d'un compilateur vers du bytecode, et d'un compilateur vers du code natif pour une grande variété de processeurs. Une fois écrit (et compilé si nécessaire), le code devient un logiciel.
Pour des projets de grande amplitude, nécessitant la collaboration de beaucoup de programmeurs, voire de plusieurs équipes, on a souvent recours à une méthodologie commune (par exemple MERISE) pour la conception et à un atelier de génie logiciel (AGL) pour la réalisation.
Au cours de la programmation et avant la livraison du produit final, le programme est testé afin de vérifier qu'il fonctionne bien (y compris dans des cas d'utilisation en mode dégradé) et qu'il est conforme aux attentes de l'utilisateur final. Les tests intermédiaires permettent de s'assurer que chaque module de code réalise correctement une fonction : ce sont les tests unitaires. Les tests finals qui vérifient le bon enchaînement des modules et des traitements sont des tests d'intégration.
Pour certaines applications demandant un haut niveau de sûreté de fonctionnement, les tests sont précédés d'une étape de vérification, où des logiciels spécialisés effectuent (généralement sur le code source, mais parfois aussi sur le code compilé) un certain nombre d'analyses pour vérifier partiellement le bon fonctionnement du programme. Il n'est toutefois pas possible (et des théorèmes mathématiques montrent pourquoi), de garantir la parfaite correction de tout logiciel par ce moyen et la phase de test reste donc nécessaire. Elle se complète aussi, lorsqu'il s'agit d'une évolution d'une application existante, de nombreux tests automatisés de non-régression.
Statistiques : la création d'un logiciel est une tâche ardue ; environ 31 % des projets informatiques sont abandonnés avant d'être terminés, plus de 50 % des projets coûtent le double du coût initialement estimé et seulement 15 % des projets finissent dans les temps et selon le budget défini. Les besoins de seule maintenance de l'existant peuvent prendre jusqu'à 50 % des effectifs d'une équipe chargée d'un logiciel (or, c'est là une fonction pénible, ingrate, peu valorisante et qui rebute et démotive les bons programmeurs).
Traitement de l'information
L'information, pour être traitée, doit être :
- représentée par un codage :
- on utilise un système de numération binaire, où l'élément unitaire informationnel est le bit (contraction de l'anglais binary digit : chiffre binaire). Les bits sont généralement regroupés par huit, pour constituer des octets (ou bytes). Un octet peut être représenté par la séquence des bits qui le constituent (par exemple : 00101110) ou par une paire de valeurs hexadécimales (pour le même exemple : 2E), plus compact. Le choix du binaire ne résulte pas de la mystique, mais tout simplement d'utiliser de simples circuits de commutation, qui ont de très larges tolérances et par conséquent de faibles coûts ;
- on représente la structuration de l'information pour permettre des échanges entre composants logiciels et entre composants matériels. Pour cela, on définit des langages et des formalismes de représentation.
- stockée dans des systèmes permanents (mémoires dites de masse) ou non (mémoires dites volatiles).
Échanges de données : protocoles et normes
Les protocoles définissent une manière de procéder, notamment pour codifier la façon dont deux entités communiquent (modules ou couches logicielles, périphériques, etc.). On parle notamment de protocole de communication lorsqu'on veut définir des mécanismes de contrôle sur la manière dont l'échange d'information est réalisé.
Un protocole peut ainsi définir :
- un langage de description d'instructions et de données graphiques (exemple : AGP) ;
- un standard de commandes et de flux d'information pour une mémoire de masse (exemples : SCSI, FireWire, IDE, Serial ATA) ;
- des échanges entre le processeur et des cartes d'extension (exemples : PCI, PCI Express, ISA) ;
- des modalités de transfert d'information entre périphériques (exemple : USB) ou sur un réseau TCP/IP, Internet, ATM, X.25) ;
- des commandes entre un client et un serveur (exemples : POP3, IMAP, HTTP, FTP …) ;
- des échanges de données informatisés spécifiques (exemples : EDI, EAI, X.400, X.500).
Certains protocoles sont définis par des normes pour permettre l'interopérabilité des matériels ou de logiciels les mettant en œuvre. D'autres normes définissent, toujours dans le domaine de l'échanges de données :
- des langages de représentation d'information sans pour autant définir la manière dont cette information peut être échangée (exemples : ASN.1, XML) ;
- des architectures de réseaux (exemples : Modèle OSI, Wifi, Ethernet, Token-Ring).
Stockage des données
En matière de stockage d'information, on distingue le dispositif permettant de l'enregistrer physiquement (périphériques et composants) de la manière dont on structure et représente l'information pour faciliter son traitement.
Mémoire de masse
:Fichier de cartes perforées
:Bande magnétique
:Disque amovible magnétique (Disquette)
:Disque magnéto-optique
:Disque dur (disque magnétique embarquant le mécanisme, l'électronique et les têtes de lecture)
:Disque optique amovible (CD-ROM, CD-R, CD-RW mais aussi DVD-ROM, DVD-R, DVD-RW, DVD+R, DVD+R DL, DVD+RW, DVD-RAM, GD-ROM, HD-DVD, Blu-ray)
:Mémoire électronique non volatile (Mémoire flash, clé USB)
Mémoire volatile
:RAM
Organisation des données en vue du stockage
:Formats (extensions) de fichiers
:Système de fichiers
:Base de données
:Annuaire
Approches scientifiques
En dehors des aspects industriels et technologiques décrits jusqu'ici, l'informatique est une discipline scientifique à part entière.
:Algorithmique
:Algèbre de Boole
:Calculabilité
:Géométrie algorithmique
:Lambda-calcul
:Logique
:Model checking
:Théorie de l'information
:Théorie des graphes
:Théorie de la complexité
:Théorie de la calculabilité
:Théorie des automates finis
Applications
:Bio-informatique
:Calcul parallèle
:Cryptographie
:Exploration de données (data mining)
:Informatique grand système (mainframe)
:Informatique de gestion
:Informatique industrielle
:Informatique décisionnelle
:Imagerie Informatique
:Intelligence artificielle
:Interface homme-machine
:Micro-informatique
:Traitement du signal
:Hypermédias
:Informatique musicale
Annexes
- Informathèque
- Abréviations en informatique
- Dictionnaire informatique
- Informatique alternative
- Liste des articles d'informatique
- Personnes célèbres en informatique
- Revues informatiques sur papier
- Sécurité informatique
- Sites d'informations sur internet
- Terminologie de la distribution informatique
- Réseaux de neurones
- Musique et informatique
- Ordinateur quantique
- Hello_world
- Visual Information Exploration
-
MathématiquesLes mathématiques peuvent être définies de plusieurs façons, complémentaires :
- la science des nombres et de l’espace
- la science des formes de déduction
- la science des structures, des modèles ou de tous les mondes possibles
On pourrait aussi parler de la Mathématique pour souligner que les diverses composantes de celle-ci (algèbre, analyse, géométrie, etc.) sont en fait seulement des façons différentes d'étudier ou de créer des systèmes structurés par des relations (notion généralisée de graphes). Dans cette optique la mathématique est vue comme un édifice à construire ou à reconstruire.
Mathématique vient du grec μάθημα (mathêma), science, connaissance, apprentissage (mathematikos : qui aime apprendre).
L’origine historique des mathématiques est liée à leurs applications concrètes, le commerce, la mesure des surfaces, la prédiction des évènements astronomiques.
L'adjectif mathématique qualifie tout objet, concept ou terme relatif aux mathématiques. Dans ce sens il s'accorde au mot auquel il est associé, contrairement au terme qui désigne la science des mathématiques, qui est le plus souvent employé au pluriel. La Mathématique, au singulier, n'est plus guère usitée que de manière didactique.
L'expression « c'est mathématique » signifie qu'il existe une logique interne et inéluctable propre à l'évènement ou à la série d'évènements ainsi commentée.
:« La possibilité même de la science mathématique semble une contradiction insoluble. Si cette science n'est déductive qu'en apparence, d'où lui vient cette parfaite rigueur que personne ne songe à mettre en doute ? Si, au contraire, toutes les propositions qu'elle énonce peuvent se tirer les unes des autres par les règles de la logique formelle, comment la mathématique ne se réduit-elle pas à une immense tautologie ? Le syllogisme ne peut rien nous apprendre d'essentiellement nouveau et, si tout devait sortir du principe d'identité, tout devrait aussi pouvoir s'y ramener. »
::Henri Poincaré, La Science et l'hypothèse
Définitions des mathématiques
La science des nombres et de l’espace
L'étude des mathématiques commence avec les nombres, tout d'abord avec les nombres naturels et les nombres entiers. Les règles gouvernant les opérations usuelles sur les nombres (addition, multiplication, soustraction, division) font partie de l'arithmétique élémentaire. L'algèbre élémentaire est fondée sur l'abstraction de ces règles. L'étude des surfaces simples (polygones, cercles,...) forme la géométrie élémentaire...
La science des formes de déduction
Une déduction consiste à partir de prémisses pour arriver à une conclusion en procédant par des étapes logiques. On peut dire que toutes les sciences sont mathématiques, même l’histoire, au sens où elles font toutes des déductions, et parce qu’une déduction a toujours quelque chose de mathématique, pourvu qu’elle soit juste.
Cependant, en mathématiques, l’étude de la forme du raisonnement, indépendamment de ses objets, a une importance cruciale. Montrons-le sur un exemple.
Les mêmes axiomes, ceux des espaces vectoriels, peuvent être utilisés à la fois pour étudier des espaces géométriques, l’espace euclidien par exemple et pour étudier l’ensemble des solutions d’une équation différentielle linéaire. Les théorèmes sur les espaces vectoriels sont donc valables à la fois pour la géométrie euclidienne et pour les équations différentielles linéaires. On peut considérer que la théorie abstraite des espaces vectoriels consiste à étudier toutes les déductions qui partent des mêmes axiomes, indépendamment des objets auxquels ils sont appliqués. On étudie alors les formes de déduction et non les objets auxquels ces formes sont appliquées.
Cette définition convient bien aux mathématiques appliquées. De nombreuses théories abstraites (les nombres entiers et réels, les fonctions réelles de variable(s) réelle(s) et les équations différentielles, les espaces vectoriels, les groupes, la théorie des probabilités, ...) ont une utilité générale pour toutes les sciences, parce qu’elles peuvent être appliquées à de nombreux objets. Le travail des mathématiques appliquées consiste à développer des théories, dont la valeur est universelle, en vue d’aider les autres sciences dans leurs recherches des conséquences.
La science de tous les mondes possibles
Pour un mathématicien, rien n’est impossible, sauf ce qui est contradictoire. Par là, on veut dire qu’un discours non-contradictoire parle d’un monde concevable, imaginable, idéal. Les mondes possibles sont parfois appelés des structures, lorsqu’ils sont très abstraits, ou des modèles.
De ce point de vue, la mathématique est la théorie de tout ce qu’on peut imaginer.
On croit souvent à tort que la connaissance de tous les possibles est une ambition démesurée et irréalisable mais elle ne l’est pas. Elle est à notre portée. Il est même très facile de connaître des vérités universelles, valables pour tous les possibles, le principe du tiers exclu par exemple. Tout énoncé sur un monde possible y est ou bien vrai, ou bien faux. Ce n’est pas forcément très intéressant mais c’est un début.
Le travail des mathématiques pures consiste à augmenter notre capacité à connaître tous les possibles. Il se trouve qu’il y a des théories particulières (les nombres, les groupes, ...) qui jouent un rôle privilégié dans cette connaissance, et qu’elles sont souvent, mais pas toujours, les mêmes que celles qui intéressent les mathématiques appliquées. C’est pourquoi les structures étudiées ont souvent leur origine dans les sciences naturelles, plus communément en physique. Toutefois, un grand nombre de structures sont purement internes aux mathématiques, unifiant différents champs d'application ou étant des outils aidant aux calculs.
En fait, les mathématiques sont la science de la mesure.
La logique et les théories des ensembles
La logique énonce les règles, ou principes, qu’il faut respecter pour faire des déductions correctes.
Les théories des ensembles sont des théories très générales qui permettent de formuler et de prouver toutes les connaissances mathématiques.
- Fondation des mathématiques
Logique
- Logique
- Calcul propositionnel
- Calcul des prédicats
- Déduction naturelle
- Logiques modales
- Théorie des modèles
- Incomplétude
Théories des ensembles
- Théorie des ensembles
- Axiomes de Zermelo-Fränkel
- Théorie des catégories
L’arithmétique et les mathématiques discrètes
Arithmétique
- Théorie des nombres
- Congruences
- Divisibilité
- PGCD / PPCM
- Théorème de d'Alembert-Gauss
- Identité de Bézout
- Petit théorème de Fermat
- Équations diophantiennes
- Cohérence des axiomes de l'arithmétique formelle
- Cryptologie
- Fonctions L
- Dernier théorème de Fermat
Mathématiques discrètes
- Mathématiques discrètes
- Théorie des graphes
Les géométries
- Géométrie
- Coupe pentagonale de la pyramide à base carrée
- Géométrie euclidienne
- Géométries non euclidiennes
- Écrire les figures de la géométrie
- Géométrie projective
- Géométrie différentielle
- Géométrie algébrique
- Géométrie non commutative
- Courbe plane
- Orientation
- Anamorphose
Trigonométrie
- Trigonométrie classique et formules
- Trigonométrie sphérique
L’algèbre
- Algèbre
- Structure algébrique
- Algèbre élémentaire
- Algèbre abstraite
- Théorie des catégories
- Théorie des groupes
- Algèbre linéaire
- Algèbre multilinéaire
- Théorie de la représentation
L’analyse et la topologie
Analyse
- Analyse
- Suites
- Séries
- Analyse réelle
- Nombres complexes, Analyse complexe
- Analyse fonctionnelle
- Algèbre des opérateurs
- Analyse p-adique
- Analyse rigide
- Équations différentielles
- Équations aux dérivées partielles
- Analyse non standard
- Analyse vectorielle
- Intégrale de Lebesgue
- Intégrale de Riemann
- Développement limité
Topologie
- Topologie
- Espaces topologiques
- Espaces métriques
- Topologie algébrique
- Théorie des nœuds
- Théorie des tresses
- K-théorie
La théorie des probabilités
- Probabilités
- Statistiques
Mathématiques appliquées
Les domaines des mathématiques appliquées utilisent la connaissance des mathématiques à fin de résolution des problèmes du monde réel.
- Recherche opérationnelle
- Optimisation
- Modèle mathématique
- Probabilité
- Statistiques
- Mathématiques financières
- Mathématiques commerciales
Mathématiques récréatives
- Mathématiques récréatives
- Jeux mathématiques
Mathématiques élémentaires (non universitaires)
- Mathématiques élémentaires
- Algèbre élémentaire
- Analyse élémentaire
- Arithmétique élémentaire
- Géométrie élémentaire
- Aire de surfaces usuelles
- Solides usuels
- Volume de solides usuels
- Logique élémentaire
- Probabilité élémentaire
- Statistique élémentaire
Statistique élémentaire
Techniques de calcul
- Techniques de calcul mental
- Règle à calcul
- Boulier
- Liste des articles de technique de calcul
- Critère de divisibilité
- Calculs de longueur
Histoire des mathématiques
- Histoire des mathématiques
- Histoire des polynômes
- Histoire du calcul infinitésimal
Voir aussi
Annexes
- Wikipédia:Index thématique
- Mathématiciens célèbres
- Abréviations en mathématiques
- Associations de mathématiciens
- :en:Clay Mathematics Institute
- Association Bourbaki
- Femmes et mathématiques
- Société Mathématique de France
- Société de Mathématiques Appliquées et Industrielles
- Concours de mathématique
- Olympiades de mathématiques
- Médaille Fields
- Nombre
- Norme d'opérateur
- Numération
- Numération romaine
- Tables
- Table d'addition
- Table de multiplication
- Table des bases
- Table des diviseurs
- Table des facteurs premiers
- Table des symboles mathématiques
- Table de constantes mathématiques
- Table de limites
- Table de dérivées
- Table de primitives
- Table d'intégrales
Liens internes
- Conjecture
- Construction des objets courants
- Erreur de signes
- Langage formel mathématique
- Liste des articles de mathématiques
- Liste des fonctions mathématiques
- Liste des nombres
- Ordre de grandeur (nombre)
- Nombre figuré
- Liste des 23 problèmes de Hilbert
- Vocabulaire multilingue mathématique
Liens externes
- [http://math-editor.sourceforge.net/fr Barre Maths] Un modèle libre pour Microsoft Word permettant d'écrire des formules mathématiques très efficacement
- [http://www.apprendre-en-ligne.net/madimu/ Madimu] Un cours complet sur tous les thèmes traités de la 1ère à la 3e année de lycée... en Suisse
- [http://dmoz.org/World/Fran%c3%a7ais/Sciences/Math%c3%a9matiques/ Répertoire Mathématiques dmoz.org]
- [http://www.les-mathematiques.net www.les-mathematiques.net] Cours de qualité niveau deug/licence/agreg
- http://planetmath.org/ : encyclopédie collaborative, libre (GFDL) en anglais sur les mathématiques.
- [http://www.ilemaths.net l'île des mathématiques] : cours et exercices pour le collège et lycée, forums d'entraide scolaire.
- [http://www.mathematex.net/phpBB2/index.php MathemateX] Forum d'entraide mathématiques avec support Latex
- [http://www.maths-forum.com/ Forum Mathématiques] Forum d'entraide mathématiques
- [http://www.ac-creteil.fr/Colleges/93/jmoulinmontreuil/mathematiques/menu/frameset.html Maths au collège :] animations Flash illustrant les plus célèbres démonstrations du théorème de Pythagore, des illusions d'optique et des courbes du plan tracées dynamiquement (hypocycloïdes...).
- [http://maxima.sourceforge.net/ Maxima], le logiciel libre (GPL) le plus sophistiqué pour les opérations algébriques.
- [http://pari.math.u-bordeaux.fr/ PARI/GP], un logiciel libre très utilisé en théorie des nombres.
- [http://www.chez.com/ophtasurf/illusion.htm Illusions d'optique] : des centaines d'illusions d'optique géométriques
- [http://perso.wanadoo.fr/jpq/ perso.wanadoo.fr/jpq/] propose des animations Java pour illustrer des notions de mathématiques et en particulier de probabilités.
- [http://perso.wanadoo.fr/gilles.costantini Bac à Maths] des documents étoffés pour le lycée et les études supérieures.
- [http://www.mathprepa.com Mathprépa.com] : une zone de mathématiques pour étudiants en classes préparatoires
- [http://www.xasa.com/directorio/mozilla/Top/World/Fran%c3%a7ais/Sciences/Math%c3%a9matiques/ Répertoire, Usenet]
- [http://www.forum.math.ulg.ac.be/ Math en ligne] : Forum d'aide en math fait par l'université de Liège
- [http://www.chronomath.com/ Chronomath] : Une chronologie des mathématiques très riche.
- [http://www.maths-express.com/ Maths-Express] : Des annales pour le baccalauréat, concours général et olympiades.
- [http://forum.maths-express.net/ Forum de maths] : Pour les élèves de lycée préparant le baccalauréat, le concours général ou les olympiades.
- [news:fr.sci.maths Forum Usenet francophone]; ses [http://groups.google.fr/groups?q=insubject%3AFAQ+OR+insubject%3Aconseils+group%3Afr.sci.maths&scoring=d&filter=0 FAQ et CU]
- [news:fr.education.entraide.maths Forum francophone d'entraide]
- [http://groups.google.fr/groups?q=sci.math Forums Usenet anglophones]
- [http://mathworld.wolfram.com/ La plus complète des ressources en Mathématiques (en anglais)]
- [http://www.contraintes.net Un site consacré aux contraintes artistiques volontaires] et sa rubrique dédié aux [http://www.contraintes.net/index.php/Bande_dessin%C3%A9e_%C3%A0_contraintes mathématiques à contraintes]
- [http://www.aromath.net @romath] Un site entièrement consacré aux mathématiques et à leur enseignement dans les lycées français.
- [http://www.SoSMath.be SoSMath.be:Forum d'aide en Math (SoSMath.fr)]
- [http://www.aide-en-maths.com: Forum d'aide en Maths pour le secondaire (aide-en-maths.com)]
-
ja:数学
ko:수학
ms:Matematik
simple:Mathematics
th:คณิตศาสตร์
zh-min-nan:Sò·-ha̍k
Algorithme ko:알고리즘 ja:アルゴリズム th:อัลกอริทึม
Catégorie:Algorithmique
On nomme algorithmique la science des algorithmes, visant à étudier les opérations nécessaires à la réalisation d'un calcul. On parle également de procédé ou de procédure. Une recette de cuisine constitue par exemple un algorithme parfaitement défini.
Historique
Antiquité
Les algorithmes dont on a retrouvé des descriptions exhaustives ont été utilisés dès l'époque des Babyloniens, pour des calculs concernant le commerce et les impôts.
L'algorithme le plus célèbre est celui attribué à Euclide permettant de trouver le plus grand commun diviseur de deux nombres.
Etude systématique
L'algorithmique a été systématisée par le mathématicien persan Al Kwarizmi (780-850), auteur d'un ouvrage décrivant des méthodes de calculs algébriques (ainsi que d'un autre introduisant le zéro des Indiens). Son nom donna au moyen-âge le nom "algorisme" qui devint algorithme avec lady Ada Lovelace, fille de lord Byron et assistante de Charles Babbage (1792-1871).
On peut voir une allusion à la méthode algorithmique chez René Descartes dans le Discours de la méthode : « diviser chacune des difficultés que j'examinerois, en autant de parcelles qu'il se pourroit, et qu'il seroit requis pour les mieux résoudre. » Néanmoins, cette approche ne parle ni de boucles, ni d'itérations.
Le substantif algorithmique désigne la méthode utilisant des algorithmes. Le terme est également employé comme adjectif.
Un algorithme énonce une résolution sous la forme d'une série d'opérations à effectuer. La mise en œuvre de l'algorithme consiste en l'écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d'un programme informatique.
Les informaticiens utilisent fréquemment l'anglicisme implémentation pour désigner cette mise en œuvre. L'écriture en langage informatique est aussi fréquemment désignée par le terme « codage », qui n'a ici aucun rapport avec la cryptographie, mais qui se réfère au terme « code source » pour désigner le texte, en langage de programmation, constituant le programme. L'algorithme devra être plus ou moins détaillé selon le niveau d'abstraction du langage utilisé ; autrement dit, une recette de cuisine doit être plus ou moins détaillée en fonction de l'expérience du cuisinier.
Exemples d'algorithme
Il existe un certain nombres d'algorithmes classiques, utilisés pour résoudre des problèmes ou plus simplement pour illustrer des méthodes de programmation. On se réfèrera aux articles suivants pour de plus amples détails :
- Tours de Hanoï, problème célèbre illustrant la programmation récursive.
- Problème du tri, ou comment trier un ensemble de nombres le plus rapidement possible.
- Problème des huit dames, placer huit dames sur un échiquier sans qu'elles puissent se prendre entre elles.
La principale notion mathématique dans le calcul du coût d'un algorithme précis sont les notions de négligeabilité (notée o(f(n)), « petit o ») et de domination (notée O(f(n)), « grand o »), où f est une fonction mathématique de n, variable désignant la quantité d'informations (en bits, en nombre d'enregistrements…) manipulée dans l'algorithme. Les fonctions mathématiques relèvent de l'analyse. En algorithmique on trouve souvent des complexités du type :
- indépendant de la taille de la donnée
- , complexité logarithmique
- , complexité linéaire
- , complexité quasi-linéaire
- , complexité quadratique
- , complexité cubique
- , complexité polynômiale
- , complexité quasi-polynômiale
- , complexité exponentielle
- , complexité factorielle
Sans entrer dans les détails mathématiques, on peut dire que lorsque l'on calcule l'efficacité d'un algorithme (sa complexité algorithmique), on cherche davantage à connaître l'évolution du nombre d'instructions de base en fonction de la quantité de données à traiter (par exemple, dans un
algorithme de tri, le nombre de lignes à trier), que le coût exact en secondes et en quantité de mémoire. Baser le calcul de la complexité d'un algorithme sur le temps qu'un ordinateur particulier prend pour effectuer le-dit algorithme ne permet pas de prendre en compte la structure interne de l'algorithme ni la particularité de l'ordinateur : selon sa charge de travail, la vitesse de son processeur, la vitesse d'accès aux données ou même l'exécution de l'algorithme (qui peut faire intervenir le hasard) le temps d'exécution ne sera pas le même.
Quelques indications sur l'efficacité des algorithmes
Souvent, l'efficacité d'un algorithme n'est connue que de manière asymptotique, c'est-à-dire pour de grandes valeurs du paramètre n.
Lorsque ce paramètre est suffisamment petit, un algorithme de complexité supérieure peut en pratique être plus efficace.
Ainsi, pour trier un tableau de 30 lignes (c'est un paramètre de petite taille), il est inutile d'utiliser un algorithme évolué comme
Quicksort (l'un des algorithmes de tri les plus efficaces en moyenne) : l'algorithme de tri le plus trivial sera suffisamment efficace.
À noter aussi : entre deux algorithmes dont la complexité est identique, on cherchera à utiliser celui dont l'occupation mémoire est la plus faible. L'analyse de la complexité algorithmique peut également servir à évaluer l'occupation mémoire d'un algorithme. Enfin, le choix d'un algorithme plutôt qu'un autre doit se faire en fonction des données que l'on s'attend à lui fournir en entrée. Ainsi, le Quicksort (ou tri rapide), lorsque l'on choisit le premier élément comme pivot, se comporte de façon désastreuse si on l'applique à une liste de valeur ... déjà triée ! Il n'est donc pas judicieux de l'utiliser si on prévoit que le programme recevra en entrée des listes à peu près triées.
Un autre paramètre à prendre en compte est la localité de l'algorithme. Par exemple pour un système à mémoire virtuelle qui dispose de peu de mémoire (par rapport au nombre de données à traiter), le Tri rapide sera normalement plus efficace que le Tri par tas car le premier ne passe qu'une seule fois sur chaque élément de la mémoire tandis que le second accède à la mémoire de manière discontinue (ce qui augmente le risque de "swapping").
Les heuristiques
Pour certains problèmes, les algorithmes ont une complexité beaucoup trop grande pour obtenir un résultat en temps raisonnable, même si l'on pouvait utiliser une puissance de calcul phénoménale. On est donc amené à rechercher une solution la plus proche possible d'une solution optimale en procédant par essais successifs. Puisque toutes les combinaisons ne peuvent être essayées, certains choix stratégiques doivent être faits. Ces choix, généralement très dépendants du problème traité, constituent ce qu'on appelle une heuristique. Le but d'une heuristique est donc de ne pas essayer toutes les combinaisons possibles avant de trouver celle qui répond au problème, afin de trouver une solution approchée convenable (qui peut être exacte dans certains cas) dans un temps raisonnable.
C'est ainsi que les programmes de jeu d'échecs, de jeu de go (pour ne citer que ceux-là) font appel de manière très fréquente à des heuristiques qui modélisent l'expérience d'un joueur. Certains logiciels antivirus se basent également sur des heuristiques pour reconnaître des virus non répertoriés dans leur base, en s'appuyant sur des ressemblances avec des virus connus.
Applications
- Cryptologie et Compression de données
- Structure de données, Algorithmes de tri et Recherche dichotomique
- Allocation de mémoire et ramasse-miettes
- Informatique musicale
- Algorithme génétique en informatique décisionnelle
Voir aussi
- Al-Khuwarizmi
- Algorithme récursif
- Algorithme réparti
- Langage K
- Métaheuristique
- Structure de contrôle
Liens externes
- [http://www-ipst.u-strasbg.fr/pat/program/algo.htm Introduction à l'algorithmique, avec des exemples en langage C]
- [http://www.pise.info/algo/codage.htm Initiation à l'algorithmique]
- [http://www.myalgorithm.com Algorithmes de base dans plusieurs langages de programmation]
Complexité algorithmique ja:計算複雑性理論 th:ทฤษฎีความซับซ้อนในการคำนวณ
Catégorie:Algorithmique
La théorie de la complexité algorithmique s'intéresse à la bonne utilisation des algorithmes.
Elle s'attache à la question : entre différents algorithmes réalisant une même tâche, quel est le plus rapide et dans quelles conditions ?
Dans les années 1960 et au début des années 1970, alors qu'on en était à découvrir des algorithmes fondamentaux (quicksort, Boyer-Moore...), on ne mesurait pas leur efficacité. On se contentait de dire : « cet algorithme (de tri) se déroule en 6 secondes avec un tableau de 50 000 entiers choisis au hasard en entrée, sur un ordinateur IBM 360/91. Le langage de programmation PL/I a été utilisé avec les optimisations standard ». (cet exemple est imaginaire)
Une telle démarche rendait difficile la comparaison des algorithmes entre eux. La mesure publiée était dépendante du processeur utilisé, des temps d'accès à la mémoire vive et de masse, du langage de programmation/compilateur utilisé, etc.
Une approche indépendante des facteurs matériels était nécessaire pour évaluer l'efficacité des algorithmes. Donald Knuth fut un des premiers à l'appliquer systématiquement dès les premiers volumes de sa série The art of computer programming. Il complétait cette analyse de considérations propres à la théorie de l'information : celle-ci par exemple, combinée à la formule de Stirling, montre qu'il ne sera pas possible d'effectuer un tri général par comparaisons de N élements en un temps croissant moins rapidement avec N que N ln N sur une machine algorithmique (à la différence peut-être d'un ordinateur quantique).
Détails
Si l'on élimine de l'analyse de la complexité la question de la vitesse d'exécution de la machine et la qualité du code produit par le compilateur, il ne reste comme paramètre significatif que « la taille des données sur lesquelles il s'exécute ».
On exprime donc le temps d'exécution en nombre d'opérations élémentaires. Le temps d'exécution d'une opération élémentaire ne dépend pas de la taille de la donnée (par exemple, l'addition de deux entiers codés sur 32 bits prend un même temps, quels que soient les entiers considérés).
Exemples d'opérations élémentaires : accès à une cellule mémoire, comparaison de valeurs, opérations arithmétiques (sur valeurs à codage de taille fixe), opérations sur des pointeurs.
Pour la taille de la donnée, on se limite à un ou plusieurs entiers liés au nombre d'éléments de la donnée. Par exemple, le nombre d'éléments dans un algorithme de tri, dans un ensemble, le nombre de sommets et d'arcs dans un graphe orienté.
On évalue le nombre d'opérations élémentaires en fonction de la taille de la donnée : si 'n' est la taille, on calcule une fonction .
Les critères d'analyse : le nombre d'opérations élémentaires peut varier substantiellement pour deux données de même taille. On retiendra deux critères :
- analyse au sens du plus mauvais cas : est le temps d'exécution du plus mauvais cas et le maximum sur toutes les données de taille n. Par exemple, le tri par insertion simple avec des entiers présents en ordre décroissants.
- analyse au sens de la moyenne : tm(n) est l'espérance sur l'ensemble des temps d'exécution muni d'une distribution des probabilités des temps d'exécution. L'analyse mathématique de la complexité moyenne est souvent très délicate. De plus, la signification de la distribution des probabilité par rapport à l'exécution réelle (sur un problème réel) est à considérer.
On a donc introduit des notations asymptotiques ou notations de Landau.
- idée 1 : évaluer l'algorithme sur des données de grande taille. Par exemple, lorsque n est 'grand', + devient indiscernable de .
- idée 2 : on élimine les constantes multiplicatrices, car deux ordinateurs de puissances différentes diffèrent en temps d'exécution par une constante multiplicatrice. À partir de là, devient
L'algorithme est dit en .
L'idée de base est donc qu'un algorithme en est « meilleur » qu'un algorithme en si | | |
