Discussion:Algorithme de Coppersmith-Winograd
Autres discussions [liste]
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Informatique théorique 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 | |
|---|---|---|---|
| Ébauche | À évaluer |  | Informatique théorique (discussion • critères • liste • stats • hist. • comité • stats vues) |
 | 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.
L'article n'est pas clair: Que déduire de "le plus efficace en théorie." et "Rien n'indique que la complexité est optimale" ? Est-il mathématiquement prouvé qu'on ne peut trouver une complexité plus faible ?
- Le plus efficace en théorie signifie l'algo de C-W est celui de plus faible complexité. Mais cette efficacité n'est atteinte que pour des très très grosses matrices (d'où l'insistance sur "en théorie"). La seule chose que l'on sache dire sur une borne inf de la complexité du produit matriciel (non trivial bien sûr) c'est que c'est en n². C'est peut-être la meilleure borne, ou pas. C'est vrai que l'article est un peu écrit pour des gens qui connaissent le calcul formel. (:Julien:) ✒ 24 novembre 2009 à 22:15 (CET)