MATHEMATIQUES DISCRETES - udsmed.u-strasbg.fr

9 janvier 2007 1

MATHEMATIQUES DISCRETES

Stéphanie FLOSSE

9 janvier 2007 2

Plan

• présentation des mathématiques discrètes

• les enseignements

• programmation linéaire – définition

– l’algorithme du simplexe

– exemple d’application

• théorie du signal : approximation multirésolutions

9 janvier 2007 3

Définition

• Mathématiques discrètes : étude des structures mathématiques fondamentalement discrètes, dans le sens où la notion de continuité n'est pas exigée ou supportée

• Mathématiques discrètes: populaires du fait de leurs applications dans l’informatique. – notations et concepts des mathématiques discrètes utilisés pour

exprimer ou étudier des problèmes et des objets en algorithmique et en programmation

9 janvier 2007 4

Enseignements

• théorie des codes : polynômes sur les corps finis, codes correcteurs

• informatique : programmation C / C++, Java ; arbres, graphes ; base de données

• probabilités

• réseaux

• théorie des jeux –optimisation• théorie du signal : transformation de Fourier, filtres,

convolution, ondelettes,approximation multi-résolutions

9 janvier 2007 5

OPTIMISATION : PROGRAMMATION LINEAIRE

9 janvier 2007 6

Programmation linéaire : exemple, résolution graphique

• Exemple:

24C03Z, intervention sur le cristallin, séjour < 2 j.valeur = 1530,19€

24C04Z, affectation de la CMD 02 avec acte opératoire, séjour < 2 j., valeur = 973,74€

1 chirurgien, 1 infirmière et 1 secrétaire pour ces séjours

24C03Z : 20 min. chirurgien, 30 min. infirmière, 6 min. secr.

24C04Z : 10 min. chirurgien, 40 min. infirmière, 18 min. secr.

9 janvier 2007 7


Chirurgien : disponible au plus 1000 min / semaine

Infirmière : disponible au plus 2000 min / semaine

Secrétaire : disponible au plus 720 min / semaine

x : nb de séjours dans GHM 24C03Z

y : nb de séjours dans GHM 24C04Z

But : déterminer x et y tel que le bénéfice lié à ces séjours et àces contraintes soit maximum.

9 janvier 2007 8


Écriture du PL :

20x + 10y ≤ 1000

30x + 40y ≤ 2000

6x + 18y ≤ 720

Bénéfice = 1530,19x + 973,74y

Résolution graphique :

- trace les droites correspondants aux contraintes aire

- intersection aire et droite bénéfice tq ord. origine soit max

donne le couple (x,y) recherché

9 janvier 2007 9


Écriture du PL :

Pour x = 40 et y = 20 :

Bénéfice max = 80 682,40 €

20x + 10y ≤ 1000

30x + 40y ≤ 2000

6x + 18y ≤ 720

Bénéfice = 1530,19x + 973,74y

9 janvier 2007 10

Programmation linéaire : définitions

• Problème de programmation linéaire (PL), forme canonique :

nn

mnmnm

nn

in

xcxcz

bxaxa

bxaxa

mxxxn

++=

≤++

≤++≥∀

K

K

M

K

K

11

11

11111

1

:objectiffonction laMaximiser

: linéaires scontrainte et 0 i, que tel, variablesSoit

• Problème de programmation linéaire (PL), forme standard :

( )

( )nn

nmnmmmn

nnn

imnn

xcxcz

xaxabx

xaxabx

xxxm

++=

++−=

++−=

≥∀

+

+

++

K

K

M

K

K

11

11

111111

1

:objectiffonction laMaximiser

:est écartsd' variablesdes base la dans redictionnai Le

.0 i, que tellesaires,supplément , variablesSoit

9 janvier 2007 11

Programmation linéaire : méthode du simplexe

• Écriture du PL sous forme standard

21

215

214

213

74,97319,1530

186720

40302000

10201000

xxz

xxx

xxx

xxx

+=

−−=−−=−−=

• Une solution évidente est : ( ) 0zet 720,2000,1000,0,0 ** ==x

74,97319,1530 21 =>= cc

( )5,5097650*19,5301z

420,500,0,0,50 :solution Nouvelle

50choix leoù d'

1203

20050

Augmentons

*

1

1

1

1

1

==

=

≤

≤

≤

x

x

x

x

x

9 janvier 2007 12

Programmation linéaire : méthode du simplexe

32

325

324

321

20

19,1530

2

19,153074,97350*19,1530

10

315420

2

325500

20

1

2

150

xxz

xxx

xxx

xxx

−

−+=

+−=

+−=

−−=

• Le programme s’écrit alors :

( )

( ) ( ) € 682,4 80et vaut 20,40,pour

atteint est maximum le donc négatifs, et de tsCoefficien

8,345863,9908-682,4 80z : et remplaçantEn

682,4 80z120,0,0,20,40 x:solution Nouvelle

20choix leoù d'

28

20

100

Augmentons

21

43

4321

**

2

2

2

2

2

=

−==

=

≤≤≤

xx

xx

xxxx

x

x

x

x

x

9 janvier 2007 13

THEORIE DU SIGNAL :APPROXIMATION

MULTIRESOLUTIONS

9 janvier 2007 14

Théorie du signal : applications

• spatial : imagerie spatiale, compression de données

• téléphone et internet : compression de données, réduction d’echos

• audiovisuel : stockage et compression de données

• industriel : prospection minière et pétrolière

• ponts et chaussées : calcul de déflexion de chaussée

• médical : imagerie médicale et compression de données

9 janvier 2007 15

APPROXIMATION MULTIRESOLUTIONS

niveau fin

niveau grossier

221 aa +

243 aa +

265 aa +

287 aa +

1a 2a 3a 4a 5a 6a 7a 8a

12 aa − 34 aa − 56 aa − 78 aa −

44321 aaaa +++

48765 aaaa +++

2

2143 aaaa −−+

2

6587 aaaa −−+

9 janvier 2007 16


• Suite d’espaces d’approximation emboîtés :

• Supplémentaire permettant de passer de Vj à Vj+1 : Wj

1+⊂ jj VV

jjj WVV ⊕=+1

( ) { }( )

jk

jk1

1jk

111k

1jk

11

22

: écrirepeut On .sur f de projection la Notons

écrirepeut on , de base une Soit

sur projection sa notons , tq

ψϕ

ϕϕ

∑∑

∑∫

∈∈+

+

∈

+++∈

+

++

+=

=

+∞<=ℜ∈

Zk

jk

Zk

jkj

jj

Zk

jkjjZ

jj

dcfP

WfQ

cfPV

VfPffLf•

9 janvier 2007 17


•( ) ( )

( )ondelette.

échelle.d' fonction

appelléefonction

unique uned' dilatées es translatélessont des base de fonctions Les

appellée f unique uned' téeset transla dilatées

lessont échelles sdifférenteaux base de f Les 2

: échelled' changement derelation une vérifiantfonctions les sConsidéron

Zk jj

k

Znn

W

nxhx

∈

∈

°

°−=∑

ψ

ϕϕ

• ( ) ( )( ) ( ) [ ]nnnxhx

kxx

Znn

jj

jk

δϕϕϕϕ

ϕϕ

=−−=

−=

∑∈

(.~,et 2~~~: ladéfinit On .22 Posons 2 duale échelled' fontion

9 janvier 2007 18


• ( )

))) ( )

) { }) ( )( ) 0

2

01

1

de Riesz de base une forme que tellefonction une existe Il

0lim

lim

.)2(.)2((.)

: iéessont vérif suivantes propriétés les si (APM)

uneest espacesd' suite unequ'dit On

V.-nv

VViv

LVViii

VfVfVfii

VVi

V

n

j

j

j

j

j

j

j

jjj

jj

j

ϕϕ

==

ℜ==

∈⇔∈⇔∈⊂

−∞→

+∞→

∞+

−∞=

−+

+

I

U

srésolution-multi ionapproximat

9 janvier 2007 19


• Relations :

( ) ( ) ( ) ( )

( ) ( ) ( ) ( )

( ) ( )1j

n1j

njn1

11

11 1~;~

1

2~~~;2

2~~~;2

+

∈

+

∈∈+

−+

−+

∈∈

∈∈

∑∑∑

∑∑

∑∑

=+=

−=−=

−=−=

−=−=

ϕψϕ

ϕψϕψ

ϕϕϕϕ

Zn

jn

Zn

jn

Zn

jnj

nn

nnn

n

Znn

Znn

Znn

Znn

cdcf

hghg

nxgxnxgx

nxhxnxhx

9 janvier 2007 20


• Reconstruction (transformée en ondelettes inverse) :

( )∑ −−+ +=

kkm

jkkm

jk

jm gdhcc 22

1

2

1

• Calcul de la décomposition en ondelettes :

12

12

~2

1;

~

2

1 +−

+− ∑∑ == j

nn

knj

kj

nn

knj

k cgdchc

9 janvier 2007 21


• Exemple : ondelette de Haar

−

+=

−=+

=

−−+

+++

++

+

pairest si 2

1

impairest si 2

1

:ion Recomposit

;2

:ion décomposit de Schéma

22

2

1

2

1

1

12

112

112

12

mdc

mdc

c

ccdcc

c

jm

jm

jm

jm

jm

jk

jk

jk

jk

jkj

k

9 janvier 2007 22


• Seuillage

0 d alors seuil, d si =<

dddd

dddd

ddcc

ddcc

K

MM

K

K

K

Taux de compression correspond au % de 0 dans la matrice décomposée

9 janvier 2007 23


Image originaleImage décomposée,

38% de zéros

Image recomposée sans seuillage

= image originale

Seuil = 1 ; 86% de zérosA l’œil nu, pas de différences entre l’image reconstruite et

l’image originale

Seuil = 5 ; 97% de zérosMauvaise qualité de l’image reconstruite sur les dégradés.

9 janvier 2007 24


Image originale Image décomposée 9% de zéros

9 janvier 2007 25


Seuil = 2 ; 37% de zérosA l’œil nu, pas de différences entre

l’image reconstruite et l’image originale

Seuil = 7 ; 65% de zérosLe chien a été bien reconstruit, mais dans le fond, apparition de « carrés » à la place du dégradé

9 janvier 2007 26


• Haar :– mauvais sur les dégradés / bon sur les contrastes

– utilisation pour la reconnaissance d’écriture

• Il existe bien d’autres ondelettes :– Morlet, Daubechies, biorthogonales interpolantes, etc.

9 janvier 2007 27

Bibliographie

• Programmation linéaire– Chvatal, Linear Programming

• Ondelettes– cours de M.SONNENDRÜCKER

– S. Mallat, Une exploration des signaux en ondelettes

– I. Daubechies,Ten Lectures on Wavelets

– http://www-lmc.imag.fr/lmc-cf/Valerie.Perrier

– www.python.org

Documents

MATHEMATIQUES DISCRETES - udsmed.u-strasbg.fr