Какую часть теории информатики я должен знать? [закрыто]

27

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

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

Джон Хопкинс
источник
42
1 (простите, пришлось)
хайлем
5
о, или самый значительный! (Я пойду сейчас ...)
Хайлем
Теоретическая информатика stackexchange подтверждает то, что все остальные упоминают здесь: сложность, структуры данных и алгоритмы. cstheory.stackexchange.com/tags
chrisaycock
2
Я чувствую необходимость возражать против этого вопроса. Нет «одного бита», который был бы достаточен для изучения, и более того, нет (ИМХО) одного «самого важного» бита. Есть несколько аспектов, которые (опять же, ИМХО) одинаково важны для CS. Поэтому я думаю, что, хотя ответы на этот вопрос могут быть интересными, вопрос мог бы быть сформулирован лучше.
Конрад Рудольф
1
Если бы у вас еще не было своего eeng, я бы сказал, булева логика и / или теория дискретных чисел. Почти каждые ifи loopутверждение когда - либо написанное использует подмножество этих двух областей исследования.
Стивен Эверс

Ответы:

52

Если я должен выбрать только один бит, который является трудным решением, я бы сказал , что пойти на нотации Big O . Понимание последствий O (n), O (ln n), O (n²), O (2 ^ n), O (n!) Поможет вам избежать множества дорогостоящих ошибок, которые хорошо работают в тестовая среда, но катастрофически не удается в производстве.

user281377
источник
2
+1, и я бы сказал, что более важно то, что просто зная, что O (n ^ 2) хуже, чем O (lg n) (например), нужно знать, как получить Big-O для данного фрагмента кода.
Дин Хардинг
3
Категорически не согласен. Этот материал относительно тривиален, и в CS есть более интересные темы. Кроме того , я думаю , что большинство людей думают о сложности интуитивно, хотя они не могли бы назвать его сложность , и они не могли бы назвать это квадратичная, показательная и т.д.
Magnus Wolffelt
Магнус: По моему опыту, большинство людей, не занимающихся программированием, вообще не думают о сложности, они интуитивно принимают O (n) для всех проблем.
user281377
Мне еще нужно это формально.
CaffGeek
1
Чад: В «Большой О-нотации» нет ничего слишком чересчур формализованного, но без названий вещей вы вряд ли сможете думать об этих вещах, не говоря уже о том, чтобы говорить об этом со своими сверстниками.
user281377
19

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

Mnementh
источник
Я бы добавил, что это очень помогает узнать, решаете ли вы проблему, которую можно легко перефразировать простым языком.
Philododad
Сложность важна как концепция, но на самом деле ее вычисление часто не так. Понимание того, что является менее сложным, является важным моментом.
Билл
@ Билл: Точно. Но эта часть - единственное, что вы не обязательно получите через практику. Теория очень полезна в этой части.
Мнемент
12

Узнайте о структурах данных, алгоритмах и сложности.

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

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

Знание моделирования базы данных также важно.

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


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

Это немного сложный вопрос.

Все аспекты информатики так или иначе важны.

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

Понимание Big O Notation важно, а также понимание того, как ваш код может выполняться, также очень важно в реальных ситуациях.

Темная ночь
источник
7

Да, это заставило меня задуматься часами.

В процессе я должен был удалить некоторые из общих ответов, приведенных здесь уже.

НЕТ СПИСКА

  1. Большая O (n) запись . Трудно выразить это здесь, но нет, мы можем интуитивно определить неэффективность и сравнить различные процедуры, даже не услышав об асимптотическом алгоритмическом анализе.

  2. Функциональные языки Нет. Единственная языковая семья - это всего лишь один подход к решению проблем. Почему только этот бит должен иметь значение?

  3. Проблема остановки Некоторые просто слишком конкретны, и люди жили жизнью, не зная, что они существуют.

  4. Слушай Если ты не слушаешь, ты живешь в своем собственном мире. Не обязательно вредно!

  5. Цикл разработки программного обеспечения Нах! Мы все еще можем пробиться к невероятному программному обеспечению или героическим усилиям.

  6. Теория сложности, я думаю, что это может быть, но без всех формализмов

Это немного идеи из Comp Science

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

Как только вы это знаете, вы начинаете учиться хорошо смотреть по сторонам.

Когда вы видите, что кто-то использует list insertionin pythonи not append, вы улыбаетесь, потому что знаете, что списки Python создаются с использованием абстракции массива, где вставки являются дорогостоящими и добавляют дешевле.

Это всего лишь один пример.

pyfunc
источник
+1 за ответ, который вы, очевидно, много обдумали.
Джон Хопкинс
просто комментарий на ваш комментарий к проблеме остановки: «Жить жизнью, не зная существующего» - это правда для ЛЮБОЙ темы информатики.
4

Теория автоматов и ФСМ. :-)

Прасун Саурав
источник
3

Конкурентные варианты использования структур данных.

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

Fanatic23
источник
3

Есть только три числа, которые имеют значение:

  • нуль
  • один
  • многие
Стивен А. Лоу
источник
но разве это не означает, что «3» также имеет значение?
Хавьер
Предполагается, что он равен нулю, единице и бесконечности: en.wikipedia.org/wiki/Zero_One_Infinity
Томас Оуэнс
@Javier: 3 является подмножеством многих
Стивен А. Лоу
@ Томас: говорит кто?
Стивен А. Лоу
@ Стивен Мое понимание может быть не на 100%, но я думаю, что идея в том, что у вас нет ничего, единственной вещи или количества вещей, которые у вас должны быть неограниченными. Если вы не ограничиваете ни одного или одного экземпляра, то вам не следует ограничивать экземпляры. Тем не менее, я не совсем уверен, ПОЧЕМУ это так (я только смутно знаком с концепцией Zero / One / Infinity).
Томас Оуэнс
3

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

JP Alioto
источник
Что именно вы подразумеваете под волатильностью?
Амара
3

Проблема остановки

Факт, что существуют проблемы, связанные с компьютером, которые просто не могут быть решены с помощью компьютера.


источник
3

Вы должны знать достаточно теории автоматов, чтобы знать, где проблема, с которой вы имеете дело, попадает в иерархию формальных языков. Исходя из этого, вы можете выяснить несколько важных практических применений, например, почему вы не должны использовать REGEX для разбора HTML (HTML требует контекстно-свободной грамматики для его описания) и почему компиляция C ++ занимает гораздо больше времени, чем Java или C # (C ++ требует машины Тьюринга, в то время как Java и C # могут быть описаны с помощью контекстно-свободных грамматик).

Наиболее важные уровни формальных языков, от самых слабых до самых сильных:

  1. Языки, которые могут быть проанализированы конечным автоматом или с помощью REGEX (реализации REGEX с обратными ссылками являются более мощными, чем эта категория, но они все еще не могут анализировать все в категории 2)

  2. Языки, которые могут быть проанализированы автоматами со стековой памятью или безконтекстной грамматикой.

  3. Языки, которые могут быть проанализированы машиной Тьюринга или автоматами с оперативной памятью.

Дэн Монего
источник
Нет Регулярное выражение анализирует грамматику. Это именно та категория грамматики, которая может быть принята конечным автоматом. И «грамматика Хомского» не относится исключительно к контекстно-свободным грамматикам, которые обрабатывают стековые машины.
Philodadad
@philosodad - грамматика, не зависящая от контекста, является более точной, и я обновил пост, чтобы использовать этот термин. Я не понимаю вашу проблему с тем, что я сказал о регулярных выражениях.
Дэн Монего
@Dan - Моя проблема в том, что регулярное выражение столь же мощно, как автомат с конечным состоянием, и если вы можете анализировать ЛЮБУЮ детерминированную контекстно-свободную грамматику с машиной, чем вы можете анализировать ВСЕ детерминированные контекстно-свободные грамматики.
Philodadad
Или, если быть более точным: либо вам нужен стек, либо нет. Если вам нужен стек для разбора языка, то у вас должен быть стек для разбора языка, и, следовательно, если языку требуется стек для его разбора, вы можете разобрать этот язык.
Philodadad
@philosodad - Существует два типа регулярных выражений - регулярные выражения в теории и регулярные выражения, реализованные в программном обеспечении. Вы правы относительно теоретических регулярных выражений, но большинство реализаций имеют несколько особенностей, выходящих за рамки их теоретической основы, и могут соответствовать некоторым нерегулярным языкам, например, ^ n для не простых n. Поскольку речь идет о теории на практике, я старался упомянуть, что существует разница между формальным определением и тем, которое используется в дикой природе.
Дэн Монего
2

Ну, я мог бы дать вам скучный ответ: теория автоматов и теория информации.

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

  • «Достаточно хорошо» не достаточно хорошо.
Майк Данлавей
источник
1

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

JB King
источник
2
Закон Мерфи: все, что может пойти не так, пойдет не так
Ричард
Это не теория CS, но это отличный ответ.
justkt
1

программирование

На факультете математики и компьютерных наук в колледжах Хобарта и Уильяма Смита поступает компьютерная наука 124 Введение в программирование :

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

Если вы не умеете программировать, вы не слишком далеко продвинулись в реальных вычислениях.

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

Является ли программирование информатики, как мы его знаем?

В ответ на комментарий @Thomas Owens, который указал (совершенно правильно), что программирование не является строго информатикой, я хотел бы процитировать статью из Википедии по информатике :

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

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

Гэри Роу
источник
Программирование не является теорией CS. На самом деле, я могу легко утверждать, что программирование вовсе не информатика.
Томас Оуэнс
@ Томас Оуэнс Я обновил свой ответ, чтобы подтвердить свое утверждение, что оно действительно. Не могли бы вы проверить это и сообщить мне ваши мысли?
Гари Роу
1
До сих пор не думаю, что программирование - это CS. Программирование МОЖЕТ быть полезным для компьютерного ученого, который хочет реализовать алгоритм или структуру данных, но темы в теории CS (от моего введения до книги по теории CS, так что, вероятно, есть и более сложные темы) включают логику, теорию автоматов, теорию графов. вычислимость, вычислительная сложность и анализ алгоритмов. Я также сказал бы, что языки программирования (теория, лежащая в основе разработки и реализации языка) также является частью информатики. Однако вам не нужно уметь программировать, чтобы стать хорошим ученым.
Томас Оуэнс
@ Томас Оуэнс Я понимаю вашу точку зрения и (надевает пуристскую шляпу) Я согласен. Тем не менее, ОП просит один бит CS, который поможет ему в реальном мире. Я твердо придерживаюсь своего мнения, что теория программирования (реализованная в хорошем коде) - это один бит. Я немного отредактировал соответственно.
Гэри Роу
Да. От CS я бы сказал, что понимание языков программирования и парадигм может помочь (особенно если вы реализуете DSL, но знание многих парадигм, таких как процедурная, функциональная, ОО, логика, просто помогает в разработке программного обеспечения). Понимание алгоритмов и структур данных также поможет вам выбрать правильный (-ые) для решения вашей проблемы наиболее эффективным способом. Теория автоматов может помочь (я когда-то работал с системой, которая когда-то была гигантским FSM, но я не знаю, насколько это распространено). Поэтому я бы сказал, что структуры данных, алгоритмы и теория PL были бы самыми полезными вещами из CS.
Томас Оуэнс
1

Я должен не согласиться с Конрадом Рудольфом. Есть одна часть компьютерной науки, которую вы должны знать, чтобы сделать вас лучшим «программистом в реальном мире». Если вы больше ничего не забираете из ответов, которые вы получаете здесь, по крайней мере, подумайте об этом - удовлетворение требований - это не то же самое, что удовлетворение клиента! Конечные пользователи ВСЕГДА будут пытаться использовать вашу программу так, как вы никогда не думали и не программировали. ВСЕГДА, ВСЕГДА, ВСЕГДА.

Поэтому, чтобы быть лучшим программистом, вы должны сначала СЛУШАТЬ. Слушай клиента. Слушай их нужды. Слушай их желания. И особенно, прислушайтесь к их уровню «технаря». Я не могу сказать вам, сколько раз я видел построенный проект, который был именно тем, о чем просили, но совсем не то, что на самом деле требовалось клиенту. Все потому, что программист, собирающий запрос, на самом деле не слушал.

Что-то еще, что вы можете убрать, если у вас нет опыта в разработке пользовательского интерфейса, попросите кого-нибудь спроектировать пользовательский интерфейс. Я ВСЕГДА могу определить приложение, в котором пользовательский интерфейс был разработан программистом, а не экспертом. То, что логично и имеет смысл для вас, не будет иметь смысла для клиента. И, если ваши клиенты не технологичны (и кто такие?), Тогда ваше «функционально правильное, но эстетически уродливое» решение будет встречено с теплотой скунса на званом обеде.


источник
3
Этот ответ не имеет отношения к теории CS, о которой спрашивал Хопкинс.
Джеймс
1

Функциональные языки!

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

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

Магнус Вольффелт
источник
0

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

therobyouknow
источник
-2

Решение проблем и желание продолжить обучение!

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

Брайан Харрингтон
источник
6
Это не теория компьютерных наук, они в равной степени применимы к электронной (или почти любой другой форме) инженерии.
Джон Хопкинс
Как я понимаю, учесть ваш пример, зная быструю сортировку, просто бесполезно. Знание того, что оно существует, и то, что делает его особенным, полезно, но это также один поиск в Google, если я ничего не знал об этом. Знание любого алгоритма также не помогает. Тем не менее, зная, как создать и интерпретировать один это! Возможно, если бы я мог изменить свой ответ, Сложность, наверное, самая важная.
Брайан Харрингтон
1
Вы не можете искать что-то, если не знаете, что вам это нужно или что оно существует. Ваш ответ перечисляет важные качества, которые должен иметь разработчик, но не отвечает на поставленный вопрос.
Адам Лир