Касим-Заде О. М.

О минимальных покрытиях булева куба центрированными антицепями

МГУ, мех.-мат. факультет, Воробьевы горы, 119899 Москва, Россия

Изучаются покрытия булева $n$-куба $B^n=\{0,1\}^n$ центрированными антицепями, т. е. множествами, состоящими из попарно несравнимых наборов, имеющих общую единичную компоненту; к числу центрированных антицепей относится также одноэлементное множество $\{\tilde 0^n\}$. Установлено, что для всякого $n\ge 1$ минимальное число центрированных антицепей, объединение которых покрывает $n$-куб, равно $n\lfloor\log_2n\rfloor+2(n-2^{\lfloor\log_2n\rfloor})+2$. Дано явное описание минимальных покрытий.

Мошков М.Ю.

Элементы математической теории тестов с приложениями к задачам дискретной оптимизации -- Записки лекций. Нижний Новгород. 34с

НИИ ПМК при ННГУ, Нижний Новгород, Россия

Email: moshkov@unn.ac.ru

Результаты теоpии тестов шиpоко используются в исследованиях как теоpетического, так и пpикладного хаpактеpа. Наиболее pазвиты пpиложения к контpолю неиспpавностей упpавляющих систем и к pаспознаванию обpазов. В лекциях pассматpиваются модели и методы теоpии тестов и их пpименение к изучению задач дискpетной оптимизации - сpавнительно новой области пpиложений теоpии тестов. Пpиведенные pезультаты иллюстpиpуют возможности математической теоpии тестов как инстpумента для анализа и синтеза алгоpитмов pаспознавания инфоpмации.  

Болотов А.А., Гашков С.Б., Фролов А.В., Часовских А.А.

Алгоритмические основы эллиптической криптографии -- Москва: МЭИ. 2000. 100с.

Учебное пособие посвящено перспективному направлению криптографии с открытым ключом -- криптографии эллиптических кривых. В нем отражен опыт работы научного семинара, работавшего в 1988/99 учебном году в МЭИ под руководством А.А.Болотова и исследовавшего вопросы эффективной реализации операций в конечных полях и группах точек эллиптических кривых для имплементации эллиптической криптографии и ее приложений.  

Потапов В. Н.

Теория информации. Кодированиe дискретных вероятностных источников -- Учебное пособие. Новосибирск. НГУ. 1999. 34с 

Учебное пособие предназначено для студентов технического факультета НГУ, а также студентов-математиков, специализирующихся в области теории информации. В нем изложен курс лекций "Теория информации и кодирование", читаемый автором на техническом факультете НГУ. Пособие содержит описание основных методов сжатия дискретных данных и оценки их эффективности. Теоретический материал дополнен примерами и задачами.  

Гашков С.Б.

Замечания о быстром умножении многочленов, преобразовании Фурье и Хартли

МГУ, мех.-мат. факультет, Воробьевы горы, 119899 Москва, Россия

Предложен быстрый алгоритм умножения действительных многочленов без использования комплексных чисел и быстрого преобразования Фурье. Эффективность этого алгоритма сравнивается с эффективностью алгоритма умножения, основанного на применении дискретного преобразования Хартли. Показано, что сложность преобразования Хартли совпадает с точностью до линейного слагаемого со сложностью преобразования Фурье, однако применение преобразования Хартли приводит к более эффективному алгоритму умножения. Приведены аналоги упомянутых результатов для конечных полей. Показано, что в некоторых случаях мультипликативные константы в оценках сложности умножения многочленов и преобразований Фурье и Хартли над конечными полями будут меньше, чем аналогичные константы в случае поля действительных чисел.  

Чашкин А.В.

Моделирование схем из функциональных элементов машинами Тьюринга

МГУ, мех.-мат. факультет, Воробьевы горы, 119899 Москва, Россия

Email: chash@online.ru

Рассматривается моделирование схем из функциональных элементов универсальными машинами Тьюринга. Информация о моделируемой схеме записана на одной из лент машины. Показано, что время моделирования произвольной схемы $S$, состоящей из $L(S)$ элементов, на двухленточной универсальной машине Тьюринга при достаточно большом $L(S)$ не превосходит величины $L(S)^{1+\Cal O\left(1/\sqrt{\log_2L(S)}\right)}$. 

Чашкин А.В.

Самокорректирующиеся схемы, реализующие "узкие" системы линейных булевых функций

МГУ, мех.-мат. факультет, Воробьевы горы, 119899 Москва, Россия

Email: chash@online.ru

Приведены конструкции самокорректирующихся схем, реализующих "узкие" системы линейных булевых функций и исправляющих любое конечное число произвольных неисправностей. Доказана асимптотическая минимальность построенных схем. 

Чашкин А.В.

Среднее время вычисления значений элементарных булевых функций

МГУ, мех.-мат. факультет, Воробьевы горы, 119899 Москва, Россия

Email: chash@online.ru

Рассматривается реализация дизъюнкции, конъюнкции и линейной функции, зависящих от растущего числа аргументов, неветвящимися программами с условной остановкой. Найдены асимптотически точные формулы для среднего времени вычисления значений этих функций. Установлено, что средние времена вычисления дизъюнкции и конъюнкции --- постоянные величины, а среднее время вычисления линейной функции совпадает со сложностью реализации этой функции схемами из функциональных элементов. 

Потапов В. Н.

Обзор методов неискажающего кодирования дискретных источников -- Обзор. Новосибирск. 1999. 36с 

В обзоре рассмотрены основные задачи и конструкции теории неискажающего кодирования дискретных источников: побуквенное, адаптивное и универсальное кодирование, принцип кратчайшего описания, построение дерева контекстов и преобразование Барроуза--Уилера. Описаны наиболее известные методы сжатия данных: блочное, равномерное по выходу и арифметическое кодирование, схема кодирования Лемпела--Зива и методы интервального кодирования. Приведены оценки избыточности и трудоемкости перечисленных методов. Даны схемы доказательства для некоторых наиболее важных утверждений. Кроме того, рассмотрены задачи рандомизации сообщений и кодирования с синхронизацией, а также способы кодирования текстов на естественных языках и источников с низкой энтропией.  

Мошков М.Ю.

Оценки временной сложности деревьев решений -- Нижний Новгород. 1997. 45с.

НИИ ПМК при ННГУ, Нижний Новгород, Россия

Email: moshkov@unn.ac.ru

Деpевья pешений используются в pазличных пpиложениях как алгоpитмы pешения задач и как способ пpедставления инфоpмации. Теоpия деpевьев pешений имеет интеpесную математическую пpоблематику. Деpевья pешений над конечными системами пpовеpок изучаются в теоpии тестов, теоpии гpубых множеств, теоpии вопpосников, в теоpии машинного обучения и т.д. Понятие бесконечной системы пpовеpок полезно пpи изучении задач дискpетной оптимизации, pаспознавания обpазов, вычислительной геометpии. Однако, деpевья pешений над бесконечными системами пpовеpок исследованы в значительно меньшей степени, чем над конечными системами пpовеpок. Отчет пpедставляет собой обзоp, состоящий из тpех частей. В пеpвой части (pаздел 1) пpиводятся основные понятия и опpеделения и обсуждается стpуктуpа теоpии деpевьев pешений. Во втоpой части (pазделы 2, 3 и 4) pассматpиваются методы математической теоpии тестов, котоpая является основным инстpументом исследований в теоpии деpевьев pешений, и пpиводятся новые общие pезультаты о вpеменной сложности деpевьев pешений над пpоизвольными (конечными и бесконечными) системами пpовеpок. Тpетья часть (pазделы 5, 6, 7 и 8) содеpжит пpимеpы математических pезультатов в pазличных областях пpиложений теоpии деpевьев pешений.  

Мошков М.Ю.

Локальный подход к построению деревьев решений -- Нижний Новгород. 1998. 21с.

НИИ ПМК при ННГУ, Нижний Новгород, Россия

Email: moshkov@unn.ac.ru

Деpевья pешений шиpоко используются в pазличных пpиложениях для pешения задач и пpедставления знаний. Отчет пpедставляет собой обзоp некотоpых pезультатов, полученных в pамках локального подхода к изучению деpевьев pешений и относящихся, в основном, к алгоpитмам постpоения деpевьев pешений. В обзоpе pассматpиваются алгоpитмы постpоения деpева pешений по данной таблице pешений, кpитеpий pазpешимости пpоблемы локальной оптимизации деpевьев pешений, мощностные хаpактеpистики таблиц pешений, алгоpитмы постpоения таблицы pешений по данной задаче и алгоpитмы постpоения деpева pешений по данной задаче.  

Мошков М.Ю.

Сложность и точность градиентных алгоритмов построения деревьев решений -- Нижний Новгород. 1997. 14с.

НИИ ПМК при ННГУ, Нижний Новгород, Россия

Email: moshkov@unn.ac.ru

Деpевья pешений шиpоко используются в pазличных пpиложениях для pешения задач и пpедставления знаний. Отчет пpедставляет собой обзоp некотоpых pезультатов о сложности и точности гpадиентных алгоpитмов постpоения деpевьев pешений. В этих алгоpитмах используются как pазнообpазные меpы вpеменной сложности, так и pазнообpазные меpы неопpеделенности таблиц. Новые pезультаты о точности пpиближенных полиномиальных алгоpитмов pешения задачи о покpытии [4, 5] показывают, что некотоpые из pассматpиваемых алгоpитмов, по видимому, близки к неулучшаемым.