• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМА ШИФРОВАНИЯ, ОСНОВАННОГО НА 2W – КОНЕЧНЫХ АВТОМАТАХ

ФИО студента: Водянова Ольга Владимировна

Руководитель: Шапошников Дмитрий Евгеньевич

Кампус/факультет: Факультет информатики, математики и компьютерных наук (Нижний Новгород)

Программа: Магистратура

Год защиты: 2014

<p>В данной работе будут рассмотрены так называемые дважды бесконечные языки, слова и автоматы (2&omega;), а также будет реализована попытка разработки алгоритма шифрования, основанного 2 &omega;-конечных автоматах и его исследование.</p><p>В <strong>первой главе</strong> даны основные определения для конечных автоматов и языков, краткая их характеристика и основные операции и теоремы, сформулированные мною по аналогии, но уже для дважды бесконечных автоматов и языков.</p><p>Во первом и втором пунктах <strong>второй главы</strong> я обратилась к регулярным выражениям и их реализации для 2-омега автоматов, а также была рассмотрена теорема Клини в контексте дважды бесконечного случая. В 3 и 4 пунктах мною выведены определения детерминированным и бидетерминированным автоматам, а также на примере разобрано их построение для данного случая, дано сравнение с построениями для конечного автомата. Мною выделены различия и особенности. В остальных пунктах 2 главы (5 и 6) получены определения для канонического 2<em>w</em> автомата и аналога функции разметки состояний. Приведены примеры их построения для 2<em>w</em> автомата.</p><p>В <strong>3 главе</strong> работы была реализована попытка разработки, построения исследования алгоритма шифрования, основанного на свойствах 2-омега-конечных автоматах.</p><p>В <strong>выводе</strong> показано, что заданная цель была достигнута. Достаточно большое количество примеров, таблиц и иллюстрация делает материал весьма наглядным и удобным для использования. К сожалению, алгоритм весьма прост, а изменение набора операций влечет за собою потерю информации.</p><p>Четко сформулированные определения и теоремы для 2&omega; случаев найти весьма затруднительно. Применение же их на практике остается весьма туманным и, скорее, именно теоретическим. Поэтому <strong>целью</strong> данной работы являлась попытка найти, разработать и построить некий алгоритм шифрования, имеющий в своей&nbsp;&nbsp;&nbsp;&nbsp; основе свойства дважды бесконечных автоматов.</p><p>Здесь будут рассмотрены некоторые примеры автоматов, даны определения и некоторые теоремы, относящиеся к дважды бесконечным вычислениям. Различные варианты их комбинаций и видоизменений, которые могут помочь достичь поставленной цели.</p><p>Передо мной стояли следующие <strong>задачи</strong>:</p><ul><li style="margin-left: 71.45pt;">Изучить поведение 2w-автоматов при различных преобразованиях и их комбинациях;</li><li style="margin-left: 71.45pt;">Рассмотреть полученные результаты на конкретных примерах;</li><li style="margin-left: 71.45pt;">Выявить, насколько полученные действия обратимы или обнаружить некий алгоритм преобразования состояний</li><li style="margin-left: 71.45pt;">Если отличия не найдены, сделать соответствующие выводы;</li><li style="margin-left: 71.45pt;">Испробовать различные виды операций и их последовательности;</li><li style="margin-left: 71.45pt;">Определить, какие операции и комбинации дают нам некий результат, поддающийся преобразованию к изначальному (расшифровке);</li><li style="margin-left: 71.45pt;">На основе полученных сведений разработать алгоритм шифрования;</li><li style="margin-left: 71.45pt;">Провести исследование алгоритма на предмет надежности и стабильности получаемого результата.</li></ul><p><strong>Актуальность </strong>представленной работы состоит в том, что эта крайне малоисследованная область теории автоматов и языков трансляций. Довольно немногие имеют представление о том, каким образом будут выглядеть уже привычные нам определения, теоремы и автоматы для случая дважды бесконечных автоматов. Эта область представляет собой большой интерес в будущем. В частности, для разработки больших программных объектов, серьезных проектов для исследования, к примеру, окружающего мира, объяснения процессов вселенной, изобретения многих важных систем, разработка над которыми ведется уже многие годы, но пока с переменным успехом или лишь на уровне теории. Наиболее важным вопросом явилось практическое приложение и его поиск. В данной работе как вариант представлена возможность создания алгоритма шифрования на основе дважды бесконечных автоматов, что само по себе весьма интересно.</p><p><strong>Новизна</strong> работы в том, что на текущий момент практического применения теории 2-омега-конечных автоматов попросту нет. Работа является попыткой выявления путей приложения теории в такой важной и крайне интересной области, как шифрование данных.&nbsp;</p>

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

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

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

Реестр дипломов НИУ ВШЭ