РЕШЕНИЕ БОЛЬШИХ СИСТЕМ БУЛЕВЫХ УРАВНЕНИЙ
Аннотация
Многие проблемы анализа, синтеза и диагностики неисправностей логических схем, а также проблемы дедуктивного вывода, распознавания образов и защиты информации сводятся к решению комбинаторных задач с неизбежным перебором вариантов. Значительная часть таких задач формулируется на языке логических уравнений. В статье рассматриваются два класса систем, содержащих сотни булевых уравнений и переменных: большие системы логических уравнений с ограниченным числом переменных в каждом из них (БСЛУ) и системы линейных логических уравнений (СЛЛУ). Для решения таких систем в лаборатории логического проектирования ОИПИ НАН Беларуси разработана серия комбинаторных методов. Результаты испытаний этих методов на потоке псевдослучайных систем свидетельствуют об их высокой практической эффективности.
Список литературы
1. Теория дискретных управляющих устройств / Под ред. А.Д. Закревского и И.В. Прангишвили. – М.: Наука, 1982.
2. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. – М.: Энергия, 1970.
3. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. – М.: Наука, 1971.
4. Основы технической диагностики / Под ред. П.П. Пархоменко. – М.: Энергия, 1976.
5. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.
6. Математические и компьютерные основы криптологии / Ю.С. Харин, В.И. Берник, Г.В. Матвеев, С.В. Агиевич. – Мн.: ООО «Новое знание», 2003.
7. Алгоритмы решения логико-комбинаторных задач: Сб. науч. тр. / Под ред. А.Д. Закревского. – Мн.: Ин-т техн. кибернетики АН БССР, 1975-1980. – Вып. 1-6.
8. Закревский А.Д. Некоторые комбинаторные задачи искусственного интеллекта // Семиотика и информатика. М.: ВИНИТИ, 1980. – Вып. 15. С. 3-17.
9. Закревский А.Д. Комбинаторика логического проектирования // Автоматика и вычислительная техника. 1990. – № 2. – С. 68-79.
10. Закревский А.Д. Комбинаторные задачи над логическими матрицами в логическом проекти-ровании и искусственном интеллекте // Успехи современной радиоэлектроники. 1998. № 2. С. 59-67.
11. Поттосин Ю.В. Задачи теории графов в логическом проектировании // Логическое проектирование. – Мн.: Ин-т техн. кибернетики НАН Беларуси, 2001. – Вып. 6. – С. 106-130.
12. Распознавание образов / Под ред. П. Колерса и М. Идена. – М.: Мир, 1970.
13. Закревский А.Д., Карелина А.В., Печерский Ю.Н. Всесоюзная школа-семинар по логико-комбинаторным методам в распознавании образов // Информационные материалы: Кибернетика. – М.: АН СССР, 1978. – № 4(104). – С. 16-18.
14. Zakrevskij A.D. A common logical approach to data mining and pattern recognition // Data Mining and Knowledge Discovery Approaches Based on Rule Induction Techniques. – Dordrecht: Kluwer Academic Publishers, 2004. – P. 1-42.
15. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980.
16. Закревский А.Д. О приближенных методах решения логических задач // Вопросы синтеза цифровых автоматов. – М.: Наука, 1967. – С. 5-13.
17. Эйнгорин М.Я. О системах уравнений алгебры логики и синтезе дискретных управляющих схем с обратными связями // Известия вузов. Радиофизика. – 1958. – Т. 1. – № 2. – С. 169-184.
18. Rudeanu S. Boolean functions and equations. – Amsterdam-London-New York: North-Holland and American Elsevier, 1974.
19. Закревский А.Д. Логические уравнения. – Мн.: Наука и техника, 1975; М.: УРСС, 2003. – 2-е изд.
20. Уткин А.А. Решение логических уравнений // Автоматизация логического проектирования. – Мн.: Ин-т техн. кибернетики АН БССР, 1982. – С. 41-58.
21. Bochmann D., Zakrevskij A.D. Posthoff Ch. Boolesche Gleichungen. – Berlin: VEB Verlag Technik, 1984.
22. Закревский А.Д. Решение логических уравнений // Логическое проектирование. – Мн.: Ин-т техн. кибернетики НАН Беларуси, 2001. – Вып. 6. – С. 51-68.
23. Закревский А.Д. Логические уравнения с приложениями в автоматизированном проектировании и управлении // Автоматика и телемеханика, 2004. – № 4. – С. 173-185.
24. Закревский А.Д. Логический синтез каскадных схем. – М.: Наука, 1981. – 416 с.
25. Закревский А.Д. ПЛМ и матричные логические уравнения // Automatentheorie und Ihre Anwendung. Seminarbericht, Sekt. Math. der Humboldt-Universitet. – Berlin, 1984 Januar. – S. 26-34.
26. Бибило П.Н. Декомпозиция булевых функций на основе решения логических уравнений // Известия Академии наук. Теория и системы управления. – 2002. – № 4. – I. – С. 53-64; 2002. – № 5. – II. – С. 57-63; 2003. – № 6. – III. – С. 88-97.
27. Zakrevskij A.D. Pattern recognition as solving logical equations. – Special Issue 1999 – SSIT'99 (AMSE). – P. 125-136.
28. Лукасевич Я. Аристотелевская силлогистика с точки зрения современной формальной логики. – М.: ИЛ, 1959.
29. Закревский А.Д. К формализации полисиллогистики // Логический вывод. – М.: Наука, 1979. – С. 300-309.
30. Закревский А.Д. Матричный аппарат логического вывода в конечных предикатах // Философские основы неклассических логик: Тр. науч.-иссл. семинара по логике. – М.: Ин-т философии АН СССР, 1990. – С. 70-80.
31. Закревский А.Д. К решению систем логических уравнений // Принципы построения сетей и систем управления. – М.: Наука, 1964. – С. 48-55.
32. Закревский А.Д. Проверка тождеств в алгебре логики // Логический язык для представления алгоритмов синтеза релейных устройств. – М.: Наука, 1966. – С. 159-163.
33. Zakrevskii A.D., Kalmykova A.Yu. The solution of systems of logical equations // LYaPAS: A programming language for logic and coding algorithms – New-York and London: Academic Press, 1969. – P. 193-206.
34. Нильсон Н. Искусственный интеллект. Методы поиска решений. – М.: Мир, 1973.
35. Zakrevskij A., Zakrevski L. Solving systems of logical equations using search tree minimization technique // Proceedings of the PDPTA’02 International Conference, June 24-27, 2002, Las Vegas, USA. – P. 1145-1150.
36. Закревский А.Д., Василькова И.В. Решение больших систем логических уравнений: метод минимизации дерева поиска // Вестник Томского государственного университета. Приложение № 1 (II), сентябрь 2002. – С. 260-265.
37. Zakrevskij A., Vasilkova I. Reducing search trees to accelerate solving large systems of Boolean equations // Boolean Problems. 5th International Workshop, Sept. 19-20, 2002, Freiberg (Sachsen). – P. 71-76.
38. Закревский А.Д., Василькова И.В. Минимизация дерева поиска корней больших систем логических уравнений // Автоматика и вычислительная техника. – 2003. – № 1. – C. 3-11.
39. Cherry C., Vaswani P.K. A new type of computer in propositional logic, with greatly reduced scanning procedures // Information and control. – 1961. – V. 4. – № 3. – P. 155-168.
40. Zakrevskij A. Reduction algorithms for solving large systems of logical equations // Computer Science Journal of Moldova. – 2000. – V. 8. – № 1. – P. 3-15.
41. Zakrevskij A., Vasilkova I. Reducing large systems of Boolean equations // 4th International Workshop on Boolean Problems, September 21-22, 2000. – Freiberg, Germany. – P. 21-28.
42. Закревский А.Д., Василькова И.В. Криптоанализ машины Hagelin – метод решения системы логических уравнений // Комплексная защита информации. – Мн.: Ин-т техн. кибернетики АН Беларуси, 1999. – Вып. 2. – С. 129-138.
43. Закревский А.Д. Метод «отраженных волн» решения логических уравнений // Прикладные аспекты теории автоматов. Тр. III Междунар. семинара. Т. 1. – Варна: БАН, 1975. – С. 81-84.
44. Baumann M., Rohde R., Barthel R. Cryptoanalysis of the Hagelin M-209 Machine // 3rd International Workshop on Boolean Problems, Sept. 17-18, 1998. – Freiberg (Sachsen). – P. 109-116.
45. Закревский А.Д. Решение систем логических уравнений методом локальной редукции // Доклады НАН Беларуси, 1999. – Т. 43. – № 5. – С. 5-8.
46. Закревский А.Д., Василькова И.В. Локальная редукция больших систем логических уравнений // Логическое проектирование. – Мн: Ин-т техн. кибернетики АН Беларуси, 1999. – Вып.4.– С. 91-101.
47. Закревский А.Д. Редукция больших систем логических уравнений: метод силлогизмов // Автоматика и вычислительная техника. – 2000. – № 5. – С. 32-39.
48. Закревский А.Д., Торопов Н.Р. Полиномиальная реализация частичных булевых функций и систем. – Мн.: Ин-т техн. кибернетики НАН Беларуси, 2001. – 200 с.
49. Zakrevskij A.D. Looking for shortest solutions of systems of linear logical equations: theory and applications in logic design // 2 Workshop «Boolesche Probleme», 19 – 20 Septem-ber 1996. Freiberg (Sachsen). – P. 63-69.
50. Закревский А.Д., Торопов Н.Р. Поиск кратчайшего решения системы линейных логических уравнений // Автоматизация проектирования дискретных систем: Мат. Второй междунар. конф. (CAD DD’97). – Мн.: Ин-т техн. кибернетики НАН Беларуси.– Т. 2. – С. 16-23.
51. Zakrevskij A.D., Zakrevski L. Optimizing solutions in a linear Boolean space – a decomposition method // Proc. of STI '2003, Orlando, Florida, USA, July 2003. – P. 276-280.
52. Закревский А.Д. Оптимизация решений в линейном булевом пространстве – методы декомпозиции // Автоматика и вычислительная техника. – 2003. – № 5. – C. 28-36.
53. Закревский А.Д. Комбинаторные методы оптимизации решений систем линейных логических уравнений // Вестник Томского государственного университета. Приложение. № 6. – Сентябрь 2003. – С. 4-8.
54. Закревский А.Д. Эффективные методы нахождения кратчайших решений систем линейных логических уравнений // Проблемы управления. – 2003. – № 4. – C. 16-22.
55. Zakrevskij A.D. Randomization of a parallel algorithm for solving undefined systems of linear logical equations // Proceedings of the International Workshop on Discrete-Event System Design – DESDes’04, 2004. – University of Zielona Gora Press, Poland. – P. 97-102.
56. Закревский А.Д., Василькова И.В. Прогнозирование затрат времени на реализацию комбинаторных алгоритмов // Методы логического проектирования. – Мн.: ОИПИ НАН Беларуси, 2003. – Вып. 2. – С. 26-32.
57. Закревский А.Д. Метод решения несовместных систем линейных логических уравнений // Вестник Томского государственного университета. Приложение. № 9(1). Сентябрь 2004. – С. 13-18.
58. Zakrevskij A.D. Solving inconsistent systems of linear logical equations // 6th International Workshop on Boolean Problems, September 23-24, 2004. Freiberg (Sachsen). – P. 183-190.
Рецензия
Для цитирования:
Закревский А.Д. РЕШЕНИЕ БОЛЬШИХ СИСТЕМ БУЛЕВЫХ УРАВНЕНИЙ. Информатика. 2004;(4(04)):42-53.
Просмотров: 973
Послать статью по эл. почте 