Introduction à la complexité algorithmique

1 Introduction la complexit algorithmique par ric TRICHET. Int grateur TICE au Centre de Ressources et d'Innovation P dagogiques de l'Universit de Limoges Remerciements Je tiens remercier messieurs Abdelkader NECER et St phane VINATIER pour leurs conseils et m'avoir donn l'occasion de publier ce travail. Merci aussi leur coll gue pour sa relecture et ses remarques. Licence Ce document est sous la licence Creative Commons. This document is licensed under the Attribution-NonCommercial-ShareAlike France license, available at Abr viation(s). RAM : Random Access Machine machine acc s al atoire Prologue Ce document est la base un m moire pr sent en vue d'obtenir l'UE Information et communication pour ing nieur Sp cialit : INFORMATIQUE du Conservatoire National des Arts et M tiers de Limoges.

2 Il a t soutenu le 19/06/2009 devant un jury compos de JURY Mme lisabeth METAIS. (pr sidente), M. Jean-Michel DURCE et M. Philippe JEULIN. Je tiens remercier M. Philippe JEULIN pour les conseils qu'il m'a prodigu s pour la cr ation de ce m moire. Introduction la complexit algorithmique Page ii Pr face Introduction la complexit algorithmique Page iii Glossaire des termes techniques algorithme proc dure de calcul bien d finie qui prend en entr e une valeur, ou un ensemble de valeurs, et qui donne en sortie une valeur, ou un ensemble de valeurs. Un algorithme est donc une s quence d' tapes de calcul qui transforment l'entr e en sortie. algorithme l'inverse d'un algorithme na f (complexit exponentielle) et par praticable, convention, un algorithme est dit praticable, efficace s'il est polynomial.

3 Efficace axiome d signe une v rit ind montrable qui doit tre admise. classe L L est l'ensemble des probl mes pour lesquels il existe un algorithme de r solution en temps logarithmique en fonction de la taille des entr es. classe NP la classe NP (probl mes Non-d terministes Polynomiaux) est l'ensemble des probl mes qui peuvent tre r solus sur une machine non d terministe en temps polynomial en fonction de la taille des entr es. classe P P est l'ensemble des probl mes pour lesquels il existe un algorithme de r solution en temps polynomial en fonction de la taille des entr es. complexit d'un la complexit d'un algorithme est le nombre d'op rations l mentaires algorithme qu'il doit effectuer pour mener bien un calcul en fonction de la taille des donn es d'entr e.

4 Complexit d'un la complexit d'un probl me A est la complexit du meilleur algorithme probl me qui r sout A . complexit soit A un algorithme, n un entier, D n l'ensemble des entr es de taille dans le meilleur n et une entr e d Dn . Posons : co t A d le nombre d'op rations des cas fondamentales effectu es par A avec l'entr e d . La complexit dans le meilleur des cas est obtenue par : Min A n =min {co t A d /d Dn } . complexit soit A un algorithme, n un entier, D n l'ensemble des entr es de taille dans le pire des n et une entr e d Dn . Posons : co t A d le nombre d'op rations cas fondamentales effectu es par A avec l'entr e d . La complexit dans le pire des cas est donn e par : Max A n =max {co t A d / d D n}.

5 / . Introduction la complexit algorithmique Page iv complexit en soit A un algorithme, n un entier, D n l'ensemble des entr es de taille moyenne n et une entr e d Dn . Posons : co t A d le nombre d'op rations fondamentales effectu es par A avec l'entr e d . La complexit en moyenne est donn e par : Moy A n = p d . co t A d . d Dn avec p d une loi de probabilit sur les entr es. corps de la ensemble des instructions comprises l'int rieur de la boucle (par boucle exemple entre le Faire et Jusqu' ). dichotomie la dichotomie ( couper en deux en grec) est, en algorithmique , un processus it ratif ou r cursif de recherche o , chaque tape, l'espace de recherche est restreint l'une des deux parties.

6 Efficacit d'un on consid re g n ralement qu'un algorithme est plus efficace qu'un algorithme autre si son temps d'ex cution du cas le plus d favorable a un ordre de grandeur inf rieur. file structure de donn es bas e sur le principe Premier arriv , premier servi ! en anglais FIFO (First In, First Out). fonctions Soient f et g deux fonctions d finies sur une partie des nombres quivalentes r els. f et g sont quivalentes si f ( x )=g ( x)(1+ (x )) avec xlim + . (x )=0 . C'est not : f ~g instance un exemple sp cifique du probl me : une configuration particuli re des villes pour le probl me du voyageur de commerce, un arbre particulier pour un probl me de graphe. C'est une entr e particuli re pour un algorithme.

7 Limite soit f une fonction . Nous disons que la limite de f x quand x tend vers est gale L si > 0, S tels que x> S , f ( x) L < . lim f x =L. On note : x . machine non- une machine non-d terministe est une variante purement th orique : on d terministe ne peut pas construire de telle machine. chaque tape de son calcul, cette machine peut effectuer un choix non-d terministe : elle a le choix entre plusieurs actions, et elle en effectue une. Si l'un des choix l'am ne accepter l'entr e, on consid re qu'elle a fait ce choix-l . En quelque sorte, elle devine toujours juste. Une autre mani re de voir leur fonctionnement est de consid rer qu' chaque choix non-d terministe, elles se d doublent, les clones poursuivent le calcul en parall le suivant les branches du choix.

8 Si l'un des clones accepte l'entr e, on dit que la machine accepte l'entr e. / . Introduction la complexit algorithmique Page v machine les machines d terministes font toujours un seul calcul la fois. Ce calcul est d terministe constitu d' tapes l mentaires ; chacune de ces tapes, pour un tat donn de la m moire de la machine, l'action l mentaire effectu e sera toujours la m me. o (petit o) soit g une fonction d finie de + dans + . L'ensemble o g est d fini ainsi : o( g )={ f fonction d fine de + dans + /. c> 0, n 0 tels que x n0 , 0 f ( x )< c g (x) }. O (grand O) soit g une fonction d finie sur une partie des nombres r els. L'ensemble O( g ) est d fini ainsi : O (g )={ f fonction d finie sur une partie de /.}

9 C >0, n0 tels que x n0 , f ( x ) c g ( x) }. pile structure de donn es fond e sur le principe dernier arriv , premier sorti (ou LIFO pour Last In, First Out). probl me NP - un probl me est NP - complet s'il appartient NP et qu'il est NP - difficile. complet probl me NP - un probl me Q est dit C - difficile si ce probl me est au moins aussi difficile difficile que tous les probl mes dans C -d. que tout probl me de C peut tre r duit Q par un algorithme polynomial. profilage le pro ling d'un programme permet d'identifier les endroits o celui-ci passe le plus de temps, mais galement quelles sont les fonctions qui sont ex cut es et combien de fois. Un pro ler est un programme capable d'analyser un ex cutable.

10 Le r sultat de l'analyse est appel un profile (ou profilage). r duction de la r duction d'un probl me P 1 vers un probl me P 2 est une transformation probl mes de toute instance de P 1 en une instance de P 2 , de sorte que toute solution . P 1 puisse induire une solution P 2 . Cette transformation doit tre polynomiale en temps et en m moire selon la taille de P 1 . Ainsi il y a une relation de difficult de r solution entre ces deux probl mes. soit g une fonction d finie sur une partie des nombres r els. L'ensemble g est d fini ainsi : (g )= { f fonction d finie sur une partie de / c1 >0 et c 2 >0, n0 . tels que n n 0 , 0 c 1 g ( n) f (n) c 2 g (n) }. soit g une fonction d finie sur une partie des nombres r els.