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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Лекции)
(→‎Лекции)
 
(не показаны 44 промежуточных версий 1 участника)
Строка 7: Строка 7:
 
==Лекции==
 
==Лекции==
  
−
'''Часть 1. Конечные функции'''.
+
'''Часть 1. Функции k-значной логики'''.
  
−
'''[[Media:ivdm-l1-selezn.pdf|Лекция 1]]'''. Универсальная алгебра. Отношения на множестве. Отношение эквивалентности. Операции на множестве. Алгебра. Сохранение функцией отношения. Функции k-значной логики. Существенность переменных.
+
'''Лекция 1'''. Функции k-значной логики. Формулы. Тождества. Представимость функций k-значной логики в 1-й и 2-й формах.
  
−
'''[[Media:ivdm-l2-selezn.pdf|Лекция 2]]'''. Функции k-значной логики. Формулы. Нормальные формы: 1-я и 2-я формы, полиномы по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.
+
'''Лекция 2'''. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.
  
−
'''[[Media:ivdm-l3-selezn.pdf|Лекция 3]]'''. Алгоритм распознавания полноты в k-значной логике. Замкнутые классы. Классы функций, сохраняющие множество, и функций, сохраняющие разбиение, их замкнутость. Теорема Кузнецова. Предполные классы.
+
'''Лекция 3'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
  
−
'''[[Media:ivdm-l4-selezn.pdf|Лекция 4]]'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
+
'''Лекция 4'''. Выразимость и полнота в P_k, их алгоритмическая разрешимость для конечных множеств. Алгоритм распознавания полноты в P_k.
  
−
'''[[Media:ivdm-l5-selezn.pdf|Лекция 5]]'''. Предикаты. Классы функций, сохраняющих предикат, их замкнутость. Предполные классы. Предикатное описание предполных классов.
+
'''Лекция 5'''. Замкнутые классы. Отношения. Сохранение функцией отношения. Замкнутость класса всех функций, сохраняющих заданное отношение. Классы функций, сохраняющих некоторые отношения.
  
−
'''[[Media:ivdm-l6-selezn.pdf|Лекция 6]]'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Существование в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Соответствие Галуа. Задача обобщенной выполнимости.
+
'''Лекция 6'''. Предполные классы. Описание предполных классов. Теорема Кузнецова о предполных классах в P_k.
  
−
Коллоквиум по теме "Конечные функции".
+
'''Лекция 7'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теорема Янова. Теорема Мучника. Мощность множества замкнутых классов в P_k.  
  
−
'''Часть 2. Теория Пойа'''.
+
Коллоквиум по теме "Функции k-значной логики".
  
−
'''[[Media:ivdm-l7-selezn.pdf|Лекция 7]]'''. Группы. Симметрическая группа перестановок S_n. Подгруппы. Теорема Кэли. Цикловой индекс группы перестановок.
+
<!---'''Часть 2. Группы'''.
  
−
'''[[Media:ivdm-l8-selezn.pdf|Лекция 8]]'''. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы. Действие группы на множестве. Орбита и стабилизатор элемента. Лемма Бернсайда.
+
'''Лекция 8'''. Группы. Подгруппы. Смежные классы. Разложение группы по подгруппе. Нормальные подгруппы. Фактор-группы.
  
−
'''[[Media:ivdm-l9-selezn.pdf|Лекция 9]]'''. Раскраски. Эквивалентность раскрасок относительно группы. Теорема Пойа. Производящие функции. Перечисляющий ряд для цветов и перечисляющий ряд для раскрасок. Теорема Пойа (общий случай). Примеры.
+
'''Лекция 9'''. Перестановки. Симметрическая группа перестановок. Теорема Кэли. Орбита и стабилизатор элемента. Лемма Бернсайда.
  
−
Коллоквиум по теме "Теория Пойа".
+
'''Лекция 10'''. Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа. Примеры.
 +
 
 +
Коллоквиум по теме "Группы".
  
 
'''Часть 3. Конечные поля'''.
 
'''Часть 3. Конечные поля'''.
  
−
'''[[Media:ivdm-l10-selezn.pdf|Лекция 10]]'''. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.
+
'''Лекция 11'''. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.
  
−
'''[[Media:ivdm-l11-selezn.pdf|Лекция 11]]'''. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля.
+
'''Лекция 12'''. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля.
  
−
'''Лекция 12'''. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.
+
'''Лекция 13'''. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.
  
 
Коллоквиум по теме "Конечные поля".
 
Коллоквиум по теме "Конечные поля".
 +
--->
  
 
'''Литература'''
 
'''Литература'''
Строка 51: Строка 54:
 
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
 
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
−
# [[Media:ivdm-sem.pdf|Задачи для семинарских занятий]] по теме "Группы. Теория Пойа".
+
<!---# [[Media:ivdm-sem.pdf|Задачи для семинарских занятий]] по теме "Группы. Теория Пойа".
−
# [[Media:ivdm-sem3.pdf|Задачи для семинарских занятий]] по теме "Конечные поля".
+
# [[Media:ivdm-sem3.pdf|Задачи для семинарских занятий]] по теме "Конечные поля".--->
−
 
+
 
Дополнительная:
 
Дополнительная:
  
Строка 64: Строка 66:
 
==Семинары==
 
==Семинары==
  
−
'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.
+
<!---'''Занятие 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(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), 1.12, 2.7(2, 8, 10), 2.12(3, 5), 2.8(2), 2.9, 2.11(1, 2).
+
На дом: [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'''. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам.  
Строка 76: Строка 78:
 
На дом: [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).
  
−
На дом: [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).
Строка 110: Строка 111:
 
[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).--->
  
−
==О проведении экзамена (2020-2021 уч. год)==
+
==О проведении экзамена==
  
−
Экзамен письменный. Экзаменационная работа содержит десять заданий разной сложности по содержанию курса. Первые четыре задания - стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания - формулировки определений или теорем с дополнительными вопросами. Вопросы проясняют понимание студентом определения или теоремы. Они оцениваются также в 3 балла каждое. Оставшиеся два задания - вопросы, связанные с доказательствами, или нестандартные задачи. Они показывают, может ли студент обосновывать утверждения и извлекать новые заключения из полученных знаний в курсе, оцениваются в 4 балла каждое. Продолжительность написания работы - 1 ч 45 мин (105 мин).
 
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Текущая версия на 21:01, 6 сентября 2024

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

Курс "Избранные вопросы дискретной математики" читается в 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-значной логики".


Литература

Основная:

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

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

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

Семинары

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

Источник — «https://mk.cs.msu.ru/index.php?title=Избранные_вопросы_дискретной_математики&oldid=11249»