English
Том 21 выпуск 3(PDF)
В данной работе приведен обзор некоторых результатов о вычислительной сложности алгебр, в частности, результатов, полученных на кафедре математической кибернетики МГУ им. М.В. Ломоносова автором и его учениками: Поспеловым А.Д., Чокаевым Б.В., Лысиковым В.В.
Ключевые слова: алгебраическая сложность, алгебра, ранг алгебры, билинейная сложность, мультипликативная сложность, сложность умножения матриц.
Для моделирования фазовых переходов в многокомпонентных растворах часто используется обобщенная модель «черной нефти». При изучении численных неустойчивостей модели было обнаружено, что они могут возникать из-за термодинамического рассогласования функций в окрестности критической точки раствора, которая, как известно, физически неустойчива по своей природе. Все измеряемые величины из-за флуктуаций, происходящих в этой об- ласти, имеют значительные погрешности измерений, что приводит к существенному рассогласованию параметров модели и соответственно к численным неустойчивостям. Предлагается физический подход к моделированию таких областей. Объяснены некоторые причины неточности моделей «черной нефти».
Ключевые слова:
В работе исследована задача о цепочках. Приведены результаты об области существования цепочек, полученных из данной переводом конца цепочки в заданную точку; оценки минимума евклидова расстояния между цепочками, получаемыми друг из друга переводом конца в заданную точку; возможное количество цепочек, полученных переводом конца в заданную точку и отличающихся минимальным количеством звеньев от данной цепочки; возможное количество цепочек, находящихся на минимальном расстоянии от данной и полученных переводом конца цепочки в заданную точку, для n = 2 и n = 3. Описаны алгоритмы перевода конца цепочки в заданную точку: экспоненциальный алгоритм, перебирающий все возможные цепочки с шагом ε, линейный алгоритм, дающий примерное решение для евклидова расстояния, и линейный алгоритм, дающий точный ответ для расстояния Хэмминга и примерный для евклидова расстояния.
Ключевые слова: цепочка, алгоритм, верхние оценки, нижние оценки, евклидово расстояние, расстояние Хэмминга.
Излагаются основные криптографические примитивы, используемые в протоколах безопасности (симметричные и асимметричные системы шифрования, хэш-функции, схемы разделения секрета), протоколы аутентификации, и алгоритмы цифровой подписи.
Ключевые слова: протоколы, безопасность, криптография, хэш-функции, аутентификация, цифровая подпись.
В работе представлены алгоритмы построения проверочных матриц для LDPC - кодов на основе графа Таннера с обхватом 8. Также, в качестве параметров графа выступают разбиение степеней символьных вершин: отношение вершин степени 3 и степени 4 к общему числу символьных вершин, и скорость полученного кода. Код строится для произвольной скорости и произвольного разбиения за линейное, относительно количество элементов матрицы, время.
Ключевые слова: LDPC - коды, граф Таннера, двудольные графы, распределение степеней вершин.
В кандидатской диссертации [1] была поставлена и решена задача о нахождении верхней оценки на минимальную длину слов из регулярного языка, склеивающихся (то есть имеющих совпадающий образ) при алфавитном кодировании (если такая склейка вообще существует). В данной статье исследуется задача о нахождении соответствующих нижних оценок на длину склейки для случая, когда регулярные языки имеют линейную функцию роста, а схема кодирования преобразует все буквы входного алфавита в один и тот же символ. Для такого кодирования образ слова однозначно определяется по его длине. Приводятся нижние оценки, совпадающие по порядку с верхними оценками из [1] для таких языков и такого кодирования. Кроме того, для этого подслучая приводится более точная верхняя оценка.
Ключевые слова: алфавитное кодирование, регулярный язык, склейка.
В работе формулируется и доказывается критерий полиномиальной полноты квазигрупп в терминах предполных классов k-значной логики.
Ключевые слова: квазигруппа, полиномиальная полнота, квазилинейность.