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

 

Объект исследования: проблема минимизации ДНФ для булевых функ-ций.

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

 

Цель работы: разработать программу, находящую минимальную ДНФ для любой булевой функции от 3 или 4 переменных.

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

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

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

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

Алгоритм состоит из двух этапов:

1. Зафиксировав число переменных n=3 или 4, создаем базу данных, содер-жащую все возможные МДНФ от n переменных, их длины l, а также их таб-лицы истинности (в виде двоичной строки значений булевой функции f).

Подчеркнем, что этот этап выполняется один раз и далее служит нам вечно. Поэтому время выполнения 1-го этапа на компьютере на имеет значе-ния – лишь бы программа закончила работу за конечное время (пусть даже несколько часов). Но тем не менее этот этап оказался самым сложный для разработки.

2. Для любой заданной нам строки значений булевой функции f в её таблице истинности осуществляем поиск в уже созданной базе данных. Ищем по воз-растанию длин l=1,2,3,… до тех пор, пока не найдем МДНФ, таблица истин-ности которой совпадает с заданной нам. МДНФ для данной БФ найдена.

Отметим еще важное достоинство нашего алгоритма. Как известно, МДНФ для заданной БФ в общем случае не единственна. Наш алгоритм по-иска отыскивает в базе данных не одну, а все МДНФ, равные заданной буле-вой функции. То есть дает полное решение этой классической задачи.

Материал поступил в редколлегию 03.04.2017

 

УДК 004.932

М.О. Селейкович

Научный руководитель: доцент кафедры «Информатика и программное обеспечение», к.т.н., А.О. Трубаков

[email protected]

ИССЛЕДОВАНИЕ МЕТОДОВ УВЕЛИЧЕНИЯ РАЗМЕРА

ИЗОБРАЖЕНИЙ

Объект исследования: алгоритмы увеличения размера растровых изображений.

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

 

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

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

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

Метод ближайшего соседа характеризуется появлением заметной ступенчатости даже при незначительном увеличении изображений. При наличии объектов с чёткими границами, не параллельными осям координат, даже увеличение в 1,5 раза приводит к заметному эффекту ступенчатости для данного метода. При увеличении до 3-4 раз билинейная и бикубическая интерполяция дают примерно одинаковое качество изображения. При увеличении в 7-8 раз билинейная интерполяция даёт гораздо более выраженный эффект ступенчатости. Если на изображении нет объектов с ярко выраженными границами, резких перепадов цветов, то качество, обеспечиваемое рассматриваемыми методами увеличения изображений, отличается в меньшей степени, иногда увеличение таких изображений увеличение в 2-3 раза не приводит к существенным различиям результатов для рассматриваемых интерполяционных методов (рис. 1).

При увеличении изображений в 2 раза билинейная интерполяции уступает методу ближайшего соседа по скорости примерно в 5,5 раз, бикубическая - в 24-28 раз. Примерно такое же различие в скорости при увеличении в 5 раз.

Рис. 1. Увеличение изображения без резких перепадов цветов в 3 раза/

С практической точки зрения, полученные результаты позволяют дать некоторые рекомендации по выбору алгоритмов увеличения изображений. Среди рассмотренных методов при увеличении изображения до 3-4 раз целесообразно выбирать билинейную интерполяцию, поскольку в таких ситуациях она не характеризуется существенными визуальными отличиями от бикубической, но работает намного быстрее. При более крупных масштабах целесообразна бикубическая интерполяция. Метод ближайшего соседа приемлем лишь при увеличении изображений без ярко выраженных границ объектов до 1,5-2 раз, и вовсе не рекомендуется использовать его при наличии ярко выраженных границ, даже если требуемое увеличение небольшое.

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

Материал поступил в редколлегию 28.04.2017

УДК 519.237.8

А.А. Смирнова

Научный руководитель: доцент кафедры «Информатика и программное обеспечение», к.т.н., Д.А. Коростелёв

[email protected]