Théorie de la complexité
========================
1. identifier des problèmes difficiles (exponentiel et avec aucune solution polynomiale)
la complexité du problème est celle de la meilleur solution possible
(on ne peut pas le résoudre autrement)
dire qu'un problème est O(f(n)) => pas d'algo < O(f(n))
2. réduction de problèmes
Soit un problème X difficile (on le suppose du moins).
Le problème Y est aussi difficile que X si on peut efficacement réduire X à Y.
Exemple: pour résoudre un problème X, on peut répéter n fois le problème Y.
Alors Y est aussi difficile que X et non pas le contraire.
Exemple: la coloration de graphe est un problème difficile (supposition).
On peut résoudre la coloration de graphe à dire:
- est-ce qu'on peut colorier le graphe avec N couleurs? (vrai/faux)
- est-ce qu'on peut colorier le graphe avec N-1 couleurs? (vrai/faux)
- est-ce qu'on peut colorier le graphe avec N-2 couleurs? (vrai/faux)
- est-ce qu'on peut colorier le graphe avec ... couleurs? (vrai/faux)
Cette question est un problème SAT, poser plusieurs fois.
Alors, le problème SAT est aussi difficile que la coloration de graphe.
Exemple 2: Le PVC cherche un tour optimal.
Le PVC est supposément difficile.
Le PVC peut-être réduit à poser la question:
- est-ce qu'il y a un tour < N (nombre entier) en diminuant le nombre N plusieurs fois.
Le problème posé par la deuxième question est alors aussi difficile que le PVC.
SAT (problème de décision)
===
Soit une expression booléenne (proposition: vraie ou fausse, oui ou non)
Question: Peut-on la satisfaire (peut-elle être vrai).
Il s'agit d'un problème de 2^n selon Cooke (1971) où n est le nombre d'éléments/variables dans l'expression.
Tout problème de décision est un problème de satisfaction.
Mais certains sont aussi difficiles que SAT.
Prouver NP_Complet.
Classes NP et P
P: Ensembles des problèmes de décisions "résolus" polynomialement (solution exacte)
NP: Ensembles des problèmes de décisions "vérifiables" polynomialement (recherche la validité et non pas l'optimalité)
P est dans NP.
Conjecture: P != NP (pas de preuve en cas)
NP - P != vide
"Oracle": fonction en O(1) qui répond à une question difficile
Réductibilité: problème X est polynomialement réductible au problème Y (Alan Turing)
au sens de Turing. X <=T Y s'il existe un algorithme polynomiale pour résoudre
X en autant que la résolution de Y est O(1)
Si X <=T Y et Y <=T Y alors X==T Y (équivalence)
Un problème de décision X appartient à NP est NP-Complet si pour tout problème Y appartenant à NP
on a Y<=X.
En pratique: un Problème NP-complet peut avoir des solutions efficaces sur des cas particuliers
ou des solutions approximatives qui sont exactes très souvent.
Tout les problèmes NP-Complet sont au même niveau de complexité:
Trouver une solution efficace pour un = trouver une solution efficae pour tous.
Théorême de Cooke (1971)
========================
Notation !P (non P) p+q = p ou q, p*q = p et q
Définition:
Une expression booléeene est satisfaisable s'il existe une assignation
de valeurs à ases variables pour la rendre vraie.
p*-(-p): ok
SAT: soit B une expression booléenne. Est-elle satisfaisable?
SAT appartient à NP, c'est facile à vérifier O(N) est vrai.
Mais pour N variables, on a 2^n assignation possibles.
Définition littéral: variable booléenne ou sa négation
Définition clause: disjonction (+) de littéraux
Définition: Une expression booléenne est en FNC (Forme Normal Conjonctive) si
c'est une clause ou une conjonction (*) de clause.
Il n'y a pas plus de k littéraux. k-FNC
Ex.: (p+q+-r)*r : 3 littéraux (3-FNC)
(p+(q*r)) est invalide car il s'agit d'une disjonction d'un littéral avec une disjonction
Toute expression booléenne peut être normalisés en FNC (mais prend plus de place)
SAT-FNC: restrictions de SAT aux FNC
Pour tous les k>0, SAT-k-FNC qui est la restriction au k-FNC
Cooke: SAT-FNC est NP-Complet (c'est le plus difficile)
Applications: 3-col, brassard, page 455
3-coloriable, une des entrées (1,2,3) est de couleur T
4 si >1 point d'entrée avec le même couleur
Algorithme déterministe
=======================
Déterministe: Comportement totalement déterminé par l'input.
Non-déterministe: lorsqu'il y a plusieurs actions possibles, choisit toujours la meilleur (magie?).
Un algo N-D peut tourner sur une machine "normale" (déterministe) s'il y a un nombre illimité de processus.
1 choix, 1 processeur, le bon choix est trouvé "du premier coup".
Résoudre les mêmes problèmes que l'algo déterministes mais en temps asymptotiquement plus bas.
Un problème NP-Complet est polynomialement résolu par un algo Non-Déterministe.
Un algorithme non-déterministe peut être transformé en déterministe avec
rallentissement asymptotique, possiblement exponentielle.
Exemple de parallélisme:
recherche dans T[1..N] non trié. Seq=0(N), En parallèle: O(1).
NP: solvables en temps polynomialement avec Non-Déterministe (N-D) et vérifiable polynomialement avec déterministe.
X est NP-complet si tout problème Y appartient à NP est <= X
X est NP-difficile (NP-Hard) si X n'appartient pas à NP mais X >= Y appartenant à NP_Complet.
Algorithme probabiliste
=======================
Trésor caché: 2 endroits possibles (immédiatement reconnaissable)
Chacun des 2 endroits est à 5 jours de voyage. À chaque jour, on prélève
une part. Une carte existe mais est déchiffrable en 4 jours. Une fée offre
la bonne solution contre 3 jours.
Soit x = valeur du trésor. y = 1 jour de butin.
x > 9y
Si on déchiffre: x - 9y
on achète x - 8y
on choisit au hasard: 50% de (x-5y) et 50% de (x-10y): espéré: x- 7,5y.
Le hasard est donc un des meilleurs choix à long terme.
Classes d'algorithmes probabilistes
===================================
1- Numérique
Solution approximative de problème numérique
Exemple: simulation pour estimer la longueur d'une file d'attente
(système stockastique n! états pour n variables)
Réponse approximative, précision selon le temps investis.
Ex. approximer PI avec des cure-dents et une planche de lattes.
cure-dents: taile x et latte: largeur 2x.
Rapport entre touche/touche pas = PI
approximer PI en lançant des dards sur un cercle.
intérieur/extérieur
2- Monte Carlo
Pas d'approximation (inapplicable)
Réponse exacte avec une probabilité d'erreurs (non détectée)
Toujours une réponse mais pas toujours correctes.
Dépend du temps investi (il s'agit d'une boucle).
P(x) -> bool (oui: premier, non: non premier)
Retourne vrai si X est premier % en 50%, et faux sinon
3- Las Vegas
Jamais d'erreur mais pas toujours de réponse
(dépend du temps investis). On a une probabilité d'échec peut-être arbitrairement réduite.
4- Sherwood: toujours une réponse. toujours exacte (non exponentielle)
Comptage probabiliste
=====================
Feuille "binaire" dans une liste chaînée par indices de tableau.
B(x): i = Premier
mx = tab[i]
Pour j de floor(L * racine(n))
Si Tab[j] < x < tab[i]
i = j; mx = tab[i]
Fin
Retour chercher(x,i)
Algorithme probabiliste
=======================
Las Vegas
Reponse toujours correcte mais % d'échec
Principe: prendre une décision aléatoire, possiblement mauvaise, doit-on recommencer?
une augmentation du temps, diminue le pourcentage d'échec
Cas de base:
AlgoLV (X:données, sol:solution, succes:bool)
Soit P(X) = probabilité de succès sur X
LV est correct si P(X) > 0 pour tout X
Soit S(X) = temps espéré sur X
S(X) = somme(S(X)*P(X))
E(X) = temps espéré d'échec
Obstine(X, sol, succes)
Boucle
AlgoLV(X, sol, succes)
jusqu'à succès = vrai
Retourne solution
Soit T(X), le temps espéré pour la fonction Obstine()
Récurrence:
T (X) = T(succèes) + T(échec)
P(X)S(X) + (1-P(X))(E(X)+T(X))
Note: solution si succès = vrai
On doit faire des compromis entre P(X), E(X), S(X).
On peut être tenter de diminuer P(X) et T(échec) est bas.
Tradeoff/compromis: choisir 3 ou 4 données aléatoirement + récursion
Ex.2: Choisir un chef dans un réseau en anneau
Chaque poste connaît N et utile une fonction random indépendante
Soit M le nombre de poste
Init: N=N
À chaque itération
chaque poste génère un entier entre 1 et M (inclus)
Ceux qui génère 1, reste actifs
Fin quand M=1
Le temps espéré est de O(N).
Monte Carlo
répond toujours avec un pourcentage d'erreur
Application: problème exponentiel, pas de L.V.
Un Monte Carlo est S-Biaisé (booléen vrai/faux) s'il y a un
sous-ensemble X des données et une solution connu S tel que
1- La réponse de l'algorithme est toujours correcte si x appartient à X
2- La bonne réponse à tout X n'appartenant pas à X est S mais
il peut se tromper dans ce cas.
Vrai-biaisé: Vrai est bon à 100%, faux est incertain (biaisé)
Faux-biaisé: Faux est bon à 100%, vrai est incertain (biaisé)
Monte Carlo est consistant si MC(x) retourne toujours la même réponse
(lorsque correcte). Soi un Monte Carlo consistant, s-biaisé et p-correct (1 - probabilité d'erreur)
probabilités de réponse correct et aussi soit x: une donnée, y: une valeurs retournée.
Exemple de problème qui n'est pas de Monte Carlo
Prendre(N)
Si pgcd(N,30030) = 1
retourne vrai
Sinon
retourne faux
Ce problème n'est pas de type Monte Carlo, car la probabilité d'erreur du pgcd() est de 85%.
Approche probabiliste
Erreur sur une des deux réponse
Vrai n'est pas sur
Faux est sur
Test probabilitiste de primalité
Pseudo-premier(a, n)
retourne vrai ssi(a^(n-1) mod n = 1)
retourne faux avec certitude
ou vrai avec probabilité de 50% d'erreur
Méthode classique
Premier(i)
i div par premier
jusqu'à floor(racine(n))
O(N) doit être rapide en temps réel.
Si N = le nombre de chiffres alors, il s'agit d'une méthode O(10^(n/2))
Si ret F une fois=faux, si retourne 0 200 fois, erreur de 1/(2^200)
Monte carlo est P-correct: solution correcte avec problème >=P.
Son avantage est P-1/2. Augmenter les probabilités de succès en le répétant
plusieurs fois. Exemple de Monte Carlo:
Tableau majoritaire.
Soit T = Tableau non trié. Existe-t-il un nombre qui rempli 50%
du tableau.
MC: piger un élément, compter son nombre d'occurence m en O(n)
si m > n/2
retourne vrai
sinon
retourne faux
Erreur:
1/2^(10) = O(10n)
Lire les commentaires | Laisser un commentaire
