| Property |
Value |
| dbo:abstract
|
- La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ». La complexité générique est une façon de mesurer la complexité d'un problème algorithmique en négligeant un petit ensemble d'entrées non représentatives et en considérant la complexité dans le pire des cas sur les entrées restantes. La concept de « petit ensemble » est définie en termes de densité asymptotique. L'efficacité apparente des algorithmes mesurée par leur complexité générique provient du fait que, pour une grande variété de problèmes informatiques concrets, les cas les plus difficiles semblent être rares, alors que les cas typiques sont, eux, relativement faciles. Cette approche de la complexité prend son origine dans la théorie combinatoire des groupes qui a une tradition dans l'étude de problèmes algorithmiques qui remonte au début du XXe siècle. La notion de complexité générique a été introduit en 2003 dans des articles de Kapovich, Miasnikov, Schupp et Shpilrain. Les auteurs montrent que, pour une large classe de groupes finiment engendrés, la complexité générique de quelques problèmes de décision classiques de la théorie combinatoire des groupes, à savoir le problème du mot, le (en), ou le problème d'appartenance, est en fait linéaire. Une introduction et un survol de la complexité générique sont donnés dans un texte de R. Gilman, A. G. Miasnikov, A. D. Myasnikov, et A. Ushakov. Les livres de Miasnikov, Shpilrain et Ushakov traitent principalement des résultats des auteurs relativement à la cryptographie. (fr)
- La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ». La complexité générique est une façon de mesurer la complexité d'un problème algorithmique en négligeant un petit ensemble d'entrées non représentatives et en considérant la complexité dans le pire des cas sur les entrées restantes. La concept de « petit ensemble » est définie en termes de densité asymptotique. L'efficacité apparente des algorithmes mesurée par leur complexité générique provient du fait que, pour une grande variété de problèmes informatiques concrets, les cas les plus difficiles semblent être rares, alors que les cas typiques sont, eux, relativement faciles. Cette approche de la complexité prend son origine dans la théorie combinatoire des groupes qui a une tradition dans l'étude de problèmes algorithmiques qui remonte au début du XXe siècle. La notion de complexité générique a été introduit en 2003 dans des articles de Kapovich, Miasnikov, Schupp et Shpilrain. Les auteurs montrent que, pour une large classe de groupes finiment engendrés, la complexité générique de quelques problèmes de décision classiques de la théorie combinatoire des groupes, à savoir le problème du mot, le (en), ou le problème d'appartenance, est en fait linéaire. Une introduction et un survol de la complexité générique sont donnés dans un texte de R. Gilman, A. G. Miasnikov, A. D. Myasnikov, et A. Ushakov. Les livres de Miasnikov, Shpilrain et Ushakov traitent principalement des résultats des auteurs relativement à la cryptographie. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 19503 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 2003 (xsd:integer)
- 2005 (xsd:integer)
- 2008 (xsd:integer)
- 2011 (xsd:integer)
- 2016 (xsd:integer)
- 2017 (xsd:integer)
|
| prop-fr:arxiv
|
- 1507.010880 (xsd:double)
- math/0203239 (fr)
- math/0206273 (fr)
|
| prop-fr:auteur
|
- Cyril Nicaud (fr)
- Frédérique Bassino (fr)
- Pascal Weil (fr)
- Cyril Nicaud (fr)
- Frédérique Bassino (fr)
- Pascal Weil (fr)
|
| prop-fr:auteurOuvrage
|
- Delaram Kahrobaei, Bren Cavallo et David Garber (fr)
- Delaram Kahrobaei, Bren Cavallo et David Garber (fr)
|
| prop-fr:collection
|
- Contemporary Mathematics (fr)
- Mathematical Surveys and Monographs (fr)
- Advanced Courses in Mathematics - CRM Barcelona (fr)
- Contemporary Mathematics (fr)
- Mathematical Surveys and Monographs (fr)
- Advanced Courses in Mathematics - CRM Barcelona (fr)
|
| prop-fr:doi
| |
| prop-fr:fr
|
- temps linéaire (fr)
- temps polynomial (fr)
- problème problème de la conjugaison dans un groupe (fr)
- échange de clés de Anshel-Anshel-Goldfeld (fr)
- énumération des cosets (fr)
- temps linéaire (fr)
- temps polynomial (fr)
- problème problème de la conjugaison dans un groupe (fr)
- échange de clés de Anshel-Anshel-Goldfeld (fr)
- énumération des cosets (fr)
|
| prop-fr:isbn
| |
| prop-fr:journal
|
- Computability (fr)
- Computability (fr)
|
| prop-fr:lang
| |
| prop-fr:lieu
|
- Bâle (fr)
- Providence, RI (fr)
- Bâle (fr)
- Providence, RI (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:mathReviews
|
- 2005 (xsd:integer)
- 2009 (xsd:integer)
|
| prop-fr:nom
|
- Kapovich (fr)
- Miasnikov (fr)
- Schupp (fr)
- Shpilrain (fr)
- Ushakov (fr)
- Kapovich (fr)
- Miasnikov (fr)
- Schupp (fr)
- Shpilrain (fr)
- Ushakov (fr)
|
| prop-fr:numéro
|
- 2 (xsd:integer)
- 4 (xsd:integer)
|
| prop-fr:numéroDansCollection
|
- 177 (xsd:integer)
- 677 (xsd:integer)
|
| prop-fr:pages
|
- 307 (xsd:integer)
- 343 (xsd:integer)
- 665 (xsd:integer)
|
| prop-fr:pagesTotales
|
- 229 (xsd:integer)
- xvi+183 (fr)
- xvi+385 (fr)
|
| prop-fr:passage
| |
| prop-fr:prénom
|
- Paul (fr)
- Vladimir (fr)
- Alexander (fr)
- Ilya (fr)
- Alexei (fr)
- Alexei G. (fr)
- Paul (fr)
- Vladimir (fr)
- Alexander (fr)
- Ilya (fr)
- Alexei (fr)
- Alexei G. (fr)
|
| prop-fr:présentationEnLigne
| |
| prop-fr:périodique
|
- Contemporary Mathematics (fr)
- J. Algebra (fr)
- Adv. Math (fr)
- Contemporary Mathematics (fr)
- J. Algebra (fr)
- Adv. Math (fr)
|
| prop-fr:sousTitre
|
- With an appendix by Natalia Mosina (fr)
- With an appendix by Natalia Mosina (fr)
|
| prop-fr:texte
|
- problème de conjugaison (fr)
- problème de conjugaison (fr)
|
| prop-fr:titre
|
- Computational complexity and the conjugacy problem (fr)
- Group-based Cryptography (fr)
- Generic-case complexity, decision problems in group theory, and random walks (fr)
- Generic properties of subgroups of free groups and finite presentations (fr)
- Non-commutative cryptography and complexity of group-theoretic problems (fr)
- Average-case complexity and decision problems in group theory (fr)
- Computational complexity and the conjugacy problem (fr)
- Group-based Cryptography (fr)
- Generic-case complexity, decision problems in group theory, and random walks (fr)
- Generic properties of subgroups of free groups and finite presentations (fr)
- Non-commutative cryptography and complexity of group-theoretic problems (fr)
- Average-case complexity and decision problems in group theory (fr)
|
| prop-fr:titreOuvrage
|
- Algebra and Computer Science (fr)
- Algebra and Computer Science (fr)
|
| prop-fr:trad
|
- Anshel–Anshel–Goldfeld key exchange (fr)
- Conjugacy problem (fr)
- Coset enumeration (fr)
- Linear time (fr)
- Polynomial time (fr)
- Anshel–Anshel–Goldfeld key exchange (fr)
- Conjugacy problem (fr)
- Coset enumeration (fr)
- Linear time (fr)
- Polynomial time (fr)
|
| prop-fr:volume
|
- 6 (xsd:integer)
- 190 (xsd:integer)
- 264 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:zbl
|
- 1248.940040 (xsd:double)
- 1248.940060 (xsd:double)
|
| prop-fr:éditeur
|
- American Mathematical Society (fr)
- Birkhäuser Verlag (fr)
- American Mathematical Society (fr)
- Birkhäuser Verlag (fr)
|
| dct:subject
| |
| rdfs:comment
|
- La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ». La complexité générique est une façon de mesurer la complexité d'un problème algorithmique en négligeant un petit ensemble d'entrées non représentatives et en considérant la complexité dans le pire des cas sur les entrées restantes. La concept de « petit ensemble » est définie en termes de densité asymptotique. L'efficacité apparente des algorithmes mesurée par leur complexité générique provient du fait que, pour une grande variété de problèmes informatiques concrets, les cas les plus difficiles semblent être rares, alors que les cas typiques sont, eux, relativement faciles. (fr)
- La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ». La complexité générique est une façon de mesurer la complexité d'un problème algorithmique en négligeant un petit ensemble d'entrées non représentatives et en considérant la complexité dans le pire des cas sur les entrées restantes. La concept de « petit ensemble » est définie en termes de densité asymptotique. L'efficacité apparente des algorithmes mesurée par leur complexité générique provient du fait que, pour une grande variété de problèmes informatiques concrets, les cas les plus difficiles semblent être rares, alors que les cas typiques sont, eux, relativement faciles. (fr)
|
| rdfs:label
|
- Complexité générique des algorithmes (fr)
- Generic-case complexity (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
