Участник:SeleznevaSN — различия между версиями
(→Лекционные курсы) |
(→Лекционные курсы) |
||
| Строка 18: | Строка 18: | ||
== Лекционные курсы == | == Лекционные курсы == | ||
* [[Избранные вопросы дискретной математики]] | * [[Избранные вопросы дискретной математики]] | ||
| + | |||
| + | Лекции по курсу "Избранные вопросы дискретной математики" | ||
| + | |||
| + | [[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. | ||
| + | |||
| + | [[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)]] | * [[Дискретная математика (гр. 141)]] | ||
Версия 16:42, 24 ноября 2013
Содержание
Области научных интересов
Алгоритмическая сложность распознавания свойств булевых и многозначных функций
Исследуется сложность алгоритмов распознавания свойств булевых и многозначных функций, заданных в определенном языке.
Полиномиальные представления булевых и многозначных функций
Исследуется сложность представления булевых и многозначных функций полиномами различных видов.
Полиномы над конечными полями
Изучаются свойства полиномов над конечными полями во взаимосвязи с полиномиальными представлениями конечнозначных функций.
Лекционные курсы
Лекции по курсу "Избранные вопросы дискретной математики"
Лекция 1: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.
Лекция 2: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.
Лекция 3: Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб, его длина и ширина. Булеан.
Лекция 4: Теорема Анселя о разбиении булева куба на цепи. Оценки числа монотонных булевых функций. Расшифровка монотонных булевых функций.
Лекция 5: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества булева куба и длины полиномиальных нормальных форм булевых функций.
Лекция 6: Коллоквиум 1.
Лекция 7: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.
Лекция 8: Линейные однородные и неоднородные рекуррентные уравнения.
Лекция 9: Группы. Изоморфизм групп. Симметрическая группа перестановок. Теорема Кэли.
Лекция 10: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.
Лекция 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-й курс)
Избранные вопросы дискретной математики
Лекции
Лекция 1: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.
Лекция 2: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.
Лекция 3: Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб, его длина и ширина. Булеан.
Лекция 4: Теорема Анселя о разбиении булева куба на цепи. Оценки числа монотонных булевых функций. Расшифровка монотонных булевых функций.
Лекция 5: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества булева куба и длины полиномиальных нормальных форм булевых функций.
Лекция 6: Коллоквиум 1.
Лекция 7: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.
Лекция 8: Линейные однородные и неоднородные рекуррентные уравнения.
Лекция 9: Группы. Изоморфизм групп. Симметрическая группа перестановок. Теорема Кэли.
Лекция 10: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.
Лекция 11: Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай). Примеры.
Лекция 12 (21.11): Коллоквиум 2.
Лекция 13 (28.11): Кольца. Кольцо многочленов.
Лекция 14 (5.12): Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.
Лекция 15 (12.12): Линейные коды.
Лекция 16 (19.12): Функции k-значной логики и способы их представления.
Избранные публикации
- О сложности распознавания полноты множеств булевых функций, реализованных полиномами Жегалкина. (PostScript) // Дискретная математика (1997), т. 9, вып. 4, с. 24-31.
- Полиномиальный алгоритм для распознавания принадлежности реализованной полиномом функции k-значной логики предполным классам самодвойственных функций. (PostScript) // Дискретная математика (1998), т. 10, вып. 3, с. 64-72.
- О некоторых свойствах полиномов над конечным полем. (PostScript) // Дискретная математика (2001), т. 13, вып. 2, с. 111-119.
- Полиномиальный алгоритм распознавания принадлежности функций k-значных логик, представленных полиномами, к предполным классам линейных функций. (PostScript) // Вестник МГУ. Серия 15. Вычислительная математика и математическая кибернетика (2001), вып. 3, с. 40-43.
- О сложности представления функций многозначных логик поляризованными полиномами. (PostScript) // Дискретная математика (2002), т. 14, вып. 2, с. 48-53.
