[PDF](+53👁️) Télécharger [ Gilles Dowek Et Al.] Informatique Et Sciences Du ( Book ZZ.org) pdf
Informatique et sciences du numérique
Télécharger gratuit [ 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 Or Y = B
Then "En vue"
El se "À l 'eau"
IfEnd
IfEnd
jpyright © 2012 Eyrolles.
Première partie - Langages
De même, exécuter l’instruction y = Isn. readlntO ; a pour effet d’inter-
rompre 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 y. À ce
point du programme, les boîtes de nom a, b, x et y contiennent chacune un
nombre. Les nombres 4 et 7 pour les deux premières et les deux nombres
entrés au clavier par l’utilisateur pour les deux dernières.
a b UU
L’exécution du programme doit alors différer selon que les deux nombres
donnés par l’utilisateur sont 4 et 7 ou non. Si c’est le cas, on veut afficher
Coulé, si ce n’est pas le cas on veut faire autre chose. C’est ce que fait
l'instruction :
if (x == a && y == b) {
System . out . pri ntl n("Coul é") ; }
else {
i f (x = a || y == b) {
System. out . pri ntl n("En vue") ; }
el se {
System. out. pri ntln("À 1 'eau") ;}}
Exécuter cette instruction a pour effet de calculer la valeur de l’expres-
sion booléenne x == a && y == b, où le symbole && représente un et.
Cette valeur est true (vrai) quand x est égal à a et y est égal à b, ou fal se
(faux) quand ce n’est pas le cas. En fonction de la valeur de cette expres-
sion, on exécute ou bien l’instruction System. out. pri ntln("Coulé") ; ou
bien l’instruction :
if (x == a | | y — b) {
System. out. println("En vue");}
else {
System. out. println("À 1 'eau") ;}
Cette instruction étant de la même forme, son exécution a pour effet de
calculer la valeur de l’expression booléenne x == a | | y == b, où le sym-
bole | | représente un ou, et en fonction de la valeur de cette expression
d’exécuter ou bien l’instruction System. out . printlnC’En vue") ; ou bien
l’instruction System. out. pri ntln("À 1 ’eau") ;.
)pyright © 2012 Eyrolles.
1 - Les ingrédients des programmes
Exercice 1.3
En C, le même extrait de programme s'écrit ainsi :
a = 4;
b = 7;
printf("À vous de jouer\n");
scanf ("%d" ,&x) ;
scanf ("%d" ,&y) ;
i f (x == a && y == b) {
pri ntf ("Cou! é\n") ; }
else {
if (x == a | | y == b) {
printfC’En vue\n");}
else {
printf("À l'eau\n");}}
Quelles sont les ressemblances et les différences entre Java et C ?
Savoir-faire Modifier un programme existant pour obtenir
un résultat différent
L’intérêt de partir d’un programme existant est qu’il n’est pas toujours nécessaire d’en
comprendre le fonctionnement en détail pour l’adapter à un nouveau besoin.
Il importe avant tout :
• d’identifier les parties du programme qui doivent être modifiées et celles qui
sont à conserver,
• de les modifier en conséquence,
• éventuellement d’adapter les entrées et les sorties au nouveau programme,
• et, comme toujours, de le tester sur des exemples bien choisis.
Exercice 1.4 (avec corrigé)
Le programme suivant permet de calculer le prix toutes taxes comprises d'un
article, connaissant son prix hors taxes, dans le cas où le taux de TVA est de
19,6%.
System. out. pri ntl n ("Quel est le prix hors taxes ?") ;
ht = Isn. readDoubleO ;
ttc = ht + ht * 19.6 / 100.0;
System. out. print("Le prix toutes taxes comprises est ") ;
System . out .pri ntl n (ttc) ;
Adapter ce programme pour permettre à l'utilisateur de choisir le taux de TVA.
Même si l'on n’est pas un expert en calcul de pourcentages, on identifie facile-
ment qu'il faut remplacer le 19.6 de la troisième ligne par un taux quelconque.
Pour que ce taux puisse être choisi par l'utilisateur, il doit être stocké dans une
nouvelle boite : appelons-la taux. Le contenu de cette boîte doit être saisi au
jpyright © 2012 Eyrolles.
Première partie - Langages
clavier. Il faut donc prévoir l'entrée correspondante. Voici donc le nouveau pro-
gramme avec, en gras, les éléments ajoutés ou modifiés :
System. out.print1n("Quel est le prix hors taxes ?") ;
ht = Isn. readDoubieO ;
System. out.print1n("Quel est le taux de TVA ?") ;
taux = Isn. readDoubleO ;
ttc = ht + ht * taux / 100.0;
System. out. pri nt("Le prix toutes taxes comprises est ");
System. out.pri ntl n (ttc) ;
Exercice 1.5
En gé
Lire la suite
- 65.45 MB
- 15
Vous recherchez le terme ""
53
28
36
