Список тем о вычислимости и сложности - List of computability and complexity topics
Это список тем о вычислимости и сложности по страницам Википедии.
Теория вычислимости - это часть теории вычислений, которая имеет дело с тем, что в принципе можно вычислить. Теория вычислительной сложности имеет дело с количественными показателями сложности вычислений как с верхними границами ( алгоритмы , сложность которых в наихудших случаях, например, использование вычислительных ресурсов, может быть оценена), так и снизу (доказательства того, что нет процедуры для выполнения некоторых задача может быть очень быстрой).
Для более абстрактных фундаментальных вопросов см. Список тем математической логики . См. Также список алгоритмов , список общих тем алгоритмов .
Расчет
- Справочная таблица
- История компьютеров
- Алгоритм умножения
- Деление на два
- Возведение в степень возведением в квадрат
- Цепочка добавления
- Арифметика пресбургера
Теория вычислимости: модели вычислений
- Арифметические схемы
- Алгоритм
-
Конечный автомат
- Мучная машина
- Регистровая машина Минского
- Машина Мура
- Диаграмма состояний
- Система перехода состояний
- Детерминированный конечный автомат
- Недетерминированный конечный автомат
- Обобщенный недетерминированный конечный автомат
- Обычный язык
- Регулярное выражение
- Обычная грамматика
- Грамматика префиксов
- Дерево-автомат
- Выталкивающий автомат
- Büchi автомат
- Иерархия Хомского
- Зарегистрировать машину
- Штабелеукладчик
- Сеть Петри
- Почтовый автомат
- Перезапись
- Высота звезды
- Клеточный автомат
- Машина Тьюринга
- Лямбда-исчисление
- Комбинаторная логика
- Параллельные вычисления
- Таксономия Флинна
- Квантовый компьютер
- Тезис Черча-Тьюринга
Проблемы с решением
- Entscheidungsproblem
- Проблема с остановкой
- Проблема с почтовой перепиской
- Решаемый язык
- Задача со словом для групп
- Плитка Ван
- Плитка Пенроуза
Вопросы определимости
- Вычислимое число
- Определимое число
- Вероятность остановки
- Алгоритмическая теория информации
- Алгоритмическая вероятность
- Сжатие данных
Теория сложности
- Совет (сложность)
- Амортизированный анализ
- Протокол Артура-Мерлина
- Лучшие и худшие случаи
- Занятый бобер
- Сложность схемы
- Конструируемая функция
- Теорема Кука
- Экспоненциальное время
- Функциональная проблема
- Линейное время
- Теорема о линейном ускорении
- Естественное доказательство
- Полиномиальное время
- Редукция "много-один" за полиномиальное время
- Редукция Тьюринга за полиномиальное время
- Теорема савича
- Теорема пространственной иерархии
- Скорость приора
- Теорема об ускорении
- Субквадратичное время
- Теорема об иерархии времени
Классы сложности
Посмотреть список классов сложности
Названные проблемы
- Проблема клики
- Проблема гамильтонова цикла
- Гамильтонова проблема пути
- Целочисленная факторизация
- Задача о рюкзаке
- Проблема выполнимости
- Проблема суммы подмножества
- 3SUM
- Проблема коммивояжера
- Проблема покрытия вершины
- Односторонняя функция
- Установить проблему с крышкой
- Независимая задача набора
Расширения
- Вероятностный алгоритм , рандомизированный алгоритм
- Алгоритм Лас-Вегаса
- Недетерминизм
- Недетерминированная машина Тьюринга
- Интерактивные вычисления
- Интерактивная система доказательств
- Вероятностная машина Тьюринга
- Алгоритм приближения
- Имитация отжига
- Алгоритм муравьиной колонии
- Семантика игры
- Обобщенная игра
- Многоагентная система
- Параметризованная сложность
- Расчет процесса
- Гипервычисления
- Реальные вычисления