Участник:SapozhenkoAA — различия между версиями

Версия 21:41, 26 декабря 2013

Сапоже́нко Александр Антонович

Биография

Александр Антонович Сапоженко родился в Ленинграде 4 апреля 1939 г. В 1964 г. окончил Радиотехнический факультет Московского физико-технического института, а в 1967 г. аспирантуру МФТИ. В 1967 г. защитил кандидатскую диссертацию. С 1967 по 1971 г. работал в институте Математики Сибирского отделения АН СССР. С мая 1971 г. работает на факультете Вычислительной математики и кибернетики Московского государственного университета им. М.В.Ломоносова. 1993 г. - доктор ф-м. н., с 1997 г. профессор кафедры математической кибернетики факультета ВМиК МГУ.

Области научных интересов и полученные результаты

Основные научные интересы А.А. Сапоженко относятся к минимизации булевых функций, случайным графам, комбинаторике, алгебре логики. В кандидатской диссертации «Геометрические свойства функций алгебры логики», защищенной им в 1967 г., получены точные значения радиуса и диаметра графа случайной булевой функции, найдена асимптотика диаметра ее графа случайной булевой функции, найдена асимптоика диаметра ее графа интервалов, описано строение компонент этого графа. Эти исследования были затем продолжены учениками А.А.Сапоженко, а также рядом зарубежных авторов.

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

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

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

Сапоженко А.А. является автором более 120 научных публикаций, учебных пособий, монографий и одного изобретения. Сборник задач по дискретной математике, написанный им в соавторстве с Г.П.Гавриловым, является одним из основных учебных пособий ля студентов, изучающих этот предмет в университетах и технических ВУЗах. Он был дважды издан на русском языке (в 1977, 1992 и 2004гг. Наука) и переведен на английский (1989 МИР, 1996 Kluver), испанский (1980 МИР) и венгерский (1981 Muszaki Konyvkiado) языки. Под руководством А.А.Сапоженко было защищено девять кандидатских диссертаций.

Лекционные курсы

• Основы кибернетики (2 поток)

Спецсеминары

• Дискретная математика и математическая кибернетика
• Дискретный анализ

Избранные публикации

1. Метрические свойства почти всех булевых функций // Сб. Дискретный анализ Новосибирск — 1967 — вып. 10 — С.91-102.
2. Диссертация "Метрические свойства почти всех булевых функций" // Новосибирск, ИМ СО АН СССР — 1967 — 70с.
3. О наибольшей длине тупиковых д.н.ф. у почти всех функций алгебры логики // Математические заметки — 1968 — v.4, No.6, — C.649-658.
4. Порядок окрестности максимальных интервалов у почти всех булевых функций // Доклады АН СССР — 968 — т. 180, No.1, C.526-530.
5. Об одном доказательстве верхней оценки сложности минимальной д.н.ф. // Тезисы докладов Всесоюзной конференции по проблемам теоретической кибернетики — Новосибирск — 1969 — С.108.
6. О сложности д.н.ф., получаемых с помощью градиентного алгоритма // Сб. Дискретный анализ — Новосибирск- Вып. 21, -С.62-71.
7. О существенных переменных булевых функций // Сб. Дискретный анализ — Новосибирск — Вып. 23, — С.38-58.
8. Геометрическое строение почти всех функций алгебры логики // Сб. Проблемы кибернетики -М.: Наука — 1975 — С.227-261
9. Дизьюнктивные нормальные формы (Метрическая теория) // Издательство МГУ — 1975 — 90с.
10. Сборник задач по дискретной математике // М.: Наука — 1977 368с. (Соавтор Гаврилов Г. П.)
11. Обзор некоторых результатов по задачам о покрытии // Сб. Методы дискретного анализа в решении комбинаторных задач — Новосибирск — 1977 — Вып.30, -С.46-75 (Соавторы Асратян А. С. и Кузюрин Н. Н.).
12. Оценка длины и числа тупиковых д.н.ф. у почти всех не всюду определенных функций алгеьры логики // Математические заметки — 1980 — т.28, No.2, -1980 — p.279-300.
13. Problemas de Mathematica Dickreta (Spanish) // MIR Publisher, Moscow — 1980 -p.316 (Соавтор Gavrilov G. P.).
14. Diszkret Matematikai feladatgyujtemeny (Hangarian) // Muszaki Konyvkiado, Budapest — 1981 — p.358 (with Gavrilov G. P.).
15. Об отрицательных эффектах, связанных с исключением несущественных переменных // Автоматика и вычислительная техника — Рига -"Зинатне" — 1981 — С.28-35 (Соавтор Караханян Л. М.).
16. О числе двоичных кодов с расстоянием 2 // Сб. Проблемы кибернетики — М.: Наука — 1983 — С.111-140 (Соавтор Коршунов А. Д.).
17. Методы логического проектирования и оценки сложности // Микроэлектроника — 1984 — т.12, вып. 1, -С.42-47 (Соавтор Ложкин С. А.).
18. Авторское свидетельство No 1088130 // А, НОЗК 19/04, Бюллетень No 15, от 23.04.1984 (Соавторы: Алексеев В. Б., Корнилов В. И., Ложкин С. А., Немудров В. Г.). (Изобретение).
19. Минимизация булевых функций в классе д.н.ф. // Итоги науки и техники(Boolean functions minimization in the class of disjunctive normal forms (English)) — ВИНИТИ — 1987 — т.25, С.68-116 (Соавтор Чухров И. П.). (Journal of Soviet Math. Pl. Publ. Corp. — 1989 — p.2021-2052 (with Chukhrov G. P.)
20. Об одном подходе к оценке пространственой сложности // Труды математического центра им. С.Банаха, Варшава — 1988 — 184-199. (Соавторы: Ложкин С. А., Рыбко А. И., Шкаликова Н. А., Хромкович Ю.)
21. Lower Bounds on the Area Complexity of Boolean Functions (Engl.) // Theoretical Computer Science — 1992 — v.97 — 285-300 (with Hromkovich J., Lozkin S. A., Rybko A. I., Shkalikova N. A.).
22. О числе связанных подмножеств с заданной мощностью границы в двудольных графах // Методы дискретного анализа в решении комбинаторных задач — Новосибирск — 1987 — вып. 45, — С.42-70.
23. Асимптотика числа монотонных функций на частично упорядоченных множествах // Доклады АН СССР — 1989 — т.305 — No 2, — С.279-283. Английский перевод: Asymptotics of the number of monotone functions on partial ordered sets // Soviet Math. Doclady — 1989 vol.39 No.2 — p.289-293.
24. О числе антицепей в ранжированных частично упорядоченных множествах // Дискретная математика — М.: Наука — 1989 — т.305 — No 2, С.279-283. Англ. перевод: Discrete Mathematics and Applications — Utrecht, The Nethelands, Tokio, Japan, — v.1, No.1 — p.35-59.
25. О числе антицепей в многослойных ранжированных частично упорядоченных множествах // Дискретная математика — М.: Наука — 1989 — т.1, вып.1, — С.110-128. Англ. перевод: Discrete Mathematics and Applicatoins — Utretch, The Nethelands, Tokio, Japan, — v.1,No.1 — p.149-171.
26. Selected Problems in Discrete Mathematics(Engl.) // — Moscow — MIR Publishers — 1989 — 414p. (with Gavrilov G.P.)
27. On the number of data-bases and closure operations (English) // Theoretical Computer Sci. — North Holland — 1991 — .377-383 (with Burosch G., Demetrovich J., Katona G., Kleitman D.).
28. О поиске максимально верхнего нуля монотонных функций на ранжированных частично упорядоченных множествах // Журнал математической физики и вычислительной математики — 1991 т.31, No 12, С.1871-1884.
29. Задачи и упражнения по курсу дискретной математики // М.: Наука — 1992 — 408с. (Соавтор Гаврилов Г. П.)
30. Метод граничных функционалов для перечислительных изопериметрических задач // Докторская диссертация — МГУ — 1993 -240с.
31. Radius and Diameter of Random Subgraphs of the n-Cube(Engl.) // Random Structures and Algoritms — 1993 v.4, No.2, -p.215-229 (with Kostochka A. V., Weber K.)..
32. On the Number of Closure Operations (English) // Combinatorics P.Erdos is Eighty — vol.1 Keszthely, Hungary — 1993 — p.91-105 (Burosch G., Demetrovich J., Katona G., Kleiton D.).
33. О предельных распределениях случайных величин, пораждаемых ограниченными последовательностями // Дискретный Анализ — Труды Института Математики СО РАН — Т.27 — Новосибирск — 1994 -Р. 166-176.
34. О возможности построения макромоделей для RC-схем // Журнал вычислительной математики и математической физики -1995 — т.35, No 12 C.1886-1898. Англ. перевод: On Possibility of Constracting Macromodels for RC-circuits // Journal of Computational Mathematics and Mathematical Physics — 1995 -т.35 No.12 -C.1886-1898..
35. Problems and Exercises in Discrete Mathematics, Kluver Academic Publishers Dordrecht // Boston/ London — 1996 -p.422 (with Gavrilov G. P.).
36. О числе связанных множеств с заданной мощностью окрестности в графе // Серия 1, Новосибирск — 1997 — т.4, No 3 -с. 18-34.
37. Оценка числа связанных множеств в графе и структура компонент случайных подмножеств // Доклады АН, 1999, том 365, No 4, с. 455-457
38. On counting boundary functional sums // Discrete Mathematics 213 (2000), 253-260.
39. On the Number of Independent Sets in Bipartite Graphs with Large Minimum Degree (PostScript) // DIMACS Technical Report 2000-25, August 2000.
40. Проблема Дедекинда и метод граничных функционалов // в кн. Математические вопросы кибернетики, Вып.6 , М. Наука, 2000г. С.161-220.
41. О числе независимых множеств в расширителях (PostScript) // Дискретная математика, т. 13, вып. 1, 2001, с. 56-62.
42. Некоторые перечислительные задачи теории графов и теории чисел // Таврический вестник математики и информатики, No 1, 2002г., С. 58-63.
43. О некоторых перечислительных задачах теории графов и теории групп // Дискретный анализ и исследование операций//Материалы конференций, Новосибирск, 24-28 июня 2002г.
44. Independent Sets and Sum-Free Sets // Discrete Mathematics and Applications.
45. Independent sets and sum-free sets // Sixth Internetional Conference on Discrete Mathematics and Applications, Ed. Sl.Shtrakov and K.Deneke, 31.08. — 02.09.2001, Bansko, Bulgaria, 35-42.
46. О числе множеств, свободных от сумм в Абелевых группах (PostScript) // Вестник Московского Университета. Сер 1, Математика, Механика 2002. No 4. С. 14-18.
47. О числе множеств, свободных от сумм, в отрезке натуральных чисел (PostScript) // Дискретная математика, том 14, вып. 3, 2002, 4-7. (соавтор Омельянов К. Г.)
48. Асимптотика числа множеств, свободных от сумм, в абелевых группах четного порядка // ДАН, том 383, No 4, 2002, C. 454-457.
49. The Cameron-Erdos Conjecture (PostScript) // Eurocomb`2003 — Abstracts, ITI-Series, Prague, 2003 -145 p.326-327.