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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
м
 
(не показаны 6 промежуточные версии 2 участников)
Строка 1: Строка 1:
 
{{DISPLAYTITLE:Алексеев Валерий Борисович}}
 
{{DISPLAYTITLE:Алексеев Валерий Борисович}}
[[Image:Alekseev.jpg|thumb|right|Алексеев Валерий Борисович]]'''Алексеев Валерий Борисович''' — доктор физико-математических наук, профессор, заведующий кафедрой.
+
[[Image:Alekseev.jpg|thumb|right|Алексеев Валерий Борисович]]'''Алексеев Валерий Борисович''' — доктор физико-математических наук, профессор кафедры МК.
  
  
Строка 7: Строка 7:
 
=== Сложность алгоритмов, квантовые алгоритмы ===
 
=== Сложность алгоритмов, квантовые алгоритмы ===
  
Разрабатываются методы ускорения алгоритмов на различных дискретных структурах, рассматриваются квантовые алгоритмы. Изучается проблема установления сложности алгоритмов умножения матриц. Устанавливаются связи между существованием быстрых алгоритмов для различных задач и существованием алгебр специальной структуры. Строятся быстрые полиномиальные алгоритмы для распознавания свойств дискретных (булевых, <math>k</math>-значных) функций. Изучается сложность сортировки на частично упорядоченных множествах.
+
Разрабатываются методы ускорения алгоритмов на различных дискретных структурах, рассматриваются квантовые алгоритмы. Изучается проблема установления сложности алгоритмов умножения матриц. Устанавливаются связи между существованием быстрых алгоритмов для различных задач и существованием алгебр специальной структуры. Строятся быстрые полиномиальные алгоритмы для распознавания свойств дискретных (булевых, k-значных) функций.
  
 
=== Теория функциональных систем ===
 
=== Теория функциональных систем ===
  
Изучается структура решетки замкнутых классов в множестве частичных <math>k</math>-значных функций. Изучаются специальные базисы в <math>k</math>-значных логиках.
+
Изучается структура решетки замкнутых классов в множестве частичных k-значных функций. Изучаются специальные базисы в k-значных логиках.
  
 
=== Оценки количества дискретных функций ===
 
=== Оценки количества дискретных функций ===
  
Разрабатываются методы оценки числа дискретных функций с заданными свойствами. Устанавливается асимптотика логарифма числа функций от <math>n</math> переменных в различных классах.
+
Разрабатываются методы оценки числа дискретных функций с заданными свойствами. Устанавливается асимптотика логарифма числа функций от n переменных в различных классах.
  
 
== Лекционные курсы ==
 
== Лекционные курсы ==
Строка 21: Строка 21:
 
* [[Дискретная математика (1й курс)]]
 
* [[Дискретная математика (1й курс)]]
 
* [[Сложность алгоритмов]]
 
* [[Сложность алгоритмов]]
 +
* [[Вероятностные и квантовые алгоритмы]]
  
 
== Спецсеминары ==
 
== Спецсеминары ==
Строка 30: Строка 31:
 
== Избранные публикации ==
 
== Избранные публикации ==
  
# О простых базисах <math>k</math>-значной логики // Математические заметки, 1969, т. 5, вып.4, с.471-482.
+
# О простых базисах k-значной логики // Математические заметки, 1969, т. 5, вып.4, с.471-482.
# Простые базисы и простые функции в <math>k</math>-значной логике // Кибернетика, 1971, N5, с.137-141.
+
# Простые базисы и простые функции в k-значной логике // Кибернетика, 1971, N5, с.137-141.
# О числе простых базисов в <math>k</math>-значной логике // Сб. "Дискретный анализ". Вып.19. Новосибирск, 1971. С.3-10.
+
# О числе простых базисов в k-значной логике // Сб. "Дискретный анализ". Вып.19. Новосибирск, 1971. С.3-10.
 
# О числе k-значных монотонных функций // ДАН СССР, 1973, т.208, N3, с.505-508.
 
# О числе k-значных монотонных функций // ДАН СССР, 1973, т.208, N3, с.505-508.
# О числе монотонных <math>k</math>-значных функций // Сб. "Проблемы кибернетики". Вып.28. М.: Наука. 1974. С.5-24.
+
# О числе монотонных k-значных функций // Сб. "Проблемы кибернетики". Вып.28. М.: Наука. 1974. С.5-24.
 
# Использование симметрии при нахождении ширины частично упорядоченного множества // Дискретн. анализ, 1974, вып.26, из-во СО АН СССР, с. 20-35.
 
# Использование симметрии при нахождении ширины частично упорядоченного множества // Дискретн. анализ, 1974, вып.26, из-во СО АН СССР, с. 20-35.
 
# О расшифровке некоторых классов монотонных многозначных функций // Журнал вычислит. математики и мат. физики, 1976, т.16, N.1, с.189-198.
 
# О расшифровке некоторых классов монотонных многозначных функций // Журнал вычислит. математики и мат. физики, 1976, т.16, N.1, с.189-198.
Строка 40: Строка 41:
 
# Теорема Абеля в задачах и решениях // М.: Наука, 1976.
 
# Теорема Абеля в задачах и решениях // М.: Наука, 1976.
 
# О разложении полного графа на подграфы, вложимые в плоскую целочисленную решетку // Сб."Методы дискретного анализа в синтезе управляющих систем", 1978, вып.32, из-во СО АН СССР, с.3-20. (совм. с Мартиновой М. К.)
 
# О разложении полного графа на подграфы, вложимые в плоскую целочисленную решетку // Сб."Методы дискретного анализа в синтезе управляющих систем", 1978, вып.32, из-во СО АН СССР, с.3-20. (совм. с Мартиновой М. К.)
# О полупростых базисах <math>k</math>-значной логики // Математические заметки, 1980, т.28, вып.3, с.407-422.
+
# О полупростых базисах k-значной логики // Математические заметки, 1980, т.28, вып.3, с.407-422.
 
# О числе функций в классах, задаваемых центральными предикатами // Математические заметки. - 1985. Т. 37, вып.6 - С.880-886.
 
# О числе функций в классах, задаваемых центральными предикатами // Математические заметки. - 1985. Т. 37, вып.6 - С.880-886.
 
# On the complexity of some algorithms of matrix multiplication // Journal of algorithms, 1985, т.6, с.71-85.
 
# On the complexity of some algorithms of matrix multiplication // Journal of algorithms, 1985, т.6, с.71-85.
# Метод построения быстрых алгоритмов в <math>k</math>-значной логике // Матем. заметки. 1985. 38, вып. 1. С. 148-156. (совм. с Емельяновым Н. Р.)
+
# Метод построения быстрых алгоритмов в k-значной логике // Матем. заметки. 1985. 38, вып. 1. С. 148-156. (совм. с Емельяновым Н. Р.)
# Recognition of properties in <math>k</math>-valued logic and approximate algorithms // Lecture Notes in Computer Science. Springer-Verlag, 1987. Т.278. С. 10-13.
+
# Recognition of properties in k-valued logic and approximate algorithms // Lecture Notes in Computer Science. Springer-Verlag, 1987. Т.278. С. 10-13.
 
# Ступенчатые билинейные алгоритмы и распознавание полноты в k-значных логиках // Известия ВУЗов. Математика. 1988, N.7. С.19-27.
 
# Ступенчатые билинейные алгоритмы и распознавание полноты в k-значных логиках // Известия ВУЗов. Математика. 1988, N.7. С.19-27.
 
# Сложность умножения матриц. Обзор. // Кибернетический сб. М.:Мир, 1988, вып. 25, с. 189-236.
 
# Сложность умножения матриц. Обзор. // Кибернетический сб. М.:Мир, 1988, вып. 25, с. 189-236.
# О числе функций в некоторых замкнутых классах частичной <math>k</math>-значной логики // Дискретная математика. 1989. Т.1, вып.1. С.32-42.
+
# О числе функций в некоторых замкнутых классах частичной k-значной логики // Дискретная математика. 1989. Т.1, вып.1. С.32-42.
 
# О числе семейств подмножеств, замкнутых относительно пересечения // Дискретная математика. Т. 1, вып. 2 (1989). С. 129-136.
 
# О числе семейств подмножеств, замкнутых относительно пересечения // Дискретная математика. Т. 1, вып. 2 (1989). С. 129-136.
 
# Вложения графов в поверхности и теория графов тока // Дискретная математика, 1990, т.2, вып.4, с.97-115. (совм. с Коржиком В. П.)
 
# Вложения графов в поверхности и теория графов тока // Дискретная математика, 1990, т.2, вып.4, с.97-115. (совм. с Коржиком В. П.)
Строка 55: Строка 56:
 
# Логические полукольца и их использование для построения быстрых алгоритмов // Вестн. Моск. ун-та. Матем. механ. 1997, N 1. С. 22-29.
 
# Логические полукольца и их использование для построения быстрых алгоритмов // Вестн. Моск. ун-та. Матем. механ. 1997, N 1. С. 22-29.
 
# Минимальные расширения с простым умножением для алгебры матриц второго порядка // Дискретная математика. 1997, т.9, N 1, с. 71-82.
 
# Минимальные расширения с простым умножением для алгебры матриц второго порядка // Дискретная математика. 1997, т.9, N 1, с. 71-82.
# О сложности распознавания полноты систем функций в классе <math>P_3^*</math> // Вестн. Моск. ун-та. Матем. механ. 1997, N 3. (совм. с Кривенко М. М.)
+
# О сложности распознавания полноты систем функций в классе P_3^* // Вестн. Моск. ун-та. Матем. механ. 1997, N 3. (совм. с Кривенко М. М.)
 
# От метода А.А.Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Труды МИРАН, 1997, т. 218. С.22-27.
 
# От метода А.А.Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Труды МИРАН, 1997, т. 218. С.22-27.
 
# Метод искусственных ограничений для оценки числа дискретных функций // Сб. "Математические вопросы кибернетики". Вып. 8 (1999). М.: Наука. С. 123-134.
 
# Метод искусственных ограничений для оценки числа дискретных функций // Сб. "Математические вопросы кибернетики". Вып. 8 (1999). М.: Наука. С. 123-134.
 
# Элементы теории графов, схем и автоматов. // М.: Издательский отдел ф-та ВМиК МГУ, 2000. 58 с. (совм. с [[Ложкин Сергей Андреевич|Ложкиным С. А.]])
 
# Элементы теории графов, схем и автоматов. // М.: Издательский отдел ф-та ВМиК МГУ, 2000. 58 с. (совм. с [[Ложкин Сергей Андреевич|Ложкиным С. А.]])
 
# Теорема Абеля в задачах и решениях // М.: МЦНМО, 2001 (новое издание, [http://www.mccme.ru/free-books/pdf/alekseev.pdf PDF]).
 
# Теорема Абеля в задачах и решениях // М.: МЦНМО, 2001 (новое издание, [http://www.mccme.ru/free-books/pdf/alekseev.pdf PDF]).
 +
# Введение в теорию сложности алгоритмов // М.: Издательский отдел ф-та ВМиК МГУ, 2002.
 +
# О числе отображений типа замыкания // Дискретная математика, 2004, т.16, вып.2, с.85-97.
 +
# Abel's theorem in problems and solutions // Kluwer Academic Publishers, 2004.
 +
# On the voltage-current transferring in topological graph theory // Ars Combinatoria, 2005 (January), v.74, p. 331-349. (совм. с Коржиком В. П.)
 +
# Сложность умножения в некоторых групповых алгебрах // Дискретная математика, 2005, т.17, вып.1, с.3-17.  (совм. с Поспеловым А.Д.)
 +
# О некоторых замкнутых классах самодвойственных частичных многозначных функций // Ученые записки Казанского государственного университета. Серия «Физико-математические науки», т.151, книга 2, 2009, с. 16-24.
 +
# Лекции по дискретной математике // М.: ИНФРА-М, 2012.
 +
# О приближении максимально-нелинейных булевых функций почти линейными функциями // Дискретная математика, т. 24, вып. 3, 2012, с. 73-81. (совм. с Омаровым Р.Р.)
 +
# On the Exact and Approximate Bilinear Complexities of Multiplication of  4 × 2  and  2 × 2 Matrices // Proceedings of the Steklov Institute of Mathematics, 2013, Vol. 282, Suppl. 1, pp. S123-S139. (совместно со Смирновым А.В.)
 +
# О билинейной сложности умножения матриц размеров mх2 и 2х2 //  Чебышевский сборник, т. 16, вып. 4, 2015, Тула, Изд-во Тул. гос. пед. ун-та им. Л.Н. Толстого, с. 11-27.
 +
# О замкнутых классах в частичной k-значной логике, содержащих класс монотонных функций  // Дискретная математика, т. 30, № 2, 2018, с. 3-13.
 +
# О билинейной сложности умножения матриц размеров 2х2 и 2хm над конечным полем // Вестн. Моск. ун-та. Выч. матем. и киберн. 2019, N 4, с. 5-10.
 +
# О замкнутых классах в частичной k-значной логике, содержащих все полиномы // Дискретная математика, т. 33, № 2, 2021, с. 6-19.
 +
# Дискретная математика. Учебник. // М.: ИНФРА-М, 2021, 133 с.

Текущая версия на 20:22, 10 марта 2022

Алексеев Валерий Борисович
Алексеев Валерий Борисович — доктор физико-математических наук, профессор кафедры МК.


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

Сложность алгоритмов, квантовые алгоритмы

Разрабатываются методы ускорения алгоритмов на различных дискретных структурах, рассматриваются квантовые алгоритмы. Изучается проблема установления сложности алгоритмов умножения матриц. Устанавливаются связи между существованием быстрых алгоритмов для различных задач и существованием алгебр специальной структуры. Строятся быстрые полиномиальные алгоритмы для распознавания свойств дискретных (булевых, k-значных) функций.

Теория функциональных систем

Изучается структура решетки замкнутых классов в множестве частичных k-значных функций. Изучаются специальные базисы в k-значных логиках.

Оценки количества дискретных функций

Разрабатываются методы оценки числа дискретных функций с заданными свойствами. Устанавливается асимптотика логарифма числа функций от n переменных в различных классах.

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

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

Аспиранты и студенты

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

  1. О простых базисах k-значной логики // Математические заметки, 1969, т. 5, вып.4, с.471-482.
  2. Простые базисы и простые функции в k-значной логике // Кибернетика, 1971, N5, с.137-141.
  3. О числе простых базисов в k-значной логике // Сб. "Дискретный анализ". Вып.19. Новосибирск, 1971. С.3-10.
  4. О числе k-значных монотонных функций // ДАН СССР, 1973, т.208, N3, с.505-508.
  5. О числе монотонных k-значных функций // Сб. "Проблемы кибернетики". Вып.28. М.: Наука. 1974. С.5-24.
  6. Использование симметрии при нахождении ширины частично упорядоченного множества // Дискретн. анализ, 1974, вып.26, из-во СО АН СССР, с. 20-35.
  7. О расшифровке некоторых классов монотонных многозначных функций // Журнал вычислит. математики и мат. физики, 1976, т.16, N.1, с.189-198.
  8. Толщина произвольного полного графа // Математический сборник, 1976, т. 101(143), вып.2(10) (совм. с Гончаковым В. С.)
  9. Теорема Абеля в задачах и решениях // М.: Наука, 1976.
  10. О разложении полного графа на подграфы, вложимые в плоскую целочисленную решетку // Сб."Методы дискретного анализа в синтезе управляющих систем", 1978, вып.32, из-во СО АН СССР, с.3-20. (совм. с Мартиновой М. К.)
  11. О полупростых базисах k-значной логики // Математические заметки, 1980, т.28, вып.3, с.407-422.
  12. О числе функций в классах, задаваемых центральными предикатами // Математические заметки. - 1985. Т. 37, вып.6 - С.880-886.
  13. On the complexity of some algorithms of matrix multiplication // Journal of algorithms, 1985, т.6, с.71-85.
  14. Метод построения быстрых алгоритмов в k-значной логике // Матем. заметки. 1985. 38, вып. 1. С. 148-156. (совм. с Емельяновым Н. Р.)
  15. Recognition of properties in k-valued logic and approximate algorithms // Lecture Notes in Computer Science. Springer-Verlag, 1987. Т.278. С. 10-13.
  16. Ступенчатые билинейные алгоритмы и распознавание полноты в k-значных логиках // Известия ВУЗов. Математика. 1988, N.7. С.19-27.
  17. Сложность умножения матриц. Обзор. // Кибернетический сб. М.:Мир, 1988, вып. 25, с. 189-236.
  18. О числе функций в некоторых замкнутых классах частичной k-значной логики // Дискретная математика. 1989. Т.1, вып.1. С.32-42.
  19. О числе семейств подмножеств, замкнутых относительно пересечения // Дискретная математика. Т. 1, вып. 2 (1989). С. 129-136.
  20. Вложения графов в поверхности и теория графов тока // Дискретная математика, 1990, т.2, вып.4, с.97-115. (совм. с Коржиком В. П.)
  21. Элементы теории графов и схем. // М.: Изд-во МГУ, 1991. 40 с. (совм. с Ложкиным С. А.)
  22. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика, 1994, т.6, вып.4, с.58-79.(совм. с Вороненко А. А.)
  23. О некоторых алгебрах, связанных с быстрыми алгоритмами // Дискретная математика. 1996, т.8, N 1, с. 52-64.
  24. Логические полукольца и их использование для построения быстрых алгоритмов // Вестн. Моск. ун-та. Матем. механ. 1997, N 1. С. 22-29.
  25. Минимальные расширения с простым умножением для алгебры матриц второго порядка // Дискретная математика. 1997, т.9, N 1, с. 71-82.
  26. О сложности распознавания полноты систем функций в классе P_3^* // Вестн. Моск. ун-та. Матем. механ. 1997, N 3. (совм. с Кривенко М. М.)
  27. От метода А.А.Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Труды МИРАН, 1997, т. 218. С.22-27.
  28. Метод искусственных ограничений для оценки числа дискретных функций // Сб. "Математические вопросы кибернетики". Вып. 8 (1999). М.: Наука. С. 123-134.
  29. Элементы теории графов, схем и автоматов. // М.: Издательский отдел ф-та ВМиК МГУ, 2000. 58 с. (совм. с Ложкиным С. А.)
  30. Теорема Абеля в задачах и решениях // М.: МЦНМО, 2001 (новое издание, PDF).
  31. Введение в теорию сложности алгоритмов // М.: Издательский отдел ф-та ВМиК МГУ, 2002.
  32. О числе отображений типа замыкания // Дискретная математика, 2004, т.16, вып.2, с.85-97.
  33. Abel's theorem in problems and solutions // Kluwer Academic Publishers, 2004.
  34. On the voltage-current transferring in topological graph theory // Ars Combinatoria, 2005 (January), v.74, p. 331-349. (совм. с Коржиком В. П.)
  35. Сложность умножения в некоторых групповых алгебрах // Дискретная математика, 2005, т.17, вып.1, с.3-17. (совм. с Поспеловым А.Д.)
  36. О некоторых замкнутых классах самодвойственных частичных многозначных функций // Ученые записки Казанского государственного университета. Серия «Физико-математические науки», т.151, книга 2, 2009, с. 16-24.
  37. Лекции по дискретной математике // М.: ИНФРА-М, 2012.
  38. О приближении максимально-нелинейных булевых функций почти линейными функциями // Дискретная математика, т. 24, вып. 3, 2012, с. 73-81. (совм. с Омаровым Р.Р.)
  39. On the Exact and Approximate Bilinear Complexities of Multiplication of 4 × 2 and 2 × 2 Matrices // Proceedings of the Steklov Institute of Mathematics, 2013, Vol. 282, Suppl. 1, pp. S123-S139. (совместно со Смирновым А.В.)
  40. О билинейной сложности умножения матриц размеров mх2 и 2х2 // Чебышевский сборник, т. 16, вып. 4, 2015, Тула, Изд-во Тул. гос. пед. ун-та им. Л.Н. Толстого, с. 11-27.
  41. О замкнутых классах в частичной k-значной логике, содержащих класс монотонных функций // Дискретная математика, т. 30, № 2, 2018, с. 3-13.
  42. О билинейной сложности умножения матриц размеров 2х2 и 2хm над конечным полем // Вестн. Моск. ун-та. Выч. матем. и киберн. 2019, N 4, с. 5-10.
  43. О замкнутых классах в частичной k-значной логике, содержащих все полиномы // Дискретная математика, т. 33, № 2, 2021, с. 6-19.
  44. Дискретная математика. Учебник. // М.: ИНФРА-М, 2021, 133 с.