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

• Автор: Отпущенников, Илья Владимирович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Иркутск
• Количество страниц: 128 с. : ил.

Содержание
Введение

Глава 1. Пропозициональное кодирование формальных вычислительных моделей

1.1. Базовые понятия и определения.

1.2. Пропозициональное кодирование программ для формальных

вычислительных моделей

1.2.1. Механизмы преобразования в булевы уравнения ИАМпрограмм, вычисляющих дискретные функции .

1.2.2. Преобразования Цейтина.

1.3. Основные алгоритмы решения систем булевых уравнений .

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

Глава 2. Преобразование процедурных описаний дискретных функций в булевы уравнения

2.1. Описание проблемноориентированного языка ТА.
2.2. Интерпретация ТАпрограмм. Формирование пропозиционального кода алгоритма.
2.2.1. Базовые механизмы символьного исполнения ТАпрограмм .
2.2.2. Символьное исполнение основных операторов языка
2.2.3. Процедура декомпозиции сложных термов.
2.2.4. Преобразование операций над целыми числами .
2.3. Программный комплекс Тгапэа для преобразования алгоритмов вычисления дискретных функций в булевы уравнения
Глава 3. Результаты преобразования в булевы уравнения алгоритмов вычисления некоторых дискретных функций .
3.1. Преобразование в булевы уравнения некоторых криптографических функций
3.1.1. Преобразование в булевы уравнения алгоритма генератора ключевого потока шифра А51.
3.1.2. Преобразование в булевы уравнения алгоритма суммирующего генератора.
3.1.3. Преобразование в булевы уравнении алгоритма генератора Гиффорда
3.1.4. Преобразование в булевы уравнения алгоритма
3.1.5. Преобразование в булевы уравнения алгоритма хеширования 5
3.2. Исследование свойств дискретноавтоматных динамических
систем
3.3. Процедуры сведения оптимизационных задач с псевдобуле
выми ограничениями к задачам
3.3.1. Сведение к задач 01целочисленного линейного программирования.
3.3.2. Сведение к квадратичных задач о назначениях .
Заключение
Литература


Для описания алгоритмов вычисления дискретных функций разработан новый проблемно-ориентированный язык ТА, обладающий С-подоб-иым синтаксисом и оригинальной семантикой, которая обеспечивает построение систем булевых уравнений в процессе интерпретации ТА-программ Для преобразования ТА-программ в булевы уравнения разработаны новые алгоритмы и структуры данных. Все разработанные алгоритмы интегрированы в программный комплекс Transalg, с применением которого были построены новые пропозициональные коды ряда криптографических преобразований и оптимизационных задач с псевдобулевыми ограничениями. Достоверность результатов. Достоверность полученных в работе теоретических результатов обеспечивается строгостью производимых математических построений. Корректность алгоритмов и эффективность их практической реализации подтверждается результатами вычислительных экспериментов. Теоретическая и практическая значимость работы. Теоретическая значимость работы заключается в сформулированной общей методологии преобразования процедурных описаний дискретных функций в булевы уравнения, в принципиальной возможности применения разработанных методов к исследованию широкого класса дискретных функций. Практическая значимость состоит в завершенности представленного в работе подхода и в возможности его применения к исследованию различных дискретных систем, поведение которых описывается полиномиально вычислимыми дискретными функциями. Соответствие специальности. Работа относится к области анализа алгоритмов и является исследованием, цель которого состоит в обосновании и развитии методологии преобразования процедурных описаний дискретных функций в булевы уравнения. В диссертации представлен метод для осуществления таких преобразований, а также разработан проблемно-ориентированный язык программирования (язык ТА), предназначенный для описания алгоритмов вычисления дискретных функций. Семантика языка ТА обеспечивает эффективное построение булевых уравнений в процессе интерпретации ТА-программ. В диссертации разработаны и реализованы в виде программного комплекса (комплекс ТУапва^) алгоритмы, осуществляющие преобразование процедурных описаний, выполненных на языке ТА, в булевы уравнения. При помощи комплекса Тгапва^ построены пропозициональные коды ряда криптографических алгоритмов, а также некоторых задач дискретной оптимизации. Таким образом, материал диссертации соответствует как формуле специальности , так и пунктам 1, 2 из «Области исследований». Содержательная часть работы включает введение и три главы. Первая глава посвящена основам методологии преобразования в булевы уравнения процедур вычисления дискретных функций в контексте формальной вычислительной модели — двоичной машины с произвольным доступом к памяти (АМ). Описываются основные механизмы построения булевых уравнений по программе для двоичной ИЛМ. В разделе 1. В разделе 1. Цейтина — основной инструмент перехода от произвольных систем булевых уравнений к уравнениям в нормальных формах. В разделе 1. В разделе 1. Вторая глава содержит теоретическую основу механизмов преобразования процедурных описаний дискретных функций в булевы уравнения. В этой главе описаны все базовые алгоритмы и структуры данных, используемые в процессе таких преобразований. Здесь же представлена архитектура программного комплекса Тгапза^ и приведено описание основных его функциональных возможностей. В разделе 2. ТА), предназначенный для описания алгоритмов, вычисляющих дискретные функции, с целью их преобразования в булевы уравнения. Язык ТА является процедурным языком с блочной структурой и С-подобным синтаксисом. Каждый блок — это список инструкций ТА-программы. Программа на языке ТА представляет собой набор определений функций, а также объявлений и определений глобальных переменных и констант. В языке ТА реализованы все основные примитивные конструкции, характерные для процедурных языков программирования. Раздел 2. ТА-программ (семантике языка ТА). В соответствии с принятым подходом [] интерпретационная семантика языка ТА описывается через ввод в рассмотрение абстрактной машины языка ТА (ТА-мапгипы).