Algorithmique Avancée Introduction PDF [PDF]

Zitiervorschau

Algorithmique avancée A. Mouloudi

Table des matières Introduction Chap 1: Complexité algorithmique Chap 2: Arbre Binaire Arbre Binaire de Recherche (ABR) Les Arbres Equilibrés Les B Arbres

Chap 3 : Graphes Eléments de la théorie des graphes Le problème du plus court chemin Flots dans les réseaux 2

Master: Génie informatique

Table des matières Chap 4 : Programmation linéaire  Résolution graphique  Méthode du simplexe

Chap 5 : Décidabilité  Machine de Turing  Décidabilité  Classes de complexité

3

Master: Génie informatique

Table des matières  NP-Complétude o 3-SAT o Clique o Couverture par les sommets o Circuit hamiltonien o Coloration de graphes

Chap 6 : Algorithmes d’approximation  Vertex cover 

Voyageur de commerce (TSP)

 Bin Packing  2-Partition 4

Master: Génie informatique

Introduction L’algorithmique est une science apparue, il y a très longtemps, bien avant l’idée même d’ordinateur. Citons, vers 1800 avant J-C, les babyloniens

de l’époque d’Hammurabi formulant des règles précises pour la résolution de certains types d’équations. 5

Master: Génie informatique

Introduction Plus tard, au 3ème siècle avant J-C, chez les grecs, fleurissent un grand nombre de procédés de calcul, dont le célèbre « algorithme d'Euclide ». En Perse, au 9ème siècle après J-C, on trouve l’origine du mot « algorithme », qui provient du nom de Abu Ja'far Mohammed Ibn Mûsâ Al-Khowâ-

rismi. 6

Master: Génie informatique

Introduction Al-Khowâ-rismi,

a

écrit

un

ouvrage

d’arithmétique utilisant les règles de calcul sur la représentation décimale des nombres, et montra l’inutilité des tables et abaques. Il eut

une influence capitale pendant plusieurs siècles. 7

Master: Génie informatique

Introduction Au fil du temps, la signification du mot s’élargit et finalement vient à désigner tout procédé de calcul

systématique,

voire

automatique,

mais

sans

référence nécessaire à une machine.

Côté informatique du 21ème siècle et en première approche, on peut dire qu'un algorithme est un

« mode d'emploi pour résoudre un problème ». 8

Master: Génie informatique

Introduction Un algorithme est un procédé de calcul

automatique composé d’un ensemble fini d’étapes, chaque étape étant formée d’un

nombre fini d’étapes élémentaires, qui permet de résoudre le problème en donnant la sortie requise. 9

Master: Génie informatique

Introduction Chaque étape élémentaire est : définie de façon rigoureuse et non ambiguë

 effective, c-à-d, pouvant être réalisée par une machine

De plus, l’algorithme doit toujours terminer après un nombre fini d’opérations, quelle que soit la donnée

en entrée, et fournir un résultat. 10

Master: Génie informatique

Introduction Quels sont les types de problème susceptibles d’être résolus par des algorithmes ? Les applications concrètes des algorithmes sont innombrables, entre autres : – L’Internet permet à des gens éparpillés un peu partout dans le monde d’accéder rapidement à toutes sortes de données. Tout cela repose sur des algorithmes intelligents qui permettent de gérer et manipuler de grosses masses de données.

Introduction – Le commerce électronique permet de négocier et échanger, de manière électronique, biens et services. Le commerce électronique exige que l’on préserve la confidentialité de données telles que numéros de carte de crédit, mots de passe et relevés bancaires. La cryptographie à clé publique et les signatures numériques qui font partie des technologies fondamentales employées dans ce contexte, s’appuient sur des algorithmes numériques et sur la théorie des nombres.

Introduction - Dans l’industrie et le commerce, il faut souvent optimiser

l’allocation de ressources limitées. Une compagnie pétrolière veut savoir où placer ses puits de façon à maximiser les profits escomptés. Un candidat à la présidence veut savoir dans quels supports publicitaires il doit investir pour maximiser ses chances d’élection. Une compagnie aérienne désire réaliser l’affectation des équipages aux vols de telle façon que les coûts soient minimisés, les vols assurés sans défaillance et la législation respectée. Un fournisseur de services Internet veut savoir où placer des ressources supplémentaires pour desservir ses clients de manière plus efficace. Ces exemples de problèmes peuvent être résolus par la programmation linéaire, que nous étudierons dans un chapitre.

Introduction Les

algorithmes

que

nous

considérons

sont

déterministes : toute exécution de l’algorithme sur les mêmes données donne le même résultat. À tout algorithme écrit en langage naturel ou pseudo-code, on peut associer un programme implémentant l’algorithme.

14

Master: Génie informatique

Introduction Ce programme écrit avec des règles syntaxiques rigoureuses et destiné à être compris par une machine. Il se pose alors le problème de trouver le bon degré

de précision nécessaire pour définir l’algorithme: il doit être suffisant pour permettre d’écrire un programme lui correspondant et pour calculer sa

complexité. 15

Master: Génie informatique

Introduction Il est à noter qu’à tout problème ne correspond pas nécessairement un algorithme permettant de le résoudre : problème indécidable, tel que le problème de la diagonalisation de Cantor ou l’arrêt de la machine de Turing (il est démontré qu’il ne

peut pas exister d’algorithme général , qui pour tout programme P, et toute donnée D, répondrait oui ou

non à la question « P termine-t-il pour D ? »). 16

Master: Génie informatique

Introduction On parle aussi de fonction non calculable. En effet,

vers 1930, avant la construction des premiers ordinateurs,

plusieurs

mathématiciens

(Gödel,

Church, Turing, Post) ont formalisé le concept d’algorithme,

ou

de

fonction

calculable,

par

différents modèles abstraits à ressources infinies (machines de Turing, fonctions récursives, λ-calcul). 17

Master: Génie informatique

Introduction En

conséquence,

si

un

algorithme

est

implémentable dans un langage (ou modèle) donné, en C par exemple, alors il est forcément implémentable dans un autre et des transcriptions

d’un langage dans un autre sont possibles (thèse

de Church).

18

Master: Génie informatique

Introduction On

peut

décrire

indépendamment

du

un

algorithme

langage

de

programmation (et de la machine sur laquelle sera exécuté le programme) et si l’on n’utilise que des pas raisonnables,

l’algorithme est implémentable dans tout langage. 19

Master: Génie informatique

Introduction Ce qui nous intéresse, étant donné un problème, est de trouver le "meilleur " algorithme. Pour cela,

on va comparer des algorithmes qui ont la même spécification. Ce que l’on veut pouvoir dire :

« Sur toute machine, quel que soit le langage de programmation, l’algorithme A1 est meilleur que

l’algorithme A2 pour les données de grande taille. » 20

Master: Génie informatique

Introduction Il faut donc évaluer les ressources nécessaires pour réaliser l’algorithme : place mémoire et temps

d’exécution. Attention avec les algorithmes récursifs, il peut y avoir de la place mémoire utilisée pour la création de la pile. Il faut trouver un juste compromis entre espace et

temps. On peut parfois gagner du temps mais c’est au détriment de la place, et réciproquement. 21

Master: Génie informatique

Introduction Un algorithme peut être préféré à un autre pour sa

clarté et sa lisibilité (produit de 2 matrices), même s’il est moins performant. Certains algorithmes ne sont pas performants en

général,

mais

peuvent

l’être

pour

certaines

configurations de données. Par exemple, si on sait que les données d’une liste sont presque triées, le tri par insertion est intéressant. 22

Master: Génie informatique