Когда теоретическая информатика полезна? - PullRequest
25 голосов
/ 25 октября 2008

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

Почему теория полезна? Вы когда-нибудь использовали это в своем повседневном кодировании?

Ответы [ 24 ]

3 голосов
/ 25 октября 2008

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

3 голосов
/ 25 октября 2008

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

2 голосов
/ 19 августа 2014

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

Однажды, например, я работал над проектом, включающим множество математических вычислений, и в определенный момент наше программное обеспечение вышло из строя. во время отладки я выяснил, что после некоторой математической операции я получил число как DOUBLE со значением 1.000000000002, но с математической точки зрения не могло быть> 1, что на более позднем этапе в программе давало легендарное исключение NaN . я потратил некоторое время, чтобы понять это, но если бы я уделил больше внимания уроку " Double and Float ", я бы не потратил впустую это время.

2 голосов
/ 19 августа 2014

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

Если вы посмотрите на свою карьеру в долгосрочной перспективе, знание теории даст вам глубину, глубину, которую вам нужно расти. Возврат инвестиций в изучение вашего 5-го или 6-го языка программирования будет намного меньше, чем изучение вашего 2-го и 3-го. Знакомство с теорией даст вам представление о реальной технике, о том, где находятся степени свободы и как вы можете сделать правильный компромисс.

Важные понятия 1) Государство, 2) Кодирование, 3) Недетерминизм. Если вы их не знаете, они вам не помогут. Теория должна предоставить вам общую картину и понимание того, как основные понятия сочетаются друг с другом. Это должно помочь вам отточить свою интуицию.

Пример: в некоторых из приведенных выше ответов упоминается проблема остановки и машины Тьюринга. Когда я наткнулся на статью Тьюринга в колледже, я совсем не чувствовал себя просветленным. Однажды я наткнулся на теорему Гёделя о неполноте и, в частности, нумерацию Гёделя. Вещи начали иметь много смысла. Спустя годы я прочитал о Георге Канторе в книжном магазине. Теперь я действительно начал понимать машины Тьюринга и проблему остановки. Попробуйте сами и посмотрите «Диагональный аргумент Кантора» в Википедии. Это одна из самых удивительных интеллектуальных вещей, с которыми вы когда-либо сталкивались.

Пища для размышления: типичная машина Тьюринга - не единственный способ создания машины перехода состояний. Машина Тьюринга с двумя, а не с одной лентой даст вам гораздо большую скорость для ряда алгоритмов. http://www.math.ucla.edu/~ynm/papers/eng.ps

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

Я нашел книгу Розенберга сенсационной. http://www.amazon.com/The-Pillars-Computation-Theory-Nondeterminism/dp/0387096388 Если у вас есть только одна книга по теории, ИМХО, это должна быть та.

1 голос
/ 21 февраля 2017

Я знаю, что это старо, но мой короткий ответ тем, кто утверждает, что теория «бесполезна» и что они могут практиковать свою профессию без нее, таков:

Без базовой теории существует нет практики.

Почему теория полезна?

Теория - это фундамент, на котором строятся другие вещи. Когда теория применяется , результатом является практика.

Рассмотрим компьютеры сегодня. Обычный компьютер сегодня смоделирован и построен на основе машины Тьюринга, которая, для простоты, является абстрактной / теоретической моделью для вычислений. Эта теоретическая модель лежит в основе вычислительной техники, и все вычислительные устройства, которые мы используем сегодня, от высокопроизводительных серверов до карманных телефонов, работают, потому что основа лежит в основе звука.

Рассмотрим анализ алгоритма. Проще говоря, анализ алгоритма и теория сложности времени использовались для классификации задач (например, P, NP, EXP и т. Д.), А также того, как алгоритмы, которые мы имеем, когда пытаясь решить разные проблемы в разных классах.

Предположим, что один из ваших друзей устроился на работу в каком-то месте X, и, пока он там, менеджер делает несколько простых запросов, например, таких примеров:

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

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

Фактически, они понятия не имеют, почему система работает на "приемлемом" уровне при проверке 5 городов, но становится очень медленной в 10 городах и просто зависает при переходе только в 40 городов. Они считают, что это только"в 2 и 8 раз больше городов, чем тест с 5 городами", и удивляются, почему программе просто не требуется "в 2 и 8 раз больше времени" соответственно ...

Понимание теории позволило бы им понять следующее, по крайней мере, с первого взгляда:

  1. Это TSP
  2. TSP NP-hard
  3. Их алгоритм роста порядка O (n!)

Числа говорят сами за себя:

+--------------+-------+-----------------------------------------------------------------+
|  No. Cities  | O(N!) |  Possibilities                                                  |
+--------------+-------+-----------------------------------------------------------------+
|       5      |   5!  | 120                                                             |
|      10      |  10!  | 3,628,800                                                       |
|      40      |  40!  | 815,915,283,247,897,734,345,611,269,596,115,894,272,000,000,000 |  <-- GG
+--------------+-------+-----------------------------------------------------------------+

Они могли с самого начала понять, что их система не будет работать так, как они себе это представляли. Впоследствии система была признана непрактичной и была отменена после того, как значительное количество времени, усилий и других ресурсов было выделено и в конечном итоге потрачено на проект - и все потому, что мысль «теория бесполезна».

Так что после этой неудачи менеджеры думают: «Ну, может быть, эта система была недооценена; в конце концов, в нашей стране очень много городов, и наши компьютеры просто не так быстры, как нам нужно, чтобы они были для наших недавних система отменена, чтобы быть успешным ".

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

Но у них есть другой проект. На самом деле проще. Они приходят через неделю и просят сказать следующее:

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

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

К сожалению, ваш друг, настаивая на том, что «теория бесполезна», не осознавал, что якобы простой запрос на самом деле был неразрешимой проблемой разрешимости (то есть самой проблемой остановки), и что не было никакого известного решения для Это. Это было невыполнимое задание.

Поэтому даже начало работы по решению этой конкретной проблемы было ошибкой, которую можно было избежать и предотвратить. Если бы существовала теоретическая основа для понимания того, что запрашивалось, они могли бы просто предложить другое и достижимое решение ... такое как реализация процесса мониторинга, который может просто kill -SIGTERM <id> любого пользователь процесс (согласно списку пользователей), который монополизирует ЦП на некоторый произвольный / разумный интервал при определенных допущениях (например, мы знаем, что каждый запуск программы должен был завершиться в течение 10 минут, поэтому любой экземпляр, работающий в течение 20 + минуты должны быть kill ред.)

В заключение, практика без теории подобна зданию без фундамента . Рано или поздно нужное количество давления под прямым углом заставит его обрушиться на . Без исключений.

Вы когда-нибудь использовали его в повседневном кодировании?

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

Конечно, мы:

  1. ежедневно используют компьютеры, которые опираются на вычислительные модели (например, машины Тьюринга)
  2. написать код, который опирается на теорию вычислимости (например, что даже вычислимо) и лямбда-исчисление (например, для языков программирования)
  3. полагаться на теорию цвета и модели (например, цветовые модели RGB и CMYK) для цветных дисплеев и печати и т. Д.
  4. Теоремы Эйлера в компьютерной графике, позволяющие строить матрицы для вращения объектов вокруг произвольных осей и т. Д. *

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

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

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

1 голос
/ 14 января 2010

Если честно, я как бы не согласен с большим количеством ответов здесь. Я написал свой первый компилятор (для забавы; у меня действительно слишком много кофе / свободного времени), не пройдя курс по компиляторам; в основном я просто сканировал код для другого компилятора и следовал шаблону. Я мог бы написать синтаксический анализатор C на макушке моей головы, но я не думаю, что мог бы вспомнить, как нарисовать автомат, если от этого зависела моя жизнь.

Когда я решил, что хочу поместить вывод типа в свой игрушечный (императивный) язык программирования, я сначала просмотрел, вероятно, пять статей, уставившись на что-то, называемое «типизированное лямбда-исчисление», что… *** ....? Сначала я пытался реализовать что-то с «общими переменными» и «неуниверсальными переменными» и не знал, что происходит. Затем я все это пересмотрел и сел с блокнотом, выясняющим, как я могу реализовать его практически с поддержкой всего, что мне нужно (подтипирование, первоклассные функции, параметризованные типы и т. Д.), Подумав пару дней И написание тестовых программ, я потратил больше недели, чтобы попытаться выяснить теоретическую чушь.

Знание основ вычислительной техники (т. Е. Как работает виртуальная память, как работают файловые системы, потоки / планирование, SMP, структуры данных) оказались чрезвычайно полезными. Теория сложности и вещи Big-O иногда оказывались полезными (особенно полезными для таких вещей, как проектирование СУБД). Проблема остановки и автомат / теория Тьюринга? Никогда.

1 голос
/ 01 февраля 2009

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

Вы не знаете, что ваш босс попросит вас сделать, возможно, вам придется использовать то, что, как вы думали, не принесет пользы, как сказал Джеффри Л. Уитледж.

1 голос
/ 06 января 2009

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

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

1 голос
/ 27 октября 2008

Потому что шаблоны C ++ на самом деле являются своего рода лямбда-исчислением. См. Www.cs.nott.ac.uk/types06/slides/michelbrink_types_06.pdf

1 голос
/ 26 октября 2008

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

...