Алгоритмы обзорная статья
Внешний вид
Алгоритмы
Ниже представлен обзор и тематический путеводитель по алгоритмам.
- Алгоритм** — это конечная, четко определенная последовательность инструкций или правил для решения задачи или выполнения вычислений. Алгоритмы являются центральным понятием в информатике, математике, исследовании операций, искусственном интеллекте, криптографии, сжатии данных, компьютерной графике, биоинформатике и многих других областях. Изучение алгоритмов включает их разработку, доказательство корректности, алгоритмическую эффективность, вычислительную сложность и реализацию в компьютерных программах.
Природа алгоритмов[править | править код]
- Алгоритм — конечная последовательность инструкций для решения задачи или выполнения вычислений
- Компьютерная программа — реализация алгоритмов и инструкций по обработке данных на языке программирования
- Структура данных — организация данных, используемых алгоритмами
- Эвристика — практический метод решения задач, который может не гарантировать оптимального решения
- Псевдокод — неформальная запись для описания алгоритмов
- Спецификация (технический стандарт) — формальное или неформальное описание того, что алгоритм должен делать
- Состояние (информатика) — сохраненная информация, используемая во время вычислений
- Анализ завершения — изучение того, останавливается ли алгоритм в конечном итоге
- Машина Тьюринга — математическая модель вычислений, используемая в теории вычислимости
История алгоритмов[править | править код]
- Алгоритм Евклида — древний алгоритм для вычисления наибольшего общего делителя
- Мухаммад ибн Муса аль-Хорезми — математик, чье латинизированное имя связано со словом «алгоритм»
- Алгоритмическая логика — логическое изучение программ и алгоритмов
- Теория вычислимости — изучение того, что может быть вычислено
- Тезис Чёрча — Тьюринга — тезис о природе эффективных вычислений
- Машина Тьюринга — модель, формализующая вычисления
- Лямбда-исчисление — формальная система, используемая в изучении вычислений
- Архитектура фон Неймана — компьютерная архитектура, влияющая на практическую реализацию алгоритмов
Анализ алгоритмов[править | править код]
- Анализ алгоритмов — изучение корректности и эффективности алгоритмов
- Асимптотический анализ — анализ поведения алгоритма при увеличении размера входных данных
- O-большое — обозначение верхней границы скорости роста
- Омега-большое — обозначение нижней границы скорости роста
- Тета-большое — обозначение точной границы скорости роста
- Временная сложность — количество времени, используемое алгоритмом при изменении размера входных данных
- Пространственная сложность — объем памяти, используемый алгоритмом при изменении размера входных данных
- Лучший, худший и средний случаи — распространенные формы анализа производительности алгоритмов
- Амортизационный анализ — анализ средней стоимости за последовательность операций
- Конкурентный анализ (онлайн-алгоритм) — анализ онлайн-алгоритмов по сравнению с оптимальными офлайн-алгоритмами
- Корректность (информатика) — свойство алгоритма удовлетворять своей спецификации
- Инвариант цикла — условие, используемое для доказательства корректности итеративных алгоритмов
- Рекуррентное соотношение — уравнение, часто используемое для анализа рекурсивных алгоритмов
- Основная теорема (анализ алгоритмов) — теорема для решения многих рекуррентных соотношений типа «разделяй и властвуй»
Парадигмы разработки алгоритмов[править | править код]
- Полный перебор — метод исчерпывающей проверки решений-кандидатов
- Алгоритм «разделяй и властвуй» — метод, разделяющий задачу на более мелкие подзадачи
- Уменьшение и завоевание — метод, сводящий задачу к меньшему экземпляру
- Динамическое программирование — метод решения задач с перекрывающимися подзадачами и оптимальной подструктурой
- Жадный алгоритм — алгоритм, делающий локально оптимальный выбор
- Возврат — метод поиска, отбрасывающий частичные решения, которые не могут привести к правильным решениям
- Ветви и границы — метод поиска с использованием границ для исключения решений-кандидатов
- Рандомизированный алгоритм — алгоритм, использующий случайность как часть своей логики
- Аппроксимационный алгоритм — алгоритм, находящий почти оптимальные решения для сложных задач оптимизации
- Онлайн-алгоритм — алгоритм, получающий входные данные постепенно
- Параллельный алгоритм — алгоритм, предназначенный для параллельных вычислений
- Распределенный алгоритм — алгоритм, предназначенный для распределенных систем
- Потоковый алгоритм — алгоритм для обработки потоков данных с ограниченной памятью
- Квантовый алгоритм — алгоритм, предназначенный для квантовых компьютеров
Структуры данных и связанные алгоритмы[править | править код]
Массивы, списки и последовательности[править | править код]
- Массив (структура данных)
- Связный список
- Динамический массив
- Стек (абстрактный тип данных)
- Очередь (абстрактный тип данных)
- Дек
- Очередь с приоритетом
- Кольцевой буфер
Деревья[править | править код]
- Дерево (структура данных)
- Бинарное дерево
- Бинарное дерево поиска
- АВЛ-дерево
- Красно-черное дерево
- B-дерево
- B+ дерево
- Префиксное дерево
- Дерево отрезков
- Дерево Фенвика
- Куча (структура данных)
Хеширование и множества[править | править код]
- Хеш-таблица
- Хеш-функция
- Фильтр Блума
- Структура данных для непересекающихся множеств
- Алгоритм объединения-поиска
- Чувствительное к локальности хеширование
Графовые структуры данных[править | править код]
- Граф (абстрактный тип данных)
- Список смежности
- Матрица смежности
- Матрица инцидентности
Алгоритмы поиска[править | править код]
- Линейный поиск
- Бинарный поиск
- Интерполяционный поиск
- Экспоненциальный поиск
- Поиск прыжками
- Поиск в глубину
- Поиск в ширину
- Поиск по первому наилучшему совпадению
- Лучевой поиск
- Алгоритм A*
- Алгоритм Дейкстры
- Итеративное углубление в глубину
- Поиск по дереву Монте-Карло
Сортировка и порядковые статистики[править | править код]
Сравнительная сортировка[править | править код]
- Пузырьковая сортировка
- Сортировка вставками
- Сортировка выбором
- Сортировка слиянием
- Быстрая сортировка
- Пирамидальная сортировка
- Timsort
- Introsort
- Сортировка Шелла
- Сортировка деревом
Несравнительная сортировка[править | править код]
- Сортировка подсчетом
- Поразрядная сортировка
- Карманная сортировка
- Сортировка по ячейкам
Порядковые статистики[править | править код]
- Алгоритм выбора
- Quickselect
- Медиана медиан
- Дерево порядковых статистик
Графовые алгоритмы[править | править код]
Обход графа[править | править код]
- Поиск в глубину
- Поиск в ширину
- Топологическая сортировка
- Заливка
Кратчайшие пути[править | править код]
- Алгоритм Дейкстры
- Алгоритм Беллмана — Форда
- Алгоритм Флойда — Уоршелла
- Алгоритм Джонсона
- Алгоритм A*
Остовные деревья и связность[править | править код]
- Минимальное остовное дерево
- Алгоритм Краскала
- Алгоритм Прима
- Алгоритм Борувки
- Компонента связности (теория графов)
- Сильно связная компонента
- Алгоритм Тарьяна для поиска сильно связных компонент
Потоки в сетях и паросочетания[править | править код]
- Задача о максимальном потоке
- Алгоритм Форда — Фалкерсона
- Алгоритм Эдмондса — Карпа
- Алгоритм проталкивания предпотока
- Задача о потоке минимальной стоимости
- Паросочетание в двудольном графе
- Алгоритм Хопкрофта — Карпа
- Алгоритм цветка
Раскраска графов и сложные графовые задачи[править | править код]
- Раскраска графов
- Задача о клике
- Независимое множество (теория графов)
- Задача о гамильтоновом пути
- Задача коммивояжёра
Строковые алгоритмы[править | править код]
- Алгоритм поиска подстроки
- Алгоритм Кнута — Морриса — Пратта
- Алгоритм Бойера — Мура
- Алгоритм Рабина — Карпа
- Алгоритм Ахо — Корасик
- Расстояние Левенштейна
- Расстояние редактирования
- Наибольшая общая подпоследовательность
- Наибольшая общая подстрока
- Суффиксное дерево
- Суффиксный массив
- Преобразование Барроуза — Уилера
- Регулярное выражение
- Синтаксический анализ
- Алгоритм Эрли
- Алгоритм Кока — Янгера — Касами
Численные и математические алгоритмы[править | править код]
Арифметика и теория чисел[править | править код]
- Алгоритм Евклида
- Расширенный алгоритм Евклида
- Решето Эратосфена
- Факторизация целых чисел
- Тест простоты
- Тест Агравала — Каяла — Саксены
- Модульное возведение в степень
- Быстрое преобразование Фурье
- Алгоритм Карацубы
- Алгоритм Шёнхаге — Штрассена
Линейная алгебра[править | править код]
- Метод Гаусса
- LU-разложение
- QR-разложение
- Сингулярное разложение
- Алгоритм поиска собственных значений
- Алгоритм Штрассена
- Умножение цепочки матриц
Численная оптимизация и аппроксимация[править | править код]
- Метод Ньютона
- Градиентный спуск
- Метод сопряженных градиентов
- Имитация отжига
- Алгоритм максимизации ожидания
- Численное интегрирование
- Метод Монте-Карло
Алгоритмы оптимизации[править | править код]
- Линейное программирование
- Симплекс-метод
- Метод внутренней точки
- Целочисленное программирование
- Динамическое программирование
- Градиентный спуск
- Стохастический градиентный спуск
- Метод Ньютона
- Квазиньютоновский метод
- Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно
- Множитель Лагранжа
- Задача удовлетворения ограничений
- Локальный поиск (оптимизация)
- Восхождение на холм
- Поиск с запретами
- Генетический алгоритм
- Муравьиный алгоритм
- Роевой интеллект
- Эволюционный алгоритм
Алгоритмы искусственного интеллекта и машинного обучения[править | править код]
Поиск и планирование[править | править код]
- Алгоритм A*
- Минимакс
- Альфа-бета отсечение
- Graphplan
- Поиск по дереву Монте-Карло
- Автоматическое планирование и составление расписаний
- Задача удовлетворения ограничений
Обучение с учителем[править | править код]
- Линейная регрессия
- Логистическая регрессия
- Дерево решений
- Случайный лес
- Метод опорных векторов
- Метод k-ближайших соседей
- Наивный байесовский классификатор
- Градиентный бустинг
- Искусственная нейронная сеть
- Обратное распространение ошибки
Обучение без учителя[править | править код]
- Кластерный анализ
- Метод k-средних
- Иерархическая кластеризация
- Метод главных компонент
- Анализ независимых компонент
- Автоэнкодер
- Самоорганизующаяся карта
Обучение с подкреплением[править | править код]
- Обучение с подкреплением
- Q-обучение
- SARSA
- Временное различие
- Метод градиента политики
- Модель актор-критик
- Глубокое обучение с подкреплением
Алгоритмическая игра[править | править код]
- AlphaGo
- AlphaGo Zero
- AlphaZero
- MuZero
- TD-Gammon
- Chinook (шашечная программа)
- Deep Blue (шахматный компьютер)
Открытие алгоритмов с помощью ИИ[править | править код]
- AlphaDev
- AlphaEvolve
- AlphaTensor
- Поиск нейронной архитектуры
- Автоматическое машинное обучение
- Синтез программ
Криптографические алгоритмы[править | править код]
Симметричные алгоритмы[править | править код]
- Advanced Encryption Standard
- Data Encryption Standard
- Triple DES
- Blowfish (шифр)
- Twofish
- ChaCha20-Poly1305
Алгоритмы с открытым ключом[править | править код]
- RSA
- Диффи — Хеллман
- Эллиптическая криптография
- Digital Signature Algorithm
- EdDSA
Хеширование и аутентификация[править | править код]
- Криптографическая хеш-функция
- MD5
- SHA-1
- SHA-2
- SHA-3
- Код аутентификации сообщения на основе хеша
- Функция формирования ключа на основе пароля
- Bcrypt
- Argon2
Алгоритмы сжатия[править | править код]
Сжатие без потерь[править | править код]
- Кодирование Хаффмана
- Арифметическое кодирование
- Кодирование длин серий
- Lempel — Ziv — Welch
- LZ77 и LZ78
- DEFLATE
- Преобразование Барроуза — Уилера
Сжатие с потерями[править | править код]
- Преобразующее кодирование
- Дискретное косинусное преобразование
- Модифицированное дискретное косинусное преобразование
- Векторное квантование
- Квантование (обработка сигналов)
- Компенсация движения
Алгоритмы вычислительной геометрии[править | править код]
- Алгоритмы построения выпуклой оболочки
- Сканирование Грэхема
- Алгоритм заворачивания подарка
- Триангуляция Делоне
- Диаграмма Вороного
- Пересечение отрезков
- Локализация точки
- Задача о ближайшей паре точек
- Вращающиеся штангенциркули
- Алгоритм заметающей прямой
Алгоритмы компьютерной графики и обработки изображений[править | править код]
- Алгоритм Брезенхема
- Заливка
- Растеризация
- Z-буферизация
- Трассировка лучей (графика)
- Трассировка пути
- Затенение по Фонгу
- Текстурное отображение
- Marching cubes
- Детектор границ Кэнни
- Масштабно-инвариантное преобразование признаков
- Преобразование Хафа
- Seam carving
Алгоритмы баз данных и информационного поиска[править | править код]
- B-дерево
- B+ дерево
- Хеш-соединение
- Соединение сортировкой слиянием
- Оптимизация запросов
- PageRank
- Инвертированный индекс
- Tf-idf
- Okapi BM25
- Чувствительное к локальности хеширование
- MapReduce
- Согласованное хеширование
Распределенные, конкурентные и сетевые алгоритмы[править | править код]
Распределенные системы[править | править код]
- Консенсус (информатика)
- Paxos (информатика)
- Raft (алгоритм)
- Византийская отказоустойчивость
- Векторные часы
- Метка времени Лампорта
- Выбор лидера
- Протокол сплетен
Конкурентность[править | править код]
- Вза
Ссылки[править | править код]
- https://www.britannica.com/science/algorithm
- https://www.tableau.com/data-insights/ai/algorithms
- https://www.britannica.com/science/computer-science/Algorithms-and-complexity
- https://www.britannica.com/technology/analysis-of-algorithms
- https://www.geeksforgeeks.org/dsa/introduction-to-algorithms/
- https://www.geeksforgeeks.org/dsa/algorithms-design-techniques/
- https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/