Важные темы в теории вычисления
Во время моих исследований в университете я должен был узнать много о теории вычисления. Я изучил предмет для трех условий. Мне пришлось нелегко, и я должен признать, что забыл много.
Я задаюсь вопросом, является ли это персональной проблемой, или если мы просто должны были изучить много (более или менее) бесполезного материала.
Таким образом, мой вопрос: Что делают темы в области теории вычисления Вы думаете, являются самыми важными, какие части стоит узнать о, и какие темы Вы используете во время своей нормальной работы?
Лично, я рад, что слышал о теории языков (особенно регулярные языки => регулярные выражения - когда они могут быть применены и если не), и в другое время (и пространство) сложности, в особенности O (n) нотации.
Но мы должны были учиться намного больше, включая:
- теория вычислимости
- проблема остановки
- полуразрешимые проблемы
- теория сложности
- p=np?
- теория логики
- исчисление высказываний
- логика предикатов
Было интересно услышать об этих темах, но я не уверен, как необходимый это должно изучить их подробно.
Я знаю, что этот вопрос субъективен, и ответы будут отличаться много в зависимости от Вашего ежедневного опыта работы и личного опыта. Но я хотел бы знать о темах, которые могли бы быть более интересными, чем я помню.
2 ответа
Какие темы в области теории вычислений вы считаете наиболее важными
Вопрос расплывчатый. Важно , кому ?
Какие части стоит изучить?
Все они достойны изучения. Это особый случай того факта, что все человеческие усилия по своей сути заслуживают изучения.
Если ваш вопрос: «Какие темы приносят мне больше пользы, чем затраты моего времени и усилий на их изучение?» тогда это вопрос, на который только вы можете ответить сами.Польза от изучения, скажем, древнегреческой истории не имеет ничего общего с тем, как она влияет на мою способность выполнять свою работу.
Какие темы вы используете в своей обычной работе?
Я использую все темы, которые вы перечислили - теорию языков, анализ асимптотического порядка, разрешимость, теорию сложности, системы доказательства теорем и так далее.
Я не использую их в формальном смысле; Я не сижу за своим столом и использую Основную теорему для вывода анализа порядка для конкретных алгоритмов. Я использую их в том смысле, что очень удобно иметь возможность взять предложенную языковую функцию и быстро решить, потребует ли ее реализация компилятора для решения линейной, полиномиальной, экспоненциальной, NP-сложной или эквивалентной проблема остановки.
Например, довольно легко понять, что разрешение перегрузки в C # 3 на вложенных лямбдах является NP-трудным, но не эквивалентным проблеме остановки. Поэтому мы знаем, что (1) попытки решить проблему за полиномиальное время - пустая трата времени, и (2) по крайней мере, мы знаем, что решение может быть найдено за некоторое время, и (3) мы мог бы предложить простые эвристики для обнаружения плохих сценариев и быстрого отказа, если бы нам это понадобилось.
Я лично не часто использую системы доказательства, хотя полезно думать о проблемах как о частном случае средства доказательства теорем. Существуют всевозможные языковые функции, которые эквивалентны задачам, которые вы бросаете программе доказательства теорем, особенно в области вывода типов и анализа потоков.К счастью, ни одна из возможностей C # на самом деле не требует реализации средства доказательства теорем; другие языки, реализованные в этом здании, имеют это свойство, например F #.
Я не уверен, что использую на работе напрямую все, что узнал из теории классов вычислений. Но я не думаю, что дело в этом. Я также не использую напрямую в жизни то, что я изучал по евклидовой геометрии в средней школе. Но это был самый важный урок, который я посещал во всей начальной школе.
Теория вычислений - действительно интересная тема, и хорошее ее знание может только помочь вам в жизни. Я не могу этого доказать, но знаю, что это правда.
Извините, если это не так уж и много.