Chapitre 8 : Classes de complexité P et NP |
Exercice 11. La méthode naïve pour chercher le plus petit diviseur d non trivial d'un entier p impair consiste à tester tous les entiers d impairs inférieurs à p1/2, jusqu'à trouver un diviseur (en cas d'échec, on en déduit que p est premier). Exprimer la complexité de cet algorithme en utilisant la notation "grand-O", d'abord en fonction de p, ensuite en fonction de la taille de p.
Exercice 12. Montrer qu'une expression O ( ln n ) est aussi O ( log2 n ), et vice-versa. Les notations O ( e n ) et O ( 2 n ) sont-elles équivalentes ?
Exercice 41.
Calculer la table de vérité de la formule :
Φ = ( x ∧ ¬y ) ∨ ( y ∧ ¬z ) ∨ z
Exercice 42. Transformer la formule ( x1 ∨ y1 ) ∧ ( x2 ∨ y2 ) ∧ … ∧ ( xn ∨ yn ) en forme normale disjonctive.
Exercice 43.
Exercice 44.
Exercice 11. La complexité de l'algorithme est assurément en O ( p1/2 ), même si, en moyenne, elle est beaucoup plus faible (la plupart des entiers ont un petit diviseur). En désignant par n la taille de p, la complexité est en O ( 2 n/2 ), car p est borné par 2n+1.
Le fait de tester seulement les diviseurs impairs divise par 2 le temps d'exécution, ce qui est appréciable en pratique, mais n'est pas visible dans la notation "grand-O", par définition de celle-ci.
Noter aussi qu'on suppose implicitement, ci-dessus, que le coût d'une division est constant, alors qu'il est en O ( n2 ), et donc la complexité est rigoureusement O ( n2 2 n/2 ) ; en pratique le terme exponentiel empêche n de devenir grand (par exemple il ne dépasse certainement pas 100), et donc le coût d'une division peut être considéré comme borné par une constante assez petite (sur un processeur standard, le coût d'une division dépend de la taille des entiers exprimée en mots de 32 bits, taille qui ne dépasse certainement pas 4 pour p, et 2 pour un diviseur d).
Exercice 12. Par définition, n = 2 log2 n, d'où en prenant le logarithme népérien de chaque côté :
ln n = ( log2 n ) ln 2 .
Par contre e n / 2 n = ( e / 2 ) n est loin d'être borné par une constante, donc une expression O ( e n ) n'est pas forcément O ( 2 n ) — mais l'inverse est vrai.
Exercice 41.
Table de vérité de Φ = ( x ∧ ¬y ) ∨ ( y ∧ ¬z ) ∨ z :
x | y | z | x ∧ ¬y | y ∧ ¬z | Φ |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 1 |
Par distributivité on obtient :
( x ∧ ¬y )
∨
( y ∧ ¬z ) =
( x ∨ y )
∧
( x ∨ ¬z )
∧
( ¬y ∨ y )
∧
( ¬y ∨ ¬z )
La troisième clause est inutile (tautologie), il reste :
( x ∨ y ) ∧ ( x ∨ ¬z ) ∧ ( ¬y ∨ ¬z )
et on peut remarquer que la clause du milieu est redondante (examiner les tables de vérité, ou considérer successivement les cas y = 0 et y = 1). D'où finalement :
( x ∨ y ) ∧ ( ¬y ∨ ¬z )
Ces clauses correspondent aux lignes de la table de vérité pour lesquelles la formule de départ vaut 0, à savoir les lignes 1 et 2 ( x = 0, y = 0, d'où la clause x ∨ y, qui vaut 0 exactement pour ces deux lignes), et les lignes 4 et 8 ( y = 1, z = 1, d'où la clause ¬y ∨ ¬z, qui vaut 0 exactement pour ces deux lignes).
Exercice 42. En développant par distributivité, on obtient une disjonction de 2n conjonctions, chacune de la forme :
z1 ∧ z2 ∧ … ∧ zn
où chaque zi vaut soit xi , soit yi . L'examen de la table de vérité montre que toute disjonction de conjonctions contient au moins chacune des conjonctions ci-dessus ; c'est un exemple d'explosion exponentielle de la taille d'une formule, lorsqu'on la transforme en forme normale disjonctive (resp. conjonctive).
Exercice 43. Rappelons que l'égalité x = y est équivalente à ( x ∨ ¬y ) ∧ ( ¬x ∨ y ) ; on peut le vérifier en calculant la table de vérité de cette expression.
L'égalité z = x ∧ y est équivalente à ( ¬ ( x ∧ y ) ∨ z ) ∧ ( ( x ∧ y ) ∨ ¬z ) ; soit, en appliquant la loi de Morgan au premier terme, et en développant le second par distributivité :
( ¬x ∨ ¬y ∨ z ) ∧ ( x ∨ ¬z ) ∧ ( y ∨ ¬z ) .
L'égalité z = x ∨ y est équivalente à ( ¬ ( x ∨ y ) ∨ z ) ∧ ( ( x ∨ y ) ∨ ¬z ) ; soit, en appliquant la loi de Morgan au premier terme :
( ( ¬x ∧ ¬y ) ∨ z ) ∧ ( x ∨ y ∨ ¬z )
puis en développant le premier terme par distributivité :
( ¬x ∨ z ) ∧ ( ¬y ∨ z ) ∧ ( x ∨ y ∨ ¬z ) .
Exercice 44.
x ⇒ ( ¬y ∧ ¬z ) équivaut par définition à ¬x ∨ ( ¬y ∧ ¬z ) ; en développant par distributivité, on obtient :
( ¬x ∨ ¬y ) ∧ ( ¬x ∨ ¬z ) .
Formule exprimant que l'une des trois variables x, y, z vaut 1, et une seulement :
( x ∨ y ∨ z ) ∧ ( ¬x ∨ ¬y ) ∧ ( ¬x ∨ ¬z ) ∧ ( ¬y ∨ ¬z ) .
Généralisation au cas de n variables :
( x1 ∨
x2 ∨
… ∨
xn )
∧
∧
( ¬x1 ∨ ¬x2 )
∧ … ∧
( ¬x1 ∨ ¬xn )
∧
∧
( ¬x2 ∨ ¬x3 )
∧ … ∧
( ¬x2 ∨ ¬xn )
∧
∧
( ¬x3 ∨ ¬x4 )
∧ etc.
La formule contient une clause ¬xi ∨ ¬xj pour chacun des n (n - 1) / 2 couples (i, j), avec i < j. La première clause garantit que l'un des xi vaut 1. Supposons par exemple x1 = 1 ; alors chaque clause ¬x1 ∨ ¬xi se réduit à ¬xi , donc xi = 0, pour tout i > 1 ; les clauses restantes (celles qui ne contiennent pas la variable x1 ) sont alors toutes (doublement) vérifiées.