Понятия со словом «сложности»
В скалолазании, альпинизме и других восходящих дисциплинах альпинисты дают оценку маршруту восхождения, в котором кратко описывается сложность и опасность восхождения по маршруту. Каждое восхождение имеют свою специфику, и разные страны разработали свои собственные системы классификации.
Подробнее: Категория сложности (скалолазание)
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется...
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов.
Подробнее: Класс сложности
Список стран по экономической сложности использует макроэкономический показатель «индекс экономической сложности», разработанный Рикардо Хаусманном и Цезарем Идальго и характеризующий сложность и диверсифицированность экспортируемых товаров страны.
Алгебраическая сложность — раздел теории сложности вычислений, имеющий дело с полиномами. Был создан в основном благодаря работам Ф. Штрассена.
В теории вычислительной сложности сложность алгоритма в среднем — это количество неких вычислительных ресурсов (обычно — время), требуемое для работы алгоритма, усреднённое по всем возможным входным данным. Понятие часто противопоставляется сложности в худшем случае, где рассматривается максимальная сложность алгоритма по всем входным данным.
Сло́жность (или сила, стойкость) паро́ля — мера оценки времени, которое необходимо затратить на угадывание пароля или его подбор каким-либо методом, например, методом полного перебора. Оценка того, как много попыток (времени) в среднем потребуется взломщику для угадывания пароля. Другое определение термина — функция от длины пароля, его запутанности и непредсказуемости.
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные . Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, т.е. при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения...
Подробнее: Временная сложность алгоритма
Новая сложность (New Complexity) — условно выделяемое направление в европейской (позже — американской) академической музыке с середины 1970-х годов, культивирующее сложность в аспектах техники композиции, особенностей исполнительской техники и нотации, и как следствие этого — в аспекте восприятия данной музыки. Лидером и основоположником направления считается английский композитор Брайан Фернихоу, а ведущими представителями направления — английская «школа» композиторов «новой сложности». Автор термина...
Нечлени́мая сло́жность (англ. Irreducible complexity, IC) — аргумент сторонников «разумного замысла», заключающийся в том, что некоторые биологические системы слишком сложны, чтобы эволюционировать от более простых, «функционально менее полных» предшественников посредством естественного отбора — непрерывной последовательности возникающих случайным образом полезных мутаций. Это центральный аргумент концепции разумного замысла. Научное сообщество отвергает его как несостоятельный, считая концепцию...
Цикломати́ческая сло́жность програ́ммы (англ. cyclomatic complexity of a program) — структурная (или топологическая) мера сложности компьютерной программы. Мера была разработана Томасом Дж. Маккейбом в 1976 году.
Связанные понятия
Комбинаторный взрыв — термин, используемый для описания эффекта резкого («взрывного») роста временной сложности алгоритма при увеличении размера входных данных задачи.
Иные значения см. разделе в Компьютерное моделирование.Теория вычислимости и теория сложности вычислений трактует модель вычисления (англ. model of computation) не только как определение множества допустимых операций, использованных для вычисления, но также и относительных издержек их применения. Охарактеризовать необходимые вычислительные ресурсы — время выполнения, объём памяти, а также ограничения алгоритмов или компьютера — можно только в том случае, если выбрана определённая модель вычислений...
Подробнее: Модель вычислений
В информатике алгоритм выбора — это алгоритм для нахождения k-го по величине элемента в массиве (такой элемент называется k-й порядковой статистикой). Частными случаями этого алгоритма являются нахождение минимального элемента, максимального элемента и медианы. Существует алгоритм, который гарантированно решает задачу выбора k-го по величине элемента за O(n).
Задача развязывания — задача алгоритмического распознавания тривиального узла если задано некоторое представление узла, то есть диаграмма узла. Существует несколько видов алгоритмов развязывания. Основная нерешённая проблема — можно ли решить задачу за полиномиальное время, то есть, принадлежит ли задача классу сложности P.
В прикладной математике под задачей о назначении минимального количества исполнителей понимается задача комбинаторной оптимизации, обобщающая задачу о покрытии множества и схожая по постановке с задачей о назначениях.
Подробнее: Задача о назначении минимального количества исполнителей
Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) — задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике.
Подробнее: Наибольшая общая подпоследовательность
Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путём полного перебора всех возможных потенциальных делителей.
Алгоритмы локального поиска — группа алгоритмов, в которых поиск ведется только на основании текущего состояния, а ранее пройденные состояния не учитываются и не запоминаются. Основной целью поиска является не нахождение оптимального пути к целевой точке, а оптимизация некоторой целевой функции, поэтому задачи, решаемые подобными алгоритмами, называют задачами оптимизации. Для описания пространства состояний в таких задачах используют ландшафт пространства состояний, в этом представлении задача сводится...
Подробнее: Локальный поиск (оптимизация)
В исследовании операций под аппроксимационным алгоритмом понимается алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.
Подробнее: Аппроксимационный алгоритм
В прикладной математике,
тестовые функции, известные как искусственные ландшафты, являются полезными для оценки характеристик алгоритмов оптимизации, таких как...
Алгоритм Верхуффа (англ. Verhoeff algorithm) — алгоритм расчёта контрольной цифры для обнаружения ошибок при ручном вводе длинных цифровых последовательностей. Впервые опубликован в 1969 году нидерландским математиком Якобом Верхуффом. Алгоритм позволяет выявить такое же число ошибок, как аналогичный алгоритм Луна, но ошибки, выявляемые только первым, совершаются людьми обычно чаще, чем ошибки, выявляемые только вторым.
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Алгоритм ближайшего соседа — один из простейших эвристических методов решения задачи коммивояжёра. Относится к категории «жадных» алгоритмов.
Алгоритм исчисления порядка (index-calculus algorithm) — вероятностный алгоритм вычисления дискретного логарифма в кольце вычетов по модулю простого числа. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер. Примером такого алгоритма является ГОСТ Р 34.10-2012.
Тео́рия алгори́тмов — наука, находящаяся на стыке математики и информатики, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов...
Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.
Задача о рюкзаке (или задача о ранце) — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике.
Трансвычисли́тельная зада́ча (англ. Transcomputational problem) — в теории сложности вычислений задача, для решения которой требуется обработка более чем 1093 бит информации. Число 1093, называемое «пределом Бремерманна», согласно Гансу-Иоахиму Бремерманну, представляет собой общее число бит, обрабатываемых гипотетическим компьютером размером с Землю, работающим с максимально возможной скоростью, за период времени, равный общему времени существования Земли. Термин «трансвычислительность» был предложен...
Вычислительная мощность компьютера (производительность компьютера) — это количественная характеристика скорости выполнения определённых операций на компьютере. Чаще всего вычислительная мощность измеряется во флопсах (количество операций с плавающей запятой в секунду), а также производными от неё. На данный момент принято причислять к суперкомпьютерам системы с вычислительной мощностью более 10 терафлопсов (10*1012 или десять триллионов флопсов; для сравнения - среднестатистический современный настольный...
Гиперэвристика (гиперэвристический алгоритм) — эвристический метод поиска, направленный на автоматизацию процесса выбора, комбинирования, обобщения или адаптации нескольких более простых эвристик (или их частей) для эффективного решения вычислительной задачи.
В криптографии 'время атаки (англ. Time attack) — это атака по сторонним каналам, в которой атакующий пытается скомпрометировать криптосистему с помощью анализа времени, затрачиваемого на исполнение криптографических алгоритмов. Каждая логическая операция требует времени на исполнение на компьютере, и это время может различаться в зависимости от входных данных. Располагая точными измерениями времени для разных операций, атакующий может восстановить входные данные.
Подробнее: Атака по времени
Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.
Криптосистема Джентри (от фамилии создателя Крейга Джентри) — первая возможная конструкция для полностью гомоморфной криптосистемы, основанная на криптографии на решетках. Впервые была предложена Крейгом Джентри в 2009 году и являлась темой его докторской диссертации. Схема Джентри поддерживает операции сложения и умножения над шифротекстом, что позволяет построить кольца для реализации любых произвольных вычислений. Впоследствии имела множество доработок и модификаций с целью улучшения её производительности...
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования.
Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно...
Обучение с ошибками (англ. Learning with errors) — это концепция машинного обучения, суть которой заключается в том, что в простые вычислительные задачи (например, системы линейных уравнений) намеренно вносится ошибка, делая их решение известными методами неосуществимым за приемлемое время.
Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2. Хотя задача разбиения чисел является NP-полной, существует решение псевдополиномиального времени методом динамического программирования существуют эвристические алгоритмы решения для многих конкрентных задач либо оптимально, либо приближённо. По этой причине задачу называют "простейшей NP-трудной...
Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
Алгоритм Дугласа-Пекера — это алгоритм, позволяющий уменьшить число точек кривой, аппроксимированной большей серией точек. Алгоритм был независимо открыт Урсом Рамером в 1972 и Давидом Дугласом и Томасом Пекером в 1973. Также алгоритм известен под следующими именами: алгоритм Рамера-Дугласа-Пекера, алгоритм итеративной ближайшей точки и алгоритм разбиения и слияния.
Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. При этом алгоритм впервые разработал и опубликовал Бернард Рой (англ. Bernard Roy) в 1959 году.