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

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

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

Ответы [ 24 ]

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

Правдивая история:

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

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

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

Так вот один пример.

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

Когда я закончил колледж, я предположил, что я был наравне со всеми остальными: «У меня есть степень бакалавра в области CS, как и у многих других людей, и мы все можем делать по существу одни и те же вещи». В конце концов я обнаружил, что мое предположение было ложным. Я выделялся, и мой опыт был во многом связан с этим - особенно моя степень.

Я знал, что было одно «небольшое» различие в том, что у меня был «Б.С.» в CS, потому что мой колледж был одним из первых (предположительно, № 2 в 1987 году) в стране, который получил аккредитацию по программе CS, и я получил второе образование, чтобы получить эту аккредитацию. В то время я не думал, что это имеет большое значение.

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

После колледжа (USAFA) я провел четыре года в Военно-воздушных силах, два из которых подали заявку на получение степени CS. Там я заметил, что очень немногие из моих коллег имели дипломы или даже обучение, связанное с компьютерами. Военно-воздушные силы отправили меня на пять месяцев сертификационной подготовки, где я снова обнаружил отсутствие степеней или подготовки. Но здесь я начал замечать разницу - стало совершенно очевидно, что многие из людей, с которыми я столкнулся, ДЕЙСТВИТЕЛЬНО не знали, что они делают, и это включало людей с обучением или степенями. Разрешите, пожалуйста, проиллюстрировать.

В моей сертификационной подготовке ВВС было всего тринадцать человек (включая меня). Как офицеры ВВС или эквивалент, у всех нас были степени бакалавра. Я был в середине, основываясь на возрасте и звании (я был O-2 среди шести O-1 и шести O-3 и выше). В конце этого обучения ВВС отметили нас всех одинаково компетентными для приобретения, создания, проектирования, обслуживания и эксплуатации ЛЮБОГО компьютера или системы связи для ЛЮБОЙ части Министерства обороны.

Однако из тринадцати из нас только шесть имели какую-либо форму степени, связанной с компьютером; остальные семь имели степень от аэронавтики до химии / биологии и психологии. Из шести человек со степенями CS я узнал, что двое никогда не писали никаких программ и никогда не пользовались компьютером чаще, чем небрежно (написание статей, игры в игры и т. Д.). Я узнал, что еще двое из нас написали ровно одну программу на одном компьютере во время обучения по программе CS. Только один человек и я написали более одной программы или использовали более одного типа компьютера - действительно, мы обнаружили, что мы оба написали много программ и использовали много типов компьютеров.

К концу нашего пятимесячного обучения нашему классу был назначен программный проект, и мы были разделены на четыре группы, чтобы выполнить его отдельно. Наши преподаватели разделили класс, чтобы справедливо распространить «талант программиста», и им были назначены роли руководителя команды, технического лидера и разработчика. Каждой группе была предоставлена ​​неделя для реализации (в Аде) полноэкранного текстового пользовательского интерфейса (это был 1990 год) для имитатора полета поверх библиотеки лётной механики, предоставляемой инструктором. Я был назначен техническим руководителем для моей команды из четырех человек.

Руководитель моей команды (у которого не было компьютерного образования) попросил остальных троих разделить проект на задачи, а затем назначил треть из них каждому из нас. Я выполнил свою третью задачу к середине первого дня, а затем провел остаток дня, помогая двум другим своим товарищам по команде, разговаривая с руководителем моей команды (BSing; ^) и играя на моем компьютере.

На следующее утро (второй день) руководитель моей команды в частном порядке сообщил мне, что два других члена нашей команды не достигли прогресса (один не мог написать заявление «если», которое будет компилироваться), и он попросил меня взять их Работа. Я закончил весь проект к середине дня, и моя команда провела остаток дня на симуляторе.

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

Между тем, к середине третьего дня я заметил, что симулятор полета, похоже, ведет себя «неправильно». Поскольку один из моих одноклассников получил степень в области аэронавтики, я спросил его об этом. Он был озадачен, а затем признался, что на самом деле не знал, что заставило самолет летать!?! Я был ошеломлен! Оказывается, вся его дипломная программа была посвящена исследованиям безопасности и аварий - без реальной математики или науки за полетом. С другой стороны, у меня была небольшая доля в аэронавтике (помните USAFA?), Но мы разработали крылья и провели реальные испытания в аэродинамической трубе. Поэтому я спокойно провел остаток недели, переписывая предоставленную инструктором библиотеку лётной механики, пока симулятор не полетел «правильно».

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

Итак, что именно я обнаружил? Не все равны, и это нормально - я не лучший человек, потому что могу эффективно программировать, но я более полезен, ЕСЛИ это то, что вам нужно от меня. Я узнал, что мой фон действительно имел значение: рос в семье электриков и инженеров-электриков, комплекты строительной электроники, читая буквально каждую компьютерную книгу в школьных / публичных библиотеках, потому что у меня не было доступа к настоящему компьютеру, затем переезжает в новый город, где в моей школе были компьютеры, затем получить свой компьютер в подарок, посещать школы, в которых были компьютеры разных размеров и типов (от ПК до мэйнфреймов), получение аккредитованной степени в ОЧЕНЬ хорошей инженерной школе, писать много программ на разных языках на разных компьютерах, необходимость писать сложные программы (например, мою собственную виртуальную машину с пользовательским языком ассемблера или реализацию сжатия Хаффмана и т. д.), необходимость устранения неполадок для себя, собирать свои компьютеры из частей и устанавливать ВСЕ программное обеспечение, и т.д.

В конечном итоге я узнал, что мои способности основаны на знании того, как компьютеры работают с электрического уровня на дискретных электронных компонентах, схемах, подсистемах, интерфейсах, протоколах, битах, байтах, процессорах, устройствах, драйверах, библиотеки, программы, системы, сети, вплоть до огромных конгломератов корпоративного класса, над которыми я обычно работаю сейчас. Поэтому, когда эта чертова штука плохо себя ведет, я точно знаю, КАК и ПОЧЕМУ. И я знаю, что нельзя сделать так же, как и то, что можно. И я много знаю о том, что было сделано, что было опробовано и что осталось относительно неисследованным.

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

И я вполне доволен этим. Но я рекомендую вам попробовать.

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

Конечно, это полезно.

Представьте себе разработчика, работающего над движком шаблонов. Вы знаете такие вещи ...

Blah blah blah ${MyTemplateString} blah blah blah.

Всё начинается просто, с нахальным маленьким регулярным выражением для выполнения замен.

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

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

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

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

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

Но подождите !!! Кто-то из команды отмечает, что, если язык шаблонов действительно завершен по Тьюрингу, то задача оценки времени выполнения каждой операции рендеринга является примером проблемы остановки !! Yikes, не делай этого !!!

Суть теории на практике заключается в том, что вся практика основана на теории. Теоретически.

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

Вещи, которые я использую больше всего:

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

Что касается всего этого на машинах Тьюринга и т. Д. Я думаю, что это важно, поскольку оно определяет ограничения, при которых мы все работаем. Это важно ценить.

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

разница между обучением алгебре и обучением использованию калькулятора

если вы знаете алгебру, вы понимаете, что одна и та же проблема может проявляться в разных формах, и вы понимаете правила ее преобразования в более краткую форму

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

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

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

Мой друг работает над языком с некоторыми шаблонами. Меня попросили сделать небольшую консультацию. Часть нашего обсуждения касалась возможности шаблонов, потому что, если бы шаблоны были выполнены по Тьюрингу, им пришлось бы действительно учитывать свойства VM-ish и то, как / если их компилятор будет поддерживать их.

Моя история на этот счет: теория автоматов все еще преподается, потому что она все еще имеет отношение. Проблема остановки все еще существует и ограничивает ваши возможности.

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

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

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

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

Воск включен ... Воск выключен ... Воск включен ... Воск выключен ... Как это вообще связано с каратэ?

6 голосов
/ 28 октября 2008

На одной работе мне было поручено усовершенствовать алгоритм трассировки сети нашей модели распределения электроэнергии, поскольку тот, который они использовали, был слишком медленным. Трехфазная сеть была, по сути, тремя n-деревьями (поскольку в электрических сетях петли не допускаются). Узлы сети находились в базе данных, и некоторые из первоначальной команды не могли понять, как построить модель в памяти, поэтому отслеживание выполнялось последовательными глубинными SELECT в базе данных с фильтрацией на каждом этапе. Таким образом, чтобы отследить узел для десяти узлов с подстанции, потребовалось бы как минимум 10 запросов к базе данных (первоначальными членами команды были базы данных, но им не хватало приличного фона в алгоритмах).

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

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

Печально то, что мне пришлось практически преподавать класс по n-деревьям, двоичным деревьям, указателям и двусвязным спискам нескольким другим программистам, которые обучались базам данных и VB, чтобы они могли понять алгоритмы.

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

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

«Как» - это очень мало из реальной работы, которую вы ожидаете делать с информатикой. Фактически, большинство успешных инженеров, которых я знаю, вероятно, поставили бы это менее чем на 20 процентов фактической работы. «Что» делать гораздо важнее; и для этого основы информатики имеют решающее значение. «Что» вы хотите сделать, имеет гораздо большее отношение к дизайну, чем к реализации; и хороший дизайн ... ну, давайте просто назовем это "нетривиальным".

"Существует два способа конструирования программного обеспечения: один из них состоит в том, чтобы сделать его настолько простым, чтобы не было никаких недостатков, а другой - сделать его настолько сложным, чтобы не было недостатки. Первый метод гораздо сложнее. " - АВТОМОБИЛЬ Хора

Удачи в учебе!

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

Большинство знаний не является «практическим», но помогает вам соединять точки способами, которые вы не можете предвидеть, или дает вам более богатый словарный запас для описания более сложных идей.

...