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

Объект исследования и разработки - программное средство, предназначенное для поиска полинома Жегалкина частично определенных булевых функций. Цель работы - разработка исследовательского комплекса минимизации полинома Жегалкина частично определенных булевых функций, то есть необходимо разработать комплекс, решающий задачу формирования минимального полинома Жегалкина по вектору значений булевой функции методом частных полиномиальных нормальных форм (ЧПНФ).В ходе работы над работой сформулирована постановка задачи, проведен обзор аналогичных решений, рассмотрено программное обеспечение для создания программного средства и разработки приложений. На этапе проектирования ПС разработана структура функциональных блоков, составлен укрупненный алгоритм работы ПС. Программное средство разработано в среде Microsoft Visual Studio 2012, версия Microsoft Visual C# 2012 Express Edition. Составлено руководство пользователю по работе с ПС, указаны технические условия, порядок запуска программы, последовательность работы с экранной формой.

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

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

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

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

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

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

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

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

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

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

Логическая функция - это сложное высказывание, состоящее из нескольких простых, связанных между собой соединительными союзами. Она записывается аналитически в виде Y = f(x1,x2, ..., xn), где хі- двоичная переменная, хі I{ 0,1}; YI{0,1 }.

Частично определенная функция - это логическая функция, значения которой определены не на всех входных наборах. На тех входных наборах, где функция не определена, проставляется прочерк (или любой другой символ, отличный от 0 и 1) [2].

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

Алгоритм поиска минимальной дизъюнктивной нормальной формы (ДНФ) частично определенной функции f можно представить следующим образом: - найти любым известным способом сокращенную ДНФ функции, получающейся доопределением единицами исходной функции f на всех неопределенных наборах;

- выбрать минимальную ДНФ по импликантной матрице, где в столбцах выписаны лишь те конституенты единицы функции f, которые соответствуют полностью определенным единичным наборам.

Аналогичный алгоритм (с доопределением нулевыми наборами) может быть предложен для поиска конъюнктивной нормальной формы (КНФ). При этом доопределение таблицы истинности функции f может быть произведено по-разному для КНФ и ДНФ.

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

Известно, что любую булеву функцию можно представить полиномом Жегалкина (полиномом по модулю 2), и это представление с точностью до перестановки слагаемых единственно. Приведем некоторые наиболее известные способы построения такого полинома [3].

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

Метод преобразования произвольной формулы алгебры логики состоит в следующем: сначала строим ДНФ или КНФ БФ, а затем формируем полином Жегалкина, используя известные соотношения

.

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

Преобразуем логическую формулу :

Таким образом, полином Жегалкина для данной функции имеет вид .

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

Метод неопределенных коэффициентов состоит в следующем [4]: записываем булеву функцию в виде полинома Жегалкина с неопределенными коэффициентами. Приравниваем значения функции к значениям полинома на соответствующих наборах переменных и находим неизвестные коэффициенты. На значениях исходной функции строим треугольник Паскаля, складывая каждый раз соответствующие значения функции по модулю 2. Тогда числа на левой стороне полученного треугольника определяют коэффициенты полинома Жегалкина при монотонных конъюнкциях, соответствующих наборам переменных. Напомним, что элементарная конъюнкция называется монотонной, если она не содержит отрицаний переменных. Константа 1 (т. е. элементарная конъюнкция нулевого ранга) считается по определению монотонной конъюнкцией.

Теперь воспользуемся методом неопределенных коэффициентов. Для этого запишем нашу функцию в виде многочлена с неопределенными коэффициентами: , где A, B, C, D, E, F, G, H ?{0,1}.

Таблица истинности нашей функции выглядит следующим образом: Таблица 1.1 - Таблица истинности функции x y z x?y y xz y?xz (x?y)(y?xz)

0 0 0 0 1 0 1 0

0 0 1 0 1 0 1 0

0 1 0 1 0 0 0 0

0 1 1 1 0 0 0 0

1 0 0 1 1 0 1 1

1 0 1 1 1 1 1 1

1 1 0 1 0 0 0 0

1 1 1 1 0 1 1 1

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

Решая систему, получим коэффициенты равные: H=0, G=0, F=0, D=0, E=1, C=0, B=1, A=1. Подставляя найденные значения A, B, C, D, E, F, G, H в формулу

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

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

Для реализации метода зададим исходную функцию набором значений f(x,y,z)=(00001101). На строке значений функции построим треугольник Паскаля, представленный на рисунке 1.1, складывая попарно по модулю 2 соседние значения функции.

Рисунок 1.1 - Треугольник Паскаля

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

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

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

Метод минимизации логических функций с помощью карт Карно заключается в следующем: на карту Карно наносятся единичные и нулевые значения логических функций. Для получения ДНФ логической функции рассматриваются единичные значения функции, а для получения КНФ - нулевые.

Пусть с помощью карты Карно задана логическая функция , необходимо найти ее тупиковую ДНФ. Тогда задача минимизации решается следующим образом: среди единичных значений логической функции , предварительно нанесенных на карту Карно, отыскиваются прямоугольники и/или квадраты с числом клеток , где k=(n-1),…,0. Выделяемые прямоугольники и/или квадраты могут пересекаться между собой.

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

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

Импликанты - это элементарные конъюнкции ранга меньше максимального, которые не могут быть склеены (т.е. объединены) между собой.

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

Если необходимо найти тупиковую КНФ логической функции , то задача минимизации решается следующим образом: среди нулевых значений логической функции , предварительно нанесенных на карту Карно, отыскиваются прямоугольники и/или квадраты с числом клеток , где k=(n-1),…,0. Выделяемые прямоугольники и/или квадраты могут пересекаться между собой.

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

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

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

Минимизируем с помощью данного метода логическую функцию , СДНФ которой определяется соотношением:

(1.1)

Построим для функции карту Карно (рисунок 1.2). ab c 00 01 11 10

0 1 1 1 0

1 1 0 1 1

Рисунок 1.2 - Карта Карно функции

Определим максимальный размер прямоугольника, которым можно покрыть клетки карты. Величина прямоугольников вычисляется как , где k=(n-1),(n-2),…,0, а n - число аргументов, от которых зависит логическая функция. В нашем случае n=3, следовательно, максимальный размер прямоугольника равен = =4. В карте Карно нет прямоугольника, состоящего из четырех единиц, стоящих рядом, поэтому объединять клетки карты можно только по две, например так, как показано на рис. 1.3.

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

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

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

Рисунок 1.3 - Карта Карно функции

Объединяя знаком дизъюнкции найденные из каждого прямоугольника импликанты, получаем тупиковую ДНФ функции :

(1.2)

Объединить клетки карты Карно можно и другим образом (рисунок 1.3),

Рисунок 1.4 - Карта Карно функции тогда получим еще одну тупиковую ДНФ, реализующую функцию (1.3):

(1.3)

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

Пусть не полностью определенная логическая функция R(a,b,c,d) задана с помощью карты Карно (рисунок 1.5).

Рисунок 1.5 - Карта Карно логической функции R(a,b,c,d)

Для представления функции R(a,b,c,d) в виде минимальной ДНФ целесообразно следующее доопределение логической функции (рисунок 1.6):

Рисунок 1.6 - Доопределенная карта Карно логической функции R(a,b,c,d)

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

Рисунок 1.7 - Карта Карно логической функции R(a,b,c,d)

В результате минимизации получим минимальную ДНФ логической функции R(a,b, c,d):

(1.4)

Сравнение эффективности минимизированных форм часто проводят по способу Шеннона. Этот способ базируется на введении такого понятия как цена схемы - Ц. Цену схемы можно рассчитать по следующей формуле:

, (1.5) где - количество входов у j-ого элемента, i-количество элементов.

Пусть логическая функция R(a,b,c,d) задана в виде СДНФ (1.6):

(1.6)

Оценим минимальную ДНФ логической функции R(a,b, c,d) (1.5): Элементов “И” в выражении присутствует 5 (два элемента “И” по 2 входа, три элемента “И” по 3 входа), элементов “ИЛИ”- 1 (один элемент на 5 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно: Ц=2*2 3*3 1*5 4*1=22 входа

Тем же способом оценим СДНФ логической функции R(a,b,c,d) - выражение (1.6): Элементов “И” - 11 (одиннадцать элементов по 4 входа), элементов “ИЛИ”- 1 (один элемент на 11 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно: Ц=11*4 1*11 4*1=59 входов.

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

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

Как уже было сказано, частичной называется булева функция, значения которой заданы лишь на некоторых наборах, образующих в совокупности область определения функции. Предположим, что на всех остальных наборах значения рассматриваемой функции могут быть любыми - их можно определить произвольно. Если число таких наборов равно k, то существует 2k различных доопределений функции и каждому из них соответствует свой полином Жегалкина. Из практических соображений возникает задача выбора среди них, самого простого, с минимальным числом конъюктивных термов.

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

Совокупность значений функции, определяемых на k безразличных наборах, представляется булевым k - вектором. Значения этого вектора перебираются по коду Грея, введенному первоначально для представления натуральных чисел. При этом, как и в случае двоичного позиционного кода, представляются числа меньшие, чем 2k, начиная с 0.

В соответствии с кодом Грея, значения вектора, кодирующие число 0, составляется из нулей, а каждое последующее получается из предыдущего изменения значения в одном разряде - самом младшем (правом) из тех, которые обеспечивают получение еще не использованной комбинации [2].

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

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

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

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

Несмотря на огромное множество языков программирования, лишь немногие из них получили широкую известность и признание программистов. Для того, что бы определить самые популярные языки программирования воспользуемся данными голландской компании «TIOBE Software BV» в первую очередь известной своим регулярно рассчитываемым рейтингом популярности языков программирования. Результаты рейтинга представлены на рисунке 1.8.

Рисунок 1.8 - Популярность языков программирования за 2014 год

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

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

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

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

Java - язык программирования, разработанный компанией SUNMICROSYSTEMS. Приложения Java обычно компилируются в специальный байт-код, поэтому они могут работать на любой виртуальной Java-машине(JVM) независимо от компьютерной архитектуры. Дата официального выпуска - 23 мая 1995 года. Сегодня технология Java предоставляет средства для превращения статических Web-страниц в интерактивные динамические документы и для создания распределенных не зависящих от платформы приложений.

Программы на Java транслируются в байт-код, выполняемый виртуальной машиной Java (JVM) -программой, обрабатывающей байтовый код и передающей инструкции оборудованию как интерпретатор.

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

Часто к недостаткам концепции виртуальной машины относят то, что исполнение байт-кода виртуальной машиной может снижать производительность программы алгоритмов, реализованных на языке Java. В последнее время был внесен ряд усовершенствований, которые несколько увеличили скорость выполнения программ на Java: - применение технологии трансляции байт-кода в машинный код непосредственно во время работы программы (JIT-технология) с возможностью сохранения версий класса в машинном коде, - широкое использование платформенно - ориентированного кода (native-код) в стандартных библиотеках, - аппаратные средства, обеспечивающие ускоренную обработку байт-кода (например, технология Jazelle, поддерживаемая некоторыми процессорами фирмы ARM).

Основные возможности языка: - автоматическое управление памятью;

- расширенные возможности об работки исключительных ситуаций;

- богатый набор средств фильтрации ввода/вывода;

- набор стандартных коллекций, таких как массив , список , стек и т.п.;

- наличие простых средств создания сетевых приложений (в том числе с использованием протокола RMI);

- наличие классов, позволяющих выполнять HTTP-запросы и обрабатывать ответы;

- встроенные в язык средства создания многопоточных приложений;

- унифицированный доступ к базам данных: - на уровне отдельных SQL-запросов-на основе JDBC,SQLJ;

- на уровне концепции объектов, обладающих способностью к хранению в базе данных-на основе Java Data Objects и Java Persistence API;

- поддержка шаблонов (начиная с версии 1.5);

- параллельное выполнение программ [6].

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

В июне 2000 года стало известно о новом языке программирования, родившемся в недрах компании Microsoft. Он стал частью новой технологии Microsoft, названной .NET (читается «Dot Net»). В рамках этой технологии предусмотрена единая среда выполнения программ (Common Language Runtime, CLR), написанных на разных языках программирования. Одним из таких языков, основным в этой среде, и является C# (C#, читается «C sharp», «Си шарп»). Названием языка, конечно же, хотели подчеркнуть его родство с Си , ведь # - это два пересекшихся плюса. Но больше всего новый язык похож на Java . И нет сомнений, что одной из причин его появления стало стремление Microsoft ответить на вызов компании Sun.

Хотя официально авторы C# не называются, но на титульном листе одной из предварительных редакций справочника по языку обозначены Андерс Хейльсберг (Anders Hejlsberg) - создатель Турбо Паскаля и Дельфи, перешедший в 1996 году в Microsoft, и Скотт Вилтамут (Scott Wiltamuth).

Единая среда выполнения программ основана на использовании промежуточного языка IL (Intermediate Language - промежуточный язык), исполняющего почти ту же роль, что и байт-код виртуальной машины языка Ява. Используемые в рамках технологии .NET компиляторы с различных языков транслируют программы в IL-код. Так же как и байт-код Явы, IL-код представляет собой команды гипотетической стековой вычислительной машины. Но есть и разница в устройстве и использовании IL.

Во-первых, в отличие от JVM, IL не привязан к одному языку программирования. В составе, предварительных версий Microsoft.NET имеются компиляторы с языков Си , C#, Visual Basic. Независимые разработчики могут добавлять другие языки, создавая компиляторы с этих языков в IL-код.

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

«C# - простой, современный, объектно-ориентированный язык с безопасной системой типов, происходящий от Си и Си . C# будет удобен и понятен для программистов, знающих Си и Си . C# сочетает продуктивность Visual Basic и мощность Си .» Такими словами начинается описание C#.

Рассмотрим технические особенности языка: - единицей компиляции является файл (как в Си, Си , Яве). Файл может содержать одно или несколько описаний типов: классов (class), интерфейсов (interface), структур (struct), перечислений (enum), типов-делегатов (delegate) с указанием (или без указания) об их распределении по пространствам имен;

- пространства имен (namespace) регулируют видимость объектов программы (как в Си ). Пространства имен могут быть вложенными. Разрешено употребление объектов программы без явного указания пространства имен, которому этот объект принадлежит. Достаточно лишь общего упоминания об использовании этого пространства имен в директиве using (как в Турбо Паскале). Предусмотрены псевдонимы для названий пространств имен в директиве using (как в языке Оберон);

- элементарные типы данных: 8-разрядные (sbyte, byte), 16-разрядные (short, ushort), 32-разрядные (int, uint) и 64-разрядные (long, ulong) целые со знаком и без знака, вещественные одиночной (float) и двойной (double) точности, символы Unicode (char), логический тип (bool, не совместим с целыми), десятичный тип, обеспечивающий точность 28 значащих цифр (decimal);

- структурированные типы: классы и интерфейсы (как в Яве), одномерные и многомерные (в отличие от Явы) массивы, строки (string), структуры (почти то же, что и классы, но размещаемые не куче и без наследования), перечисления, несовместимые с целыми (как в Паскале);

- типы-делегаты или просто «делегаты» (подобны процедурным типам в Модуле-2 и Обероне, указателям на функции в Си и Си );

- типы подразделяются на ссылочные (классы, интерфейсы, массивы, делегаты) и типы-значения (элементарные типы, перечисления, структуры). Объекты ссылочных типов размещаются в динамической памяти (куче), а переменные ссылочных типов являются, по сути, указателями на эти объекты. В случае типов-значений переменные представляют собой не указатели, а сами значения. Неявные преобразования типов разрешены только для случаев, когда они не нарушают систему безопасности типов и не приводят к потере информации. Все типы, включая элементарные, совместимы с типомobject, который является базовым классом всех прочих типов. Предусмотрено неявное преобразование типов-значений к типу object, называемое упаковкой (boxing), и явное обратное преобразование - распаковка (unboxing);

- автоматическая сборка мусора (как в Обероне и Яве);

- обширный набор операций с 14 уровнями приоритета. Переопределение операций (как в Алголе-68, Аде, Си ). С помощью операторов checked и unchecked можно управлять контролем переполнения при выполнении операций с целыми;

- методы с параметрами значениями, параметрами-ссылками (ref) и выходными параметрами (out). Слова ref и out нужно записывать перед параметром не только в описании метода, но и при вызове. Наличие выходных параметров позволяет контролировать выполнение определяющих присваиваний. По правилам языка любая переменная должна гарантированно получить значение до того, как будет предпринята попытка ее использования;

- управляющие операторы: if, switch, while, do, for, break, continue (как в Си, Си и Яве). Оператор foreach, выполняющий цикл для каждого элемента «коллекции», несколько разновидностей оператора перехода goto;

- обработка исключений (как в Яве);

- свойства - элементы классов (объектов), доступ к которым осуществляется так же, как и к полям (можно присвоить или получить значение), но реализуется неявно вызываемыми подпрограммами get и set (как в Объектном Паскале - входном языке системы Delphi);

- индексаторы - элементы классов (объектов), позволяющие обращаться к объектам так же, как к массивам (указанием индекса в квадратных скобках). Реализуются неявно вызываемыми подпрограммами get и set. Например, доступ (для чтения) к символам строки может выполняться как к элементам массива благодаря тому, что для стандартного класса string реализован индексатор;

- события - элементы классов (поля или свойства) процедурного типа (делегаты), к которым вне класса, где они определены, применимы только операции = и -=, позволяющие добавить или удалить методы-обработчики событий для объектов данного класса;

- небезопасный (unsafe) код, использующий указатели и адресную арифметику, локализуется в частях программы, помеченных модификатором unsafe;

- препроцессор, предусматривающий, в отличие от Си и Си , только средства условной компиляции [8].

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

Сравнивая C# с Явой, можно увидеть много общих черт. Правда, если Ява-системы многоплатформны, то реализация C# существует пока только для операционной системы Windows и только одна. Но, несмотря на тяжеловесность, можно ожидать, что язык будет реализован и для других систем. Кроме того, сама платформа Microsoft .NET с единой средой выполнения программ может быть продвинута на альтернативные архитектуры, в первую очередь на UNIX-системы.

C# представляется более реалистичным языком, чем Ява. В отличие от Явы, он самодостаточен. То есть на C# можно написать любую программу, не прибегая к другим языкам. Это возможно благодаря наличию «небезопасных» блоков кода, которые открывают доступ непосредственно к аппаратуре. В языке Ява для доступа к средствам низкого уровня должны использоваться «родные методы» (native methods), которые необходимо программировать на других языках.

И, разумеется, перспективы C# в первую очередь связаны с теми усилиями, которые, конечно же, приложит компания Microsoft для его продвижения [8].

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

Eclipse - свободная интегрированная среда разработки модульных кроссплатформенных приложений. Развивается и поддерживается Eclipse Foundation .

Наиболее известные приложения на основе Eclipse Platform - различные «Eclipse IDE » для разработки ПО на множестве языков (например, наиболее популярный «Java IDE», поддерживавшийся изначально, не полагается на какие-либо закрытые расширения, использует стандартный открытый API для доступа к Eclipse Platform).

Eclipse служит в первую очередь платформой для разработки расширений, чем он и завоевал популярность: любой разработчик может расширить Eclipse своими модулями. Уже существуют Java Development Tools (JDT), C/C Development Tools (CDT), разрабатываемые инженерами QNX совместно с IBM, и средства для языков Ada (GNATBENCH, Hibachi), COBOL, FORTRAN, PHP, X10 (X10DT) и пр. от различных разработчиков. Множество расширений дополняет среду Eclipse диспетчерами для работы с базами данных, серверами приложений и др.

Eclipse JDT (Java Development Tools) - наиболее известный модуль, нацеленный на групповую разработку: среда интегрирована с системами управления версиями - CVS , GIT в основной поставке, для других систем (например,Subversion , MS SOURCESAFE ) существуют плагины. Также предлагает поддержку связи между IDE и системой управления задачами (ошибками). В основной поставке включена поддержка трекера ошибок Bugzilla , также имеется множество расширений для поддержки других трекеров (Trac , Jira и др.). В силу бесплатности и высокого качества, Eclipse во многих организациях является корпоративным стандартом для разработки приложений.

Eclipse написана на Java, потому является платформо-независимым продуктом, за исключением библиотеки SWT, которая разрабатывается для всех распространенных платформ (см. ниже). Библиотека SWT используется вместо стандартной для Java библиотеки Swing . Она полностью опирается на нижележащую платформу (операционную систему), что обеспечивает быстроту и натуральный внешний вид пользовательского интерфейса, но иногда вызывает на разных платформах проблемы совместимости и устойчивости приложений.

Основой Eclipse является платформа расширенного клиента (RCP - от англ. rich client platform). Ее составляют следующие компоненты: - ядро платформы (загрузка Eclipse, запуск модулей);

- OSGI (стандартная среда поставки комплектов (англ. bundles));

- SWT (портируемый инструментарий виджетов );

- JFACE (файловые буферы, работа с текстом , текстовые редакторы );

- рабочая среда Eclipse (панели, редакторы, проекции, мастеры);

- GUI в Eclipse написан с использованием инструментария SWT.

Последний, в отличие от Swing (который самостоятельно эмулирует графические элементы управления), использует графические компоненты данной операционной системы. Пользовательский интерфейс Eclipse также зависит от промежуточного слоя GUI, называемого JFACE, который упрощает построение пользовательского интерфейса, базирующегося на SWT.

Гибкость Eclipse обеспечивается за счет подключаемых модулей , благодаря чему возможна разработка не только на Java, но и на других языках, таких как /C , Perl , Groovy , Ruby , Python , PHP , Erlang , Компонентного Паскаля ,Zonnon и прочих [6].

Microsoft Visual Studio - линейка продуктов компании Microsoft , включающих интегрированную среду разработки программного обеспечения и ряд других инструментальных средств. Данные продукты позволяют разрабатывать как консольные приложения , так и приложения с графическим интерфейсом , в том числе с поддержкой технологии Windows Forms , а также вебсайты , веб-приложения , веб-службы как в родном , так и в управляемом кодах для всех платформ, поддерживаемых Windows , Windows Mobile , Windows CE , .NET Framework , Xbox , Windows Phone .NET Compact Framework и Silverlight .

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

Visual Studio позволяет создавать и подключать сторонние дополнения (плагины ) для расширения функциональности практически на каждом уровне, включая добавление поддержки систем контроля версий исходного кода (как например, Subversion и Visual SOURCESAFE ), добавление новых наборов инструментов (например, для редактирования и визуального проектирования кода напредметно-ориентированных языках программирования или инструментов для прочих аспектов процесса разработки программного обеспечения (например, клиент Team Explorer для работы с Team Foundation Server ) [9].

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

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

Что касается выбора среды разработки, то была выбрана среда Microsoft Visual Studio 2012, в частности, версия Microsoft Visual C# 2012 Express Edition, потому что она является свободно распространяемой. То есть, выбрав эту среду, мы получили возможность разработать наш модуль и приложение, не нарушив ни одного закона об авторском праве.

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

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

В [5] предложен алгоритм полиномиального преобразования БФ на основе метода частных полиномиальных нормальных форм (ЧПНФ). Метод заключается в формировании ПНФ БФ путем последовательного преобразования каждого минтерма СДНФ (совершенная дизъюнктивная нормальная форма) функции в ЧПНФ. Рассмотрим метод ЧПНФ подробнее.

Пусть логическая функция f(а, b, с) задана таблицей истинности, представленной в таблице 2.1, индексом i обозначен номер набора значений логических переменных.

Таблица 2.1 - Истинности логической функций f(а,b,с) i а b с f

0 0 0 0 1

1 0 0 1 1

2 0 1 0 1

3 0 1 1 0

4 1 0 0 0

5 1 0 1 0

6 1 1 0 1

7 1 1 1 0

Преобразуем каждый минтерм СДНФ функции f(а, в, с) в частные ПНФ - Bj, где , если известно, что и , для .

, , , , , .

Сведем полученные данные в таблицу 2.2.

Таблица 2.2 - Частные полиномиальные нормальные формы Bi

Ki ЧПНФ

1 с с а ас а а с Bi

1 1 1 1 1 1 1 1 B0

1 1 1 1 B1

1 1 1 1 B2

1 1 B3

1 1 1 1 B4

1 1 B5

1 1 B6

1 B7

В таблице 2.2 в первом столбце перечислены все возможные минтермы функции f(а, b, с) - Ki, а в первой строке указаны все возможные члены ПНФ той же функции. В остальных строках метками «1» отмечены те члены ПНФ, которые входят в частные ПНФ в соответствии с вычисленными выше ЧПНФ. Жирным шрифтом выделены те Bj, которые соответствуют единичным значениям функции f(а, b, с). Просуммируем по модулю 2 в символьном виде те ЧПНФ, которые соответствуют выделенным в таблице 2.2 минтермам логической функции. В результате, после раскрытия скобок и приведения подобных членов, получим

Тождественный результат с использованием данных таблицы 2.2 может быть получен путем суммирования по модулю 2 двоичных векторов Bj, соответствующих выделенным минтермам, что иллюстрируется в таблице 2.3.

Таблица 2.3 - Частные полиномиальные нормальные формы Bj

Ki ЧПНФ

1 000 с 001 b 010 bc 011 а 100 ас 101 ab 110 abc 111 Bi

000 1 1 1 1 1 1 1 1 B0

001 1 1 1 1 B1

010 1 1 1 1 B2

011 1 1 B3

100 1 1 1 1 B4

101 1 1 B5

110 1 1 B6

111 1 B7

1 0 0 1 1 0 1 0 B

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

Анализ данных таблицы 2.3 наглядно демонстрирует следующую закономерность: разряды двоичных векторов Bj принимают единичные значения только в том случае, если единичные значения переменных в номерах строк полностью входят в двоичные номера столбцов таблицы. Исключение составляет только вектор В0, все элементы которого равны 1.

Вскрытая закономерность позволяет автоматически формировать ПНФ функции без пред

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

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

На этапе проектирования ПС разработана структура функциональных блоков, составлен укрупненный алгоритм работы ПС. Программное средство разработано в среде Microsoft Visual Studio 2012, версия Microsoft Visual C# 2012 Express Edition.

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

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

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

- коэффициент изменения функциональных возможностей = 1,11;

- коэффициент цены потребления = 0,91;

- коэффициент технической прогрессивности = 1,72;

- затраты на разработку = 207204,00 руб.;

- продажная цена = 12014,92 руб.

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

1 Торопов Н.Р. Полиномиальная реализация частичных булевых функций и систем / Н.Р Торопов, А.Д. Закревский // Полиномы Жегалкина для частичных булевых функций. - 2006г. С. 27-29.

2 Акинина Ю.С. Разработка метода преобразования дизъюнктивных нормальных форм в полиномиальную нормальную форму // Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях: сборник трудов IX международной открытой научной конференции, 2004. - Вып. 9. С. 271.

3 Алехина М.А. Об одном методе построения полинома Жегалкина / М.А. Алехина, П.Г. Пичугина // Дискретная математика для инженера. - 2006. - N 2. - C. 49-51.

4 Автоматизация полиномиального разложения булевых функций на основе метода неопределенных коэффициентов / А. А. Акинин, Ю. С. Акинина, С. Л. Подвальный, С. В. Тюрин // Системы управления и информационные технологии, 2011. - Т. 44. - № 2. - С. 4-8.

5 Казимиров А.С. Исследование полиномиальных представлений одной последовательности булевых функций / А.С. Казимиров // Дискретные модели в теории управления систем: VII Международная конференция, Покровское, 4-6 марта, 2006 г.: Труды. - М.: МАКС Пресс, 2006. - С. 139-141.

6 Википедия: Язык программирования Java / Режим доступа : https://ru.wikipedia.org/wiki/Java

7 C# "От и до" / Режим доступа : http://cppp.ucoz.ru/publ/c/s/dostoinstva_jazyka/12-1

8 Майкрософт : Операторы С# / Режим доступа : https://msdn.microsoft.com/ru-ru/library/6a71f45d.aspx

9 Майкрософт : Среда разработки Visual Studio / Режим доступа : http://msdn.microsoft.com/vstudio Visual Studio 2012.

10 Наролина Т.С. Технико-экономические обоснование дипломных проектов: учеб. пособие / Т.С. Наролина. - Воронеж: ВГТУ, 2009. - 123 с.

11 ГОСТ 12.0.003-74 Опасные и вредные производственные факторы. Классификация.

12 Асташкин В.П. ,Безопасность и экологичность: методические указания к выполнению раздела “Безопасность и экологичность” в дипломном проекте для студентов всех специальностей и всех форм обучения: Учеб. Пособие/ В.П. Асташкин, Н.В. Мозговой, О.А. Семенихин - Воронеж. : ГОУВПО “Воронежский государственный технический университет.,2011. -25 с.

Размещено на .ru