Discussion inspirante pour les lycéens de dernière année

Mon département me demande souvent de donner des conférences aux élèves de dernière année du secondaire sur les éléments les plus mathématiques de l’informatique. Je fais de mon mieux pour choisir dans le SDC des sujets susceptibles de susciter leur intérêt (principalement en rapport avec le problème de l'arrêt), mais j'aimerais entendre les idées, les réussites et les échecs des autres.

Il s’agit des élèves qui envisagent de demander un diplôme de premier cycle en sciences dans une université décente, mais qui pourraient être davantage attirés par les mathématiques ou une autre des sciences. Je trouve que les sujets habituels des algorithmes du plus court chemin ou des méthodes de tri plus rapides ne fonctionnent plus vraiment pour piquer leur intérêt.

Il existe un moyen astucieux d'introduire des preuves de zéro connaissance auprès des étudiants, qui, je pense, est à l'origine due à Oded Goldreich (corrigez-moi si je me trompe).

Vous avez une boule rouge et une boule verte, qui, selon Charlie, est daltonien de la même couleur. Vous voulez convaincre Charlie que vous pouvez faire la différence entre la balle rouge et la balle verte, et vous voulez le faire de manière à ce que Charlie n'apprenne pas ce qui est rouge et ce qui est vert. (Vous voulez prouver que quelque chose est vrai, de manière à ce que personne d'autre ne puisse faire demi-tour et en demander la preuve.) Comment pouvez-vous faire cela? Ou est-ce impossible?

Un protocole est le suivant. Charlie met une balle dans chaque main, puis choisit d’échanger ou non les deux balles derrière lui. Puis il présente à nouveau les deux balles. Si vous pouvez toujours détecter s'il a échangé les deux balles ou non, alors Charlie est de plus en plus convaincu que vous pouvez faire la différence. Si Charlie le fait aléatoire au hasard et vous ne pouvez vraiment pas faire la différence entre les couleurs, alors vous ne devinez correctement avec une probabilité . Après k essais, Charlie doit être convaincu que vous pouvez faire la différence avec une probabilité au moins 1 - 1 / 2 k .$1/2$$k$$1-1/2^k$

Maintenant, alors que Charlie devient de plus en plus convaincu que vous pouvez faire la différence, il n’apprend jamais, frustré, quelle balle est rouge et laquelle est verte.

Une bonne source à des fins d'éducation en général est CS débranché , ce qui a beaucoup d'idées CS nettes traduites en haute école et l' école moyenne activités .

L'un des aspects les plus attrayants du SDC est la manière dont il utilise des idées mathématiques abstraites pour des applications pratiques quotidiennes. Une présentation peut se concentrer sur les idées abstraites qui se trouvent un pas en arrière par rapport à ce qu’elles voient quotidiennement sur Internet: Les chemins les plus courts deviennent excitants une fois qu’ils sont placés dans le contexte d’amis entre amis sur Facebook. Plus d'algorithmes graphiques peuvent être utilisés dans le PageRank. Les recommandations d'Amazon soulèvent le défi de l'apprentissage automatique. et acheter des choses sur Internet est certainement une bonne piste pour la crypto à clé publique.

Je pense que presque tous les sujets de l'informatique peuvent être utilisés pour donner une conférence intéressante, mais certains conviennent mieux, la partie la plus importante étant la présentation.

Côté amusant de l'informatique

J'ai utilisé divers jeux de la théorie des jeux combinatoires, principalement de "Fair Games" de Richard Guy et d'Elwyn R. Berlekamp, ​​John H. Conway et de "Moyens gagnants pour vos jeux mathématiques" ( wiki ).

Ils sont amusants et vous pouvez les jouer en classe avec eux et les laisser trouver le bon moyen de le jouer, de leur donner des indices afin qu’ils trouvent le moyen de gagner à la fin . Ces jeux sont probablement plus adaptés aux plus jeunes.

En informatique, il existe d’autres sujets amusants dans lesquels vous pouvez choisir un problème qui convient mieux à votre public et l’utiliser pour le faire participer.

Côté philosophique de l'informatique

Il existe de nombreux sujets en informatique théorique qui sont liés à la philosophie et aux grandes questions . Du théorème d'inachèvement de Gödel aux preuves à zéro connaissance, sécurité, confidentialité, théorie des jeux algorithmique, P vs NP, apprentissage automatique, ... je n'entrerais pas dans les détails, je démontrerais simplement que les problèmes sont intéressants, ils ne sont pas que de la science informatique , ils sont liés à de grandes questions. (Jetez un oeil à l' informatique quantique de Scott Aaronson depuis Démocrite et aux grandes idées de conférences théoriques en informatique ). Ne leur faites pas sentir que le sujet est mort (c’est-à-dire qu’on a répondu à toutes les questions), donnez-leur l’impression que la région est vivante, des progrès ont été accomplis, mais il reste encore de gros défis à relever, et c’est un voyage vers une terre inconnue.

Côté technologique de l'informatique

Parlez de l'informatique derrière les technologies. Vous pouvez choisir ici autant de sujets que ce soit des technologies connues , des jeux vidéo à la recherche Google, à la traduction automatique, à la vision,… des technologies que tout le monde utilise au quotidien, voire même des technologies inconnues. Parlez des technologies en cours et de la prochaine génération, de l'impact qu'elles ont eu sur nos vies et de la façon dont elles l'ont amélioré. Parlez des recherches en cours dans de grandes entreprises célèbres (telles que Google, Microsoft, Apple, IBM, ...) et des produits qu’elles développent. Parlez des gros problèmes de notre époque et de l’effet de la science informatique sur eux.

Côté mathématique de l'informatique

C’est bon pour les étudiants qui s’intéressent déjà aux mathématiques, ceux qui s’intéressent au côté pur et exact , mais sans le combiner avec un autre thème mentionné ci-dessus, il ne sera pas aussi efficace pour les autres étudiants. Je voudrais aller avec une grande question et à un moment donné mentionner commencer à parler de problèmes mathématiques impliqués.

Volet interdisciplinaire de l'informatique

L’informatique est probablement l’un des sujets les plus interdisciplinaires , il existe des liens avec presque tous les autres sujets, humanistes (sociologie, linguistique, économie, philosophie, ...), sciences naturelles (mathématiques, physique, ...), biologie, sciences médicales, art, ingénierie (électronique, mécanique, ...), ... n'importe quoi! Quel que soit le sujet qui vous intéresse, il y a quelque chose dans l'informatique qui y est lié! Comme Scott l'a dit, tous les autres grands gâchent par comparaison :).

Tous

Vous pouvez également essayer de mentionner tous les thèmes que j'ai mentionnés ci-dessus. Je n'ai pas essayé cela et je ne suis pas sûr de son efficacité. Vous devez transférer le sentiment et faire valoir le point, et cela prend parfois. Une autre option consiste à les mentionner tous brièvement au début (ou à la fin), puis de poursuivre avec l’un d’eux et de leur dire qu’ils peuvent vous contacter pour obtenir plus d’informations sur les autres s’ils sont intéressés.

certains commentaires

Quoi que vous parliez, vous devriez être enthousiaste à ce sujet. Il sera beaucoup plus difficile de les intéresser à un sujet qui ne vous intéresse pas vraiment. Parlez-leur de vos propres raisons de choisir l'informatique. Et ne soyez pas ennuyeux .

J'ai utilisé deux entretiens avec succès avec les deux lycéens et les étudiants de première année.

1. Origami. Je commence avec le problème des étoiles à 5 points (cela fonctionne bien dans les contextes américains, en raison de la connexion au drapeau américain) et laisse les étudiants essayer de trouver comment créer une étoile à cinq points avec pliage + 1 coupe. Je parle de la "ressource" (découpe) et de la façon dont la conception d'algorithmes consiste à travailler avec des ressources limitées. Ensuite, je parle d'autres questions et applications de l'origami dans le monde réel (valves cardiaques, télescopes de la NASA, zones de déformation des voitures).

2. Le tri des crêpes: Il existe un lien magnifique entre le tri des crêpes et le réarrangement du génome, et j’ai en fait fabriqué des piles de crêpes en mousse pour que les élèves puissent jouer avec. Fonctionne très bien et laisse-moi parler des algorithmes, du séquençage des gènes, de Bill Gates (!) Et d’autres choses amusantes.

La cryptographie est toujours quelque chose qui capture l’esprit des personnes plus jeunes (et j’espère personnellement plus âgées). J'avais des amis qui voulaient être assistants infirmiers, joueurs de hockey, hommes d'affaires, hommes d'affaires et politiciens et amis (malgré leurs objectifs élevés) occupant des emplois de baggers d'épicerie et de charrettes, de travailleurs de la construction et d'assistants de chenil - qui se sont tous inventés et se sont brisés » (certes naïf et simple) des codes. En particulier, l’existence d’une cryptographie à clé publique est généralement assez facile à expliquer si l’on prend la voie de la RSA. On pourrait également énumérer certains des résultats importants sans preuves ni constructions - les preuves Zéro-Connaissance et le cryptage homomorphique vont forcément ajouter du facteur geek à ce que cela vaut.

Les codes de correction d’erreur et de détection d’erreur sont également très intéressants et, s’ils le sont bien, ils peuvent être appris à un public curieux. Pour les rendre plus faciles à digérer, vous pouvez mentionner «l’universalité» de l’indice de coïncidence: tous les langages et écrits que nous parlons ont de petites redondances et des exagérations qui nous aident à communiquer dans le canal bruyant d’une pièce contenant des sacs, des pieds et des fredonnant les climatiseurs.

Enfin, je suggérerais également de faire une simple introduction à la théorie de la complexité - un peu dans la lignée de ma réponse à la description de l’informatique théorique par le dîner .

Le nouvel omnibus de Turing par AK Dewey propose 66 excursions dites en informatique. Il couvre des sujets tels que l'analyse des algorithmes, l'intelligence artificielle, la théorie de la complexité, la théorie du calcul, la cryptographie, l'infographie, etc. Chaque sujet est écrit sous une forme plutôt condensée, capturant un résultat historique en informatique. Ce livre pourrait fournir une inspiration.

Une autre possibilité est de permettre aux étudiants de se salir les mains via quelque chose comme le programme Code-in de Google . C'est un peu comme Summer of Code de Google , mais, vous le savez, pour les enfants. Peut-être qu’il serait peut-être intéressant de montrer certains des incroyables projets de codage auxquels les étudiants peuvent participer.

À mon avis, pour être sexy pour les lycéens, il faut être une sorte de magicien. C'est pourquoi je pense que les algorithmes randomisés sont très bons pour attirer les étudiants. Par exemple, le test de propriété est vraiment quelque chose d’intriguant, qui peut aussi être expliqué à n’importe qui (pas les détails techniques, mais l’idée).

Le PCP est aussi magique, mais j'imagine que c'est hors de portée ...

Voici un très bel article de Michael Mitzenmacher sur la théorie du codage destiné aux lycéens:

http://www.eecs.harvard.edu/~michaelm/FUTUREOFCS/codes-mitzenmacher.pdf

Ma réponse n’est pas directement liée au TCS, mais elle peut montrer que les mathématiques peuvent être belles et utiles.

Vous pouvez faire un discours sur la manière d'obtenir des données fiables sur le nombre d'étudiants qui trichent à l'examen. Si vous leur demandiez directement, vous n'auriez pas de données fiables. L'idée d'obtenir des données fiables est très simple. Vous dites d’abord à chaque élève de penser à un nombre entier, puis vous dites:
- Si c’était un nombre impair, écrivez si vous aimez la couleur verte ou non. Vous pouvez choisir n'importe quelle autre question simple, mais vous devez savoir, à partir d'une autre enquête, quel pourcentage de personnes répondent oui à cette question.
- S'il s'agissait d'un nombre pair, notez si vous avez triché ou non.

Environ 50% des étudiants vont répondre à la première question et les autres 50% vont répondre à la deuxième question. Maintenant, il est très facile d'estimer combien d'élèves ont triché. Exemple: Si 40% des réponses étaient oui et que vous savez que 30% des gens aiment la couleur verte, vous savez qu'environ 50% des étudiants trichaient.

Je pense que cela est étroitement lié à la description de l’informatique théorique par une table de dîner.

En postant ce poste, j’ai le sentiment que l’algorithmique concerne le mieux les problèmes de tous les jours et peut donc très bien motiver le SDC. ("Combien de temps une recherche sur Google prendrait-elle si elles cherchaient de la même manière que vous recherchez des numéros de téléphone")

Selon moi, "l'informatique" est la "science de toutes les sciences" :)

Qu'est ce que la science"? Nous obtenons des données de la nature et nous essayons de construire un modèle qui explique les données. En outre, nous supposons implicitement que la nature n’est pas arbitraire. Les lois de la nature doivent avoir une expression concise, les données doivent satisfaire certaines symétries, etc.

Mais c'est exactement un problème d'apprentissage! Les données sont générées par un processus dont la promesse est «peu complexe», et notre tâche est de reconstruire une description du processus.

Notre compréhension de tels problèmes est à un niveau si primitif qu'il est de votre devoir d'y travailler! :) Même notre compréhension du problème apparemment plus simple de savoir si le résultat d'un processus de boîte noire est équivalent à une fonction fixe est loin d'être complète. Par exemple, supposons qu'on nous promette que la boîte noire évalue une fonction qui peut être calculée par un circuit arithmétique de faible profondeur (ceci est facile à expliquer aux lycéens), et nous voulons savoir si la boîte est calculer la fonction zéro. Nous ne savons pas si cela peut être fait dans la vie de l'univers pour des fonctions sur des domaines de taille raisonnable!

Commencez à parler de la théorie de la complexité arithmétique, du gouffre en profondeur 4, du rôle de l’aléatoire dans le calcul, de ce que l’on sait si nous réduisons le nombre de portes de multiplication, etc., etc.

Dans l'atelier DIMACS sur les algorithmes sur le terrain il y a un mois, Graham Cormode plaidait en faveur de l'enseignement des techniques de dessin, des algorithmes de transmission en continu aux étudiants de premier cycle. Moses Charikar a déclaré qu'ils leur enseignaient à Princeton. Je pense que @Suresh Venkat a également mentionné qu'il enseigne des choses comme l'algorithme de Misra-Gries pour les gros frappeurs. Je pense que certains résultats de diffusion en continu seraient très utiles pour les étudiants du secondaire: ils s’appuient sur des astuces mathématiques simples mais importantes, les formulations de problèmes ressemblent à des énigmes, les solutions sont magiques et la magie est un excellent moyen d’inspirer les étudiants du secondaire. Assurez-vous de souligner la différence spectaculaire entre l’ampleur du problème et la quantité de ressources que vous pouvez utiliser. Un exemple ridicule: supposons que vous puissiez demander à chaque personne entrant ou sortant de l’aéroport JFK son code postal.