Discussion:Diviser pour régner (informatique)
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. 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.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| B | Moyenne |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) |
| Faible |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Importance de l'article[modifier le code]
Même si je pense qu'une importance moyenne convient, l'article pourrait peut-être être rétrogradé en pertinence faible.--Pethrus 20 novembre 2007 à 23:21 (CET)
Article FAUX ![modifier le code]
Cet article fait une confusion lamentable entre les familles d'algorithme "Diviser pour régner" et la récursivité. Le sujet de la récursivité n'a rien à voir avec cette famille d'algo. En effet la plupart des algorithmes e cette famille peuvent être réalisés sous forme itérative (et heureusement pour les performances). J'ai juste corrigé le premier paragraphe, mais il faudrait tout revoir. — Le message qui précède, non signé, a été déposé par un utilisateur sous l’IP 78.237.45.109 (discuter), le 18 mai 2014.
D'ailleurs[modifier le code]
L'idée n'est pas non plus nécessairement « d'abandonner » une branche du traitement, mais seulement de ramener le traitement d'un problème de taille donnée à un certain nombre de problèmes de plus petits ordres de grandeur (passer de n à n/k, k constant). La récursion est la manière « naturelle » d'écrire un algorithme de ce type, mais n'a effectivement pas spécialement de lien avec la manière de l'implémenter.
- Je n'irais pas jusqu'à dire "lamentable" mais effectivement c'est faux... Des idées de structure pour l'article ? —Shiningfm (discuter) 14 mai 2015 à 15:03 (CEST)
Algorithme récursif[modifier le code]
L'article contenait la phrase ː "Les algorithmes récursifs utilisent naturellement cette technique : ils s'appellent eux-mêmes une ou plusieurs fois sur une partition du problème initial et combinent les solutions pour retrouver une solution au problème initial."
C'est 'partiellement vrai' mais tiré par les cheveux. (prendre des exemples comme "chercher un élément x dans une liste L"). Bref ça n'apporte rien à la compréhension.
Ensuite, si on a conçu un algorithme "haut-niveau" comme "tri fusion" avec le paradigme diviser pour régner, on peut l'implémenter avec un algorithme récursif ou avec un algorithme itératif. C'est pourquoi j'opterai pour une section "Implémentation" où cela est discuté.
--Fschwarzentruber (discuter) 30 mars 2016 à 13:55 (CEST)
Deux stratégies... puis 1 2 3[modifier le code]
L'article est difficile à lire. Il y a écrit "Deux stratégies" puis ensuite il y a trois points. Je réécris.--Fschwarzentruber (discuter) 30 mars 2016 à 13:58 (CEST)
Liste de tâches[modifier le code]
- Parler de parallélisme
- Enrichir la liste des exemples
- Une motivation plus claire (pt parler de FFT et de ses applications en traitement du signal etc. dans l'introduction)
- Parler d'implémentation (récursif / itératif)
- Parler de programmation dynamique (peut-être supprimer le code Caml, non ?)
- Ajouter un historique (qui a utilisé le nom "diviser pour régner", etc.)
--Fschwarzentruber (discuter) 30 mars 2016 à 14:24 (CEST)
Complexité[modifier le code]
Je vais bientôt supprimer l'actuelle section "Complexité". Je vais faire une section "Intérêt" (de diviser pour régner) à la place. La raison essentielle est que l'article Master theorem me paraît très bien et subsume l'actuelle section "Complexité". Ensuite, la section ne cite aucune source et il vaut avoir un bon article sur "Master theorem". Bien sûr, wikipedia conserve trace des modifications et donc de l'ancienne section Complexité si jamais quelqu'un veut y revenir. --Fschwarzentruber (discuter) 31 mars 2016 à 20:29 (CEST)
Sous-problèmes redondants[modifier le code]
J'ai reformulé car ː
- j'ai trouvé confus qu'il y ait DEUX exemples en même temps. J'ai choisi l'exemple le plus simple des deux ː suite de Fibonacci
- qu'il y ait du code OCaml. Plutôt du pseudo-code, plus compréhensible, plus neutre
- J'ai essayé d'être plus précis.