Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Избранные вопросы дискретной математики
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Математические методы обработки информации и принятия решений
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299)

1. Дисциплина относится к вариативной части ОПОП ВО.

2. Входные требования для освоения дисциплины (модуля): учащиеся должны владеть знаниями по математическому анализу, линейной алгебре и дискретной математике в объеме, соответствующем программе первых двух лет обучения основных образовательных программ бакалавриата по укрупненным группам направлений и специальностей 01.00.00 «Математика и механика», 02.00.00 «Компьютерные и информационные науки».

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.

Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):

•	ОПК-1.Б Способность применять и адаптировать существующие математические и компьютерные методы для разработки и реализации алгоритмов решения актуальных задач в области фундаментальной и прикладной математики
•	ПК-2.Б Способность понимать и применять в научно-исследовательской деятельности современный математический аппарат
•	СПК-ИВДМ-1.Б Способность понимать и применять алгебраические конструкции при решении задач дискретной математики в профессиональной деятельности.

Планируемые результаты обучения по дисциплине (модулю):

Знать:
1.	основы универсальной алгебры;
2.	основы теории конечнозначных функций, основные способы представления конечнозначных функций и их свойства;
3.	основы теории полноты, критерии полноты конечнозначных функций, основные подходы и методы решения задач распознавания полноты систем конечнозначных функций;
4.	основные свойства замкнутых классов, максимальных и минимальных замкнутых классов конечнозначных функций;
5.	основы теории групп, основные свойства конечных групп; 
6.	основные подходы и методы решения задач подсчета числа классов эквивалентности, определяемых через группы перестановок;
7.	основы теории колец и полей, свойства колец многочленов над конечным полем, основные свойства конечных полей. 

Уметь:  
1.	обосновывать тождества в k-значных логиках;
2.	представлять k-значные функции формулами или нормальными формами;
3.	представлять k-значные функции полиномами по модулю k при простых k и выяснять представимость k-значных функций полиномами по модулю k при составных k;
4.	выяснять полноту систем k-значных функций;
5.	находить левое (правое) регулярное представление Кэли конечных групп;
6.	находить цикловой индекс групп перестановок;
7.	находить число неэквивалентных объектов (без ограничений или с дополнительными ограничениями) относительно группы перестановок;
8.	обосновывать неприводимость многочленов над конечным полем, находить неприводимые многочлены над конечным полем;  
9.	строить конечное поле с заданным число элементов (если оно существует);
10.	находить примитивный элемент конечного поля.

Владеть:
1.	навыками понимания и применения подходов и методов современной алгебры в профессиональной деятельности;
2.	навыками  понимания и применения подходов и методов современной дискретной математики в профессиональной деятельности; 
3.	навыками понимания и применения алгебраических конструкций при решении задач дискретной математики в профессиональной деятельности.

4. Формат обучения: лекции проводятся с применением слайдов, семинарские занятия проводятся с использованием меловой доски.

5. Объем дисциплины (модуля) составляет 3 з.е., в том числе 54 академических часа, отведенных на контактную работу обучающихся с преподавателем, 54 академических часа на самостоятельную работу обучающихся. 

6. Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и виды учебных занятий.
Наименование и краткое содержание разделов и тем дисциплины (модуля),

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Конечнозначные функции. Элементарные k-значные функции. Способы представления k-значных функций: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба. Алгоритм распознавания полноты в P_k. Замкнутые классы. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. Предполные классы.
Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции. Классы функций, сохраняющих предикат, их замкнутость. Предполные классы. Предикатное описание предполных классов. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Существование в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Соответствие Галуа. Задача обобщенной выполнимости.	24	16	4	20	4	
2.	Текущий контроль успеваемости: коллоквиум № 1 по теме «Конечнозначные функции».	4	0	2	2	2	
3.	Группы. Симметрическая группа перестановок S_n. Подгруппы. Теорема Кэли. Цикловой индекс группы перестановок. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы. Действие группы на множестве. Орбита и стабилизатор элемента. Лемма Бернсайда. Раскраски. Эквивалентность раскрасок относительно группы. Теорема Пойа. Производящие функции. Перечисляющий ряд для цветов и перечисляющий ряд для раскрасок. Теорема Пойа (общий случай). Примеры. 	18	10	4	14	4	
4.	Текущий контроль успеваемости: коллоквиум № 2 по теме «Группы. Теория Пойа». 	4	0	2	2	2	
5.	Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля.  Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.	18	10	4	14	4	
6.	Текущий контроль успеваемости: коллоквиум № 3 по теме «Конечные поля».	4	0	2	2	2	
Промежуточная аттестация: устный экзамен	36	0	0	0	36	
Итого	108	36	18	54	54	

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)

7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.

Коллоквиум № 1	
Вариант 1	Вариант 2	

1.	Найти полином по модулю 5 функции f(x) = 2j1(x)+3j2(x) из P5.
2.	Исследовать систему A = {k-2, x+2y, x \dot{-} y} на полноту в Pk. 
3.	Доказать, что система A = {x-2y, xy+x+y} полна в Pk тогда и только тогда, когда k – простое число.
4.	Доказать, что функция f(x, y) = min(x, y) не представима полиномом по модулю k ни при каком составном k.	
1.	Выяснить, представима ли полиномом по модулю 4 функция f(x) = j1(x) + 2j3(x) из P4.
2.	Исследовать систему A = {2, 2x-y, x \dot{-} y} на полноту в Pk. 
3.	Доказать, что система A = {k-2, x+2, xy^2} полна в Pk тогда и только тогда, когда k – простое число.
4.	Доказать, что функция f(x, y) = J1(x)+xy не представима полиномом по модулю k ни при каком составном k.
	
Коллоквиум № 2	
Вариант 1	Вариант 2	

1.	Разложить в произведение циклов перестановку, заданную строкой:  [3,2,1,4,6,5,8,7], и найти ее тип. 
2.	Найти левое регулярное представление Кэли группы сложений по модулю 6 чисел {0, 1, 2, 3, 4, 5} и найти цикловой индекс полученной группы перестановок. 
3.	По теореме Пойа найти число различных ожерелий из 5-ти бусин 4-х цветов, красного, синего, зеленого и белого, в которых ровно 2 зеленые бусины.
4.	По теореме Пойа найти число кубов, не переводящихся друг в друга вращениями в пространстве, с гранями двух цветов.  
	
1.	Разложить в произведение циклов перестановку, заданную строкой: [4,5,8,6,2,1,7,3], и найти ее тип. 
2.	Найти левое регулярное представление Кэли группы сложений по модулю 5 чисел {0, 1, 2, 3, 4} и найти цикловой индекс полученной группы перестановок. 
3.	По теореме Пойа найти число различных ожерелий из 6-ти бусин 4-х цветов, красного, синего, зеленого и белого, в которых ровно 3 синие бусины.
4.	По теореме Пойа найти число кубов, не переводящихся друг в друга вращениями в пространстве, с гранями трех цветов.  
	
Коллоквиум № 3	
Вариант 1	Вариант 2	

1.	Поделить с остатком многочлен f(x) = 2 x^5 + x^4 + 2 x + 1 на многочлен g(x) =  x^2 + 1 над полем Z3. 
2.	Выяснить, является ли многочлен f(x) = x^4 + x + 4 неприводимым над полем Z5. 
3.	Выяснить, является ли фактор-кольцо Z2[x]/(x^5 + x^2 + 1) полем. 
4.	Найти какой-то примитивный элемент поля Z19.
	
1.	Поделить с остатком многочлен f(x) = 2 x^4 + x^3 +  x + 2 на многочлен g(x) =  x^2 +  над полем Z3. 
2.	Выяснить, является ли многочлен f(x) = x^4 + x^2 + 2 неприводимым над полем Z5. 
3.	Выяснить, является ли фактор-кольцо Z2[x]/(x^5 + x^4 + 1) полем. 
5.	4. Найти какой-то примитивный элемент поля Z15.	

7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации.

Вопросы к экзамену.

В билете два вопроса (один из части А и один из части Б) и задача.  

Часть А – ответ без подготовки по любым бумажным материалам (конспектам, книгам, распечаткам лекций и т.д.); проверяется понимание доказательств;  определения и теоремы формулируются без конспектов. Электронными средствами (компьютерами, телефонами и т.д.) на экзамене пользоваться не разрешается.

1.	Теорема о полноте системы Поста и следствия из нее. Функция Вебба. 
2.	Теорема Кузнецова о функциональной полноте. Предполные классы. 
3.	Существенные функции. Лемма о трех наборах. 
4.	Критерий полноты Яблонского. Критерий Слупецкого. 
5.	Основной предикат замкнутого класса. Предикатное описание предполных классов, содержащих не все функции одной переменной. 
6.	Основной предикат замкнутого класса. Предикатное описание предполного класса, содержащего все функции одной переменной. Класс Слупецкого. 
7.	Симметрическая группа перестановок. Теорема Кэли. 
8.	Действие группы на множестве. Теорема об индексе стабилизатора элемента. 
9.	Действие группы на множестве. Лемма Бернсайда. 
10.	Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа (частный случай). 
11.	Перечисляющие ряды для цветов и для раскрасок. Теорема Пойа (общий случай). 
12.	Наибольший общий делитель двух многочленов над полем. Теорема о его существовании и единственности. 
13.	Теорема о мультипликативной группе конечного поля. Примитивный элемент конечного поля. 
14.	Теорема о произведении неприводимых нормированных многочленов над простым полем. 
15.	Формула обращения Мебиуса. Теорема о числе неприводимых многочленов степени n над простым полем. Существование поля из p^n элементов, где p – простое число, n ≥ 1. 
16.	Расширения полей. Теорема о корнях неприводимых многочленов в расширении простого поля. 
17.	Расширения полей. Теорема о свойствах корней неприводимых многочленов в расширении простого поля.

Часть Б – ответ без конспектов и без подготовки.

18.	Теоремы о представлении k-значных функций в 1-й и 2-й формах. 
19.	Теорема о представлении k-значных функций полиномами по модулю k.
20.	Полные системы. Алгоритм распознавания полноты в P_k.
21.	Замкнутые классы. Классы функций, сохраняющих множество, их замкнутость и критерий совпадения с P_k.
22.	Замкнутые классы. Классы функций, сохраняющих разбиение, их замкнутость и критерий совпадения с P_k.
23.	Замкнутые классы. Классы функций, сохраняющих предикат, их замкнутость.
24.	Существенные функции. Основная лемма и лемма о квадрате.
25.	Полные системы, шефферовы функции. Критерий шефферовости k-значной функции. 
26.	Базис замкнутого класса. Теорема Янова о существовании в P_k при k ≥ 3 замкнутого класса без базиса.
27.	Базис замкнутого класса. Теорема Мучника о существовании в P_k при k ≥ 3 замкнутого класса со счетным базисом. Мощность множества замкнутых классов в P_k при k ≥ 3.
28.	Группы, их простейшие свойства. Правило сокращения в группе. Конечные коммутативные группы, их свойства.
29.	Подгруппы, критерий подгруппы. Смежные классы. Теорема Лагранжа.
30.	Действие группы на множестве. Цикловой индекс группы. Орбита и стабилизатор элемента. 
31.	Кольца, их виды. Поля. Теорема о конечном целостном кольце. Простое поле.
32.	Характеристика кольца. Характеристика конечного целостного кольца.
33.	Кольцо многочленов над кольцом. Наследование свойств кольца в кольце многочленов.
34.	Кольцо многочленов над полем. Деление с остатком многочленов над полем.
35.	Приводимые и неприводимые многочлены над полем. Корни многочленов. Критерий неприводимости над полем для многочленов степени два и три.
36.	Теорема о поле по модулю многочлена над полем. Построение поля из p^n элементов, где p – простое число, n ≥ 1.
37.	Наибольший общий делитель двух многочленов над полем. Алгоритм Евклида его нахождения. Нахождение обратного элемента в поле.

Типовые задачи для экзамена.

1.	Доказать заданное тождество в k-значной логике.
2.	Представить заданную k-значную функцию в 1-й или 2-й форме при заданном k.
3.	Найти полином по модулю k заданной k-значной функции при заданном простом k.
4.	Выяснить, можно ли представить заданную k-значную функцию полиномом по модулю k при заданном составном k.
5.	Исследовать заданную систему k-значных функций на полноту при каждом k.
6.	Найти левое (правое) регулярное представление Кэли для заданной конечной группы.
7.	Найти цикловой индекс заданной группы перестановок.
8.	Найти число объектов (без ограничений или с дополнительными ограничениями), неэквивалентных относительно заданной группы перестановок.
9.	Поделить с остатком многочлены над конечным полем.
10.	Найти наибольший общий делитель двух многочленов над конечным полем.
11.	Выяснить, является ли заданный многочлен неприводимым над заданным конечным полем.
12.	Построить конечное поле с заданным числом элементов (если это возможно).
13.	Найти обратный элемент к заданному элементу в заданном конечном поле.
14.	Найти какой-то примитивный элемент заданного конечного поля.
		
Экзаменационный билет состоит из двух вопросов и задачи, например

1.	Теорема Кузнецова о функциональной полноте. Предполные классы.
2.	Группы, их простейшие свойства. Правило сокращения в группе. Конечные коммутативные группы, их свойства.
3.	Построить конечное поле с девятью элементами. 

ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Коллоквиум,
Экзамен	Отсутствие знаний	Отдельные знания	Общие, но не структурированные знания	Сформированные систематические знания	
Умения
Контрольная работа, зачет
	Отсутствие умений	В целом успешное, но не систематическое умение	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципиального характера)	Успешное и систематическое умение	
Навыки 
(владения, опыт деятельности)
Экзамен	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие частичного опыта)	В целом, сформированные навыки (владения), но недостаточно используемые 	Сформированные навыки (владения), применяемые при решении задач	

Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)
	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	основы универсальной алгебры;
2.	основы теории групп, основные свойства конечных групп; 
3.	основы теории колец и полей, свойства колец многочленов над конечным полем, основные свойства конечных полей. 
Уметь: 
1.	обосновывать тождества в многозначных логиках;
2.	находить левое (правое) регулярное представление Кэли конечных групп;
3.	находить цикловой индекс групп перестановок;
4.	обосновывать неприводимость многочленов над конечным полем, находить неприводимые многочлены над конечным полем;  
5.	строить конечное поле с заданным число элементов (если оно существует);
6.	находить примитивный элемент конечного поля.
Владеть:  
1.	навыками понимания и применения подходов и методов современной алгебры в профессиональной деятельности.	

ОПК-1.Б	
Знать:
1.	основы теории конечнозначных функций, основные способы представления конечнозначных функций и их свойства;
2.	основы теории полноты, критерии полноты конечнозначных функций, основные подходы и методы решения задач распознавания полноты систем конечнозначных функций;
3.	основные свойства замкнутых классов, максимальных и минимальных замкнутых классов конечнозначных функций;
4.	основные подходы и методы решения задач подсчета числа классов эквивалентности, определяемых через группы перестановок;
Уметь:  
1.	представлять k-значные функции формулами или нормальными формами;
2.	представлять k-значные функции полиномами по модулю k при простых k и выяснять представимость k-значных функций полиномами по модулю k при составных k;
3.	выяснять полноту систем k-значных функций;
4.	находить число неэквивалентных объектов (без ограничений или с дополнительными ограничениями) относительно группы перестановок
Владеть:  
1.	навыками понимания и применения подходов и методов современной дискретной математики в профессиональной деятельности.

ПК-2.Б	
Владеть:  
1.	навыками понимания и применения алгебраических конструкций при решении задач дискретной математики в профессиональной деятельности.

СПК-ИВДМ-1.Б	

8. Ресурсное обеспечение: http://mk.cs.msu.ru/index.php/Избранные_вопросы_дискретной_математики  - страница курса со всеми материалами

Основная литература:
  
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.

Информационные справочные системы: http://mk.cs.msu.ru/index.php/Избранные_вопросы_дискретной_математики - страница курса со всеми материалами

Материально-техническое обеспечение: аудитория с партами, проектором, экраном и меловой доской для лекций; аудитория с партами и меловой доской для семинарских занятий.

9. Язык преподавания:	русский.

10. Преподаватели:  		профессор факультета ВМК МГУ С.Н. Селезнева.
.
11. Авторы программы:  	профессор факультета ВМК МГУ С.Н. Селезнева.