Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

Полный перебор

31 мая 2011 года в 18:57   Просмотров: 3117

Полный перебор (или метод «грубой силы» от англ. brute force) — метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

Любая задача из класса NP может быть решена полным перебором. При этом, даже если вычисление целевой функции от каждого конкретного возможного решения задачи может быть осуществлена за полиномиальное время, в зависимости от количества всех возможных решений полный перебор может потребовать экспоненциального времени работы.

В криптографии на вычислительной сложности полного перебора основывается оценка криптостойкости шифров. В частности, шифр считается криптостойким, если не существует метода «взлома» существенно более быстрого чем полный перебор всех ключей. Криптографические атаки, основанные на методе полного перебора, являются самыми универсальными, но и самыми долгими.

Методы оптимизации полного перебора

Метод ветвей и границ

Для ускорения перебора метод ветвей и границ использует отсев подмножеств допустимых решений, заведомо не содержащих оптимальных решений.

Распараллеливание вычислений


Для увеличения скорости подбора ключа используется распараллеливание вычислений. Существует два подхода к распараллеливанию:
Первый подход — построение конвейера. Пусть алгоритм соотношения можно представить в виде цепочки простейших действий (операций): . Возьмём процессоров , зададим их порядок и положим, что — ый процессор выполняет три одинаковые по времени операции:
приём данных от — го процессора;
выполнение операции ;
передача данных следующему -му процессору.
Тогда конвейер из последовательно соединённых, параллельно и синхронно работающих процессоров работает со скоростью , где — скорость выполнения одной операции одним процессором.
Второй подход состоит в том, что множество всех возможных ключей разбивается на непересекающиеся подмножества . Система из машин перебирает ключи так, что — ая машина осуществляет перебор ключей из множества . Система прекращает работу, если одна из машин нашла ключ. Самое трудное — это разделение ключевого множества. Но если каждый процессор начнёт вычисление с какого-то произвольного ключа, то время нахождения увеличится, а схема значительно упростится. Среднее число шагов в этом случае составляет , где — число элементов во множестве ключей, а — число процессоров.

Пример продолжительности подбора паролей

В таблице представлено оценочное время полного перебора паролей в зависимости от их длины. Предполагается, что в пароле могут использоваться 36 различных символов (латинские буквы одного регистра + цифры), а скорость перебора составляет 100 000 паролей в секунду.[1]Кол-во знаков Кол-во вариантов Время перебора
1  = 36 = менее секунды
2 = 1296 = менее секунды
3 = 46 656 = менее секунды
4 = 1 679 616 = 17 секунд
5 = 60 466 176 = 10 минут
6 = 2 176 782 336 = 6 часов
7 = 78 364 164 096 = 9 дней
8 = 2,821 109 9 x 1012 = 11 месяцев
9 = 1,015 599 5x1014 = 32 года
10 = 3,656 158 4x1015 = 1 162 года
11 = 1,316 217 0x1017 = 41 823 года
12 = 4,738 381 3x1018 = 1 505 615 лет


Таким образом, пароли длиной до 6 символов в общем случае не являются надежными.

Оставить комментарий

Пожалуйста, введите символы, показанные на рисунке.

Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта