Избранные вопросы дискретной математики — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Лекции)
(Объявления)
 
(не показаны 30 промежуточные версии 1 участника)
Строка 4: Строка 4:
  
 
==Объявления==
 
==Объявления==
 +
 +
Пересдача экзамена состоится 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 мин, то считается, что студент работу не сдал.
  
 
==Лекции==
 
==Лекции==
Строка 9: Строка 19:
 
'''Часть 1. Конечные функции'''.
 
'''Часть 1. Конечные функции'''.
  
'''[[Media:ivdm-l1-selezn.pdf|Лекция 1]]'''. Универсальная алгебра. Отношения на множестве. Отношение эквивалентности. Операции на множестве. Алгебра. Сохранение функцией отношения. Функции k-значной логики. Существенность переменных.
+
'''[[Media:ivdm-l1-selezn.pdf|Лекция 1]]'''. Функции k-значной логики. Формулы. Тождества. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах.
  
'''[[Media:ivdm-l2-selezn.pdf|Лекция 2]]'''. Функции k-значной логики. Формулы. Нормальные формы: 1-я и 2-я формы, полиномы по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.
+
'''[[Media:ivdm-l2-selezn.pdf|Лекция 2]]'''. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.
  
'''[[Media:ivdm-l3-selezn.pdf|Лекция 3]]'''. Алгоритм распознавания полноты в k-значной логике. Замкнутые классы. Классы функций, сохраняющие множество, и функций, сохраняющие разбиение, их замкнутость. Теорема Кузнецова. Предполные классы.
+
'''[[Media:ivdm-l3-selezn.pdf|Лекция 3]]'''. Выразимость и полнота в P_k, их алгоритмическая разрешимость для конечных множеств. Замкнутые классы. Классы функций, сохраняющих множество, и функций, сохраняющих разбиение, их замкнутость.
  
 
'''[[Media:ivdm-l4-selezn.pdf|Лекция 4]]'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
 
'''[[Media:ivdm-l4-selezn.pdf|Лекция 4]]'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
  
'''[[Media:ivdm-l5-selezn.pdf|Лекция 5]]'''. Предикаты. Классы функций, сохраняющих предикат, их замкнутость. Предполные классы. Предикатное описание предполных классов.
+
'''[[Media:ivdm-l5-selezn.pdf|Лекция 5]]'''. Предполные классы. Описание предполных классов. Теорема Кузнецова о предполных классах в P_k.
  
'''[[Media:ivdm-l6-selezn.pdf|Лекция 6]]'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Существование в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Соответствие Галуа. Задача обобщенной выполнимости.
+
'''[[Media:ivdm-l6-selezn.pdf|Лекция 6]]'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теорема Янова. Теорема Мучника. Мощность множества замкнутых классов в P_k.  
  
 
Коллоквиум по теме "Конечные функции".
 
Коллоквиум по теме "Конечные функции".
Строка 25: Строка 35:
 
'''Часть 2. Теория Пойа'''.
 
'''Часть 2. Теория Пойа'''.
  
Лекция 7. Группы. Симметрическая группа перестановок S_n. Подгруппы. Теорема Кэли. Цикловой индекс группы перестановок.
+
'''[[Media:ivdm-l7-selezn.pdf|Лекция 7]]'''. Группы. Подгруппы. Смежные классы. Разложение группы по подгруппе. Нормальные подгруппы. Фактор-группы.
  
Лекция 8. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы. Действие группы на множестве. Орбита и стабилизатор элемента. Лемма Бернсайда.
+
'''[[Media:ivdm-l8-selezn.pdf|Лекция 8]]'''. Перестановки. Симметрическая группа перестановок. Теорема Кэли. Орбита и стабилизатор элемента. Лемма Бернсайда.
  
Лекция 9. Раскраски. Эквивалентность раскрасок относительно группы. Теорема Пойа. Производящие функции. Перечисляющий ряд для цветов и перечисляющий ряд для раскрасок. Теорема Пойа (общий случай). Примеры.
+
'''[[Media:ivdm-l9-selezn.pdf|Лекция 9]]'''. Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа. Примеры.
 
+
Коллоквиум по теме "Теория Пойа".
+
  
 
'''Часть 3. Конечные поля'''.
 
'''Часть 3. Конечные поля'''.
  
Лекция 10. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.
+
'''[[Media:ivdm-l10-selezn.pdf|Лекция 10]]'''. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.
 
+
Лекция 11. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля.
+
  
Лекция 12. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.
+
'''[[Media:ivdm-l11-selezn.pdf|Лекция 11]]'''. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля.
  
 +
<!---'''Лекция 12'''. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.--->
 
Коллоквиум по теме "Конечные поля".
 
Коллоквиум по теме "Конечные поля".
  
Строка 76: Строка 83:
 
На дом: [4] Гл. III 2.13(7, 8, 9, 10), 2.16(2, 4), 2.19(5, 9, 10, 11, 12), 2.14, 2.15.
 
На дом: [4] Гл. III 2.13(7, 8, 9, 10), 2.16(2, 4), 2.19(5, 9, 10, 11, 12), 2.14, 2.15.
  
'''Занятие 3'''. Распознавание полноты систем функций. Критерий полноты. Система полиномов. Базисы.  
+
'''Занятие 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(1, 2, 3), 2.21(1, 2, 5, 7), 2.22(1, 3, 5), 2.23(1, 3, 4), 2.25(1, 3).

Текущая версия на 14:22, 16 февраля 2022

Курс читает Селезнева Светлана Николаевна

Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.

Объявления

Пересдача экзамена состоится 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-значной логики. Формулы. Тождества. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах.

Лекция 2. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.

Лекция 3. Выразимость и полнота в P_k, их алгоритмическая разрешимость для конечных множеств. Замкнутые классы. Классы функций, сохраняющих множество, и функций, сохраняющих разбиение, их замкнутость.

Лекция 4. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.

Лекция 5. Предполные классы. Описание предполных классов. Теорема Кузнецова о предполных классах в P_k.

Лекция 6. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теорема Янова. Теорема Мучника. Мощность множества замкнутых классов в P_k.

Коллоквиум по теме "Конечные функции".

Часть 2. Теория Пойа.

Лекция 7. Группы. Подгруппы. Смежные классы. Разложение группы по подгруппе. Нормальные подгруппы. Фактор-группы.

Лекция 8. Перестановки. Симметрическая группа перестановок. Теорема Кэли. Орбита и стабилизатор элемента. Лемма Бернсайда.

Лекция 9. Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа. Примеры.

Часть 3. Конечные поля.

Лекция 10. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.

Лекция 11. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля.

Коллоквиум по теме "Конечные поля".

Литература

Основная:

  1. Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
  2. Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
  3. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
  4. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
  5. Задачи для семинарских занятий по теме "Группы. Теория Пойа".
  6. Задачи для семинарских занятий по теме "Конечные поля".

Дополнительная:

  1. Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2016. Глава 1.
  2. Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. Глава 1.
  3. Яблонский С.В., Гаврилов Г.П., Набебин А.А. Предполные классы в многозначных логиках. М.: МЭИ, 1997. Часть 1.
  4. Lau D. Function Algebras on Finite Sets. Springer, 2006.
  5. Горшков С.П., Тарасов А.В. Сложность решения систем булевых уравнений. М.: Курс, 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).

О проведении экзамена