Discussion:Algorithmique

Autres discussions [liste]

• Suppression -
• Neutralité -
• Droit d'auteur -
• Article de qualité -
• Bon article -
• Lumière sur -
• À faire -
• Archives -
• Traduction

informations sur cette boîte Cet article est indexé par les projets Mathématiques, Sélection transversale, informatique. Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs, dans le cadre du projet 1.0. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs. Évaluation de l’article « Algorithmique » Avancement Importance pour le projet : Bon début Élevée Mathématiques (discussion • critères • liste • stats • hist. • comité) Sélection transversale (discussion • critères • liste • stats • hist. • comité) Maximum informatique (discussion • critères • liste • stats • hist. • comité) Cet article comporte une liste de tâches suggérées : modifier • suivre • rafraîchir • aide Wikifier un peu plus Ajouter quelques exemples Ajouter quelques schémas/illustrations (voir peut-être la version anglaise (Bon article) pour compléter certains points)

Implémentation

Le Grand dictionnaire terminologique de l'Office québécois de la langue française semble indiquer, à ma grande surprise, que le mot « implémentation » soit un synonyme correcte de « mise en œuvre ». Est-ce un anglicisme ou un terme accepté en France ?

-- Mathieugp 21 jun 2005 à 16:45 (CEST)

Il y a d'horribles confusions entre "emprunt" d'un mot complet à la langue anglaise et "anglicisme" qui est un mot employé dans la signification anglaise. Par exemple, "contrôler" signifie "surveiller" en français (contrôleur de la SNCF) et "commander" en anglais ("radio control": radiocommande).

Emprunt: "rodingote" est une francisation de l'emprunt "riding coat".

gallicisme: en anglo-américain le mot "rendez vous" employé dans la signification française de rencontre galante serait un gallicisme. Chez le dentiste, ce serait "appointment". "meeting" est utilisé pour une rencontre à plus de deux.

"implementation" correspond à "implantation" avec le suffixe "ation" qui indique "l'acte de..." et le résultat de cet acte, comme dans "organisation" et "complémentation" qui indique l'acte de "complémenter" et son résultat qui est différent de celui de "compléter" CQFD

Une langue qui n'évolue pas au besoin devient une langue morte et la francophonie n'est pas seulement le franco-française hexagonale. Logiquememt et linguistiquement, les "septante, "octante" et "nonante" franco-suisses et franco-belges (ne pas confondre le .belgicain", de même formation que "Afrique e Africain") sont plus exacts, sinon, on dirait deux-vingt-dix, au lieu de cinquante. CQFD.

Takima 24 février 2006 à 14:23 (CET)

Exemple d'algorithme

Je pense que l'exemple d'algorithme des bonbons, que je poste ici en copie, n'illustre pas vraiment ce qu'est un algorithme en informatique, dans le sens où il ne résout pas de problème, mais donne simplement une suite d'instructions à réaliser

Exemple d'algorithme

1. entrer dans le magasin
2. prendre 150g de bonbons
3. passer en caisse
4. compter ses sous
5. s'il reste plus de 1/2 € alors retourner au point 2
6. sortir du magasin

Je propose de le remplacer par un lien sur la page d'un fameux problème d'informatique, du genre les tours de Hanoï.

--Kingmike 27 juillet 2005 à 10:48 (CEST)

Origine du terme algorithme

Je propose de remplacer :

Son nom est d'ailleurs à l'origine du mot algorithme créé par lady Ada Lovelace,

par :

Son nom est d'ailleurs à l'origine du mot algorithme car un de ses ouvrages avait été traduit en latin sous le nom Algoritmi par Ada Lovelace

Je vous laisse faire si ok. BMR 7 septembre 2005 à 08:51:05 (CEST)

Algorithmique vs algorithmie

Je sais que cela a déjà été discuté, mais je pense qu'il serait bon de faire (au moins une fois) mention du mot algorithmie. En effet, bien que ce mot ne soit pas dans le dictionnaire de l'Académie française, il est suffisamment utilisé par la société informatique pour être présent dans cet article (la preuve est que le site developpez.com qui est référencé dans cet article utilise algorithmie aussi bien que algorithmique). Si personne ne me répond, j'ajouterais algorithmie dans l'introduction par quelque chose du genre On nomme algorithmique ou algorithmie la science des .... Si quelqu'un a un lien vers une discussion WP sur la politique à tenir vis-à-vis des mots qui ne sont pas dans le dictionnaire, je suis preneur. A.K. 23 mai 2006 à 16:46 (CEST)

Donald Knuth

Donald Knuth ayant joué un rôle fondamental dans le développement de l'algorithmique mathématique, une section de cet article devrait lui être consacrée.

Liens externes

• Donald E. Knuth, Professor Emeritus of The Art of Computer Programming at Stanford University

Effectivement je pense que ce cher Knuth merite quelque chose dans cet article. Un lien interne, c'est sûr, une référence dans l'historique aussi, du genre : 'Donald E. Knuth est l'une des personnes qui a fait le plus avancer l'algorithmie durant ces dernières années...' . Une section, ca fait beaucoup je pense surtout qu'il y a déjà une bonne page sur lui (un peu courte certes). A.K. 30 mai 2006 à 12:15 (CEST)

Complexité algorithmique

Je trouve que cette section pourrait introduire la différence entre évaluation dans le pire cas et évaluation en moyenne. De plus, je trouve que la même section règle un peu rapidement et à sens unique le problème que les algorithmiciens appellent presser la constante (squeezing the constant) et qui est important pratiquement. Si dans un algorithme, la constante est 1 000 000, un algorithme logarithmique l'emporte. De plus, les derniers gains d'une implantation se font dans les optimisations de moyen et bas niveau comme l'explique Jon Bentley dans son très beau livre Writing efficient programs (Prentice Hall, Englewood Cliffs, 1982). Pierre de Lyon 25 juillet 2006 à 15:33 (CEST)

Ou classer "Algorithmique" dans la Liste des disciplines scientifiques ?

Dans logique mathématique ? mathématiques ? informatique ? ou a part...?--Josce 27 septembre 2006 à 18:12 (CEST)

Il me semble qu'en 2006, on doit la classer dans l'informatique. Pierre de Lyon 28 septembre 2006 à 09:54 (CEST)

Personnellement, je laisserais l'algorithmique dans la mathématique car l'informatique n'est pas la seule cliente de ses outils. Lacrymocéphale 1 septembre 2008 à 20:01 (CEST)

Les débuts de l'algorithmique

Il me semble qu'il manque une partie sur les débuts de l'algorithmique, notamment avec :

• Les travaux de Turing et de Church, qui permirent la définition rigoureuse de la notion d'algorithme
• La thèse de Church
• Les travaux de Gödel
• Le 10ème problème de Hilbert (important car il a été posé par Hilbert sans vraiment connaître ce qu'était précisément un algorithme).

Tout cela existe sur les pages de ces sujets. Mais perso je ne classerai pas cela (classiquement) dans l'algo. On pourrait faire un renvoi. Outs 15 juillet 2007 à 13:02 (CEST)

Proposition de sélection de cet article pour Portail:Informatique

Cet article est proposé pour faire partie de la sélection Wikipédia:Sélection/Informatique. Cette page permet d'afficher aléatoirement un article parmis la sélection sur Portail:Informatique. Les articles sélectionnés représentent la vitrine du projet.

Vous êtes invités à vous exprimer sur la page suivante : Wikipédia:Sélection/Informatique/Algorithmique. Toutes les remarques d'amélioration sont les bienvenues, mais notez que puisque c'est un vote interne au projet, seuls les votes des participants déjà inscrits sur le projet informatique seront pris en compte. --T (d) 11 décembre 2007 à 13:26 (CET)

Objects trouvés

---

Le terme algorithmie n'est pas correct. J'ai apporté quelques modifications concernant les heuristiques. Il faut noter que certains problèmes ne seront jamais résolus, quand bien même nous aurions toute la puissance de calcul possible. De même, une heuristique fournit généralement une solution approchée. Enfin, il peut exister plusieurs solutions exactes différentes. Bien à vous, --bd 213.103.47.200 25 oct 2004 à 09:58 (CEST)

---

J ai un probleme de fond avec néologisme, en quoi algorithmique est un néologisme, parce qu'il n est pas dans le dictionnaire ? N'est-ce pas des plus courant pour des termes scientifiques ?

Dtcube

---

Je pense que le "n'est pas dans le dictionnaire" est là pour souligner le fait que c'est un mot récent, et donc un néologisme. Mais je suis pour enlever cette détermination relative au présent (comme je l'ai dis déjà en d'autres endroits). Tout d'abord parce que, effectivement, ce mot est très utilisé dans les professions informatiques et que, s'il n'est pas encore dans quelques dictionnaires, il ne tardera plus à y être, et ensuite car cette justification ne me plait pas.

Je propose à la place "l'Algorithmique est un mot apparu en même temps que l'émergence des sciences de l'informatique" (si cela est bien vrai et que ce mot ne se trouve effectivement pas avant dans la littérature, à vérifier, je n'ai pas le dico sur moi).

Mokona

---

Je pense que la personne qui a écris l'intro de Algorithmique voulais juste donner des détails sur l'origine du mot (ce qui est louable). Mais c'est vrai qu'en première ligne ca fait un peu bizarre. Pourquoi pas déplacer la remarque plus bas ?
Je suis d'accord avec Mokona a propos des notions temporelles qui sont a eviter dans Wikipedia.

Aoineko

---

Ca me plait mieux mais c'est à verifier... Algorithme trouve tout de meme son origine dans le nom de Abu Ja'far Mohammed ibn Musa al-Khwarizmi (genre 750-850 ap jc) auteur de ce que l'on considère comme l un des premiers traités sur le calcul algebrique. On peut également mentionner le célèbre algorithme d'Euclide qui pour le coup remonte à avant jc.
Certes, algorithmique est un peu different, mais bon

Dtcube

---

Puisque c'est moi qui ai écrit cette définition, il me faut donner mon avis. Ok pour changer la définition (prenons celle de Mokona) et supprimer l'emploi du terme "néologisme", voire déplacer ma remarque. Mais j'aimerai que soit conservée l'explication de l'origine du nom, à savoir l'adjectif relatif à "algorithme". Et ajouter celle de "algorithme" si Dtcube peut/veut vérifier.

J'insiste sur la distinction du nom commmun "algorithme" (d'origine ancienne, grecque ou arabe vraisemblablement) et du nom nouveau "algorithmique", forgé récemment pour désigner la science des algorithmes. C'est ce que j'ai voulu dire.

Valéry Beaud

---

Depuis quand Descartes est l'auteur de l'Esprit des Lois ??? Aurélien

Depuis qu'on mes les nouveaux messages en haut des pages de discussion ;-) (Normalement, c'est en bas. Sans rancune !) FvdP (disc.) 10 jun 2004 à 18:09 (CEST)

Je sais, mais c'est une provocation. Maintenant que le point est corigé, ça peut aller en bas :) Aurélien

---

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. Ce n'est pas plutôt une définition des algorithmes "diviser pour régner" ? --Turb 17 jul 2004 à 16:06 (CEST)

---

Une procédure désigne une méthode d’organisation, la stratégie d'une modification qui passe par les étapes d'un processus. Elle introduit donc ce terme de processus. Ne serait-il pas sage de garder la page procédure plutôt que de faire une redirection. Procédure peut s'appliquer à d'autres choses qu'à une procédure algorithmique. Le manuel d'utilisation de la machine à laver nous donne la procédure à suivre pour ressortir le linge propre ? --LR 13 mai 2005 à 09:51 (CEST)

---

Je trouve la première illustration peu convaincante, et fausse: "L'ampoule fonctionne-t'elle? --> Oui -> Changer l'ampoule" ... Elle n'illustre pas ce qu'est un algorithme, et d'ailleurs c'est une adaptation de l'illustration de l'article en anglais flowchart.

Complexité factorielle

Est-ce que cette terminologie est classique? Puisque $O(n!)$ est égale à $O(n^n)$, ne devrait-on pas plutôt citer cette complexité quoique je ne sache pas lui donner de nom? --Pierre de Lyon (d) 12 décembre 2009 à 18:22 (CET)

Je n'ai jamais rencontré de truc en $O(n!)$ ou $O(n^n)$. Il faudrait que je réfléchisse où on peut trouver ça, j'imagine un truc de chemins dans $K_n$ et regarder la littérature. (:Julien:) ✒ 14 décembre 2009 à 19:44 (CET)

Le Problème du voyageur de commerce a une solution optimale calculable en $O(n!)$ (voir l'Algorithme de Little) Spikyvins (d) 5 février 2012 à 12:50 (CET)

Algorithms + Data Structures = Programs

Il manque une description succincte des structures de données et structures de contrôle. Dans une version précédente http://fr.wikipedia.org/w/index.php?title=Algorithmique&oldid=47655328 j'avais mis :

Les concepts en œuvre en algorithmique sont en petit nombre, ils appartiennent à deux classes :

• les structures de contrôle
  • séquences
  • conditionnelles
  • boucles
• les structures de données
  • constantes
  • variables
  • tableaux
  • structures récursives (listes, arbres, graphes)

avec quelques renvois à d'autres sections de wikipédia pour une définition complète. Cet ajout a été supprimé avec une explication courte "pas convaincu par ce parag "concept", c'est plus lié à la prog qu'à l'algo.".

L'équation "Algorithms + Data Structures = Programs" vient de

author = {Wirth, Niklaus},
title = {Algorithms + Data Structures = Programs},
year = {1978},
isbn = {0130224189},
publisher = {Prentice Hall PTR},
address = {Upper Saddle River, NJ, USA},

une autre équation intéressante pour légitimer mon ajout est :

• Kowalski, Robert (1979). "Algorithm=Logic+Control". Communications of the ACM 22 (7): 424–436. doi:10.1145/359131.359136. ISSN 0001-0782.

Ces deux citations, d'auteurs de références, montrent que l'algorithmique est liée à la notion de programme, de structures de données et de structures de contrôle, et que l'on ne peut définir algorithmique sans en faire mention.

Plus généralement, en regardant l'historique de cet article, j'observe qu'il est difficile d'apporter des contributions pour cet article, une modification sur 3 est un retour en arrière ! Au vu de l'article, c'est étonnant, car il est loin d'être idéal. Outre l'ajout que je souhaite voir :

• il manque un paragraphe ou une section sur la récursivité,
• il manque une description sur les différents types d'algorithmes (glouton, diviser-et-régner, brut-force, combinatoire, aléatoire, ...),
• il manque une section sur les problèmes classiques de l'algorithmique (complétude, correction, terminaison, complexité, ...)
• la section "exemple" demande à être complétée et illustrée (sont-ce les algorithmes qui sont décrits ou les problèmes, ou ni l'un ni l'autre ?) en particulier, quelques exemples paradigmiques pourraient être développés à travers plusieurs algorithmes éventuellement (échange, tri, ...)
• l'aspect 'complexité' est sur-développé (une seule section ou sous-section doit suffire)
• ...

L'article anglais est bien meilleur, sans être excellent non plus.

J'aimerais donc que l'on éclaire ma lanterne, dans quelle optique est écrit cet article "Algorithmique", en tant qu'informaticien, je ne m'y retrouve pas, la quotation Avancement : "B" me semble usurpée, mais je suis d'accord sur l'importance "Maximum" de cet article pour la communauté informatique. Comment améliorer cet article sans être "défait".

Par ailleurs, "Algorithmique" nécéssite facilement un livre (ou plus), -mais le cours sur wikiuniversité est en panne !- je comprendrais que l'on veuille se limiter à une ou deux pages (mais alors il faut savoir ce que l'on veut y mettre) — Le message qui précède, non signé, a été déposé par Bdenis (d).

Plutôt d'accord avec toutes ces remarques. En ce qui concerne le "revert" sur les concepts, je le comprends, car il présentait les choses de manière absolue : les concepts de l'algorithmique c'est ça, alors qu'il existe des approches algorithmiques comme le LISP sans véritable structure de contrôle, et sans séparation entre structure de donnée et de contrôle. Il aurait mieux valu dire : selon l'approche de N. Wirth, correspondant aux langages les plus répandus (Pascal, C, etc..) les bases de l'algorithmique sont.. Cordialement --Jean-Christophe BENOIST (d) 28 décembre 2009 à 11:22 (CET)

proposition de changement dans le plan de l'article

Est-ce que l'on pourrait un peu restructurer (et développer) l'article de la manière suivante :

1. Définition (repris)
2. Historique (repris)
   1. Antiquité (repris)
   2. Étude systématique (repris)
3. Vocabulaire (à voir)
4. Exemples d’algorithmes (repris, à développer)
5. Approche pratique (à écrire) : description des stratégies courantes (glouton, diviser-et-régner, brut-force, combinatoire, aléatoire, ...) ajout peut-être de la section "heuristique"
6. Etude formelle (à écrire)
   1. Structures algorithmiques classiques (à écrire, ou a reprendre de la page discusssion) : structures de données, structures de contrôle, récursivité
   2. Complétude, correction, terminaison (à écrire)
   3. Complexité (repris, déplacé)
      1. Quelques indications sur l’efficacité des algorithmes (repris, déplacé, revoir le titre (?))
      2. Les heuristiques (repris, à déplacer vers approche pratique(?))

--Bdenis (d) 11 janvier 2010 à 11:32 (CET)

Je trouve cette proposition pas mal. Je mettrais l'"Etude formelle" avant "Approche pratique" (les fondements avant l'application), et "Exemples d'algorithmes" après "Approche pratique" (même logique), mais c'est une question de goût. Cordialement Jean-Christophe BENOIST (d) 11 janvier 2010 à 12:27 (CET)

Restructuration des exemples

La partie "Exemples d’algorithmes et d'applications" est peu homogène, pas très structurée, etc ...

Que pensez-vous de :

Titre : Exemples d’algorithmes, de problèmes, d'applications ou domaines d'application

Il existe un certain nombre 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 (voir aussi liste des algorithmes) :

• Algorithmes ou problèmes classiques (du plus simple ou plus complexe)
  • échange, ou comment échanger les valeurs de deux variables : problème classique illustrant la notion de variable informatique (voir aussi Structure de données)
  • Algorithmes de recherche, ou comment retrouver une information dans un ensemble structuré ou non (par exemple Recherche dichotomique)
  • algorithme de tri, ou comment trier un ensemble de nombres le plus rapidement possible ou en utilisant le moins de ressources possible
  • Problème du voyageur de commerce, Problème du sac à dos et autres algorithmes ou approximations de solutions pour les problèmes combinatoires difficiles (dit NP-complets)
• Algorithmes ou problèmes illustrant la programmation récursive (voir aussi algorithme récursif)
  • tours de Hanoï
  • huit dames, placer huit dames sur un échiquier sans qu’elles puissent se prendre entre elles
  • Suite de Conway
  • algorithme de dessins récursifs pour le Tapis_de_Sierpiński_(programme_informatique), la Courbe du dragon, le flocon, ...
• Algorithmes dans le domaine des mathématiques
  • calcul de la Factorielle d'un nombre, de la Fonction d'Ackermann ou de la suite de Fibonnacci
  • algorithme du simplexe, qui minimise une fonction linéaire de variables réelles soumises à des contraintes linéaires
  • Fraction continue d'un nombre quadratique, permettant d'extraire une racine carrée
• Algorithmes pour et dans le domaine de l'informatique
  • Cryptologie et compression de données
  • Informatique musicale
  • Algorithme génétique en informatique décisionnelle
  • Analyse et compilation des langages formels (voir Compilateur et Interprète (informatique))
  • Allocation de mémoire (ramasse-miettes)

BDenis.--90.27.16.32 (d) 27 mai 2010 à 10:22 (CEST)