Livre_silo 30 août 2013 16:32 Page 11
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
XI
Table des matières
12.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
12.3.1 Analyse des mots bien parenthésés . . . . . . . . . . . . . . . . . . . . . 306
12.3.2 Évaluation d’une expression arithmétique en notation polonaise inverse . . . . 308
12.3.3 Construction d’un labyrinthe parfait . . . . . . . . . . . . . . . . . . . . 310
12.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
C
Algorithmes de tri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
13.1 Tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
13.1.1 Réalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
13.1.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
13.2 Tri rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
13.2.1 Réalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
13.2.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
13.3 Tri fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
13.3.1 Réalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
13.3.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
13.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
A A
Travaux pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
A.1 Création de programmes autonomes . . . . . . . . . . . . . . . . . . . . 331
A.1.1 Compilation d’un programme . . . . . . . . . . . . . . . . . . . . . . . 331
A.1.2 Exécution autonome d’un programme Python . . . . . . . . . . . . . . . . 333
A.2 Mémoire virtuelle et performances de l’ordinateur . . . . . . . . . . . . . 334
A.3 Démontage d’un PC de bureau . . . . . . . . . . . . . . . . . . . . . . . 337
A.3.1 Sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
A.3.2 Repérage des composants . . . . . . . . . . . . . . . . . . . . . . . . . 338
A.3.3 Mise en œuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
A.4 Résolution d’une équation du second degré
avec gestion de la comparaison à zéro . . . . . . . . . . . . . . . . . . . . 352
A.5 Représentation des nombres
dans les calculatrices scientifiques . . . . . . . . . . . . . . . . . . . . . . 352
A.6 Arithmétique et cryptographie . . . . . . . . . . . . . . . . . . . . . . . 354
A.6.1 Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
A.6.2 Décomposition en facteurs premiers . . . . . . . . . . . . . . . . . . . . 355
A.6.3 Recherche de grands nombres premiers . . . . . . . . . . . . . . . . . . . 356
A.6.4 Application à la cryptographie : la méthode RSA . . . . . . . . . . . . . . 358
A.7 Manipulation d’images bitmap . . . . . . . . . . . . . . . . . . . . . . . 359
A.7.1 Traitement pixel par pixel . . . . . . . . . . . . . . . . . . . . . . . . . 360
A.7.2 Traitement local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
A.7.3 Traitement global . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
A.7.4 En couleurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
XI
Table des matières
12.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
12.3.1 Analyse des mots bien parenthésés . . . . . . . . . . . . . . . . . . . . . 306
12.3.2 Évaluation d’une expression arithmétique en notation polonaise inverse . . . . 308
12.3.3 Construction d’un labyrinthe parfait . . . . . . . . . . . . . . . . . . . . 310
12.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
C
Algorithmes de tri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
13.1 Tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
13.1.1 Réalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
13.1.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
13.2 Tri rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
13.2.1 Réalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
13.2.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
13.3 Tri fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
13.3.1 Réalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
13.3.2 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
13.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
A A
Travaux pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
A.1 Création de programmes autonomes . . . . . . . . . . . . . . . . . . . . 331
A.1.1 Compilation d’un programme . . . . . . . . . . . . . . . . . . . . . . . 331
A.1.2 Exécution autonome d’un programme Python . . . . . . . . . . . . . . . . 333
A.2 Mémoire virtuelle et performances de l’ordinateur . . . . . . . . . . . . . 334
A.3 Démontage d’un PC de bureau . . . . . . . . . . . . . . . . . . . . . . . 337
A.3.1 Sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
A.3.2 Repérage des composants . . . . . . . . . . . . . . . . . . . . . . . . . 338
A.3.3 Mise en œuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
A.4 Résolution d’une équation du second degré
avec gestion de la comparaison à zéro . . . . . . . . . . . . . . . . . . . . 352
A.5 Représentation des nombres
dans les calculatrices scientifiques . . . . . . . . . . . . . . . . . . . . . . 352
A.6 Arithmétique et cryptographie . . . . . . . . . . . . . . . . . . . . . . . 354
A.6.1 Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
A.6.2 Décomposition en facteurs premiers . . . . . . . . . . . . . . . . . . . . 355
A.6.3 Recherche de grands nombres premiers . . . . . . . . . . . . . . . . . . . 356
A.6.4 Application à la cryptographie : la méthode RSA . . . . . . . . . . . . . . 358
A.7 Manipulation d’images bitmap . . . . . . . . . . . . . . . . . . . . . . . 359
A.7.1 Traitement pixel par pixel . . . . . . . . . . . . . . . . . . . . . . . . . 360
A.7.2 Traitement local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
A.7.3 Traitement global . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
A.7.4 En couleurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362