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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Лекционные курсы)
(→‎Лекционные курсы)
 
(не показаны 134 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{DISPLAYTITLE:Селезнева Светлана Николаевна}}
 
{{DISPLAYTITLE:Селезнева Светлана Николаевна}}
−
[[Image:Selezneva.jpg|thumb|right|Селезнева Светлана Николаевна]]'''Селезнева Светлана Николаевна''' — кандидат физико-математических наук, доцент.
+
[[Image:Selezneva3.jpg|thumb|right|Селезнева Светлана Николаевна]]'''Селезнева Светлана Николаевна''' — доктор физико-математических наук, профессор кафедры МК,
  
 +
e-mail: selezn@cs.msu.ru
  
−
== Области научных интересов ==
+
[http://istina.msu.ru/profile/selezn@cs.msu.su Профиль Селезневой С.Н. в системе "ИСТИНА"]
−
===Алгоритмическая сложность распознавания свойств булевых и многозначных функций===
+
  
−
Исследуется сложность алгоритмов распознавания свойств булевых и многозначных функций, заданных в определенном языке.
+
== [[Области научных интересов]]==
  
−
===Полиномиальные представления булевых и многозначных функций===
+
'''Полиномиальные представления дискретных функций'''
  
−
Исследуется сложность представления булевых и многозначных функций полиномами различных видов.
+
Рассматриваются представления функций алгебры логики и функций многозначной логики полиномами над соответствующим полем или кольцом и изучаются свойства таких представлений в следующих направлениях.  
  
−
===Полиномы над конечными полями===
+
*Сложность распознавания свойств функций, заданных полиномами.
  
−
Изучаются свойства полиномов над конечными полями во взаимосвязи с полиномиальными          представлениями конечнозначных функций.  
+
Разрабатываются быстрые алгоритмы распознавания ряда важных свойств функций, если на вход вычислителю функция подается в виде полинома. При этом оценивается сложность алгоритмов относительно длины полинома (т.е. числа слагаемых в полиноме) и числа переменных в нем. Селезневой С.Н. получены быстрые алгоритмы проверки свойств монотонности, самодвойственности, инвариантности, периодичности функции по ее полиному. Рассматриваемые свойства существенны в приложениях, связанных с защитой информации.  
  
−
== Лекционные курсы ==
+
*Сложность полиномиальных представлений функций.
−
* [[Избранные вопросы дискретной математики]]
+
  
−
Лекции по курсу "Избранные вопросы дискретной математики"
+
Разрабатываются подходы к построению для функций полиномиальных форм (поляризованных, обобщенных, псевдополиномиальных) с оценками их сложности. Селезневой С.Н. получены алгоритмы построения оптимальных по порядку псевдополиномиальных форм для функций n переменных. Рассматриваемые представления применимы при проектировании цифровых устройств с операциями сложения и умножения в конечных кольцах и полях.
  
−
[[Media:dm_lection1.pdf|Лекция 1]]: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.
+
*Свойства функций и их полиномиальных представлений.
  
−
[[Media:dm_lection2.pdf|Лекция 2]]: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.
+
Исследуются вопросы выразимости и полноты в классах функций, связанных с классом всех полиномиальных функций. Селезневой С.Н. получены критерии полиномиальности функций k-значной логики по составному модулю k. На основе этих критериев найден линейный алгоритм проверки полиномиальности по составному модулю функции, заданной вектором значений. При положительном ответе этот алгоритм находит канонический полином функции, которая подается на вход вычислителю. Рассматриваемые вопросы направлены на более глубокое понимания свойств конечных алгебр и функций, а также для дальнейшего применения при разработке алгоритмов.
 +
<!---[https://www.youtube.com/watch?v=h8eLGaS3gQY Видео: лекция "О сложности функций k-значных логик в классах полиномиальных форм" (6 октября 2015 г.)]--->
  
−
[[Media:dm_lection3.pdf|Лекция 3]]: Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб, его длина и ширина. Булеан.
+
== Спецсеминары ==
  
−
[[Media:dm_lection4.pdf|Лекция 4]]: Теорема Анселя о разбиении булева куба на цепи. Оценки числа монотонных булевых функций. Расшифровка монотонных булевых функций.
+
*[[Сложность решения дискретных задач]]
  
−
[[Media:dm_lection5.pdf|Лекция 5]]: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества булева куба и длины полиномиальных нормальных форм булевых функций.
+
== Лекционные курсы ==
−
 
+
−
[[Media:dm_lection6.pdf|Лекция 6]]: Коллоквиум 1.
+
−
 
+
−
[[Media:dm_lection7.pdf|Лекция 7]]: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.
+
−
 
+
−
[[Media:dm_lection8.pdf|Лекция 8]]: Линейные однородные и неоднородные рекуррентные уравнения.
+
−
 
+
−
[[Media:dm_lection9.pdf|Лекция 9]]: Группы. Изоморфизм групп. Симметрическая группа перестановок. Теорема Кэли.
+
−
 
+
−
[[Media:dm_lection10.pdf|Лекция 10]]: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.
+
−
 
+
−
[[Media:dm_lection11.pdf|Лекция 11]]: Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай). Примеры.
+
−
 
+
−
Лекция 12 (21.11): Коллоквиум 2.
+
−
 
+
−
Лекция 13 (28.11): Кольца. Кольцо многочленов.
+
−
 
+
−
Лекция 14 (5.12): Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.
+
−
 
+
−
Лекция 15 (12.12): Линейные коды.
+
−
 
+
−
Лекция 16 (19.12): Функции k-значной логики и способы их представления.
+
−
* [[Булевы функции и полиномы (спецкурс)]]
+
−
* [[Дискретная математика (гр. 141)]]
+
−
* [[Дискретные модели (магистратура, 1-й курс)]]
+
−
 
+
−
==Избранные вопросы дискретной математики==
+
−
 
+
−
==Лекции==
+
−
[[Media:dm_lection1.pdf|Лекция 1]]: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.
+
−
 
+
−
[[Media:dm_lection2.pdf|Лекция 2]]: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.
+
−
 
+
−
[[Media:dm_lection3.pdf|Лекция 3]]: Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб, его длина и ширина. Булеан.
+
−
 
+
−
[[Media:dm_lection4.pdf|Лекция 4]]: Теорема Анселя о разбиении булева куба на цепи. Оценки числа монотонных булевых функций. Расшифровка монотонных булевых функций.
+
−
 
+
−
[[Media:dm_lection5.pdf|Лекция 5]]: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества булева куба и длины полиномиальных нормальных форм булевых функций.
+
  
−
[[Media:dm_lection6.pdf|Лекция 6]]: Коллоквиум 1.
+
*[[Дискретная математика (1-й поток)]] (курс для студентов 1-го курса, см. также [[Дискретная математика (1-й курс)]])
  
−
[[Media:dm_lection7.pdf|Лекция 7]]: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.
+
*[[Избранные вопросы дискретной математики]] (курс для студентов 318 группы)
  
−
[[Media:dm_lection8.pdf|Лекция 8]]: Линейные однородные и неоднородные рекуррентные уравнения.
+
*[[Дискретные функции и выполнимость ограничений | Обобщенная выполнимость]] (курс для студентов 518/1 группы, спецкурс для студентов магистратуры)
  
−
[[Media:dm_lection9.pdf|Лекция 9]]: Группы. Изоморфизм групп. Симметрическая группа перестановок. Теорема Кэли.
+
* Основы дискретной математики (спецкурс для студентов магистратуры, филиал МГУ в г. Сарове)
  
−
[[Media:dm_lection10.pdf|Лекция 10]]: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.
+
* Основы теории графов (спецкурс для студентов магистратуры, филиал МГУ в г. Сарове)
  
−
[[Media:dm_lection11.pdf|Лекция 11]]: Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай). Примеры.
+
*[[Графы и их приложения]] (спецкурс для аспирантов)
  
−
Лекция 12 (21.11): Коллоквиум 2.
+
*[[Булевы функции и полиномы]] (спецкурс) - читался в 2008-2013 г.г.
  
−
Лекция 13 (28.11): Кольца. Кольцо многочленов.
+
==Учебные пособия==
  
−
Лекция 14 (5.12): Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.
+
[[Media:ok-2.pdf|Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу "Основы кибернетики"]], 2-е изд. М.: МАКС Пресс, 2011.
  
−
Лекция 15 (12.12): Линейные коды.
+
[[Media:odm-selezn.pdf|Селезнева С.Н. Основы дискретной математики]]. М.: МАКС Пресс, 2010.
  
−
Лекция 16 (19.12): Функции k-значной логики и способы их представления.
+
[[Media:bool_polynoms.pdf|Селезнева С.Н. Булевы функции и полиномы]]. Пособие по спецкурсу. Составители: Дайняк А.Б., Шуплецов М.С. Москва, 2006.
  
−
== Избранные публикации ==
+
== Аспиранты и студенты ==
  
−
# О сложности распознавания полноты множеств булевых функций, реализованных полиномами Жегалкина. ([http://mathcyb.cs.msu.su/paper/selezn/selezn97.ps PostScript]) // Дискретная математика (1997), т. 9, вып. 4, с. 24-31.
+
* аспиранты: Лобанов Алексей (3 г/о), Шурыгин Дмитрий (2 г/о)
−
# Полиномиальный алгоритм для распознавания принадлежности реализованной полиномом функции k-значной логики предполным классам самодвойственных функций. ([http://mathcyb.cs.msu.su/paper/selezn/selezn98.ps PostScript]) // Дискретная математика (1998), т. 10, вып. 3, с. 64-72.
+
* 618/1 группа: Бубнов Егор
−
# О некоторых свойствах полиномов над конечным полем. ([http://mathcyb.cs.msu.su/paper/selezn/selez01d.ps PostScript]) // Дискретная математика (2001), т. 13, вып. 2, с. 111-119.
+
* 518/1 группа: Ефремов Виктор, Ушаков Дмитрий, Жэнь Цзежуй
−
# Полиномиальный алгоритм распознавания принадлежности функций k-значных логик, представленных полиномами, к предполным классам линейных функций. ([http://mathcyb.cs.msu.su/paper/selezn/selez01v.ps PostScript]) // Вестник МГУ. Серия 15. Вычислительная математика и математическая кибернетика (2001), вып. 3, с. 40-43.
+
* 418 группа: Голобоков Дмитрий, Колесникова Наталья
−
# О сложности представления функций многозначных логик поляризованными полиномами. ([http://mathcyb.cs.msu.su/paper/selezn/selezn02.ps PostScript]) // Дискретная математика (2002), т. 14, вып. 2, с. 48-53.
+

Текущая версия на 18:32, 29 января 2025

Селезнева Светлана Николаевна
Селезнева Светлана Николаевна — доктор физико-математических наук, профессор кафедры МК,

e-mail: selezn@cs.msu.ru

Профиль Селезневой С.Н. в системе "ИСТИНА"

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

Полиномиальные представления дискретных функций

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

  • Сложность распознавания свойств функций, заданных полиномами.

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

  • Сложность полиномиальных представлений функций.

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

  • Свойства функций и их полиномиальных представлений.

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

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

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

  • Основы дискретной математики (спецкурс для студентов магистратуры, филиал МГУ в г. Сарове)
  • Основы теории графов (спецкурс для студентов магистратуры, филиал МГУ в г. Сарове)

Учебные пособия

Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу "Основы кибернетики", 2-е изд. М.: МАКС Пресс, 2011.

Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010.

Селезнева С.Н. Булевы функции и полиномы. Пособие по спецкурсу. Составители: Дайняк А.Б., Шуплецов М.С. Москва, 2006.

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

  • аспиранты: Лобанов Алексей (3 г/о), Шурыгин Дмитрий (2 г/о)
  • 618/1 группа: Бубнов Егор
  • 518/1 группа: Ефремов Виктор, Ушаков Дмитрий, Жэнь Цзежуй
  • 418 группа: Голобоков Дмитрий, Колесникова Наталья
Источник — «https://mk.cs.msu.ru/index.php?title=Участник:SeleznevaSN&oldid=11699»