Математика для майора TCS

10

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

complexity-theory automata education ADR
источник
2
Смотрите связанный вопрос.
Николас Манкузо
1
Также проверьте требования курса в вашей школе , а также похожие вопросы по теоретической информатике (например, это или это ). Я испытываю желание закрыть этот здесь как дубликат; это также довольно локализовано.
Рафаэль
6
Возьми ВСЕМ математику!
Джефф
2
@JeffE Возьми ... всю математику?
MrGomez
2
Вся математика в пособии теоретика .
Чао Сюй

Ответы:

2

(Резюме комментариев к вопросам)

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


На этот вопрос также ответили в других SE, и очень информативные детали можно найти в:

  1. какой-добрейший из-математического-фона-это необходимый обмен на сложности-теорию
  2. Примеры «несвязанной» математики, играющей фундаментальную роль в TCS?
  3. Какие математические курсы я должен пройти, чтобы подготовиться к магистратуре или докторантуре?
Ран Г.
источник
1
Категорически не согласен с этим общим заявлением. На самом деле, подавляющее большинство областей математики не помогают теоретической информатике. Скажем, функциональный анализ, теория множеств (например, принуждение), топология, алгебраическая геометрия (нет, GCT не в счет), дифференциальные уравнения, и список можно продолжать и продолжать. Самый важный математический предмет - теория вероятностей (даже это зависит от того, какой тип TCS вы делаете). Кроме того, некоторые очень базовые знания в некоторых областях, например, теория групп.
Юваль Фильмус
@Yuval, я думаю, что это немного незаметно. Кто считал, что преобразования Фурье могут быть настолько полезны для TCS (до славы, которую он достиг при использовании для PCP и т. Д.) Кто думал, что решатели SDP так актуальны для TSP (как недавно показано в [arxiv: 1111.0837], если я правильно понимаю их работу ) .. Я думаю, что многие другие методы могут быть использованы для TCS и, конечно, для CS в целом. Правда, не все методы одинаково важны, и я надеялся, что этот поток станет списком методов / приложений, где большинство важные методы получили бы самые высокие голоса.
Ран Г.
Преобразования Фурье являются очень элементарными понятиями. Вам не нужно понимать ядро ​​Fejer в TCS. Что касается SDP, они приходят из исследования операций (или выпуклой оптимизации, если вы предпочитаете). Это правда, что некоторые вещи могут быть полезны. Например, я нашел свой опыт в Си очень полезным, а Вирджиния Уильямс нашла свой опыт в Maple очень полезным. С точки зрения вашей карьеры, письма и публичные выступления также очень полезны. Все это, вероятно, более полезно, чем курс по комбинаторной теории множеств. Почему бы не сказать людям изучать эти предметы вместо случайных математических курсов?
Юваль Фильмус
1
@YuvalFilmus Я не понимаю: принцип инвариантности MMO - строгое обобщение Берри-Эссеена. Я тоже не согласен с вашей более важной точкой. Многие TCS могут использовать вероятность до границы Черноффа. Но лемма JL, концентрация меры в, скажем, ARV, теорема Дворецкого для сжатого зондирования, неравенство Гротендика в приближении нормы отсечения - это лишь некоторые очень успешные примеры того, как FA полезна в TCS. да, основной фокус этих двух областей различен - но пересечения выходят за рамки «первых 10 страниц» и делают изучение математики того стоящим.
Сашо Николов
1
более того, в то время как наши приложения обычно позволяют нам придерживаться (вариантов) результатов, которые можно описать и часто доказывать элементарно, более широкий контекст обеспечивает интуицию (например, CLT - отличная эвристика). и поскольку трудно сказать, что полезно, пока вам не нужно его использовать, я не возражаю против того, чтобы посещать некоторые курсы по математике в дополнение к группам чтения в TCS, которые помогут вам узнать то, что, как известно, полезно. Я недавно обнаружил, что результат FA (который почти никогда не используется в TCS afaik) является ключом к проблеме, над которой я работал
Сашо Николов