Общие сведения о булевых функциях

Пояснительная записка

 

Разработал А.Ю. Мальцев

Подпись, дата Инициалы, Фамилия

 

Зав. кафедрой С.Л. Подвальный

Подпись, дата Инициалы, Фамилия

 

Руководитель Ю.С. Акинина

Подпись, дата Инициалы, Фамилия

 

Консультанты: Т.С. Наролина

Подпись, дата Инициалы, Фамилия

 

О.А. Семенихин

Подпись, дата Инициалы, Фамилия

 

Нормоконтроль провёл О.Б. Кремер

Подпись, дата Инициалы, Фамилия

 

 

Воронеж

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

Факультет информационных технологий и компьютерной безопасности

(факультет)

Кафедра автоматизированных и вычислительных систем

Специальность 230101 Вычислительные машины, комплексы, системы и сети

Студент группы ВМ-101

(индекс группы)

Мальцев Андрей Юрьевич

 

ЗАДАНИЕ

 

на выпускную квалификационную работу

 

1.Тема дипломной работы «Разработка исследовательского комплекса минимизации полинома Жегалкина частично определенных булевых функций»

 

утверждена распоряжением по факультету № 1 от « 14 » января 2015 г.

 

2. Технические условия: Аппаратные средства: класс компьютера IBM PC/AT, монитор с разрешением не ниже 1024x768, ОЗУ 512 Mb; программные средства: ОС Microsoft Windows 7, среда разработки Microsoft Visual Studio 2012, версия Microsoft Visual C# 2012 Express Edition.

 

3. Содержание (разделы, графические работы, расчеты и проч.) Разделы:

1) Общие сведения о булевых функциях

2) Проектирование программного средства

3) Разработка программного обеспечения

4) Организационно-экономическая часть

5) Безопасность и экологичность

Демонстрационные плакаты:

1) ;

2) ;

3) Алгоритм работы программы;

4) Экранные формы программы;

5) Результаты тестирования;

6) Технико-экономические показатели.

 

4. План выполнения дипломной работы

с «16» марта 2015 г. по «05» июля 2015 г.

 

Название элементов проектной работы	%	Сроки	% выполн	Подпись рук., консульт.
Обзор методов и средств решения задачи				Акинина Ю.С.
Выбор инструментальной среды для разработки приложения				Акинина Ю.С.
Разработка приложения				Акинина Ю.С.
Организационно-экономическая часть				Наролина Т.С.
Безопасность и экологичность				Семенихин О.А.
Составление пояснительной записки				Акинина Ю.С.

Руководитель дипломной работы

Акинина Юлия Сергеевна

(подпись) (Фамилия, имя, отчество)

5. Дипломная работа закончен(а)

« » г (подпись дипломника)

6. Пояснительная записка и все материалы просмотрены

Оценка руководителя

 

Консультанты: Наролина Татьяна Станиславовна

(подпись) (Фамилия, имя, отчество)

Семенихин Олег Александрович

(подпись) (Фамилия, имя, отчество)

 

7. Допустить дипломника Мальцева А.Ю.

(фамилия, инициалы)

к защите дипломной работы в Государственной аттестационной комиссии (протокол заседания кафедры № 11 от « 19 » мая 2015 г.

 

8. Назначить защиту на «» июня 2015 г.

 

Заведующий кафедрой С. Л. Подвальный

(подпись) (Инициалы, фамилия)

Декан факультета С. М. Пасмурнов

(подпись) (Инициалы, фамилия)

Реферат

 

Пояснительная записка 99 страниц, 28 таблица, 23 рисунков, 12 источников.

Ключевые слова – полином Жегалкина, булевы функции, программное средство, дизъюнктивная нормальная форма.

Объект исследования и разработки – программное средство, предназначенное для поиска полинома Жегалкина частично определенных булевых функций.

Цель работы – разработка исследовательского комплекса минимизации полинома Жегалкина частично определенных булевых функций, то есть необходимо разработать комплекс, решающий задачу формирования минимального полинома Жегалкина по вектору значений булевой функции методом частных полиномиальных нормальных форм (ЧПНФ).

Метод исследования и аппаратура – персональный компьютер с операционной системой Microsoft Windows 7, среда разработки Microsoft Visual Studio 2012 (Microsoft Visual C# 2012 Express Edition).

Полученные результаты и их новизна – «Исследовательский комплекс минимизации полинома Жегалкина частично определенных булевых функций» - программное средство, которое осуществляет формирование полинома Жегалкина методом ЧПНФ. В программном модуле также реализована возможность формирования таблицы истинности булевой функции, ввода и коррекции числа аргументов булевой функции, предусмотрены различные режимы доопределения БФ, осуществлен вывод полученных результатов программы на экранную форму в структурированном виде.

 

Содержание

ЗАДАНИЕ.. 2

Реферат. 4

Введение. 8

1 Общие сведения о булевых функциях. 10

1.1 Частично определенные булевы функции. 10

1.2 Методы формирования полинома Жегалкина. 11

1.2.1 Преобразование произвольной формулы алгебры логики. 11

1.2.2 Метод неопределенных коэффициентов. 11

1.2.3 Метод минимизации полностью определенных логических функций с помощью карт Карно. 13

1.2.4 Метод минимизации полностью определенных логических функций с помощью карт Карно. 14

1.2.5 Метод минимизации частично определенных логических функций с помощью карт Карно. 18

1.3 Полиномы Жегалкина для частично определенных булевых функций 21

1.4 Обзор программных средств решения задачи. 21

1.4.1 Анализ современных языков и сред программирования. 21

1.4.2 Язык программирования Java. 23

1.4.3 Язык программирования C#. 25

1.4.4 Сравнение сред программирования. 29

1.4.5 Обоснование выбора средств для разработки программного продукта. 31

2 Проектирование программного средства. 33

2.1 Метод частных полиномиальных нормальных форм. 33

2.2 Модульная структура ПС.. 37

2.3 Алгоритм работы программного средства. 40

2.4 Описание синтаксиса ПС.. 44

3 Разработка программного обеспечения. 52

3.1 Разработка макета программного продукта. 52

3.2 Технические условия работы.. 53

3.3 Руководство пользователя. 53

3.4 Анализ работы программного средства. 59

4 Организационно-экономическая часть. 63

4.1 Обоснование необходимости и актуальности разработки программного продукта «Полиномиальное преобразования БФ на основе метода частных полиномиальных нормальных форм в полином Жегалкина». 63

4.2 Определение трудоемкости разработки программного продукта. 64

4.3 Определение состава исполнителей. 69

4.4 Расчет стоимости разработки программного продукта. 70

4.5 Расчет трудоемкости сопровождения ПС.. 75

4.6 Определение стоимости сопровождения ПС.. 78

4.7 Планирование цены ПП и прогнозирование прибыли. 78

4.8 Анализ конкурентоспособности и качества разрабатываемого программного средства. 79

4.8.1 Анализ технической прогрессивности разрабатываемого программного продукта. 80

4.8.2 Анализ изменения функциональных возможностей разрабатываемого программного продукта. 81

4.8.3 Анализ соответствия разрабатываемого программного продукта нормативам. 83

4.8.4 Анализ экономических параметров ПП.. 83

4.8.5 Оценка конкурентоспособности программного продукта. 85

4.9 Анализ технико-экономических показателей разработки и эксплуатации ПП 85

5 Безопасность и экологичность. 87

5.1 Безопасность в производственной среде. 87

5.2 Анализ опасных и вредных производственных факторов. 88

5.2.1 Параметры микроклимата. 88

5.2.2 Шум. 89

5.2.3 Освещение. 90

5.2.4 Электробезопасность. 91

5.3 Расчёт и проектирование средств защиты.. 92

5.4 Экологичность. 96

5.5 Пожарная безопасность. 97

Заключение. 99

Список литературы.. 100

 

Введение

 

На протяжении последних 20 лет в России, странах СНГ и особенно в дальнем зарубежье, ведутся научно-технические разработки по реализации логических преобразователей в электронной компонентной базе (ЭКБ) на основе представления реализуемых булевых функций в виде различных полиномиальных форм, среди которых в первую очередь выделяют полиномы Жегалкина и полиномы Рида-Маллера с фиксированной полярностью.

Теоретический интерес к полиномиальным формам булевых функций (БФ) обусловлен тем, что нахождение полиномиальной формы БФ относят к NP-трудным задачам [1], в связи с чем асимптотические вычислительная (О) и объемная (V) сложности алгоритмов полиномиального преобразования БФ имеют оценку порядка О(2ⁿ) и V(2ⁿ), где n - количество аргументов преобразуемой БФ. Асимптотические оценки вычислительной и объемной сложности характеризуют весь класс алгоритмов полиномиального преобразования БФ, подчеркивая то, что любой алгоритм из данного класса не может быть реализован быстрее чем за 2ⁿ шагов алгоритма, при этом потребуется более чем 2ⁿ бит (слов) памяти. Таким образом, теоретический интерес состоит в отыскании наилучших алгоритмов полиномиального преобразования БФ, ориентированных на практическую реализацию средствами вычислительной техники (программными или аппаратурными).

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

Целью данной работы является разработка исследовательского комплекса минимизации полинома Жегалкина частично определенных булевых функций, другими словами, необходимо разработать комплекс, решающий задачу формирования минимального полинома Жегалкина по вектору значений булевой функции методом частных полиномиальных нормальных форм (ЧПНФ).

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

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

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

В-третьих, необходимо проработать (детализировать, уточнить, определить типы данных) алгоритм программы. На данном этапе должна быть разработана схема алгоритма, а также, определена структура интерфейсной части будущей программы.

В-четвертых, проверить работоспособность программы на контрольных примерах.

Общие сведения о булевых функциях