[PDF](+88👁️) Télécharger [ Gilles Dowek Et Al.] Informatique Et Sciences Du ( Book ZZ.org) pdf

Gilles Dowek

Jean-Pierre Archambault, Emmanuel Baccelli, Claudio Cimelli,

Albert Cohen, Christine Eisenbeis, Thierry Viéville et Benjamin Wack
Préface de Gérard Berry, professeur au Collège de France

Informatique

et SCICI1CCS du ï

numérique


Spécialité ISN en terminale S



ûvet des exertues torrigés
et des idées de projets



EYROLLES



À qui s'adresse ce livre ?

Ce manuel de cours destiné aux élèves de terminale S ayant choisi la spécialité Informatique et sciences du numérique sera également lu avec
profit par tous les professionnels de l'informatique, qu'ils soient autodidactes ou non, et tous ceux qui veulent apprendre l'informatique.



l'Académie française pour son livre les Métamorphoses du Calcul.






Informatique

et sciences du
numérique

Spécialité ISN en terminale S

Avec des exercices corrigés
et idées de projets


ipyright © 2012 Eyrolles.


Dans la collection Noire


P. Cegielski. - Conception de systèmes d’exploitation. Le cas Linux.
N°GI 1479. 2 e édition, 2004, 680 pages.

J. Engels. HTML5 et CSS3. Cours et exercices corrigés.

N° 13400, 2012, 550 pages.

G. Swtnnen. Apprendre à programmer avec Python 3.

N° 13434, 3' édition, 2012, 435 pages.


H. Bersini. La programmation orientée objet. Cours et exercices en
LJML 2 avec Java 6, C# 4, C++, Python. PHP 5 et LinQ.

N° 12806, 5 e édition, 201 1 , 644 pages.

É. Sarrion. - jQuery et jQuery UI.

N° 12892, 2011, 132 pages.

A. Brillant. XML - Cours et exercices.

N° 12691, 2 e édition, 2010. 336 pages.


Chez le même éditeur


Créer son site web avec un CMS

F.-X. et L. Bois. - WordPress 3 pour le blogueur efficace.

N°12829, 201 1,358 pages.

H. Cocriamont. Réussir son premier site Joomla! 2.5.

N° 13425. 2012, 250 pages environ.

T. Parisot. - Réussir son blog professionnel.

N° 12768, 2 e édition, 2010, 322 pages.


V. Isaksen. T. Tardik. - Joomla 2.5 et Virtuemart 2. Réussir sa
boutique en ligne.

N°12804, 3 e édition à paraître, 2012, 350 pages environ.

Y. Brault, préface d’Edwy Plenel. - Concevoir et déployer ses sites
web avec Drupal 6 et 7.

N° 12780. 2 e édition, 2010. 420 pages.


Développer soi-meme son site web avec HTML, CSS, PHP, JavaScript


R. Rimelé. - HTML5.

N° 12982. 20 II. 600 pages.

F. Draillard. - Premiers pas en CSS et HTML.

N° 13338. 20 11. 464 pages.

R. Goetter. - CSS avancées. Vers HTML5 et CSS3.

N° 13405, 2 e édition. 2012. 385 pages.

R. Guetter. - CSS 2 : pratique du design web.

N° 1 2461 . 3 e édition. 2009. 340 pages.

Développer pour le Web mobile

F. Daoust. D. Hazaël-Massieux. - Bonnes pratiques pour le Web

mobile. Conception et développement.

N° 12828, 20 11. 300 pages.

T. Baillet. Créer son thème WordPress mobile en HTML5 et CSS3.
N°13441, 2012, 128 pages.


R. Rimelé. - Mémento HTML5.

N°13420,2012, 14 pages.

R. Goetter. - Mémento CSS 3.

N° 1328 1,2011, 14 pages.

E. Daspet et C. Pierre Df. Geyer. PHP 5 avancé.

N° 13435, 6 e édition, 2012, 870 pages.

C. Porteneuve. - Bien développer pour le Web 2.0.

N°12391, 2 e édition, 2008, 674 pages.


É. Sarrion. - XHTML/CSS et JavaScript pour le Web mobile.

Développement iPhone et And roid avec et iUI et XUI.

N° 12775, 2010, 274 pages.

É. Sarrion. - jQuery Mobile.

N°13388, 2012, 601 pages.


Ressources autour du Web : design, ergonomie, bonnes pratiques


A. Boucher. - Ergonomie web. Pour des sites web efficaces.
N°13215, 3' édition, 2011, 380 pages.


E. Sloïm. - Mémento Sites web. Les bonnes pratiques.
N° 12802, 3 e édition, 2010. 18 pages.


A. Boucher. - Ergonomie web illustrée. 60 sites à la loupe.
N° 12695. 2010. 302 pages (Design & Interface).

A. Boucher. - Mémento Ergonomie web.

N° 12698, 2 e édition, 2010, 14 pages.



0. Andrieu. - Réussir son référencement web.

N° 13396. 2012,480 pages.

1. Canivet. - Bien rédiger pour le Web. Stratégie de contenu pour
améliorer son référencement.

N° 12883, 2 e édition, 2011, 540 pages.









Gilles Dowek

Jean-Pierre Archambault, Emmanuel Baccelli, Claudio Cimelli,
Albert Cohen, Christine Eisenbeis, Thierry Viéville et Benjamin Wack
Préface de Gérard Berry, professeur au Collège de France

Informatique

et sciences du
numérique

Spécialité ISN en terminale S

Avec des exenues t orrigés
et idées de projets


EYROLLES


)pyright © 2012 Eyrolles


ÉDITIONS EYROLLES
61, bd Saint-Germain
75240 Paris Cedex 05
www.editions-eyrolles.com


Ouvrage publié avec le concours
de l’association EPI - Enseignement Public et Informatique,
de la SIF - Société Informatique de France,
et de l’Institut public de recherche en sciences du numérique - lnria.


Remerciements à Anne Bougnoux (relecture) et Gaël Thomas (maquette),
ainsi qu ’à Raphaël Hertzog, Pierre Néron, Christine Paulin, Grégoire Péan, Jonathan Protzenko
et Dominique Quatravaux pour leurs témoignages.

Merci à Randall Munroe du site XKCD pour les dessins d’ouverture de partie adaptés de l’anglais
ainsi qu ’à Rémi Cieplicki de www.DansTonChat.com pour nous avoir autorisés à utiliser leur logo.

Illustrations de Camille Vorng (cactus, boîtes, arborescences),

Laurène Gibaud et Bernard Sullerot (circuits logiques, opérations binaires, schémas, labyrinthes)

Photographies d’ouvertures de chapitres

Alan Turing (aimable autorisation de la Sherborne School, merci à Rachel Hassall),

John Backus (Pierre. Lescanne, CC-BY-SA-3.0), Grâce Hopper (James S. Davis, domaine public),

Gilles Kahn (marcstephanegoldberg — Flickr), Gordon Plotkin (merci à lui d’avoir accepté de nous fournir une photographie),
John McCarthy (nullO - Flickr, CC BY 2.0), Robin Milner (http://www.cl.cam.ac.uk/archive/rml35/),

Dana Scott (Andrej Bauer -http://andrej.com/mathematicians), Claude Shannon (Tekniska museet Flickr, CC BY-SA 2.0),
Tim Berners-Lee (Paul Clarke, CC-BY-2.0), Ronald Rivest (carbackl, CC BY 2.0),

Adi Shamir (Ira Abramov de Even Yehuda, Israël, CC-BY-SA-2.0), Len Adleman (len adltnen, CC-BY-SA-3.0),

Fronces Allen (Rama, CC-BY-SA-2.0-fr), John Von Neumann (LANL, domaine public),

Vinton Cerf et Robert Kahn (Paul Morse, domaine public), Ada Lovelace (Alfred Edward Chalon, domaine public),

Ivan Sutherland (Dick Lyon, CC-BY-SA-3.0), Donald Knuth (Jacob Appelbaum, CC-BY-SA-2.5),

Philippe Flajolet (Luc Devroye, CC-BY-SA-3.0), Joseph Sifakis (Rama, CC-BY-SA-2.0-fr),

Christopher Strachey ( http://www.rutherfordjournal.org/article040l01.html ), Gottlob Frege (inconnu, domaine public),
Muhammad al-Khwarizmi et Samuel Morse (inconnu, domaine public),

Thomas Flowers (http://www.ithistory.org/honor _roll/fame-detail.php?recordID=444 - merci à l ’ équipe de 1T History pour leur
aimable autorisation), Otto Schmitt (http://160.94.W2.47/index.htm), Norbert Wiener (Konrad Jacobs, CC-BY-SA-2.0-de)

Autres images

Qui est-ce est un jeu développé par la société Theora Design (http://theoradesign.com)
et distribué en France par MB (Idées de projets)

La Joconde, tableau de Léonard de Vinci (chapitre 19) et L’Annonciation, tableau de Sandro Botticelli (chapitre 19)

Robolab : par Mirko Tobias Schàfèr (chapitre 1 7)

Thyroïdectomie assistée par un robot : CHU de Nîmes (http://www.chu-nimes.fr/espace-presse-galerie-photos.html) (chapitre 17)
Robot mOway : http://www.moway-robot.com, http://www.adrirobot.it/moway/mowaydrcuito.htm (chapitre 17)


En application de la loi du 1 1 mars 1957, il est interdit de reproduire intégralement ou partiellement le présent ouvrage, sur quelque support que ce soit,
sans l’autorisation de l’Éditeur ou du Centre Français d'exploitation du droit de copie, 20, rue des Grands Augustins, 75006 Paris.

© Groupe Eyrolles. 20 1 2, ISBN : 978-2-2 1 2- 1 3543-5



)pyright © 2012 Eyrolles.


Préface


L’année 2012 voir l’entrée de l’informatique en tant qu’enseignement de spé-
cialité en classe de Terminale scientifique. Cette entrée devenait urgente, car
l’informatique est désormais partout. Créée dans les années 1950 grâce à une
collaboration entre électroniciens, mathématiciens et logiciens (ces derniers
en ayant posé les bases dès 1935), elle n’a cessé d’accélérer son mouvement
depuis, envahissant successivement l’industrie, les télécommunications, les
transports, le commerce, l’administration, la diffusion des connaissances, les
loisirs, et maintenant les sciences, la médecine et l’art, tout cela en créant de
nouvelles formes de communication et de relations sociales. Les objets infor-
matiques sont maintenant par milliards et de toutes tailles, allant du giga-
ordinateur équipé de centaines de milliers de processeurs aux micro-puces des
cartes bancaires ou des prothèses cardiaques et auditives, en passant par les
PC, les tablettes et smartphones, les appareils photos, ou encore les ordina-
teurs qui conduisent et contrôlent les trains, les avions et bientôt les voitures.
Tous fonctionnent grâce à la conjonction de puces électroniques et de logi-
ciels, objets immatériels qui décrivent très précisément ce que vont faire ces
appareils électroniques. Au XXI e siècle, la maîtrise du traitement de l’infor-
mation est devenue aussi importante que celle de l’énergie dans les siècles
précédents, et l’informatique au sens large est devenue un des plus grands
bassins d’emploi à travers le monde. Cela implique que de nombreux lycéens
actuels participeront à son essor dans l’avenir.

Ces jeunes lycéens sont bien sûr très familiers avec les appareils informatisés.
Mais ce n’est pas pour cela qu’ils en comprennent le fonctionnement, même


)pyright © 2012 Eyrolles.


Informatique et sciences du numérique


sur des plans élémentaires pour certains. Une opinion encore fort répandue est
qu’il n’y a pas besoin de comprendre ce fonctionnement, et qu’il suffit
d’apprendre l’usage des appareils et logiciels. À l’analyse, cette opinion appa-
remment naturelle s’avère tout à fait simpliste, avec des conséquences néfastes
qu’il faut étudier de près. Pour faire un parallèle avec une autre discipline, on
enseigne la physique car elle est indispensable à la compréhension de la nature
de façon générale, et aussi de façon plus spécifique au travail de tout ingénieur
et de tout scientifique, c’est-à-dire aux débouchés naturels de beaucoup
d’élèves de terminale scientifique. Mais qui penserait qu’il suffit de passer le
permis de conduire pour comprendre la physique d’un moteur ou la méca-
nique une voiture ? Or, nous sommes tous autant confrontés à l’informatique
qu’à la physique, même si elle ne représente pas un phénomène
naturel préexistant ; comme pour la physique, les ingénieurs et scientifiques
devront y être au moins autant créateurs que consommateurs. Pour être plus
précis, sous peine de ne rester que des consommateurs serviles de ce qui se crée
ailleurs, il est indispensable pour notre futur de former au cœur conceptuel et
technique de l’informatique tout élève dont le travail technique sera relié à
l’utilisation avancée ou à la création de l’informatique du présent ou du futur. Il
est donc bien naturel que la nouvelle formation à l’informatique s’inaugure en
terminale scientifique. Mais elle devra immanquablement ensuite être élargie
à d’autres classes, car tout élève sera concerné en tant que futur citoyen.

Pour être efficace, toute formation scolaire demande un support adéquat. Ce
premier livre va jouer ce rôle pour l’informatique, en présentant de façon
pédagogique les quatre composantes scientifiques et techniques centrales de
son cœur scientifique et technique : langages de programmation, numérisa-
tion de l’information, machines et réseaux, et algorithmes. Il a été écrit par
des chercheurs et enseignants confirmés, tous profondément intéressés par
le fait que les élèves comprennent, assimilent et apprécient les concepts et
techniques présentées. Il insiste bien sur deux points essentiels : le fait que
ces quatre composantes sont tout à fait génériques, c’est-à-dire valables pour
tous les types d’applications, des méga-calculs nécessaires pour étudier l’évo-
lution du climat aux calculs légers et rapides à effectuer dans les micro-puces
enfouies partout, et le fait que les concepts associés resteront valables dans le
temps. En effet, si les applications de l’informatique évoluent très vite, son
cœur conceptuel reste très stable, au moins au niveau approprié pour la ter-
minale scientifique. L’enseigner de façon adéquate est nécessaire autant à la
compréhension des bases qu’à tout approfondissement ultérieur. À n’en pas
douter, cet ouvrage y contribuera.

Gérard Berry, directeur de recherche Inria
Professeur au Collège de France,
Membre de l’Académie des sciences, de l’Académie des technologies,

et de l’Academia Europaea

VI


)pyright © 2012 Eyrolles.


Table des matières


Préface V

Avant-propos 1


Structure de l’ouvrage • 2
Parcours possibles • 4
Remerciements • 4

Première partie


Langages 5

1. Les ingrédients des programmes 7

Un premier programme • 8
La description du programme • 9


SAVOIR-FAIRE Modifier un programme existant pour obtenir
un résultat différent *11
Les ingrédients d’un programme • 12

SAVOIR-FAIRE Comprendre un programme et expliquer
ce qu’il fait • 14

SAVOIR-FAIRE Ecrire un programme • 15
SAVOIR-FAIRE Mettre un programme au point en le testant • 16
Les instructions et les expressions • 17
Les opérations *18
Les accolades • 19

SAVOIR-FAIRE Indenter un programme • 21
Ai-je bien compris ? • 22

2. Les boucles 23

La boucle for • 24

SAVOIR-FAIRE Écrire un programme utilisant une boucle for • 26
SAVOIR-FAIRE Imbriquer deux boucles • 26
La boucle while • 28


SAVOIR-FAIRE Écrire un programme utilisant une boucle while • 29
SAVOIR-FAIRE Commenter un programme • 30
La non-terminaison • 31

La boucle for, cas particulier de la boucle while *31

SAVOIR-FAIRE Choisir entre une boucle for et la boucle while
pour écrire un programme • 33
Ai-je bien compris ? • 34

3. Les types 35

Les types de base • 37

SAVOIR-FAIRE Différencier les types de base • 39
SAVOIR-FAIRE Changer le type d’une expression • 39
La portée et l’initialisation des variables • 41
SAVOIR-FAIRE Déclarer les variables avec des types
et des portées appropriés • 43
SAVOIR-FAIRE Initialiser les variables • 43
Les tableaux • 44

SAVOIR-FAIRE Utiliser un tableau dans un programme • 46
Les tableaux bidimensionnels • 48
Les chaînes de caractères • 50

Savoir-faire Calculer avec des chaînes de caractères • 50
La mise au point des programmes • 52

SAVOIR-FAIRE Mettre au point un programme
en l’instrumentant • 52
Ai-je bien compris ? • 54

4. Les fonctions (avancé) 55

Isoler une instruction • 56

Passer des arguments • 58
Récupérer une valeur • 59

SAVOIR-FAIRE Écrire l’en-tête d’une fonction • 60


VII


)pyright © 2012 Eyrolles.


Informatique et sciences du numérique


Savoir-faire Écrire une fonction • 61
Le programme principal • 62
La portée des variables et les variables globales • 62
SAVOIR-FAIRE Identifier la portée des variables
dans un programme comportant des fonctions • 65
SAVOIR-FAIRE Choisir une portée adaptée aux differentes
variables d’un programme comportant des fonctions • 69
Le passage par valeur *71

Savoir-faire

Choisir entre un passage par valeur et une variable globale • 73
Le passage par valeur et les tableaux • 74
Ai-je bien compris ? • 76

5. La récursivité (avancé) 77

Des fonctions qui appellent des fonctions • 78

Des fonctions qui s’appellent elles-mêmes • 79

SAVOIR-FAIRE Définir une fonction récursive • 81
Des images récursives • 83
Ai-je bien compris ? • 84

6. La notion de langage formel (avancé) 85

Les langages informatiques et les langues naturelles • 86
Les ancêtres des langages formels • 87
Les langages formels et les machines • 88
La grammaire • 89
La sémantique • 91
Redéfinir la sémantique • 92
Ai-je bien compris ? • 93

Deuxième partie


Informations 95

7. Représenter des nombres entiers et à virgule 97

La représentation des entiers naturels • 99
La base cinq • 100


SAVOIR-FAIRE Trouver la représentation en base cinq
d’un entier naturel donné en base dix • 100
SAVOIR-FAIRE Trouver la représentation en base dix
d’un entier naturel donné en base cinq • 101
La base deux • 102

SAVOIR-FAIRE Trouver la représentation en base deux
d’un entier naturel donné en base dix • 102
SAVOIR-FAIRE Trouver la représentation en base dix
d’un entier naturel donné en base deux • 102
Une base quelconque • 103

VIII


SAVOIR-FAIRE Trouver la représentation en base k
d’un entier naturel donné en base dix • 103
SAVOIR-FAIRE Trouver la représentation en base dix
d’un entier naturel donné en base k • 104
La représentation des entiers relatifs • 105

SAVOIR-FAIRE Trouver la représentation binaire sur n bits
d’un entier relatif donné en décimal • 106
SAVOIR-FAIRE Trouver la représentation décimale
d’un entier relatif donné en binaire sur n bits *106
SAVOIR-FAIRE Calculer la représentation p’ de l’opposé
d’un entier relatif x à partir de sa représentation p,
pour une représentation des entiers relatifs sur huit bits • 106
La représentation des nombres à virgule *108

SAVOIR-FAIRE Trouver la représentation en base dix
d’un nombre à virgule donné en binaire • 108
Ai-je compris ? • 110

8. Représenter des caractères et des textes 111

La représentation des caractères • 112
La représentation des textes simples • 113

SAVOIR-FAIRE Trouver la représentation en ASCII binaire
d’un texte *113

SAVOIR-FAIRE Décoder un texte représenté en ASCII binaire • 114
La représentation des textes enrichis *116
SAVOIR-FAIRE Écrire une page en HTML *118
Ai-je bien compris ? • 120

9. Représenter des images et des sons 121

La représentation des images • 122
La notion de format • 123

SAVOIR-FAIRE Identifier quelques formats d’images • 124
La représentation des images en niveaux de gris et en couleurs • 124
SAVOIR-FAIRE Numériser une image sous forme d’un fichier • 126
La représentation des sons • 128
La taille d’un texte, d’une image ou d’un son • 129

SAVOIR-FAIRE Comprendre les tailles des données et les ordres
de grandeurs • 130

SAVOIR-FAIRE Choisir un format approprié par rapport
à un usage ou un besoin, à une qualité, à des limites • 131
Ai-je bien compris ? • 131

10. Les fonctions booléennes 133

L’expression des fonctions booléennes • 134

Les fonctions non, et, ou • 134
L’expression des fonctions booléennes
avec les fonctions non, et, ou • 135


)pyright © 2012 Eyrolles.


Table des matières


SAVOIR-FAIRE Trouver une expression symbolique exprimant
une fonction à partir de sa table • 136
L’expression des fonctions booléennes
avec les fonctions non et ou *137
Ai-je bien compris ? • 138

11. Structurer l'information (avancé) 139

La persistance des données *140

La notion de fichier • 141
Utiliser un fichier dans un programme • 141
Organiser des fichiers en une arborescence • 144
SAVOIR-FAIRE Classer des fichiers sous la forme
d’une arborescence *145
Liens et hypertextes • 147
L’hypermnésie • 148

Pourquoi l’information est-elle souvent gratuite ? * 149

Ai-je bien compris ? • 152

12. Compresser, corriger, chiffrer (avancé) 153

Compresser • 154

SAVOIR-FAIRE Utiliser un logiciel de compression • 156
Compresser avec perte *157
Corriger* 158
Chiffrer *160
Ai-je bien compris ? • 164


Troisième partie

Machines

13. Les portes booléennes

165

167

Le circuit NON • 168

Le circuit OU • 169

Quelques autres portes booléennes • 170

Ai-je bien compris ? • 175

14. Le temps et la mémoire

177

La mémoire • 178

L’horloge *182

Ai-je bien compris ? • 184

15. L'organisation d'un ordinateur

185

Trois instructions • 187

Le langage machine *188

SAVOIR-FAIRE Savoir dérouler l’exécution d’une

séquence

d’instructions *190

La compilation • 191



Les périphériques • 192
Le système d’exploitation *192
Ai-je bien compris ? • 195

16. Les réseaux (avancé) 197

Les protocoles • 198

La communication bit par bit : les protocoles de la couche

physique • 200

Les réseaux locaux :

les protocoles de la couche lien • 201

SAVOIR-FAIRE Trouver les adresses MAC des cartes réseau
d’un ordinateur • 203

Le réseau global : les protocoles de la couche réseau • 204
SAVOIR-FAIRE Trouver l’adresse IP attribuée à un ordinateur • 204
SAVOIR-FAIRE Déterminer le chemin suivi par l’information • 207
SAVOIR-FAIRE Déterminer l’adresse IP du serveur par lequel
un ordinateur est connecté à Internet • 208
La régulation du réseau global : les protocoles de la couche
transport • 209

Programmes utilisant le réseau : la couche application *211
Quelles lois s’appliquent sur Internet ? • 212
Qui gouverne Internet ? • 213

Ai-je bien compris ? • 214

17. Les robots (avancé) 215

Les composants d’un robot • 216

La numérisation des grandeurs captées • 217

Le contrôle de la vitesse : la méthode du contrôle en boucle

fermée • 219

Programmer un robot : les actionneurs • 220
Programmer un robot : les capteurs • 222

SAVOIR-FAIRE Ecrire un programme pour commander un robot • 223
Ai-je bien compris ? • 225

Quatrième partie

Algorithmes 227

18. Ajouter deux nombres exprimés en base deux 229

L’addition • 230

L’addition pour les nombres exprimés en base deux • 231
La démonstration de correction du programme • 235

Ai-je bien compris ? • 238

19. Dessiner 239

Dessiner dans une fenêtre • 240

IX


)pyright © 2012 Eyrolles.


Informatique et sciences du numérique


SAVOIR-FAIRE Créer une image • 240
Dessiner en trois dimensions • 242
Produire un fichier au format PPM • 245
Lire un fichier au format PPM • 247
Transformer les images • 248

SAVOIR-FAIRE Transformer une image en couleurs
en une image en niveaux de gris • 248
SAVOIR-FAIRE Augmenter le contraste d’une image
en niveaux de gris • 249

SAVOIR-FAIRE Modifier la luminance d’une image • 250
SAVOIR-FAIRE Changer la taille d’une image • 250
SAVOIR-FAIRE Fusionner deux images • 251
SAVOIR-FAIRE Lisser une image pour éliminer
ses petits défauts et en garder les grands traits • 252
Ai-je bien compris ? • 254

20. La dichotomie (avancé) 255

La recherche en table • 256

La conversion analogique-numérique • 261
Trouver un zéro d’une fonction *261

Ai-je bien compris ? • 262

21. Trier (avancé) 263

Le tri par sélection • 264

Le tri par fusion • 268
L’efficacité des algorithmes • 272

SAVOIR-FAIRE S’interroger sur l’efficacité d’un algorithme • 273
L’efficacité des algorithmes de tri par sélection et par fusion • 274
Ai-je bien compris ? • 276

22. Parcourir un graphe (avancé) 277

La liste des chemins à prolonger • 278

Eviter de tourner en rond • 280

La recherche en profondeur et la recherche en largeur • 282
Le parcours d’un graphe • 283
États et transitions • 284
Ai-je bien compris ? • 287

Idées de projets 289

Un générateur d’exercices de calcul mental • 289


Mastermind • 289

Brin d’ARN • 289

Bataille navale • 289

Cent mille milliards de poèmes • 289

Site de rencontres • 289

Tracer la courbe représentative d’une fonction polynôme

du second degré • 291

Gérer le score au tennis • 291

Automatiser les calculs de chimie • 291

Tours de Hanoï • 291

Tortue Logo • 291

Dessins de plantes • 291

Langage CSS • 291

Calcul sur des entiers de taille arbitraire • 291
Calcul en valeur exacte sur des fractions • 293
Représentation des dates et heures • 293
Transcrire dans l’alphabet latin • 293
Correcteur orthographique • 293
Daltonisme • 293
Logisim • 293
Banc de registres • 293

Simuler le comportement du processeur • 295
Utilisation du logiciel Wireshark • 295
Algorithme de pledge • 295

Algorithme calculant le successeur d’un nombre entier
naturel n • 295
Le jeu de la vie • 295
Une balle • 297

Générateur d’œuvres aléatoires • 297
Détecteur de mouvement visuel • 297
Qui est-ce ? • 297
Un joueur de Tic-tac-toe • 297
Enveloppe convexe • 298
Chemins les plus courts • 298
Utilisation des réseaux sociaux • 298

Index 299



)pyright © 2012 Eyrolles.


Avant-propos


Il y a un siècle, il n’y avait pas d’ordinateurs ; aujourd’hui, il y en a plu-
sieurs milliards. Ces ordinateurs et autres machines numériques que sont
les réseaux, les téléphones, les télévisions, les baladeurs, les appareils
photos, les robots, etc. ont changé la manière dont nous :

• concevons et fabriquons des objets,

• échangeons des informations entre personnes,

• gardons trace de notre passé,

• accédons à la connaissance,

• faisons de la science,

• créons et diffusons des œuvres d’art,

• organisons les entreprises,

• administrons les états,

• etc.

Si les ordinateurs ont tout transformé, c’est parce qu’ils sont polyvalents,
ils permettent de traiter des informations de manières très diverses. C’est
en effet le même objet qui permet d’utiliser des logiciels de conception
assistée par ordinateur, des machines à commande numérique, des logi-
ciels de modélisation et de simulation, des encyclopédies, des cours en
ligne, des bases de données, des blogs, des forums, des logiciels de cour-
rier électronique et de messagerie instantanée, des logiciels d’échange de
fichiers, des logiciels de lecture de vidéos et musique, des tables de
mixage numériques, des archives numériques, etc.

Cette polyvalence s’illustre aussi par le nombre d’outils que les ordina-
teurs ont remplacé : machines à écrire, téléphones, machines à calculer,
télévisions, appareils photos, électrophones, métiers à tisser. . .

En fait, les ordinateurs sont non seulement capables de traiter des infor-
mations de manières diverses, mais également de toutes les manières
possibles. Ce sont des machines universelles.



En 1936, soit quelques années
avant la construction des premiers
ordinateurs. Alan Turing (1912-
1954) - et en même temps que lui
Alonzo Church - a étudié les liens
entre les notions d'algorithme et
de raisonnement mathématique.

Cela l'a mené à imaginer un pro-
cédé de calcul, les machines de
Turing, et à suggérer que ce pro-
cédé de calcul puisse être universel,
c'est-à-dire capable d'exécuter tous
les algorithmes possibles.


jpyright © 2012 Eyrolles.


Informatique et sciences du numérique


//. Traiter des informations

Traiter des informations signifie appliquer,
d'une manière systématique, des opérations à des
symboles. La recherche d’un mot dans un diction-
naire, le chiffrement et le déchiffrement d'un mes-
sage secret, l’addition et la multiplication de deux
nombres, la fabrication des emplois du temps des
élèves d'un lycée ou des pilotes d'une compagnie
aérienne, le calcul de l'aire d'une parcelle agricole
ou encore le compte des points des levées d'un
joueur au Tarot sont des exemples de traitements
d'informations.


ALLER PLUS LOIN Des algorithmes aussi vieux
que l'écriture

Il y a quatre mille ans, les scribes et les arpen-
teurs, en Mésopotamie et en Égypte, mettaient
déjà en œuvre des algorithmes pour effectuer
des opérations comptables et des calculs d'aires
de parcelles agricoles. La conception d'algo-
rithmes de traitement de l’information semble
remonter aux origines mêmes de l'écriture. Dès
l'apparition des premiers signes écrits, les
hommes ont imaginé des algorithmes pour les
transformer.


Un procédé systématique qui permet de traiter des informations s’appelle un
algorithme. Ainsi, on peut parler d’algorithmes de recherche d’un mot dans
un dictionnaire, d’algorithmes de chiffrement et de déchiffrement, d’algo-
rithmes pour faire des additions et des multiplications, etc. De manière plus
générale, un algorithme est un procédé systématique qui permet de faire
quelque chose. Par exemple une recette de cuisine est un algorithme.

La notion d’algorithme est très ancienne. Depuis la nuit des temps, les
hommes ont conçu et appris des algorithmes, pour fabriquer des objets
en céramique, tisser des étoffes, nouer des cordages ou, simplement, pré-
parer des aliments.

Le bouleversement survenu au milieu du XX e siècle tient à ce que les
hommes ont cessé d’utiliser exclusivement ces algorithmes à la main ; ils
ont commencé à les faire exécuter par des machines, les ordinateurs.
Pour y parvenir, il a fallu exprimer ces algorithmes dans des langages de
programmation, accessibles aux ordinateurs. Ces langages sont différents
des langues humaines en ce qu’ils permettent la communication non pas
entre êtres humains, mais entre les êtres humains et les machines.

L’informatique est donc née de la rencontre de quatre concepts très anciens :

• machine,

• information,

• algorithme,

• langage.

Ces concepts existaient tous avant la naissance de l’informatique, mais l’infor-
matique les a profondément renouvelés et articulés en une science cohérente.


Structure de l’ouvrage

L’objectif de ce cours est d’introduire les quatre concepts de machine,
d’information, d’algorithme et de langage, mais surtout de montrer la
manière dont ils fonctionnent ensemble. Quand nous étudierons les
algorithmes fondamentaux, nous les exprimerons souvent dans un lan-
gage de programmation. Quand nous étudierons l’organisation des
machines, nous verrons comment elles permettent d’exécuter des pro-
grammes exprimés dans un langage de programmation. Quand nous
étudierons la notion d’information, nous verrons des algorithmes de
compression, de chiffrement, etc.

Ce livre est donc organisé en quatre parties regroupant vingt-deux chapi-
tres, dont certains d’un niveau plus avancé (indiqués par un astérisque) :



)pyright © 2012 Eyrolles.


Avant-propos


• Dans la première partie « Langages », nous apprendrons à écrire des
programmes. Pour cela, nous allons découvrir les ingrédients dont les
programmes sont constitués : l’affectation, la séquence et le test
(chapitre 1), les boucles (chapitre 2), les types (chapitre 3), les fonc-
tions (chapitre 4*) et les fonctions récursives (chapitre 5*). Pour finir,
nous nous pencherons sur la notion de langage formel (chapitre 6*).
Dès que l’on commence à maîtriser ces concepts, il devient possible
de créer ses propres programmes.

• Dans la deuxième partie, « Informations », nous abordons l’une des pro-
blématiques centrales de l’informatique : représenter les informations
que l’on veut communiquer, stocker et transformer. Nous apprendrons à
représenter les nombres entiers et les nombres à virgule (chapitre 7), les
caractères et les textes (chapitre 8), les images et les sons (chapitre 9). La
notion de valeur booléenne, ou de bit, qui apparaît dans ces trois chapi-
tres, nous mènera naturellement à la notion de fonction booléenne
(chapitre 10). Nous apprendrons ensuite à structurer de grandes quan-
tités d’informations (chapitre 11*), à optimiser la place occupée grâce à la
compression, corriger les erreurs qui peuvent se produire au moment de
la transmission et du stockage de ces informations, et à les protéger par le
chiffrement (chapitre 12*).

• Dans la troisième partie, « Machines », nous verrons que derrière les
informations, il y a toujours des objets matériels : ordinateurs, réseaux,
robots, etc. Les premiers ingrédients de ces machines sont des portes
booléennes (chapitre 13) qui réalisent les fonctions booléennes vues au
chapitre 10. Ces portes demandent à être complétées par d’autres cir-
cuits, comme les mémoires et les horloges, qui introduisent une dimen-
sion temporelle (chapitre 14). Nous découvrirons comment
fonctionnent les machines que nous utilisons tous les jours (chapitre 15).
Nous verrons que les réseaux, comme les oignons, s’organisent en cou-
ches (chapitre 16*). Et nous découvrirons enfin les entrailles des robots,
que nous apprendrons à commander (chapitre 17*).

• Dans la quatrième partie, « Algorithmes », nous apprendrons quel-
ques-uns des savoir-faire les plus utiles au XXI e siècle : ajouter des
nombres exprimés en base deux (chapitre 18), dessiner (chapitre 19),
retrouver une information par dichotomie (chapitre 20*), trier des
informations (chapitre 21*) et parcourir un graphe (chapitre 22*).

Chaque chapitre contient trois types de contenus :

• une partie de cours ;

• des sections intitulées « Savoir-faire », qui permettent d’acquérir les
capacités essentielles ;

• des exercices, avec leur corrigé lorsque nécessaire.


REMARQUE Chapitres élémentaires
et chapitres avancés*

Les chapitres avancés sont notés ici d'un asté-
risque. Il s'agit des deux ou trois derniers chapi-
tres de chaque partie. Ils sont signalés en début
de chapitre.


^ Exercices difficiles

Les exercices notés d'un cactus sont d'un niveau
plus difficile.



jpyright © 2012 Eyrolles.


Informatique et sciences du numérique


Des encadrés « Aller plus loin » donnent des ouvertures vers des ques-
tions hors-programme. Chaque chapitre se conclut de trois questions de
cours sous forme d’encadré intitulé « Ai-je bien compris ? ».

Les propositions de projets sont regroupées en fin de manuel.


Parcours possibles

Cet ouvrage peut être parcouru de plusieurs manières. Nous proposons
par exemple de commencer par les chapitres élémentaires de la partie
Informations (7, 8, 9 et 10), de poursuivre par ceux de la partie Lan-
gages (1, 2 et 3), de continuer par les chapitres avancés de la partie
Informations (11 et 12), les chapitres élémentaires de la partie Algo-
rithmes (18 et 19) et de la partie Machines (13, 14 et 15), et enfin de
passer aux chapitres avancés de la partie Machines (16 et 17), de la partie
Langages (4, 5 et 6) et de la partie Algorithmes (20, 21 et 22).

Il n’est pas nécessaire de lire ces chapitres au même degré de détails. À
chaque élève de choisir les thématiques qu’il souhaite approfondir parmi
celles proposées, en particulier par le choix de ses projets.

La seule contrainte est d’acquérir assez tôt les bases des langages de pro-
grammation, aux chapitres 1, 2 et 3, pour pouvoir écrire soi-même des
programmes. Quand on apprend l’informatique, il est en effet important
non seulement d’écouter des cours et de lire des livres, mais aussi de
mettre en pratique les connaissances que l’on acquiert en écrivant soi-
même des programmes, en se trompant et en corrigeant ses erreurs.


Remerciements

Les auteurs tiennent à remercier Ali Assaf, Olivier Billet, Manuel Bricard,
Stéphane Bortzmeyer, Alain Busser, David Cachera, Vint Cerf, Julien
Cervelle, Sébastion Chapuis, S. Barry Cooper, Ariane Delrocq, Lena
Domrôse, Raffi Enficiaud, Monique Grandbastien, Guillaume Le Blanc,
Fabrice Le Fessant, Philippe Lucaud, Pierre-Ftienne Moreau, Claudine
Noblet, François Périnet, Gordon Plotkin, François Pottier, David Roche,
Laurent Sartre, Dana Scott, Adi Shamir et Joseph Sifakis pour leur aide
au cours de la rédaction de ce livre ainsi que l’équipe des éditions Eyrolles,
Anne Bougnoux, Laurène Gibaud, Muriel Shan Sei Fan, Gaël Thomas et
Camille Vorng pour leur travail éditorial très créatif.

Merci également à Christine Paulin, Raphaël Hertzog, Pierre Néron,
Grégoire Péan, Jonathan Protzenko et Dominique Quatravaux pour
leurs témoignages vivants.



Langages


Dans cette première partie, nous apprenons à écrire des
programmes. Pour cela, nous découvrons les ingrédients dont les
programmes sont constitués : l’affectation, la séquence et le test
(chapitre 1), les boucles (chapitre 2), les types (chapitre 3), les
fonctions (chapitre 4*) et les fonctions récursives (chapitre 5*). Pour
finir, nous nous penchons sur la notion de langage formel
(chapitre 6*).

Dès que l’on commence à maîtriser ces concepts, il devient possible
de créer ses propres programmes.


int getN ombre AleatoireÇ)
{


1


return 4 ; // Nombre choisi au dé (non truqué)

// Garanti 100% aléatoire.



)pyright © 2012 Eyrolles.


Les ingrédients

des

programmes



Un ordinateur peut faire bien des choses ,
mais il faut d'abord les lui expliquer.


Apprendre la programmation, ce n’est pas seulement savoir
écrire un programme, c’est aussi comprendre de quoi il est fait,
comment il est fait et ce qu’il fait. Un programme est
essentiellement constitué d’expressions et d’instructions.

Nous introduisons dans ce premier chapitre les trois premières
instructions fondamentales que sont l’affectation, la séquence
et le test. Pour mettre en évidence leur structure, nous
indentons les programmes et utilisons les accolades lorsque
l’écriture est ambiguë. Nous étudions les instructions
en observant les transformations qu’elles opèrent sur l’état
de l’exécution du programme, c’est-à-dire sur l’ensemble
des boîtes pouvant contenir des valeurs, avec leur nom
et leur valeur, le cas échéant.



John Backus (1924-2007) est
l'auteur de l'un des premiers lan-
gages de programmation : le lan-
gage Fortran (1954). Il a par la suite
proposé, avec Peter Naur, la notation
de Backus et Naur qui permet de
décrire des grammaires, en particu-
lier celles des langages de program-
mation (voir le chapitre 6).

Grâce Hopper (1906-1992) est, elle
aussi, l'auteur d'un des premiers lan-
gages de programmation : le lan-
gage Cobol (1959). Avant cela, elle a
été l'une des premières à pro-
grammer le Harvard Mark I de
Howard Aiken, l'un des tous premiers
calculateurs électroniques.



)pyright © 2012 Eyrolles.


Première partie - Langages


Un programme est un texte qui décrit un algorithme que l’on souhaite
faire exécuter par une machine. Ce texte est écrit dans un langage parti-
culier, appelé langage de programmation. Il existe plusieurs milliers de
langages de programmation, parmi lesquels Java, C, Python, Caml, For-
tran, Cobol, etc. Il n’est cependant pas nécessaire d’apprendre ces lan-
gages les uns après les autres, car ils sont tous plus ou moins organisés
autour des mêmes notions : déclaration, affectation, séquence, test,
boucle, fonction, etc. Ce sont ces notions qu’il importe de comprendre.
Dans ce livre, nous utilisons principalement le langage Java. Mais rien de
ce que nous disons ici n’est propre à ce langage et les élèves qui en utili-
sent un autre n’auront aucun mal à transposer.

Nous verrons, au chapitre 3, comment faire pour exécuter un programme
sur un ordinateur. Dans ce chapitre et le suivant, nous parlons des pro-
grammes de manière théorique, c’est-à-dire sans les exécuter. Bien
entendu, les lecteurs sont libres d’anticiper et de lire les premières pages du
chapitre 3, s’ils souhaitent exécuter leurs programmes tout de suite.


Un premier programme

Voici un premier petit programme écrit en Java :

a = 4;
b = 7;

System. out.print1n("À vous de jouer");
x = Isn . readlntO ;
y = Isn . readlntO ;
if (x == a && y == b) {

System. out . pri ntl n("Coulé") ;}
else {

if (x = a | | y == b) {

System. out. print)n("En vue") ;}
else {

System. out. pri ntln("À 1 'eau") ;}}

Quand on exécute ce programme, il affiche À vous de jouer puis attend
que l’on tape deux nombres au clavier. Si ces deux nombres sont 4 et 7, il
affiche Coulé ; si le premier est 4 ou le second 7, mais pas les deux, il
affiche En vue, sinon il affiche À 1 ' eau.

Ce programme permet de jouer à la bataille navale, dans une variante
simplifiée dans laquelle il n’y a qu’un seul bateau, toujours placé au
même endroit et qui n’occupe qu’une seule case de la grille. On considère



)pyright © 2012 Eyrolles.


1 - Les ingrédients des programmes


qu’un bateau est « en vue » si la case proposée est sur la même ligne ou la
même colonne que le bateau.

Exercice 1.1

Modifier ce programme afin qu'il affiche À toi de jouer et non À vous de
jouer.

Exercice 1.2

Modifier ce programme afin que le bateau soit sur la case de coordonnées (6 ; 9) .


La description
du programme


Commençons par observer ce programme pour essayer d’en comprendre
la signification. La première ligne contient l’instruction a = 4;. Pour
comprendre ce qu’il se passe quand on exécute cette instruction, il faut
imaginer que la mémoire de l’ordinateur que l’on utilise est composée
d’une multitude de petites boîtes. Chacune de ces boîtes porte un nom et
peut contenir une valeur. Exécuter l’instruction a = 4; a pour effet de
mettre la valeur 4 dans la boîte de nom a.



Après avoir exécuté cette instruction, on exécute b = 7 ; , ce qui a pour
effet de mettre la valeur 7 dans la boîte de nom b .


CU L±J [ Jfj ULJ

0000


On exécute ensuite l’instruction System. out.pri ntl n ("À vous de
jouer") ; , ce qui a pour effet d’afficher à l’écran À vous de jouer.

On exécute ensuite l’instruction x = Isn . readlntO ; , ce qui a pour effet
d’interrompre le déroulement du programme jusqu’à ce que l’utilisateur
tape un nombre au clavier. Ce nombre est alors mis dans la boîte de nom x.


Dans d'autres langages

Texas Instruments et Casio

Ce même algorithme peut s'exprimer dans de
nombreux langages. À titre d'exemple, le voici
exprimé dans le langage des calculatrices Texas
Instruments et Casio. Dans ces deux cas l'algo-
rithme utilisé est le même qu'en Java. Les
seules différences sont dans la manière
d'exprimer cet algorithme : la variable à affecter
est située à droite de la flèche pour les calcula-
trices, l'instruction de test est structurée par des
mots-clés supplémentaires, entre autres.

• Texas Instruments

PROGRAM: BATAILLE
:4 ->A
:7 ->B

:Disp "À vous de jouer"

:Input X
:Input Y

:If X = A et Y = B
:Then

:Disp "Coulé"

:Else

:If X = A ou Y = B
:Then

:Disp "En vue"

:Else

:Disp "À 1 'eau"

:End

:End

• Casio

=====BATAILLE ======

4 ->A
7 ->B

"À vous de jouer"

? ->X
? ->Y

If X = A And Y = B
Then "Coulé"

El se

If X = A
Lire la suite

• Taille
  65.45 MB
• Nombre de pages
  15