Enseignement du secondaire TCS - programmes existants

16

On m'a proposé d'enseigner un nouveau programme de lycée TCS, qui nécessite la construction d'un curriculum. J'aimerais beaucoup entendre des opinions et des suggestions à ce sujet.

Premièrement, quelqu'un connaît-il des écoles secondaires où un programme TCS a été enseigné avec succès (ou sans succès)?

L'idée est un programme de 3 ans (10e-12e années, 16-18 ans), environ 8 heures hebdomadaires, pour des étudiants exceptionnels sélectionnés, ce qui signifie qu'il peut et doit être exigeant. Contrairement au programme "informatique" standard, ce programme ne doit pas se concentrer sur la programmation, mais plutôt sur des sujets sélectionnés dans CS, principalement dans TCS. Jusqu'à présent, les sujets que nous avons à l'esprit sont:

  • Analyse asymptotique
  • Structures et algorithmes de données de base (listes, tableaux)
  • Algorithmes graphiques, également comme démonstration d'algorithmes gourmands vs programmation dynamique.
  • Autres algorithmes (par exemple probabilistes)
  • Calculabilité - le concept d'une MT, réduction, décidabilité.
  • Complexité - NP, P, peut-être PSPACE et NL. Complétude.
  • Théorie des automates

Fondamentalement, cela couvre la partie TCS des deux premières années d'un B.Sc en CS. Cependant, nous devons garder à l'esprit que ces élèves n'ont pas les bases mathématiques nécessaires pour la plupart de ce matériel. En particulier, des choses comme la théorie des ensembles, la combinatoire, la probabilité et l'artihmétique modulaire ne sont pas enseignées au lycée (malheureusement).

Pour résumer et poser des questions précises:

  1. Quelqu'un connaît-il un programme similaire quelque part?
  2. Y a-t-il des suggestions de sujets concrets / généraux qui, selon vous, peuvent et devraient être enseignés en plus / au lieu des sujets ci-dessus, tout en gardant le programme intéressant ainsi qu'important et directement pertinent (par exemple, la théorie de groupe est importante et intéressante, mais pas suffisamment pertinente) pour justifier le temps qu'il faudra)
  3. J'aurais été heureux d'introduire l'apprentissage automatique sous une forme ou une autre, car c'est un sujet vraiment brûlant de nos jours. Toutes les idées sur la façon dont l'apprentissage automatique peut être présenté sans outils tels que les théorèmes de mesure-concentration sont les bienvenues.
Shaull
la source
2
Il semble que vous listiez la théorie des automates à la fin comme une sorte de réflexion après coup. Je préconiserais de faire de la théorie des automates le thème central et fédérateur. Il peut initier les élèves au raisonnement mathématique formel sans aucune formation mathématique spécifique. Il a de forts théorèmes inconditionnels qui sont fondamentaux mais relativement simples à prouver. Il peut être directement lié à l'apprentissage automatique , bien que d'après mon expérience, il soit difficile d'enseigner aux étudiants de premier cycle dans un premier cours théorique, donc plus de prudence est requise avec HS.
Artem Kaznatcheev
1
personne n'en a entendu parler avant! étudiants "sélectionnés"? cela signifie-t-il également avancé, probablement? essayez d'explorer des livres scientifiques populaires sur TCS ou aussi des blogs en ligne [plusieurs bons là-bas]. Machines de Turing, calcul quantique autres domaines clés / intéressants. pense que cela pourrait être réalisé si les mathématiques ne sont pas lourdes et faites de manière plus conceptuelle que mathématique. aussi ce site revient beaucoup dans les questions edu: cs débranché . bonne chance!
vzn
2
Je me demande s'il serait préférable de consacrer une partie de votre temps à l'enseignement des compétences mathématiques que vous mentionnez (par exemple, la probabilité) ... cela pourrait également vous aider à couvrir des sujets plus avancés, mais aussi à préparer les étudiants à de futures études en mathématiques / cs .
Usul
1
@vzn - oui, ce sont des étudiants avancés (j'ose dire - doués).
Shaull
1
@vzn C'est une suggestion très intéressante. D'une certaine manière, TCS ne fait pas encore partie de la culture populaire. Autrement dit, même les étudiants curieux ne sont généralement pas au courant de questions telles que P vs NP. Mais nous allons certainement demander aux étudiants CS actuels des suggestions et voir ce qu'ils proposent. Je suppose que la cryptographie serait centrale.
Shaull

Réponses:

8

De nombreux pays organisent des écoles d'été pour leurs équipes IOI (composées d'élèves du secondaire âgés d'environ 16 ans de l'IIRC). Celui que nous avons en Iran avait l'habitude d'avoir les cours suivants:

  • programmation,
  • structure de données et algorithmes,
  • combinatoire, et
  • la théorie des graphes.

Je pense que l'Association des professeurs d'informatique d'ACM a un programme K12 sur sa page Ressources pédagogiques, bien qu'il soit probablement beaucoup trop léger pour les adolescents talentueux.


Je pense que la programmation doit définitivement faire partie du curriculum. Python devrait être une bonne première langue à apprendre.

Vous voudrez peut-être également couvrir certains sujets accessibles avec des applications (la joie de créer quelque chose de cool peut avoir un grand effet sur leur intérêt). Je pense que le cours ML d'Andrew Ng sur Coursera devrait être accessible aux étudiants talentueux (spécialement pour ceux dans des pays comme le vôtre où il existe un programme de mathématiques K12 plus sérieux).

Un sujet non standard que vous voudrez peut-être considérer est la théorie des jeux combinatoires, ce n'est peut-être pas très intéressant avec 16 ans (je n'ai pas d'expérience), mais cela fonctionne assez bien pour les étudiants un peu plus jeunes de mon expérience.

Personnellement, je pense que le thème central et de connexion devrait être autour des algorithmes, je pense que cela fonctionnerait mieux que la théorie des automates comme thème central et sans doute la perspective algorithmique (pas les machines de Turing, les automates, etc.) est l' essence de l'informatique.

Kaveh
la source
La partie programmation est couverte par le programme CS standard, qu'ils prennent tous. Ce sont des sujets supplémentaires. Avez-vous un lien vers un tel site Web d'école d'été? Quant à se concentrer sur les algorithmes - bien que je convienne qu'ils sont au cœur de CS, je pense que la calculabilité et la complexité sont également l' essence de l'informatique. Je me souviens avoir été beaucoup plus impressionné par le fait qu'il y a des choses que nous ne pouvons pas résoudre, plutôt que par des algorithmes intelligents. Mais les deux seront couverts, probablement.
Shaull
d'une certaine manière, les machines de Turing sont toutes des algorithmes . le rubis est également une excellente option comparable au python . sur le même sujet, une autre excellente option pour apprendre le développement est le javascript pour de nombreuses raisons, par exemple sa prolifération dans les navigateurs, beaucoup de code public / exemple, des fonctionnalités étendues, une utilisation élevée, etc.
vzn
1
@Shaull, ils ont un site ( Young Scholars Club ) mais il est en persan et ne contient pas grand-chose sur ce qui est couvert dans l'école d'été.
Kaveh
1
@vzn, je ne pense pas que vous ayez beaucoup d'expérience dans l'enseignement du TCS aux lycéens et je vous ai expliqué très clairement que je ne suis pas intéressé par vos opinions . Arrêtez de traquer mes réponses.
Kaveh
k, plz ne devinez pas mon bkg et fera la même courtoisie. le commentaire est essentiellement à l' appui de vos opinions ... sonne comme un sujet pour meta = (
vzn
5

Curieusement, il y a quelqu'un qui a fait valoir que l'apprentissage automatique est parfaitement adaptéparmi les sujets d'informatique à enseigner aux élèves du secondaire, car il est censé être l'un des rares sous-domaines où les mathématiques de base peuvent vous aider à comprendre suffisamment pour apprécier les défis importants. Je ne suis pas d'accord avec cette affirmation - les algorithmes de base (par exemple pour la recherche, le tri) peuvent être présentés comme des énigmes, et vous pouvez très rapidement passer à un état très simple à énoncer, mais des problèmes ouverts fondamentaux comme «la multiplication peut être effectuée avec essentiellement le même nombre d'opérations comme addition ", ou le tri d'entiers en temps linéaire, ou la factorisation (je suppose que le concept de nombres premiers ne serait pas nouveau pour le groupe restreint d'élèves du secondaire?). D'un autre côté, beaucoup d'apprentissage automatique serait difficile à saisir sans un bon niveau d'expérience en statistique et en théorie des probabilités. Cependant,

En termes de programme d'enseignement, il y en a un plus détaillé par Essinger et Rosen à Drexel.

En plus de cela, je pense que l'on peut tenter d'esquisser certaines des idées les plus avancées de la théorie de l'apprentissage:

  • quel est le problème de classification de base
  • qu'est-ce qu'une classe conceptuelle et que signifie apprendre un concept
  • pourquoi vous ne pouvez pas espérer apprendre des concepts à partir d'une classe de concepts sans restriction avec une complexité d'échantillonnage moins qu'exponentielle (comme introduction au comptage des arguments)
  • qu'est-ce que la dimension VC

Une autre suggestion est d'introduire des circuits et d'essayer une esquisse de la limite inférieure de Shannon. Cela dépend de la façon dont les élèves sont à l'aise avec le comptage. Si c'est trop lourd, cela pourrait tout de même aider à faire valoir l'argument tout en demandant aux élèves de compter eux-mêmes les circuits sur la foi. Je pense que l'idée de «la plupart des problèmes nécessitent de grands circuits car il y a trop de problèmes et trop peu de petits circuits» sera frappante. Cette idée est importante et omniprésente dans la complexité.

Sasho Nikolov
la source
Les deux suggestions sont très agréables. Merci! J'ai le sentiment que pour le lycée, juste apprendre ce qu'est une dimension VC pourrait prendre environ 3 mois, ce qui peut être trop. Mais cela vaut vraiment la peine d'être considéré, d'autant plus qu'on y a déjà pensé.
Shaull
Je pense que même juste pour comprendre ce que signifie apprendre un concept et avoir une vague idée que vous ne pouvez pas apprendre des choses arbitrairement compliquées avant que le soleil ne gèle sera une victoire.
Sasho Nikolov
3

voici une direction prometteuse pour aller dans ce sens. AP / NSF a récemment annoncé une nouvelle initiative du programme CS de placement avancé dans les écoles secondaires. il y aura de nombreux avantages à utiliser un tel programme, comme un plan de cours normalisé, l'accréditation d'un collège, etc.

il est en cours d'élaboration et devrait être prêt pour 2016. Le programme de cours provisoire et le matériel sont disponibles en ligne. (pour les experts universitaires, il pourrait même y avoir une possibilité à ce stade d'influencer le contenu futur via une collaboration de type «intelligence collective».)

Le programme de placement avancé du College Board a annoncé jeudi qu'il prévoyait d'ajouter un nouveau programme informatique à ses cours, le premier nouveau test en sept ans. Cette décision reflète un intérêt croissant pour la formation des étudiants à des carrières dans les sciences au milieu d'un effort national pour rendre l'économie américaine plus compétitive à l'échelle mondiale.

Le nouveau programme, AP Computer Science Principles, se concentrera sur les "aspects créatifs" de l'informatique et sera financé en partie par une subvention de 5,2 millions de dollars de la National Science Foundation. L'agence fédérale vise à former 10000 enseignants en informatique supplémentaires dans le même nombre d'écoles secondaires à l'échelle nationale d'ici 2016 dans le cadre d'un effort visant à améliorer l'enseignement dans les domaines des sciences, de la technologie, de l'ingénierie et des mathématiques, ou STEM. Le College Board sera dans environ ébrécher $ 3,5 millions de dollars pour le soutien des enseignants et de l' équipement.

le programme existant s'appelle AP Computer Science A et le nouveau programme s'appelle AP Computer Science Principles. la classe existante existe depuis de nombreuses années et est également utile en tant que modèle pour les enseignants développant un programme.

vzn
la source
3
Soit dit en passant, Baker Franke et moi-même avons soumis une proposition de session BOF (Birds-of-a-Feather) au SIGCSE '14 pour discuter de la façon de rendre les sujets théoriques accessibles au programme CS Principles.
rahulmehta95
@ rahulmehta95 - y a-t-il un lien vers la proposition que je peux lire?
Shaull
2
C'est parti : cs.ucls.uchicago.edu/~rahulmehta/papers/BOF-Theory.pdf . J'espère que cela t'aides!
rahulmehta95
2

Une idée que j'ai essayée récemment est de savoir comment enseigner aux étudiants HS la notion d'une réduction entre les problèmes. J'ai trouvé que c'était l'un des sujets les plus intéressants mais les plus difficiles quand j'ai été initié à la complexité, car il est assez difficile (au moins initialement) de se faire une idée du fait qu'un problème comme le 3-SAT est "tout aussi difficile" comme Vertex-Cover.

L'exemple que j'ai trouvé était une réduction entre Vertex Cover (VC) et Independent Set (IND-SET), formulée comme suit;

"Vous êtes le directeur d'un musée et vous êtes chargé d'embaucher des agents de sécurité pour garder les couloirs. Lorsqu'il est placé à une intersection de couloirs, un gardien peut surveiller TOUS les couloirs adjacents à lui. Quel est le nombre minimum de gardes nécessaires pour patrouiller l'ensemble du musée? "

"Un peu plus tard, certains enfants décident de jouer à cache-cache dans le musée. Leur objectif est de se cacher de sorte qu'aucun autre enfant ne puisse les voir. Cependant, les gardes ne veulent pas qu'ils courent dans le couloirs, donc ils sont relégués à "se cacher" dans les intersections. Quel est le plus grand nombre d'enfants qui peuvent se cacher dans le musée sans se voir? "

VCPIND-SET

g=(V,E)SV est un ensemble indépendant VS désigne la différence d'ensemble).

La raison pour laquelle j'ai choisi VC & IND-SET est qu'il n'est pas trop difficile de voir que les problèmes sont étroitement liés; chaque fois qu'il y a un ensemble indépendantS, il induit une couverture vertex VS dans g.

rahulmehta95
la source
Bien que je comprenne la motivation derrière l'exemple (très agréable), je pense que dans HS, je commencerais par les réductions de Turing, qui sont beaucoup plus intuitives. De plus, je commencerais par un problème où l'entrée doit être vraiment manipulée, et pas seulement un changement de paramètre. Par exemple, je commencerais parCLjeQUEpjeN-SET, qui est plus "impliqué".
Shaull
en ce qui concerne les réductions, la preuve qu'il existe une machine de turing universelle est un chemin à parcourir et probablement compréhensible par les lycéens avancés ... [notez qu'il existe de nombreuses vidéos lego TM, certaines même par des chercheurs cs ...] aussi, peut-être la transformation de la tséitine ?
vzn