Cours Algo Avancee [PDF]

Zitiervorschau

Cours d’Algorithmique avanc´ee Deuxi`eme cycle en Math´ematiques et Informatique Prof. Ruffin-Benoˆıt M. Ngoie Docteur en Sciences

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Pr´esentation du cours

Objectifs du cours : Ce cours permet `a l’´etudiant d’acqu´erir une parfaite maˆıtrise des structures des algorithmes et des donn´ees au travers d’une analyse sur leur complexit´e et leur correction.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Pr´esentation du cours

Objectifs du cours : Ce cours permet `a l’´etudiant d’acqu´erir une parfaite maˆıtrise des structures des algorithmes et des donn´ees au travers d’une analyse sur leur complexit´e et leur correction. Volume horaire : Pour atteindre la maˆıtrise de cours l’´etudiant a besoin de 45 heures avec l’enseignant en classe. En outre, des efforts personnels lui seront exig´es ce qui peut repr´esenter un volume de 30 heures de travaux personnels.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Pr´esentation du cours

Objectifs du cours : Ce cours permet `a l’´etudiant d’acqu´erir une parfaite maˆıtrise des structures des algorithmes et des donn´ees au travers d’une analyse sur leur complexit´e et leur correction. Volume horaire : Pour atteindre la maˆıtrise de cours l’´etudiant a besoin de 45 heures avec l’enseignant en classe. En outre, des efforts personnels lui seront exig´es ce qui peut repr´esenter un volume de 30 heures de travaux personnels. Modalit´ es d’´ evaluation : Interrogations ´ecrites ou orales, contrˆ ole continu, examen final `a l’´ecrit et/ou `a l’oral.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Contrat p´edagogique

Il s’agit d’une convention entre l’enseignant et les apprenants. Quelques points d’entente : Heure de d´ ebut des enseignements

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Contrat p´edagogique

Il s’agit d’une convention entre l’enseignant et les apprenants. Quelques points d’entente : Heure de d´ ebut des enseignements Usage d’appareils de t´ el´ ecommunication

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Contrat p´edagogique

Il s’agit d’une convention entre l’enseignant et les apprenants. Quelques points d’entente : Heure de d´ ebut des enseignements Usage d’appareils de t´ el´ ecommunication Dur´ ee des enseignements

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Contrat p´edagogique

Il s’agit d’une convention entre l’enseignant et les apprenants. Quelques points d’entente : Heure de d´ ebut des enseignements Usage d’appareils de t´ el´ ecommunication Dur´ ee des enseignements Pauses ´ eventuelles

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Contrat p´edagogique

Il s’agit d’une convention entre l’enseignant et les apprenants. Quelques points d’entente : Heure de d´ ebut des enseignements Usage d’appareils de t´ el´ ecommunication Dur´ ee des enseignements Pauses ´ eventuelles Autres avis

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Organisation du cours

Ce cours est organis´e en 4 chapitres : Chapitre 1 : Notions de base Chapitre 2 : Complexit´ e algorithmique Chapitre 3 : M´ ethodes de programmation Chapitre 4 : Programmation proc´ edurale en Python

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base

Algorithme Math´ ematiciens. M´ethode de r´esolution d’un probl`eme.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base

Algorithme Math´ ematiciens. M´ethode de r´esolution d’un probl`eme. Informaticiens. Proc´ed´e mis en oeuvre sur un ordinateur, et qui, r´ep´et´e autant de fois qu’il est n´ecessaire, permet d’obtenir le r´esultat cherch´e.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base

Algorithme Math´ ematiciens. M´ethode de r´esolution d’un probl`eme. Informaticiens. Proc´ed´e mis en oeuvre sur un ordinateur, et qui, r´ep´et´e autant de fois qu’il est n´ecessaire, permet d’obtenir le r´esultat cherch´e. Markov. Tout ensemble de r`egles pr´ecises destin´e `a obtenir un r´esultat d´etermin´e `a partir de certaines donn´ees initiales.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base

Algorithme Math´ ematiciens. M´ethode de r´esolution d’un probl`eme. Informaticiens. Proc´ed´e mis en oeuvre sur un ordinateur, et qui, r´ep´et´e autant de fois qu’il est n´ecessaire, permet d’obtenir le r´esultat cherch´e. Markov. Tout ensemble de r`egles pr´ecises destin´e `a obtenir un r´esultat d´etermin´e `a partir de certaines donn´ees initiales. Origine. Arabe ! ! !

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base Algorithmique

Algorithmique Branche de l’informatique qui ´etudie le maniement des structures logiques des programmes informatiques. Algorithmique =⇒ Langages de programmation

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base Algorithmique

Algorithmique Branche de l’informatique qui ´etudie le maniement des structures logiques des programmes informatiques. Algorithmique =⇒ Langages de programmation Programme R´ealisation d’un algorithme au moyen d’un langage de programmation donn´e (sur une architecture donn´ee).

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base Ordinateurs

Ordinateur Calculateur dot´e de m´emoires `a grande capacit´e, de moyens de traitement des informations `a grande vitesse, capable de r´esoudre des probl`emes arithm´etiques et logiques complexes grˆace `a l’exploitation automatique des programmes enregistr´es. Origine : Jacques Perret

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base Ordinateurs (extrait de la lettre de Perret)

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base Structure de donn´ees

Structure de donn´ees Description de l’organisation des donn´ees g´er´ees par un algorithme. Exemples : Tableaux, Fichiers, Listes tri´ees, Graphes, Bases de donn´ees, Entrepˆots de donn´ees, etc.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base Probl`emes fondamentaux en Algorithmique

Complexit´ e. D´eterminer, sous un certain nombre de conditions, quel sont les temps de calcul et espace m´emoire requis pour obtenir un r´esultat donn´e.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base Probl`emes fondamentaux en Algorithmique

Complexit´ e. D´eterminer, sous un certain nombre de conditions, quel sont les temps de calcul et espace m´emoire requis pour obtenir un r´esultat donn´e. Calculabilit´ e. Existe-t-il des tˆaches pour lesquelles il n’existe aucun algorithme ? Etant donn´e une tˆache, peut-on dire s’il existe un algorithme qui la r´esolve ?

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base Probl`emes fondamentaux en Algorithmique

Complexit´ e. D´eterminer, sous un certain nombre de conditions, quel sont les temps de calcul et espace m´emoire requis pour obtenir un r´esultat donn´e. Calculabilit´ e. Existe-t-il des tˆaches pour lesquelles il n’existe aucun algorithme ? Etant donn´e une tˆache, peut-on dire s’il existe un algorithme qui la r´esolve ? Correction. S’assurer qu’un algorithme r´epond au probl`eme pour lequel il a ´et´e con¸cu.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base Conseils pour ˆetre bon en algorithmique

Intuition. Parfois naturel pour les uns mais peut s’acqu´erir `a force de travailler.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 1 : Notions de base Conseils pour ˆetre bon en algorithmique

Intuition. Parfois naturel pour les uns mais peut s’acqu´erir `a force de travailler. M´ ethode et rigueur. Syst´ematiquement se mettre mentalement `a la place de la machine, parfois avec papier et crayon. N’attribuez jamais ` a la malveillance ce qui s’explique tr` es bien par l’incomp´ etence (Bonaparte). A l’origine de toute erreur attribu´ ee ` a l’ordinateur, il y a au moins deux erreurs humaines dont celle consistant ` a attribuer l’erreur ` a l’ordinateur.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique D´efinition & notations

Complexit´e algorithmique Mesure du nombre d’op´erations fondamentales qu’effectue un algorithme sur un jeu de donn´ees (en temps) ou la quantit´e de m´emoire n´ecessaire pour qu’un algorithme s’ex´ecute (en espace).

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique D´efinition & notations

Complexit´e algorithmique Mesure du nombre d’op´erations fondamentales qu’effectue un algorithme sur un jeu de donn´ees (en temps) ou la quantit´e de m´emoire n´ecessaire pour qu’un algorithme s’ex´ecute (en espace). Notations de Landau f = O(g ) ⇔ ∃n0 ≥ 0, ∃c ≥ 0, ∀n ≥ n0 , f (n) ≤ c.g (n) f = Ω(g ) ⇔ ∃n0 ≥ 0, ∃c ≥ 0, ∀n ≥ n0 , f (n) ≥ c.g (n) f = Θ(g ) ⇔ f = O(g ) et g = O(f ). Dans ce cours, nous ne traiterons que de la complexit´ e temporelle.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Types de complexit´e

Complexit´e au meilleur Plus petit nombre d’op´erations qu’aura `a ex´ecuter l’algorithme sur un jeu de donn´ees de taille n (borne inf´ erieure).

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Types de complexit´e

Complexit´e au meilleur Plus petit nombre d’op´erations qu’aura `a ex´ecuter l’algorithme sur un jeu de donn´ees de taille n (borne inf´ erieure). Complexit´e au pire Plus grand nombre d’op´erations qu’aura `a ex´ecuter l’algorithme sur un jeu de donn´ees de taille n (borne sup´ erieure).

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Types de complexit´e

Complexit´e au meilleur Plus petit nombre d’op´erations qu’aura `a ex´ecuter l’algorithme sur un jeu de donn´ees de taille n (borne inf´ erieure). Complexit´e au pire Plus grand nombre d’op´erations qu’aura `a ex´ecuter l’algorithme sur un jeu de donn´ees de taille n (borne sup´ erieure). Complexit´e en moyenne Moyenne des complexit´es de l’algorithme sur des jeux de donn´ees de taille n. P C (d) Tmoy (n) = d∈Dn |Dn | Tenir compte de la probabilit´e d’apparition de chacun des jeux de donn´ees. Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Optimalit´e

Algorithme optimal Algorithme dont la complexit´e est minimale parmi les algorithmes de sa classe. RAM Machine ` a acc` es al´ eatoire. Cette machine a deux caract´eristiques : s´equentielle et d´eterministe. Machine s´equentielle Processeur unique, les instructions sont ex´ecut´ees l’une apr`es l’autre sans op´erations simultan´ees. Machine d´eterministe Les mˆemes donn´ees fournies au mˆeme programme produisent les mˆemes r´esultats ind´ependamment du moment et de l’environnement de l’ex´ecution. Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

E x
er ci c
e s

Prof. Ruffin-Benoˆıt M. Ngoie

!

!

Algorithmique avanc´ ee

!

Exercices 1

Etudier la complexit´e des algorithmes ci-dessous : • 1. Algorithme 1 Lire n l ←0 Pour i ← 1 ` a n faire Pour j ← 1 ` a 2n faire l ←l +1 Fin Pour Fin Pour Ecrire l

• 2. Algorithme 2 Lire n l ←0 Pour i ← 1 ` a n faire Pour j ← 1 ` a i faire Pour k ← j ` a n faire l ←l +1 Fin Pour Fin Pour Fin Pour Ecrire l Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Exercices

• 3. Montrer que : 1 2 3 4 5

f (n) = 60n2 + 5n + 1 est O(n2 ) f (n) = 60n3 + 5n2 − 6n + 7 est O(n3 ) f (n) = 3n2 + 7n − 8 est Θ(n2 ) f (n) = 2n + 1 est O(n2 ) f (n) = 4n + 3 est O(n9 )

• 4. Quel est l’ordre de complexit´e de : 1 2 3

f (n) = 3n2 + 2n log(n) − 5n + 8 f (n) = cos n f (n) = 3n3 + 7n3 log(n) − 12

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Th´eor`emes

Th´ eor` eme 1 : Si f1 (n) = O(g1 (n)) et f2 (n) = O(g2 (n)) alors f1 (n) + f2 (n) = O(max{g1 (n), g2 (n)}) Th´ eor` eme 2 : Si f (n) = O(g (n)) alors ∀k > 0, f (n) = O(k.g (n)) Th´ eor` eme 3 : Si f (n) = O(g (n)) et h(n) ≥ g (n), ∀n ≥ n0 (avec n0 ∈ N) alors f (n) = O(h(n))

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Machine de Turing

Calculabilit´e Domaine scientifique traitant de la capacit´e de r´esoudre un probl`eme algorithmiquement.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Machine de Turing

Calculabilit´e Domaine scientifique traitant de la capacit´e de r´esoudre un probl`eme algorithmiquement. Machine de Turing Quintuplet M = (Q, Γ, δ, q0 , F ) o` u Q d´esigne l’ensemble fini des ´etats de la machine, Γ l’ensemble fini de symboles pouvant ˆetre ´ecrits sur la bande de la machine (incluant le symbole “blanc” pouvant apparaˆıtre infiniment sur la bande de la machine), δ : Q × Γ → Q × Γ × {−1, +1} est la fonction de transition, q0 est l’´etat initial, et F ⊆ Q est l’ensemble des ´etats finaux.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Machine de Turing

Calculabilit´e Domaine scientifique traitant de la capacit´e de r´esoudre un probl`eme algorithmiquement. Machine de Turing Quintuplet M = (Q, Γ, δ, q0 , F ) o` u Q d´esigne l’ensemble fini des ´etats de la machine, Γ l’ensemble fini de symboles pouvant ˆetre ´ecrits sur la bande de la machine (incluant le symbole “blanc” pouvant apparaˆıtre infiniment sur la bande de la machine), δ : Q × Γ → Q × Γ × {−1, +1} est la fonction de transition, q0 est l’´etat initial, et F ⊆ Q est l’ensemble des ´etats finaux. Th´eor`eme de Church-Turing Tout calcul fond´e sur une m´ethode effective peut ˆetre effectu´e par une machine de Turing. Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Machine de Turing

Machine de Turing universelle Turing a d´emontr´e qu’il existait des machines de Turing M = (Q, Γ, δ, q0 , F ) pouvant simuler les calculs de toutes les machines de Turing. Pour que M puisse simuler M 0 il faut montrer comment encoder le quintuplet M = (Q 0 , Γ0 , δ 0 , q00 , F 0 ) d´ecrivant M 0 sur le ruban de M (Cf. Ordinateur). Il n’y a pas de diff´ erence formelle entre donn´ ees et programme. Tous les deux sont des donn´ ees pour une machine de Turing universelle.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Ind´ecidabilit´e

Existe-t-il une m´ethode algorithmique permettant de r´esoudre tous les probl`emes ? Non ! ! ! Il existe des probl`emes qui ne sont pas d´ ecidables, i.e. pour lesquels il n’existe pas de machine de Turing permettant de les r´esoudre. Th´ eor` eme 4 (Turing, 1936). Etant donn´e une machine de Turing M et pour toute entr´ee x de cette machine, d´eterminer si M s’arrˆete ou pas sur l’entr´ee x est ind´ecidable.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Complexit´e de probl`emes

Complexit´e temporelle d´efinie par les machines de Turing Soit M une machine de Turing d´eterministe qui s’arrˆete sur toutes les entr´ees. La complexit´ e temporelle de M est la fonction f : N → N, o` u f (n) est le nombre maximum d’´etapes que M utilise pour n’importe quelle entr´ee de taille n. On dit que M s’ex´ ecute en temps f (n).

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Complexit´e de probl`emes

Complexit´e temporelle d´efinie par les machines de Turing Soit M une machine de Turing d´eterministe qui s’arrˆete sur toutes les entr´ees. La complexit´ e temporelle de M est la fonction f : N → N, o` u f (n) est le nombre maximum d’´etapes que M utilise pour n’importe quelle entr´ee de taille n. On dit que M s’ex´ ecute en temps f (n). Complexit´e d’un probl`eme d´efinie par les machines de Turing Soit t : N → R+ une fonction. La classe de complexit´e de temps TIME (t(n)) est l’ensemble de tous les langages qui sont d´ecidables par une machine de Turing d´eterministe en temps t(n).

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Complexit´e de probl`emes

Classe P Ensemble des langages qui sont d´ecidables en temps polynomial par une machine de Turing d´eterministe. Autrement dit : P = ∪k∈N TIME (nk ) P correspond en pratique `a l’ensemble des probl`emes qui sont traitables en un temps raisonnable par un ordinateur. Temps d’ex´ecution d’une machine de Turing non d´eterministe Soit N une machine de Turing non d´eterministe qui est un d´ecideur. Le temps d’ex´ ecution de N est la fonction f : N → N, o` u f (n) est le nombre d’´etapes que N utilise pour n’importe quelle entr´ee de taille n. Soit t : N → R+ une fonction. La classe de complexit´e de temps NTIME (t(n)) est l’ensemble de tous les langages qui sont d´ecidables par une machine de Turing non Prof.temps Ruffin-Benoˆ M. Ngoie Algorithmique avanc´ ee d´eterministe en f ıt(n).

Chapitre 2 : Complexit´e algorithmique Complexit´e de probl`emes

Temps d’ex´ecution d’une machine de Turing non d´eterministe Soit N une machine de Turing non d´eterministe qui est un d´ecideur. Le temps d’ex´ ecution de N est la fonction f : N → N, o` u f (n) est le nombre d’´etapes que N utilise pour n’importe quelle entr´ee de taille n. Soit t : N → R+ une fonction. La classe de complexit´e de temps NTIME (t(n)) est l’ensemble de tous les langages qui sont d´ecidables par une machine de Turing non d´eterministe en temps f (n).

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Complexit´e de probl`emes

Temps d’ex´ecution d’une machine de Turing non d´eterministe Soit N une machine de Turing non d´eterministe qui est un d´ecideur. Le temps d’ex´ ecution de N est la fonction f : N → N, o` u f (n) est le nombre d’´etapes que N utilise pour n’importe quelle entr´ee de taille n. Soit t : N → R+ une fonction. La classe de complexit´e de temps NTIME (t(n)) est l’ensemble de tous les langages qui sont d´ecidables par une machine de Turing non d´eterministe en temps f (n). Classe NP Ensemble des langages qui sont d´ecid´es en temps polynomial par une machine de Turing non d´eterministe. Autrement dit : NP = ∪k∈N NTIME (nk ) Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Classe NP

Proposition. Un langage A sur un alphabet Σ est dans NP si et seulement si il existe un polynˆ ome p(n) et un langage B ∈ P tels que x ∈ A ⇔ ∃y ∈ Σp(|x|) (x, y ) ∈ B Le mot y justifiant l’appartenance de x `a A est appel´e certificat. Autrement dit : Soit, pour une instance donn´ee, une solution `a un probl`eme de d´ecision et un certificat, il est possible de prouver en temps polynomial (grˆace au certificat) que la solution du probl`eme est correcte.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Tous les probl`emes de P appartiennent `a NP.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Tous les probl`emes de P appartiennent `a NP. • Clique Entr´ ee : Un graphe non orient´e G et un entier k.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Tous les probl`emes de P appartiennent `a NP. • Clique Entr´ ee : Un graphe non orient´e G et un entier k. Question : G poss`ede-t-il une clique de taille k ?

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Tous les probl`emes de P appartiennent `a NP. • Clique Entr´ ee : Un graphe non orient´e G et un entier k. Question : G poss`ede-t-il une clique de taille k ? Certificat : Ensemble des k sommets formant une clique (on v´erifie en temps polynomial que ces k sommets forment bien une clique).

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Tous les probl`emes de P appartiennent `a NP. • Clique Entr´ ee : Un graphe non orient´e G et un entier k. Question : G poss`ede-t-il une clique de taille k ? Certificat : Ensemble des k sommets formant une clique (on v´erifie en temps polynomial que ces k sommets forment bien une clique). • Chaˆıne hamiltonienne Entr´ ee : Un graphe non orient´e G .

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Tous les probl`emes de P appartiennent `a NP. • Clique Entr´ ee : Un graphe non orient´e G et un entier k. Question : G poss`ede-t-il une clique de taille k ? Certificat : Ensemble des k sommets formant une clique (on v´erifie en temps polynomial que ces k sommets forment bien une clique). • Chaˆıne hamiltonienne Entr´ ee : Un graphe non orient´e G . Question : G poss`ede-t-il une chaˆıne hamiltonienne ?

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Tous les probl`emes de P appartiennent `a NP. • Clique Entr´ ee : Un graphe non orient´e G et un entier k. Question : G poss`ede-t-il une clique de taille k ? Certificat : Ensemble des k sommets formant une clique (on v´erifie en temps polynomial que ces k sommets forment bien une clique). • Chaˆıne hamiltonienne Entr´ ee : Un graphe non orient´e G . Question : G poss`ede-t-il une chaˆıne hamiltonienne ? Certificat : Chaˆıne hamiltonienne.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Partition Entr´ ee : Un ensemble S de n entiers positifs.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Partition Entr´ ee : Un ensemble S de n entiers positifs. Question : Peut-on partitionner S en deux sous-ensembles S 0 et S 00 tels que la somme des ´el´ements de S 0 soit ´egale `a la somme des ´el´ements de S 00 ?

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Partition Entr´ ee : Un ensemble S de n entiers positifs. Question : Peut-on partitionner S en deux sous-ensembles S 0 et S 00 tels que la somme des ´el´ements de S 0 soit ´egale `a la somme des ´el´ements de S 00 ? Certificat : Couple (S 0 , S 00 ).

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Partition Entr´ ee : Un ensemble S de n entiers positifs. Question : Peut-on partitionner S en deux sous-ensembles S 0 et S 00 tels que la somme des ´el´ements de S 0 soit ´egale `a la somme des ´el´ements de S 00 ? Certificat : Couple (S 0 , S 00 ). • Satisfiabilit´ e (SAT) Entr´ ee : Une formule bool´eenne φ.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Partition Entr´ ee : Un ensemble S de n entiers positifs. Question : Peut-on partitionner S en deux sous-ensembles S 0 et S 00 tels que la somme des ´el´ements de S 0 soit ´egale `a la somme des ´el´ements de S 00 ? Certificat : Couple (S 0 , S 00 ). • Satisfiabilit´ e (SAT) Entr´ ee : Une formule bool´eenne φ. Question : φ est-elle satisfiable ?

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Exemples de probl`emes dans NP

• Partition Entr´ ee : Un ensemble S de n entiers positifs. Question : Peut-on partitionner S en deux sous-ensembles S 0 et S 00 tels que la somme des ´el´ements de S 0 soit ´egale `a la somme des ´el´ements de S 00 ? Certificat : Couple (S 0 , S 00 ). • Satisfiabilit´ e (SAT) Entr´ ee : Une formule bool´eenne φ. Question : φ est-elle satisfiable ? Certificat : affectation des valeurs Vrai et Faux aux variables.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique P versus NP

• P est la classe des probl`emes dont on peut rapidement trouver une solution (rapidement = temps polynomial). • NP est la classe des probl`emes dont on peut rapidement v´erifier qu’une solution en est bien une solution. • Question : P = NP ? Malgr´e de nombreuses recherches, cette question n’est pas r´esolue. Il est conjectur´e que P 6= NP mais on ne connaˆıt pas de probl` eme de NP dont il est prouv´ e qu’il n’appartienne pas ` a P.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Probl`emes NP-complets

Cook et Levin dans les ann´ees 1970 ont d´ecouvert certains probl`emes de NP dont la complexit´e est li´ee `a la complexit´e de la classe NP enti`ere : si un algorithme polynomial existe pour un de ces probl` emes alors tous les probl` emes de NP peuvent ˆ etre r´ esolus en temps polynomial. Ces probl`emes sont dits NP-complets.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Perspectives ´eventuelles

• En th´eorie, pour prouver que P = NP ou P 6= NP, se concentrer sur un probl`eme NP-complet et montrer qu’il peut ou ne peut pas se r´esoudre en un temps polynomial. • En pratique, pour prouver qu’un probl`eme est NP-complet, montrer qu’il est peu probable qu’un algorithme polynomial existe pour ce probl`eme (puisqu’il est conjectur´e que P 6= NP). • Le premier probl` eme qui a ´ et´ e montr´ e NP-complet est le probl` eme de satisfiabilit´ e (SAT). Th´ eor` eme 5. Sat ∈ P ⇔ P = NP.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique R´eduction polynomiale

r´eduction polynomiale Soit A et B deux probl`emes de d´ecision. Le probl`eme A peut ˆetre r´eduit en temps polynomial au probl`eme B, ce qui s’´ecrit A ≤P B, s’il existe une fonction f ex´ecutable en temps polynomial tel que pour toute instance w de A, la r´eponse au probl`eme A sur l’instance w est Oui ⇔ la r´eponse au probl`eme B sur l’instance f (w ) est Oui. Alors on dit que f est une r´ eduction polynomiale de A vers B

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique R´eduction polynomiale

Th´ eor` eme 6. Si A ≤P B et B ∈ P alors A ∈ P. Probl`eme NP-complet Soit A un probl`eme de d´ecision. A est NP-complet si : • A ∈ NP et

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique R´eduction polynomiale

Th´ eor` eme 6. Si A ≤P B et B ∈ P alors A ∈ P. Probl`eme NP-complet Soit A un probl`eme de d´ecision. A est NP-complet si : • A ∈ NP et • Chaque probl`eme B de NP peut ˆetre r´eduit en temps polynomial au probl`eme A.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique R´eduction polynomiale

Th´ eor` eme 7. Si B est NP-complet et B ≤P A avec A ∈ P alors A est NP-complet. Probl`eme NP-complet Pour montrer qu’un probl`eme A est NP-complet : • On montre que A ∈ NP et

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique R´eduction polynomiale

Th´ eor` eme 7. Si B est NP-complet et B ≤P A avec A ∈ P alors A est NP-complet. Probl`eme NP-complet Pour montrer qu’un probl`eme A est NP-complet : • On montre que A ∈ NP et • On montre qu’il existe un probl`eme NP-complet B tel que B ≤P A.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

Chapitre 2 : Complexit´e algorithmique Comment montrer qu’un probl`eme est NP-complet

En r´esum´e : • On ´enonce clairement le probl`eme A dont on veut montrer qu’il est NP-complet • On montre que A ∈ NP en donnant un certificat. • On ´enonce clairement un probl`eme B dont on sait qu’il est NP-complet. • On d´ecrit une r´eduction polynomiale f qui transforme B en A • On prouve que f est bien une r´eduction polynomiale de B en A : Pour toute entr´ee w de B on obtient une entr´ee f (w ) de A telle que la solution au probl`eme B sur l’instance w est Vrai si et seulement si la solution au probl`eme A sur l’instance f (w ) est Vrai.

Prof. Ruffin-Benoˆıt M. Ngoie

Algorithmique avanc´ ee

M er ci

p our

att
enti on

Prof. Ruffin-Benoˆıt M. Ngoie

votr e

!

!

Algorithmique avanc´ ee

!