Algorithmiquement

"algorithmiquement" dans l'encyclopédie

• COMPLEXITÉ, mathématique

  • Écrit par Jean-Paul DELAHAYE
  • 8 935 mots

  Ces preuves d'impossibilité sont importantes et une fine répartition entre ce qui est algorithmiquement faisable et ce qui ne l'est pas, est maintenant disponible. Les classes P et NP Ce domaine a ouvert la voie dans la décennie 1970 à une analyse d'un niveau plus fin, appelée théorie des classes de complexité, où l'on se pose des questions du type suivant : peut-on décomposer en facteurs premiers un nombre de n chiffres en utilisant un temps de calcul t majoré par un polynôme en n (on parle de temps polynomial) ? Les problèmes que l'on peut traiter en temps polynomial constituent la classe de complexité P.

• ALGORITHMIQUE

  • Écrit par Philippe COLLARD, Philippe FLAJOLET
  • 36 583 mots
  • 3 médias

  , sont algorithmiquement équivalents : on entend par là qu'ils sont inter-réductibles au moyen de réductions algorithmiquement « efficaces », c'est-à-dire calculables en temps polynomial. Malgré l'ampleur des recherches algorithmiques, aucun algorithme n'a été trouvé qui permette de résoudre l'un quelconque de ces problèmes en un temps polynomial en la taille des données d'entrées.

• CRYPTOLOGIE

  • Écrit par Jacques STERN
  • 31 728 mots
  • 3 médias

  Le problème de recouvrer p et q à partir de la seule connaissance de n est algorithmiquement très difficile : on est actuellement incapable de le résoudre dès que n dépasse 200 chiffres décimaux et ce « record » n'est atteint qu'au prix de l'utilisation de centaines de machines durant plusieurs mois. On recommande actuellement pour R.S.A. l'emploi de nombres allant de 300 à 600 chiffres.

• ONDELETTES

  • Écrit par Alexandre GROSSMANN, Bruno TORRESANI
  • 31 482 mots

  Les paquets d'ondelettes contiennent non seulement les ondelettes usuelles, mais aussi une multitude d'autres méthodes, toutes aussi efficaces algorithmiquement. Cela suggère de rechercher, pour un signal donné, laquelle de ces méthodes conduit à la représentation la plus efficace dans un sens donné. Ainsi, si l'application est la compression des signaux, on va rechercher la méthode qui fournit une compression optimale.