Рубрика «перебор»

в 15:54, , рубрики: sql, высокая производительность, оптимизация запросов, перебор, Программирование, распределение в запросе

Хороший перебор — это отсутствие перебора. Рассмотрим пример замены полного перебора запросом.

В свое время, года 3 назад, возникла необходимость оптимизации конфигурации 1С и устранения ее узких мест в одной компании. Одним из таких узких мест оказался, казалось бы, безобидный, механизм распределения товаров в реализации по сериям. Суть в том, что строк распределялось достаточно много и было это очень медленно. Не миллионы за раз, конечно, но на это самое распределение для одного документа могло уходить до минуты.

Запрос специально привожу на T-SQL, т.к. думаю, что Хабравцам это будет ближе.
Читать полностью »

в 15:28, , рубрики: Алгоритмы, база решений, игры, искусственный интеллект, комбинаторика, логические игры, перебор, поиск в ширь, Программирование, шахматы

Хотите озадачить начинающего шахматиста?
Попросите его поставить мат конём и слоном.

Хотите озадачить начинающего программиста?
Попросите его рассчитать мат конём и слоном.

image

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

в 16:58, , рубрики: Алгоритмы, генерация кроссвордов, Занимательные задачки, перебор, Программирование, метки:

С статье "Алгоритм формирования кроссвордов" были предложены несколько эвристик, которые были реализованы в программе автоматической генерации кроссвордов. Несмотря на то, что предложенные эвристики хорошо проработаны, даже они не позволили за разумное время сгенерировать кроссворд для самой сложной из приведенных сеток:

image
Этот и все последующие рисунки взяты из исходной статьи

В этой статье, я бы хотел обсудить гораздо более простое решение, которое позволяет решить эту задачу.
Читать полностью »

в 16:49, , рубрики: гаджеты, Здоровье гика, перебор, роботы, сидячая работа, стол

Автоматический стол изменит свою высоту и подскажет вам, когда сидеть, а когда — стоять - 1

«Умный» стол от компании Stir не только подскажет вам, что пришло время сменить позицию (с сидячей на стоячую или наоборот), но и благодаря встроенным моторам, автоматически поднимется или опустится. Это уже второе поколение подобных устройств от Stir.
Читать полностью »

в 18:58, , рубрики: Алгоритмы, математика, перебор, Программирование, метки: ,

В данной статье будут рассмотрены следующие вопросы:

  • Двоичные коды Грея. Их существование. Перебор подмножеств данного множества в порядке минимального изменения.
  • Существование и реализация перебора подмножеств из k элементов в порядке минимального изменения.

Итак, приступим.
Читать полностью »

в 10:50, , рубрики: Алгоритмы, оптимизация, перебор, метки: ,

В прошлой статье я писал про эвристические методы оптимизации перебора. В этой статье я расскажу вам о ещё одной, но уже асимптотической оптимизации — meet-in-the-middle.

Типичные для этого метода снижения асимптотики: Meet in the middle: оптимизация перебора и не только и Meet in the middle: оптимизация перебора и не только.

Вступление

Метод заключается в том, чтобы разделить задачу пополам, получить какие-то данные и сопоставить их друг с другом.

Meet-in-the-middle имеет смысл применять, если для конкретной задачи выполняются два условия:
1) Время обработки половины данных асимптотически меньше времени получения итогового ответа.
2) Известен асимптотически более быстрый способ получения ответа для всей задачи с использованием информации об обработки её половинок.
Читать полностью »

в 8:34, , рубрики: bruteforce, Алгоритмы, жадность, оптимизация, перебор, метки: , , ,

Дисклеймер: для понимания этой статьи требуются начальные знания теории графов, в частности знание поиска в глубину, поиска в ширину и алгоритма Беллмана — Форда.

Введение

Наверняка вы сталкивались с задачами, которые приходилось решать перебором. А если вы занимались олимпиадным программированием, то точно видели NP-полные задачи, которые никто не умеет решать за полиномиальное время. Такими задачами, например, является поиск пути максимальной длины без самопересечений в графе и многим известная игра — судоку, обобщенная на размер Оптимизация перебора. Полный перебор крайне долгий, ведь время его работы растёт экспоненциально относительно размера входных данных. Например, время поиска максимального пути в графе из 15 вершин наивным перебором становится заметным, а при 20 — очень долгим.

В этом посте я расскажу как можно оптимизировать большинство переборов, чтобы они стали работать на порядки быстрее.
Читать полностью »

в 2:03, , рубрики: брутфорс, генератор паролей, информационная безопасность, перебор, частотный анализ, метки: , , , ,

Генератор/валидатор паролей по результатам взлома LinkedInПосле анализа подобранных паролей к LinkedIn появилась идея создать генератор паролей, совмещенный с валидатором, не допускающим легко подбирающиеся пароли. Простейшего анализа на длину, наличие специальных символов здесь не достаточно — некоторые пароли можно легко собрать из очень вероятных «кусочков» и на их перебор уходит существенно меньшее время, нежели теоретически заявленное. И гарантий, что программа-генератор не выдаст вам подобный пароль нет — случайность, она на то и случайность. Мое творение не претендует на полное решение вопроса, скорее это повод для размышлений, но оно вполне работоспособно (исходники и небольшой разбор тоже присутствуют).
Читать полностью »

в 18:31, , рубрики: CUDA, sha1, Алгоритмы, брутфорс, информационная безопасность, перебор, радужные таблицы, релевантность, Соль, частотный анализ, метки: , , , , , , ,

Анализ возможностей массового аудита на основе утечки хешей из LinkedInНеделю назад утекла база хешей с LinkedIn, для других это событие может быть примечательным само по себе, но для меня, в первую очередь, это означает возможность провести анализ современных возможностей взлома паролей. И я не собираюсь рассказывать о том сколько раз слово «password» было встречено среди паролей и о том, сколько времени занимает перебор шестисимвольных комбинаций. Скорее буду пугать пользователей тем, насколько сложные пароли можно «взломать» за несколько часов. А программистам расскажу как это возможно эффективно реализовать, и в качестве небольшого подарка приложу программу, которую я написал для массового аудита. Присутствует и некоторый ликбез по использованию радужных таблиц с простыми выводами.

И так, за час удалось «восстановить» около 2.5 миллионов паролей на средней рабочей конфигурации, без специальных словарей и радужных таблиц. Среди найденных паролей присутствуют 16-символьные алфавитно-цифровые комбинации, и далеко не в единственном экземпляре.
Читать полностью »

в 20:37, , рубрики: Алгоритмы, кубик рубика, перебор, Программирование, метки: , ,

Недавно я решил написать программу, которая будет выдавать алгоритм решения некоторых механических головоломок, таких как кубик 2х2х2, 3х3х1, пирамидка и других. Полный список есть в интерфейсе программы, а также на её сайте, но об этом позже. Естественно, алгоритм этот должен быть самым коротким, иначе не интересно: можно было бы забить туда известные формулы, чтобы она собирала как человек. Сразу скажу две причины, почему я не стал включать в список кубик Рубика 3х3: во-первых, из за его популярности. Наверняка есть уже куча софта для этого, не хочется изобретать велосипед. Ну и во-вторых, из за его сложности: начав писать программу, я хотел «потренироваться» на чём-нибудь попроще. Итак, приступим. Читать полностью »

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js