Понятия со словом «сложность»
В теории вычислительной сложности сложность алгоритма в среднем — это количество неких вычислительных ресурсов (обычно — время), требуемое для работы алгоритма, усреднённое по всем возможным входным данным. Понятие часто противопоставляется сложности в худшем случае, где рассматривается максимальная сложность алгоритма по всем входным данным.
Цикломати́ческая сло́жность програ́ммы (англ. cyclomatic complexity of a program) — структурная (или топологическая) мера сложности компьютерной программы. Мера была разработана Томасом Дж. Маккейбом в 1976 году.
Связанные понятия
Парадо́кс Парро́ндо — парадокс в теории игр, который обычно характеризуют как комбинацию проигрышных стратегий, которая выигрывает. Парадокс назван в честь его создателя, Хуана Паррондо, испанского физика. Утверждение парадокса выглядит следующим образом...
Чемпионат мира по классическому тетрису (англ. Classic Tetris World Championship, CTWC) — это серия соревнований по видеоиграм, организуемая Portland Retro Gaming Expo. Чемпионат был впервые организован в 2010 году во время съемок фильма «Ecstasy of Order: The Tetris Masters». Чемпионат считает своей целью определить лучшего игрока в тетрис в мире. Первые два года чемпионат проводился в Лос-Анджелесе, в Калифорнии, но затем переехал в Портленд, в Орегон. Там он и проводится ежегодно с 2012 года...
Дерево Фенвика (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году. Дерево Фенвика напоминает дерево отрезков, однако проще в реализации.
«Хамса» (также называется Национальная интеллектуальная игра «Хамса»; азерб. Xəmsə; “Xəmsə” milli intellektual oyunu) — командная интеллектуальная игра, созданная в Азербайджане знатоком Фаиком Гусейновым на основе интеллектуальной игры «Эрудит-квартет» в 2006 году.
Вычисления с памятью — способ построения вычислительных платформ, в которых используются принцип хранения результатов функций в массивах памяти, одномерных или двухмерных, в виде таблиц поиска, а вычисление функций заменяется извлечением значения из таблиц. Такие вычислительные платформы могут следовать как чисто пространственной модели вычислений, как в ПЛИС, так и временно́й модели вычислений (процедурной), когда функция вычисляется за множество тактов. Второй подход нацелен на уменьшение избыточности...
В поте лица (англ. Sweat of the brow) — это правовая доктрина интеллектуальной собственности, в основном затрагивающая авторское право. Согласно этой доктрине, автор получает авторские права на свою не оригинальную работу благодаря усердию во время её создания. Примером может служить база данных, каталог или телефонный справочник. Существенного творческого подхода или оригинальности при создании подобного рода работ не требуется.
Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.
Функция Шпрага-Гранди широко используется в теории игр для нахождения выигрышной стратегии в комбинаторных играх, таких как игра Ним. Функция Шпрага-Гранди определяется для игр с двумя игроками, в которых проигрывает игрок, не имеющий возможности сделать очередной ход.
В вычислительной биологии для оценки качества сборки генома используются различные показатели, наиболее известными из которых являются статистики длин набора контигов (или скэффолдов) N50 и L50. Эти статистики являются мерами качества сборки генома. N50 — максимальная длина контига такая, что суммарная длина всех контигов не короче данного составляет не менее половины общей дины всех контигов сборки. N50 сходна с медианой или средним значением длин, но в её расчете больший вес имеют длинные контиги...
Подробнее: Оценки качества сборки генома
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Два-графы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2».
Футбольный рейтинг Эло (часто произносится побуквенно, хотя не является акронимом) — система ранжирования национальных мужских сборных по футболу. Метод основан на рейтинге Эло, но с рядом изменений, принимающих в расчёт футбольную специфику. Не следует путать рейтинг Эло с Рейтингом сборных ФИФА, который имеет более широкое распространение, так как используется международным руководящим органом.
Стратегическая карта — это диаграмма, которая используется для документирования главных стратегических целей, поставленных перед организацией или руководством организации. Это — элемент документации, ассоциирующийся со Сбалансированной системой показателей (ССП), и в частности, со вторым поколением ССП, разработанным в середине 1990-х годов. Первые диаграммы такого типа появились в 1990-х, и идея использовать такой тип диаграмм была впервые обсуждена в 1996 году в статье Р.Каплана и Д.Нортона.
Быки и коровы — логическая игра, в ходе которой за несколько попыток один из игроков должен определить, что задумал другой игрок. Варианты игры могут зависеть от типа отгадываемой последовательности — это могут быть числа, цвета, пиктограммы или слова. После каждой попытки задумавший игрок выставляет «оценку», указывая количество угаданного без совпадения с их позициями (количество «коров») и полных совпадений (количество «быков»). Роли участников игры не равнозначны — угадывающий должен анализировать...
Футбольный рейтинг — система ранжирования национальных мужских сборных по футболу. Существует несколько разновидностей, отличающихся различными критериями подсчета.
Профессиональная футбольная статистика — элемент современного профессионального футбола, служащий для совершенствования тренировочного процесса и контроля качества индивидуальной и командной игры.
Домини́рование в теории игр — ситуация, при которой одна из стратегий некоторого игрока дает больший выигрыш, нежели другая, при любых действиях его оппонентов. Обратное понятие, нетранзитивность, возникает, если некоторая стратегия может давать меньшие выигрыши, чем другая, в зависимости от поведения остальных участников.
В теории игр, игра в нормальной или стратегической форме (англ. normal form) состоит из трех элементов: множества игроков, множества чистых стратегий каждого игрока, множества платежных функций каждого игрока. Таким образом, игру в нормальной форме можно представить в виде n-мерной матрицы (таблицы), элементы которой это n-мерные платежные вектора. Эта таблица называется платёжной матрицей (англ. payoff matrix).
Подробнее: Нормальная форма игры
История чемпионата мира по футболу началась в 1928 году, когда президент ФИФА Жюль Римэ решил провести международный футбольный турнир. Первый чемпионат, который состоялся в Уругвае в 1930 году, был оспорен в качестве финального турнира, так как в нем участвовало только 13 команд. С тех пор чемпионат мира по футболу трансформировался в нынешний финальный турнир, включающий 32 команды, с предшествующим двухлетним отборочным циклом с участием почти 200 команд со всего мира.
Цифровой тёмный век — термин, описывающий предполагаемый сценарий будущего, подразумевающий значительную трудность или невозможность открытия текстовых и любых других электронных документов ввиду их устаревшего формата.
Матчевые гонки — формат проведения соревнований, когда победитель определяется в результате серии матчей между парами участников. Проще говоря, когда победитель в группе участников выявляется по результату встреч каждый с каждым. Термин применяется как правило в отношении к парусным регатам.
Двоичный алгоритм поиска подстроки (также bitap algorithm, shift-or algorithm) — алгоритм поиска подстроки, использующий тот факт, что в современных компьютерах битовый сдвиг и побитовое ИЛИ являются атомарными операциями. По сути, это примитивный алгоритм поиска с небольшой оптимизацией, благодаря которой за одну операцию производится до 32 сравнений одновременно (или до 64, в зависимости от разрядности машины). Легко переделывается на приблизительный поиск.
Фэнтези-футбол — игра, в которой участники формируют виртуальную команду футболистов, чьи прототипы принимают участие в реальных соревнованиях и, в зависимости от актуальной статистики своих выступлений, набирают зачетные баллы. Как правило, эти футболисты должны играть в одном дивизионе определенной страны, но существует и много других вариантов.
Логические трудозатраты, метод логических трудозатрат (англ. logical effort, method of logical effort) — термин, введённый...
Задачи прогнозирования — в прогностике существуют различные частные виды классических задач на прогнозирование. Формулирование таких задач единообразным образом позволяет сравнивать различные методы, предлагаемые различными дисциплинами.
Оператор Кэнни (детектор границ Кэнни, алгоритм Кэнни) в дисциплине компьютерного зрения — оператор обнаружения границ изображения. Был разработан в 1986 году Джоном Кэнни (англ. John F. Canny) и использует многоступенчатый алгоритм для обнаружения широкого спектра границ в изображениях.
Алгоритм Джонсона — позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом.
Вектор Шепли — принцип оптимальности распределения выигрыша между игроками в задачах теории кооперативных игр. Представляет собой распределение, в котором выигрыш каждого игрока равен его среднему вкладу в благосостояние тотальной коалиции при определенном механизме её формирования.
Пас — нацеленная передача мяча от одного игрока одной команды другому игроку той же команды.
Промежуточная сумма — это сумма последовательности чисел, которая обновляется каждый раз, когда новое число добавляется к последовательности, увеличивая предыдущую промежуточную сумму на величину нового значения. Другое название термина — частичная сумма.
Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования.
Оценка проектов в портфеле проектов — это анализ отдельных проектов, для составления итогового инвестиционного портфеля компании, позволяющий ей правильно оценить и выгодно распределить финансовые средства по различным проектам, и получить с этого максимальную прибыль.
Ретроспективный анализ (от лат. retro — назад и specto — смотрю), в шахматах — метод построения баз данных шахматных окончаний, выясняющий объективную оценку позиции на основе оценок всех заключительных позиций, которые могут быть получены из данной. Двигаясь в обратном направлении, переходят к позициям, которые переводятся в заключительные в 1 полуход, затем — к позициям, которые переводятся в заключительные в 2 полухода, и так далее, пока не будет достигнута исходная позиция. Ретроспективный анализ...
Многоугольник видимости или область видимости для точки p на плоскости среди препятствий — это (возможно неограниченная) многоугольная область всех точек плоскости, видимых из точки p. Многоугольник видимости можно определить для видимости из отрезка или многоугольника. Многоугольники видимости полезны в робототехнике, компьютерных играх и для определения позиций объектов, например, для определеиня наилучшего расположения охраны в картинных галереях.
Теория характеристик труда (теория основных характеристик труда; теория значимых характеристик труда; теория субъективно важных характеристик работы) — один из теоретических подходов дескриптивного типа к трудовой мотивации. Теория предложена Дж. Хакменом и Г. Р. Олдхамом в начале 1970-х годов. Учёные выделили пять основных характеристик содержания трудового процесса, который, по их мнению, отражают полное представление об особенностях репрезентации образа трудовой ситуации у сотрудника и оказывают...
Атака методом бумеранга – криптографическая атака на блочный шифр, основанная на методах дифференциального криптоанализа. Алгоритм атаки был опубликован в 1999 году профессором университета Беркли Дэвидом Вагнером, который использовал его для взлома шифров COCONUT98, Khufu и CAST-256 .
В информатике алгоритм выбора — это алгоритм для нахождения k-го по величине элемента в массиве (такой элемент называется k-й порядковой статистикой). Частными случаями этого алгоритма являются нахождение минимального элемента, максимального элемента и медианы. Существует алгоритм, который гарантированно решает задачу выбора k-го по величине элемента за O(n).
Дрон-рейсинг (от англ. drone racing) — гоночные соревнования FPV квадрокоптеров небольших размеров на специально оборудованных трассах.
Обработка сложных событий (англ. complex event processing, CEP) заключается в обработке множества событий, происходящих на всех уровнях организации, при этом идентифицируются наиболее существенные события из множества событий, анализируется их влияние и в режиме реального времени предпринимаются соответствующие действия.
Компью́теры пя́того поколе́ния (яп. 第五世代コンピュータ) — в соответствии с идеологией развития компьютерных технологий, после четвёртого поколения, построенного на сверхбольших интегральных схемах, ожидалось создание следующего поколения, ориентированного на распределенные вычисления, одновременно считалось, что пятое поколение станет базой для создания устройств, способных к имитации мышления.
Алгоритм Карплуса-Стронга для синтеза струны — способ синтеза звука, заключающийся в пропускании короткого сигнала через линию задержки с фильтром. В зависимости от параметров, полученный звук может быть похож на звук струны, извлекаемый медиатором или тэппингом, либо на звуки некоторых ударных инструментов.
Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида.
Бондграф — графическое представление динамической системы, возникающее при описании той или иной физической (механической, электрической, гидравлической, пневматической, экономической и т.д.) системы, отражающее процесс перераспределения энергии в данной системе. Похож на граф, более известный как блок-схема, или на граф прохождения сигналов и опирается на закон сохранения энергии. Основное отличие от блок-схем или графов прохождения сигналов состоит в том, что в бондграфе рёбрам ставится в соответствие...
Байесовская
игра (англ. Bayesian game) или игра с неполной информацией (англ. incomplete information game) в теории игр характеризуются неполнотой информации о соперниках (их возможных стратегиях и выигрышах), при этом у игроков есть веры относительно этой неопределённости. Байесовскую игру можно преобразовать в игру полной, но несовершенной информации, если принять допущение об общем априорном распределении. В отличие от неполной информации, несовершенная информация включает знание стратегий и выигрышей...