Introduction à la complexité

Complexité : mesure des ressources nécessaires en temps ou en mémoire d’un calcul.

Calcul du temps d’exécution :

- matériel utilisé et

- donnée traitée.

Trop concret et sans information abstraite sur le comportement.

Détermination de l’information pertinente par rapport à la taille de la donnée traitée.

3 cas d’analyse possible :

- complexité dans le meilleur des cas,

- complexité en moyenne,

- complexité dans le pire des cas.

Pour un algorithme donné et une représentation donnée, le temps sur les machines est identique à un facteur constant près.

Algorithme classique de recherche du

maximum dans une liste

Algorithme de recherche séquentiel du maximum dans une liste d’éléments tous distincts :

spécification MAX LISTE(E, DOMAINE(max)) étend LISTE RECURSIVE(E),

ORDRE(E, DOMAINE(max)) opérations max liste : Liste(E) → E préconditions {l : Liste(E)} pré max liste(l) : ¬vide ?(l) axiomes{l : Liste(E)}

lr_{1}(0) : max liste(l) = ; \begin{matrix}si vide ?(fin(l)) alors premier(l) \\ sinon max(premier(l), max liste(fin(l))) \end{matrix}

Le nombre de comparaisons entre éléments par rapport au nombre d’éléments dans la liste est déterminant pour la complexité.

Le nombre de comparaisons pour une liste de longueur n est exactement de n − 1.

Algorithme du Tournoi

Algorithme du tournoi : affrontement par paires de joueurs puis réalisation d’un tournoi avec les joueurs restants.

Recherche du maximum par l’algorithme du

tournoi

spécification TOURNOI LISTE_{0}(E, DOMAINE(max))

étend LISTE RECURSIVE(E), ORDRE(E, DOMAINE(max))

opérations vainqueur : Liste(E) → E tournoi : Liste(E) → Liste(E) élimination : Liste(E) → Liste(E)

L’opération élimination réalise un tour du tournoi.

suite de TOURNOI LISTE_{0}

préconditions {l : Liste(E)} pré élimination(l) : ¬vide ?(l)

axiomes {l : Liste(E)}

tl_{0}(0) : élimination(l) = ; \begin{matrix}si vide ?(fin(l)) alors premier(l) \\ sinon cons( \begin{matrix}max(premier(l), second(l)), \\ élimination(fin(fin(l)))) \end{matrix} \end{matrix}

L’opération tournoi enchaîne les tours d’élimination jusqu’à ce qu’il n’y ait plus qu’un seul joueur dans la liste ; l’opération vainqueur en extrait alors le vainqueur.

suite de TOURNOI LISTE_{0}

préconditions {l : Liste(E)}

\begin{matrix}pré tournoi(l) : ¬vide ?(l) \\ pré vainqueur(l) : ¬vide ?(l) \end{matrix}

axiomes {l : Liste(E)}

tl_{0}(1) : tournoi(l) =

\begin{matrix}si vide ?(fin(l)) alors premier(l) \\ sinon tournoi(élimination(l)) \end{matrix}

tl_{0}(2) : vainqueur(l) = premier(tournoi(l))

Un arbre de tournoi est un arbre binaire localement complet et le nombre de nœuds d’un arbre binaire localement complet ayant n feuilles est n − 1.

La complexité en nombre de comparaisons entre éléments de l’algorithme du tournoi pour la recherche du maximum dans une liste est exactement de n − 1.

Optimalité des deux algorithmes de recherche

Propriété : La complexité dans le pire des cas d’un algorithme de recherche du maximum dans une liste de longueur n est au mieux en n − 1.

Lemme : Soit un algorithme quelconque de recherche du plus grand élément dans une liste alors nécessairement tout élément autre que le maximum est comparé au moins une fois avec un élément qui lui est plus grand.

Les algorithmes classique et du tournoi sont optimaux pour la recherche du maximum dans une liste.

Le deuxième plus grand élément

Première approche : Chercher le deuxième plus grand élément d’une liste, c’est cherché le plus grand élément de la liste privée de son maximum.

Complexité dans le pire des cas en nombre de comparaisons de la première approche est exactement (n − 1) + ((n − 1) − 1).

Deuxième approche : Le deuxième meilleur joueur d’un tournoi, c’est un de ceux qui n’ont perdu que contre le vainqueur.

Si n est le nombre de joueurs alors le nombre des joueurs qui ont rencontré le vainqueur est ⌈log_{2} n⌉.

Complexité dans le pire des cas en nombre de comparaisons de la deuxième approche est exactement (n − 1) + (log_{2} n − 1).

Un peu de recul

Pour des données de grande taille les constantes sont négligeables. Une fonction de complexité g est en Θ(f), si il existe des constantes c, d, n_{0} et n_{1} telles que :

\begin{matrix}∀n > max(n_{0}, n_{1}), \\ d ∗ f(n) + n_{0} ≤ g(n) ≤ c ∗ f(n) + n_{1} \end{matrix}

Comparaison de quelques complexités :

Θ(log_{2} n) < Θ(n) < Θ(n log_{2} n) < Θ(n^{2}) < Θ(2^{n})

\begin{aligned}n & log_{2} n & n & n log_{2} n & n^{2} & 2^{n} \\ 10 & ≈ 3.3 & 10 & ≈ 33 & 10^{2} & 1024 \\ 10^{2} & ≈ 6.6 & 10^{2} & ≈ 6.6 ∗ 10^{2} & 10^{4} & ≈ 10^{30} \\ 10^{3} & ≈ 10 & 10^{3} & ≈ 10^{4} & 10^{6} & ≈ 10^{301} \\ 10^{6} & ≈ 20 & 10^{6} & ≈ 2 ∗ 10^{7} & 10^{12} & ∞ \end{aligned}

Influence du codage sur la complexité

Un codage est raisonnable si il n’affecte la taille des données que de façon polynômiale.

Règles à respecter :

- pas de bourrage du codage,

- décodage polynômial,

- représentation des chiffres autre qu’unaire.

En pratique : tous les codages “naturels” d’un même langage (instances d’un problème) sont raisonnables.

Exemple : Représentation d’un graphe (V, E) (|V |= n, |E|= m et codage binaire des sommets sur log_{2}(|V |) bits) par :

- Liste des sommets et liste des arcs : O((n+m)log_{2}(n)) ;

- Matrice d’incidence : O(n^{2}).

Complexité et machines de Turing

déterministes

Soit M une machine de Turing déterministe (sur un alphabet Σ) qui s’arrête toujours. La complexité en temps de M est la fonction : T_{M}(n) = max{m/∃x ∈ Σ^{∗}, |x|= n et l’exécution de M sur x comporte m étapes}.

Une machine de Turing déterministe M est polynômiale si il existe un polynôme p(n) tel que la fonction de complexité de T_{M} soit en O(p(n)).

Lemme : Si il existe un algorithme polynômial pour résoudre un problème alors il existe une machine de Turing déterministe polynômiale qui décide le langage des instances positives du problème.

La classe P

La classe P ( Polynomial ) est la classe des langages décidés par une machine de Turing déterministe polynômiale.

classe P ≅ algorithmes efficaces (insensible au choix de la machine et d’un codage raisonnable).

La classe P est close par composition.

Comment établir une hiérarchie de complexité des problèmes?

Un outil : la réduction (ou transformation ) polynômiale.

La réduction polynômiale

Soient L_{1} et L_{2} deux langages respectivement sur Σ_{1} et Σ_{2}. Une réduction polynômiale de L_{1} vers L_{2} (notée L_{1} ≤_{P} L_{2}) est une fonction f : Σ_{1}^{∗} → Σ_{2}^{∗} telle que - elle est calculable en temps polynômial,

- f(x) ∈ L_{2} si et seulement si x ∈ L_{1}.

L_{1} se réduit polynômialement à L_{2} signifie que L_{1} n’est pas plus difficile, à un facteur polynômial près, que L_{2}.

Exemple : Soient L_{1} = {x/ax + b = 0} et L_{2} = {x/ax^{2} + bx + c = 0}.

L_{1} ≤_{P}^{?} L_{2}.

Soit f : ax + b = 0 → 0x^{2} + ax + b = 0,

- f est calculable en temps polynômial,

- f(x) ∈ L_{2} si et seulement si x ∈ L_{1}.

La réduction polynômiale (suite)

Lemme : Si L_{1} ≤_{P} L_{2} alors

- si L_{2} ∈ P alors L_{1} ∈ P,

- si L_{1} ∉ P alors L_{2} ∉ P.

Lemme : Si L_{1} ≤_{P} L_{2} et L_{2} ≤_{P} L_{3} alors L_{1} ≤_{P} L_{3}.

Deux langages L_{1} et L_{2} sont polynômialement équivalents (noté L_{1} ≡_{P} L_{2}) si L_{1} ≤_{P} L_{2} et L_{2} ≤_{P} L_{1}.

La classe P est une classe d’équivalence pour ≡_{P}.

Une classe d’équivalence polynômiale C_{1} est inférieure à une classe d’équivalence polynômiale C_{2} (noté C_{1}[≤_{P}]C_{2}) si

∀L_{1} ∈ C_{1}, ∀L_{2} ∈ C_{2}, L_{1} ≤_{P} L_{2}.

Voyageur de commerce et

circuit hamiltonien

Problème du voyageur de commerce (T S) : Soit un ensemble de ville V et pour chaque paire de villes, une distance. Soit une distance m. Existe-t-il un parcours fermé passant par toutes les villes et qui revient à son point de départ?

Problème du circuit hamiltonien (HC) : Pour un graphe donné, existe-t-il un parcours fermé du graphe contenant chaque sommet une et une seule fois?

Lemme : HC ≡_{P} T S.

Algorithme de résolution : génération d’une permutation puis vérification.

Problème : exploration de l’espace des permutations.

Machines de Turing non-déterministes

Soit M = (Q, Γ, Σ, δ, s, #, F)

- Q est un ensemble fini d’états,

- Γ est un alphabet de ruban,

- Σ est un alphabet d’entrée,

- Δ ⊂ ((Q × Γ) × (Q × Γ × {g, d})) la relation de transition,

- s ∈ Q l’état initial,

- # ∈ Γ − Σ le caractère “blanc”,

- F ⊆ Q l’ensemble des états accepteurs.

M est une machine de Turing non-déterministe .

Un mot est accepté par une machine de Turing nondéterministe si il existe une exécution qui contienne une configuration dont l’état est accepteur.

Machines de Turing non-déterministes et

complexité

Le temps de calcul d’une machine de Turing sur un mot est donné par

- la longueur de la plus petite exécution en nombre d’étapes acceptant le mot,

- 1 si le mot n’est pas accepté.

Soit M une machine de Turing (sur un alphabet Σ). La complexité en temps de M est la fonction :

T_{M}(n) = max{m/∃x ∈ Σ^{∗}, |x|= n et le temps de calcul de M sur x est m}.

Une machine de Turing non-déterministe M est polynômiale si il existe un polynôme p(n) tel que la fonction de complexité de T_{M} soit en O(p(n)).

La classe N P

1^{ère} caractérisation : La classe N P ( N on déterministe Polynômial ) est la classe des langages acceptés par une machine de Turing non-déterministe polynômiale.

2^{ème} caractérisation : La classe N P est la classe des langages telle que la vérification soit décidable par une machine de Turing polynômiale.

Th.: Soit L ∈ N P, alors il existe une machine de Turing déterministe M et un polynôme p(n) tel que M décide L en O(2^{p(n)}).

Lemme : P ⊆ N P

Lemme : ∀L_{1} ∈ P, ∀L_{2} ∈ N P, L_{1} ≤_{P} L_{2}

Question ouverte : P =^{?} N P

La classe N P −complet

La classe des problèmes N P −complet est la classe des problèmes les plus durs de N P.

Un langage L est N P −complet si

- L ∈ N P et

- ∀L′ ∈ N P, L′ ≤_{P} L.

Un langage L est N P −dur si

- L ∉ N P et

- ∀L′ ∈ N P, L′ ≤_{P} L.

Lemme : N P −complet est une classe d’équivalence pour ≡_{P} et P ≤_{P} N P −complet.

cor.: si il existe un langage L ∈ N P −complet décidé par une machine de Turing déterministe polynômiale alors P = N P.

cor.: Pour démontrer qu’un langage L est N P −complet, il suffit de montrer que

- L ∈ N P et

- ∃L′ ∈ N P −complet, L′ ≤_{P} L.

Un problème N P −complet: SAT

Le problème SAT : Existe-t-il une interprétation qui satisfasse une formule propositionnelle en forme normale conjonctive?

Exemple : La formule (p ∨ ¬q) ∧ r ∧ (s ∨ ¬p) est en forme normale conjonctive.

Th. de Cook : Le problème SAT est N P −complet.

Idée Démo : - Montrer que SAT ∈ N P.

- Construire une fonction f de l’ensemble des couples (Machine de Turing polynômiale, mot) vers l’ensemble des formules propositionnelles sous forme normale conjonctive telle pour toute machine de Turing polynômiale M et tout mot w, M accepte w si et seulement si f(< M, w >) est satisfaisable.

D’autres problèmes N P −complet

Lemme : Le problème 3−SAT est N P −complet. Lemme : Pour tout k ≤ 3, k−SAT est N P −complet. Lemme : Le problème de couverture de sommets dans un graphe est N P −complet. Lemme : HC est N P −complet. Lemme : T S est N P −complet. Lemme : Le problème du nombre chromatique d’un graphe est N P −complet. Lemme : Le problème de la programmation entière est N P −complet.

Au delà de N P

La classe co − N P est la classe des langages dont le complément est dans N P.

La classe EXP T IME est la classe des langages décidés par une machine déterministe dont la complexité est en O(2^{p(n)}), p(n) un polynôme.

La classe P SP ACE est la classe des langages décidés par une machine de Turing déterministe dont la complexité en espace est polynômiale.

La classe NP SP ACE est la classe des langages décidés par une machine de Turing non-déterministe dont la complexité en espace est polynômiale.

Lemme : P ⊆ \begin{matrix}N P \\ co−N P \end{matrix} ⊆ P SP ACE ⊆ EXP T IME.

Lemme : P SP ACE = NP SP ACE.

Lemme : P ⊂ EXP T IME.