Избранные вопросы дискретной математики — различия между версиями
(→Лекции) |
(→Лекции) |
||
| Строка 24: | Строка 24: | ||
'''[[Media:ivdm-l6-selezn.pdf|Лекция 6]]'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Существование в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Соответствие Галуа. Задача обобщенной выполнимости.---> | '''[[Media:ivdm-l6-selezn.pdf|Лекция 6]]'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Существование в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Соответствие Галуа. Задача обобщенной выполнимости.---> | ||
| − | |||
Коллоквиум по теме "Конечные функции". | Коллоквиум по теме "Конечные функции". | ||
| Строка 33: | Строка 32: | ||
'''[[Media:ivdm-l8-selezn.pdf|Лекция 8]]'''. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы. Действие группы на множестве. Орбита и стабилизатор элемента. Лемма Бернсайда. | '''[[Media:ivdm-l8-selezn.pdf|Лекция 8]]'''. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы. Действие группы на множестве. Орбита и стабилизатор элемента. Лемма Бернсайда. | ||
| − | '''[[Media:ivdm-l9-selezn.pdf|Лекция 9]]'''. Раскраски. Эквивалентность раскрасок относительно группы. Теорема Пойа. Производящие функции. Перечисляющий ряд для цветов и перечисляющий ряд для раскрасок. Теорема Пойа (общий случай). Примеры. | + | '''[[Media:ivdm-l9-selezn.pdf|Лекция 9]]'''. Раскраски. Эквивалентность раскрасок относительно группы. Теорема Пойа. Производящие функции. Перечисляющий ряд для цветов и перечисляющий ряд для раскрасок. Теорема Пойа (общий случай). Примеры.---> |
| − | + | Коллоквиум по теме "Теория Пойа". | |
| − | Коллоквиум по теме "Теория Пойа". | + | |
'''Часть 3. Конечные поля'''. | '''Часть 3. Конечные поля'''. | ||
| Строка 44: | Строка 42: | ||
'''Лекция 12'''. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.---> | '''Лекция 12'''. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.---> | ||
| − | |||
Коллоквиум по теме "Конечные поля". | Коллоквиум по теме "Конечные поля". | ||
Версия 14:18, 26 августа 2021
Курс читает Селезнева Светлана Николаевна
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.
Содержание
Объявления
Экзамен - 8 января. Начало в 10 ч.
Консультация к экзамену состоится 6 января с помощью zoom; ссылка такая же, как и для лекций. Начало в 10 ч.
Лекции
Часть 1. Конечные функции.
Коллоквиум по теме "Конечные функции".
Часть 2. Теория Пойа.
Коллоквиум по теме "Теория Пойа".
Часть 3. Конечные поля.
Коллоквиум по теме "Конечные поля".
Литература
Основная:
- Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
- Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
- Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
- Задачи для семинарских занятий по теме "Группы. Теория Пойа".
- Задачи для семинарских занятий по теме "Конечные поля".
Дополнительная:
- Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2016. Глава 1.
- Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. Глава 1.
- Яблонский С.В., Гаврилов Г.П., Набебин А.А. Предполные классы в многозначных логиках. М.: МЭИ, 1997. Часть 1.
- Lau D. Function Algebras on Finite Sets. Springer, 2006.
- Горшков С.П., Тарасов А.В. Сложность решения систем булевых уравнений. М.: Курс, 2017.
Семинары
Занятие 1. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.
[4] Гл. III 1.1(3, 6, 10, 12), 1.5, 1.11(2, 4, 8, 11), 2.7(1, 3, 6, 9), 2.12(1, 2), 2.8(1, 3).
На дом: [4] Гл. III 1.1(4, 7, 11, 13), 1.6, 1.11(5, 10), 1.12, 2.7(2, 8, 10), 2.12(3, 5), 2.8(2), 2.9, 2.11(1, 2).
Занятие 2. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам.
[4] Гл. III 2.1(1 а, б, г, д), 2.2(1, 2), 2.13(1, 2, 5, 6), 2.16(1, 3), 2.19(1, 2, 3, 4).
На дом: [4] Гл. III 2.13(7, 8, 9, 10), 2.16(2, 4), 2.19(5, 9, 10, 11, 12), 2.14, 2.15.
Занятие 3. Распознавание полноты систем функций. Критерий полноты. Система полиномов. Базисы.
[4] Гл. III 2.20(1, 2, 3), 2.21(1, 2, 5, 7), 2.22(1, 3, 5), 2.23(1, 3, 4), 2.25(1, 3).
На дом: [4] Гл. III 2.20(4, 5, 7), 2.21(3, 4, 6, 8), 2.22(2, 4, 6), 2.23(5, 7), 2.25(2, 4).
Занятие 4. Группы, подгруппы, теорема Кэли. Цикловой индекс группы перестановок.
[5] 2.1(1, 2), 2.2(2, 4), 2.3(1, 3, 5, 7), 2.4(2, 4), 2.5(2, 4, 6, 8), 2.6(2, 3), 2.7(1).
На дом: [5] 2.1(3, 4), 2.2(1, 3), 2.3(2, 4, 6, 8), 2.4(1, 3, 5), 2.5(1, 3, 5, 7), 2.6(1, 4), 2.7(2).
Занятие 5. Раскраски. Теорема Пойа (частный случай).
[5] 2.8(2, 3, 6), 2.12(1, 2 (1-2)), 2.13(1, 2).
На дом: [5] 2.8(1, 4, 5, 7, 8), 2.12(2 (3-4)), 2.13(3), 2.14(2, 3), 2.15(2, 3).
Занятие 6. Раскраски. Теорема Пойа (общий случай).
[5] 2.9(1-4), 2.10(2, 4), 2.11(1, 2), 2.16(1, 3), 2.17(1,3).
На дом: [5] 2.9(5-8), 2.10(1, 3), 2.11(3, 4), 2.16(2, 4), 2.17(2, 4).
Занятие 7. Построение конечных полей.
[6] 3.1(1, 3, 5, 7), 3.3(1, 3, 5, 7), 3.4(1, 3, 5, 7), 3.5(1, 3), 3.7(1, 3).
На дом: [6] 3.1(2, 4, 6, 8), 3.3(2, 4, 6, 8), 3.4(2, 4, 6, 8), 3.5(2, 4), 3.7(2, 4).
Занятие 8. Вычисления в конечных полях.
[6] 3.6(1, 3, 5, 7), 3.8(1, 3, 5, 7), 3.9(1, 3, 5, 7), 3.10(1, 3, 5, 7), 3.11(1, 3, 5, 7).
На дом: [6] 3.6(2, 4, 6, 8), 3.8(2, 4, 6, 8), 3.9(2, 4, 6, 8), 3.10(2, 4, 6, 8), 3.11(2, 4, 6, 8).
О проведении экзамена
Схема проведения экзамена в 2020-2021 уч. году разослана студентам.
