Структура данных и алгоритмы которые надо знать программисту
10.01.2018
Собственно на сабж я наткнулся в телеграмме и, дабы его не потерять, публикую тут. Начнем со структур данных. Простейшие варианты вы скорее всего уже прошли, даже если только начали изучать какой-либо язык программирования.
Линейные структуры данных:
- Массивы
- Связный список
- Стек
- Очереди
Нелинейные структуры данных:
- Деревья – бинарное дерево, дерево общего вида, наименьший общий предок
- Бинарное дерево поиска – симметричный обход, обход по уровням, нахождение k’ого наибольшего элемента, диаметр, глубина, количество узлов и т.д.
- Динамическая память – динамический массив, двоичная куча, пирамидальная сортировка
- Алгоритм объединения-поиска
- Хеш таблица – метод нахождения коллизий (Linear Probing), открытая адресация, предотвращение коллизий
Базовые алгоритмы:
- Сортировка — сортировка слиянием, сортировка вставками, быстрая сортировка, несколько взаимных перестановок
- Умножение матриц (хотя бы знать алгоритм)
- Основные алгоритмы просеивания
- Беззнаковая математика, включая умножение и деление
- Алгоритм Евклида для нахождения НОД (наибольший общий делитель), модульная инверсия, быстрое возведение в степень
- Числа Фибоначчи с матричным умножением
- Нормальное распределение и математическое ожидание
- Статистика – среднее вероятностное значение случайной величины, медиана, дисперсия, теорема Байеса
Популярные алгоритмические методы:
- Алгоритмы декомпозиции – бинарный поиск, нахождение подмассива с наибольшей суммой элементов
- Жадные алгоритмы – выбор задач, кодирование по алгоритму Хаффмана
- Динамичное программирование – цепное матричное умножение, алгоритм решения задачи по укладке ранца
- Линейное программирование – максимизация параметра, линейное время сортировки
- Криптографические алгоритмы – алгоритм Манакера по нахождению длиннейшей подстроки-палиндрома, алгоритм нахождения наибольшей общей подпоследовательности (LSC), расстояние Левенштейна
Графы:
- Список смежных вершин графа, матрица смежности графа, взвешенные рёбра графа
- Основные алгоритмы обхода – поиск в ширину, поиск в глубину и т.д.
- Алгоритмы нахождения кратчайшего пути — алгоритм Дейкстры, алгоритм Флойда-Уоршелла, алгоритм Беллмана-Форда
- Минимальное остовное дерево — алгоритм Крускала, алгоритм Прима
Усложнённые деревья и графы:
- Сбалансированные деревья – AVL-дерево, красно-черное дерево
- Heavy-light декомпозиция, Б-деревья, дерево квадрантов
- Усложнённый граф – минимальный разрез, максимальный поток
- Максимальное покрытие – теорема о свадьбах
- Гамильтонов цикл
- Рёберный граф/ Линейный граф
- Сильно связные компоненты
- Главный подграф, покрытие вершин, задача коммивояжёра – алгоритм аппроксимации
Продвинутые криптографические алгоритмы:
- Алгоритм Кнута-Морриса-Пратта
- Алгоритм Рабина-Карпа
- Префиксные и суффиксные деревья
- Автоматизация суффиксов – алгоритм Укконена
Высшая математика:
- Быстрое преобразование Фурье
- Проверка простоты
- Вычислительная геометрия – задача поиска ближайшей пары, диаграмма Вороного, выпуклая оболочка множества точек
Общие продвинутые темы:
- Выполнение обхода всех комбинаций/перестановок
- Поразрядная обработка
Для изучающих язык Java могу посоветовать книгу «Структуры данных и алгоритмы Java» Роберт Лафоре. По содержанию она покрывает почти все вышеперечисленные темы. Книгу легко можно найти на русском языке.
Один комментарий
User
Спасибо за полезную информацию. В данный момент занимаюсь изучением и программной реализацией алгоритмов работы с графами (теоретический материал беру с сайта https://www.mathros.net.ua). Довольно интересно.