WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Оценки распределений расстояний от случайной булевой функции до аффинных и квадратичных функций

Учреждение Российской академии наук

Математический институт им. В.А.Стеклова РАН

На правах рукописи

УДК 519.7+519.213

Серов Александр Александрович

ОЦЕНКИ РАСПРЕДЕЛЕНИЙ РАССТОЯНИЙ

ОТ СЛУЧАЙНОЙ БУЛЕВОЙ ФУНКЦИИ

ДО АФФИННЫХ И КВАДРАТИЧНЫХ ФУНКЦИЙ

01.01.05 теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук Москва 2011

Работа выполнена в Учреждении Российской академии наук Математическом институте им. В. А. Стеклова РАН.

Научный руководитель: доктор физико-математических наук А. М. Зубков

Официальные оппоненты: доктор физико-математических наук, профессор Г. И. Ивченко кандидат физико-математических наук, доцент С. И. Чечёта

Ведущая организация: Механико-математический факультет Московского государственного университета им. М. В. Ломоносова

Защита диссертации состоится 12 мая 2011 года в 14 часов на заседании диссертационного совета Д 002.022.01 в МИАН по адресу: 119991, г. Москва, ул. Губкина, д. 8.

С диссертацией можно ознакомиться в библиотеке МИАН.

Автореферат разослан апреля 2011 года.

Ученый секретарь диссертационного совета Д 002.022.01 в МИАН доктор физико-математических наук В. А. Ватутин

Общая характеристика работы

Актуальность темы Понятие булевой функции сформировалось во второй половине ХIХ века в работах одного из основоположников математической логики английского математика Джорджа Буля (G. Boole, 1815-1864). В первой половине ХХ века булевы функции приобрели фундаментальное значение для оснований математики. Вместе с тем длительное время булевы функции оставались невостребованными в прикладных областях.

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

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

Как известно из практики математических исследований, линейность (в математическом смысле) изучаемого объекта упрощает его исследование.

Линейность с успехом используется в алгебре, теории систем, математической кибернетике и других разделах математики. С другой стороны, для построения надёжных криптографических систем важна как раз нелинейность, а существование свойств, близких к свойствам линейных функций, считается слабостью. Наличие таких свойств противоречит фундаментальным принципам построения криптографических систем.

Одной из мер нелинейности булевой функции f является величина Nf, численно равная расстоянию (в метрике Хэмминга) от данной функции до множества аффинных функций An.

С точки зрения теории кодирования множество аффинных функций представляет собой код Рида-Маллера первого порядка RM (1, n), а значение Nf является верхней границей для радиуса покрытия кода RM (1, n) (см. Ф. Дж. Мак-Вильямс, Н. Дж. Слоэн1 ). В случае четного n значение Nf в точности совпадает с радиусом покрытия кода RM (1, n).

При нечётном n точное значение радиуса покрытия кода RM (1, n) известно лишь для некоторых значений n, а в остальных случаях имеются только его нижние и верхние оценки.

По аналогии с нелинейностью булевой функции f как расстояния до множества аффинных функций можно рассматривать также расстояние от f до множества булевых функций, представимых в виде многочленов второй степени (квадратичных функций).

В настоящей работе получены двусторонние оценки и асимптотические формулы для количеств булевых функций от n переменных, которые с заданной точностью аппроксимируются линейными, аффинными или квадратичными булевыми функциями. Используя термины теории вероятностей, можно сказать, что эти результаты описывают распределение расстояния от случайной равновероятной булевой функции до линейных, аффинных и квадратичных функций в области вероятностей больших уклонений. Доказана предельная теорема для расстояния Хемминга между случайной равновероятной булевой функцией от n переменных и множеством аффинных булевых функций от тех же переменных, дополняющая аналогичную теорему Б.В. Рязанова для расстояния до множества линейных булевых функций.

Цели работы:

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

Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов исправляющих ошибки. М.: Связь, 1979.

Научная новизна Все полученные результаты являются новыми. Основные результаты работы состоят в следующем.

1. Доказана предельная теорема для расстояния Хемминга от случайной равновероятной булевой функции до множества аффинных булевых функций от n переменных.

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

Методы исследования В диссертации используются методы теории вероятностей и перечислительной комбинаторики.

Теоретическая и практическая ценность Работа имеет теоретический характер. Результаты диссертации могут найти применение в теории кодирования, в теории конечных автоматов и теоретической кибернетике.

Апробация работы Результаты диссертации докладывались на семинарах Отдела дискретной математики Математического института им. В. А. Стеклова РАН (г. Москва, 2007–2010 гг.), Х Всероссийском Симпозиуме по прикладной и промышленной математике (г. Санкт-Петербург, 2009 г.), Х Международном семинаре Дискретная математика и её приложения (г. Москва, 2010 г.), 9-й Международной конференции по компьютерному анализу данных и моделированию (г. Минск, 2010 г.).

Публикации Основные результаты диссертации опубликованы в 5 работах, список которых приведён в конце автореферата [1–5].

Структура диссертации Диссертация состоит из введения, четырёх глав и списка литературы.

Общий объём диссертации составляет 87 страниц. Список литературы включает 18 наименований.

Краткое содержание диссертации Во введении приведён краткий исторический обзор по тематике работы, изложены цели исследования, а также перечислены основные полученные результаты.

В первой главе диссертации доказывается предельная теорема для расстояния Хемминга между случайной равновероятной булевой функцией от n переменных и множеством аффинных булевых функций от тех же переменных, дополняющая аналогичную теорему Б.В. Рязанова для расстояния до множества линейных булевых функций.

Перейдём к более подробному изложению результатов главы 1.

Пусть F2 – поле из двух элементов. Для произвольного натурального числа n будем обозначать через Vn = Fn пространство n-мерных векторов с компонентами из F2. Между множеством FVn = {f : Vn F2 } всех булевых функций от n переменных и пространством V2n можно установить взаимно однозначное соответствие, отождествляя функцию f FVn с вектором {f (x)| x Vn }.

Расстояние Хэмминга (f, g) между булевыми функциями f, g FVn определяется как число значений переменной x Vn, при которых f (x) = g(x). Для произвольного множества булевых функций A FVn и функции f FVn обозначим через (f, A) = min (f, g) расстояние Хэмминга от f до ближайшей к ней функции из множества A.

В множестве FVn всех булевых функций естественно выделяются: класс линейных функций класс аффинных функций и класс квадратичных функций уклонений (где 1 ee 0) относительная погрешность приближения величины 22 |F2 (Qn, r)| величиной 1 ee быстро растет с уменьшением r.

Следствие 2. Если c > 1 и n, r так, что выполняется условие r < 2n1 c 2n2 (n2 + n) ln 2, то при достаточно больших n Автор выражает глубокую благодарность своему научному руководителю д.ф.-м.н. А. М. Зубкову за постановку интересных задач, постоянное внимание к работе и критические замечания.

[1] Зубков А.М., Серов А.А. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. Дискретн. матем., 2010, т. 22, № 4, с. 3–19.

[2] Серов А.А. Предельное распределение расстояния между случайной вероятн. и её примен., 2010, т. 55, № 4, с. 791–795.

[3] Зубков А.М., Серов А.А. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. Обозрение прикладной и промышленной математики, 2009, т. 16, вып. 2, с. 337–339.

[4] Зубков А.М., Серов А.А. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. Материалы Х Международного семинара Дискретная математика и её приложения (Москва, МГУ, 1-6 февраля 2010 г.). М.: Изд-во механикоматематического факультета МГУ, 2010, с. 230–232.

[5] Serov A.A., Zubkov A.M. On the number of Boolean functions in a given neighbourhood of the ane functions set. Computer Data Analysis and Modeling: Complex Sthohastic Data and Systems: Proc. of the 9th Intern.

Conf., Minsk, Sept. 7–11, 2010. Vol. 2, p. 67–70.





Похожие работы:

«КОНЮХОВА ИРИНА АЛЕКСАНДРОВНА УГЛОВЫЕ ЧАСТИЦА–ГАММА-КВАНТ КОРРЕЛЯЦИИ И ОРИЕНТАЦИОННЫЕ ХАРАКТЕРИСТИКИ ЯДЕР 11B, 12C, 28Si Специальность 01.04.16 – физика атомного ядра и элементарных частиц Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2010 Работа выполнена на кафедре физики атомного ядра и...»

«Белоусов Федор Анатольевич К ВОПРОСУ О СУЩЕСТВОВАНИИ И ЕДИНСТВЕННОСТИ ПЕРИОДИЧЕСКИХ РЕШЕНИЙ ДЛЯ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ Специальность 01.01.09 - Дискретная математика и математическая кибернетика Специальность 01.01.02 -Дифференциальные уравнения, динамические системы и оптимальное управление АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва - 2014 Работа выполнена в Федеральном государственном бюджетном учреждении науки...»

«Баталыгин Сергей Николаевич АВТОМАТИЗАЦИЯ СРЕДСТВ ДИАГНОСТИКИ ЭЛЕКТРИЧЕСКИХ ЦЕПЕЙ СИЛОВЫХ ВЫСОКОВОЛЬТНЫХ ТРАНСФОРМАТОРОВ Специальность 01.04.01 – Приборы и методы экспериментальной физики АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Ижевск – 2007 2 Работа выполнена в Федеральном государственном образовательном учреждении высшего профессионального образования Чувашский государственный университет имени И.Н. Ульянова Научный руководитель :...»

«Глаголева Анна Александровна ВЛИЯНИЕ ТЕМПЕРАТУРЫ И ПРОСТРАНСТВЕННЫХ ОГРАНИЧЕНИЙ НА САМООРГАНИЗАЦИЮ АМФИФИЛЬНЫХ ГРЕБНЕОБРАЗНЫХ МАКРОМОЛЕКУЛ Специальности 02.00.06 – высокомолекулярные соединения 01.04.07 – физика конденсированного состояния Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва–2012 Работа выполнена на кафедре физики полимеров и кристаллов физического факультета Московского Государственного Университета имени М. В....»

«Володин Владислав Владимирович ИССЛЕДОВАНИЕ ПАРАМЕТРОВ ДЕТОНАЦИОННОГО ГОРЕНИЯ ПРИ РАЗДЕЛЬНОЙ ИМПУЛЬСНОЙ ПОДАЧЕ КОМПОНЕНТОВ ТОПЛИВА 01.04.14 – теплофизика и теоретическая теплотехника Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва - 2005 Работа выполнена в Отделе физической газодинамики Института теплофизики экстремальных состояний Объединенного института высоких температур Российской академии наук Научный руководитель :...»

«Матвеенко Евгений Александрович ФИЗИЧЕСКИЕ СВОЙСТВА ТВЕРДЫХ РАСТВОРОВ La2-хСахNiO4+ 01.04.07. – Физика конденсированного состояния АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Петропавловск-Камчатский - 2008 Работа выполнена в Камчатском государственном университете имени Витуса Беринга (“КамГУ им. Витуса Беринга”). Научный руководитель : кандидат технических наук, доцент Федорченко Владимир Петрович Научный консультант : доктор...»

«Зверева Татьяна Витальевна СВЯЗНОСТИ НА ОСНАЩЕННЫХ МНОГОМЕРНЫХ ПОВЕРХНОСТЯХ В КОНФОРМНОМ ПРОСТРАНСТВЕ 01.01.04 – геометрия и топология Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Казань – 2011 Работа выполнена на кафедре геометрии ФГБОУ ВПО Чувашский государственный педагогический университет им. И. Я. Яковлева Научный руководитель : доктор физико-математических наук, профессор Столяров Алексей Васильевич Официальные оппоненты :...»

«Матвеев Иван Алексеевич Методы и алгоритмы автоматической обработки изображений радужной оболочки глаза 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук Москва – 2014 Работа выполнена в Федеральном государственном бюджетном...»

«УДК 512.815.1, 512.816.2 Стырт Олег Григорьевич Компактные линейные группы с факторпространством, гомеоморфным клетке 01.01.06 математическая логика, алгебра и теория чисел АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва 2011 Работа выполнена на кафедре высшей алгебры Механико-математического факультета Московского государственного...»

«УДК 517.55 + 517.958 Домрин Андрей Викторович ГОЛОМОРФНЫЕ РЕШЕНИЯ СОЛИТОННЫХ УРАВНЕНИЙ 01.01.01 — вещественный, комплексный и функциональный анализ автореферат диссертации на соискание ученой степени доктора физико-математических наук Москва 2013 Работа выполнена в ФГБОУ ВПО “Московский государственный университет им. М. В. Ломоносова”. Официальные оппоненты : доктор физико-математических наук, профессор Гриневич Петр Георгиевич, старший научный сотрудник ФГБУН Институт...»

«Макарова Елена Станиславовна ТЕРМОДИНАМИКА РАСТВОРОВ ПОЛИЭЛЕКТРОЛИТОВ В ГАУССОВОМ ЭКВИВАЛЕНТНОМ ПРЕДСТАВЛЕНИИ В РАМКАХ МЕЗОСКОПИЧЕСКИХ МОДЕЛЕЙ. ВОДНЫЙ РАСТВОР ХОНДРОИТИНСУЛЬФАТА 02.00.04-физическая химия АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата химических наук Иваново 2008 www.sp-department.ru Работа выполнена в Учреждении Российской академии наук Институте химии растворов РАН Научный руководитель : кандидат физико-математических наук, доцент НОГОВИЦЫН...»

«Рахматуллина Жанна Геннадьевна ТЕОРЕМЫ О МИНИМУМЕ МОДУЛЯ И МНОЖЕСТВО ФАТУ ЦЕЛОЙ ФУНКЦИИ С ЛАКУНАМИ 01.01.01 вещественный, комплексный и функциональный анализ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Уфа 2011 Работа выполнена в Учреждении Российской академии наук Институт математики с вычислительным центром Уфимского научного центра РАН. Научный руководитель : доктор физико-математических наук, профессор Гайсин Ахтяр Магазович...»

«ТРОИЦКИЙ ВИКТОР СЕРГЕЕВИЧ КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ОБРАЗОВАНИЯ ПОР В ДИЭЛЕКТРИЧЕСКИХ КРИСТАЛЛАХ Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Барнаул – 2007 Работа выполнена на кафедре общей физики ГОУ ВПО Алтайский государственный технический университет им. И.И.Ползунова Научный руководитель : Доктор физико-математических наук, профессор...»

«КАЗАНЦЕВА ЕКАТЕРИНА ЛЕОНИДОВНА ВЛИЯНИЕ ДИСПЕРСНОСТИ И ПОСТОЯННЫХ ПРИМЕСЕЙ НА СТРУКТУРУ, СВОЙСТВА И ПРЕВРАЩЕНИЯ – Al(OH)3 Специальность 02. 00. 21 – химия твердого тела Автореферат диссертации на соискание ученой степени кандидата химических наук Челябинск 2010 2 Работа выполнена в ГОУ ВПО Челябинский государственный педагогический университет Научный руководитель : доктор химических наук, профессор Толчев Александр Васильевич Официальные оппоненты : доктор химических наук,...»

«УДК 621.373 ПРОХОРОВ АЛЕКСЕЙ ВАЛЕРЬЕВИЧ КОГЕРЕНТНЫЕ ЭФФЕКТЫ РЕЗОНАНСНЫХ ВЗАИМОДЕЙСТВИЙ МНОГОЧАСТИЧНЫХ АТОМНЫХ СИСТЕМ И ЭЛЕКТРОМАГНИТНОГО ПОЛЯ Специальность 01.04.21 – лазерная физика АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва 2005 Работа выполнена на кафедре физики и прикладной математики Владимирского государственного университета. Научный руководитель : доктор физико-математических наук, профессор Аракелян Сергей...»

«Илларионов Андрей Анатольевич Статистические свойства полиэдров Клейна и локальных минимумов решеток 01.01.06 — математическая логика, алгебра и теория чисел Автореферат диссертации на соискание ученой степени доктора физико-математических наук Хабаровск – 2014 Общая характеристика работы Актуальность темы. Алгоритм разложения вещественного числа в непрерывную (цепную) дробь является одним из важнейших инструментов теории чисел, восходящим еще к античному алгоритму Евклида...»

«Афанасьев Антон Александрович МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ДЕНЕЖНОГО ОБРАЩЕНИЯ В ХОЗЯЙСТВЕ С ГАЗОВОЙ ОТРАСЛЬЮ Специальность 08.00.13. – Математические и инструментальные методы экономики (экономические наук и) Автореферат диссертации на соискание учёной степени доктора экономических наук Москва – 2013 Работа выполнена в Федеральном государственном бюджетном учреждении науки Центральном экономико-математическом институте Российской академии наук (ЦЭМИ РАН) Научный консультант...»

«Адамьян Дмитрий Юрьевич Метод генерации синтетической турбулентности на входных границах для расчета турбулентных течений в рамках вихреразрешающих подходов 01.02.05 – Механика жидкости, газа и плазмы АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Санкт-Петербург – 2011 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования “Санкт-Петербургский государственный...»

«ШУРУХИН Виталий Олегович ИЗУЧЕНИЕ ЭНТРОПИИ В КУРСЕ ФИЗИКИ СРЕДНЕЙ ШКОЛЫ Специальность: 13.00.02 - теория и методика обучения физике АВТОРЕФЕРАТ ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ КАНДИДА ТА ПЕДАГОГИЧЕСКИХ НА УК Санкт-Петербург 2000 Работа выполнена на кафедре методики обучения физике Российского государственного педагогического университета им.А.И. Герцена. Научный руководитель : кандидат педагогических наук, доцент А.А.Быков Официальные оппоненты : член-корреспондент...»

«КОНОНОВА Полина Александровна АЛГОРИТМЫ ПОСТРОЕНИЯ РАСПИСАНИЙ ДЛЯ ЦЕХОВЫХ ЗАДАЧ ПОТОКОВОГО ТИПА С ЦИФРОВЫМ БУФЕРОМ Специальность 05.13.18 математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Новосибирск – 2012 Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук...»














 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.