|
|
Пробл. управл., 2008, выпуск 1, страницы 43–50
(Mi pu132)
|
 |
|
 |
Эта публикация цитируется в 14 научных статьях (всего в 14 статьях)
Информационные технологии в управлении
Технология крупноблочного параллелизма в SAT-задачах
О. С. Заикин, A. A. Семенов
Институт динамики систем и теории управления СО РАН,
г. Иркутск
Аннотация:
Предложен новый подход к решению SAT-задач, основанный на концепции крупноблочного параллелизма, свойственного многочисленным задачам большой размерности. В рамках данного подхода строится декомпозиция исходной конъюнктивной нормальной формы (КНФ) на семейство КНФ с последующим решением SAT-задачи для каждой КНФ полученного семейства на отдельном вычислительном узле кластера. Планирование оптимального по трудоемкости вычисления осуществляется через решение задачи оптимизации специальной прогнозной функции. Эффективность подхода подтверждена на примере задач криптоанализа суммирующего и порогового генераторов.
 Полный текст:
PDF файл (427 kB)
Список литературы:
PDF файл
HTML файл
Тип публикации:
Статья
УДК:
519.7
Образец цитирования:
О. С. Заикин, A. A. Семенов, “Технология крупноблочного параллелизма в SAT-задачах”, Пробл. управл., 2008, № 1, 43–50
Цитирование в формате AMSBIB
\RBibitem{ZaiSem08}
\by О.~С.~Заикин, A.~A.~Семенов
\paper Технология крупноблочного параллелизма в~SAT-задачах
\jour Пробл. управл.
\yr 2008
\issue 1
\pages 43--50
\mathnet{http://mi.mathnet.ru/pu132}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/pu132 http://mi.mathnet.ru/rus/pu/v1/p43
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
А. С. Игнатьев, А. А. Семенов, Д. В. Беспалов, О. С. Заикин, “Гибридный подход (SAT+ROBDD) в задачах криптоанализа поточных систем шифрования”, ПДМ, 2009, приложение № 1, 19–20
 -
А. А. Семёнов, “О преобразованиях Цейтина в логических уравнениях”, ПДМ, 2009, № 4(6), 28–50
-
Семенов А.А., “Декомпозиционные представления логических уравнений в задачах обращения дискретных функций”, Изв. РАН. Теория и системы управления, 2009, № 5, 47–61
 ; Semenov A.A., “Decomposition representations of logical equations in problems of inversion of discrete functions”, J. Comput. Systems Sci. Internat., 48:5 (2009), 718–731     -
Семенов А.А., Отпущенников И.В., Кочемазов С.Е., “Пропозициональный подход в задачах тестирования дискретных автоматов”, Современные технологии. Системный анализ. Моделирование, 2009, № 4, 48–56
-
Игнатьев А.С., Семенов А.А., Хмельнов А.Е., “Использование двоичных диаграмм решений в задачах обращения дискретных функций”, Вестн. Томского гос. ун-та. Управление, вычислительная техника и информатика, 2009, № 1, 115–129
-
А. С. Игнатьев, А. А. Семенов, “Алгоритмы работы с ROBDD как с базами булевых ограничений”, ПДМ, 2010, № 1(7), 86–104
-
Бычков И.В., Опарин Г.А., Новопашин А.П., Феоктистов А.Г., Корсуков А.С., Сидоров И.А., “Высокопроизводительные вычислительные ресурсы Института динамики систем и теории управления СО РАН: текущее состояние, возможности и перспективы развития”, Вычислительные технологии, 15:3 (2010), 69–81
-
Опарин Г.А., Феоктистов А.Г., Сидоров И.А., “Разработка и применение распределенных пакетов прикладных программ”, Программные продукты и системы, 2010, № 2, 15
-
О. С. Заикин, “Решение задач криптоанализа в грид-системах (на примере BOINC)”, ПДМ, 2011, приложение № 4, 66–67
-
Заикин О.С., Отпущенников И.В., Семенов А.А., “Параллельные алгоритмы решения проблемы выполнимости в применении к оптимизационным задачам с булевыми ограничениями”, Вычислительные методы и программирование: новые вычислительные технологии, 12:1 (2011), 205–212
-
Евдокимов А.А., Кочемазов С.Е., Семенов А.А., “Применение символьных вычислений к исследованию дискретных моделей некоторых классов генных сетей”, Вычислительные технологии, 16:1 (2011), 30–47
-
Новопашин А.П., Сидоров И.А., Горский С.А., “Инструментальные средства организации параллельных вычислений в пакетах прикладных программ”, Вестник уфимского государственного авиационного технического университета, 15:5 (2011), 78–86
-
Заикин О.С., Посыпкин М.А., Семёнов А.А., Храпов Н.П., “Опыт организации добровольных вычислений на примере проектов optima@home и sat@home”, Вестник нижегородского университета им. Н.И. Лобачевского, 2012, 340–347
-
О. С. Заикин, А. А. Семёнов, М. А. Посыпкин, “Процедуры построения декомпозиционных множеств для распределенного решения sat-задач в проекте добровольных вычислений sat@home”, УБС, 43 (2013), 138–156
|
| Просмотров: |
| Эта страница: | 356 | | Полный текст: | 94 | | Литература: | 32 |
|
Пользовательское соглашение