- В диссертации установлена асимптотика логарифма количества отображений вершин булева куба в вершины произвольного графа, переводящих смежные вершины в смежные или совпадающие. Для отображений декартовых степеней частичных порядков в себя, удовлетворяющих части аксиом замыкания, также найдена асимптотика логарифма количества. Для получения оценок количества дискретных функций предложен метод жирных точек, при помощи которого получена асимптотика логарифма количества дискретных функций в нескольких семействах классов функций, сохраняющих двуместные предикаты.
- Исследована проблема тестирования бесповторных функций. Поставлена задача построения теста относительно бесповторной альтернативы. Для ее решения разработан метод квадратов существенности (для случая базиса всех функций двух переменных), который был обобщен на случай базисов, содержащих функции большего количества переменных. Получен порядок роста функций Шеннона длины теста в ряде базисов. Для элементарного базиса установлен линейный рост функции Шеннона. В базисе функций двух переменных построены последовательности функций с длиной проверяющего теста от линейной до квадратичной.
- Разработан метод разложения для схемного распознавания принадлежности дискретных функций, задаваемых столбцом значений, наследственным классам. При помощи этого метода получены верхние оценки 0(iV-^log!VloglogiV) для сложности распознавания монотонности, частичной монотонности и поляризуемости булевых функций (N - длина вектор-столбца). Доказана линейность сложности задач распознавания свойств доопре-делимости до линейной функции и бесповторности в произвольном конечном базисе. Исследована задача построения схем, распознающих наличие у булевой функции растущего количества фиктивных переменных.
[2] АЛЕКСЕЕВ В.Б. О числе монотонных fc-значных функций // Пробл. киберн. Вып. 28. М.: Наука, 1974. C. 5-24.
[3] АЛЕКСЕЕВ В.Б. О числе функций в классах, задаваемых центральными предикатами // Матем. заметки. 1985. 37. Вып. 6. C. 880-885.
[4] АЛЕКСЕЕВ В.Б. От метода Карацубы для быстрого умножения чисел к быстрым ал-горитмам для дискретных функций // Тр. матем. ин-та им. В.А.Стеклова. Т. 218. 1997. C. 20-27.
[5] ЗУЕВ Ю.А. Комбинаторно- вероятностные и геометрические методы в пороговой ло¬гике // Дискр. матем. 1991. 3. Вып. 2. C. 47-57.
[6] КАРАЦУБА А.А., ОФМАН Ю.П. Умножение многозначных чисел на автоматах // Докл. АН СССР. 1962. 145. No 2. C. 293-294.
[7] КАТЕРИНОЧКИНА Н.Н. Поиск максимального верхнего нуля монотонной функции ал¬гебры логики // Докл. АН СССР. 1975. 224. No 3. C. 557-560.
[8] Катериночкина Н.Н. Поиск максимального нуля для некоторых классов монотон-ных функций из классификации Поста // Журн. выч. матем. и матем. физики. 1988. 28. No 9. C. 1397–1406.
[9] Коробков В.К. К вопросу о числе монотонных функций алгебры логики // Дискр. анализ. Вып. 1, Новосибирск, 1965. C. 24–27.
[10] Коршунов А.Д. О числе монотонных булевых функций // Пробл. киберн. Вып. 38. М.: Наука, 1981. C. 5–108.
[11] Кузнецов А.В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики // Тр. матем. ин-та им. В.А.Стеклова. 1958. Т. 51. С. 186–225.
[12] Сапоженко А.А. Проблема Дедекинда и метод граничных функционалов // Матем. вопр. киберн. Физматлит. Вып. 9, 2000. С. 161–220.
[13] Сапоженко А.А. О поиске максимального верхнего нуля монотонных функций на ранжированных множествах // Журн. выч. матем. и матем. физики. 1991. 31. No 12. C. 1871–1884.
[14] Соколов Н.А. Поиск максимального верхнего нуля для одного класса монотонных дискретных функций // Докл. АН СССР. 1980. 251. No 5. C. 1077–1080.
[15] Соколов Н.А. О поиске максимального верхнего нуля для одного класса монотон-ных функций конечнозначной логики // Журн. выч. матем. и матем. физики. 1981. 21. No 6. C. 1552–1565.
[16] Чегис И.А., Яблонский С.В. Логические способы контроля работы электрических схем // Тр. матем. ин-та им. В.А.Стеклова. Том 51. 1958. C. 270–360.
[17] Черухин Д.Ю. Алгоритмический критерий сравнения булевых базисов // Матем. вопр. киберн. Вып. 8. M: Физматлит, 1999. C. 77–122.
[18] Яблонский С.В. Об алгopитмических тpудностях синтеза минимальных контакт-ных схем // Пpобл. кибеpн. Вып. 2. М.: Физматгиз, 1959. C. 75–121.
[19] DEDEKIND R. Uber Zerlegungen von Zahlen durch ihre grossten gemeinsamen Teilor, Festschrift Hoch. Braunschweig u. ges. Werke, II, 1887, S. 103-148.
[20] HANSEL G. Sur le nombre des fonctions booleennes monotones de n variables // C. R. Acad Sci. Paris, 1966, 262, p. 1088-1090. ( Русский перевод: Ансель Ж. О числе монотонных булевых функций п переменных // Киберн. сб., изд-во Мир. Новая серия. Вып. 5, 1968. C. 53-57).
[21] KLEITMAN D. On Dedekind’s problem: the number of monotone Boolean functions // Proc. Amer. Math. Soc, 1969, 21, N 3, p. 677-682. (Русский перевод: Клейтмен Д. О проблеме Дедекинда: число монотонных булевых функций // Киберн. сб., изд-во Мир. Новая серия. Вып. 7, 1970. C. 43-52).
[22] STRASSEN V. Gaussian elimination is not optimal // Numerische Mathematik, 13, H. 4, 1969, p. 354-356 (Русский перевод: HlTPACCEH В. Алгоритм Гаусса не оптимален // Киберн. сб., изд-во Мир. Новая серия. Вып.7, 1970. C. 67-70).
Список основных публикаций автора по теме диссертации
[23] ВОРОНЕНКО А.А. Бесповторность распознается схемами линейной сложности // Дискр. матем. 2005. 17. Вып. 4. C. 111-115.
[24] ВОРОНЕНКО А.А. О длине проверяющего теста для бесповторных функций в базисе {0,1,&,V,¬} // Дискр. матем. 2005. 17. Вып. 2. С. 139-143.
[25] ВОРОНЕНКО А.А. О количестве замкнутых многомерных монотонных отображений // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2002. No 2. C. 41-45.
[26] ВОРОНЕНКО А.А. О количестве замкнутых экстенсивных отображений // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2001. No 4. C. 46-48.
[27] ВОРОНЕНКО А. А. О количестве метрических дискретных функций п переменных // Матем. вопpосы кибеpнетики. М.: Физматлит, 1998. Вып. 7. C. 203-212.
[28] ВОРОНЕНКО А.А. О количестве метрических функций булева куба // Дискр. матем. 2001. 13. Вып. 4. C. 116-121.
[29] Вороненко А.А. О количестве многомерных монотонных экстенсивных отображе-ний // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2001. No 1. C.37–40.
[30] Вороненко А.А. О методе разложения для распознавания принадлежности инва-риантным классам // Дискр. матем. 2002. 14. Вып. 4. С. 110–116.
[31] Вороненко А.А. О проверяющих тестах для бесповторных функций // Матем. вопр. киберн. Вып. 11. М.: Физматлит, 2002. С. 163–176.
[32] Вороненко А.А. О распознавании наличия растущего числа фиктивных перемен-ных булевых функций // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2003. No 2. C. 45–46.
[33] Вороненко А.А. О росте количества дискретных липшицевых функций при рас-тущей размерности области определения // Вестн. Моск. ун-та. Сер. 1. Математика и механика, 2000. No 2. C. 3–7.
[34] Вороненко А.А. О сложности распознавания монотонности // Матем. вопр. киберн. Вып. 8. М.: Наука, 1999. C. 301–303.
[35] Вороненко А.А. О тестировании бесповторных функций // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2006. No 2. C. 45–48.
[36] Вороненко А.А. Об одном подходе к задачам оценки количества дискретных функ¬ций // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 2004. No 1. C. 42–47.
[37] Вороненко А.А. Об оценке длины проверяющего теста для некоторых бесповторных функций // Прикл. матем. и информатика. 2003. 15. C. 85–97.
[38] Вороненко А.А. Об условиях полной асимптотики мощности классов функций k-значной логики, сохраняющих конечноместный предикат // Вестн. Моск. ун-та. Сер. 15. Выч. матем. и киберн. 1997. No 3. C. 44–47.
[39] Вороненко А.А. Распознавание бесповторности в произвольном базисе // Прикл. матем. и информатика. 2006. 23. С. 67–84.