Вдохновенный разговор для выпускников старших классов

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

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

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

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

Один протокол заключается в следующем. Чарли кладет мяч в каждую руку, затем решает либо поменять два мяча позади себя, либо нет. Затем он снова представляет два мяча. Если вы всегда можете определить, поменял ли он два шарика или нет, то Чарли все больше убежден, что вы можете различить их. Если Чарли делает это случайным образом, и вы действительно не можете определить разницу между цветами, то вы будете правильно угадывать только с вероятностью . После испытаний Чарли должен убедиться, что вы можете определить разницу с вероятностью не менее .к 1 - 1 / 2 $1/2$$k$$1-1/2^k$

Теперь, когда Чарли все больше убеждается в том, что вы можете заметить разницу, он разочарованно никогда не узнает, какой шар красный, а какой - зеленый.

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

Одним из наиболее привлекательных аспектов TCS является то, как он использует абстрактные математические идеи для повседневного практического применения. Презентация может сфокусироваться на абстрактных идеях, которые лежат на один шаг позади того, что они ежедневно видят в Интернете: кратчайшие пути становятся интересными, когда они попадают в контекст друзей в Facebook. Больше алгоритмов графа может ездить на Pagerank; Рекомендации Amazon поднимают проблему машинного обучения; и покупка вещей в Интернете, безусловно, является хорошим лидером для криптографии с открытым ключом.

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

Весёлая сторона информатики

Я использовал различные игры из теории комбинаторных игр, в основном из «Честных игр» Ричарда Гая и из книги Элвина Р. Берлекампа, Джона Х. Конвея и «Пути победы в ваших математических играх» Ричарда Гая ( вики ).

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

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

Философская сторона информатики

В теоретической информатике много тем, связанных с философией и большими вопросами . От теоремы Гёделя о неполноте до доказательств с нулевым знанием, безопасности, конфиденциальности, алгоритмической теории игр, P против NP, машинного обучения ... Я не буду вдаваться в подробности, просто продемонстрирую, что проблемы интересны, это больше, чем просто информатика они связаны с большими вопросами. (Взгляните на « Квантовые вычисления Скотта Ааронсона с Демокрита и великие идеи в теоретических лекциях по информатике» ). Не дайте им почувствовать, что тема мертва (т.е. на все вопросы даны ответы), дайте им почувствовать, что область жива, прогресс достигнут, но впереди еще большие проблемы, и это путешествие в неизведанную землю.

Технологическая сторона информатики

Поговорим о компьютерных науках за технологиями. Здесь так много тем, которые можно выбрать, знакомые технологии от видеоигр до поиска в Google, машинный перевод, зрение, ... технологии, которые каждый использует каждый день, или даже незнакомые. Поговорите о прогрессе и технологиях следующего поколения, о влиянии, которое они оказали на нашу жизнь, и о том, как они улучшили его. Поговорите об исследованиях, проводимых в крупных известных компаниях (таких как Google, Microsoft, Apple, IBM, ...) и продуктах, которые они разрабатывают. Расскажите о больших проблемах нашего времени и о том, какое влияние на них оказывает информатика.

Математическая сторона информатики

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

Междисциплинарная сторона информатики

Информатика, вероятно, является одним из наиболее междисциплинарных предметов, и здесь есть какая-то связь почти с любым другим предметом: гуманистическим (социология, лингвистика, экономика, философия, ...), естественными науками (математика, физика, ...), биология, медицинские науки, искусство, инженерия (электроника, механика, ...), ... все что угодно! Какую бы тему вы ни интересовали, в компьютерной науке есть что-то, что связано с этим! Как сказал Скотт, каждый второй майор сосет по сравнению :).

Все они

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

некоторые комментарии

О чем бы вы ни говорили, вы должны быть в восторге от этого. Будет гораздо труднее заинтересовать их темой, которая не очень интересна для вас. Расскажите им о своих собственных причинах выбора информатики. И не скучай .

Я успешно использовал две беседы как со старшеклассниками, так и с первокурсниками.

1. Оригами. Я начинаю с проблемы с 5-балльной звездой (это хорошо работает в американском контексте из-за связи с американским флагом) и позвольте студентам попытаться выяснить, как сделать пятибалочную звезду со сгибом + 1 разрез. Я говорю о «ресурсе» (сокращении) и о том, как разработка алгоритма заключается в работе с ограниченными ресурсами. Затем я расскажу о других вопросах и применениях оригами в реальном мире (сердечные клапаны, телескопы НАСА, зоны смятия в автомобилях).

2. Сортировка блинов: между сортировкой блинов и перегруппировкой генома есть прекрасная связь, и я фактически сделал стопки блинов из пены, чтобы студенты могли поиграть с ними. Прекрасно работает, и позвольте мне рассказать об алгоритмах, генном секвенировании, Билле Гейтсе (!) И других забавных вещах.

Криптография - это всегда то, что захватывает разум молодых людей (и я лично на это надеюсь). У меня были друзья, которые хотели быть помощниками медсестер, хоккеистами, бизнесменами и политиками, а также друзьями (которые, несмотря на свои более высокие цели), устраивались на работу в качестве продуктовых упаковщиков и толкачей тележек, строителей и помощников питомника - все они изобрели и сломали друг друга (по общему признанию наивных и простых) кодов. В частности, существование криптографии с открытым ключом, как правило, довольно легко объяснить, если выбрать маршрут RSA. Можно также перечислить некоторые важные результаты без каких-либо доказательств или конструкций - доказательства с нулевым знанием и гомоморфное шифрование неизбежно приводят к тому, что он стоит за чудаком.

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

Наконец, я бы также предложил сделать простое введение в теорию сложности - что-то вроде моего ответа на описание «Теоретической информатики за обеденным столом» .

Омнибус нового Тьюринга А. К. Дьюи проводит 66 так называемых экскурсий по информатике. Он охватывает такие темы, как анализ алгоритмов, ИИ, теория сложности, теория вычислений, криптография, компьютерная графика и так далее. Каждая тема написана в довольно сжатой форме, отражая какой-то знаменательный результат в информатике. Эта книга может послужить источником вдохновения.

Другая возможность - позволить студентам испачкать руки с помощью программы Google Code-in . Это немного похоже на Google Summer of Code , но, вы знаете, для детей. Возможно, показ некоторых из удивительных проектов по программированию, в которых учащиеся могут участвовать, - это один из возможных способов пробудить интерес.

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

PCP тоже магия, но я думаю, что это вне досягаемости ...

Вот очень хорошая статья Михаила Митценмахера по теории кодирования, предназначенная для старшеклассников:

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

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

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

Около 50% студентов ответят на первый вопрос, а остальные 50% ответят на второй вопрос. Теперь очень легко оценить, сколько студентов обманывали. Пример: если 40% ответов были положительными, и вы знаете, что 30% людей любят зеленый цвет, значит, вы знаете, что около 50% студентов обманывали.

Я думаю, что это тесно связано с описанием обеденного стола теоретической информатики?

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

По моему мнению, «информатика» - это «наука всех наук» :)

Что такое "наука"? Мы получаем данные от природы и пытаемся построить модель, которая объясняет эти данные. Также мы неявно предполагаем, что природа не является произвольной. Законы природы должны иметь краткое выражение, данные должны удовлетворять некоторым симметриям и т. Д.

Но это именно проблема обучения! Данные генерируются каким-то процессом, который обещает быть «малосложным», и наша задача - восстановить описание процесса.

Наше понимание таких проблем находится на таком примитивном уровне, что вы обязаны поработать над ними! :) Даже наше понимание, казалось бы, более простой проблемы того, эквивалентен ли вывод процесса черного ящика некоторой фиксированной функции, далеко не завершено. Например, предположим, что нам обещано, что черный ящик оценивает функцию, которая может быть вычислена с помощью арифметической схемы малой глубины (это легко объяснить старшеклассникам), и мы хотим выяснить, является ли блок вычисление нулевой функции. Мы не знаем, можно ли это сделать за время существования юниверса для функций в доменах разумного размера!

Подсказка, чтобы начать говорить о теории арифметической сложности, пропасти на глубине 4, роли случайности в вычислениях, о том, что известно, если мы уменьшим число элементов умножения и т. Д. И т. Д. ...

На семинаре «Алгоритмы в полевых условиях», который состоялся месяц назад в DIMACS, Грэм Кормод выступал за обучение методам рисования эскизов от потоковых алгоритмов до студентов. Моисей Чарикар сказал, что они учат их в Принстоне, я думаю, @Suresh Venkat также упомянул, что он преподает такие вещи, как алгоритм Мисры-Гриса для тяжелых нападающих. Я думаю, что некоторые базовые результаты потоковой передачи были бы хороши и для старшеклассников: они полагаются на основные, но важные математические приемы, постановки задач похожи на головоломки, а решения кажутся волшебством, а магия - отличный способ вдохновить старшеклассников. Вы можете убедиться, что подчеркнули существенную разницу между масштабом проблемы и количеством ресурсов, которые вы можете использовать. Глупый пример: предположим, что вы можете задать каждому человеку, входящему или покидающему аэропорт JFK, свой почтовый индекс.