WWW.OS.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Научные публикации
 


«О присуждении Масленниковой Марине Игоревне, гражданке Российской Федерации, ученой степени кандидата ...»

ЗАКЛЮЧЕНИЕ ДИССЕРТАЦИОННОГО СОВЕТА Д 004.006.04

на базе Федерального государственного бюджетного учреждения

науки Института математики и механики им. Н. Н. Красовского

Уральского отделения Российской академии наук, Федеральное

агентство научных организаций, по диссертации на соискание

ученой степени кандидата наук

аттестационное дело №

решение диссертационного совета от 14 октября 2015 г., протокол № 8

О присуждении Масленниковой Марине Игоревне, гражданке Российской Федерации, ученой степени кандидата физикоматематических наук.

Диссертация Идеальные языки и синхронизируемые автоматы по специальности 01.01.09 – дискретная математика и математическая кибернетика принята к защите 16 июня 2015 г., протокол № 4 диссертационным советом Д 004.006.04 на базе Федерального государственного бюджетного учреждения науки Института математики и механики им. Н. Н. Красовского Уральского отделения Российской академии наук, Федеральное агентство научных организаций, 620990, г. Екатеринбург, ул. С. Ковалевской, д. 16, приказы Министерства образования и науки РФ о создании диссертационного совета № 75/нк от 15.02.2013 и 298/нк от 03.06.2014.

Соискатель Масленникова Марина Игоревна 1989 года рождения.



В 2012 году окончила магистратуру Федерального государственного автономного образовательного учреждения высшего профессионального образования Уральский федеральный университет имени первого Президента России Б.Н.Ельцина (далее ФГАОУ ВПО УрФУ им. Б.Н.Ельцина ), г. Екатеринбург, по направлению Математика. Прикладная математика. В 2012-2015 годах обучалась в очной аспирантуре ФГАОУ ВПО УрФУ им. Б.Н.Ельцина. Работает преподавателем Специализированного учебно-научного центра ФГАОУ ВПО УрФУ им. Б.Н.Ельцина, младшим научным сотрудником лаборатории комбинаторной алгебры Института математики и компьютерных наук ФГАОУ ВПО УрФУ им. Б.Н.Ельцина.

Диссертация выполнена на кафедре алгебры и дискретной математики ФГАОУ ВПО УрФУ им. Б.Н.Ельцина.

доктор физико-математических наук, проНаучный руководитель фессор Волков Михаил Владимирович, заведующий кафедрой алгебры и дискретной математики Института математики и компьютерных наук ФГАОУ ВПО УрФУ им. Б.Н.Ельцина.

Официальные оппоненты:

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

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

Ведущая организация Федеральное государственное автономное образовательное учреждение высшего образования Казанский (Приволжский) федеральный университет, г. Казань, в своем положительном заключении, подписанном Аблаевым Фаридом Мансуровичем, доктором физикоматематических наук, профессором, заведующим кафедрой теоретической кибернетики Института вычислительной математики и информационных технологий КФУ, и утвержденном Нургалиевым Данисом Карловичем, доктором геолого-минералогических наук, профессором, проректором КФУ по научной деятельности, указала, что в диссертации развивается новый подход к исследованию идеальных языков, связанный с построением сильно связного автомата, для которого данный идеальный язык является языком синхронизирующих слов; все утверждения снабжены строгими подробными доказательствами, опирающимися на методы комбинаторики слов, теории автоматов, теории сложности вычислений и теории формальных языков. Указано, что диссертация представляет собой законченное научное исследование на актуальную тему, обладающее научной новизной и содержащее существенный вклад в решение задач, связанных с исследованиями идеальных языков, и удовлетворяет всем требованиям Положения о порядке присуждения ученых степеней, а ее автор достоин присуждения ученой степени кандидата физико-математических наук по специальности 01.01.09 – дискретная математика и математическая кибернетика.

Соискатель имеет 15 опубликованных работ, в том числе по теме диссертации опубликовано 10 научных работ общим объемом 8.64 усл. печ. л., в том числе 4 работы опубликованы в международных изданиях, включенных в перечень ВАК рецензируемых научных изданий для опубликования основных научных результатов диссертаций. Эти 4 работы оформлены в виде статей.

Наиболее значимые научные работы по теме диссертации:

1. Gusev V.V., Maslennikova M.I., Pribavkina E.V. Finitely generated ideal languages and synchronizing automata. // In J. Karhumki, A.Lepist, L.Zamboni a o (eds.) 9th Int. Conf. WORDS 2013. Lect. Notes Comp. Sci. Springer-Verlag, Berlin-Heidelberg. 2013. Vol. 8079. P. 143–154.

2. Gusev V.V., Maslennikova M.I., Pribavkina E.V. Principal ideal languages and synchronizing automata. // Fundamenta Informaticae. 2014. Vol. 132(1). P.

95–108.

3. Maslennikova M. Complexity of checking whether two automata are synchronized by the same language. // In H.Jrgensen, J.Karhumki, A.Okhotin u a (eds.) 16th Int. Workshop DCFS 2014. Lect. Notes Comp. Sci. Springer-Verlag, Berlin-Heidelberg. 2014. Vol. 8614. P. 306–317.





4. Maslennikova M., Rodaro E. Representation of (left) ideal regular languages by synchronizing automata. // In L. Beklemishev (Ed.) 10th Int. Comp. Sci. Symp. CSR

2015. Lect. Notes Comp. Sci. Springer-Verlag, Berlin-Heidelberg. 2015.

Vol. 9139. P. 325–338.

В указанных работах все основные результаты принадлежат диссертанту.

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

Из других 6 работ по теме диссертации 5 работ опубликованы в виде тезисов в материалах всероссийских и международных конференций, одна работа опубликована в виде статьи в материалах международной конференции.

На диссертацию и автореферат поступили следующие отзывы:

– Официального оппонента Гутермана А. Э., в отзыве которого подчеркнута актуальность темы диссертационной работы, отмечено, что совокупность полученных результатов об идеальных регулярных языках и связанных с ними конечных автоматах является новым крупным научным достижением в дискретной математике. Указано, что в диссертации решены открытые проблемы и предложены новые оригинальные методы их исследования. Отмечено, что автореферат достаточно полно и правильно отражает содержание диссертации.

Имеется замечание по поводу обозначений и опечаток.

– Официального оппонента Куликова А. С., в отзыве которого указано, что в диссертации рассматриваются актуальные задачи, связанные с многими теоретическими и практическими областями (теорией кодирования, теорией формальных языков и вычислений, ДНК-вычислениями и комбинаторикой на словах). Отмечено, что полученные в диссертации результаты лежат в русле основных направлений исследований теории сложности формальных систем и докладывались на международных и российских конференциях и семинарах.

Указано, что автореферат достаточно полно и правильно отражает содержание диссертации. Отмечены замечания по поводу опечаток, обозначений, неточностей в формулировках (замечание по поводу определения собственного фактора, сформулированное на странице 23, замечание по поводу описания алгоритма на странице 25), нумерации утверждений, несущественные замечания по поводу доказательств утверждения 3 и леммы 4.7, не влияющие на справедливость указанных утверждения и леммы.

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

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

по теме диссертации в рецензируемых научных изданиях за последние 5 лет:

1. Guterman A. E., Emov M. A. Monotone maps on diagonalizable matrices // Mathematical Inequalities and Applications. 2014. Vol. 17, №4.

P. 1441–1452.

2. LeRoy B. Beasley, Alexander E. Guterman, Yaroslav N. Shitov. The arctic rank of a Boolean matrix // Journal of Algebra. 2015. Vol. 433. P. 168–182.

3. Бахадлы Б.Р., Гутерман А.Э., Маркова О.В. Графы, определенные ортогональностью // Записки научных семинаров ПОМИ им. В.А.Стеклова Российской академии наук. 2014. Т. 428. С. 49–80.

4. Marianne Akian, Stephane Gaubert, Alexander Guterman. Tropical Cramer determinants revisited // American Mathematical Society, Contemporary Mathematicsю Amer. Math. Soc., Providence, RI. 2014. Vol. 616. P. 1–45.

5. G. Dolinar, A. Guterman, and J. Marovt. Monotone transformations on B(H) with respect to the left-star and the right-star partial order // Mathematical Inequalities and Applications. 2014. Vol. 17, №2. P. 573–589.

6. А.Э. Гутерман, О.В. Маркова, С.Д. Сочнев. Алгебра полумагических матриц и ее длина // Записки научных семинаров ПОМИ. 2013. Т. 419.

С. 52–77.

7. A. Guterman, R. Lemos, and G. Soares. Extremal case in Marcus-Oliveira conjecture and beyond // Linear and Multilinear Algebra. 2013. Vol. 61, №9.

P. 1206–1222.

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

по теме диссертации в рецензируемых научных изданиях за последние 5 лет:

1. Evgeny Demenkov, Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin.

New Lower Bounds on Circuit Size of Multioutput Functions // Theory of Computing Systems. 2015. Vol. 56, №4. P. 630–642.

2. Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin.

Lower Bounds for the Graph Homomorphism Problem // Proc. of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP).

Lect. Notes Comp. Sci. 2015. Vol. 9134, №2. P. 481–493.

3. Alexander S. Kulikov, Sergey Savinov, Evgeniy Sluzhaev. Greedy Conjecture for Strings of Length 4 // Proc. of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM). Lect. Notes Comp. Sci. 2015. Vol.

9133. P. 307–315.

4. Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with Infants: A General Approach to Solve Hard Partition Problems // Proc. of the 41st International Colloquium on Automata, Languages, and Programming (ICALP).

Lect. Notes Comp. Sci. 2014. Vol. 8572. P. 551-562.

5. Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Solving SCS for Bounded Length Strings in Fewer than 2n Steps // Information Processing Letters.

2014. Vol. 114, №8. P. 421–425.

В ведущей организации работает ряд известных специалистов в области дискретной математики: Аблаев Ф.М., Аблаев М.Ф., Гайнутдинова А.Ф., Хадиев Р.М., Хайруллин А.Ф. и др.

Среди публикаций работников ведущей организации по теме диссертации в рецензируемых научных изданиях за последние 5 лет:

1. F. Ablayev, M. Ablayev. Quantum hashing via -universal hashing constructions and classical ngerprinting // Lobachevskii Journal of Mathematics.

2015. Vol. 36, №2. P. 89–96.

2. K. Khadiev. Width hierarchy for k-OBDD of small width // Lobachevskii Journal of Mathematics. 2015. Vol. 36, №2. P. 178–183.

3. Ф. М. Аблаев, М. Ф. Аблаев, А. В. Васильев. Универсальное квантовое хэширование // Учён. зап. Казан. гос. ун-та. Физико-математические науки.

2014. Т. 156, №3. С. 7–18.

4. F. M. Ablayev, M. Ablayev. Quantum hashing via -universal hashing constructions and Freivalds’ ngerprinting schemas // Proc. DCFS 2014. Lect.

Notes Comp. Sci. 2014. Vol. 8614. P. 42–52.

5. F. M. Ablayev, A. Gainutdinova, K. Khadiev, A. Yakaryilmaz. Very narrow quantum OBDDs and width hierarchies for classical OBDDs // Proc. DCFS 2014.

Lect. Notes Comp. Sci. 2014. Vol. 8614. P. 53–64.

6. F. Ablayev, A. Vasiliev. Cryptographic quantum hashing. // Laser physics letters. 2014. Vol. 11, №2.

7. Ф. М. Аблаев, К. Р. Хадиев. Уточнение иерархии класса булевых функций, представимых в моделях k-OBDD ветвящихся программ // Изв. вузов.

Матем. 2013. №3. С. 56–61.

8. F. Ablayev, A. Vasiliev. Algorithms for quantum branching programs based on ngerprinting // International journal of software and informatics. 2013.

Vol. 7, №4. P. 485–500.

9. M. Ziatdinov. Using frequency analysis and Grover’s algorithm to implement known ciphertext attack on symmetric ciphers // Lobachevskii Journal of Mathematics. 2013. Vol. 34, №4. P. 313–315.

10. F. Ablayev, A. Vasiliev. Classical and quantum parallelism in the quantum ngerprinting method // Parallel Computing Technologies. Lect. Notes Comp.

Sci. 2011. Vol. 6873. P. 1–12.

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

– введена новая характеристика регулярного языка, являющегося идеалом, связанная с представлением языка синхронизируемыми автоматами и называемая синхронизационной сложностью;

– доказано, что дескриптивная сложность идеального языка может быть экспоненциально больше его синхронизационной сложности;

– разработан и обоснован полиномиальный алгоритм построения сильно связного минимального синхронизируемого автомата для главного идеального языка;

– разработан и обоснован алгоритм построения сильно связного синхронизируемого автомата, язык синхронизирующих слов которого совпадает с данным конечно порожденным идеалом;

– доказана PSPACE-полнота задачи проверки равенства языков синхронизирующих слов двух данных автоматов;

– доказана PSPACE-полнота задачи проверки того, что синхронизационная сложность данного языка не превосходит = 3 в случае четырехбуквенного алфавита и = 4 в случае двухбуквенного алфавита.

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

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

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

– в Санкт-Петербургском отделении Математического института им. В. А.

Стеклова РАН;

– в Институте математики им. С. Л. Соболева СО РАН;

– в Московском и Южно-Уральском государственных университетах;

– в Уральском и Казанском (Приволжском) федеральных университетах.

Оценка достоверности результатов исследования выявила:

– построенная теория строго обоснована с использованием известных математических фактов и утверждений с указанием первоисточников;

– установлены результаты, которые согласуются с опубликованными исследованиями других авторов, дополняют и усиливают некоторые из них;

– использованы современные методы теории автоматов, теории формальных языков и теории сложности вычислений.

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

В третьей главе диссертанту принадлежат доказательства всех основных утверждений, Е. В. Прибавкиной предложена идея конструкций из теорем 3.1 и 3.2, а В. В. Гусевым идея конструкции из теоремы 3.3. В пятой главе соискателю принадлежат все результаты, кроме теорем 5.1 и 5.2, которые принадлежат Э. Родаро, в текст диссертации они включены (без доказательства) для полноты изложения.

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

Диссертационный совет пришел к выводу о том, что диссертация представляет собой научно-квалификационную работу, которая соответствует критериям, установленным Положением о порядке присуждения ученых степеней, утвержденным постановлением Правительства Российской Федерации от 24 сентября 2013 г. № 842.

На заседании 14 октября 2015 года диссертационный совет принял решение присудить Масленниковой Марине Игоревне ученую степень кандидата физико-математических наук.

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

–  –  –



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

«УДК 330.65 И.Н. Тюкавкин* РАЗВИТИЕ МЕХАНИЗМА УПРАВЛЕНИЯ ИНФОРМАТИЗАЦИЕЙ ЭКОНОМИКИ РЕГИОНА НА СОВРЕМЕННОМ ЭТАПЕ В статье представлены механизмы информатизации регионального развития. Рассмотрены основные факторы, вопросы создания и развития сети информатизации, принципы и методы ее организации. Ключевые слова: региональное развитие, подсистема информатизации, ресурсы информатизации, резервы, нормирование, оптимизация, управление регионом. Современный этап функционирования и развития национальной...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ ОДЕССКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ имени И. И. МЕЧНИКОВА ИНСТИТУТ МАТЕМАТИКИ, ЭКОНОМИКИ И МЕХАНИКИ Т. С. Горячая ПОДХОДЫ К РЕШЕНИЮ ПСИХОЛОГИЧЕСКИХ ПРОБЛЕМ ЛИЧНОСТИ: СВЕТСКАЯ ПСИХОЛОГИЯ И ХРИСТИАНСКАЯ БОГОСЛОВСКАЯ МЫСЛЬ (ТЕОРЕТИЧЕСКИЙ КУРС) Монография ОДЕССА ОНУ УДК 159.923:23/28 ББК 88.3 Г716 Рекомендовано в печать Учёным советом ОНУ имени И. И. Мечникова. Протокол № 2 от 21 октября 2014 г. Рецензенты: С. А. Ставицкая – доктор психологических наук,...»

«Теплофизика и аэромеханика, 2010, том 17, № 4 УДК 532.5+519.63 Оптимизационное проектирование ротора гидротурбины по критериям эффективностьпрочность* Д.В. Банников, Д.В. Есипов, С.Г. Черный, Д.В. Чирков Институт вычислительных технологий СО РАН, Новосибирск E-mail: cher@ict.nsc.ru Система оптимизационного проектирования рабочего колеса гидротурбины [1] расширяется включением экономичных методик расчета потерь энергии во всей проточной части гидротурбины и напряженно-деформированного состояния...»

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

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ ХАРЬКОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ГОРОДСКОГО ХОЗЯЙСТВА Л.Н.Шутенко, В.П.Пустовойтов, Н.А.Засядько СТРОИТЕЛЬНАЯ МЕХАНИКА Краткий курс РАЗДЕЛ 1 СТАТИЧЕСКИ ОПРЕДЕЛИМЫЕ СТЕРЖНЕВЫЕ СИСТЕМЫ (для студентов строительных специальностей) Харьков – ХГАГХ 2003 Шутенко Л.Н., Пустовойтов В.П., Засядько Н.А. Строительная механика: Краткий курс / Раздел 1. Статически определимые стержневые системы (для студентов строительных специальностей). – Харьков: ХГАГХ, 2003 –...»

«УДК 343.148.27:639.382 ВЕТЕРИНАРНО-САНИТАРНАЯ ЭКСПЕРТИЗА МЯСА ПРИ СТРЕССАХ Исабаев А.Ж. к.в.н., доцент кафедры ветеринарной санитарии, Костанайский государственный университет имени А.Байтурсынова. В условиях промышленной технологии значительно возрастает физиологическая и нервная нагрузка на животных, снижаются их адаптационные возможности, увеличивается негативное воздействие стрессов. Поэтому при вынужденном убое животных со стрессовым синдромом или после перенесенных заболеваний, получают...»

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

«План лекции 1. Системный подход в экологии 2. Концепции окружающей среды 3. Адаптация как экологическая характеристика и эволюционный механизм 4. Экологические факторы 5. Аутэкология (экология организмов) 6. Демэкология (экология популяций) 7. Основные характеристики популяций и методы их изучения 8. Особенности развития популяций 9. Эйдэкология (экология видов) 10. Тест по лекции 2 1.Системный подход в экологии Система – это множество взаимосвязанных элементов, образующих определенную...»



 
2016 www.os.x-pdf.ru - «Бесплатная электронная библиотека - Научные публикации»

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