Преподавание в старшей школе TCS - существующие программы

16

Мне предложили преподавать новую программу средней школы TCS, которая требует составления учебного плана. Мне бы очень хотелось услышать мнения и предложения по этому поводу.

Во-первых, кто-нибудь знает о средних школах, где программа TCS преподавалась успешно (или безуспешно)?

Идея предназначена для трехлетней программы (10-12 классы, возраст 16-18 лет), около 8 часов в неделю, для отобранных выдающихся учеников, что означает, что она может и должна быть сложной. В отличие от стандартной программы «компьютеры», эта программа должна быть ориентирована не на программирование, а на отдельные темы в CS, в основном в TCS. На данный момент мы имеем в виду следующие темы:

  • Асимптотический анализ
  • Основные структуры данных и алгоритмы (списки, массивы)
  • Графовые алгоритмы, также как демонстрация жадных алгоритмов против динамического программирования.
  • Другие алгоритмы (например, вероятностные)
  • Вычислимость - понятие ТМ, редукция, разрешимость.
  • Сложность - NP, P, возможно, PSPACE и NL. Полнота.
  • Теория автоматов

По сути, это охватывает часть TCS первых двух лет бакалавриата в области CS. Однако мы должны помнить, что этим студентам не хватает математической базы, необходимой для большей части этого материала. В частности, такие вещи, как теория множеств, комбинаторика, вероятность и модульная артистика, не преподаются в средней школе (к сожалению).

Подводя итоги и задавая точные вопросы:

  1. Кто-нибудь знает подобную программу где-нибудь?
  2. Существуют ли предложения по конкретным / общим темам, которые, по вашему мнению, можно и нужно преподавать в дополнение / вместо тем выше, сохраняя при этом программу интересной, а также важной и непосредственно актуальной (например, теория групп важна и интересна, но недостаточно актуальна оправдать время, которое потребуется)
  3. Я был бы счастлив представить машинное обучение в некоторой форме, поскольку это действительно горячая тема в наше время. Любые идеи относительно того, как машинное обучение может быть представлено без таких инструментов, как теоремы измерения меры, приветствуются.
Shaull
источник
2
Похоже, что в конце вы перечислите теорию автоматов как своего рода последующую мысль. Я бы выступил за то, чтобы сделать теорию автоматов центральной и объединяющей темой. Он может познакомить студентов с формальными математическими рассуждениями без какого-либо конкретного математического образования. Он имеет четкие безусловные теоремы, которые являются основополагающими, но относительно простыми для доказательства. Это может быть напрямую связано с машинным обучением , хотя из моего опыта это трудно преподавать студентам на первом курсе теории, поэтому с HS требуется большая осторожность.
Артем Казнатчеев
1
не слышал об этом раньше! «отобранные» студенты? это также означает продвинутый, предположительно? попробуйте добывать научно-популярные книги на TCS или также онлайн-блоги [несколько хороших там]. Машины Тьюринга, квантовые вычисления, другие ключевые / интересные области. думаю, что это может быть осуществлено, если математика не тяжелая и сделана скорее в концептуальном, чем в математическом смысле. также этот сайт часто встречается в вопросах edu: cs unplugged . удачи!
vzn
2
Интересно, лучше ли было бы посвятить немного вашего времени обучению тем математическим навыкам, которые вы упомянули (например, вероятность) ... это также потенциально поможет вам охватить более сложные темы, но также поможет подготовить студентов к будущему изучению математики / сс. ,
усуль
1
@vzn - да, это продвинутые (смею сказать, одаренные) студенты.
Шаул
1
@vzn Это очень интересное предложение. Так или иначе, TCS еще не является частью популярной культуры. То есть даже любопытные ученики обычно не знают о таких вопросах, как P против NP. Но мы обязательно спросим у нынешних студентов CS предложения и посмотрим, что они придумают. Я предполагаю, что криптография будет центральной.
Шал

Ответы:

8

Многие страны организуют летние школы для своих команд IOI (состоящих из учащихся старших классов в возрасте примерно 16 лет IIRC). У того, что у нас в Иране, были следующие курсы:

  • программирование,
  • структура данных и алгоритмы,
  • комбинаторика и
  • теория графов.

Я думаю, что Ассоциация учителей информатики ACM имеет учебный план K12 на своей странице ресурсов по учебным программам, хотя, вероятно, она слишком легкая для талантливых подростков.


Я думаю, что программирование обязательно должно быть частью учебной программы. Python должен быть хорошим первым языком для изучения.

Вы можете также охватить некоторые доступные темы приложениями (радость от создания чего-то интересного может сильно повлиять на их интерес). Я думаю, что курс ML Andrew Ng по Coursera должен быть доступен для талантливых студентов (особенно для таких стран, как ваша, где существует более серьезная учебная программа по математике K12).

Нестандартная тема, которую вы, возможно, захотите рассмотреть, - это теория комбинационных игр, она может быть не очень интересной для 16-летнего возраста (у меня нет опыта для этого), но, по моему опыту, она работает довольно хорошо для немного младших школьников.

Я лично считаю , что центральная и присоединительные тема должна быть вокруг алгоритмов, я думаю , что это будет работать лучше , чем теории автоматов в качестве центральной темы и , возможно , алгоритмической точки зрения (не Тьюринг машины, автоматы и т.д.) является сущность информатики.

Кава
источник
Программная часть покрыта стандартной программой CS, которую они все принимают. Это дополнительные темы. У вас случайно есть ссылка на такой сайт летней школы? Что касается сосредоточения внимания на алгоритмах - хотя я согласен с тем, что они являются центральными для CS, я думаю, что вычислимость и сложность в равной степени являются сущностью компьютерной науки. Я помню, что меня больше впечатлил тот факт, что есть вещи, которые мы не можем решить, а не умные алгоритмы. Но оба будут прикрыты, наверное.
Шаул
В некотором смысле, машины Тьюринга - все об алгоритмах . также ruby - это также отличный вариант, сравнимый с python . на том же subj другом отличном варианте изучения разработки является javascript по многим причинам, например, по причине его распространения в браузерах, большого количества открытого / примера кода, широких возможностей, высокого использования и т. д.
vzn
1
@Shaull, у них есть сайт ( Клуб молодых ученых ), но он написан на персидском языке и не содержит много информации о том, что освещается в летней школе.
Каве
1
@vzn, я не думаю, что у вас есть большой опыт преподавания TCS ученикам старших классов, и я очень четко объяснил вам, что мне не интересно ваше мнение . Хватит троллить мои ответы.
Каве
k, плз, не угадай на моем bkg & сделаю то же самое. комментарий в основном в поддержке от ваших мнений ... звучит как тема для меты = (
ВЗНА
5

Любопытно, что есть кто-то, кто утверждал, что машинное обучение уникально подходитсреди тем информатики, чтобы преподавать учащимся старших классов, потому что, предположительно, это одна из немногих областей, где базовая математика может помочь вам понять достаточно, чтобы оценить важные задачи. Я не согласен с этим утверждением - базовые алгоритмы (скажем, для поиска, сортировки) могут быть представлены в виде головоломок, и вы можете очень быстро добраться до очень простых формулировок, но фундаментальные открытые проблемы, такие как «умножение, можно выполнить по существу с таким же количеством операций как сложение », или сортировка целых чисел по линейному времени, или факторинг (я предполагаю, что концепция чисел простых чисел не была бы новой для избранной группы учащихся средней школы?). С другой стороны, много машинного обучения было бы трудно понять без хорошего уровня статистики и теории вероятностей. тем не менее,

Что касается учебной программы, то есть более детальная Essinger и Rosen в Drexel.

В дополнение к этому, я думаю, можно попытаться набросать некоторые из более высокоуровневых идей теории обучения:

  • что является основной проблемой классификации
  • что такое концептуальный класс и что значит изучать концепт
  • почему вы не можете надеяться выучить понятия из неограниченного класса понятий с менее чем экспоненциальной сложностью выборки (как введение в подсчет аргументов)
  • что такое VC-измерение

Другое предложение состоит в том, чтобы ввести схемы и попытаться сделать набросок нижней границы Шеннона. Зависит от того, насколько комфортно учащимся считать. Если это слишком тяжело, это все равно может помочь в аргументации, в то время как ученики сами начнут считать контуры на вере. Я думаю, что идея «большинство проблем требует больших цепей, потому что есть слишком много проблем и слишком мало маленьких цепей» будет поражать. Эта идея важна и распространена по сложности.

Сашо Николов
источник
Оба предложения очень хороши. Благодарность! У меня есть ощущение, что для старшей школы просто изучение того, что такое измерение венчурного капитала, может занять около 3 месяцев, что может быть слишком много. Но это определенно стоит задуматься, тем более что об этом уже думали.
Шаул
Я думаю, что даже просто понять, что значит изучать концепцию, и иметь какое-то смутное представление о том, что нельзя научиться сколь-нибудь сложным вещам до того, как солнце замерзнет, ​​будет победой.
Сашо Николов
3

Вот одно из многообещающих направлений для этого. AP / NSF недавно объявили о новой инициативе CS по программе повышения квалификации. использование такой программы будет иметь много преимуществ, таких как стандартизированный план урока, аккредитация колледжа и т. д.

В настоящее время он находится в стадии разработки и будет готов к 2016 году. Предварительная программа курса и материалы доступны онлайн. (для академических экспертов на этом этапе может даже существовать некоторая возможность повлиять на будущее содержание посредством сотрудничества типа «коллективного разума».)

В четверг Программа повышения квалификации Совета колледжей заявила, что планирует добавить новую программу информатики к своим предложениям в классе, первый новый тест за семь лет. Этот шаг отражает растущий интерес к подготовке студентов к карьере в области естественных наук на фоне общенационального усилия по повышению конкурентоспособности экономики США в глобальном масштабе.

Новая программа AP Computer Science Principles будет сосредоточена на «творческих аспектах» вычислений и будет частично финансироваться за счет гранта в размере 5,2 млн. Долл. США от Национального научного фонда. Федеральное агентство планирует подготовить еще 10 000 учителей информатики в том же количестве вузов по всей стране к 2016 году в рамках усилий по улучшению образования в области науки, техники, техники и математики, или STEM. Совет колледжа будет скинуться около $ 3,5 миллиона для поддержки и оборудования учителей.

существующая программа называется AP Computer Science A, а новая программа называется AP Computer Science Principles. Существующий класс существует уже много лет и также полезен в качестве модели для преподавателей, разрабатывающих учебную программу.

ВЗН
источник
3
Между прочим, Бейкер Франке и я представили предложение о проведении сессии BOF («Птицы перья») на SIGCSE '14, чтобы обсудить, как сделать темы теоретически доступными для учебной программы по принципам CS.
rahulmehta95
@ rahulmehta95 - есть ли ссылка на предложение, которое я могу прочитать?
Шаул
2
Вот и вы: cs.ucls.uchicago.edu/~rahulmehta/papers/BOF-Theory.pdf . Надеюсь это поможет!
rahulmehta95
2

Идея, о которой я недавно догадался, заключается в том, как научить студентов ГС понятию сокращения проблем. Я обнаружил, что это одна из самых интересных, но наиболее сложных тем, когда я познакомился со сложностью, поскольку довольно сложно (по крайней мере, на начальном этапе) обдумать тот факт, что такая проблема, как 3-SAT, «столь же сложна» как Vertex-Cover.

В качестве примера я привел сокращение между Vertex Cover (VC) и Independent Set (IND-SET), сформулированное следующим образом;

«Вы - директор музея, и вам поручено нанять охрану для охраны прихожих. Когда их помещают на перекрестке прихожих, охранник может следить за ВСЕМИ прихожими, находящимися рядом с ним. Какое минимальное количество охранников требуется? патрулировать весь музей?

«Чуть позже некоторые дети решают поиграть в прятки в музее. Их цель - спрятаться так, чтобы ни один ребенок их не увидел. Однако охранники не хотят, чтобы они бегали в в коридорах, поэтому их «прячут» на перекрестках. Какое наибольшее количество детей может спрятаться в музее, не видя друг друга? »

Основная цель для студентов состоит в том, чтобы сформулировать и доказать следующую теорему, которая является центральной для сокращения, показывающего ВСпIND-SET;

Теорема: дляграммзнак равно(В,Е), SВ это независимый набор ВS это вершинное покрытие (где обозначает установленную разницу).

Причина я выбрал VC & IND-SET является то , что это не слишком трудно понять , что проблемы тесно связаны между собой ; всякий раз, когда есть независимый наборS, это вызывает покрытие вершины ВS в грамм,

rahulmehta95
источник
Хотя я понимаю мотивацию (очень приятного) примера, я думаю, что в HS я бы начал с сокращений Тьюринга, которые гораздо более интуитивны. Кроме того, я бы начал с проблемы, когда ввод должен быть действительно изменен, а не просто изменение параметра. Например, я бы начал сСLяQUЕпяND-SЕT, который более «вовлечен».
Шаул
Что касается сокращений, то доказательство того, что существует универсальная машина Тьюринга, является одним из способов, и, вероятно, понятным для продвинутых старшеклассников ... [обратите внимание, что есть много видео lego TM, некоторые даже исследователями cs ...] также, возможно Цейтин преобразования ?
vzn