INFO-4xx-ALG1-resume de cours

Informations

• Publié par: Siop
• Nombre de lectures: 78
• Langue: Serbian

Extrait

IF4-ALG1 : Algorithmique
R´esum´e de cours
Bastien Leblanc
7 janvier 2003Table des mati`eres
1 Algorithmes gloutons 2
1.1 Proc´edure globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Arbre de poids minimum (Kruskal 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Matro¨ıdes 3
2.1 D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Matro¨ıde pond´er´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Algorithme glouton associ´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 Op´erateurs Morphologiques de base 4
3.1 d´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 le dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.3 Enveloppe Convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.4 Propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.5 El´ement structurant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.6 Erosion et dilatation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.7 Ouverture et fermeture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.8 Dilatation G´eod´esique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4 Transformation de voisinage et de distance 6
4.1 Transformation de voisinage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.2 Tr de distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.3 Algorithme parall`ele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.4 s´equentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.5 Axe M´edian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5 Topologie 7
5.1 Homotopie - Point simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.2 Nombre topologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.3 Algorithme de squelettisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6 Diviser pour r´egner 8
6.1 Algorithme g´en´eral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.2 fouille dichotomique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3 Tri par fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.4 Transform´ee de Fourier rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
7 Polynˆomes 9
7.1 Repr´esentation par coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2 Repr´esentation par valeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.3 multiplication rapide de polynˆomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1Chapitre 1
Algorithmes gloutons
1.1 Proc´edure globale
x =x ;π ={x }i 0 0
Tant que x n’appartient pas `a B faire :
choisir yΓ(x) tel que h(y) = min (h(y))yΓ(x)
π =π.y
x =y
fin tant que
1.2 Arbre de poids minimum (Kruskal 1)
−→
A = 0;i = 1
−→
Tant que A =E−1 faire
−→
Si A ∪{u} ne contient pas de cyclei
−→ →−
alors faire A = A ∪{u}i
i =i+1
fin tant que
2
6Chapitre 2
Matro¨ıdes
Un matro¨ıde est un couple (M,F) ou` :
1- M est ensemble fini
2- F est une famille de sous-ensemble de M appel´es sous ensembles ind´ependants, tel que :
∀f ∈F,∀h⊂f,h∈F (propri´et´e d’h´er´edit´e)
3-∀f,h∈Fsi|Fk<kHk, alors
∃x∈h, tel que f∪{x}∈F (propri´et´e d’´echange)
2.1 D´efinitions
Soit f ∈F, on dit que x∈M est une extension de f si f∪{x}∈F
On dit que f ∈F est maximal si f ne poss`ede aucune extension.
Tous les ensembles ind´ependants maximaux de M sont de mˆeme cardinalit´e.
2.2 Matro¨ıde pond´er´e
+∗Un matro¨ıde pond´er´e est un matro¨ıde avec une application w :M −→< .
P
∀f ⊂M, on d´efinit w(f) = w(x).
On dit que f est optimal si w(f) est maximal.
2.3 Algorithme glouton associ´e
Glouton (M(M,F),w)
1- F =∅
2- trier M par ordre de poids d´ecroissants
3- Pour chaque x∈M pris par ordre de poids d´ecroissants w(x)
3’- sif∪{x}∈F, alors f =f∪{x}.
fin pour
4- Retourner f.
Complexit´e : o(n∗logn+n∗f(n)).
3Chapitre 3
Op´erateurs Morphologiques de base
3.1 d´efinition Γ croissant⇔∗Γ est croissant
E, un ensemble quelconque
X ⊂E
X ={x∈E;x∈/ X} 3.5 El´ement structurant
P(E) ={X ⊂E}
Un op´erateur est une application : Γ :E→P(E)
−1 −1P(E)→P(E) Sym´etriquedeP:Γ telque:y∈ Γ ⇔x∈ Γ(y)
−1X ⊂E→ Γ(X)⊂E Γ est sym´etrique si Γ = Γ
Γ est r´eflexif si∀x∈E,x∈ Γ(x)
x est l’origine de Γ(x)
3.2 le dual
Le dual d’un op´erateur Γ est l’op´erateur ∗Γ tel
que : 3.6 Erosion et dilatation
∀X ⊂E;∗Γ(X) = Γ(X)
3.6.1 Dilatation
S
∀x⊂E,Γ(x) = Γ(x) =X⊕Γ
X⊕Γ est le dilat´e de X par Γ3.3 Enveloppe Convexe
on a :S
ec(X) = {xy;x∈X,y∈X}
3.6.2 Erosion
ou : S
Xborne,ec(X) = {xy;xety∈∂X} ∀x⊂E,(X⊕Γ) =XΓ
XΓ est l’´erod´e de X par Γ.
3.4 Propri´et´es
3.6.3 Propositions
On dit que
−1∀X ⊂E,X⊕Γ ={x∈E,Γ (x)∩X =∅}Γ est extensif si∀X ⊂E,X ⊂ Γ(X)
−1∀X ⊂E,XΓ ={x∈E,Γ (x)⊂X}Γ est antiextensif si∀X ⊂E,Γ(X)⊂X
∀X ⊂E,X⊕(Γ ∪Γ ) = (X⊕Γ )∪(X⊕Γ )1 2 1 2Γ est croissant si ∀X,Y ⊂ E,X ⊂ Y ⇒ Γ(X) ⊂
∀X ⊂E,X(Γ ∪Γ ) = (XΓ )∩(XΓ )1 2 1 2Γ(Y)
Γ est d´ecroissant si ∀X,Y ⊂ E,X ⊂ Y ⇒ Γ(Y)⊂
Γ(X)
Γ est idempotent si∀X ⊂E,Γ◦Γ(X) = Γ(X) 3.6.4 D´efinition
Propositions : Γ ⊕Γ estun´el´ementstructuranttelque:∀X ⊂1 2
Γ extensif⇔∗Γ est antiextensif E,(Γ ⊕Γ )(x) = Γ (x)⊕Γ1 2 1 2
4
63.6.5 Propositions
∀X ⊂E,X⊕(Γ ⊕Γ ) = (X⊕Γ )⊕Γ1 2 1 2
∀X ⊂E,X(Γ Γ ) = (XΓ )⊕Γ1 2 1 2
3.7 Ouverture et fermeture
3.7.1 d´efinition
On appelle ouverture (par Γ) l’op´erateur sur E
tel que :
−1X ⊂E−→ (XΓ )⊕Γ =XΓ
On appelle fermeture (par Γ) le dual de l’ouver-
ture tel que :
ΓX ⊂E−→ (X)
3.7.2 Propositions
S
∀X ⊂E,X = Γ(X)Γ Γ(X)⊂X
Γ −1∀X ⊂E,X = (X⊕Γ )Γ
X −→ X est anti-extensive, crois-Γ
sante,idempotente.
ΓX −→X est extensive, croissante,idempotente.
3.8 Dilatation G´eod´esique
La dilatation g´eod´esique par Γ dans Y est
l’op´erateur :
X ⊂E−→ (X⊕Γ)∩Y =D (X;Y)Γ
La reconstruction par Γ dans Y est l’op´erateur
qui a` chaque X ⊂ E associe le r´esultat de l’appli-
cation de la dilatation g´eod´esique r´ep´et´e jusqu’a
stabilit´e : R (X,Y).Γ
5Chapitre 4
Transformation de voisinage et de
distance
4.1 Transformation de voisi- 1. On balaye l’image au sens vid´eo
Ψ(x) =Min [Ψ(y)+1] si x∈Xy∈Γ (x)1nage
Ψ(x) = 0 sinon
2. On balaye l’image en sens vid´eo inverse.- E,Γ ´element structurant r´eflexif
0k Ψ (x) =Min [Ψ(x),Ψ(y)+1]-∀X ⊂E,Ψ (x,X) =Min{k∈ ;x∈X⊕Γ }Γ y∈Γ (x)2
0 0On d´efinit Γ =∀x∈E,Γ ={x}
4.5 Axe M´edian
4.2 Transformation de dis-
4.5.1 Boule maximaletance
Soit X ⊂ E, on dit qu’une boule B (x,ρ) estd
X ⊆ E,∀x ∈ E,Ψ (x,X) = Min{d(x,y);∀y ∈ maximale (pour X) sid
X} B (x,ρ)⊂X etd
0 0∀B (y,ρ ) si B (x,ρ)⊂ B (y,ρ )⊂ X alors x = yd d d
0et ρ =ρ
4.3 Algorithme parall`ele
4.5.2 Axe m´edianAlgorithme de Bellman de plus court chemin
avec Π(x) =Min [Π(y)+l(y,x)]y∈Γ(x) Soit X ⊂E, l’axe m´edian de X est l’ensemble :
AM(X) ={x∈X;∃B (x,ρ) maximale}Algo Ψ// d
2(donn´ees X ⊂I ⊂ ,Ifini)
(r´esultat : Ψ(x) = Ψ (x,X)d 4.5.3 Reconstruction de l’objet8
∀x∈I, faire :Ψ(x) = 0 si x∈I X
On peut reconstituer l’objet a` partir de l’axeΨ(x) =∞ si x∈X
m´edian :Tant que S
X = {B (x,ρ);(x,ρ)∈AM(x)}d∀x∈I, faire Ψ(x) =Min [Ψ(y)+1]y∈Γ (x)8
Pour calculer AM(X) on a la formule :Jusqu’`a stabilit´e.
x∈AM(X)⇐⇒∀y∈ Γ (x),Ψ (x,X)≥ Ψ (y,X)8 d dFin tant que.
4.4 Algorithme s´equentiel
X X X
Γ = X1
Γ = X2
X X X
6
NZChapitre 5
Topologie
5.1 Homotopie - Point simple 5.3 Algorithme de squelettisa-
tion
2Soit x∈ , (n,n)
Soitx∈X,onditquexestn-simplesi”onpeuten- Y est un squelette de X si Y est un noyau
leverxde Xsans changerde topologiede XetdeX homotopique de X.
1. X et X\{x} ont la mˆeme nombre de compo-
5.3.1 Technique de la sous-maillesantes n-connexes
On divise la maille carr´ee en 4 sous-mailles. A
2. X et X∪{x} ont la mˆeme nombre de compo-
chaque it´eration, on ne consid`ere que les points
santes n-connexes
d’une mˆeme sous-maille. (cf. cours pour exemples)
On dit que Y est sous-homotope `a X si on peut
obtenir Y `a partir de X en d´etruisant de fa¸con
it´erative des points n-simples de x. 5.3.2 Strat´egie directionelle
Soit x ∈ X, on dit que x est simple pour X