Об особенностях асимптотического поведения сложности реализации к-значных и автоматных функций схемами в произвольном конечном базисе тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА 1. О СЛОЖНОСТИ РЕАЛИЗАЦИИ К-ЗНАЧНЫХ ФУНКЦИЙ СХЕМАМИ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ В ПРОИЗВОЛЬНОМ ПОЛНОМ КОНЕЧНОМ БАЗИСЕ

§ 1. Реализация булевых функций

§ 2. Реализация квазибулевых функций.

§ 3. Реализация к-значных функций

§ 4. Оптимальные базисы и сильно существенные системы к -значных функций

§ 5 Оценки числа сильно существенных функций.

§ 6 Об оптимальности почти всех &-значных базисов.

§ 7 О сравнении булевых и к -значных базисов

ГЛАВА 2. О СЛОЖНОСТИ РЕАЛИЗАЦИИ АВТОМАТНЫХ ФУНКЦИЙ СХЕМАМИ В ФУНКЦИОНАЛЬНО ПОЛНЫХ БАЗИСАХ

§ 8. Основные определения и формулировка результатов.

§ 9. Моделирование продукций Поста схемами в функционально полных базисах

§ 10. Описание автомата И

§11. Свойства схем в базисе Ве

§ 12. Доказательства основных результатов главы 2.

ГЛАВА 3. РЕАЛИЗАЦИЯ ФУНКЦИЙ СХЕМАМИ, В КОТОРЫХ ДОПУСТИМЫ СУЩЕСТВЕННЫЕ ЦИКЛЫ

§ 13. Реализация функций правильными схемами.

§ 14. Реализация функций С-схемами

Оптимальная реализация дискретных функциональных отображений различными средствами является одной из основных областей математической кибернетики [39]. Актуальность этой задачи обусловлена все возрастающей потребностью построения оптимальных устройств обработки цифровой информации. В качестве отображений наиболее часто рассматривают функции алгебры логики (булевы функции), функции /г-значной логики (/с-значные функции, функции из Рк) и ограниченно-детерминированные (автоматные) функции. Наиболее распространенными средствами реализации являются схемы различных видов: контактные и релейно-контактные схемы, схемы из функциональных элементов и схемы в автоматных базисах. В качестве критериев оптимальности схемы рассматривают сумму весов элементов (сложность), быстродействие и мощность.

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

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

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

Одной из первых работ в области синтеза управляющих систем является широко известная работа К. Шеннона [49].

В фундаментальных работах О. Б. Лупанова [9-17] получены асимптотики функций Шеннона для класса всех булевых функций в случае контактных и релейно-контактных схем, формул и схем в произвольном конечном полном базисе, элементы которого не обладают памятью.

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

В последнее время возрос интерес к проектированию устройств, математической моделью функционирования которых являются к-значные функции (см., например, [44]). Работ, в которых рассматриваются вопросы реализации функций /с-значной логики схемами из функциональных элементов и формулами, мало. , Здесь следует отметить работы C.B. Яблонского, Е.Ю. Захаровой, Е.И. Кри-чевского и С.А. Ложкина, в которых получены нижние оценки и асимптотики функции Шеннона для некоторых базисов.

Для практических приложений наибольший интерес представляет проектирование устройств, математической моделью функционирования которых являются автоматные функции. Публикаций по вопросам сложности реализации автоматных функций схемами и формулами в автоматных базисах довольно мало. Первый результат в этом направлении опубликовал Б.А. Трахтенброт [35], который получил асимптотику функции Шеннона для случая реализации автоматных функций в алфавите {0,1} схемами в базисах, состоящих из функциональных элементов и элемента единичной задержки, при некоторых соотношениях между мощностями входных и выходных алфавитов и весом реализуемых автоматных функций. Отметим, также, раннюю работу автора [19], в которой доказана алгоритмическая неразрешимость задачи нахождения асимптотического поведения функции Шеннона в случае произвольных автоматных базисов.

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

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

Все результаты диссертации являются новыми. Перечислим основные из них.

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

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

Доказано, что для любого к > 3 почти любой конечный полный базис из функциональных элементов является оптимальным (асимптотическое поведение функции Шеннона определяется минимальным "приведенным" весом элементов базиса). Отсюда, в частности, следует, что предложенный метод синтеза для почти любого базиса является асимптотически наилучшим (без использования нижней оценки из [43]). Отметим, что доля базисов, не являющихся оптимальными, убывает трижды экспоненциально с ростом максимального числа входов элементов базиса и более чем дважды экспоненциально с ростом значности.

С использованием построенных автором сильно существенных систем /е-значных функций растущей мощности и разработанного автором метода получения нижних оценок для любого к > 3 приведены примеры конечных полных базисов из функциональных элементов таких, что константа в асимптотической формуле для функции Шеннона в этих базисах зависит от параметров (вес, число входов, реализуемая функция) к — 1 элементов. Для любых к > 3 и с > 1 построены базисы такие, что константа в асимптотической формуле для функции Шеннона в этих базисах: в с раз превышает максиупум приведенных весов элементов базиса.

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

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

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

Диссертация носит теоретический характер. Полученные в ней результаты для любого к > 3 дают довольно полное описание асимптотического поведения функции Шеннона в случае реализации /г-значных функций схемами в произвольном полном конечном базисе из функциональных элементов. Получены новые результаты в малоисследованном (и как показало время трудноисследуемом) случае реализации функций схемами в произвольном конечном автоматном базисе. Полученные результаты и методы найдут применение в развивающейся области проектирования устройств, математической моделью функционирования которых являются к -значные и автоматные функции.

1. Захарова Е.Ю. Реализация функций из Д формулами (к >3). // Математические заметки, том 11, вып. 1, 1972, С. 99-108.

2. Касим-Заде О.М. О синтезе сетей из функциональных элементов // Докл. РАН.- 1996, Т.348, N 2.- С. 159-161.

3. Касим-Заде О.М. О сложности параметрических .представлений булевых функций // Математические вопросы кибернетики вып. 7. М.: Наука, Физматгиз, 1998, —С. 85-160.

4. Кратко М.И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов. // Докл. АН СССР. — 1964. — Т. 155, N 1. — С. 35-37.

5. Кричевский P.E. О реализации функций суперпозициями. // Проблемы кибернетики. Вып. 2. -М.: Физматгиз, 1959. С. 123138.

6. Кудрявцев В.Б. О мощностях множеств предполных множеств некоторых функциональных систем связанных с автоматами. // Проблемы кибернетики. Вып. 13. М.: "Наука", 1965. - С. 4574.

7. Ложкин С.А. О сложности реализации функций fc-значной логики формулами и квазиформулами.// Проблемы теоретической кибернетики Тезисы докладов XI Международной конференции 10-14 июня 1996 г.- М., 1996.- С. 125-127.

8. Ложкин С.А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов.// Математические вопросы кибернетики, Вып. 6.- М.-.Наука, 1996.- С. 189-214.

9. Лупанов О.Б. О синтезе контактных схем. // Докл. АН СССР. — 1958.- Т.119, N 1 — С. 23-26.

10. Лупанов О.Б. Об одном методе синтеза схем. // Изв. вузов, Радиофизика.- 1958.- T.l, N.1. С. 120 140.

11. Лупанов О.Б. О сложности реализации функций алгебры логики формулами. // Проблемы кибернетики. Вып. 3. М.: Физмат-гиз, 1960. - С. 61-80.

12. Лупанов О.Б. Об одном классе схем из функциональных элементов (формулы с частичной памятью). Проблемы кибернетики. Вып. 7 М.: Физматгиз, 1962.- С. 61-114.

13. Лупанов О.Б. О синтезе некоторых классов управляющих систем. // Сб."Проблемы кибернетики", вып. 10, М., 1963, Физматгиз, С. 63 97.

14. Лупанов О.Б. О сложности реализации функции алгебры логики релейно-контактными схемами.// Проблемы кибернетики. Вып. 11.- М.гНаука, 1964.- С. 25-48.

15. Лупанов О.Б. Об одном подходе к синтезу управляющих систем принципе локального кодирования.// Сб."Проблемы кибернетики", вып. 14, М., 1965, Физматгиз, С. 31 - 110.

16. Лупанов О.Б. О схемах из функциональных элементов с задержками. // Проблемы кибернетики. Вып.23.- М., Наука, 1970.- С. 43-81.

17. Лупанов О.Б. Асимптотические оценки сложности управляющих систем.- М.:Изд-во Моск. ун-та, 1984.

18. Мальцев А.И. Алгоритмы и рекурсивные функции. — Наука, М., 1965.

19. Орлов В.А. Алгоритмическая неразрешимость задачи нахождения асимптотического поведения функции Шеннона при реализации ограниченно-детерминированных операторов схемами в произвольном базисе. // Докл. АН СССР. — 1971. — Т. 196, N5.-0. 1036-1039.

20. Орлов В.А. Об особенностях поведения функции Шеннона в случае автоматных базисов. // Математические заметки.— 1972. — Т. 11, вып. 1. — С. 73-82.

21. Орлов В.А. О сложности реализации ограниченно-детерминированных операторов схемами в автоматных базисах. // Сб. "Проблемы кибернетики". — М.: Изд-во Физматгиз. 1973. вып. 26. — С. 141-182.

22. Орлов В.А. Простое доказательство алгоритмической неразрешимости некоторых задач о полноте автоматных базисов. // Кибернетика. 1973. N 4. - С. 109 113.

23. Орлов В.А. О двух классах схем в автоматных базисах. // Кибернетика. — 1981. — N 5. — С. 134-135.

24. Орлов В.А. О полноте автоматных базисов. // Межвузовский сборник научных трудов "Методы и системы технической диагностики". — Саратов: Изд-во Саратовского ун-та. 1993. —вып. 18. — С. 134.

25. Орлов В.А. О реализации функций из Д схемами в произвольном базисе. // Тезисы докладов XI Международной конференции "Проблемы теоретической кибернетики". Ульяновск: Изд-во Рос. гос. гуманит. ун-та М. 1996. С. 154 155.

26. Орлов В.А. О полноте систем конечных автоматов. // Дискретная математика. — 1997. — Т.9, вып. 2. — С. 74-78.

27. Орлов В.А. Реализация функций из Д схемами в произвольном базисе из функциональных элементов. // Докл. РАН. — 1998.Т. 359, N 3. — С. 308 309.

28. Орлов В.А. О сильно существенных системах функций изДискретная математика. — 1998. — Т. 10, вып. 2. — С. 120-127.

29. Орлов В.А. О сложности реализации функций fc-значной логики схемами и формулами в функционально полных базисах. // Дискретный анализ и исследование операций. — 1998. Серия 1— Т. 5 , N 2. — С. 78-89.

30. Орлов В.А. О реализации k-значных функций схемами из функциональных элементов. // Математические заметки. — 1998.Т. 64, вып. 3. — С. 431-436.

31. Орлов В.А. О сложностной многопараметричности fc-значных логик. // Труды III Международной конференции "Дискретные модели в теории управляющих систем" ( 22 27 июня 1998г. )1998. — М., Диалог МГУ — С. 84-86.

32. Орлов В.А. Об оптимальности почти всех базисов из Д. // Докл. РАН. — 1998. — Т. 363, N 5. — С. 602-603.

33. Орлов В.А. О реализации функций схемами и формулами в функционально полных базисах. // Докл. РАН. — 1999. — Т. 365, N 6. — С. 734-735.

34. Соловьев H.A. К вопросу о существенной зависимости функций алгебры логики // Проблемы кибернетики. Вып. 9.- М.: Физ-матгиз, 1963.- С. 333-335.

35. Трахтенброт Б.А., Асимптотическая оценка сложности логических сетей с памятью. // Докл. АН СССР. — 1959. — Т. 127, N 2. — С. 281-284.

36. Трахтенброт Б.А., О сложности схем, реализующих многопараметрические семейства операторов. // Сб. "Проблемы кибернетики". — М.: Изд-во "Наука". 1964. — вып. 12. — С. 99-112.

37. Трахтенброт Б.А., Барздинь Я.М., Конечные автоматы (Поведение и синтез), М., "Наука", 1970.

38. Яблонский C.B., Функциональные построения в /г-значной логике, // Труды Матем. ин-таим. В.А. СтекловаЫ, 1958, С. 5-142.

39. Яблонский C.B., Основные понятия кибернетики.// Проблемы кибернетики, Вып. 2.- М.:Физматгиз, 1959.- С. 7-38.

40. Яблонский C.B. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики, Вып. 2.-М.:Физматгиз, 1959.- С. 75-121.

41. Яблонский C.B. Введение в дискретную математику. — Наука, М., 1979.

42. Яблонский C.B. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов // Banach Center Pub.-1982.- N 7.- P. 11-19.

43. Яблонский C.B. Нижние мощностные оценки для сложности реализации функций из Рк схемами из функциональных элементов в произвольном базисе // Дискретная математика, — 1994 — т. 6, вып.4 С. 3-9.

44. Яблонский C.B., Гаврилов Г.П., Набебин A.A. Предполные классы в многозначных логиках. — МЭИ, М., 1997.126

45. Burks A.W., Wright J.B., Theory of logical nets. // Proceedings IRE, 41, 1953, p. 1357-1365 (русский перевод: Кибернетич. сб. вып. 46, ИЛ, 1962, С. 33-57).

46. Minsky M.L., Recursive unsolvability of Post's problem of "TAG" and topics in theory of Turing machines. // Ann. Math. 74, 1961, p. 437-455.

47. Piccard S., Sur les fonctions definies dans les ensembles finis quelconque. // Fund. Math., 24, 1935, p. 183-185.

48. Post E.L., Finite combinatory processes-formulation. //J. Symbolic Logic 1, 1936, p. 103-105.

49. Shannon C.E. The synthesis of two-terminal switching circuits // Bell Syst. Techn., 1949. V.28, N1. P. 59-98.

50. Slupecki J., Kriterium pelnosci wielowar-tosciowych systemow logiki zdan. // Comptes rendus de seances de la Société de Sciences et des Lettres de Varsovie, Cl. III, 32, 1939, p. 102-109.