Избранные вопросы дискретной математики — различия между версиями
(→Лекции) |
(→Лекции) |
||
(не показаны 26 промежуточные версии 1 участника) | |||
Строка 5: | Строка 5: | ||
==Объявления== | ==Объявления== | ||
− | <!--- | + | <!---Пересдача экзамена состоится 18 февраля (в пятницу) удаленно. Начало в 16 ч 30 мин. |
− | + | ВАЖНО: просьба к каждому студенту, сдающему пересдачу, прислать на эл. почту dm1@cs.msu.ru письмо. В теме письма написать "пересдача по ИВДМ". Ответными письмами будет выслан вариант экзаменационного задания. | |
+ | |||
+ | В день экзамена в 16 ч 30 мин каждый студент по эл. почте получает вариант экзаменационного задания. На выполнение работы отводится 1 ч 30 мин (90 мин). Работу нужно написать от руки на светлых листах контрастной ручкой. Вверху на каждом листе нужно написать фамилию, имя. | ||
+ | |||
+ | Выполненную работу нужно отсканировать или сфотографировать. Затем сканы или фотографии выполненной работы в формате pdf, jpg или png нужно прислать ответным письмом на dm1@cs.msu.ru. На сканирование или фотографирование работы и ее отправку отводится 15 мин. | ||
+ | |||
+ | Если работа студента не получена через 1 ч 45 мин (105 мин) после начала экзамена, т.е. до 18 ч 15 мин, то считается, что студент работу не сдал.---> | ||
==Лекции== | ==Лекции== | ||
− | '''Часть 1. | + | '''Часть 1. Функции k-значной логики'''. |
− | ''' | + | '''Лекция 1'''. Функции k-значной логики. Формулы. Тождества. Представимость функций k-значной логики в 1-й и 2-й формах. |
− | '''Лекция 2'''. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k | + | '''Лекция 2'''. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба. |
− | '''Лекция 3'''. | + | '''Лекция 3'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции. |
− | '''Лекция 4'''. | + | '''Лекция 4'''. Выразимость и полнота в P_k, их алгоритмическая разрешимость для конечных множеств. Алгоритм распознавания полноты в P_k. |
− | '''Лекция 5'''. | + | '''Лекция 5'''. Замкнутые классы. Отношения. Сохранение функцией отношения. Замкнутость класса всех функций, сохраняющих заданное отношение. Классы функций, сохраняющих некоторые отношения. |
− | '''Лекция 6'''. | + | '''Лекция 6'''. Предполные классы. Описание предполных классов. Теорема Кузнецова о предполных классах в P_k. |
− | + | '''Лекция 7'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теорема Янова. Теорема Мучника. Мощность множества замкнутых классов в P_k. | |
− | + | Коллоквиум по теме "Функции k-значной логики". | |
− | + | '''Часть 2. Группы'''. | |
− | ''' | + | '''Лекция 8'''. Группы. Подгруппы. Смежные классы. Разложение группы по подгруппе. Нормальные подгруппы. Фактор-группы. |
− | ''' | + | '''Лекция 9'''. Перестановки. Симметрическая группа перестановок. Теорема Кэли. Орбита и стабилизатор элемента. Лемма Бернсайда. |
− | Коллоквиум по теме " | + | |
+ | '''Лекция 10'''. Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа. Примеры. | ||
+ | |||
+ | Коллоквиум по теме "Группы". | ||
'''Часть 3. Конечные поля'''. | '''Часть 3. Конечные поля'''. | ||
− | + | '''Лекция 11'''. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3. | |
+ | |||
+ | '''Лекция 12'''. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля. | ||
− | ''' | + | '''Лекция 13'''. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1. |
− | |||
Коллоквиум по теме "Конечные поля". | Коллоквиум по теме "Конечные поля". | ||
Строка 53: | Строка 63: | ||
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988. | # Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988. | ||
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004. | # Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004. | ||
− | # [[Media:ivdm-sem.pdf|Задачи для семинарских занятий]] по теме "Группы. Теория Пойа". | + | <!---# [[Media:ivdm-sem.pdf|Задачи для семинарских занятий]] по теме "Группы. Теория Пойа". |
− | # [[Media:ivdm-sem3.pdf|Задачи для семинарских занятий]] по теме "Конечные поля". | + | # [[Media:ivdm-sem3.pdf|Задачи для семинарских занятий]] по теме "Конечные поля".---> |
− | + | ||
Дополнительная: | Дополнительная: | ||
Строка 66: | Строка 75: | ||
==Семинары== | ==Семинары== | ||
− | '''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k. | + | <!---'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k. |
− | [4] Гл. III 1.1(3, 6, 10, 12), 1. | + | [4] Гл. III 1.1(3, 6, 10, 12), 1.2(1, 3), 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) | + | На дом: [4] Гл. III 1.1(4, 7, 11, 13), 1.2(2, 4), 1.6, 1.11(5, 10), 2.7(2, 8, 10), 2.12(3, 5), 2.8(2), 2.11(1, 2). |
'''Занятие 2'''. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам. | '''Занятие 2'''. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам. | ||
Строка 82: | Строка 91: | ||
[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(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] Гл. 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'''. Группы, подгруппы, теорема Кэли. Цикловой индекс группы перестановок. | |
− | '''Занятие 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(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). | ||
Строка 112: | Строка 120: | ||
[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(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). | + | На дом: [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).---> |
==О проведении экзамена== | ==О проведении экзамена== | ||
− | |||
[[Категория:Лекционные курсы кафедры МК]] | [[Категория:Лекционные курсы кафедры МК]] |
Версия 13:35, 23 января 2023
Курс читает Селезнева Светлана Николаевна
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.
Содержание
Объявления
Лекции
Часть 1. Функции k-значной логики.
Лекция 1. Функции k-значной логики. Формулы. Тождества. Представимость функций k-значной логики в 1-й и 2-й формах.
Лекция 2. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.
Лекция 3. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
Лекция 4. Выразимость и полнота в P_k, их алгоритмическая разрешимость для конечных множеств. Алгоритм распознавания полноты в P_k.
Лекция 5. Замкнутые классы. Отношения. Сохранение функцией отношения. Замкнутость класса всех функций, сохраняющих заданное отношение. Классы функций, сохраняющих некоторые отношения.
Лекция 6. Предполные классы. Описание предполных классов. Теорема Кузнецова о предполных классах в P_k.
Лекция 7. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теорема Янова. Теорема Мучника. Мощность множества замкнутых классов в P_k.
Коллоквиум по теме "Функции k-значной логики".
Часть 2. Группы.
Лекция 8. Группы. Подгруппы. Смежные классы. Разложение группы по подгруппе. Нормальные подгруппы. Фактор-группы.
Лекция 9. Перестановки. Симметрическая группа перестановок. Теорема Кэли. Орбита и стабилизатор элемента. Лемма Бернсайда.
Лекция 10. Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа. Примеры.
Коллоквиум по теме "Группы".
Часть 3. Конечные поля.
Лекция 11. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.
Лекция 12. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля.
Лекция 13. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.
Коллоквиум по теме "Конечные поля".
Литература
Основная:
- Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
- Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
- Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
Дополнительная:
- Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2016. Глава 1.
- Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. Глава 1.
- Яблонский С.В., Гаврилов Г.П., Набебин А.А. Предполные классы в многозначных логиках. М.: МЭИ, 1997. Часть 1.
- Lau D. Function Algebras on Finite Sets. Springer, 2006.
- Горшков С.П., Тарасов А.В. Сложность решения систем булевых уравнений. М.: Курс, 2017.