В данной статье будут рассмотрены следующие вопросы:
Итак, приступим.
Читать полностью »
В прошлой статье я писал про эвристические методы оптимизации перебора. В этой статье я расскажу вам о ещё одной, но уже асимптотической оптимизации — meet-in-the-middle.
Типичные для этого метода снижения асимптотики: 
и 
.
Метод заключается в том, чтобы разделить задачу пополам, получить какие-то данные и сопоставить их друг с другом.
Meet-in-the-middle имеет смысл применять, если для конкретной задачи выполняются два условия:
1) Время обработки половины данных асимптотически меньше времени получения итогового ответа.
2) Известен асимптотически более быстрый способ получения ответа для всей задачи с использованием информации об обработки её половинок.
Читать полностью »
Дисклеймер: для понимания этой статьи требуются начальные знания теории графов, в частности знание поиска в глубину, поиска в ширину и алгоритма Беллмана — Форда.
Наверняка вы сталкивались с задачами, которые приходилось решать перебором. А если вы занимались олимпиадным программированием, то точно видели NP-полные задачи, которые никто не умеет решать за полиномиальное время. Такими задачами, например, является поиск пути максимальной длины без самопересечений в графе и многим известная игра — судоку, обобщенная на размер 
. Полный перебор крайне долгий, ведь время его работы растёт экспоненциально относительно размера входных данных. Например, время поиска максимального пути в графе из 15 вершин наивным перебором становится заметным, а при 20 — очень долгим.
В этом посте я расскажу как можно оптимизировать большинство переборов, чтобы они стали работать на порядки быстрее.
Читать полностью »
После анализа подобранных паролей к LinkedIn появилась идея создать генератор паролей, совмещенный с валидатором, не допускающим легко подбирающиеся пароли. Простейшего анализа на длину, наличие специальных символов здесь не достаточно — некоторые пароли можно легко собрать из очень вероятных «кусочков» и на их перебор уходит существенно меньшее время, нежели теоретически заявленное. И гарантий, что программа-генератор не выдаст вам подобный пароль нет — случайность, она на то и случайность. Мое творение не претендует на полное решение вопроса, скорее это повод для размышлений, но оно вполне работоспособно (исходники и небольшой разбор тоже присутствуют).
Читать полностью »
Неделю назад утекла база хешей с LinkedIn, для других это событие может быть примечательным само по себе, но для меня, в первую очередь, это означает возможность провести анализ современных возможностей взлома паролей. И я не собираюсь рассказывать о том сколько раз слово «password» было встречено среди паролей и о том, сколько времени занимает перебор шестисимвольных комбинаций. Скорее буду пугать пользователей тем, насколько сложные пароли можно «взломать» за несколько часов. А программистам расскажу как это возможно эффективно реализовать, и в качестве небольшого подарка приложу программу, которую я написал для массового аудита. Присутствует и некоторый ликбез по использованию радужных таблиц с простыми выводами.
И так, за час удалось «восстановить» около 2.5 миллионов паролей на средней рабочей конфигурации, без специальных словарей и радужных таблиц. Среди найденных паролей присутствуют 16-символьные алфавитно-цифровые комбинации, и далеко не в единственном экземпляре.
Читать полностью »
Недавно я решил написать программу, которая будет выдавать алгоритм решения некоторых механических головоломок, таких как кубик 2х2х2, 3х3х1, пирамидка и других. Полный список есть в интерфейсе программы, а также на её сайте, но об этом позже. Естественно, алгоритм этот должен быть самым коротким, иначе не интересно: можно было бы забить туда известные формулы, чтобы она собирала как человек. Сразу скажу две причины, почему я не стал включать в список кубик Рубика 3х3: во-первых, из за его популярности. Наверняка есть уже куча софта для этого, не хочется изобретать велосипед. Ну и во-вторых, из за его сложности: начав писать программу, я хотел «потренироваться» на чём-нибудь попроще. Итак, приступим. Читать полностью »
