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

Конкретные:

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

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

• последовательность
• последовательность с произвольным доступом
• словарь (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):

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

Протоколы:

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

ООП:

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

Упражнения:

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

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

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

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

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

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

Игра “Жизнь”:

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

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

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

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

Решатель Sudoku:

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