Какие алгоритмы нужно знать, чтобы стать хорошим программистом?

[HHIDE_DUMP]

Данная статья содержит не только самые распространенные алгоритмы и структуры данных, но и более сложные вещи, о которых вы могли не знать. Читаем и узнаем!


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

Для начала давайте начнем с линейных структур данных и алгоритмов

• Массивы
• Связный список
• Стек
• Очереди

Перейдем к базовым алгоритмам

• Сортировка — Сортировка слиянием, Сортировка вставками, Быстрая сортировка, Несколько взаимных перестановок.
• Умножение матриц (Не обязательно реализовывать, главное — знать алгоритм)
• Основные алгоритмы просеивания
• Беззнаковая математика, включая умножение и деление
• Алгоритм Евклида для нахождения НОД (наибольший общий делитель), Модульная инверсия, Быстрое возведение в степень
• Числа Фибоначчи с матричным умножением
• Нормальное распределение и математическое ожидание
• Статистика – среднее вероятностное значение случайной величины, медиана, дисперсия, теорема Байеса

Также можно изучить популярные алгоритмические методы:

• Алгоритмы декомпозиции – Бинарный поиск, Нахождение подмассива с наибольшей суммой элементов
• Жадные алгоритмы – Выбор задач, кодирование по алгоритму Хаффмана
• Динамичное программирование – Цепное матричное умножение, Алгоритм решения задачи по укладке ранца
• Линейное программирование – Максимизация параметра, Линейное время сортировки
• Криптографические алгоритмы – Алгоритм Манакера по нахождению длиннейшей подстроки-палиндрома, алгоритм нахождения наибольшей общей подпоследовательности (LSC), расстояние Левенштейна

Теперь перейдем к типичным нелинейным структурам данных

• Деревья – Бинарное дерево, Дерево общего вида, Наименьший общий предок
• Бинарное дерево поиска – Симметричный обход, Обход по уровням, Нахождение k’ого наибольшего элемента, Диаметр, Глубина, Количество узлов и т.д.
• Динамическая память – Динамический массив, Двоичная куча, Пирамидальная сортировка
• Алгоритм объединения-поиска
• Хеш-таблица – Метод нахождения коллизий (Linear Probing), Открытая адресация, Предотвращение коллизий

Рассмотрим графы

• Список смежных вершин графа, Матрица смежности графа, Взвешенные рёбра графа
• Основные алгоритмы обхода – Поиск в ширину, Поиск в глубину и т.д.
• Алгоритмы нахождения кратчайшего пути — Алгоритм Дейкстры, Алгоритм Флойда-Уоршелла, Алгоритм Беллмана-Форда
• Минимальное остовное дерево — Алгоритм Крускала, Алгоритм Прима

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

Усложнённые деревья и графы

• Сбалансированные деревья – AVL-дерево, Красно-черное дерево
• Heavy-light декомпозиция, Б-деревья, Дерево квадрантов
• Усложнённый граф – Минимальный разрез, Максимальный поток
• Максимальное покрытие – Теорема о свадьбах
• Гамильтонов цикл
• Рёберный граф/ Линейный граф
• Сильно связные компоненты
• Главный подграф, Покрытие вершин, Задача коммивояжёра – Алгоритм аппроксимации

Продвинутые криптографические алгоритмы:

• Алгоритм Кнута-Морриса-Пратта
• Алгоритм Рабина-Карпа
• Префиксные и суффиксные деревья
• Автоматизация суффиксов – Алгоритм Укконена

Высшая математика

• Быстрое преобразование Фурье
• Проверка простоты
• Вычислительная геометрия – Задача поиска ближайшей пары, Диаграмма Вороного, Выпуклая оболочка множества точек

Общие продвинутые темы:

• Выполнение обхода всех комбинаций/перестановок
• Поразрядная обработка