Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Моё представление о необходимом минимуме знаний чтобы что-то программировать более-менее осмысленно.

Вступление

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

Философия такова. Для того чтобы осмысленно программировать на начальном этапе не нужно знать Computer Science, теорию алгоритмов и сложности вычислений или детально разбираться в устройстве и работе компьютера. Достаточно хорошо делать две вещи:

  1. алгоритмизировать решение задачи (разбивать его на простые последовательные шаги: сначала это, а потом вот это),
  2. знать, понимать смысл и назначение, использовать и подгонять друг к другу стандартные элементы решений (условия, циклы, структуры данных, алгоритмы и прочие "паттерны")

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

Конкретные:

  • массив
  • список (односвязный, двусвязный)
  • бинарное дерево
  • хеш-таблица -- за компанию является примером соединения первых двух структур

Абстрактные:

  • последовательность
  • последовательность с произвольным доступом
  • словарь (dictionary), он же - отображение (map)
  • множество (set)
  • стек (stack)
  • очередь (queue)
  • дек (dequeue)

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

Продвинутые (для начала можно не учить):

  • красно-чёрные деревья (red-black trees)
  • finger trees
  • B-trees
  • rope
  • trie (prefix tree)
  • heap

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

Алгоритмы:

Сортировка:

  • сортировка выбором минимума/максимума -- просто для разминки
  • быстрая сортировка (quick sort) -- классика, нужно понять как рекурсивный, так и итеративный ("циклический") вариант
  • сортировка слиянием (merge sort) -- используется сплошь и рядом
  • radix sort

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

Для развития можно ещё изучить

  • сортировка вставкой в бинарное дерево
  • heap sort

Поиск:

  • прямой поиск
  • бинарный поиск

Это как упражнения для самых маленьких. Для развития мышления нужно изучать алгоритмы поиска подстроки в строке -- Кнута-Морриса-Пратта хотя бы.

Алгоритмы на структурах данных:

  • вставка элемента (в первую/последнюю/произвольную позицию)
  • удаление элемента
  • поиск элемента
  • обход (перебор всех элементов)

Алгоритмы на последовательностях:

  • отображение (map)
  • фильтрация (filter)
  • свёртка левая (fold left, foldl), правая (fold right, foldr) и её вариант -- reduce
  • префиксная сумма (prefix sum, scan)

Работа с текстом:

Регулярные выражения (regexps):

Основа и классика. Следует выучить синтаксис и разобраться в работе "классических" регулярных выражений. Полезно познакомиться с Perl-compatible regular expressions (pcre), понять принципиальные отличия от "классических": преимущества и недостатки.

В этом контексте любознательные могут познакомиться с теорией (конечных) автоматов и узнать как regexp'ы преобразуются в КА -- недетерминированные и детерминированные. Далее можно узнать что такое регулярные грамматики, контекстно-свободные, контекстно-зависимые и грамматики общего вида. Вопрос "на засыпку" -- можно ли регулярными выражениями разбирать XML? Почему?

Это подводит нас к следующему разделу -- "продвинутому".

Автоматические парсеры:

Системы формального описания и автоматического построения парсеров грамматик (и лексеров здесь же) -- такие как yacc, bison, ANTLR и т.п. Любознательные могут в дополнение познакомиться с комбинаторами парсеров, но если ничего не поймут - пусть бросают, потом вернутся.

Многопоточное программирование:

Вообще-то, есть два варианта -- parallel и concurrent -- существенно различающихся между собой, но в русской терминологии толком не обособляющиеся. Первый -- когда большой объём однородных данных обрабатывается поэлементно (более-менее) одинаковым образом независимо друг от друга. Параллельно. Второй -- когда есть много (более-менее) одновременно выполняющихся задач (процессов, потоков, нитей), которые могут выполнять абсолютно разные работы.

И то, и другое слишком сложно чтобы писать самому с нуля. Кроме того -- очень подверженно нетривиальным ошибкам. Лучше всего пользоваться готовыми библиотеками, которые делают то что нужно заведомо правильным образом. Категорически НЕ рекомендуется пользоваться такими механизмами синхронизации как мьютексы, семафоры и прочие критические секции. Лучше всего пользоваться библиотечными "параллельными" или "синхронными" коллекциями, преимущественно -- очередями.

Сетевое программирование:

Сокеты (sockets):

Необходимо понимать абстракцию сокета, виды сокетов, режимы работы.

Протоколы:

  1. TCP, UDP -- запоминать структуру пакетов необязательно, достаточно понимать что там есть и какие свойства протокола обеспечивает
  2. HTTP -- повсеместен. Следует знать форматы запросов и ответов, основные заголовки. Хотошо бы знать сопутствующие стандарты: HTML, XML, JSON, MIME и т.д.

ООП:

Нет никакого "объектно-ориентированного программирования" -- есть "объектно-ориентированное проектирование". ООП -- это способ структурирования программы в целом. "Мясом" программы остаются структуры данных и алгоритмы, но ООП позволяет аккуратно их "упаковать", чтобы "кишки" не торчали наружу и было удобно пользоваться. Это называется "инкапсуляция". Наследование -- штука непростая и противоречивая. Прежде всего, нужно понять разницу между "наследованием интерфейса" и "наследованием реализации". Второго лучше избегать, хотя в примерах такое может быть сплошь и рядом. Примеры намеренно упрощают архитектуру и потому учат неправильным "шаблонам". Нужно внимательно читать и разбираться в "шаблонах проектирования" (design patterns) -- хорошо бы почитать оригинальную книжку "банды четырёх" (gang of four, GoF), но можно читать переложения на другие языки и более современные варианты.

Упражнения:

Упражнения в освоении программирования -- важнее всего остального. Программирование -- это не про то, что ты знаешь, а про то, что ты можешь сесть и написать руками.

Для разминки:

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

Написать программу преобразования текста в код Морзе и обратно.

Консольный калькулятор:

Классический пример. Читаем выражения одно за другим, производим вычисления и выводим результаты. Можно делать с разным уровнем сложности: выражения записываются в обратной польской нотации (RPN) или в обычной инфиксной, без переменных или с переменными, можно добавить встроенные функции и т.д.

Игра "Жизнь":

Культовый алгоритм не только для компьютерщиков, но и для математиков -- почитать можно на Википедии, но лучше в книжке Мартина Гарднера. Графический вывод можно и не делать -- текстового достаточно. Для упражнения важно реализовать сам алгоритм.

Консольный Excel:

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

В задаче есть несколько "подводных камней", обсуждение можно найти в Рунете.

Решатель Sudoku:

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

@aliev

This comment has been minimized.

Copy link

@aliev aliev commented Apr 18, 2013

Спасибо отличная статья! Я алгоритмы изучаю по книге Седжвика - Алгоритмы на Java. Книга отличная, вот только перевод на русском ужасен :-)

@gabriel-fallen

This comment has been minimized.

Copy link
Owner Author

@gabriel-fallen gabriel-fallen commented May 20, 2013

Спасибо на добром слове! :)

Судя по содержанию, http://interactivepython.org/courselib/static/pythonds/index.html - почти идеально отражает моё представление о том, как следует строить курс программирования. Но сам не читал.

@aliev

This comment has been minimized.

Copy link

@aliev aliev commented Nov 6, 2013

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

@gabriel-fallen

This comment has been minimized.

Copy link
Owner Author

@gabriel-fallen gabriel-fallen commented Nov 25, 2013

Мне уведомления о комментариях тоже не приходят...
Если будете собирать переводчиков - сообщите, пожалуйста. Постараюсь принять участие.
Только лучше на email пишите. :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment