WWW.DISS.SELUK.RU

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

 

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ

М.В.ЛОМОНОСОВА

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

УДК 519.71

Мастихина Анна Антоновна

ЧАСТИЧНОЕ ПРЕДВОСХИЩЕНИЕ СВЕРХСОБЫТИЙ

АВТОМАТАМИ.

01.01.09 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

МОСКВА 2012

Работа выполнена на кафедре математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М.В.Ломоносова.

Научный руководитель доктор физико-математических наук, профессор Гасанов Эльяр Эльдарович

Официальные оппоненты Подловченко Римма Ивановна, доктор физико-математических наук, профессор, Научно-исследовательский вычислительный центр Московского государственного университета имени М.В.Ломоносова, ведущий научный сотрудник Лялин Илья Викторович, кандидат физико-математических наук, Элайн Технолоджи, старший разработчик

Ведущая организация Российский государственный гуманитарный университет (РГГУ)

Защита диссертации состоится 8 июня 2012 г. в 16 ч. 45 мин. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М.В.Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

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

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ, д.ф.-м.н., профессор Иванов А.О.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

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

Понятие автомата с предвосхищением появилось еще в начале развития теории автоматов1. Такой автомат использует в своей работе не только данные, уже поступившие на вход, но и некоторые значения, которые должны поступить в будущем. Используя эти значения, можно существенно ускорить работу устройства, а в случае, если предполагаемый символ не совпал с поступившим на вход на самом деле, происходит откат алгоритма, и выигрыша во времени не случается.

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

Также можно использовать для предсказания некоторую информацию о строении последовательности. Например, если она порождена некоторой 1 Трахтенброт Б.А., Бардзин Я.М. Конечные автоматы (поведение и синтез) // М.: Наука, 2 Hutter M. Optimality of Universal Bayesian Sequence Prediction for General Loss and Alphabet// Journal of Machine Learning Research N.4. 2003. Pp. 971-1000.

формальной грамматикой. Наиболее популярны регулярные3 и контекстносвободные грамматики4, они используются в языках программирования и относительно просты для разбора.

В статье А.Г.Вереникина и Э.Э.Гасанова5 были введены угадывающие автоматы конечные автоматы, угадывающие сверхслово или множество сверхслов. Это значило, что через некоторое конечное время после начала подачи сверхслова автомат начинает угадывать каждый следующий символ, то есть на выходе в момент времени t выдавать элемент входной последовательности с номером t + 1. Было показано, что угадываемы только множества периодических сверхслов.

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

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

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



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

3 Maurel D., Pevedic B. The syntactic prediction with token automata: application to HandiAS system // Theoretical Computer Science. 2001. Vol. 267, Issue 1-2. Pp.121-129.

4 Wiles J., Elman J. L. Learning to count without a counter: A case study of dynamics and activation landscapes in recurrent networks. // Proceedings of the Seventeenth Annual Conference of the Cognitive Science Society. - MIT Press. - 1995. - Pp.

482Џ487.

5 Вереникин А.Г., Гасанов Э.Э. Об автоматной детерминизации множеств сверхслов // Дискретная математика.

2006. Т.18, №2. C. 84–97.

6 Мастихина А.А. О частичном угадывании сверхслов // Интеллектуальные системы. 2007. Т.11, вып.1-4 С.609Цель работы. Цель работы состоит в нахождении критериев, позволяющих определить, является ли некоторое сверхсобытие частично угадываемым. В случае положительного ответа необходимо построить автомат, угадывающий данное сверхсобытие с как можно большей степенью.

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

Научная новизна.

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

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

2. Получен критерий частичной угадываемости сверхитераций языков, порожденных простыми LL(1)-грамматиками. Для частично угадываемых сверхсобытий строится угадывающий алгоритм, реализуемый автоматом с магазинной памятью. Частичная угадываемость рассматривается в смысле верхнего и нижнего пределов доли верно предсказанных символов. Критерии и алгоритмы для этих двух случаев различаются.

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

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

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

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

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

Рассмотренные машины, реализующие алгоритмы угадывания детерминированные автоматы представляются естественными для этой цели.

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

Допустимы обобщения, такие как подсчет средней доли угадывания во всем множестве, а также комбинации с вероятностным подходом.

Результаты могут быть использованы в программировании при создании оптимизирующих компиляторов. Регулярные и LL(1)-грамматики широко распространены в этой области, так как они обладают широкими выразительными возможностями, но при этом достаточно просты для распознавания. Угадывающие автоматы могут иметь широкое применение при синтезе чипов для обработки интенсивных потоков данных, поскольку в этих устройствах без предсказания поступающих последовательностей невозможно добиться нужной производительности.

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

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

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

Конференция студентов, аспирантов и молодых ученых мех-мат. ф-та МГУ (2008, Москва).

Международная конференция "Современные проблемы математики, механики и их приложений", посвященная 70-летию академика В.А.Садовничего (2009, Москва).

Международная конференция студентов, аспирантов и молодых ученых "Ломоносов"(2009, 2010, 2011, 2012, Москва). Доклады на конференциях "Ломоносов-2010", "Ломоносов-2011" и "Ломоносов-2012" были отмечены грамотами за лучший доклад.

Международный семинар "Дискретная математика-2010" (2010, Москва).

54-ая научная конференция МФТИ "Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе"(2011, Москва-Долгопрудный-Жуковский).

Х Международная конференция "Интеллектуальные системы и компьютерные науки" (Москва, 2011).

Также результаты докладывались на семинарах механикоматематического факультета МГУ им. М.В.Ломоносова: на семинаре "Теория автоматов" под руководством академика, проф., д.ф-м.н. В.Б.

Кудрявцева (2011 г.), на семинаре "Вопросы сложности алгоритмов поиска" под руководством проф., д.ф-м.н. Э.Э.Гасанова (2006-2011 гг.), на семинаре МИАН и ВЦ по теории сложности под руководством член-корр., д.ф-м.н. А.А.Разборова (2011 г.), на семинарах факультета ВМиК МГУ им. М.В.Ломоносова: на семинаре "Дискретная математика и математическая кибернетика" под руководством проф., д.ф-м.н. В.Б.Алексеева, проф., д.ф-м.н. А.А.Сапоженко, проф., д.ф-м.н. С.А.Ложкина (2011 г.), на семинаре "Теоретические проблемы программирования" под руководством проф., д.ф-м.н. Р.И.Подловченко, д.ф-м.н. В.А.Захарова (2012 г.).

Публикации. По теме диссертации опубликовано 10 работ, список которых приведен в конце автореферата [1-10].

Структура и объем работы. Диссертация состоит из введения и глав. Объем диссертации 95 страниц. Список литературы содержит 25 наименований.

ОСНОВНЫЕ ПОНЯТИЯ

Будем рассматривать класс детерминированных, но, возможно, бесконечных автоматов M.

Через y обозначим выходное сверхслово некоторого автомата A при подаче на его вход сверхслова. Детерминированность автомата означает, что после подачи на его вход t первых символов сверхслова он однозначно выдает некоторый выходной символ y (t).

Если {0, 1}, то обозначим Автомат A угадывает сверхслово {0, 1} с (нижней) степенью [0, 1], если A угадывает сверхслово {0, 1} с верхней степенью [0, 1], если Величины cA () и cA () будем называть соответственно степенью угадывания (предвосхищения) и верхней степенью угадывания сверхслова автоматом A.

Автомат A частично угадывает множество сверхслов A (частично угадывает в смысле верхнего предела), если > 0, такое что A выполнено cA() > > 0 (cA () > > 0). Множество A частично угадываемо, если найдется частично угадывающее его A M.

Степень угадывания множества A Также будут рассматриваться автоматы без выходов A = (A, Q,, q0 ).

Автомат A = (A, Q,, q0 ) допускает сверхсобытие R с помощью выделенного множества семейств состояний F 2Q, если R тогда и только тогда, когда множество состояний, проходимых автоматом бесконечное число раз при подаче на его вход сверхслова, есть элемент F.

В любом автомате можно выделить сильно связные компоненты Q1,..., Qk, то есть совокупности состояний, достижимых друг из друга:

Назовем сильно связную компоненту замкнутой, если из нее не достижима никакая другая сильно связная компонента.

нетерминальных символов (НС), T множество терминальных символов, S N аксиома, P множество правил вывода) находится в нормальной форме Грейбах, если все правила имеют вид A aB1...Bk, где B1,...Bk N, a T, или A a, или S, где символ для обозначения пустого слова. Причем, если грамматика простая LL(1), для каждого нетерминального символа есть не более |T | правил (с разными терминальными символами). Любую грамматику можно привести к нормальной форме Грейбах (то есть найти грамматику в нормальной форме Грейбах, порождающую тот же язык)7. Причем простая LL(1)-грамматика при приведении к нормальной форме Грейбах остается простой LL(1).

Символ A достижим из символа B, если найдутся такие T, Символ грамматики A называется достижимым, если найдутся такие T, (T N ), что S A. Иначе символ называется недостижимым.

Нетерминальный символ A называется тупиковым, если не найдется такого слова T, что A.

7 Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции: Пер. с англ. М.: Мир, 1978.

Далее будем рассматривать грамматики в нормальной форме Грейбах и считать, что недостижимые и тупиковые символы отсутствуют. Также будем считать, что аксиома не встречается в правой части правил. Будем тогда говорить, что грамматика находится в нормальной форме.

Автомат с магазинной памятью это семерка (Q,,, Z,, q0, F ), где Q множество состояний, входной алфавит, магазинный алфавит, Z символ для обозначения пустого магазина, q0 Q выделенное начальное состояние, F Q множество заключительных состояний, множеотображение (Q ( ) Q ).

ство команд, каждая команда Конфигурацией будем называть пару (q, ), q Q, : текущее состояние и содержимое магазина.

Автомат работает потактово. Такт работа автомата после поступения одного символа. Считаем, что -такт выполняется мгновенно.

Автомат называется детерминированным, если для каждой конфигурации (q, ) имеется либо не более одной команды вида (q, a, ]1 r, ), q, r Q,, для каждого a и ни одной команды вида (q,, ] r, ), r Q,, либо ни одной команды вида (q, a, ]1 r, ) и не более одной вида (q,, ]1 r, ).

СОДЕРЖАНИЕ РАБОТЫ

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

Пусть B () множество всех автоматов, угадывающих сверхслово со степенью не меньшей.

Обозначим через (A) число состояний автомата A и введем минимальное число состояний автомата, угадывающего сверхслово со степенью, не меньшей.

Пусть A(n) множество сверхслов с периодом n.

Теорема 1. 1) Если = 1, то для любого n N и любого A(n) выполнено где m длина минимального периода сверхслова.

3) Если >, то для любого натурального n найдется такое периодическое сверхслово, что R () > n.

Теорема 2. Существует такое сверхслово, что ни один конечный автомат не угадывает его ни с какой степенью (0, 1].

Теорема 3. 1) Для любого 0, 1 существует сверхслово, которое угадывается любым конечным автоматом со степенью большей или равной.

автоматы угадывают его со степенью большей или равной.

Во второй главе рассматривается частичное угадывание общерегулярных сверхсобытий конечными автоматами.

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

Теорема 5. Пусть общерегулярное сверхсобытие R представимо в конечном инициальном автомате A = ({0, 1}, Q,, q0 ), |Q| = n с помощью некоторого F 2Q, тогда следующие утверждения эквивалентны.

1. Сверхсобытие R, R {0, 1}, не является частично угадываемым;

3. Хотя бы для одной замкнутой сильно связной компоненты Q автомата A выполнено Q F.

Теорема 7. Общерегулярное сверхсобытие R1 R1 R2 R2... Rk Rk, где R1, R2,..., Rk, R1, R2,..., Rk некоторые регулярные события, частично угадываемо тогда и только тогда, когда частично угадываемо каждое из сверхсобытий R1, R2,..., Rk.

Теорема 8. Пусть общерегулярное сверхсобытие L {0, 1} представимо в конечном инициальном автомате A = ({0, 1}, Q,, q0 ), |Q| = n с помощью некоторого F 2Q. Сверхсобытие L не является частично угадываемым тогда и только тогда, когда хотя бы для одной замкнутой сильно связной компоненты Q автомата A выполнено Q F.

Обозначим класс автоматов, отличающихся от A только добавлением функции выхода, (A) = {({0, 1}, Q, {0, 1},,, q0 ), : Q {0, 1}}.

Теорема 9. Рассмотрим общерегулярное множество L и автомат A = ({0, 1}, Q,, q0 ), принимающий это множество с помощью F 2Q, при этом Qi, Qj F, i = j выполнено Qi Qj =.

Тогда g M выполнено cg (L) maxA (A) cA (L).

Как следствие, возникает следующая теорема.

Теорема 10. Существует алгоритм, определяющий, является ли сверхсобытие L, представимое в приведенном автомате с n состояниями, частично угадываемым, и его сложность линейно зависит от n. Также существует алгоритм построения минимального автомата с наибольшей возможной степенью предвосхищения в случае, если сверхсобытие частично угадываемо.

В третьей главе рассматривается частичное угадывание сверхитераций простых LL(1)грамматик. Угадывание производится автоматами с магазинной памятью, отдельно рассмотрен случай нижней и верхней степеней.

Найдены оценки для степеней угадывания и грамматики, для которых эти оценки достигаются.

Теорема 11. Множество сверхслов, образованное сверхитерацией языка L(G), порожденного простой LL(1)-грамматикой G в нормальной форме, частично угадываемо в смысле нижней степени тогда и только тогда, когда хотя бы для одного нетерминального символа грамматики существует только одно правило вывода.

Обозначим за G(n, l) класс простых LL(1)-грамматик в нормальной форме с параметрами |N | = n и максимальной длиной команды (числом нетерминальных символов справа в команде) l.

За G0 (n, l) обозначим класс таких грамматик из G(n, l), для которых L(G) частично угадываемо.

Назовем правило грамматики регулярным, если оно имеет вид A aB (глубина стека соответствующего МП-автомата не увеличивается), A, B N. Назовем правило стирающим, если правило имеет вид A a (глубина стека уменьшается). Остальные правила назовем удлинняющими.

НС B достижим по регулярным правилам по слову из НС A, если существуют регулярные правила Если существует такое слово, то B достижим из A по регулярным правилам.

Назовем регулярной сильно связной компонентой R множество НС, попарно достижимых друг из друга по регулярным правилам.

Выходом из регулярной сильно связной компоненты R назовем правило для A R, не являющееся регулярным или имеющее вид A aB, где Опишем алгоритм D, разделяющий НС грамматики G = (N, {0, 1}, P, S) на классы следующим образом.

1-й шаг.

Рассмотрим регулярные сильно связные компоненты, все выходы из которых являются стирающими, занесем их в класс D1.

Далее удалим из грамматики НС из класса D1. То есть преобразуем грамматику G в грамматику G = (N, {0, 1}, P, S), где N = N \ D1, а P получается из P удалением правил, начинающихся с элементов D и вычеркиванием элементов D1 из правых частей других содержащих их правил.

Например, если D1 = {A}, то правило B aAC из P в P будет иметь вид B aC.

Пусть сделано i шагов.

Опишем (i + 1)-й шаг.

В грамматике G(i) рассмотрим сильно связные регулярные компоненты, все выходы из которых являются стирающими. Все НС из таких компонент занесем в класс Di+1.

Удалим из правил грамматики правила, начинающиеся с НС из класса Di+1, а также вычеркнем элементы Di+1 из других правил. Получившуюся грамматику назовем G(i+1).

Алгоритм останавливается, когда некоторый класс Dk оказывается пуст или на k-ом шаге объединение классов k Di есть множество всех НС N.

Теорема 13. Множество сверхслов L(G), где G = (N, {0, 1}, P, S) простая LL(1)-грамматика в нормальной форме, частично угадываемым в смысле верхней степени тогда и только тогда, когда после работы горитм D остановился.

Обозначим lmin (G) минимальная длина правила грамматики G.

Обозначим rc (G) наибольшую длину цепи регулярных правил в грамматике G(i), то есть наибольшее r, такое что существуют A1 a1 A2, A a2 A3,..., Ar ar Ar+1 P (i), причем A1,...Ar+1 попарно различны.

Rc (G) = maxi=0,...,k rc (G).

Обозначим за G(l, l, Rc ) класс простых LL(1)-грамматик G с параметрами lmin (G) = l, lmax (G) = l, Rc (G) = Rc.

За G0 (l, l, Rc ) обозначим класс таких грамматик из G(l, l, Rc ), которые являются частично угадываемыми.

GG(l,L,Rc ) AM где k номер шага, на котором алгоритм D, примененный к G, останавливается.

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

Теорема 15. Пусть язык L допускается детерминированным автоматом с магазинной памятью A = (Q, {0, 1},, Z,, q0, F ). Множество L является частично угадываемым тогда и только тогда, когда для некоторой пары (q, A), q Q, A существует только одна команда Рассмотрим класс детерминированных автоматов с магазинной памятью с m состояниями, n магазинными символами и максимальной длиной команды l (под длиной подразумевается число магазинных символов в правой части команды), каждый из которых допускает такой язык L, что L является частично угадываемым. Обозначим этот класс M (n, m, l). Пусть L(B) язык, допускаемый автоматом B.

Теорема 16. Для любых n, m, l 2 верно

БЛАГОДАРНОСТИ

Автор выражает глубокую благодарность своему научному руководителю профессору Гасанову Э.Э. за постановку задачи и помощь в работе, академику Кудрявцеву В.Б. за многочисленные полезные советы на всех этапах подготовки диссертации и всему коллективу кафедры математической теории интеллектуальных систем механико-математического факультета Московского государственного университета имени М.В.Ломоносова за теплую творческую атмосферу.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации автора по данной теме из списка ВАК:

1. Мастихина А.А. О частичном угадывании сверхслов // Интеллектуальные системы. 2007. Т.11, вып.1-4 С.609-619.

2. Мастихина А.А. Критерий частичного предвосхищения общерегулярных свехсобытий // Дискретная математика. 2011. Т.23, вып.4 С.103Мастихина А.А. Частичное угадывание сверхсобытий, порожденных простыми LL(1)-грамматиками // Интеллектуальные системы. 2011.

Т.15, вып.1-4 С.507-532.

Публикации не из списка ВАК:

4. Мастихина А.А. Частичное угадывание сверхсобытий, образованных детерминированными контекстно-свободными языками. Материалы X международной конференции "Интеллектуальные системы и компьютерные науки 2011. С.157-160.

5. Мастихина А.А. О частичном угадывании сверхслов. Международная конференция "Современные проблемы математики, механики и их приложений", посвященная 70-летию академика В.А.Садовничего (30 марта Џ апреля 2009 г., Москва). Материалы конференции. С. 365-366.

6. Мастихина А.А. Частичное угадывание регулярных выражений.

Международная конференция студентов, аспирантов и молодых ученых Ломоносов-2009њ (2009, Москва). С.45-46.

7. Мастихина А.А. О частичном угадывании регулярнх выражений.

Международный семинар "Дискретная математика-2010"(2010, Москва).

Издательство механико-математического факультета МГУ, Москва, 2010.

385-387.

8. Мастихина А.А. О частичном угадывании множеств сверхслов, заданных общерегулярными выражениями. Международная конференция студентов, аспирантов и молодых ученых "Ломоносов-2010"(2010, Москва).

9. Мастихина А.А. Частичное угадывание некоторых контекстносвободных языков. Международная конференция студентов, аспирантов и молодых ученых "Ломоносов-2011"(2011, Москва).

10. Мастихина А.А. Частичное предвосхищение множеств последовательностей. Труды 54-й научной конференции МФТИ (10-30 ноября, 2011).

Т.1. М.:МФТИ, 2011. С.60-61.





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

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

«Бубнов Николай Владимирович ИССЛЕДОВАНИЕ ВЗАИМОДЕЙСТВИЯ 1-АРИЛ-4-АРОИЛ-5МЕТОКСИКАРБОНИЛ-1H-ПИРРОЛ-2,3-ДИОНОВ С 1,3 CH,NH- и NH,NH-БИНУКЛЕОФИЛЬНЫМИ РЕАГЕНТАМИ Специальность 02.00.03 – Органическая химия Автореферат на соискание ученой степени кандидата химических наук Новосибирск - 2013 Работа выполнена на кафедре органической химии химического факультета Федерального государственного бюджетного образовательного учреждения высшего профессионального образования Пермский...»

«ВАН Чжэ Особенности восприятия русского художественного текста носителями русского и китайского языков (на материале рассказа А.П. Чехова Шуточка) Специальность 10.02.01 – русский язык Автореферат диссертации на соискание ученой степени кандидата филологических наук Москва 2012 Работа выполнена на кафедре русского языка филологического факультета Московского государственного университета имени М.В. Ломоносова Научный руководитель : доктор филологических наук, профессор...»

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

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

«Синдеев Михаил Сергеевич Исследование и разработка алгоритмов матирования видеопоследовательности Специальность 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Автореферат диссертации на соискание учёной степени кандидата физико-математических наук Москва – 2013 Работа выполнена в Институте прикладной математики им. М.В.Келдыша РАН. Научный руководитель : кандидат физико-математических наук, доцент Баяковский Юрий...»

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

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

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

«ШМАГИН Александр Николаевич Особенности защиты нарушенных или оспариваемых прав и законных интересов граждан в арбитражном судопроизводстве 12.00.15 – гражданский процесс; арбитражный процесс АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата юридических наук САРАТОВ – 2010 2 Работа выполнена в Государственном образовательном учреждении высшего профессионального образования Саратовская государственная академия права Научный руководитель доктор юридических наук,...»

«ВИКТОРОВА Наталья Александровна АНГЛИЙСКАЯ ЛИТЕРАТУРНАЯ СКАЗКА ЭПОХИ ПОСТМОДЕРНИЗМА Специальность 10.01.03 – Литература народов стран зарубежья (английская литература) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата филологических наук Казань - 2011 2 Работа выполнена на кафедре зарубежной литературы ФГОУ ВПО Казанского (Приволжского) федерального университета Министерства образования и науки Российской Федерации Научный руководитель - кандидат филологических...»

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

«РУМЯНЦЕВ ДМИТРИЙ ЕВГЕНЬЕВИЧ ДЕМОКРАТИЗАЦИЯ ОРГАНОВ ГОРОДСКОГО САМОУПРАВЛЕНИЯ В ПОВОЛЖЬЕ В 1917 ГОДУ: ИСТОРИКО-ПОЛИТИЧЕСКИЙ АНАЛИЗ Специальность 23.00.01 - Теория политики, история и методология политической наук и (по историческим наукам) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата исторических наук Казань-2006 2 Работа выполнена на кафедре истории и литературы Федерального государственного образовательного учреждения высшего профессионального образования...»

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

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

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

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

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

«Кольба Алексей Иванович Политическое управление конфликтами в регионах современной России Специальность 23.00.05 – Политическая регионалистика. Этнополитика Автореферат диссертации на соискание ученой степени доктора политических наук Саратов – 2013 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Кубанский государственный университет доктор социологических наук, доцент, главный Научный консультант :...»

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






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

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