INFO-4xx-ALG1-resume de cours

INFO-4xx-ALG1-resume de cours

Documents
10 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

IF4-ALG1 : AlgorithmiqueR´esum´e de coursBastien Leblanc7 janvier 2003Table des mati`eres1 Algorithmes gloutons 21.1 Proc´edure globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Arbre de poids minimum (Kruskal 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Matro¨ıdes 32.1 D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Matro¨ıde pond´er´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3 Algorithme glouton associ´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Op´erateurs Morphologiques de base 43.1 d´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.2 le dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.3 Enveloppe Convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.4 Propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.5 El´ement structurant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.6 Erosion et dilatation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.7 Ouverture et fermeture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53.8 Dilatation G´eod´esique . . . . . . . . . . . ...

Sujets

Informations

Publié par
Nombre de visites sur la page 78
Langue Serbian
Signaler un problème

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 si x∈
x ∈ X est un point Nord (respectivementn-simple pour X∪{x}.
Sud,Est,Ouest) si x a un voisin nord (respective-2On dit que X et Y⊂ sont homotopes
ment S,E,O) qui appartient `a X2Proposition : x∈ est n-simple pour X⇔ x est
Algo :n-simple.
2 – A chaque it´eration on consid`ere les points deSoit X ⊂ , Y ⊂ X est un noyau homotopique
type N (respect. S,E,O)de X si :
– On enl`eve tous les points simple non extr´emit´e
(en parall`ele)1. Y est sous homotope a` X.
– On r´eit`ere jusqu’a stabilit´e.
2. ∀x∈Y, x est non n-simple. 2Complexite : X ⊂I(n∗n)N =n
31 it´eration : o(N)⇒ au maximum o(n ).
On dit que x∈X est un point n-extr´emit´e pour X
si|Γ(x)∩X| = 1.
5.2 Nombre topologique
2 2Soit x∈ , et X ⊂ , on d´efinit le nombre
topologique :
T (x,X) = Nombre de composantes n-connexes den
∗Γ (x)∩X qui sont n-voisins de x.8
Propositions :
x∈δ(x)⇔T > 0 (Point du bord)
x est un point int´erieur⇔T = 0
7
ZZZZZZChapitre 6
Diviser pour r´egner
6.1 Algorithme g´en´eral trifusion(U); trifusion(V)
fusionner(T,U,V)
fonction RP(x) (retournelasolutiondel’exem-
ncomplexit´e : t(n) =t( )+c∗n⇒o(n∗logn)plaire x) 2
1. Si x est petit ou simple retourner ADHOC(x)
6.4 Transform´ee de Fourier2. Sinon d´ecomposer x en k exemplaires
x ,x ,...x1 2 k rapide
3. Pour i=1 `a k faire y :=RP(x )i
pOn suppose n=24. fusionner les y pour obtenir une solution y `ai
TFR(a)x
n :=longueur(a)
5. retourner y.
si n=1, alors retourner a
2πi
nω :=1;ω =en
0 1a := (a ,a ,...,a );a := (a ,a ,...,a )0 2 n−2 1 3 n−16.2 fouille dichotomique 0 0 1y :=TFR(a ); y :=TFR(a );
nPour k=0 a` −1 faireTri classique : 2
0 1y :=y +ωyk k kfonction dich(T[1,...,n],x)
0 1y :=y −ωyk+n/2 k k– si n=0 et x¡T[1] alors retourner 0
ω :=ω∗ωn– sinon retourner rechdich(T,x)
fin pourfonction rechdich(T[i,j],x)
retourner y– si i=j alors retourner i
ncomplexit´e : t(n) = 2t( )+c∗n⇒o(n∗logn)– k := (i+j +1)/2 2
– si x<T(k) alors retourner rechDich(T[i,k],x) 6.4.1 Transform´ee de fourier inverse
rapide
– sinon retourner rechdich(T[k,j],x)
−1Il suffit de remplacer a par y et ω par ω dansn n
n l’algorithme de TFR.complexit´e : t(n) =t( )+c⇒o(logn)2
6.3 Tri par fusion
Algorithme :
proc´edure trifusion(T[1...n])
si n=1 alors retourner T[1...n]
n n+1cr´eer tableaux U[1... ] et V[1... ]2 2
nU :=T[1... ]2
nV :=T[1+ ...n]2
8Chapitre 7
Polynˆomes
7.1 Repr´esentation par coefficients
Pn−1 jOn dit qu’un polynˆome A est repr´esent´e par ses coefficients si on connait A(x) = a xjj=0
Evaluation de A(x ) : on a A(x ) =a +x [a +x [a +x [...]]] Cet algorithme est en o(n)0 0 0 0 1 0 2 0
7.2 Repr´esentation par valeurs
C’est un ensemble de n points du plan repr´esent´e par leurs coordonn´ees :
{(x ,y ),(x ,y ),...,(x ,y )}0 0 1 1 n−1 n−1
Proposition : Une r´epresentation par valeurs d´etermine un polynˆome unique :
Formule de Lagrange :
Qn−1X (x−x )jj=k
QA(x) = y ∗ =y (7.1)k p
(x −x )k jj=kk=0
2Passage de la repr´esentation par coefficients a` celle par valeurs en o(n ). Addition et multiplication en
o(n).
7.3 multiplication rapide de polynˆomes
1. doubler leur borne (o(n)) : on ajoute n coefficients nuls
2. ´evaluer(o(nlog(n))) : on calcul des repr´esentations par valeur de A et B en appliquant la TF d’ordre
eme2n (valeurs des polynomeˆ s sur les racines (2n) de l’unit´e
3. multiplication point `a point (o(n))
−14. repr´esentation par coefficient (o(nlog(n))) : avec TF
Complexit´e : o(nlog(n)).
9
66