01.01.09 (дискретная математика и математическая кибернетика)
Дата рождения:
18.02.1936
E-mail:
Ключевые слова:
булевы функции,
конечные автоматы,
случайные графы,
перечислительные задачи,
синтез управляющих систем,
восстановление графа по~подграфам,
гамильтоновы циклы,
дизъюнктивные нормальные формы,
змея в булевом кубе,
изоморфизм графов,
нижние оценки,
$\mathrm{NP}$-полнота,
полиномиальные задачи,
протыкание кубов,
сложно вычислимые булевы функции,
совершенные двоичные коды,
тройки Штейнера.
Основные темы научной работы
Найдены асимптотические формулы для числа сильно связных, источниковых и инициально связных конечных автоматов, а также для числа функций заданного веса, реализуемых конечными автоматами. Доказана теорема о наследственных свойствах автоматов. Найдены асимптотические формулы для числа монотонных булевых функций от $n$ переменных. Эти формулы различны для четных и нечетных $n$. Показано, что длина кратчайшей дизъюнктивной нормальной формы плочти кпаждой булевой функции от $n$ переменных с точностью до порядка равна $2^n/(log_2 n log_2 log_2 n)$. Доказано, что хроматическое число почти каждого $n$-вершинного графа асимптотически равно $n/(2 log_2 n)$.
Основные публикации:
Коршунов А. Д., “О перечислении конечных автоматов”, Проблемы кибернетики, 34, Наука, М., 1978, 5–82
Коршунов А. Д., “О хроматическом числе $n$-вершинных графов”, Методы дисретного анализа в теории булевых функций, 35, Институт математики СО АН СССР, Новосибирск, 1980, 15–44
Коршунов А. Д., “О числе монотонных булевых фкункций”, Проблемы кибернетики, 38, Наука, М., 1981, 5–108
Коршунов А. Д., “О сложности кратчайших дизъюнктивных нормальных форм случайных булевых функций”, Методы дискретного анализа в оптимизации управляющих систем, 40, Институт математики СО АН СССР, Новосибирск, 1983, 25–53
Korshunov A. D., “Families of subsets of a finite set and closed classes of Boolean functions”, Extremal problems for finite sets, Bolyai Society Mathematical Studies, 3, Janos Bolyai Mathematical Society, Budapest, 1994, 375–306
А. Д. Коршунов, “Сложность вычислений булевых функций”, УМН, 67:1(403) (2012), 97–168; A. D. Korshunov, “Computational complexity of Boolean functions”, Russian Math. Surveys, 67:1 (2012), 93–165
А. Д. Коршунов, “Некоторые нерешенные задачи дискретной математики и математической кибернетики”, УМН, 64:5(389) (2009), 3–20; A. D. Korshunov, “Some unsolved problems in discrete mathematics and mathematical cybernetics”, Russian Math. Surveys, 64:5 (2009), 787–803
А. Д. Коршунов, “Число $k$-неразделённых подмножеств $n$-элементного множества ($k$-неразделённых булевых фунеций от $n$ переменных). Часть III. Случай $k\geqslant 3$ и произвольных $n$”, Дискретн. анализ и исслед. опер., сер. 1, 12:3 (2005), 60–73
А. Д. Коршунов, “Число $k$-неразделенных семейств подмножеств $n$-элементного множества ($k$-неразделенных булевых функций от $n$ переменных). Часть II. Случай нечетных $n$ и $k=2$”, Дискретн. анализ и исслед. опер., сер. 1, 12:1 (2005), 12–70
А. Д. Коршунов, “Число $k$-неразделенных семейств подмножеств $n$-элементного множества ($k$-неразделенных булевых функций). Часть 1. Случай четных $n$ и $k=2$”, Дискретн. анализ и исслед. опер., сер. 1, 10:4 (2003), 31–69
А. Д. Коршунов, “При каких $k$ в почти каждом $n$-вершинном графе имеются все неизоморфные $k$-вершинные подграфы”, Дискретн. анализ и исслед. опер., сер. 1, 8:4 (2001), 54–67
А. Д. Коршунов, И. Шмулевич, “Число специальных монотонных булевых функций и статистические свойства стековых фильтров”, Дискретн. анализ и исслед. опер., сер. 1, 7:3 (2000), 17–44
А. Д. Коршунов, “Об асимптотике числа бинарных слов с заданной длиной максимальной серии. 1”, Дискретн. анализ и исслед. опер., сер. 1, 4:4 (1997), 13–46
Ю. Л. Васильев, Ю. И. Журавлев, А. Д. Коршунов, В. Б. Кудрявцев, О. Б. Лупанов, А. А. Сапоженко, С. И. Янов, “Сергей Всеволодович Яблонский (к семидесятилетию со дня рождения)”, Сиб. журн. исслед. опер., 1:4 (1994), 3–6
А. Д. Коршунов, “О количестве графов с фиксированным числом вершин, ребер и изолированных вершин”, Тр. Ин-та математики СО РАН, 27 (1994), 43–93
14.
А. Д. Коршунов, “О линейных расширениях частично упорядоченных множеств”, Тр. Ин-та математики СО РАН, 27 (1994), 34–42
1988
15.
А. Д. Коршунов, “О мощности и структуре замкнутых классов Поста (семейств подмножеств конечного множества)”, Тр. Ин-та математики, 10 (1988), 159–204
1987
16.
А. Д. Коршунов, “О мощности и структуре некоторых замкнутых классов Поста (семейств подмножеств конечного множества)”, Докл. АН СССР, 295:3 (1987), 533–537; A. D. Korshunov, “On the power and structure of some closed Post classes (families
of subsets of a finite set)”, Dokl. Math., 36:1 (1988), 88–91
А. Д. Коршунов, “Основные свойства случайных графов с большим числом
вершин и ребер”, УМН, 40:1(241) (1985), 107–173; A. D. Korshunov, “The main properties of random graphs with a large number of vertices and edges”, Russian Math. Surveys, 40:1 (1985), 121–198
А. Д. Коршунов, “Число автоматов и ограниченно-детерминированных функций. Наследственные свойства автоматов”, Докл. АН СССР, 221:6 (1975), 1264–1267
1974
21.
А. Д. Коршунов, “О числе пар гамильтоновых циклов в полном графе, имеющих заданное число общих ребер”, Управляемые системы, 1974, № 13, 40–57
1971
22.
А. Д. Коршунов, “О диаметре графов”, Докл. АН СССР, 196:5 (1971), 1013–1015
23.
А. Д. Коршунов, “О числе неизоморфных подграфов в $n$-вершинном графе”, Матем. заметки, 9:3 (1971), 263–273; A. D. Korshunov, “Number of nonisomorphic subgraphs in an $n$-point graph”, Math. Notes, 9:3 (1971), 155–160
А. Д. Коршунов, “О верхней оценке длин кратчайших однородных экспериментов по распознаванию заключительного
состояния для почти всех автоматов”, Докл. АН СССР, 184:1 (1969), 28–29
А. Д. Коршунов, “Число, степень различимости и диаметр перестановочных автоматов и реализуемых ими операторов”, Докл. АН СССР, 182:2 (1968), 262–265
1966
27.
В. С. Гринберг, А. Д. Коршунов, “Об асимптотическом поведении максимума веса конечного дерева”, Пробл. передачи информ., 2:1 (1966), 96–99; V. S. Grinberg, A. D. Korshunov, “Asymptotic Behavior of the Maximum of the Weight of a Finite Tree”, Problems Inform. Transmission, 2:1 (1966), 75–78
2008
28.
А. Д. Коршунов, “Новые книги по дискретной математике”, Дискретн. анализ и исслед. опер., 15:2 (2008), 100–101
2007
29.
А. Д. Коршунов, “Новые книги по дискретной математике”, Дискретн. анализ и исслед. опер., сер. 1, 14:4 (2007), 103–105
30.
А. Д. Коршунов, “Новые книги по дискретной математике”, Дискретн. анализ и исслед. опер., сер. 1, 14:2 (2007), 102–103
2006
31.
А. Д. Коршунов, “Новые книги по дискретной математике”, Дискретн. анализ и исслед. опер., сер. 1, 13:2 (2006), 100–101
2005
32.
А. Д. Коршунов, “Новые книги по дискретной математике”, Дискретн. анализ и исслед. опер., сер. 1, 12:4 (2005), 95–97
33.
А. Д. Коршунов, “Новые книги по дискретной математике”, Дискретн. анализ и исслед. опер., сер. 1, 12:2 (2005), 100–102
34.
В. Л. Береснев, А. А. Евдокимов, А. Д. Коршунов, П. С. Краснощеков, В. К. Леонтьев, О. Б. Лупанов, Ю. Н. Павловский, А. А. Сапоженко, Ю. А. Флеров, “Юрий Иванович Журавлёв (к 70-летию со дня рождения)”, Дискретн. анализ и исслед. опер., сер. 1, 12:1 (2005), 3–11
Обратная связь: