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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Другие статьи по теме

Объясняем известные алгоритмы сортировки на пальцах

Собеседование на должность программиста: вопросы по алгоритмам

МЕРОПРИЯТИЯ

Комментарии

ВАКАНСИИ

Добавить вакансию
Web-разработчик
от 150000 RUB до 200000 RUB
Senior Product Manager
Москва, по итогам собеседования
Admitad
Москва, от 250000 RUB до 310000 RUB
QA Engineer
от 120000 RUB

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ