Стратегии неприкосновенности в понимании TCS

19

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

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

trigoman
источник
5
бьет меня это кажется разумным вопросом для этого сайта.
Суреш
4
Я проголосовал за закрытие. Основная проблема, которую я вижу, состоит в том, что вопрос на самом деле не о компьютерной науке; это о том, как изучать информатику. У последнего нет объективного ответа, потому что у каждого человека будет свой лучший путь. Все три голоса для закрытия назначены «слишком локализованной» причине, но я думаю, что этот вопрос также не по теме, поскольку он не касается информатики.
Карл Маммерт
1
Я думаю, что этот вопрос имеет свои достоинства и тот тип вопросов, с которым я борюсь интенсивно. Я думаю, что многим учащимся, изучающим CS, трудно получить рекомендации по этим типам вопросов от доверенного сообщества. Я понимаю возражение на этот вопрос. Мне кажется, что вопрос довольно уместен для мета-раздела этого сайта.
BrotherJack,
6
@CarlMummert: Каждый вопрос о информатике - это вопрос о том, как изучать информатику.
Джефф
2
Вопрос слишком широк в его нынешнем виде. Сфокусируйте свой вопрос, например, попросите ресурсы (например, проблемные книги), чтобы помочь вам улучшить способность решать вопрос в курсе, или, если у вас есть конкретный пример, сфокусируйтесь на этой проблеме и спросите об интуиции или методах решения подобных проблем.
Каве

Ответы:

15

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

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

Прежде всего, вы должны понять содержание до некоторой степени. С этой целью я считаю полезным задавать следующий вопрос всякий раз, когда вам что-то непонятно:

  • Почему мы это делаем?
  • Для чего мы будем использовать это?
  • С какими похожими вещами это связано?
  • Как другие источники объясняют это?
  • Что именно я не понимаю?

После того, как вы ответили на эти вопросы (или обнаружили последующие вопросы и относились к ним одинаково), но у вас остались проблемы, обратитесь к своим учителям (или сюда). К настоящему времени вы должны быть в состоянии сформулировать сфокусированный, точно сформулированный вопрос; отвечать на такие вопросы - работа ваших учителей (и философия StackExchange).

Помимо этого, это упражнения и опыт. Попробуйте воспроизвести доказательства после их прочтения; позаботьтесь о том, чтобы не выучить их наизусть, но извлечь из них важные идеи. Через некоторое время вы сможете воспроизвести все основные доказательства, заполнив пробелы между основными этапами. Даже позже вы начнете видеть шаблоны в утверждениях и доказательствах. Вот как люди смотрят на утверждение и говорят: «О да, конечно, используйте метод X с теоремой Y, а затем просто используйте Z, чтобы получить то, что вы хотите». Это распознавание образов, основанное на многолетнем обучении. Потерпи.

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

Еще одна полезная книга - « Введение в алгоритмы » Кормена, Лизерсона, Ривеста и Штейна. Включена большая глава по математическим основам. Он также содержит много упражнений; решения доступны через связанную страницу (Дополнительный контент). Есть также видео-лекция одного из авторов, которая может хорошо сочетаться с книгой.

Для ознакомительных лекций о доказательствах, посмотрите на доказательства линейной алгебры в Академии Хана . Я не наблюдал за ними, но, надеюсь, они являются основными и полезными. Есть еще много доказательств по ханской академии; Я просто полагаю, что доказательства линейной алгебры могут лучше всего соответствовать информатике. Не стесняйтесь смотреть и на других.

Рафаэль
источник
7
Я согласен, что понимание концепций важнее, чем умение вычислять или доказывать вещи. Но понимание - это результат практики с расчетами и доказательствами, а не замена этой практики.
Джефф
Спасибо за понимание. Я приму ваш совет и постараюсь улучшить на этом основании.
trigoman
Для более простых нужд Книга доказательств может быть ценным справочным материалом.
Рафаэль
8

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

Как сказал @fbernardo, неплохо было бы начать с самого начала. Не так, как FLA (в этом нет смысла при изучении ТС, ИМХО), но обязательно откройте Sipser и начните решать вопросы один за другим по их порядку. С опытом вы получите интуицию и основные инструменты, которые необходимы для более продвинутых концепций.

Если вы не можете справиться с основными вопросами Sipser из первой главы (не с главами автоматов, если вы изучаете ТМ), то у вас могут отсутствовать даже более фундаментальные понятия, такие как базовые методы доказательства (индукция и т. Д.) Или базовые наборы. теория и дискретная математика.

В любом случае, удачи!

Ран Г.
источник
3

Мой единственный совет - начать с самого начала. В моем курсе мы также используем книгу Сипсера, на мой взгляд, это хорошая книга. Но у нас есть курс до TC под названием FLA (Формальные языки - автомат), который дал лучшую интуицию и знания о TC. Итак, опять же, все учатся с разной скоростью, и у вас есть очень хорошая книга. Любой другой конкретный вопрос вы всегда можете найти здесь. :)

fbernardo
источник
2

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

  • как доказать вещи
  • создать формальное описание поведения ТМ

Здесь речь идет только о 1-м пункте (который по своей сути широк и заслуживает его) - своего рода слона в комнате обучения STEM (наука, технология, инженерия, математика), которая становится недолгой и часто приукрашивается до ошеломляющей степени , Может показаться, что никто не знает, как научить создавать доказательства. Этот subj начинается в классах геометрии, тригонометрии и исчисления, но редко является его строгим элементом. большинство учителей считают это необязательным. Кажется, целый класс, посвященный тому, «как доказать вещи», был бы отличным или даже критическим дополнением или изменением в образовании STEM.

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

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

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

ВЗН
источник
1
Добавьте классику Поли "Как ее решить". Также полезно (особенно для выпускников) искать математическое письмо, например, Кнут и др. «Математическое письмо». Этот навык слишком часто воспринимается как должное.
vonbrand