[PDF] [PDF] L3 Info Cours 10 : Algorithmes gloutons Coloration de graphe

View - Download [PDF] L3 Info Cours 10 : Algorithmes gloutons Coloration de graphe

Previous PDF

Next PDF

Algorithmique et Analyse d"Algorithmes

Algorithmique et Analyse d"Algorithmes

L3 Info

Cours 10 : Algorithmes gloutons

Coloration de graphe

Benjamin Wack2021 - 2022

1 / 35

Algorithmique et Analyse d"Algorithmes

La dernière fois

I

Arbre partiellement ordonné

I

Structure de tas

I

Application à la FAP

I

Diviser pour RégnerAujourd"hui

I

Problèmes d"optimisation

I

Algorithmes gloutons

I

Coloration de graphes2 / 35

Algorithmique et Analyse d"Algorithmes

Plan

Problèmes d"optimisation

Algorithmes gloutons

Exemple : le problème de choix des activités

Graphes

Définitions, notations

Manipulation algorithmique

Complexité des algorithmes de graphes

Coloration de graphe

3 / 35

Algorithmique et Analyse d"Algorithmes

Problèmes d"optimisationDéfinition

Un problème d"optimisation a les caractéristiques suivantes : I Une solution est unsous-ensembled"une des données du problème. IIl existe en général plusieurs solutionsadmissibles. IÀ chaque solution (admissible) est associée unevaleur(en général un coût ou un gain). Le problème d"optimisation consiste non seulement à trouver une solution admissible, mais à trouver une solution de valeurminimale(pour un coût) oumaximale(pour un gain).Un exemple : rendu de monnaie I Problème: On dispose de pièces de valeursv1,v2,...(en nombre illimité). On cherche à fournir une somme d"argentSen monnaie. I Solution: une suite de (valeurs de) pièces ayant pour totalS I Meilleure solution: celle utilisant le moins possible de pièces5 / 35

Algorithmique et Analyse d"Algorithmes

Problèmes d"optimisation

Algorithmes gloutonsDéfinition

Il s"agit d"une stratégie particulièrepour résoudre un problème d"optimisation.Algorithme glouton Un algo rithmeglouton est un algo rithmequi construit une telle solution : I élément par élémentsans jamais revenir en arrière I

en se basant sur des considérationslocales.La séquence construite est un optimum global; ses sous-séquences sont

des optimums des sous-problèmes.Il n"existepa stoujours un algo rithmeglouton p ourrésoudre un p roblème

d"optimisation.Il s"agit d"une caractéristique de l"algorithme mais surtout de la structure du problème (notamment c"est impossible s"il existe des optima locaux).7 / 35

Algorithmique et Analyse d"Algorithmes

Problèmes d"optimisation

Algorithmes gloutonsAlgorithme glouton pour le rendu de monnaie

Algorithme glouton

1.

T antque S>0 :

2. Choisir la piè cede plus grande valeur vinférieure àS 3.

Recommencer avec S-v.Exemple correct

S=16 avec pièces de 10, 5, 2, 1 :

I

16-10=6

I 6-5=1 I 1-1=0

3 piècesExemple incorrect

S=16 avec pièces de 9, 8 et 1 :

I

16-9=7

I 7-1=6 I

8 pièces alors que 8+8=16 en 2

pièces8 / 35

Algorithmique et Analyse d"Algorithmes

Problèmes d"optimisation

Algorithmes gloutonsAlgorithme glouton générique

Initialiser un ensembleUtilisables

InitialiserSol:=∅//ensemble vide ou suite vide ou ...

whileSol estincomplète et Utilisab lesn"est pas vide SélectionnerxdansUtilisables//selon critère glouton

ifxcompatible avec Sol //dans certains problèmes //c"est toujours le cas AjouterxàSolifcondition//true ou xincompatible ou ...RetirerxdeUtilisablesRenvoyerSol

9 / 35

Algorithmique et Analyse d"Algorithmes

Problèmes d"optimisation

Algorithmes gloutonsComplexité

Le choix du prochain élément est en principe efficace car il ne considère qu"une partie des données : I logndans une FAP I

1 pour les pièces de monnaie (si leurs valeurs sont préalablement

triées) I ...La complexité de l"algorithme sera en général de la forme

O(n×f(n))

oùf(le coût du choix) est une fonction sub-linéaire.10 / 35

Algorithmique et Analyse d"Algorithmes

Problèmes d"optimisation

Algorithmes gloutonsPreuve de correction

Schéma de preuve générique

Pour la boucle principale, on maintient l"invariant : Il existe une solution optimale dont Sol est un préfixe. La preuve de cet invariant se fait en utilisant les propriétés de l"opération

Sélectionneret de la mise à jour deUtilisables.Lorsqu"il y a plusieurs solutions optimales, il est souvent nécessaire de

faire appel à une propriété " d"échange » :

Supposons que Sol?S une solution optimale

et que le choix glouton ajoute à Sol un élément x??S. Alors il existe un élément y?S\Sol tel que S? {x}\{y}soit une autre solution au moins aussi bonne que S.11 / 35

Algorithmique et Analyse d"Algorithmes

Problèmes d"optimisation

Exemple : le problème de choix des activitésProblème de choix des activités

Énoncé du problème

On dispose d"une salle pouvant être louée pour une durée variable. On choisit parmi un ensemble dendemandes de location celles qui seront acceptées. I Données : les dates de débutdiet de finfide chaque demandei. I Solution optimale = satisfaisant le plus de demandes.CHOIX_ACTIVITES (demandes)

Trier les demandes pardate de fincroissante.

Sol:=∅

dispo:= 0//Première date disponible fori := 1tonifdi≥dispo//demande acceptable InséreridansSoldispo:=fi13 / 35

Algorithmique et Analyse d"Algorithmes

Problèmes d"optimisation

Exemple : le problème de choix des activitésPreuve de l"algorithme glouton On maintient l"invariant :Sol est un préfixe d"une solution optimale. En début d"algorithmeSolest vide, c"est donc un préfixe de toute solution.Supposons qu"au début de laième itérationSolest un préfixe d"une solution optimaleS. I Si l"itération n"ajoute pas de demande àSolalors elle reste un préfixe de la mêmeS. I

Sinon, elle ajoute la demandeiàSol.14 / 35

Algorithmique et Analyse d"Algorithmes

Problèmes d"optimisation

Exemple : le problème de choix des activitésPreuve de l"algorithme glouton (2) On distingue alors trois possibilités sur lapremière demandedeS\Sol:I c"est une demandeki: on montre qu"on peut la remplacer pari.Propriété d"échange Si la première demande deS\Solest une demandek>i, alors T= (S\{k})? {i}est également une solution optimale :I fk≥fidonc la demandeiest compatible avec toutes les autres demandes deS(qui ont des dates postérieures àfk).I

Test de même taille queS.15 / 35

Algorithmique et Analyse d"Algorithmes

Problèmes d"optimisation

Exemple : le problème de choix des activitésUn autre algorithme glouton déjà connu

L"algorithme de Huffman est

glouton

Choix glouton :

tout noeud construit est définitif I Le choix du prochain noeud repose sur le maintien des 2 noeuds de poids minimal. (ne nécessite pas de tous les reparcourir si la file à priorité est implantée dans un tas)Optimalité

À toute itération

la fo rêtc onstruiteest incluse dans un a rbrede co dage optimal Donc l"algorithme de Huffman produit un code optimal.16 / 35

Algorithmique et Analyse d"Algorithmes

Graphes

Définitions, notationsNotions de base

Graphe non orienté

Un graphe non o rienté est un couple G= (X,R): I

Xest l"ensemble dessommets

I

Rest une relation binairesymétriquesurX

(ensemble de couples non ordonnés deX).D G HA EC BIF Sur l"exemple :R={(B,A),(A,C),(C,D),(D,E),(D,F),(D,I),...}18 / 35

Algorithmique et Analyse d"Algorithmes

Graphes

Définitions, notationsVoisinages

Voisin

On appelle

voisin d"un sommet xtout sommetytel que(x,y)(ou de façon équivalente(y,x)) est une arête du graphe.Degré d"un sommet Le degré d"un sommetxest le nombre d"arêtesincidentesàx, autrement dit le nombre de voisins dex.Degré d"un graphe Le degré d"un graphe est le maximum de sdegrés de ses sommets.

19 / 35

Algorithmique et Analyse d"Algorithmes

Graphes

Définitions, notationsÉtiquettes, pondération

Dans un graphe il est possible d"

étiqueter

I les sommets I et / ou les arêtes au moyen d"une fonction deX(respectivement deR) dans un ensemble

d"étiquettes donné.Si les étiquettes sont à valeur numérique (entier, réel...) elles peuvent

représenter un p oids (coût, valeur...) p ourles sommets ou les a rêtes: on parle alors de graphe p ondéré .20 / 35

Algorithmique et Analyse d"Algorithmes

Graphes

Définitions, notationsApplications

I

Réseau (routier, de communication)

I

Calculer un itinéraire

IIdentifier les goulots d"étranglementI

Conflits

I Chaque sommet représente un processus, une activité... IChaque arête représente une compétition pour une ressource IDéterminer le nombre de ressources nécessaires, ou les activités compatiblesI

Dépendances (avec un grapheorienté)

I

Chaque sommet représente une tâche

IL"origine de chaque arc doit être réalisée avant son extrémité IDétecter une incohérence, calculer un ordre appropriéI ...De façon générale toute relation, orientée ou non, se traduit par un graphe qui permet ensuite de raisonner algorithmiquement sur cette relation.21 / 35

Algorithmique et Analyse d"Algorithmes

quotesdbs_dbs29.pdfusesText_35

[PDF] algorithme de coloration de welsh et powell

[PDF] algorithme de coloration de graphe en java

[PDF] coloration des graphes pdf

[PDF] coloration graphe terminale es

[PDF] algorithme de coloration de graphe en c

[PDF] algorithme de coloration de graphe en python

[PDF] coloriage magique avec les puissances correction

[PDF] coloriage numérique isabelle guillot

[PDF] écrire une fraction sous la forme d'un entier et d'une fraction cm2

[PDF] les fractions supérieures ? 1

[PDF] cours cap coiffure la permanente

[PDF] cours coloration cap coiffure

[PDF] boxe anglaise veteran

[PDF] reglement boxe anglaise

[PDF] boxe anglaise technique de base