Во-первых, это моё мнение, и я его никому не навязываю. Во-вторых, список не обязательно исчерпывающий. В-третьих, он ориентирован на определённую "философию", которая тоже не является исчерпывающей или абсолютно правильной. Поэтому, если Вам эти рекомендации не подходят -- не следуйте им.
Философия такова. Для того чтобы осмысленно программировать на начальном этапе не нужно знать Computer Science, теорию алгоритмов и сложности вычислений или детально разбираться в устройстве и работе компьютера. Достаточно хорошо делать две вещи:
- алгоритмизировать решение задачи (разбивать его на простые последовательные шаги: сначала это, а потом вот это),
- знать, понимать смысл и назначение, использовать и подгонять друг к другу стандартные элементы решений (условия, циклы, структуры данных, алгоритмы и прочие "паттерны")
- массив
- список (односвязный, двусвязный)
- бинарное дерево
- хеш-таблица -- за компанию является примером соединения первых двух структур
- последовательность
- последовательность с произвольным доступом
- словарь (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)
Основа и классика. Следует выучить синтаксис и разобраться в работе "классических" регулярных выражений. Полезно познакомиться с Perl-compatible regular expressions (pcre), понять принципиальные отличия от "классических": преимущества и недостатки.
В этом контексте любознательные могут познакомиться с теорией (конечных) автоматов и узнать как regexp'ы преобразуются в КА -- недетерминированные и детерминированные. Далее можно узнать что такое регулярные грамматики, контекстно-свободные, контекстно-зависимые и грамматики общего вида. Вопрос "на засыпку" -- можно ли регулярными выражениями разбирать XML? Почему?
Это подводит нас к следующему разделу -- "продвинутому".
Системы формального описания и автоматического построения парсеров грамматик (и лексеров здесь же) -- такие как yacc, bison, ANTLR и т.п. Любознательные могут в дополнение познакомиться с комбинаторами парсеров, но если ничего не поймут - пусть бросают, потом вернутся.
Вообще-то, есть два варианта -- parallel и concurrent -- существенно различающихся между собой, но в русской терминологии толком не обособляющиеся. Первый -- когда большой объём однородных данных обрабатывается поэлементно (более-менее) одинаковым образом независимо друг от друга. Параллельно. Второй -- когда есть много (более-менее) одновременно выполняющихся задач (процессов, потоков, нитей), которые могут выполнять абсолютно разные работы.
И то, и другое слишком сложно чтобы писать самому с нуля. Кроме того -- очень подверженно нетривиальным ошибкам. Лучше всего пользоваться готовыми библиотеками, которые делают то что нужно заведомо правильным образом. Категорически НЕ рекомендуется пользоваться такими механизмами синхронизации как мьютексы, семафоры и прочие критические секции. Лучше всего пользоваться библиотечными "параллельными" или "синхронными" коллекциями, преимущественно -- очередями.
Необходимо понимать абстракцию сокета, виды сокетов, режимы работы.
- TCP, UDP -- запоминать структуру пакетов необязательно, достаточно понимать что там есть и какие свойства протокола обеспечивает
- HTTP -- повсеместен. Следует знать форматы запросов и ответов, основные заголовки. Хотошо бы знать сопутствующие стандарты: HTML, XML, JSON, MIME и т.д.
Нет никакого "объектно-ориентированного программирования" -- есть "объектно-ориентированное проектирование". ООП -- это способ структурирования программы в целом. "Мясом" программы остаются структуры данных и алгоритмы, но ООП позволяет аккуратно их "упаковать", чтобы "кишки" не торчали наружу и было удобно пользоваться. Это называется "инкапсуляция". Наследование -- штука непростая и противоречивая. Прежде всего, нужно понять разницу между "наследованием интерфейса" и "наследованием реализации". Второго лучше избегать, хотя в примерах такое может быть сплошь и рядом. Примеры намеренно упрощают архитектуру и потому учат неправильным "шаблонам". Нужно внимательно читать и разбираться в "шаблонах проектирования" (design patterns) -- хорошо бы почитать оригинальную книжку "банды четырёх" (gang of four, GoF), но можно читать переложения на другие языки и более современные варианты.
Упражнения в освоении программирования -- важнее всего остального. Программирование -- это не про то, что ты знаешь, а про то, что ты можешь сесть и написать руками.
Написать программу перевода чисел из десятичной арабской записи в римскую и обратно.
Написать программу преобразования текста в код Морзе и обратно.
Классический пример. Читаем выражения одно за другим, производим вычисления и выводим результаты. Можно делать с разным уровнем сложности: выражения записываются в обратной польской нотации (RPN) или в обычной инфиксной, без переменных или с переменными, можно добавить встроенные функции и т.д.
Культовый алгоритм не только для компьютерщиков, но и для математиков -- почитать можно на Википедии, но лучше в книжке Мартина Гарднера. Графический вывод можно и не делать -- текстового достаточно. Для упражнения важно реализовать сам алгоритм.
Широкоизвестная в узких кругах задача. Необходимо считать файл какого-то табличного формата (CSV, например), в котором в ячейках могут быть числа, строки и выражения, оперирующие числами, строками и содержимым других ячеек, и вывести (в файл или stdout) аналогичное табличное представление, но вычислив все ячейки.
В задаче есть несколько "подводных камней", обсуждение можно найти в Рунете.
Реализовать программу, автоматически подбирающую решение для заданного Судоку. Можно решить несколькими способами. Можно считывать спецификацию Судоку в более простых или более сложных форматах, или поддерживать несколько форматов сразу.