Специальность ВАК:
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
