Enseñanza de TCS de secundaria - programas existentes

Me ofrecieron enseñar un nuevo programa de escuela secundaria TCS, que requiere la construcción de un plan de estudios. Me gustaría mucho escuchar opiniones y sugerencias sobre esto.

Primero, ¿alguien sabe de las escuelas secundarias donde se ha enseñado un programa TCS con éxito (o sin éxito)?

La idea es un programa de 3 años (grados 10-12, edades 16-18), aproximadamente 8 horas semanales, para estudiantes sobresalientes seleccionados, lo que significa que puede y debe ser exigente. A diferencia del programa estándar de "computadoras", este programa no debe enfocarse en la programación, sino en temas seleccionados en CS, principalmente en TCS. Los temas que tenemos en mente hasta ahora son, en general:

• Análisis asintótico
• Estructuras de datos y algoritmos básicos (listas, matrices)
• Algoritmos gráficos, también como demostración de algoritmos codiciosos frente a programación dinámica
• Otros algoritmos (por ejemplo, probabilístico)
• Computabilidad: el concepto de TM, reducción, capacidad de decisión.
• Complejidad: NP, P, quizás PSPACE y NL. Lo completo.
• Teoría de autómatas

Básicamente, esto cubre la parte TCS de los primeros dos años de un B.Sc en CS. Sin embargo, debemos tener en cuenta que estos estudiantes carecen de la base matemática necesaria para la mayor parte de este material. En particular, cosas como la teoría de conjuntos, la combinatoria, la probabilidad y la técnica modular no se enseñan en la escuela secundaria (desafortunadamente).

Para resumir y dar preguntas precisas:

1. ¿Alguien sabe de un programa similar en alguna parte?
2. ¿Hay sugerencias para temas concretos / generales que crees que pueden y deberían enseñarse además / en lugar de los temas anteriores, mientras se mantiene el programa interesante, así como importante y directamente relevante (por ejemplo, la teoría de grupo es importante e interesante, pero no lo suficientemente relevante para justificar el tiempo que llevará)
3. Me hubiera encantado presentar el aprendizaje automático de alguna forma, ya que es un tema muy candente en la actualidad. Cualquier idea sobre cómo se puede presentar el aprendizaje automático sin herramientas como los teoremas de concentración-medida es bienvenida.

Muchos países organizan escuelas de verano para sus equipos de IOI (que consisten en estudiantes de secundaria de aproximadamente 16 años IIRC). El que tenemos en Irán solía tener los siguientes cursos:

• programación,
• estructura de datos y algoritmos,
• combinatoria, y
• Teoría de grafos.

Creo que la Asociación de Maestros de Ciencias de la Computación de ACM tiene un currículo K12 en su página de Recursos Curriculares , aunque probablemente sea demasiado ligero para adolescentes con talento.

Creo que la programación definitivamente debe ser parte del plan de estudios. Python debería ser un buen primer idioma para aprender.

Es posible que también desee cubrir algunos temas accesibles con aplicaciones (la alegría de construir algo genial puede tener un gran efecto en su interés). Creo que el curso de ML de Andrew Ng sobre Coursera debería ser accesible para estudiantes talentosos (especialmente para aquellos en países como el suyo donde hay un plan de estudios de matemáticas K12 más serio).

Un tema no estándar que es posible que desee considerar es la teoría de juegos combinacionales, puede que no sea muy interesante con 16 años (no tengo experiencia para ello), pero en mi experiencia funciona bastante bien para estudiantes un poco más jóvenes.

Personalmente, creo que el tema central y de conexión debería estar relacionado con los algoritmos, creo que funcionaría mejor que la teoría de autómatas como tema central y podría decirse que la perspectiva algorítmica (no las máquinas de Turing, los autómatas, etc.) es la esencia de la informática.

Curiosamente, hay alguien que argumentó que el aprendizaje automático es únicoentre los temas de ciencias de la computación para enseñar a los estudiantes de secundaria, porque supuestamente es uno de los pocos subcampos donde las matemáticas básicas pueden hacerte entender lo suficiente como para apreciar los desafíos importantes. No estoy de acuerdo con esta afirmación: los algoritmos básicos (por ejemplo, para buscar, ordenar) se pueden presentar como acertijos, y puedes llegar muy rápidamente a un estado muy simple, pero los problemas abiertos fundamentales como "se puede hacer la multiplicación esencialmente con el mismo número de operaciones como suma ", o ordenando enteros en tiempo lineal, o factorizando (supongo que el concepto de números primos no sería nuevo para el grupo selecto de estudiantes de secundaria?). Por otro lado, una gran cantidad de aprendizaje automático sería difícil de comprender sin un buen nivel de experiencia en estadística y teoría de la probabilidad. Sin embargo,

En términos de un programa de enseñanza, hay uno más detallado de Essinger y Rosen en Drexel.

Además de estos, creo que se puede intentar esbozar algunas de las ideas de alto nivel de la teoría del aprendizaje:

• ¿Cuál es el problema básico de clasificación?
• ¿Qué es una clase de concepto y qué significa aprender un concepto?
• por qué no puede esperar aprender conceptos de una clase de concepto sin restricciones con una complejidad de muestreo menor que exponencial (como introducción a los argumentos de conteo)
• ¿Qué es la dimensión VC?

Otra sugerencia es introducir circuitos e intentar un bosquejo del límite inferior de Shannon. Depende de lo cómodos que estén los estudiantes con el conteo. Si esto es demasiado pesado, aún podría ser útil argumentar mientras los estudiantes toman el conteo de los circuitos por fe. Creo que la idea de "la mayoría de los problemas requieren circuitos grandes porque hay demasiados problemas y muy pocos circuitos pequeños" será sorprendente. Esta idea es importante y penetrante en complejidad.

Heres una dirección prometedora para ir en esto. AP / NSF anunció recientemente una nueva iniciativa del programa CS de colocación avanzada en la escuela secundaria. Habrá muchas ventajas al usar un programa como un plan de lecciones estandarizado, acreditación universitaria, etc.

Actualmente está en desarrollo y estará listo para 2016. El programa de estudios y los materiales del curso provisional están disponibles en línea. (para los expertos académicos, incluso podría haber alguna posibilidad en este punto de influir en el contenido futuro a través de la colaboración de tipo "inteligencia colectiva").

El Programa de Colocación Avanzada del College Board dijo el jueves que planea agregar un nuevo programa de ciencias de la computación a sus ofertas de clase, la primera prueba nueva en siete años. La medida refleja un creciente interés en capacitar a estudiantes para carreras en las ciencias en medio de un impulso nacional para hacer que la economía de EE. UU. Sea más competitiva a nivel mundial.

El nuevo programa, AP Computer Science Principles, se concentrará en los "aspectos creativos" de la informática y será financiado en parte por una subvención de $ 5.2 millones de la National Science Foundation. La agencia federal tiene como objetivo capacitar a otros 10,000 maestros de ciencias de la computación en la misma cantidad de escuelas secundarias en todo el país para 2016 como parte de un esfuerzo por mejorar la educación en los campos de ciencia, tecnología, ingeniería y matemáticas, o STEM. El College Board aportará alrededor de $ 3.5 millones para apoyo y equipo de maestros.

el programa existente se llama AP Computer Science A y el nuevo programa se llama AP Computer Science Principles. La clase existente ha existido durante muchos años y también es útil como modelo para los maestros que desarrollan el currículo.

• Colocación Avanzada Agrega Nueva Prueba de Informática WSJ Junio ​​2013
• Informática AP , wikipedia
• Página de inicio de informática AP
• Estudiantes de AP / informática de College Board
• Principios de AP CS
• Principios de CS de la junta universitaria

Una idea que he estado dando vueltas recientemente es cómo enseñar a los estudiantes de HS la noción de una reducción entre los problemas. Descubrí que este es uno de los temas más interesantes pero más desafiantes cuando me presentaron la complejidad, ya que es bastante difícil (al menos inicialmente) entender el hecho de que un problema como 3-SAT es "igual de difícil". como Vertex-Cover.

El ejemplo que se me ocurrió fue una reducción entre Vertex Cover (VC) y Independent Set (IND-SET), redactada de la siguiente manera;

"Usted es el director de un museo y tiene la tarea de contratar seguridad para proteger los pasillos. Cuando se coloca en una intersección de pasillos, un guardia puede vigilar TODOS los pasillos adyacentes a él. ¿Cuál es el número mínimo de guardias necesarios? para patrullar todo el museo?

"Un poco más tarde, algunos niños deciden jugar al escondite en el museo. Su objetivo es esconderse de tal manera que ningún otro niño pueda verlos. Sin embargo, los guardias no quieren que corran en el museo. pasillos, por lo que están relegados a "esconderse" en las intersecciones. ¿Cuál es el mayor número de niños que pueden esconderse en el museo sin verse? "

$\text{V}C \leq_{P} \text{IND-SET}$

$G=(V,E)$$S \subseteq V$$\iff$ $V \backslash S$$\backslash$ denota la diferencia establecida).

$S$$V\backslash S$$G$