WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 38 |
РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ СОВРЕМЕННЫЕ ПРОБЛЕМЫ МАТЕМАТИКИ Тезисы Международной (43-й Всероссийской) молодежной школы-конференции, 29 января 5 февраля 2012 г.

ЕКАТЕРИНБУРГ 2012 РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ СОВРЕМЕННЫЕ ПРОБЛЕМЫ МАТЕМАТИКИ Тезисы Международной (43-й Всероссийской) молодежной школы-конференции, 29 января 5 февраля 2012 г.

ЕКАТЕРИНБУРГ 2012 УДК 51 СОВРЕМЕННЫЕ ПРОБЛЕМЫ МАТЕМАТИКИ: тезисы Международной (43-й Всероссийской) молодежной школы-конференции. Екатеринбург: Институт математики и механики УрО РАН, 2012.

Настоящее издание включает тезисы Международной (43-й Всероссийской) школы-конференции молодых ученых, прошедшей с 29 января по 5 февраля 2012 года в г. Екатеринбурге.

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

Сборник представляет интерес для специалистов по указанным областям науки.

Конференция проведена при финансовой поддержке РФФИ (проект 12-01-06802) и Президиума УрО РАН (грант поддержки молодежных научных школ и конференций).

Ответственный редактор чл.-корр. РАН А.А. Махнев.

Рецензенты:

чл.-корр. РАН А.А. Махнев, д.ф.-м.н. А.Л. Агеев, д.ф.-м.н. А.Г. Бабенко, к.ф.-м.н. А.Л. Гаврилюк, д.ф.-м.н. А.Р. Данилин, д.ф.-м.н.

А.В. Ким, д.ф.-м.н. А.С. Кондратьев, д.ф.-м.н. А.И. Короткий, к.ф.м.н. В.Б. Костоусов, д.ф.-м.н. Н.Ю. Лукоянов, к.ф.-м.н. Н.В. Маслова, к.ф.-м.н. М.Ф. Прохорова, д.ф.-м.н. С.С. Титов, д.ф.-м.н.

М.Ю. Хачай, к.ф.-м.н. Д.В. Хлопин, д.ф.-м.н. В.Т. Шевалдин.

Ответственные за выпуск:

Л.В. Камнева, Н.В. Маслова, М.С. Морина, С.Ф. Правдин.

© Институт математики и механики УрО РАН, 2012 г.

Алгебра МЕТРИЧЕСКИЕ ИНВАРИАНТЫ ДЛЯ ВОССТАНОВЛЕНИЯ КОДОВ Августинович С.В., Горкунов Е.В.Рассмотрим булев куб En = {0, 1}n с расстоянием Хэмминга, заданным на его вершинах: d(x, y) = |{i | xi = yi}|. Двоичным кодом длины n называется любое подмножество En. Минимальное расстояние между различными вершинами кода определяет его кодовое расстояние. Два кода эквивалентны, если существует изометрия булева куба, отображающая один код в другой.

Интересен вопрос о том, какие условия, параметры или части кодов позволяют восстанавливать их однозначно или, например, с точностью до эквивалентности. Один из естественных подходов к восстановлению кодов заключается в использовании их метрических свойств. Ситуация выглядит нетривиальной, поскольку наличие изометрии между кодами не гарантирует их задания в объемлющем пространстве даже с точностью до эквивалентности. Примером служат коды Адамара: хотя все эти коды изометричны друг другу, среди них имеются неэквивалентные. Здесь вопрос о восстановлении выступает как проблема метрической жёсткости кодов, разрешённая для отдельных классов кодов [1]. Напомним, что код называется метрически жёстким, если любая изометрия, определённая на вершинах кода, продолжается до изометрии всего пространства.

В качестве инвариантов для восстановления кода с некоторой степенью точности рассматривались также: граф минимальных расстояний между кодовыми вершинами [2]; множество вершин на заданном расстоянии p друг от друга [3]; треугольники, построенные на кодовых вершинах, и соответствующие им тройки попарных расстояний [4].

Одним из наиболее сильных инвариантов оказался [5] набор размерностей подкодов двоичного кода, где под размерностью Dim(C) кода C понимается размерность минимальной грани булева куба, содержащей код. Впоследствии удалось уточнить [6], что для восстаРабота выполнена при поддержке РФФИ (проект № 10-01-00424), а также ФЦП Научные и научно-педагогические кадры инновационной России на 2009–2013 гг. (гос. контракт № 02.740.11.0429).

4 Тезисы 43-й молодежной школы-конференции новления двоичного кода с точностью до эквивалентности достаточно знать размерности его подкодов лишь чётной мощности. Точнее, эти размерности позволяют найти размерности всех остальных подкодов.

Пусть C приведённый двоичный код мощности k длины n.

Упорядочим векторы из {0} Ek-1 некоторым образом и обозначим 0,..., 2k-1 количество столбцов соответствующего вида в прове-рочной матрице кода C с нулевой верхней строкой. Зная размерности 2 подкодов чётной мощности кода C, можно составить Ck + Ck +... = = 2k-1 - 1 уравнений, связывающих величины 1,..., 2k-1. В до-полнение имеем равенство для числа нулевых столбцов 0 = n Dim(C). В результате получаем квадратную систему линейных уравнений для i. Результаты статьи [6] показывают, что эта система имеет единственное решение и, тем самым, невырожденна.

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

Одним из объектов, близких к кодам, для которого исследование восстановимости весьма актуально, является граф. Проблема изоморфизма графов является ориентиром в этом направлении. Колодой графа G называется мультимножество {G - v | v V (G)}, где G - v подграф графа G, полученный удалением вершины v и инцидентных ей рёбер. Известная гипотеза Улама о том, что колода графа определяет его с точностью до изоморфизма, доказана для отдельных классов графов [7]. Аналогичная гипотеза о рёберной восстановимости графа также является открытой, см., например, [8].



Литература [1] Августинович С.В., Соловьёва Ф.И. К метрической жесткости двоичных кодов // Пробл. передачи информ. 2003. Т. 39, № 2.

С. 23–28.

Алгебра [2] Могильных И.Ю. О слабых изометриях кодов Препараты // Пробл. передачи информ. 2009. Т. 45, вып. 2. С. 78–83.

[3] Красин В.Ю. О слабых изометриях булева куба // Дискретн.

анализ и исслед. операций. Сер. 1. 2006. Т. 13, № 4. С. 26–32.

[4] Абдурахманов Ж.К. О геометрической структуре кодов, исправляющих ошибки: Дис.... канд. физ.-мат. наук: 01.01.09. Ташкент, 1991.

[5] Августинович С.В. О сильной изометрии бинарных кодов // Дискретн. анализ и исслед. операций. Сер. 1. 2000. Т. 7, № 3.

С. 3–5.

[6] Горкунов Е.В., Августинович С.В. О восстановлении двоичных кодов по размерностям их подкодов // Дискретн. анализ и исслед. операций. 2010. Т. 17, № 5. С. 15–21.

[7] Kelly P.J. A congruence theorem for trees // Pacific Journal of Mathematics. 1957. Vol. 7. Pp. 961–968.

[8] Ramachandran S. Graph reconstruction – some new developments // AKCE Journal of Graphs and Combinatorics. 2004. Vol. 1, № 1. Pp. 51–61.

6 Тезисы 43-й молодежной школы-конференции ОБ АВТОМОРФИЗМАХ ДИСТАНЦИОННО РЕГУЛЯРНОГО ГРАФА С МАССИВОМ ПЕРЕСЕЧЕНИЙ {19,16,8;1,2,8} Белоусов И.Н.

Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины a графа через i(a) обозначим iокрестность вершины a, то есть подграф, индуцированный на множестве всех вершин, находящихся на расстоянии i от a. Положим [a] = 1(a), a = {a} [a].

Пусть граф, a, b, число вершин в [a] [b] обозначается через µ(a, b) (через (a, b)), если a, b находятся на расстоянии (смежны) в. Далее, индуцированный [a] [b] подграф называется µ-подграфом (-подграфом). Если граф диаметра d, то через i, где i d, обозначается граф с тем же множеством вершин, что и, в котором две вершины смежны тогда и только тогда, когда они находятся на расстоянии i в.

Если вершины u, w находятся на расстоянии i в, то через bi(u, w) (через ci(u, w)) обозначим число вершин в пересечении i+1(u) (i-1(u)) с [w]. Граф диаметра d называется дистанционно регулярным с массивом пересечений {b0, b1,..., bd-1; c1,..., cd}, если значения bi(u, w) и ci(u, w) не зависят от выбора вершин u, w на расстоянии i в для любого i = 0,..., d. Положим ai = k - bi - ci.

Заметим, что для дистанционно регулярного графа b0 это степень графа, c1 = 1. Для подмножества X автоморфизмов графа через Fix(X) обозначается множество всех вершин графа, неподвижных относительно любого автоморфизма из X.

Граф называется рёберно симметричным, если его группа автоморфизмов действует транзитивно на множестве его дуг (упорядоченных ребер).

В работе [1] найдены массивы пересечений дистанционно регулярных локально циклических графов с числом вершин, не большим 1000.

Предложение. Пусть является дистанционно регулярным графом диаметра, большего 2, на v 1000 вершинах. Если = 2 и µ > 1, то верно одно из утверждений:

Алгебра (1) примитивный граф с массивом пересечений {15, 12, 6; 1, 2, 10}, {19, 16, 8; 1, 2, 8}, {24, 21, 3; 1, 3, 18}, {35, 32, 8; 1, 2, 28}, {51, 48, 8; 1, 4, 36};

(2) антиподальный граф с µ = 2 и массивом пересечений {2r + 1, 2r - 2, 1; 1, 2, 2r + 1}, r {3, 4,..., 21}\{10, 16} и v = 2r(r + 1);

(3) антиподальный граф с µ 3 и массивом пересечений {15, 12, 1; 1, 4, 15}, {18, 15, 1; 1, 5, 18}, {27, 24, 1; 1, 8, 27}, {35, 32, 1; 1, 4, 35}, {45, 42, 1; 1, 6, 45}, {42, 39, 1; 1, 3, 42}, {75, 72, 1; 1, 12, 75}.

Предполагается исследование рёберно симметричных графов с такими массивами пересечений. Окрестность вершины в таком графе является объединением изолированных многоугольников. В данной работе изучаются автоморфизмы гипотетического дистанционно регулярного графа с массивом пересечений {19, 16, 8; 1, 2, 8}.

Теорема. Пусть дистанционно регулярный граф, имеющий массив пересечений {19, 16, 8; 1, 2, 8}, G = Aut(), g элемент из G простого порядка p и = Fix(g). Тогда (G) {2, 3, 19} и верно одно из утверждений:

(1) пустой граф и либо (i) p = 3, 3(g) = 60r, 2(g) = 20r + 50l - 20 и 1(g) = 180-80r - 50l, либо (ii) p = 2, 3(g) = 24r и 2(g) = 8r + 20l;

(2) || = 1, p = 19, 1(g) = 19 и 2(g) = 152;

(3) || > 1, p = 2 и либо (i) 3(g) = 0 и || 123, либо (ii) 3(g) = 0 и || 87.

Следствие. Пусть дистанционно регулярный граф с массивом пересечений {19, 16, 8; 1, 2, 8} и G = Aut(). Тогда |G| равен 2·19 или 2 · 3, 4, в частности, граф не является рёберно симметричным.

Литература [1] Буриченко В.П., Махнев А.А. О вполне регулярных локально циклических графах / в сб. Современные проблемы математики, тезисы 42-й Всероссийской молодежной конференции.

C. 181–183. Екатеринбург: ИММ УрО РАН, 2011.

8 Тезисы 43-й молодежной школы-конференции О СТРОЕНИИ КОНЕЧНЫХ ЦИКЛИЧЕСКИХ ПОЛУКОЛЕЦ Бестужев А.С.

Полукольцом называется алгебраическая структура S, +, · с двумя бинарными операциями: сложением + и умножением ·, для которых S, + коммутативная полугруппа с нейтральным элементом 0, S, · полугруппа с нейтральным элементом 1 и a(b + c) = ab + ac, (a + b)c = ac + bc, 0 · a = 0 = a · 0 для любых a, b, c S [1].

(Мультипликативно) циклическим полукольцом называется полукольцо, все элементы которого, кроме нуля и единицы, являются натуральными степенями некоторого образующего элемента a (a = и a = 1), нуль же может являться, а может и не являться степенью элемента a; считаем, что a0 = 1.





Cтроение бесконечных циклических полуколец известно и определяется одним из законов сложения: am +an = amin{m,n}; am + an = = amax{m,n}.

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

Элемент x полукольца называется нильпотентным, если xn = для некоторого натурального числа n.

Теорема 1. Если в циклическом полукольце образующий a нильпотентен, то am+an = amin{m,n} для любых целых неотрицательных чисел m, n.

Теорема 2. Если в циклическом полукольце образующий элемент не является нильпотентным и сумма некоторых двух различных элементов равна нулю, то данное полукольцо является конечным полем.

Далее, обозначим через s сумму всех элементов конечного циклического полукольца с образующим a. Если s = 0, то по теореме получаем конечное поле. В случае s = 0 полукольцо будет устрое но так: элементы 0, 1, a, a2, a3,... ak-1, ak различные, ak = ak+1. В дальнейшем будем рассматривать только такие полукольца, а элемент ak будем называть поглощающим, так как ak в произведении с любым ненулевым элементом дает ak.

Алгебра Предложение 1. Сумма 1 + ak, где ak – поглощающий элемент, может принимать одно из двух значений: 1 или ak.

Сложение в случае 1 + ak = 1 описано в теореме 1. В случае 1 + ak = ak сумма любого элемента с элементом ak дает ak. Это значит, что поглощающий по умножению элемент ak будет еще и поглощающим по сложению.

Среди циклических полуколец существуют идемпотентные, в которых 1+1 = 1, и неидемпотентные, в которых 1+1 = am, где m > 0.

Аддитивная полугруппа циклических идемпотентных полуколец является верхней полурешеткой.

Далее рассматриваются только неидемпотентные циклические полукольца S = {0, 1, a, a2,..., ak}, где ak = ak+1 поглощающий элемент.

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

Введем обозначения. Запись al,...,l+r означает, что на месте al,...,l+r может находиться любой из элементов al, al+1,..., al+r.

Пусть дано полукольцо с поглощающим элементом ak, где k = = m + n + p + 1. При этом неотрицательные целые числа m, n, p таковы, что в полукольце выполняются равенства:

am + am+n = am+n+p;

() a0,...,k + am+n+1,...,k = am+1,...,k + am+n = ak.

Предложение 2. Если в полукольце выполняются равенства (), то p > m.

Теорема 3. Возможен один из следующих четырех случаев:

1) n - 1 < m;

2) n - 1 m, p > n - 1;

3) n - 1 m, p n - 1, 1 + 1 = an+1...k;

4) n - 1 m, n - 1 p + m, 1 + 1 = an.

Для первых трех случаев получены формулы, описывающие строение всех таких полуколец. Для четвертого случая строение полукольца зависит от значения сумм 1 + a0,...,m. Зная значения сумм 1 + a,..., 1 + am, можно указать точные значения сумм 1+ +an+1,..., 1 + an+m, a + an,..., am + an. Чтобы убедиться в том, что 10 Тезисы 43-й молодежной школы-конференции данная структура (для четвертого случая) является полукольцом, нужно проверить справедливость равенств:

1 + (aq + al) = (1 + aq) + al = (1 + al) + aq.

Теорема 4. Пусть неотрицательные целые числа t и r такие, что t + r < m + 1. Тогда:

1) 1 + at = an+t тогда и только тогда, когда 1 + an+t = at + an = +an+t+p;

2) 1 + at = an+t+r тогда и только тогда, когда 1 + an+t = = 1 + an+t+r = at + an = at+r + an = an+t+r+p;

3) 1 + an+t = an+m+1,...,k тогда и только тогда, когда 1 + an+t = = at + an = ak.

Предложение 3. Если для какого-то элемента at (0 < t < m + 1) выполняется равенство 1 + at = an+t, то для всех таких k, что kt < m + 1, верно 1 + akt = an+kt.

Следствие 1. Если 1+a = an+1, то 1+a2 = an+2,..., 1+am = an+m.

Литература [1] Golan J.S. Semirings and Their Applications. Dordrecht–Boston– London: Kluwer Academic Publishers, 1999.

Алгебра НЕЗАВИСИМЫЕ СЛОВА В СИММЕТРИЧЕСКИХ И ЗНАКОПЕРЕМЕННЫХ ГРУППАХ Бородина Е.В.Определение. Рассмотрим некоторое множество слов V в алфавите X. Слово v называется независимым относительно V в алфавите X, если для любого w V невозможна ситуация w = pvq, где p и q – некоторые слова и по крайней мере одно из них непусто.

При компьютерном моделировании конечных бернсайдовых групп B(2, 3), B(2, 4), B(3, 3), B0(2, 5) использование независимых слов в алфавите образующих существенно сокращало время расчета указанных групп, что было связано с тем обстоятельством, что таблица умножения, состоящая из независимых слов, содержала все элементы группы, в то время как само количество независимых слов приблизительно равнялось |G|, где G – одна из перечисленных выше групп.

В работе [1] эти два факта были подтверждены для некоторых симметрических групп малых степеней. Кроме того, выяснилось, что количество независимых слов зависит от выбора образующих. В связи с этим возникает задача о минимальном количестве независимых слов для данной группы и поиска образующих группы, которое это минимальное количество обеспечивают. В моей работе данная задача решена для групп S5 и A5. Указанное число независимых слов для группы S5 равно 15, где a – инволюция, a b – элемент порядка 5. Для группы A5 это число равно 14, где a и b – элементы порядка 5.

Литература [1] Бородина Е.В. Независимые слова в симметрических группах / в сб. Студент и научно-технический прогресс, труды XLIX Международной научной студенческой конференции. С. 6. Новосибирск: НГУ, 2011.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 38 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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