Введение к работе
Актуальность темы исследований. Теория дискретных функций является важим разделом современной математики, тесно связанным с такими разделами, как алге-эа, математическая логика, теория чисел. Интерес к теории дискретных функций также іязан с созданием различных вычислительных систем.
Среди характеристик любого математического объекта важную роль играют его коли-хтвенпые характеристики. Для классов дискретных функций одной из наиболее важ-ых количественных характеристик является число ф(п) функций в классе, зависящих от фиксированных переменных. Как показал О.Б.Лупанов, наибольшая сложность схем, зализующих булевы функции из некоторого класса связана с асимптотикой логарифма пела функций в этом классе, зависящих от п переменных.
Трудность задачи оценки числа дискретных функций показало уже исследование их пела в предполных классах в алгебре булевых функций, а именно, в классе монотонных ункций. К настоящему времени получена асимптотика мощности классов монотонных лиевых функций (А.Д.Коршуновым) и асимптотика логарифма мощности для классов значных монотонных функций (В.Б.Алексеевым).
Наряду с отношением порядка часто рассматриваются и другие отношения. Ра-:е оценивалась асимптотика логарифма для замкнутых классов булевых функций от-эсителыго различных операций (С.В.Яблонским, О.Б.Лупановым, Ю.В.Кузнецовым). .Б.Алексеев получил асимптотику логарифма для мощности всех предполных классов значной логики. Также изучалась задача о числе различных полиномов в Р* при составам к. С.Б.Гашков получил асимптотику функции Шеннона для приближения нелрерыв-ах функций на отрезке полиномами, а Г.Г.Аманжаев - для приближения дискретными ункциями, причем для получения нижней оценки в обоих случаях потребовалось найти :имптотику логарифма мощности соответствующих классов функций. Ряд работ был по-іящен изучению вопроса о существовании дискретных отображений, обладающих теми га иными свойствами. В настоящей работе рассматриваются вопросы оценки количества декретных функций, для которых близость наборов из области определения порождает газость значений функции.
Методы исследования. В работе используются методы теории функциональных систем, комбинаторики, алгебры и теории графов.
Научная новизна. Все основные результаты являются новыми. В диссертации получены следующие основные результаты:
-
разработаны методы проверки условия \ogk \Fn\ ~ кп при п —> со для классов функций fc-значной логики, сохраняющих конечномествый предикат,
-
найдена асимптотика логарифма мощности для классов функций, сохраняющих предикаты, удовлетворяющие части аксиом монотонности;
-
построены методы оценки асимптотики логарифма мощности для классов метрических дискретных функций;
-
найдена асимптотика логарифма мощности для классов липшицевых дискретных функций при растущем числе переменных;
-
получены оценки для роста числа липшицевых дискретных функций при фиксированной размерности и растущей значносги области определения;
-
получена асимптотика логарифма числа многомерных отображений, ие увеличивающих расстояния.
Практическая и теоретическая ценность. Диссертация носит теоретический ха рактер. Полученные результаты и методы могут быть использованы для получения асимптотических оценок числа различных дискретных объектов в таких приложениях, как проектирование сложных управляющих систем и статистическая физика.
Апробация работы. Результаты работы докладывались на школе-семинаре (Мо сква,1995), на международной конференции по проблемам теоретической кибернетики (Ульяновск,1996), на семинарах по математическим вопросам кибернетики под руководством чл.-корр. РАН С.В.Яблонского, на других школах и семинарах.
Публикации. По теме диссертации имеется 2 публикации, список которых приводится в конце автореферата.
Структура и объем работы. Диссертация состоит из введения, трех глав и спискг литературы. Первая глава разбита на 4 параграфа, вторая - на 5 параграфов, третья -на 3. Объем работы 82 страницы. Список литературы содержит 34 наименования.