XXII Table des mati` eres
10.4.3 Formules de caract´ erisations . . . . . . . . . . . . . . . . . . . . . . . . 303
10.5 Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
10.5.1 Balades uniformes sur un carr´ e . . . . . . . . . . . . . . . . . . . . . . 305
10.5.2 Le carr´ e de Sierpinski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
10.5.3 Une marche al´ eatoire vers le carr´ e de Sierpinski . . . . . . . 310
10.5.4 Convergence ` a l’´ equilibre . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
10.6 Fractales sym´ etriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
10.6.1 Les sym´ etries d’un polygone . . . . . . . . . . . . . . . . . . . . . . . . 313
10.6.2 Marches al´ eatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
10.6.3 V´ eg´ etations fractales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
11 Optimisation et Combinatoire ´ enum´ erative . . . . . . . . . . . . . . . . 325
11.1 Description des mod` eles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
11.2 Interpr´ etations de Feynman-Kac-Jarzynski . . . . . . . . . . . . . . . . . 326
11.3 Algorithmes de simulation particulaires. . . . . . . . . . . . . . . . . . . . . 328
11.4 Analyse des performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
11.5 Quelques variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
11.6 Le probl` eme du sac ` a dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
11.6.1 Description du probl` eme combinatoire . . . . . . . . . . . . . . . 335
11.6.2 Quelques strat´ egies d’exploration locale . . . . . . . . . . . . . . 337
11.6.3 Quelques variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
11.7 Organisation optimale multi-crit` eres . . . . . . . . . . . . . . . . . . . . . . . 341
11.8 Le probl` eme d’affectation quadratique . . . . . . . . . . . . . . . . . . . . . . 342
11.9 D´ ecoupage maximal de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . 344
11.10Travaux pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
12 Traitement du signal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
12.1 Filtre de Kalman-Bucy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
12.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
12.1.2 Description du mod` ele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
12.1.3 Les ´ equations du filtrage . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
12.1.4 Le filtre de Kalman-Bucy . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
12.1.5 Une version markovienne ` a rebours . . . . . . . . . . . . . . . . . . 352
12.2 Une introduction au filtrage non lin´ eaire . . . . . . . . . . . . . . . . . . . . 355
12.2.1 Formules int´ egrales de Feynman-Kac . . . . . . . . . . . . . . . . . 355
12.2.2 Les ´ equations du filtrage . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
12.2.3 Les filtres particulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
12.2.4 Filtrage et lissage en termes d’arbres g´ en´ ealogiques . . . . 364
12.2.5 Mod` eles de filtrage approch´ es . . . . . . . . . . . . . . . . . . . . . . . 368
12.3 Filtres de Kalman-Bucy en interaction . . . . . . . . . . . . . . . . . . . . . 371
12.3.1 Description des mod` eles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
12.3.2 Mesures gaussiennes conditionnelles . . . . . . . . . . . . . . . . . . 373
12.3.3 Mesures de Feynman-Kac conditionnelles . . . . . . . . . . . . . 373
12.3.4 Pr´ edicteurs optimaux conditionnels . . . . . . . . . . . . . . . . . . 375
12.3.5 Calcul des vraisemblances conditionnelles . . . . . . . . . . . . . 377
.
.
10.4.3 Formules de caract´ erisations . . . . . . . . . . . . . . . . . . . . . . . . 303
10.5 Quelques exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
10.5.1 Balades uniformes sur un carr´ e . . . . . . . . . . . . . . . . . . . . . . 305
10.5.2 Le carr´ e de Sierpinski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
10.5.3 Une marche al´ eatoire vers le carr´ e de Sierpinski . . . . . . . 310
10.5.4 Convergence ` a l’´ equilibre . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
10.6 Fractales sym´ etriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
10.6.1 Les sym´ etries d’un polygone . . . . . . . . . . . . . . . . . . . . . . . . 313
10.6.2 Marches al´ eatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
10.6.3 V´ eg´ etations fractales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
11 Optimisation et Combinatoire ´ enum´ erative . . . . . . . . . . . . . . . . 325
11.1 Description des mod` eles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
11.2 Interpr´ etations de Feynman-Kac-Jarzynski . . . . . . . . . . . . . . . . . 326
11.3 Algorithmes de simulation particulaires. . . . . . . . . . . . . . . . . . . . . 328
11.4 Analyse des performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
11.5 Quelques variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
11.6 Le probl` eme du sac ` a dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
11.6.1 Description du probl` eme combinatoire . . . . . . . . . . . . . . . 335
11.6.2 Quelques strat´ egies d’exploration locale . . . . . . . . . . . . . . 337
11.6.3 Quelques variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
11.7 Organisation optimale multi-crit` eres . . . . . . . . . . . . . . . . . . . . . . . 341
11.8 Le probl` eme d’affectation quadratique . . . . . . . . . . . . . . . . . . . . . . 342
11.9 D´ ecoupage maximal de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . 344
11.10Travaux pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
12 Traitement du signal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
12.1 Filtre de Kalman-Bucy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
12.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
12.1.2 Description du mod` ele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
12.1.3 Les ´ equations du filtrage . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
12.1.4 Le filtre de Kalman-Bucy . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
12.1.5 Une version markovienne ` a rebours . . . . . . . . . . . . . . . . . . 352
12.2 Une introduction au filtrage non lin´ eaire . . . . . . . . . . . . . . . . . . . . 355
12.2.1 Formules int´ egrales de Feynman-Kac . . . . . . . . . . . . . . . . . 355
12.2.2 Les ´ equations du filtrage . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
12.2.3 Les filtres particulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
12.2.4 Filtrage et lissage en termes d’arbres g´ en´ ealogiques . . . . 364
12.2.5 Mod` eles de filtrage approch´ es . . . . . . . . . . . . . . . . . . . . . . . 368
12.3 Filtres de Kalman-Bucy en interaction . . . . . . . . . . . . . . . . . . . . . 371
12.3.1 Description des mod` eles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
12.3.2 Mesures gaussiennes conditionnelles . . . . . . . . . . . . . . . . . . 373
12.3.3 Mesures de Feynman-Kac conditionnelles . . . . . . . . . . . . . 373
12.3.4 Pr´ edicteurs optimaux conditionnels . . . . . . . . . . . . . . . . . . 375
12.3.5 Calcul des vraisemblances conditionnelles . . . . . . . . . . . . . 377
.
.