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

0
57611

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылка на оригинальную статью
Перевод: Александр Давыдов