Структура данных и алгоритмы которые надо знать программисту

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

Линейные структуры данных:

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

Нелинейные структуры данных:

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

Базовые алгоритмы:

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

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

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

Графы:

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

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

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

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

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

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

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

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

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

Для изучающих язык Java могу посоветовать книгу «Структуры данных и алгоритмы Java» Роберт Лафоре. По содержанию она покрывает почти все вышеперечисленные темы. Книгу легко можно найти на русском языке.

 

Один комментарий

  • User

    Спасибо за полезную информацию. В данный момент занимаюсь изучением и программной реализацией алгоритмов работы с графами (теоретический материал беру с сайта https://www.mathros.net.ua). Довольно интересно.

Оставить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *