Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

L’informatique sans ordinateur Parties IV, V et VI Programme d’enrichissement e

L’informatique sans ordinateur Parties IV, V et VI Programme d’enrichissement et d’approfondissement pour les élèves du primaire et du collège Created by Tim Bell, Ian H. Witten and Mike Fellows Adapted for classroom use by Robyn Adams and Jane McKenzie Illustrated by Matt Powell An enrichment and extension programme for primary-aged children Créé par Tim Bell, Ian H. Witten et Mike Fellows Adapté à l’utilisation en classe par Isaac Freeman à partir du travail de Robyn Adams et Jane McKenzie Illustrations de Malcolm Robinson, Gail Williams, Matt Powell et Isaac Freeman ______________________________________________________________________________________________ CC BY-NC-SA Computer Science Unplugged (csunplugged.org) 2012-2015 107 Introduction Cet ouvrage présente huit activités qui viennent compléter le livre de l’enseignant de Computer Science Unplugged. Elles figuraient déjà dans l’édition originale de 1999 mais sont ici adaptées à une utilisation en classe dans le même esprit que l’édition 2002 du livre de l’enseignant. Cet ouvrage destiné à un usage personnel et éducatif est disponible en téléchargement libre grâce à la participation généreuse de Google Inc. Il est distribué sous une licence Creative Commons Attribution – Pas d’utilisation commerciale – Partage dans les mêmes conditions, ce qui signifie que vous êtes libres de reproduire, distribuer et communiquer ce manuel, ainsi que de le modifier ou de l’adapter, dans les conditions suivantes : vous devez indiquer le nom des auteurs de la version originale, ne pas l’utiliser à des fins commerciales, et si vous le modifiez ou l’adaptez, partager le résultat sous la même licence. Pour plus d’informations sur cette licence, recherchez sur le Web CC BY-NC-SA 3.0. Nous encourageons son utilisation dans un contexte pédagogique, nous vous invitons à l’imprimer pour vos propres besoins et à distribuer les exercices à vos élèves. Toutes les remarques ou suggestions sont les bienvenues. Veuillez les adresser directement aux auteurs (cf. csunplugged.org). Ce manuel est traduit de l’anglais en plusieurs langues. Merci de consulter le site Web pour toutes informations relatives à la disponibilité des traductions. La version française a été coordonnée par l’équipe d’Interstices https://interstices.info et la mission de médiation scientifique d’Inria. Merci à Laurent Théry et Samuel Chalifour pour leur relecture attentive. ______________________________________________________________________________________________ 108 CC BY-NC-SA Computer Science Unplugged (csunplugged.org) 2012-2015. Sommaire Les problèmes vraiment difficiles—L'intraitabilité .............................................................. 109 Le cartographe sans le sou—Coloration de graphes ........................................................ 112 Touristeville—Ensembles dominants .............................................................................. 125 Les routes de glace—Arbres de Steiner ........................................................................... 133 Partager des secrets et lutter contre la criminalité—La cryptographie ............................. 144 Partager des secrets—Protocoles de protection des données .......................................... 148 Le pile ou face péruvien—Protocoles cryptographiques ................................................. 152 Les cryptographes en herbe—Chiffrement à clé publique .............................................. 162 Le visage humain de l'informatique—Interagir avec les ordinateurs ................................ 172 La chocolaterie—Conception d'interfaces utilisateurs .................................................... 175 Dialoguer avec les ordinateurs—Test de Turing ............................................................. 187 Partie IV Les problèmes vraiment difficiles — L’intraitabilité ______________________________________________________________________________________________ 110 CC BY-NC-SA Computer Science Unplugged (csunplugged.org) 2012-2015 L’intraitabilité Certains problèmes sont-ils trop difficiles, même pour les ordinateurs ? La réponse est oui. Nous verrons dans l’Activité 20 que le simple fait de bavarder, de converser, est une chose impossible à faire pour les ordinateurs, non pas parce qu’ils sont incapables de parler, mais parce qu’ils ne peuvent pas comprendre ni dire des choses sensées. Les problèmes sur lesquels nous allons nous pencher ne concernent pas tant l’incapacité des ordinateurs à bavarder que notre propre incapacité à comprendre comment nous le faisons, et donc à expliquer à l’ordinateur comment le faire. Dans cette partie, toutefois, nous allons nous pencher sur des problèmes où il est facile de donner des ordres à l’ordinateur, en le programmant, mais où ce dernier ne peut pas accomplir la tâche en question parce que cela prendrait beaucoup trop de temps, peut-être des millions de siècles. Se procurer un ordinateur plus performant ne servirait pas à grand-chose : même cent fois plus rapide, il lui faudrait encore des millions d’années pour accomplir la tâche ; et même un million de fois plus rapide, il lui faudrait des centaines d’années. Un problème que même l’ordinateur le plus rapide imaginable mettrait plus d’une vie humaine à résoudre, voilà ce qu’on appelle un problème difficile ! Les activités de la Partie II sur les algorithmes vous ont montré comment améliorer l’efficacité des programmes informatiques. Nous allons aborder ici des problèmes pour lesquels aucune solution efficace n’est connue à ce jour, des problèmes qu’un ordinateur mettrait des millions de siècles à résoudre. Nous découvrirons ce qui constitue sans doute le plus grand mystère de la science informatique actuelle : nul ne sait s’il existe une manière plus efficace de résoudre ces problèmes ! Peut-être simplement que personne n’a encore trouvé la bonne méthode, ou peut-être que la bonne méthode n’existe pas… Il est impossible de le savoir. Et ce n’est pas tout. Il existe des milliers de problèmes qui, bien que totalement différents en apparence, sont équivalents au sens où si une méthode efficace était trouvée pour résoudre l’un d’eux, on pourrait l’adapter pour résoudre tous les autres. Ce sont ces problèmes que vous découvrirez dans les activités suivantes. Pour les enseignants Cette partie regroupe trois activités. Dans la première, il s’agit de colorier des cartes géographiques en déterminant le nombre de couleurs nécessaires pour que tous les pays limitrophes soient différents. Dans la deuxième, il faut savoir utiliser un plan de ville simple pour placer les camions des marchands de glaces à certains coins de rue, le but étant que personne n’ait trop de chemin à parcourir pour acheter une glace. La troisième est une activité de plein-air où l’on apprend à construire, à l’aide de ficelles et de piquets, des réseaux courts reliant un ensemble de points. Ces activités permettent d’appréhender concrètement l’idée de complexité, c’est-à-dire le fait que des problèmes très simples à énoncer puissent s’avérer incroyablement difficiles à résoudre. Ces problèmes ne sont pas incompréhensibles : il s’agit de questions pratiques que l’on rencontre dans des activités aussi courantes que la création de cartes géographiques, d’itinéraires ou d’emplois du temps. La notion informatique qui les sous- tend, appelée « NP-complétude », est expliquée dans la section « Ce qu'il faut retenir » qui suit chaque activité. Bien que les activités elles-mêmes puissent être réalisées dans n’importe quel ordre, ces dernières sections doivent être lues dans leur ordre d’apparition. Une fois arrivé à la fin, vous aurez compris ce qui constitue la plus grande question ouverte de l’informatique contemporaine. ______________________________________________________________________________________________ CC BY-NC-SA Computer Science Unplugged (csunplugged.org) 2012-2015. 111 Le terme technique définissant les problèmes insolubles en pratique est « intraitabilité ». Il provient du latin tractare, « tirer », « traîner ». Ce concept définit donc des problèmes difficiles à appréhender parce que leur résolution demanderait trop de temps. Sous ses dehors abscons, le concept d’« intraitabilité » revêt un grand intérêt pratique. Une découverte dans ce domaine aurait en effet des répercussions majeures dans de nombreux axes de recherche. La plupart des systèmes cryptographiques, par exemple, sont fondés sur l’« intraitabilité » de certains problèmes. Un criminel qui trouverait une solution efficace pourrait donc faire fortune en décodant des informations secrètes et en les revendant, ou plus simplement, en réalisant de fausses transactions bancaires. Nous aborderons ce sujet dans la Partie V, intitulée « Cryptographie ». ______________________________________________________________________________________________ 112 CC BY-NC-SA Computer Science Unplugged (csunplugged.org) 2012-2015. Activité 13 Le cartographe sans le sou — Coloration de graphes Résumé Souvent, les problèmes d’optimisation sont liés à des situations dans lesquelles certains événements ne peuvent être simultanés, ou dans lesquelles certains éléments d’un ensemble d’objets ne peuvent être adjacents. Quiconque a déjà essayé d’établir un emploi du temps scolaire ou de fixer une date de réunion, par exemple, sait combien il est difficile de répondre aux contraintes de toutes les personnes impliquées. Bon nombre de ces difficultés s’apparentent au problème du coloriage des cartes, où deux pays limitrophes ne doivent jamais être de la même couleur. Cette activité porte précisément sur ce problème. Liens pédagogiques  Mathématiques : nombres. Étudier les nombres dans d’autres bases. Représenter les nombres en base 2  Mathématiques : algèbre. Continuer une séquence, décrire la règle qui la définit. Séquences et relations en puissance de 2 Compétences  Résolution de problèmes  Raisonnement logique  Procédures algorithmiques et complexité  Communication des idées Âge  7 ans et plus Matériel  Un tableau Pour chaque élève :  Une copie d’une ou plusieurs fiches d’activité  De petits éléments mobiles de couleur (jetons ou autres)  Quatre crayons ou feutres de couleurs différentes ______________________________________________________________________________________________ CC BY-NC-SA Computer Science Unplugged (csunplugged.org) 2012-2015 113 Coloration de graphes Introduction Dans cette activité, les élèves sont chargés d’aider un cartographe (quelqu'un qui fabrique des cartes géographiques) à colorier les pays d’une carte. La couleur attribuée à chaque pays importe peu, l’essentiel étant qu’elle soit différente de celle des pays limitrophes. Prenons pour exemple cette carte qui représente quatre pays. Si on colorie le Nord en rouge, alors l’Ouest et l’Est ne peuvent pas être en rouge parce qu’il serait difficile de distinguer leur frontière avec le Nord. On pourrait donc colorier l’Ouest en vert, et il serait alors aussi possible uploads/Litterature/ csunplugged-part2-fr.pdf