Исчерпывающий — термин логики и информатики¶
Исчерпывающий — термин из области логики, теории множеств, информатики и теории информации, означающий полноту, завершённость и отсутствие пропусков в некоторой совокупности данных, аргументов или перебора вариантов. В зависимости от контекста слово применяется к перечням, классификациям, доказательствам, алгоритмам, наборам данных и методам анализа. Противоположное по смыслу понятие — «неисчерпывающий», указывающий на неполноту или ограниченность.
¶Исчерпывающий перечень (исчерпывающий список)
В юриспруденции и нормотворчестве исчерпывающий перечень — список, за пределами которого не допускается включение дополнительных элементов. Такие перечни используются в российском законодательстве, например в перечнях оснований для ограничения конституционных прав, перечнях видов деятельности, подлежащих лицензированию, и перечнях документов, необходимых для получения государственных услуг. Ключевое отличие исчерпывающего перечня от открытого (неисчерпывающего) состоит в том, что открытый перечень дополняется по усмотрению уполномоченного органа, а исчерпывающий может быть изменён только внесением поправок в сам нормативный акт.
Примеры исчерпывающих перечней в российском праве:
- перечень объектов, в отношении которых допускается приватизация;
- перечень сведений, составляющих коммерческую тайну (до 2008 года);
- перечень оснований для досрочного расторжения государственного контракта.
¶Исчерпывающее доказательство и исчерпывающая аргументация
В теории познания и методологии исчерпывающее доказательство — рассуждение, полностью обосновывающее утверждение без оставшихся неопределённых случаев. В судебной практике под исчерпывающей аргументацией понимается совокупность доводов, достаточных для принятия решения по существу спора. В математической логике доказательство считается исчерпывающим, если в нём рассматриваются все возможные случаи (метод исключения случаев) либо если опровергается каждая альтернатива рассматриваемому утверждению (от противного).
¶Исчерпывающий перебор
В информатике и теории алгоритмов исчерпывающий перебор (полный перебор, brute force) — метод решения задачи, основанный на последовательном рассмотрении всех или практически всех возможных вариантов. Метод гарантирует нахождение решения, если оно существует, но его вычислительная сложность, как правило, экспоненциальная или факториальная, что ограничивает применимость на больших объёмах данных.
Применение исчерпывающего перебора:
- криптоанализ: подбор ключа перебором всех допустимых значений;
- комбинаторные оптимизации: нахождение гамильтонова цикла, задача коммивояжёра на малых графах;
- проверка программ: перебор всех входных данных на ограниченном домене (fuzzing, model checking);
- шахматные программы: оценка позиций на несколько ходов вперёд.
В российской математической традиции метод полного перебора исследовался в работах по дискретной математике и вычислительной математике, в частности в трудах по комбинаторной оптимизации.
¶Исчерпывающая классификация
В биологии, лингвистике, библиотечном деле и других науковедческих дисциплинах исчерпывающая классификация — система деления объектов, при которой каждый элемент исследуемой совокупности попадает ровно в один класс. Требования к исчерпывающей классификации формулируются как:
- полнота охвата — каждый объект отнесён хотя бы к одному классу;
- взаимное исключение классов — объект не может одновременно принадлежать нескольким классам;
- соподчинённость — классы одного уровня сопоставимы по объёму.
Пример — Библиотечно-библиографическая классификация (ББК), разработанная в России и используемая в библиотеках страны: она стремится охватить всю сумму знаний, распределённую по отраслям.
¶Исчерпывающая информация и исчерпывающая энтропия
В теории информации исчерпывающее кодирование — способ кодирования, при котором ни один код не является префиксом другого, что позволяет однозначно декодировать сообщение без разделителей. Понятие связано с кодами Хаффмана и арифметическим кодированием. Понятие «исчерпывающей информации» используется также в теории принятия решений: исчерпывающий набор данных — такой, после получения которого дальнейшее наблюдение не меняет апостериорную вероятность гипотезы.
¶Исчерпывающий анализ в социологии и статистике
В социологических исследованиях исчерпывающее наблюдение (сплошное наблюдение) — сбор данных обо всех элементах генеральной совокупности, в отличие от выборочного наблюдения. Сплошное наблюдение применяется при переписях населения, проведение которых в России регулируется федеральным законодательством. В статистике термин употребляется для обозначения полного охвата совокупности при подсчёте показателей.
¶История и употребление термина
Слово «исчерпывающий» происходит от глагола «исчерпать» (в значении «вычерпать до дна, использовать полностью»). В научный и юридический оборот термин вошёл в XIX веке вместе с кодификацией права и развитием формальной логики. В советской философской литературе понятие обсуждалось в связи с проблемой полноты научного знания и классификаций.
¶См. также
- Полный перебор
- Библиотечно-библиографическая классификация
- Префиксный код
- Метод исключения случаев
¶Литература
- Клятисский В. Л. Логика: учебное пособие. — М., 2005.
- Клайн М. Математика. Поиск истины. — М.: Мир, 1988.
- Берри Д. С. Информация и энтропия // Кибернетика на службе науке. — М., 1962.
- ГОСТ Р 7.0.5-2008. Библиографическая ссылка.