XVI
Table des mati` eres
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
11 Compression d’images par fonctions it´ er´ ees . . . . . . . . . . . . . . . . . . . . . . . . 335
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
11.2 Les transformations affines du plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
11.3 Les syst` emes de fonctions it´ er´ ees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
11.4 It´ eration d’une contraction et point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
11.5 La distance de Hausdorff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
11.6 La dimension des attracteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
11.7 Une photographie comme attracteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
11.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
12 Compression d’images : le standard JPEG . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.2 Un zoom sur une photographie num´ erique en format JPEG . . . . . . . . . 382
12.3 Le cas du carr´ e de 2 × 2 pixels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
12.4 Le cas du carr´ e de N × N pixels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
12.5 Le standard JPEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
12.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
13 L’ordinateur ` a ADN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
13.2 Le probl` eme du chemin hamiltonien r´ esolu par Adleman . . . . . . . . . . . . 418
13.3 Machines de Turing et fonctions r´ ecursives . . . . . . . . . . . . . . . . . . . . . . . . 421
13.3.1 Le fonctionnement d’une machine de Turing . . . . . . . . . . . . . . . . . 421
13.3.2 Fonctions primitives r´ ecursives et fonctions r´ ecursives . . . . . . . . 428
13.4 Les machines de Turing et les syst` emes d’insertion–d´ el´ etion . . . . . . . . . 439
13.5 Les probl` emes NP-complets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
13.5.1 Le probl` eme du chemin hamiltonien . . . . . . . . . . . . . . . . . . . . . . . . 443
13.5.2 Le probl` eme de la satisfaisabilit´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
13.6 Retour sur les ordinateurs `
a ADN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
13.6.1 Probl` eme du chemin hamiltonien et insertion–d´ el´ etion . . . . . . . . 447
13.6.2 Les limites actuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
13.6.3 Quelques explications biologiques sur la r´ eplication des bases . . 450
13.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
Table des mati` eres
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
11 Compression d’images par fonctions it´ er´ ees . . . . . . . . . . . . . . . . . . . . . . . . 335
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
11.2 Les transformations affines du plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
11.3 Les syst` emes de fonctions it´ er´ ees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
11.4 It´ eration d’une contraction et point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
11.5 La distance de Hausdorff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
11.6 La dimension des attracteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
11.7 Une photographie comme attracteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
11.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
12 Compression d’images : le standard JPEG . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.2 Un zoom sur une photographie num´ erique en format JPEG . . . . . . . . . 382
12.3 Le cas du carr´ e de 2 × 2 pixels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
12.4 Le cas du carr´ e de N × N pixels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
12.5 Le standard JPEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
12.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
13 L’ordinateur ` a ADN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
13.2 Le probl` eme du chemin hamiltonien r´ esolu par Adleman . . . . . . . . . . . . 418
13.3 Machines de Turing et fonctions r´ ecursives . . . . . . . . . . . . . . . . . . . . . . . . 421
13.3.1 Le fonctionnement d’une machine de Turing . . . . . . . . . . . . . . . . . 421
13.3.2 Fonctions primitives r´ ecursives et fonctions r´ ecursives . . . . . . . . 428
13.4 Les machines de Turing et les syst` emes d’insertion–d´ el´ etion . . . . . . . . . 439
13.5 Les probl` emes NP-complets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
13.5.1 Le probl` eme du chemin hamiltonien . . . . . . . . . . . . . . . . . . . . . . . . 443
13.5.2 Le probl` eme de la satisfaisabilit´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
13.6 Retour sur les ordinateurs `
a ADN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
13.6.1 Probl` eme du chemin hamiltonien et insertion–d´ el´ etion . . . . . . . . 447
13.6.2 Les limites actuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
13.6.3 Quelques explications biologiques sur la r´ eplication des bases . . 450
13.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
R´ ef´ erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459