Поиск по всему репозиторию:

Метод нахождения булевой формулы многоугольника в дизъюнктивной нормальной форме без использования дополнительных предикатных переменных

Thumbnail
Открыть/скачать файлы документа
Автор
Дата издания
2012
Издательство
БрГТУ
УДК
004.5
 
621.38
Библиографическое описание
Бутов, А. А. Метод нахождения булевой формулы многоугольника в дизъюнктивной нормальной форме без использования дополнительных предикатных переменных / А. А. Бутов // Вестник БрГТУ. Серия : Физика, математика, информатика. – 2012. – № 5. – С. 22–25.
Аннотация
Предложен приемлемый на практике метод решения задачи построения булевой формулы многоугольника в дизъюнктивной нормальной форме. Метод основан на последовательном формировании выпуклых компонентов, которые представляют в искомой формуле отдельные элементарные конъюнкции и покрывают в совокупности все точки плоскости, принадлежащие исходному многоугольнику. Достоинством метода является присутствие в полученной формуле только тех предикатных переменных, которые связаны с полуплоскостями, порождаемыми лишь сторонами многоугольника. Метод может быть использован, в частности, в системах автоматизированного проектирования топологии интегральных схем.
Аннотация на другом языке
A feasible in practice method of the solution of the constructing a Boolean formula of a polygon in the disjunctive normal form is proposed. The method is based on a sequential formation of convex components, which represent in the desired formula individual elementary conjunctions and cover in aggregate all the points of the plane belonging to the original polygon. The advantage of the method is the presence in the resulting formula only the predicate variables that are associated with the half-planes generated only by the sides of the polygon. The method can be used, in particular, in the systems computer-aided design of integrated circuits topology.
URI документа
https://rep.bstu.by/handle/data/1067
Документ расположен в коллекции