Какие концепции компьютерных наук я должен знать? [закрыто]

95

Как вы думаете, какие концепции компьютерных наук сделали вас лучшим программистом?

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

Особенности языка

  • Указатели и рекурсия (спасибо, Джоэл!)

Структуры данных

  • Связанные списки
  • Хеш-таблицы

Алгоритмы

  • Пузырьковые сортировки

Очевидно, что на данный момент список немного короткий, поэтому я надеялся на предложения относительно:

  1. Какие концепции я должен понимать,
  2. Любые хорошие ресурсы для их правильного понимания (поскольку Википедия иногда может быть немного скучной и академической).
Джон Артус
источник
5
Виды пузырей? Держитесь от них как можно дальше! Скорее узнайте, как работает quicksort / heapsort.
Carra
18
Да выучите Bubbleort. Узнайте, почему это ужасно. Изучите быструю сортировку, сортировку слиянием и все остальное, включая их индивидуальные недостатки. Но не записывайте их в производственном коде: вызывайте функции сортировки, предоставляемые любой платформой, на которой вы находитесь.
Брайан Энсинк,
@Roger Pate - +1 для вас, нужно знать, для чего нужен алгоритм или структура данных, а в чем - отстой. И Quicksort, и Bubblesort имеют одинаковую производительность в худшем случае [O (n ^ 2)], но для очень разных типов входных данных, а Bubblesort имеет лучшую производительность O (n), где QS по-прежнему O (n log n). Конечно, если вы рассматриваете пузырьковую сортировку, вы можете вместо этого выбрать сортировку вставкой.
Андре Артус

Ответы:

60

Взгляните на это сообщение в блоге Стива Йегге (ранее работавшего в Amazon, теперь в Google):

В нем подробно рассматриваются пять наиболее важных концепций, которые разработчики должны знать:

  1. Базовое программирование (включая рекурсию, файловый ввод-вывод, форматированный вывод, циклы и т. Д.)
  2. Объектно-ориентированный дизайн (включая шаблоны проектирования и т. Д.). Вы должны уметь создавать разумные объектно-ориентированные проекты, а также понимать концепции.
  3. Сценарии и регулярные выражения.
  4. Структуры данных - списки, множества, хэш-таблицы, деревья, графики и т. Д. - а также нотация Big O и алгоритмическая сложность.
  5. Биты, байты и двоичные числа - как числа представлены в компьютере и как ими управлять.
оборота джеммикейков
источник
Хорошая ссылка. Немного сосредоточено на стороне unix (полностью отсутствует .NET), но все же приятно.
Toon Krijthe
Отличная ссылка - мне есть над чем поработать, я просто хотел бы, чтобы у нее были ссылки на хорошие страницы, объясняющие эти вещи.
Джон Артус,
Ссылка будет мне очень полезна, чтобы проверить себя и разобраться в основах. Спасибо ..
rpr
Согласен, отличная ссылка. Хотя многие из идентифицированных возможных решений основаны на Unix, общие концепции не зависят от языка / платформы. Для большинства программистов такие вещи, как рекурсия, написание ADT, например, деревья, и побитовые операции довольно редки, но они являются важной основой.
Зак Бурлингейм,
4
Я согласен со всем, кроме регулярных выражений. Это хороший бонус, но большая часть материала - это основы начального уровня, фундамент, на котором все построено ... регулярные выражения - это здорово, но я знаю множество отличных программистов, которые никогда их не используют и никогда не нуждаются в них.
Beska
35

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

оборота острый зуб
источник
1
Вы можете начать со статьи в Википедии, на которую я ссылаюсь - это довольно просто и математически правильно.
Sharptooth
3
Вы должны иметь довольно низкое мнение о продвинутой математике. Я понял это на первом году обучения в колледже, когда я только частично изучил математику.
GoatRider
1
Не забывайте концепцию NP, и когда проблема содержится в ней, разработчик, который пытается закодировать TSP (Коммивояжер) в каждую транзакцию базы данных с целью поиска или какой-то другой подобный идиотизм, является серьезной проблемой =]
Эд Джеймс
2
Вы также должны знать, что большой O не говорит вам, какой алгоритм занимает меньше времени. То, чего не понимают большинство выпускников CS
Мартин Беккет,
3
Это вроде как. Он сообщает вам, какой из них имеет лучший наихудший случай, и не обязательно, какой из них «быстрее», поскольку это зависит от входного набора.
Эд Джеймс,
30

Мне кажется немного забавным, что вы ищете предметы по информатике , но находите Википедию слишком академической: D

Во всяком случае, здесь идет, в произвольном порядке:

Рик
источник
2
+1, потому что вы упомянули базы данных, которые часто упускаются из виду в таких списках, но это очень важная концепция, которую должен знать любой хорошо подготовленный выпускник CS.
Брайан Энсинк,
14

Некоторые концепции, которые помогли моему развитию (интеллект и код):

  • Лексирование, синтаксический анализ, сопоставление строк, регулярное выражение
  • Мемоизация
    • инкапсуляция / определение объема / закрытия
    • кеширование
  • Рекурсия
  • Итераторы / генераторы
  • Функциональное программирование - изумительная статья Джона Хьюза заставила меня задуматься "почему?"

Это целые области дискретной математики, но для CS требуется серьезное введение:

  • Матрица / линейная алгебра
  • Теория графов

Хотя лекции и статьи Марка Джейсона-Доминуса часто адресованы хакерам Perl, я думаю, что любой программист выиграет от его ясного представления и реального кода, особенно на Perl высшего порядка .

оборота бубакер
источник
10

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

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

Джереми Френч
источник
10

Я вижу несколько хороших концепций CS, но мало говорю о математике.

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

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

Беркшир
источник
1
Если бы мне пришлось выбрать только одну, это была бы дискретная математика. Это в значительной степени CS 101. Мне трудно придумать область или парадигму в общем программировании, которую DM каким-либо образом не затронет.
Андре Артус
7

Матрица компетенций программистов подробно рассмотрела это, но я выделю пару:

  • Структуры данных
    • Расширенные структуры данных, такие как B-деревья, биномиальные и кучи Фибоначчи, AVL / красно-черные деревья, Splay Trees, списки пропуска, попытки и т. Д.
  • Алгоритмы
    • Дерево, График, простые жадные алгоритмы и алгоритмы «разделяй и властвуй» способны понять значимость уровней этой матрицы.
  • Системное программирование
    • Понимает весь программный стек, аппаратное обеспечение (ЦП + память + кэш + прерывания + микрокод), двоичный код, сборку, статическое и динамическое связывание, компиляцию, интерпретацию, JIT-компиляцию, сборку мусора, кучу, стек, адресацию памяти…
  • Контроль версий исходного кода
    • Знание распределенных систем VCS. Пробовал Bzr / Mercurial / Darcs / Git
  • Автоматизация сборки
    • Может настроить сценарий для сборки системы, а также документацию, установщики, создать примечания к выпуску и пометить код в системе контроля версий.
  • Автоматизированное тестирование
    • Понимает и может настраивать автоматизированные функциональные, нагрузочные / производительные и пользовательские тесты.
  • Разложение проблемы
    • Использование соответствующих структур данных и алгоритмов и создание универсального / объектно-ориентированного кода, который инкапсулирует аспекты проблемы, которые могут быть изменены.
  • Разложение систем
    • Способен визуализировать и разрабатывать сложные системы с несколькими линейками продуктов и интеграции с внешними системами. Также должна быть возможность разрабатывать системы поддержки операций, такие как мониторинг, отчетность, отработка отказа и т. Д.
cgp
источник
5

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

Mork0075
источник
4

Правило 1. Программное обеспечение - это сбор знаний . Программное обеспечение что-то значит. Если вам неясно значение, потратьте больше времени на разговоры с пользователями, чтобы понять, что они делают.

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

Как можно быстрее отучитесь от пузырьковой сортировки. Шутки в сторону. Все современные языки (Java, Python и т. Д.) Имеют классы коллекций, которые реализуют лучшую сортировку, чем пузырьковая сортировка. Нет абсолютно никаких обстоятельств, при которых вам следует использовать пузырьковую сортировку для чего-либо. Вам следует искать класс коллекции, который включает метод сортировки. Более того, вам следует искать алгоритм, который полностью избегает сортировки.

Вы должны выучить несколько языков.

  • Язык программирования (Java, Python и др.)

  • Язык оболочки.

  • Язык базы данных (SQL)

  • Языки представления (HTML и CSS)

  • Другие языки представления данных (XML, JSON)

Вы должны изучить несколько структур данных.

  • Последовательности (списки, кортежи, файлы)

  • Иерархический (как документы XML и HTML, а также основная файловая система)

  • Реляционные (например, базы данных и файловая система с добавленными жесткими и программными ссылками)

  • Карты (или индексы, или ассоциативные массивы), включая хэш-карты и древовидные карты

  • Наборы

Плюс некоторый анализ алгоритмической сложности. Иногда называют «Большой О». Плохая пузырьковая сортировка состоит в том, что это O ( n ^ 2), где быстрая сортировка - O ( n log n ).

С.Лотт
источник
Для справки, я бы никогда не использовал пузырьковую сортировку! Мне только что было интересно узнать, как это работает, и я решил, что есть еще несколько таких алгоритмов, которые люди должны понимать достаточно хорошо, чтобы писать на своем языке.
Джон Артус,
Есть бесчисленное множество алгоритмов. Большинство из них плохие. Некоторые из них хороши. Пузырьковая сортировка - это просто плохо. Купите ЛЮБУЮ книгу по алгоритмам и двигайтесь дальше.
S.Lott
Просто придирки, но Quicksort - наихудший случай O (n ^ 2). Я указываю на это только потому, что считаю понимание того, почему это правда, является ценным образовательным упражнением при изучении фундаментальных алгоритмов.
Брайан Энсинк,
Для быстрой сортировки да - важное упражнение. Для пузырьковой сортировки нужно только увидеть, насколько это действительно плохой алгоритм. В целом важно понимать типичный и худший случай.
S.Lott
4

Ну, теперь банка с червями открыта! :)
Я начинал с электротехники.

Дизайн реляционной базы данных: отслеживание данных похоже на Арнольда в «Детском саду».
Это может быть полный хаос. Это нужно контролировать.
Как хранить ваши данные в минимальном количестве мест и с минимальным количеством дублирования информации. Как сохранить ваши данные легкими и доступными. Как контролировать рост и целостность данных.

Дизайн пользовательского интерфейса (UI): именно так пользователь должен получить доступ к данным, которые мы отслеживаем.
Большинство пользовательских интерфейсов разрабатываются разработчиками. Таким образом, большинство пользовательских интерфейсов, к сожалению, параллельны дизайну базы данных. Пользователи вообще не заботятся о дизайне данных. Они просто хотят того, чего хотят. Они хотят получить это легко. Обычно это требует большого разделения от дизайна данных и пользовательского интерфейса. Научитесь отделять "инженерное" вас от "южного гостеприимства".

Объектно-ориентированное программирование: многие языки сводятся к этому формату.

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

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

События контролируют ... Методы делают свою работу:
держите вещи отдельно в вашем коде. Это позволяет другим пользователям делать обновления в будущем. Это также несколько аналогично структуре Модель / Представление / Контроллер (MVC).

PJ

PJ
источник
3

Для меня я многому научился на следующем курсе в университете

  • Управление проектом
  • Взаимодействие человека с компьютером (помогает нам, гикам, создавать более удобные экраны)
  • Дизайн базы данных (включая принципы работы баз данных, журналы транзакций, блокировку и т. Д.)
  • Хранилище данных
  • Графика (OpenGL)
  • Продвинутые алгоритмы
  • Структуры данных

То, что я хотел бы сделать в университете

  • Конструкция компилятора
  • Шаблоны проектирования
  • Теория автоматов
уридий
источник
3

ЛОГИКА - Я просто преувеличиваю важность логики в программировании. Вы сказали, что изучали машиностроение, поэтому должны знать, насколько математика может облегчить вашу жизнь.

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

Тамаш Чинеге
источник
3

Я думаю, что хорошо знать, как работает компилятор. У Ахо есть классическая книга по концепциям, используемым при создании компилятора. Название - «Компиляторы: принципы, методы и инструменты». Его прозвище - Книга Дракона. Чтобы по-настоящему понять эту книгу, вы должны понимать формальные языки. У Хопкрофта есть хорошая книга по этому поводу - Введение в теорию автоматов, языки и вычисления.

зооропа
источник
2

Инкапсуляция

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

Давид Басараб
источник
2

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

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

  • Общие концепции объектно-ориентированного программирования и функции современного языка программирования (классы, скрытие данных и т. Д.).
  • Метрики производительности алгоритма (нотация Big O). При разработке алгоритма выполнение анализа Big O для определения стоимости алгоритма и поиск более эффективных альтернатив в узких местах.
  • Связанные списки и другие сложные структуры данных.
  • Быстрая сортировка и разные концепции сортировки.
  • Деревья и быстрое манипулирование деревьями.

Если ваш язык / платформа не поддерживает сборку мусора, выделение памяти и очистка имеют решающее значение и будут добавлены в список.

Pearcewg
источник
2

Я поддерживаю дискретную математику. Информатика - это абстракция. очень полезно научиться думать как математик.

Я также хотел добавить к тому, что С.Лотт сказал о языках. Также важно изучить несколько ТИПОВ языков. Не просто скомпилировано против сценариев. Но функциональная (ML, Lisp, Haskell) логическая (Prolog) объектно-ориентированная (C ++, Java, Smalltalk) императивная (C, Pascal, даже FORTRAN).

Чем больше парадигм программирования вы знаете, тем легче будет освоить новые языки, когда появится популярный новый язык!

Брайан Постоу
источник
2

Некоторые концепции ОС

 ( memory, IO, Scheduling, process\Threads, multithreading )

[хорошая книга « Современные операционные системы , 2-е издание, Эндрю С. Таненбаум»]

Базовые знания компьютерных сетей

[хорошая книга Таненбаума

Концепции OOPS

Конечный автомета

Язык программирования (сначала я изучил C, затем C ++)

Алгоритмы (время \ пространственная сложность, сортировка, поиск, деревья, связанный список, стек, очередь)

[хорошая книга Введение в алгоритмы ]

aJ.
источник
авто мета? - обязательно «автоматы» по первой правке.
Том Дакеринг,
Ой! я увяз в проверке правописания. Я поправлю. Спасибо.
А.Дж.
1

Постарайтесь разобраться во всех уровнях программирования. От самого низкого уровня (сборки) до самого высокого уровня.

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

Chrys
источник
1

Алгоритмы.

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

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

Подводя итог - взгляните на Введение в алгоритмы.

Не нужно осваивать это, просто знайте, что происходит ...

Лиран Ореви
источник
1

Как недавний выпускник информатики я бы порекомендовал следующее:

  • Как упоминалось в различных сообщениях, нотация Big O

    OO Дизайн

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

    Операционные системы http://www.amazon.com/Modern-Operating-Systems-2nd-GOAL/dp/0130313580

    Проблемы НП

CodeMonkey
источник
1

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

Если вы посмотрите на SOA или DDD, все они в конечном итоге возвращаются к той или иной форме концепций ООП.

Я бы порекомендовал вам получить несколько хороших книг по ООП и для начала выбрать богатый язык, такой как C # или Java.

ООП Грэди Буч

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

Шрикар Додди
источник
1

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

лямбда
источник
1

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

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

Джон Хайленд
источник
0

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

Семафоры, критические секции и события.

Джим Т
источник
0

Нет, не пузырьковая сортировка, а быстрая сортировка. Это большая вещь - пузырьковая сортировка в среднем составляет O (n ^ 2), быстрая сортировка - O (n * log (n)).

GoatRider
источник
0

Я бы сказал, что ниже самые важные вещи

  • Объектно-ориентированного программирования
  • Понятия операционной системы
    • Процесс и поток
    • Алгоритмы планирования
  • Структура данных
    • Тип хранения и сбора данных, типы (связанный список, хеш, массив и т. Д.)
    • Алгоритмы сортировки
    • Сложность алгоритмов

Затем перейдите к конкретному языку. Надеюсь, это поможет !!

Мутант
источник
0

Я бы начал с цитаты:

«Если у вас есть только молоток, вы относитесь ко всему как к гвоздю». (Авраам Маслоу)

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

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

Этот совет согласуется с сегодняшней тенденцией для многоязычных проектов (возьмем, например, веб-приложения, которые могут включать несколько языков в одном приложении, например C #, JS, CSS, XPath, SQL, XML, HMTL, RegExp .... и даже различные парадигмы программирования (например, C # недавно представил некоторые концепции из парадигм функционального программирования, лямбды).

Итак, главное - это постоянное обучение, навсегда :)

майкинетор
источник
0

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

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

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

Чувак
источник
0

Поскольку машины с несколькими ядрами (как CPU, так и GPU) становятся стандартом, я бы сказал, чтобы включить распределенные алгоритмы (от нескольких потоков до нескольких машин). Очень важно понимать многопоточность и распределенную обработку. Извините, что ссылка на самом деле не очень помогает.

Эрих Мирабаль
источник