Важные темы в теории вычислений

Question

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

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

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

Лично я рад, что слышал о теории языков (особенно регулярные языки => регулярные выражения - когда их можно применять, а когда нет) и о различных временные (и пространственные) сложности , в частности, обозначения O (n).

Но нам пришлось изучить намного больше, в том числе:

• теория вычислимости
  • проблема остановки
  • полуразрешимые проблемы
• теория сложности
  • p = np?
• теория логики
  • исчисление высказываний
  • логика предикатов

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

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

Answer 1

Какие темы в области теории вычислений вы считаете наиболее важными

Вопрос неопределенный.Важно , кто ?

о каких частях стоит узнать?

Все они заслуживают изучения.Это особый случай того, что все человеческие начинания по своей сути заслуживают изучения.

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

Какие темы вы используете во время своей обычной работы?

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

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

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

Лично я не пользуюсь системами доказательств, хотя полезно рассматривать проблемы как частный случай теоремы.испытатель.Существуют все виды языковых возможностей, которые эквивалентны проблемам, которые вы бросаете при проверке теорем, особенно в области вывода типов и анализа потока.К счастью, ни одна из возможностей C # на самом деле не требует реализации средства доказательства теорем;другие языки, реализованные в этом здании, имеют это свойство, например, F #.

Answer 2

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

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

Извините, если это не так много ответов.