Введение к работе
Актуальность темы. Одной из основных задач математической кибернетики является оптимальная реализация дискретных отображений различными средствами 1.
Эта задача актуальна ввиду непрерывного возрастания потребности построения оптимальных устройств обработки цифровой информации.
Наиболее часто рассматривают следующие отображения: функции алгебры логики (булевы функции), функции fc-значной логики и ограниченно-детерминированные (автоматные) функции. Наиболее распространенными средствами реализации являются схемы различных видов: контактные и релейно-контактные схемы, схемы из функциональных элементов и схемы в автоматных базисах. В качестве критериев оптимальности схемы рассматривают сумму весов элементов (сложность), быстродействие и мощность.
Ввиду сложности задачи построения имеющей минимальную сложность схемы, реализующей произвольную функцию, часто ограничиваются изучением асимптотического поведения функционала, равного максимуму минимальных сложностей схем, реализующих функции из заданного класса.
В фундаментальных работах О. В. Лупанова 2 3 4 5 получены
'Яблонский СВ. Основные понятия кибернетики.// Проблемы кибернетики,
Вып. 2- М.:Физматгиз, 1959.- С.7-38.
2Лупанов О.В. О синтезе контактных схем // ДАН СССР.- 1958.- Т.119, N 1.- С.23-26.
3Лупанов О.Б. Об одном методе синтеза схем. // Изв. вузов, Радиофизика.-
1958.-Т.1, N.1.-C. 120-140.
Лупанов О.В. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. - М.: Физматгиз, 1960. - С. 61-80.
5Лупанов О.В. О сложности реализации функции алгебры логики релейно-
контактными схемами.// Проблемы кибернетики. Вып. П.- М.:Наука, 1964.-
асимптотики таких функционалов для класса всех булевых функций в случае контактных и ролейно-контактных схем, формул и схем в произвольном конечном полном базисе, элементы которого не обладают памятью.
В работе исследуются вопросы сложности реализации конечных языков в произвольном конечном алфавите. В качестве средств реализации рассматриваются языки, каждый из которых состоит из слова длины 1, и операции объединения, конкатенации и итерации языков. Рассматривается также реализация языков схемами, элементы которых реализуют эти операции. Такие схемы будем называть Л-схемами. Критерием оптимальности выбрана сложность (число операций). Большое внимание уделено вопросам реализации языков, являющихся множествами наборов, на которых булева функция принимает значение 1.
Из результатов А.Брауэра 6 и В.Штрассена 7 следуют оценки сложности реализации Л-схемами языков, состоящих из одного слова. При этом используется только операция конкатенации языков. Отметим также работы Ю.В.Мерекина 8 , который привел пример набора, на котором достигается оценка В.Штрассена, и В.В.Кочергина 9 , который получил асимптотически наилучшие
С. 25-48.
"Brauer A., On addition chains // Bull. Amer. Math. Soc., 1939, v.45, p. 736-739.
'Strassen V., B«rechnungen in partiellen Algebren endlichen Typs // J. of Computing, 1973, v. 11, p. 181-196.
*Мерекин Ю.В. Нижняя оценка сложности для схем конкатенации слов //
Дискретный анализ и исследование операций. — 1996. Т. 3 , N 1. — С. 52-56.
'Кочергин В.В. О сложности сложности реализации двоичных слов с заданным числом единиц схемами конкатенации // Труды III Международной конференции "Дискретные модели в теории управляющих систем" (22-27 июня 1998 г.). — М.: Диалог-МГУ, 1998. — С. 58-62.
и наилучшие по порядку оценки сложности реализации двоичных слов с заданным числом единиц схемами конкатенации.
Целью работы является исследование асимптотического поведения сложности реализации конечных языков в произвольном конечном алфавите регулярными выражениями и R -схемами.
Методы исследования. В работе использованы известные и разработанные автором методы асимптотической теории сложности управляющих систем, методы теории булевых и fc-значных функций и других разделов дискретной математики и математической кибернетики.
Научная новизна. Все результаты диссертации являются новыми. Перечислим основные из них.
Предложен наилучший по порядку метод реализации произвольных конечных языков в произвольном конечном алфавите регулярными выражениями.
Разработан асимптотически наилучший метод реализации произвольных конечных языков в произвольном конечном алфавите R -схемами.
Получены асимптотически наилучшие и наилучшие по порядку оценки сложности реализации регулярными выражениями и R -схемами языков заданной мощности и симметрических языков.
Теоретическая и практическая ценность. Диссертация носит теоретический характер. Исследовано асимптотическое поведение сложности реализации произвольных конечных языков в произвольном конечном алфавите регулярными выражениями и R -схемами. Получены также результаты о сложности реализации некоторых классов языков. Результаты работы и предложенные методы найдут применение в области оптимальной реализации языков с использованием операций объединения, конкатенации
и итерации.
Апробация работы и публикации. Результаты диссертации в 1996-1999 годах докладывались на XI международной конференции по теоретическим проблемам кибернетики (Ульяновск, 1996 г.), на VI международном семинаре по дискретной математике и ее приложениям (Москва, 1998г.) и на XII международной конференции по теоретическим проблемам кибернетики (Нижний Новгород, 1999 г.).
Все основные результаты диссертации опубликованы. По теме диссертации автором опубликованы 3 печатные работы. Работ, выполненных в соавторстве, нет.
Структура работы. Диссертация состоит из введения, двух глав и списка литературы. Глава 1 разбита на 6 параграфов, глава 2 - на 4 параграфа. Список литературы содержит 21 наименование. Общий объем работы составляет 54 страницы текста. Изложение иллюстрируют 2 рисунка.