Как придумать нетривиальную идею в теоретической информатике?

19

Я аспирант, работающий в области теоретической информатики. Я прочитал исследовательские работы многих исследователей, и я видел много инструментов и математики, которые они используют для разработки алгоритма. Например, см. Эту исследовательскую работу [Primality in P] . Я бы не сказал, что эта исследовательская работа основана на одной или двух идеях, но она основана на многих идеях, которые требуют серьезной математики. Я изо всех сил пытаюсь придумать такие идеи из пары лет. Я работал над одной проблемой в течение многих месяцев, но в моей голове нет ничего нетривиального. Все идеи, которые приходили мне в голову до сих пор, тривиальны и очень мало полезны для теоретических исследователей информатики. Мне интересно, как создать механизм, который позволит мне генерировать нетривиальные результаты.

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

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

lovw
источник
7
Как отмечает Арье, это лучше обсудить с вашим консультантом, чем с интернетом. Они могут помочь вам избежать тупиков, предложить что-то попробовать, помочь освоить основные инструменты, указать, чего не хватало в предыдущей работе. Помните, что один из авторов Primality в P был опытным исследователем, который очень хорошо знал проблему.
Сашо Николов
11
Интересно, ты поставил свой бар слишком высоко? Хорошие исследования - это редко преобразующий или совершенно новый механизм. Часто это происходит от глубокого понимания вашей проблемы до такой степени, что вы наталкиваетесь на маленькую, даже «тривиальную» идею, которая показывает, почему что-то является правдой; тогда вы обнаружите, что написание этого текста занимает 30 страниц. Сделайте это несколько раз в тесно связанных проблемах, и вы можете увидеть появление механизмов (надеюсь, метафорически).
Усул
5
Огромные дубы растут из маленьких желудей. Большинство докторских диссертаций, которые я видел, выросли из небольшого понимания или результатов чрезвычайно ограниченных случаев, которые затем медленно продлевались в течение многих месяцев.
Андрас Саламон
2
Этот совет кажется уместным здесь.
Джефф

Ответы:

9
  1. Почти наверняка есть списки открытых проблем в вашем конкретном подполе. Найдите их и прочитайте их. Хотя вряд ли вы сможете решить эти проблемы - по крайней мере, сразу - используйте их в качестве отправной точки. Можете ли вы решить некоторые конкретные случаи? Можете ли вы решить менее общую проблему? Можете ли вы показать, что более общая проблема сложна в вычислительном отношении?

  2. Прочитайте, что делают другие люди. Это означает составление списка конференций и журналов в вашем регионе и посвящение не менее часа в день чтению в них газет. Нет необходимости понимать все сразу. Попробуйте ознакомиться с общими темами, затем выберите одну или две статьи, которые кажутся интересными или фундаментальными, и погрузитесь в них. Изучите методы и доказательства. Можете ли вы применить их к аналогичным или связанным проблемам? Разрабатывайте конкретные примеры подробно, насколько это возможно.

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

Джеффри Шаллит
источник
8

Я попытаюсь ответить на это с моим ограниченным опытом. Отказ от ответственности Я просто старший кандидат кандидат сам.

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

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

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

Итак, что вы контролируете? Я думаю, что самое большое значение для времени, если вы застряли в ничейной стране, это читать, От консенсуса наиболее влиятельных бумаг вашего региона до опросов и последних результатов. Если у вас есть хоть какой-то шанс, продолжайте опираться на эту картинку в своей голове о том, как выглядит ваш район; каковы самые большие проблемы, каковы наиболее ценные инструменты, кто является ключевыми людьми, чьей работой вы должны следовать. Это медленный и утомительный процесс, и вам приходится читать много статей, иногда даже чтобы определить влиятельных, но сделайте это. Удостоверьтесь, что вы читаете статьи в своем собственном темпе, но, как советовали ваши коллеги, убедитесь, что вы понимаете их (да, это включает - по определению - теоремы и доказательства). После того, как вы прочитали достаточно статей и нарисовали свою картину богато украшенной, вы начнете замечать маленькие, и по мере продвижения вперед большие «дыры», которые вы можете медленно заполнять своими вопросами и, надеюсь, ответами.

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

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

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

Вот предложение: ищите открытые проблемы в вашей области, которая вас интересует. Попробуйте переформулировать проблему в разных представлениях, особенно нестандартных. Попробуйте объединить разные идеи, теоремы и результаты из разных смежных областей для создания инструментов для решения вашей проблемы. Сформулируйте гипотезы и попробуйте доказать их (или спроектируйте алгоритм и докажите его правильность).

Мухаммед Аль-Туркистани
источник
4

Это общий вопрос, поэтому я собираюсь дать общий ответ: поговорите со своим научным руководителем! У вас есть один, верно? Вы знакомы с его / ее исследовательскими проектами? Кто-нибудь из них вас интересует? Если никто не делает, возможно, вам следует искать другого советника ...

Арье
источник