Перейти к содержанию

Алгоритмы обзорная статья

Статья из Авикипедии. Энциклопедии

Алгоритмы

Ниже представлен обзор и тематический путеводитель по алгоритмам.

    • Алгоритм** — это конечная, четко определенная последовательность инструкций или правил для решения задачи или выполнения вычислений. Алгоритмы являются центральным понятием в информатике, математике, исследовании операций, искусственном интеллекте, криптографии, сжатии данных, компьютерной графике, биоинформатике и многих других областях. Изучение алгоритмов включает их разработку, доказательство корректности, алгоритмическую эффективность, вычислительную сложность и реализацию в компьютерных программах.

Природа алгоритмов[править | править код]

  • Алгоритм — конечная последовательность инструкций для решения задачи или выполнения вычислений
  • Компьютерная программа — реализация алгоритмов и инструкций по обработке данных на языке программирования
  • Структура данных — организация данных, используемых алгоритмами
  • Эвристика — практический метод решения задач, который может не гарантировать оптимального решения
  • Псевдокод — неформальная запись для описания алгоритмов
  • Спецификация (технический стандарт) — формальное или неформальное описание того, что алгоритм должен делать
  • Состояние (информатика) — сохраненная информация, используемая во время вычислений
  • Анализ завершения — изучение того, останавливается ли алгоритм в конечном итоге
  • Машина Тьюринга — математическая модель вычислений, используемая в теории вычислимости

История алгоритмов[править | править код]

  • Алгоритм Евклида — древний алгоритм для вычисления наибольшего общего делителя
  • Мухаммад ибн Муса аль-Хорезми — математик, чье латинизированное имя связано со словом «алгоритм»
  • Алгоритмическая логика — логическое изучение программ и алгоритмов
  • Теория вычислимости — изучение того, что может быть вычислено
  • Тезис Чёрча — Тьюринга — тезис о природе эффективных вычислений
  • Машина Тьюринга — модель, формализующая вычисления
  • Лямбда-исчисление — формальная система, используемая в изучении вычислений
  • Архитектура фон Неймана — компьютерная архитектура, влияющая на практическую реализацию алгоритмов

Анализ алгоритмов[править | править код]

  • Анализ алгоритмов — изучение корректности и эффективности алгоритмов
  • Асимптотический анализ — анализ поведения алгоритма при увеличении размера входных данных
  • 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 (алгоритм)
  • Византийская отказоустойчивость
  • Векторные часы
  • Метка времени Лампорта
  • Выбор лидера
  • Протокол сплетен

Конкурентность[править | править код]

  • Вза

Ссылки[править | править код]