Remerciez-le!

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

Exercices et solutions 2017 Années HarmoS 11/12 http://www.castor-informatique.

Exercices et solutions 2017 Années HarmoS 11/12 http://www.castor-informatique.ch/ Éditeurs : Julien Ragot, Gabriel Parriaux, Jean-Philippe Pellet, Nicole Müller, Christian Datzko, Hanspeter Erni Ont collaboré au Castor Informatique 2017 Ont collaboré au Castor Informatique 2017 Andrea Adamoli, Christian Datzko, Susanne Datzko, Olivier Ens, Hanspeter Erni, Martin Guggis- berg, Per Matzinger, Carla Monaco, Nicole Müller, Gabriel Parriaux, Jean-Philippe Pellet, Julien Ragot, Silvan Stöckli, Beat Trachsler. Nous adressons nos remerciements à : Juraj Hromkovič, Giovanni Seraﬁni, Urs Hauser, Regula Lacher, Ivana Kosírová : ETHZ Valentina Dagien˙ e : Bebras.org Hans-Werner Hein, Wolfgang Pohl : Bundesweite Informatikwettbewerbe (BWINF), Allemagne Anna Morpurgo, Violetta Lonati, Mattia Monga : Italie Gerald Futschek, Wilfried Baumann : Austrian Computer Society, Austria Zsuzsa Pluhár : ELTE Informatikai Kar, Hongrie Eljakim Schrijvers, Daphne Blokhuis : Eljakim Information Technology bv, Pays-Bas Roman Hartmann : hartmannGestaltung (Flyer Castor Informatique Suisse) Christoph Frei : Chragokyberneticks (Logo Castor Informatique Suisse) Pamela Aeschlimann, Andreas Hieber, Aram Loosmann, Daniel Vuille, Peter Zurﬂüh : Lernetz.ch (page web) Andrea Leu, Maggie Winter, Brigitte Maurer : Senarclens Leu + Partner La version allemande des exercices a également été utilisée en Allemagne et en Autriche. L’adaptation française a été réalisée par Nicole Müller et la version italienne par Andrea Adamoli. Le Castor Informatique 2017 a été réalisé par la Société Suisse de l’Informatique dans l’Enseignement SSIE. Le Castor Informatique est un projet de la SSIE, aimablement soutenu par la Fondation Hasler. Tous les liens ont été vériﬁés le 1er novembre 2017. Ce cahier d’exercice a été produit le 9 octobre 2019 avec avec le logiciel de mise en page L AT EX. Les exercices sont protégés par une licence Creative Commons Paternité – Pas d’Utilisation Commerciale – Partage dans les Mêmes Conditions 4.0 Interna- tional. Les auteurs sont cités p. 40. © Castor Informatique 2017, SSIE i Préambule Préambule Très bien établi dans diﬀérents pays européens depuis plusieurs années, le concours «Castor Infor- matique» a pour but d’éveiller l’intérêt des enfants et des jeunes pour l’informatique. En Suisse, le concours est organisé en allemand, en français et en italien par la SSIE, la Société Suisse pour l’Informatique dans l’Enseignement, et soutenu par la Fondation Hasler dans le cadre du programme d’encouragement «FIT in IT». Le Castor Informatique est le partenaire suisse du concours «Bebras International Contest on Infor- matics and Computer Fluency» (http://www.bebras.org/), initié en Lituanie. Le concours a été organisé pour la première fois en Suisse en 2010. Le Petit Castor (années HarmoS 5 et 6) a été organisé pour la première fois en 2012. Le Castor Informatique vise à motiver les élèves à apprendre l’informatique. Il souhaite lever les réticences et susciter l’intérêt quant à l’enseignement de l’informatique à l’école. Le concours ne suppose aucun prérequis quant à l’utilisation des ordinateurs, sauf de savoir naviguer sur Internet, car le concours s’eﬀectue en ligne. Pour répondre, il faut structurer sa pensée, faire preuve de logique mais aussi de fantaisie. Les exercices sont expressément conçus pour développer un intérêt durable pour l’informatique, au-delà de la durée du concours. Le concours Castor Informatique 2017 a été fait pour cinq tranches d’âge, basées sur les années scolaires : — Années HarmoS 5 et 6 (Petit Castor) — Années HarmoS 7 et 8 — Années HarmoS 9 et 10 — Années HarmoS 11 et 12 — Années HarmoS 13 à 15 Les élèves des années HarmoS 5 et 6 avaient 9 exercices à résoudre (3 faciles, 3 moyens, 3 diﬃciles). Chaque autre tranche d’âge devait résoudre 15 exercices (5 faciles, 5 moyens et 5 diﬃciles). Chaque réponse correcte donnait des points, chaque réponse fausse réduisait le total des points. Ne pas répondre à une question n’avait aucune incidence sur le nombre de points. Le nombre de points de chaque exercice était ﬁxé en fonction du degré de diﬃculté : Facile Moyen Diﬃcile Réponse correcte 6 points 9 points 12 points Réponse fausse −2 points −3 points −4 points Utilisé au niveau international, ce système de distribution des points est conçu pour limiter le succès en cas de réponses données au hasard. Les participants disposaient de 45 points (Petit Castor 27) sur leur compte au début du concours. Le maximum de points possibles était de 180 points (Petit Castor 108), le minimum étant de 0 point. Les réponses de nombreux exercices étaient aﬃchées dans un ordre établi au hasard. Certains exer- cices ont été traités par plusieurs tranches d’âge. Pour de plus amples informations : SVIA-SSIE-SSII (Société Suisse de l’Informatique dans l’Enseignement) Castor Informatique Julien Ragot castor@castor-informatique.ch http://www.castor-informatique.ch/ https://www.facebook.com/informatikbiberch ii © Castor Informatique 2017, SSIE Table des matières Table des matières Ont collaboré au Castor Informatique 2017 i Préambule ii 1. Honomakato 1 2. Un art martial japonais 5 3. La ville riche en ronds-points 7 4. Une commande chiﬀrée 9 5. Jeu des pièces 11 6. Bar à jus de fruits 13 7. Des jeux de lumière 17 8. Substitutions 19 9. Sors du labyrinthe ! 21 10.Jeu de billes 23 11.À table, mais vite ! 27 12.Aide l’Arabot ! 31 13.Les piles de cure-dents à diviser 33 14.Calculer la distance entre les mots 35 15.Des téléchargements en parallèle 37 A. Auteurs des exercices 40 B. Sponsoring : Concours 2017 41 C. Oﬀres ultérieures 43 © Castor Informatique 2017, SSIE iii Honomakato (7/8H: diﬃcile; 9/10H: moyen; 11/12H: facile) 1. Honomakato L’archipel Honomakato est formé de cinq îles Ho, No, Ma, Ka et To. L’île principale Ho est connectée à Internet par un câble. En outre, quelques câbles parcourent les îles Ho et No, Ho et Ka, Ka et Ma ainsi que Ka et To. Toutes les îles sont donc connectées à l’île principale Ho et par conséquent à Internet. Les habitants de Honomakato demandent une connexion ﬁable à Internet pour toutes les îles : cela veut dire que même si un des câbles est endommagé, chacune des îles doit avoir accès à Internet. Fais en sorte que l’archipel Honomakato obtienne une connexion ﬁable à Internet. Pose deux autres câbles entre les îles. Il existe plusieurs solutions possibles. © Castor Informatique 2017, SSIE 2017-DE-06a 1 (7/8H: diﬃcile; 9/10H: moyen; 11/12H: facile) Honomakato Solution En posant deux autres câbles, l’archipel Honomakato obtient une connexion ﬁable à Internet. Pour résoudre notre problème, il existe six possibilités diﬀérentes. Les câbles posés préservent les îles du moment inopportun où elles n’auraient plus accès à Internet si un câble était endommagé. 1. Ho-Ma et No-To : Ho-Ma préserve Ma und Ka, No-To préserve No und To. 2. Ho-To et No-Ma : Ho-To préserve To et Ka, No-Ma préserve Ma, No, et Ka. 3. No-To et No-Ma : No-To préserve No, To et Ka, No-Ma préserve Ma, No, et Ka. 4. No-To et Ma-To : No-To préserve No, To et Ka, Ma-To préserve Ma et To. 5. No-Ka et Ma-To : No-Ka préserve No et Ka, Ma-To préserve Ma et To. 6. No-Ma et Ma-To : No-Ma préserve Ma, No, et Ka, Ma-To préserve Ma et To. En général, pour chaque solution, les règles suivantes doivent être respectées : (1) chaque île est équipée d’au moins deux connexions et (2) il n’est pas possible de diviser l’archipel Honomakato en deux groupes qui n’ont qu’une seule connexion. C’est de l’informatique ! D’une part, le réseau de câbles avec lequel l’archipel Honomakato est connecté à Internet ne re- présente qu’une petite partie du réseau global. D’autre part, il sert aussi d’exemple pour montrer comment le réseau global est construit. Les routers, les serveurs et les autres dispositifs télématiques pourvus d’une propre adresse Internet sont des nœuds d’un grand réseau global appelé «Internet» ; dans notre tâche, les îles de l’archipel Honomakato représentent justement ces nœuds. Internet a été conçu dans les années 1960 comme un réseau robuste (appelé aussi «ﬁable»). Un des objectifs était qu’une panne de connexion entre les nœuds de réseau ne provoquerait pas une panne dans le réseau entier. C’est la raison pour laquelle on connecte les nœuds de manière multiple et on les 2 2017-DE-06a © Castor Informatique 2017, SSIE Honomakato (7/8H: diﬃcile; 9/10H: moyen; 11/12H: facile) conﬁgure de façon à ce que, en cas de défaillance ou congestion d’une connexion, on ait la possibilité de recourir à une autre connexion. Cette précaution est également importante pour d’autres réseaux, comme par exemple pour les réseaux de transport ou les réseaux d’approvisionnement. En informatique, on utilise la théorie des graphes pour eﬀectuer des calculs concernant ces types de réseaux. Un graphe (en théorie des graphes) est un réseau qui se compose de «points» appelés des nœuds ou sommets et de «liens» entre les nœuds appelés des arêtes. Un graphe est appelé «connexe» lorsque pour chaque paire de nœuds A et B, B est connecté avec A à travers au moins une arête. Une seule arête est donc nécessaire pour qu’un graphe soit connecté et dans ce cas-là, l’arête assume la fonction d’un pont. En informatique, on développe des algorithmes qui sont capables de repérer ces ponts à l’intérieur des graphes. Robert Tarjan a développé un de ces algorithmes (eﬃcaces). Mots clés et sites web structure de données dynamique, graphe, pont uploads/Science et Technologie/ castor-informatique-2017-anneesscolaires9-10-avecsolutions.pdf