Прикладная дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2013, номер 2(20), страницы 59–70 (Mi pdm404)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Вычислительные методы в дискретной математике

Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искажённой правой частью

А. Н. Алексейчук, А. Ю. Грязнухин

Институт специальной связи и защиты информации Национального технического университета Украины "Киевский политехнический институт", г. Киев, Украина

Аннотация: Рассматривается система линейных булевых уравнений с искажённой правой частью, истинное решение которой имеет заданный вес, не зависящий от числа неизвестных в системе. Предлагается вероятностный алгоритм нахождения этого решения, имеющий меньшую временную сложность по сравнению с методом максимума правдоподобия. В отличие от известных алгоритмов, обладающих указанным свойством, предложенный алгоритм использует только операции сравнения и (поразрядного и арифметического) сложения двоичных целых чисел, что позволяет применять его на практике в случае, когда другие алгоритмы оказываются менее эффективными.

Ключевые слова: система булевых уравнений с искаженной правой частью, вероятностный алгоритм.

Полный текст: PDF файл (671 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 631.391+519.2

Образец цитирования: А. Н. Алексейчук, А. Ю. Грязнухин, “Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искажённой правой частью”, ПДМ, 2013, № 2(20), 59–70

Цитирование в формате AMSBIB
\RBibitem{AleGry13}
\by А.~Н.~Алексейчук, А.~Ю.~Грязнухин
\paper Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с~искажённой правой частью
\jour ПДМ
\yr 2013
\issue 2(20)
\pages 59--70
\mathnet{http://mi.mathnet.ru/pdm404}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm404
  • http://mi.mathnet.ru/rus/pdm/y2013/i2/p59

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Е. К. Алексеев, И. Б. Ошкин, В. О. Попов, С. В. Смышляев, “Решение систем линейных уравнений булева типа с искаженной правой частью над полем действительных чисел”, Дискрет. матем., 29:1 (2017), 3–9  mathnet  crossref  elib; E. K. Alekseev, I. B. Oshkin, V. O. Popov, S. V. Smyshlyaev, “Solving systems of linear Boolean equations with noisy right-hand sides over the reals”, Discrete Math. Appl., 28:1 (2018), 1–5  crossref  isi
    2. Н. Ю. Руменко, А. В. Костюк, “Способ решения недоопределённых систем линейных уравнений над $\mathrm{GF}(2)$ с искажёнными правыми частями и ограничением на малый вес решения”, ПДМ. Приложение, 2019, № 12, 235–237  mathnet  crossref  elib
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:233
    Полный текст:92
    Литература:26
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2022