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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

Логическая функция — это сложное высказывание, состоящее из нескольких простых, связанных между собой соединительными союзами. Она записывается аналитически в виде Y = f (x₁, x₂, …, x_n), где х_i— двоичная переменная, х_i { 0,1}; Y{0,1 }.

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

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

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

— найти любым известным способом сокращенную ДНФ функции, получающейся доопределением единицами исходной функции f на всех неопределенных наборах;

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

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

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

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

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

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

.

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

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

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

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

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

Теперь воспользуемся методом неопределенных коэффициентов. Для этого запишем нашу функцию в виде многочлена с неопределенными коэффициентами:

где A, B, C, D, E, F, G, H ?{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)=(1 101). На строке значений функции построим треугольник Паскаля, представленный на рисунке 1.1, складывая попарно по модулю 2 соседние значения функции.

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

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

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

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

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

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

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

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

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

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

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

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

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

(1.1)

Построим для функции карту Карно (рисунок 1.2).

Рисунок 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, то существует 2^k различных доопределений функции и каждому из них соответствует свой полином Жегалкина. Из практических соображений возникает задача выбора среди них, самого простого, с минимальным числом конъюктивных термов.

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

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

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

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);

— параллельное выполнение программ.

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-код файлы несут достаточно информации для работы оптимизирующего компилятора.

«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), структуры (почти то же, что и классы, но размещаемые не куче и без наследования), перечисления, несовместимые с целыми (как в Паскале);

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

— типы подразделяются на ссылочные (классы, интерфейсы, массивы, делегаты) и типы-значения (элементарные типы, перечисления, структуры). Объекты ссылочных типов размещаются в динамической памяти (куче), а переменные ссылочных типов являются, по сути, указателями на эти объекты. В случае типов-значений переменные представляют собой не указатели, а сами значения. Неявные преобразования типов разрешены только для случаев, когда они не нарушают систему безопасности типов и не приводят к потере информации. Все типы, включая элементарные, совместимы с типом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;

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

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

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

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

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

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/C++, Perl, Groovy, Ruby, Python, PHP, Erlang, Компонентного Паскаля, Zonnon и прочих.

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).

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

Вскрытая закономерность позволяет автоматически формировать ПНФ функции без предварительного составления и хранения — таблица 1.4. Более того, отпадает необходимость хранения всей таблицы истинности логической функции, для формирования ПНФ достаточно иметь только таблицу минтермов данной функции.

Алгоритм формирования ПНФ с использованием ЧПНФ представлен на рисунке 2.1.

Рисунок 2.1 — Алгоритм формирования ПНФ с использованием ЧПНФ

2.2 Модульная структура ПС Исходя из цели дипломного проектирования и рассмотренного выше алгоритма полиномиального преобразования БФ, сформулированы основные требования к разрабатываемому исследовательскому комплексу минимизации полинома Жегалкина частично определенных булевых функций. Исследовательский комплекс должен обеспечивать пользователю следующие возможности:

— ввод количества аргументов булевой функции;

— формирование таблицы истинности БФ для установленного пользователем количества переменных;

— заполнение значений БФ таблице истинности;

— ввод вектора значений БФ в автоматическом и ручном режиме;

— доопределение вектора БФ;

— вычисление минимального полинома Жегалкина;

— подсчет количества минтермов.

Учитывая вышесказанное, была предложена функциональная схема разрабатываемого исследовательского комплекса минимизации полинома Жегалкина частично определенных БФ, которая представлена на рисунке 2.2.

Рисунок 2.2 — Структура функциональных блоков программного средства

«Управляющий блок» программного обеспечения предназначен для взаимодействия пользователя с программой и обеспечения взаимосвязи между остальными блоками.

Блок «Справка» предназначен для вывода информации о возможностях программы, ее технических и программных требованиях, а также о функциональных элементах и их расположении.

«Блок ввод данных» предназначен для ввода основных параметров вычисления — числа аргументов булевой функции и значений вектора F (). Функция F () в программном продукте, может быть как полностью определена, так и частично. Если функция определена частично, то программа дополняет вектор БФ произвольно.

«Блок заполнения таблицы истинности»: при выборе числа аргументов БФ, автоматически рассчитывается размерность таблицы истинности и заполняются ее значения.

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

«Блок вычисления» предназначен для систематизации введенной информации и выполнения расчетов (записи функции в виде полинома Жегалкина с вычисленными коэффициентами). Реализуется алгоритм минимизации полинома Жегалкина частично определенных булевых функций Он включает в себя следующие блоки:

1 — «Блок поиска количества конъюнкций»;

2 — «Блок формирования полинома Жегалкина методом ЧПНФ».

Блочная структура ПС состоит из 8 модулей. В разделе 2.3 спроектирован алгоритм использования частных полиномиальных нормальных форм БФ.

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

Суть алгоритма заключается в следующем, пользователь вводит n — число аргументов булевой функции. По числу n определяем, как будет производиться ввод вектора значений БФ: вручную, если n<5 или автоматически, если 5

После проделанной работы сравнивается количество конъюнкций в текущем и предыдущем полиномах. Программа запоминает коэффициенты полинома Жегалкина с минимальным количеством конъюнкций и соответствующий доопределенный вектор значений БФ, после чего выводит их на экранную форму. Процесс доопределения происходит 2^k раз, где k — число неопределенных наборов. Схема алгоритма разрабатываемого программного модуля представлена на рисунке 2.3.

Рисунок 2.3 — Cхема алгоритма В данной программе будет реализован алгоритм булевой функции полинома Жегалкина методом частных полиномиальных нормальных форм, для этого необходимо:

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

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

— последовательно вычислить неизвестные коэффициенты;

— записать функцию в виде полинома Жегалкина с вычисленными коэффициентами;

— построить минимальный полином.

2.4 Описание синтаксиса ПС Опишем данные, которые будут использованы в программном обеспечении. Информация будет делиться на категории, для каждой категории будут определены её компоненты. Например такие, как основы языка С#:

— типы данных;

— одномерные массивы;

— цикл с предусловием while;

— цикл с параметром for;

— оператор выбора switch.

Для каждого компонента категории будут представлены характеристики: описание, синтаксис, листинг.

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

Каждый из функциональных блоков представленных в пункте 2.2, в свою очередь, состоит из классов. Основной класс в программе ZhegalkinMainForm описан ниже. Находим множество двоичных наборов функции, на которых она принимает значение 1. После составления СДНФ в формуле каждый знак дизъюнкции меняем на знак суммы Жегалкина. Упрощаем, полученное выражение, используя тождества. В полученной формуле каждый элемент с отрицанием заменяем на. Раскрываем скобки в полученной формуле, содержащей только. Приводим подобные члены.

public partial class ZhegalkinMainForm: Form

{

private Random Rand = new Random (Environment.TickCount);

private ZhegalkinPolinomBuilder builder = new ZhegalkinPolinomBuilder ();

public ZhegalkinMainForm ()

{

InitializeComponent ();

this.FillTable ((int)nudN.Value);

}

private void nudN_ValueChanged (object sender, System. EventArgs e)

{

this.FillTable ((int)nudN.Value);

}

Добавление строк в таблице истинности происходит при увеличении числа аргументов функции.

private void FillTable (int n)

{

dgvTruthTable.Rows.Clear ();

var rowsCount = (int)Math.Pow (2, n);

for (int i = 0; i < rowsCount; i++)

{

dgvTruthTable.Rows.Add ();

}

// Заполнение колонок таблицы истинности.

for (int i = 0; i < Constants. MaxN; i++)

{

dgvTruthTable.Columns[i]. ReadOnly = true;

if (i < n)

{

dgvTruthTable.Columns[i]. DefaultCellStyle. BackColor = Color. White;

this.FillColumn (n, rowsCount, i);

}

else

{

dgvTruthTable.Columns[i]. DefaultCellStyle. BackColor = Color. DarkGray;

}

}

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

if (n >= Constants. AutoN || cbRandom. Checked)

{

this.FillF (rowsCount);

}

}

private void FillColumn (int variableCount, int rowsCount, int columnNumber)

{

var c = (int)rowsCount / (int)Math.Pow (2, columnNumber + 1);

var vc = 0;

var v = false;

for (int i = 0; i < rowsCount; i++)

{

dgvTruthTable[columnNumber, i]. Value = Convert. ToInt32(v).ToString ();

vc++;

if (vc == c)

{

vc = 0;

v = !v;

}

}

}

private void FillF (int rowsCount)

{

for (int i = 0; i < rowsCount; i++)

{

dgvTruthTable[Constants.MaxN, i]. Value=Convert.ToInt32(Rand.Next (0, 2)).ToString ();

}

}

private void FillFEmpty (int rowsCount)

{

for (int i = 0; i < rowsCount; i++)

{

dgvTruthTable[Constants.MaxN, i]. Value = string. Empty;

}

}

private void cbRandom_CheckedChanged (object sender, EventArgs e)

{

var rowsCount = (int)Math.Pow (2, (int)nudN.Value);

if (cbRandom.Checked)

{

this.FillF (rowsCount);

}

else

{

this.FillFEmpty (rowsCount);

}

}

private void btBuild_Click (object sender, EventArgs e)

{

var variableCount = (int)nudN.Value;

var rowsCount = (int)Math.Pow (2, variableCount);

var matrix = new List (rowsCount);

var function = new List (rowsCount);

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

// Функция заполнения

for (int i = 0; i < rowsCount; i++)

{

int value;

if (dgvTruthTable[Constants.MaxN, i]. Value == null || Int32. TryParse (dgvTruthTable[Constants.MaxN, i]. Value. ToString (), out value) == false)

{

this.InputError ();

return;

}

function.Add (value);

}

// Матрица заполнения

for (int i = 0; i < rowsCount; i++)

{

matrix.Add (new int[variableCount]);

for (int j = 0; j < variableCount; j++)

{

matrix[i][j] = int. Parse (dgvTruthTable[j, i]. Value. ToString ());

}

}

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

// Нахождение полинома Жегалкина.

try

{

var minterns = 0;

var polynom = builder. BuildZhegalkinPolinom (matrix, function, Constants. Variables, out minterns);

polinomy.Add (polynom);

minterny.Add (minterns);

}

catch

{

this.UnexpectedError ();

}

}

// Нахождение минимального полинома

var minPol = polinomy[0];

var minMin = minterny[0];

var nessesaryLine = 0;

for (int k = 1; k < emptyRowsCount; k++)

{

if (minterny[k] < minMin)

{

minMin = minterny[k];

minPol = polinomy[k];

nessesaryLine = k;

}

}

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

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

var g = 0;

for (int i = 0; i < rowsCount; i++)

{

int value;

if (dgvTruthTable[Constants.MaxN, i]. Value == null || Int32. TryParse (dgvTruthTable[Constants.MaxN, i]. Value. ToString (), out value) == false)

{

dgvTruthTable[Constants.MaxN, i]. Value = indexs[nessesaryLine][g]. ToString ();

g++;

}

}

lResult.Text = minPol;

if (cbUse.Checked)

{

lResult.Text = lResult.Text.Replace («@», «(+)»);

}

lResult.Text = lResult.Text.Replace («^», «&»);

lMinternsResult.Text = minMin. ToString ();

}

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

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

Блок входных данных «Введите количество переменных» — предназначен для ввода основных параметров вычисления — числа аргументов булевой функции и значений вектора F ().

Таблица истинности необходима в программе. Это удобный инструмент описания поведения логической функции. Она служит для наглядности и удобства пользователя вводить данные и изменять вектор БФ.

Кнопка «Доопределить вектор F (…)» позволяет пользователю мгновенно доопределять функцию таким образом, что полином Жегалкина будет минимальным.

Кнопка «Построить полином Жегалкина» вычисляет полином методом ЧПНФ. Если вектор БФ определен, то программа автоматически производит расчет полинома и выводит результат на экран.

Кнопка «Доопределить вектор и построить минимальный полином» доопределяет вектор БФ 2^K — раз и выводит на экран пользователю минимальный полином Жегалкина.

Текстовый блок «Количество конъюнкций» — показывает наименьшее количество конъюнкций в полиноме Жегалкина.

Объект CheckBoks «Ввод вектора значений булевой функции в автоматическом режиме» будет расположен вверху формы. При нажатии на него вектор БФ будет заполняться автоматически независимо от того, сколько пользователь выбрал аргументов функции. Если нажать на него повторно, то вектор БФ обнулится.

Часть формы, связанная с проверкой данных, после стадии разработки будет расположена либо на данной форме в нижележащей панели, либо на отдельной вкладке, для того, чтобы избежать «загруженности» формы компонентами, что поведет к усложнению работы с программой. Изначально был предложен тестовый вид формы (рисунок 3.1) для работы в программе. Для удобного пользования программой создадим виджеты — элементы интерфейса, используемые при создания макетов. Панель виджетов включает в себя библиотеку наиболее популярных элементов, таких как кнопки, изображения и текстовые блоки.

Рисунок 3.1 — Макет интерфейса пользователя

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

Для работы приложения и реализации данного алгоритма необходима следующая конфигурация ЭВМ:

— процессор уровня Intel Pentium 3 и выше;

— 512 Мб ОЗУ;

— операционная система не ниже MS Windows XP;

— среда разработки Microsoft Visual Studio 2012 (в частности свободно распространяемая версия Microsoft Visual C# 2012 Express Edition);

— дисплей с разрешением 1024×768;

— мышь;

— клавиатура.

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

Установка приложения осуществляется посредством копирования папки с приложением «Elevator.Zhegalkin.Gui» на любой жесткий диск компьютера.

При запуске приложения двойным щелчком мыши файла «Elevator.Zhegalkin.Gui» открывается окно, интерфейс которого представлен на рисунке 3.2. После чего пользователь вводит n — число аргументов булевой функции в графу «Введите количество переменных» (изначально количество переменных равно 2).

Рисунок 3.2 — Главное окно программы

Рисунок 3.3 — Доопределение вектора F (…)

При выборе пункта меню «Доопределить вектор F (…)», в графе «F (…)» выводятся значения вектора БФ. Для того чтобы значения вектора БФ выводились в автоматическом режиме, достаточно поставить флажок на кнопке «Ввод вектора значений булевой функции в автоматическом режиме». При снятии флажка, значения вектора БФ обнуляются. Ввод вектора в автоматическом режиме всегда генерируются по-разному. Для ручного режима ввода вектора БФ, достаточно изменить значение ячейки в таблице истинности. Вид формы представлен на рисунке (рисунок 3.3) .

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

Рисунок 3.4 — Построение полинома Жегалкина При некорректной работе пользователя программа выводит предупреждающие сообщения. Если кнопка «Построить полином Жегалкина» нажата ранее построения вектора F (…), на экране появится текстовое предупреждение пользователя (рисунок 3.5).

Рисунок 3.5 — Предупреждающее сообщение Рисунок 3.6 — Предупреждающее сообщение Если пользователь что — то сделал не правильно, появляется предупреждающее окно с содержанием: «Неожиданная ошибка, пожалуйста проверьте данные».

Рисунок 3.7 — Предупреждение об ошибке

В программе предусмотрена возможность для ввода компонентов вектора БФ с частично определенными значениям, в форме содержащей случайным образом сгенерированный вектор значений БФ (рисунок 3.8). Затем доопределяем вектор БФ и реализуем алгоритм формирования полинома Жегалкина методом ЧПНФ используя кнопку «Доопределить вектор и построить минимальный полином» (рисунок 3.9).

Рисунок 3.8 — Ввод компонентов вектора БФ с частично определенными значениям После сравнения количества коньюнкций в текущем и предыдущем полиномах, программа запоминает коэффициенты полинома Жегалкина с минимальным количеством коньюнкций и соответствующий доопределенный вектор значений БФ и выводит на экранную форму в разделы «Количество конъюнкций:» и «Полином Жегалкина:».

Рисунок 3.9 — Параметры тестирования

При нажатии на кнопку «Справка» появляется экранная форма с информацией о разработчике и назначении программы.

Рисунок 3.10 — Форма «Справка»

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

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

Пример.

Таблица 3.1 — Таблица истинности функции

Пусть не полностью определена логическая функция, заданная с помощью таблицы истинности. Два первых значения в векторе БФ не определены (таблица 3.2):

Таблица 3.2 — Таблица истинности логической функции

Определяются исходные данные a, b и с, при которых значение логической функции равно 1. Доопределяем функцию единицами и нулями так, чтобы при составлении ДНФ было минимальное число импликант наименьшего ранга. Используя наборы для доопределения функции, получим следующие полиномы:

Форма ЧПНФ: .

Строим ДНФ БФ, а затем формируем полином Жегалкина, используя известные соотношения:

;

;

;

;

;

;

;

;

.

Для синтеза логической схемы используется СДНФ. Доопределим значение вектора БФ функции F (1,0,1,0,1,0,1,0)

Таблица 3.3 — Таблица истинности логической функции

При значении вектора БФ равным 10 100 110, вычислим:

СДНФ:

Перейдём от СДНФ к ПНФ, приведем подобные члены.

ПНФ:

Получаем полином Жегалкина .

Доопределим значение вектора БФ функции F (0,1,1,0,1,0,1,0)

Таблица 3.4 — Таблица истинности логической функции

При значении вектора БФ равным 1 100 110, вычислим:

СДНФ:

Перейдём от СДНФ к ПНФ, приведем подобные члены.

ПНФ:

Получаем полином Жегалкина — минимальный полином.

Доопределим значение вектора БФ функции F (0,0,1,0,1,0,1,0)

Таблица 3.5 — Таблица истинности логической функции

При значении вектора БФ равным 100 110, вычислим:

СДНФ:

ПНФ:

Получаем полином Жегалкина

Доопределим значение вектора БФ функции F (1,1,1,0,1,0,1,0)

Таблица 3.6 — Таблица истинности логической функции

При значении вектора БФ равным 11 100 110, вычислим:

СДНФ:

ПНФ:

Получаем полином Жегалкина .

Из решения можно сделать вывод, что комбинация 1 100 110 — является минимальным полиномом.

Таблица 3.7 — Таблица доопределения функции

Результаты работы программного средства полностью совпадают с вышеизложенным решением и представлены на рисунке 3.11 и 3.12.

Рисунок 3.11 — Результат работы ПС Рисунок 3.12 — Результат работы ПС Таким образом, из результатов вычислительного эксперимента, следует, что разработанный алгоритм является верным и корректно реализованным.

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

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

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

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

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

На сегодняшний день задачу преобразования функции в виде полинома Жегалкина можно попытаться решить с помощью пакетов математических программ, таких как MatCAD, MatLab, Mathematca. Но их стоимость достаточно ощутима, да и к тому же, они требуют специальных навыков в работе, что, несомненно, приведет к увеличению общего времени решения задач, в которых представление булевых функций в полиномиальной форме в базисе Жегалкина является не основной, а косвенной задачей. Поэтому, в процессе разработки дипломного проекта, мы проанализировали дипломные проекты, затрагивающие данную тему ранее. Наиболее интересными и качественными программными продуктами оказались следующие: «Бинарно-векторное разложение булевых функций в полином Жегалкина» и «Метод фрактальных преобразований».

Первый критерий для сравнения — быстродействие. Здесь понимается потраченное время на решение задачи. Программы «Бинарно-векторное разложение булевых функций в полином Жегалкина» и «Метод фрактальных преобразований», решают задачу методами, вычислительная мощность которых намного превышает вычислительную мощность реализуемого нами метода. Что позволяет с уверенностью говорить о более высокой производительности разрабатываемого нами ПО. Минус программ, на мой взгляд, является то, что они разработаны на языке Delphi. Архитектура полученного исполняемого файла построена таким образом, что все необходимые библиотеки компонуются вместе с исполняемым файлом, что заметно увеличивает его размер. Большой размер исполняемого файла влияет на скорость запуска приложения, что также является немаловажным фактором. Разрабатываемое же нами ПО написано в среде Visual C#, а значит, все системные функции будут браться из стандартных системных библиотек.

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

4.2 Определение трудоемкости разработки программного продукта Для определения трудоемкости разработки программного продукта воспользуемся «Укрупненными нормами времени на изготовление и сопровождение программных средств вычислительной техники».

В этом случае параметрами, влияющими на расчет трудоемкости разработки, являются:

ѕ стадии разработки ПС;

ѕ сложность ПС;

ѕ степень новизны ПС;

ѕ новый тип ЭВМ;

ѕ новый тип ОС;

ѕ степень охвата реализуемых функций стандартными ПС;

ѕ средства разработки ПС;

ѕ характер среды разработки;

ѕ характеристики ПС;

ѕ группа сложности;

ѕ функции ПС;

ѕ тип ЭВМ.

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

Таблица 4.1 — Численные величины, характеризующие ПС

Общий объем разрабатываемого ПС, определяется по формуле

(4.1)

где V₀ — общий объем разрабатываемого ПС;

V_i — объем i-ой функции ПС, i = 1.16, учитывающий тип ЭВМ;

n — общее число функций.

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

(4.2)

где Т_УР — трудоемкость разработки ПС с учетом конкретных условий разработки;

Т_Б — базовая трудоемкость разработки ПС, учитывающая объем ПС и группу сложности, чел.-дни;

К_УР — поправочный коэффициент, учитывающий характер среды разработки и средства разработки ПС.

Коэффициент сложности ПС, определяется по формуле

(4.3)

где K_СЛ — коэффициент сложности ПС;

K_i — коэффициенты повышения сложности ПС, i = 1.7, зависящий от наличия у разрабатываемой системы характеристик, повышающих сложность ПС и от количества характеристик ПС;

n — количество дополнительно учитываемых характеристик ПС.

Общая трудоемкость разработки ПС определяется по формуле

(4.4)

(чел.-дни),

где Т_О — общая трудоемкость разработки ПС, чел.-дни;

Т_УР — трудоемкость разработки ПС с учетом конкретных условий разработки, чел.-дни;

К_СЛ — коэффициент сложности ПС.

Трудоемкость i-ой стадии разработки ПС определяется по формуле

(4.5)

где Т_i — трудоемкость i-ой стадии разработки, чел.-дни;

Li — удельный вес трудоемкости i-ой стадии разработки ПС, учитывающий наличие той или иной стадии и использование CASE-технологии;

К_Н — поправочный коэффициент, учитывающий степень новизны ПС и использование при разработке ПС новых типов ЭВМ и ОС;

Т_О — общая трудоемкость разработки ПС, чел.-дни;

К_Т — поправочный коэффициент, учитывающий степень использования в разработке стандартных (типовых) ПС.

Общая трудоемкость разработки ПС рассчитывается по формуле

(4.6)

где Т_ОБЩ — общая трудоемкость разработки ПС, чел.-дни;

Т_i — трудоемкость i — ой стадии разработки ПС, чел.-дни, i = 1.5;

n — количество стадий разработки ПС.

Таким образом, общая трудоемкость разработки ПС равняется 148,71 чел.-дней.

4.3 Определение состава исполнителей Произведем расчет числа исполнителей, которое нужно для разработки ПС при известной трудоемкости и сроках разработки. Значения рассчитанных величин приведем в таблице 4.2.

Таблица 4.2 — Расчет необходимого количества исполнителей

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

. (4.7)

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

Таблица 4.3 — Состав исполнителей разработки ПС

4.4 Расчет стоимости разработки программного продукта На момент написания работы:

социальные отчисления с заработной платы составляют 30%;

ставка НДС составляет 18%.

Сметную стоимость и договорную цену ПС рассчитаем в таблице 4.13, выполнив предварительно расчеты составляющих сметной стоимости в таблицах 4.4 — 4.9.

Расчет затрат на материалы и покупные изделия представлен в таблице 4.4.

Таблица 4.4 — Расчет затрат на материалы и покупные изделия

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

Таблица 4.5 — Показатели по расчету затрат на оплату труда работников, обеспечивающих функционирование ПЭВМ, административного и вспомогательного персонала

Расчет затрат на оплату труда работников, обеспечивающих функционирование ПЭВМ, административного и вспомогательного персонала, приведен в таблице 4.6.

Таблица 4.6 — Затраты на оплату труда работников, обеспечивающих функционирование ПЭВМ, административного и вспомогательного персонала

Расчет затрат на электроэнергию произведем в таблице 4.7.

Таблица 4.7 — Расчет затрат на электроэнергию

Расчет затрат на эксплуатацию специального оборудования представлен в таблице 4.8.

Таблица 4.8 — Расчет затрат на эксплуатацию специального оборудования

Сумма расходов на содержание и эксплуатацию ПЭВМ, относящихся к данному программному продукту, составит 3534 р.

Расчет затрат на оплату труда и социальные отчисления представлен в таблице 4.9.

Таблица 4.9 — Расчет затрат на оплату труда и социальные отчисления

Расчет сметной стоимости и договорной цены разработки ПС произведем в таблице 4.10.

Таблица 4.10 — Расчет сметной стоимости и договорной цены разработки ПС

4.5 Расчет трудоемкости сопровождения ПС Параметрами, которые влияют на расчет трудоемкости сопровождения, являются:

ѕ характер поставки;

ѕ характеристика средств разработки ПС;

ѕ характеристика полноты тестирования;

ѕ степень участия службы сопровождения в разработке ПС;

ѕ характер внедрения;

ѕ функции ПС;

ѕ объем документации;

ѕ функции, подлежащие доработке;

ѕ разработка дополнительных функций;

ѕ показатели повышения сложности ПС.

Общая трудоемкость сопровождения ПП (в чел.-днях) рассчитывается как сумма всех трудоемкостей.

Трудоемкость приемки и освоения опытного образца ПП определяется по формуле

(4.8)

где Т_ОС — трудоемкость приемки и освоения опытного образца ПП, (чел.-дни).

К_СЛ — коэффициент, учитывающий уровень повышения сложность ПП;

К_АН. — коэффициент, учитывающий наличие в фонде аналогов данного ПП;

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

Н_вр.ос. — норма времени на приемку и освоение опытного образца ПП (чел.-дни).

Трудоемкость проверки и оценки опытного образца ПП определяется по формуле

(4.9)

где Т_ПР — трудоемкость проверки и оценки опытного образца ПП;

К_СЛ — коэффициент, учитывающий сложность ПП;

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

Н_вр.пр. — норма времени на проверку и оценку опытного образца ПП.

Трудоемкость разработки документации по доработке ПП определяется по формуле

(4.10)

где Т_РР — трудоемкость разработки документации по доработке ПП;

К_УЧ — коэффициент, характеризующий степень участия службы сопровождения в разработке ПП;

К_СЛ — коэффициент, учитывающий сложность ПП;

Н_вр.ан — норма времени на анализ опытного образца ПП.

Трудоемкость обучения специалистов организации заказчика работе с ПП, определяется по формуле

(4.11)

где Т_ОБ — трудоемкость обучения специалистов организации заказчика работе с ПП;

К_СЛ — коэффициент, учитывающий сложность ПП;

Н_вр.об — норма времени на обучение специалистов организации-заказчика работе с ПП.

Исходя из ранее подсчитанных формул можно рассчитать общую трудоемкость сопровождения ПП (в чел.-днях) по формуле Тсопр = 5,85 + 2,37 + 2,02 + 4,93 = 15,2, (4.12)

Таким образом, трудоемкость сопровождения ПС равняется 15,2 чел.-дней.

4.6 Определение стоимости сопровождения ПС Расчет стоимости сопровождения произведем в таблице 4.11, предполагая, что сопровождение проводит специалист с месячным окладом 7500 р.

Таблица 4.11 — Расчет стоимости сопровождения ПС

Таким образом, стоимость сопровождения программного продукта равняется 5822,21 рублей.

4.7 Планирование цены ПП и прогнозирование прибыли Разрабатываемый комплекс, решающий задачу формирования минимального полинома Жегалкина по вектору значений булевой функции методом частных полиномиальных нормальных форм, предназначен для применения в учебном процессе с малым количеством рабочих мест, исходя из этого, можно сделать вывод, что данная программа будет рентабельна только локально. Стоимость выставляемого на рынок ПП определяется частью стоимости разработки ПП, затрат на сопровождение и прибыли организации-разработчика. Запланируем реализацию 20 копий разработанной программы.

Стоимость ПП можно рассчитать, используя соотношение по формуле

(4.13)

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

С_СОПР — стоимость сопровождения ПП;

D_ПРИБ — процент прибыли, закладываемый в стоимость.

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

(4.14)

где С_ПП — стоимость проекта,

N — число копий ПП,

Н_СТ — ставка банковского процента по долгосрочным кредитам (более одного года).

Таким образом, цена программного продукта равняется 12 014,92 рублей.

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

Анализ конкурентоспособности и качества программного продукта должен учитывать специфику программного продукта, как товара и может включать в себя:

ѕ оценку функциональной пригодности;

ѕ оценку способности к взаимодействию;

ѕ оценку защищенности;

ѕ оценку надежности;

ѕ оценку потребности в ресурсах памяти и производительности компьютера.

В качестве базового ПС возьмём программу «Бинарно-векторное разложение булевых функций в полином Жегалкина», которая была описана в параграфе 4.1.

4.8.1 Анализ технической прогрессивности разрабатываемого программного продукта Для расчета коэффициента технической прогрессивности разрабатываемого ПС использованы параметры: время выполнения запроса, объем оперативной памяти, объем памяти на жестком диске. Расчет коэффициента технической прогрессивности разрабатываемого ПП приведен в таблице 4.12.

Таблица 4.12 — Расчет коэффициента технической прогрессивности разрабатываемого ПС

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

. (4.15)

Можно сделать вывод, что анализируемая ПС технически прогрессивна, так как К_ТП > 1.

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

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

Оценка каждого параметра ведется в баллах. Общая сумма баллов базового ПС (товара-конкурента) принимается равной количеству оцениваемых функциональных возможностей ПС. Сравнение произведем в таблице 4.13.

Таблица 4.13 — Расчет коэффициента изменения функциональных возможностей разрабатываемого ПС

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

. (4.16)

Убеждаемся, что анализируемое ПС имеет лучшие функциональные возможности, чем базовый.

4.8.3 Анализ соответствия разрабатываемого программного продукта нормативам Нормативные или, так называемые, регламентируемые параметры характеризуют соответствие разрабатываемого ПП международным и национальным стандартам, нормативам, законодательным актам и др. Для оценки этого показателя применяется единичный или групповой показатель — k_НОРМ. Для данной разработки k_НОРМ=1, это означает, что данный ПП по нормативным параметрам конкурентоспособен.

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

Цена потребления (Ц_П) представляет собой затраты покупателя на приобретение, доработку, а также эксплуатацию анализируемого ПС на протяжении периода эксплуатации и вычисляется по формуле

(4.17)

где Ц_П — цена потребления, р;

Ц_ПР — продажная цена ПС (копии ПС), т. е. цена приобретения ПС покупателем, р.;

И_ЭКС — годовые эксплуатационные издержки потребителя, р.;

Т_Н — нормативный срок эксплуатации ПС, лет;

Р_СОПР — затраты на сопровождение, р.

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

Таблица 4.14 — Расчет годовых эксплуатационных издержек потребителя ПС

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

Период эксплуатации примем равным 3 годам. Расчет цены потребления ПС представлен в таблице 4.15.

Таблица 4.15 — Расчет цены потребления ПС

Значение коэффициента цены потребления рассчитывается по формуле

k_ЦП =, (4.18)

где Ц_П^НОВ, Ц_П^БАЗ — цена потребления соответственно разрабатываемого и базового ПС.

Т.к. К_ЦП < 1, то экономические показатели разрабатываемого ПС лучше, чем у базового.

4.8.5 Оценка конкурентоспособности программного продукта В целом конкурентоспособность нового ПП по отношению к базовому можно оценить с помощью интегрального коэффициента конкурентоспособности (К_И), учитывающего все ранее рассчитанные параметры, по формуле

(4.19)

.

Анализируемое изделие будет конкурентоспособно, так как К_И>1.

4.9 Анализ технико-экономических показателей разработки и эксплуатации ПП В результате выполнения организационно-экономических расчетов получены показатели разработки и эксплуатации ПС, которые сравним с базовым ПС. Показатели сведем в таблицу 4.16.

Таблица 4.16 — Технико-экономические показатели разработки и эксплуатации ПС «Полиномиальное преобразования БФ на основе метода частных полиномиальных нормальных форм в полином Жегалкина»

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

ѕ высокий коэффициент конкурентоспособности;

ѕ высокий коэффициент технической прогрессивности;

ѕ низкий коэффициент цены потребления;

ѕ высокий интегральный коэффициент конкурентоспособности.

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

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

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

В данной дипломной работе разрабатывается программное обеспечение решения задачи минимизации полинома Жегалкина частично определенных булевых функций. Будут рассмотрены мероприятия по обеспечению БЖД при работе на ПЭВМ.

Во время работы на работника могут воздействовать опасные и вредные факторы, такие как:

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

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

— при эксплуатации видеодисплейных терминалов на электронно-лучевых трубках в рабочих зонах регистрируются статические электрические и импульсные электрические и магнитные поля низкой и сверхнизкой частоты, создаваемые системами кадровой и строчной развертки. Кроме ВДТ источниками электромагнитных полей (ЭМП) являются процессор, принтер, клавиатура, многочисленные соединительные кабели;

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

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

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

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

В производственных помещениях, в которых ведется работа с использованием ПЭВМ, температура, относительная влажность и скорость движения воздуха на рабочих местах должны соответствовать действующим санитарным нормам микроклимата производственных помещений. По таблице 5.1 (определение категории тяжести работ) видим, что характер производимых работ нашими сотрудниками относится к категории «1а».

Таблица 5.1 — Определение категории тяжести работ

В соответствии с этой категории работ определим допустимые величины показателей микроклимата на рабочих местах производственных помещений (СанПиН 2.2.4.548−96) и занесём данные в таблицу 5.2.

Таблица 5.2 — Допустимые величины показателей микроклимата на рабочих местах производственных помещений (извлечение из СанПин 2.2.4.548−96)

В помещениях, оборудованных ПЭВМ, должна проводиться ежедневная влажная уборка и систематическое проветривание. Система вентиляции выполняется в соответствии с требованием СНиП 2.04.05 — 91(1999) «Отопление, вентиляция и кондиционирование воздуха». В летний период года используется кондиционер, а в зимний период паровое отопление.

5.2.2 Шум Объективно действия шума проявляются в виде повышения кровяного давления, учащенного пульса и дыхания, снижения остроты слуха, ослабления внимания, некоторые нарушения координации движения, снижения работоспособности. Субъективно действия шума могут выражаться в виде головной боли, головокружения, бессонницы, общей слабости. В производственных помещениях при выполнении основных или вспомогательных работ с использованием ПЭВМ уровни шума на рабочих местах не должны превышать предельно допустимых значений, установленных для данных видов работ, в соответствии с действующими санитарно — эпидемиологическими нормативами таблица 5.3.

Таблица 5.3 — Допустимые уровни звукового давления, уровни звука, эквивалентные и максимальные уровни звука проникающего шума в помещениях общественных здании (извлечение из СанПин 23−03−2003)

Шумящее оборудование (печатающие устройства, серверы и т. п.), уровни шума которого превышают нормативные, должны размещаться вне помещений с ПЭВМ.

5.2.3 Освещение

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

В нашем офисе используется комбинированная система освещения. Характер зрительных работ относится к категории средней точности (разряд IV), нормативные величины освещенности для которой (по СНиП 23−05−95) занесены в таблицу 5.4.

Таблица 5.4 — Нормированные значения КЕО при естественном и совмещенном освещении (извлечение из СНиП 23−05−95)

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

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

Электробезопасность должна обеспечиваться:

— конструкцией электроустановок;

— техническими способами и средствами защиты;

— организационными и техническими мероприятиями.

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

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

Таблица 5.5 — Предельно допустимые уровни напряжений прикосновения и токов (время нахождения под напряжением 10 сек)

Нормативные требования:

ГОСТ 12.1.019−79(1996). Электробезопасность. Общие требования и номенклатура видов защиты;

ГОСТ 12.1.030−81(2001). Электробезопасность. Защитное заземление, зануление.

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

Условия расчетного задания:

— количество человек в помещении — 2;

— количество ПЭВМ в помещении — 2;

— мощность одной ПЭВМ — 500 Вт;

— тепло, выделяемое одним человеком — 90 Вт;

— площадь остекления — 6 м² ;

— высота помещения — 3,5 м;

— длина помещения — 6,5 м;

— ширина помещения — 4 м.

Расчет вентиляции проводится для наиболее неблагоприятных условий: тёплый период года, в помещении включены все ПЭВМ. В помещении работают два программиста. Учитывая, что один человек выделяет 90 Вт тепла, общие тепловыделения от людей составят

Вт.

Тепловыделения от ПЭВМ и источников искусственного освещения определяются по формуле:

(5.1)

где Q — тепловыделения, Вт;

N — суммарная мощность устройств, Вт;

n — коэффициент тепловых потерь (n=0,7 для ПЭВМ, n=0,55 для люминесцентных ламп).

Тепловыделения от 2-х ПЭВМ составят

Вт.

Тепловыделения от 2-х ламп ЛБ-65 составят Вт.

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

(5.2)

где — тепловыделения от солнечной радиации, Вт;

— площадь остекления, м²;

— тепловыделения через 1 м² поверхности остекления, Вт/м²;

— коэффициент учёта характера остекления.

В рассматриваемом случае F_ост = 6 м², q = 145 Вт/м², А_ост = 1,15.

Тогда по (2) Вт.

Суммарные избыточные тепловыделения

Вт, Объём приточного воздуха, необходимого для поглощения избытков тепла определяется по формуле

(5.3)

где G — объём приточного воздуха, м³/ч;

Q — теплоизбытки, Вт;

Cр — удельная теплоёмкость воздуха (1000 Дж/(кг•⁰С));

— плотность воздуха (1,2 кг/м³);

t_уд — температура удаляемого воздуха, ⁰С;

t_пр — температура приточного воздуха, ⁰С.

Температура приточного воздуха в тёплый период года принимается равной 20 ⁰С. Температура удаляемого воздуха определяется по формуле

(5.4)

где t_yg — температура удаляемого воздуха, ⁰С;

t_pc — оптимальная температура воздуха в рабочей зоне (23 ⁰С);

— температурный градиент (1 ⁰С/м);

H — высота помещения (3,5 м).

Тогда по (5.3)

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

— приточной камеры, в состав которой входят вентилятор с электродвигателем, калорифер для подогрева воздуха в холодное время года и жалюзийная решётка для регулирования объёма поступающего воздуха;

— круглого стального воздуховода длиной 1,5 м;

— воздухораспределителя ВП для подачи воздуха в помещение.

Потери давления в вентиляционной системе определяются по формуле

(5.5)

где H — потери давления, Па;

R — удельные потери давления на трение в воздуховоде, Па/м;

L — длина воздуховода, м (L=1,5 м);

— суммарный коэффициент местных потерь в системе;

V — скорость воздуха (V=3 м/с);

— плотность воздуха (=1,2 кг/м³).

Необходимый диаметр воздуховода для данной вентиляционной системы Принимаем в качестве диаметра ближайшую большую стандартную величину — 0,4 м. Для воздуховода данного диаметра удельные потери давления на трение R=0,21 Па/м.

Местные потери возникают в жалюзийной решётке (=1,2), воздухораспределителе (=1,4) и калорифере (=2,2). Тогда суммарный коэффициент .

Тогда по (5.5)

Па.

С учётом 10%-ого запаса

Па.

м³/ч.

По каталогу выбираем вентилятор осевой серии МЦ № 4: расход воздуха 1600 м³/ч, давление 40 Па, КПД 65%, скорость вращения 960 об/мин, диаметр колеса 400 мм, мощность электродвигателя 0,032 кВт (двигатель соединён на одной оси с вентилятором).

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

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

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

Категория помещения по пожаровзрывной и пожарной опасности: класс В.

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

Для обнаружения самой первоначальной стадии пожара (загорания) и сообщения о месте его возникновения в здании установлена вспомогательная сигнальная установка. Она состоит из следующих частей: вспомогательной сигнальной станции, подключенной к главной сигнальной установке пожарной службы; ионизационных дымоизвещателей; термодифференционных извещателей, которые реагируют на повышение температуры на единицу времени; кнопочных сигнализаторов для ручной подачи сигналов тревоги; системы проводов (сети), соединяющих извещатели с приемной станцией. План помещения изображен на рисунке 5.1.

Рисунок 5.1 — План эвакуации из помещения

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

Заключение

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

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

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

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

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

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

— интегральный коэффициент конкурентоспособности ПП = 2,1;

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

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

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

— затраты на разработку = 207 204,00 руб.;

— продажная цена = 12 014,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 с.