Typologie des problèmes

1. Contexte

L’émergence d’une nouvelle discipline comme l’informatique quantique pose la question des problèmes qu’elle peut aider à résoudre. Comme évoqué précédemment, on qualifie un algorithme de résolution avec sa complexité. Cette notion nous permet donc de catégoriser les problèmes que les algorithmes considérés participent à résoudre.

Commençons par détailler cette notion de complexité des algorithmes.

2. La complexité Complexité

En informatique classique, il a fallu à un moment donné quantifier la performance d’un algorithme en fonction des données en entrée du problème à résoudre. Il en va de même en informatique quantique. Cette quantification se nomme complexité.

a. Première approche

Il s’agit donc de caractériser cette complexité en fonction de la nature des entrées de l’algorithme selon le problème à résoudre. En effet, plus les données en entrée correspondent à des grandeurs conséquentes, plus l’algorithme mettra a priori du temps pour atteindre la solution.

Prenons par exemple l’algorithme qui consiste à parcourir un tableau d’une seule dimension. Il s’agit pour l’algorithme de parcourir tout le tableau en lisant chaque valeur dans chaque case...

Pour consulter la suite, découvrez le livre suivant :
couv_DPQINF.png
60-signet.svg
En version papier
20-ecran_lettre.svg
En version numérique
41-logo_abonnement.svg
En illimité avec l'abonnement ENI
130-boutique.svg
Sur la boutique officielle ENI
Précédent
Classification des problèmes à résoudre et complexité
Suivant
Vers la suprématie quantique ?