Краткое описание алгоритмов ⇐ Васина Википедия

[wiki_en]

Следующий план представляет собой обзор и тематическое руководство по «алгоритмам»:

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

== История алгоритмов ==

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

== Анализ алгоритма ==

* Анализ алгоритмов — исследование корректности и эффективности алгоритмов
* Асимптотический анализ — анализ поведения алгоритма при увеличении размера входных данных
* Обозначение Big O — обозначение верхней границы темпов роста
* Обозначение Big Omega — обозначение нижней границы темпов роста
* Обозначение Big Theta — жесткое обозначение темпов роста
* Временная сложность — количество времени, которое алгоритм использует при изменении размера входных данных.
* Пространственная сложность — объем памяти, который алгоритм использует при изменении размера входных данных.
* Лучший, худший и средний случай — распространенные формы анализа производительности алгоритма
* Амортизированный анализ — анализ средней стоимости по последовательности операций
* Конкурентный анализ (онлайн-алгоритм) — анализ онлайн-алгоритмов в сравнении с оптимальными оффлайн-алгоритмами
* Корректность (информатика) — свойство, при котором алгоритм удовлетворяет своей спецификации
* Инвариант цикла — условие, используемое для доказательства корректности итерационных алгоритмов
* Рекуррентное соотношение — уравнение, часто используемое для анализа рекурсивных алгоритмов
* Основная теорема (анализ алгоритмов) — теорема для решения многих повторяющихся задач по принципу «разделяй и властвуй».

== Парадигмы проектирования алгоритмов ==

* Перебор — метод исчерпывающей проверки возможных решений
* Алгоритм «разделяй и властвуй» — метод, который делит проблему на более мелкие подзадачи
* Уменьшай и властвуй — техника, которая сводит проблему к меньшему размеру
* Динамическое программирование — методика решения задач с перекрывающимися подзадачами и оптимальной подструктурой
* Жадный алгоритм — алгоритм, который делает локально оптимальный выбор
* Поиск с возвратом — метод поиска, который отбрасывает частичные решения, которые не могут привести к действительным решениям.
* Ветви и границы — метод поиска с использованием границ для исключения возможных решений
* Рандомизированный алгоритм — алгоритм, использующий случайность как часть своей логики
* Алгоритм аппроксимации — алгоритм, который находит почти оптимальные решения сложных задач оптимизации.
* Онлайн-алгоритм — алгоритм, который получает входные данные постепенно
* Параллельный алгоритм — алгоритм, предназначенный для параллельных вычислений
* Распределенный алгоритм — алгоритм, разработанный для распределенных систем
* Алгоритм потоковой передачи — алгоритм обработки потоков данных с ограниченной памятью
* Квантовый алгоритм — алгоритм, разработанный для квантовых компьютеров
== Структуры данных и связанные с ними алгоритмы ==

=== Массивы, списки, на
* Разложение по сингулярным значениям
* Алгоритм собственных значений
* Алгоритм Штрассена
* Умножение цепочки матриц

=== Численная оптимизация и аппроксимация ===
*Метод Ньютона
* Градиентный спуск
* Метод сопряженных градиентов
* Имитация отжига
* Алгоритм ожидания-максимизации
* Численное интегрирование
* Метод Монте-Карло

== Алгоритмы оптимизации ==

* Линейное программирование
* Симплексный алгоритм
* Метод внутренней точки
* Целочисленное программирование
* Динамическое программирование
* Градиентный спуск
* Стохастический градиентный спуск
*Метод Ньютона
* Квазиньютоновский метод
* Алгоритм Бройдена–Флетчера–Гольдфарба–Шенно
* Множитель Лагранжа
* Проблема удовлетворения ограничений
* Локальный поиск (оптимизация)
* Восхождение на холм
* Поиск табу
* Генетический алгоритм
* Алгоритмы оптимизации колонии муравьев
* Оптимизация роя частиц
* Эволюционный алгоритм

== Алгоритмы искусственного интеллекта и машинного обучения ==

=== Поиск и планирование ===
* Алгоритм поиска A*
* Минимакс
* Альфа-бета-обрезка
* Графплан
* Поиск по дереву Монте-Карло
* Автоматизированное планирование и составление графиков
* Проблема удовлетворения ограничений

=== Обучение под присмотром ===
* Линейная регрессия
* Логистическая регрессия
* Изучение дерева решений
* Случайный лес
* Машина опорных векторов
* алгоритм k-ближайших соседей
* Наивный байесовский классификатор
* Повышение градиента
* Искусственная нейронная сеть
* Обратное распространение ошибки

=== Обучение без присмотра ===
* Кластерный анализ
* K-средства кластеризации
* Иерархическая кластеризация
* Анализ главных компонентов
* Независимый анализ компонентов
* Автоэнкодер
* Самоорганизующаяся карта

=== Обучение с подкреплением ===
* Обучение с подкреплением
* Q-обучение
* Состояние-действие-вознаграждение-состояние-действие (SARSA)
* Обучение временной разнице
* Метод градиента политики
* Модель актер-критик|Алгоритм актер-критик
* Глубокое обучение с подкреплением

=== Алгоритмичный геймплей ===
* АльфаГо
* AlphaGo Ноль
* АльфаЗеро
* МуЗеро
* ТД-Окорок
* Чинук (шашечный игрок)
* Deep Blue (шахматный компьютер)

=== Открытие алгоритма с помощью ИИ ===
* АльфаДев
* АльфаЭволюв
* АльфаТензор
* Поиск нейронной архитектуры
* Автоматизированное машинное обучение
* Синтез программ

== Криптографические алгоритмы ==

=== Алгоритмы с симметричными ключами ===
* Расширенный стандарт шифрования
* Стандарт шифрования данных
* Тройной DES
* Иглобрюхая рыба (шифр)
* Две рыбы
* ЧаЧа20-Поли1305

=== Алгоритмы с открытым ключом ===
* Криптосистема RSA
* Обмен ключами Диффи-Хеллмана
* Криптография на основе эллиптических кривых
* Алгоритм цифровой подписи
* ЭдДСА

=== Хеширование и аутентификация ===
* Криптографическая хэш-функция
* MD5
* SHA-1
* ША-2
* ША-3
* Код аутентификации сообщения на основе хеша
* Функция получения ключа на основе пароля
* Бикрипт
* Аргон2

== Алгоритмы сжатия ==

=== Сжатие без потерь ===
* Кодирование Хаффмана
* Арифметическое кодирование
* Кодирование длин серий
* Лемпель–Зив–Уэлч
* LZ77 и LZ78
* СДУВАТЬ
* Преобразование Берроуза–Уиллера

=== Методы сжатия с потерями ===
* Преобразование кодирования
* Дискретное косинусное преобразование
* Модифицированное дискретное косинусное преобразование
* Векторное квантование
* Квантование (обработка сигналов)|Квантование
* Компенсация движения

== Алгоритмы вычислительной геометрии ==

* Алгоритмы выпуклой оболочки
* Сканирование Грэма
* Алгоритм упаковки подарка
* Триангуляция Делоне
* Диаграмма Вороного
* Пересечение отрезков
* Местоположение точки
* Задача о ближайшей паре точек
* Вращающиеся суппорты
* Алгоритм развертки линии

== Компьютерная графика и алгоритмы обработки изображений ==

* Алгоритм линии Брезенхема
* Заливка
* Рендеринг развертки
* Z-буферизация
* Трассировка лучей (графика)
* Отслеживание пути
* Затенение Фонга
* Наложение текстур
* Марширующие кубики
* Детектор границ Канни
* Преобразование масштабно-инвариантного объекта
* Преобразование Хафа
* Резьба по шву

== База данных и алгоритмы поиска информации ==

* B-дерево
* Дерево B+
* Хэш-соединение
* Соединение сортировки-слияния
* Оптимизация запросов
* Рейтинг страницы
* Инвертированный индекс
* Tf–idf
* Окапи BM25|BM25
* Хеширование с учетом местоположения
* MapReduce
* Согласованное хеширование

== Распределенный, параллельные и сетевые алгоритмы ==

=== Распределенные системы ===
* Консенсус (информатика)
* Паксос (информатика)
* Плот (алгоритм)
* Византийская отказоустойчивость
* Векторные часы
* Временная метка Лампорта
* Выборы лидера
* Протокол сплетен

=== Параллелизм ===
* Взаимное исключение
* Семафор (программирование)
* Монитор (синхронизация)
* Алгоритмы предотвращения тупиков
* Алгоритмы без блокировки и ожидания
* Сравнение и обмен

=== Сеть ===
* Алгоритм маршрутизации
* Алгоритм Дейкстры
* Алгоритм Беллмана-Форда
* Протокол дистанционно-векторной маршрутизации
* Протокол маршрутизации по состоянию канала
* Контроль перегрузок
* Протокол управления передачей

== Биоинформатика и научные алгоритмы ==

* Алгоритм Нидлмана-Вунша
* Алгоритм Смита–Уотермана
* ВЗРЫВ (биотехнология)
* Выравнивание последовательности
* Скрытая марковская модель
* Алгоритм Витерби
* Филогенетическое древо
* Молекулярная динамика
* Метод конечных элементов
* Быстрый многополюсный метод

== Классы сложности и алгоритмические ограничения ==

* P (сложность)
* НП (сложность)
* NP-полнота
* NP-твердость
* ВРЕМЯ ЭКСПЛУАТАЦИИ
* PSPACE
* БПП (сложность)
* БКП
* Неразрешимая проблема
* Проблема с остановкой
* Теорема Райса
* Теорема о бесплатном обеде

== Списки алгоритмов ==
* Список алгоритмов
* Список алгоритмов искусственного интеллекта
* Список комбинаторных алгоритмов

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

=== Разработка и анализ алгоритма ===
* Дональд Кнут — анализ алгоритмов и «Искусство компьютерного программирования»
* Эдсгер В. Дейкстра — Алгоритм Дейкстры и структурное программирование
* Роберт В. Флойд — Алгоритм Флойда–Уоршалла и его анализ
* Тони Хоар — Быстрая сортировка и логика Хоара
* Майкл О. Рабин — рандомизированные алгоритмы и теория автоматов
* Ричард М. Карп — NP-полнота и комбинаторная оптимизация

=== Теория сложности ===
* Стивен Кук — Теорема Кука–Левина и NP-полнота
* Леонид Левин — NP-полнота и теория сложности вычислений
* Юрис Хартманис — теория сложности вычислений
* Ричард Э. Стернс — теория сложности вычислений
* Ави Вигдерсон — случайность и вычислительная сложность

=== График, сеть и алгоритмы оптимизации ===
* Ричард Беллман — динамическое программирование и алгоритмы поиска кратчайшего пути
* Джордж Данциг — симплекс-алгоритм и линейное программирование
* Джек Эдмондс — паросочетание (теория графов)|сопоставление и многогранная комбинаторика
* Л. Р. Форд-младший — Алгоритм Форда – Фулкерсона и задачи максимального потока
* Д. Р. Фулкерсон — Алгоритм Форда – Фулкерсона и сетевые потоки
* Роберт Тарьян — графовые алгоритмы и структуры данных

=== Криптография и рандомизированные алгоритмы ===
* Уитфилд Диффи — обмен ключами Диффи-Хеллмана
* Мартин Хеллман — обмен ключами Диффи-Хеллмана
* Рон Ривест — RSA (криптосистема)|RSA и криптографические алгоритмы
* Ади Шамир — RSA и криптографические алгоритмы
* Леонард Адлеман — RSA и ДНК-вычисления
* Шафи Гольдвассер — криптография и сложность вычислений

=== Искусственный интеллект и алгоритмы поиска ===
* Джон Маккарти (ученый-компьютерщик)|Джон Маккарти — искусственный интеллект и символический искусственный интеллект
* Марвин Мински — искусственный интеллект и вычислительные модели
* Герберт А. Саймон — эвристический поиск и искусственный интеллект
* Аллен Ньюэлл — эвристический поиск и искусственный интеллект
* Артур Сэмюэл (ученый-компьютерщик) | Артур Сэмюэл — ранние алгоритмы машинного обучения и игровых игр
* Джудея Перл — Байесовские сети и вероятностные рассуждения

== См. также ==
* Разработка алгоритмов
* Краткое описание искусственного интеллекта
* Очерк информатики
* Процедура (информатика)
* Список структур данных
* Список тем численного анализа
* Список программного обеспечения для оптимизации

== Дальнейшее чтение ==
* * * *
* * *

Алгоритмы
Очерки вычислительной техники и инженерии
Краткое содержание Википедии

Подробнее: https://en.wikipedia.org/wiki/Outline_of_algorithms