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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Семинары)
(→‎Лекции)
 
(не показаны 2 промежуточных версий 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 мин, то считается, что студент работу не сдал.--->
 
  
 
==Лекции==
 
==Лекции==
Строка 35: Строка 25:
 
Коллоквиум по теме "Функции k-значной логики".
 
Коллоквиум по теме "Функции k-значной логики".
  
−
'''Часть 2. Группы'''.
+
<!---'''Часть 2. Группы'''.
  
−
'''Лекция 7'''. Группы. Подгруппы. Смежные классы. Разложение группы по подгруппе. Нормальные подгруппы. Фактор-группы.
+
'''Лекция 8'''. Группы. Подгруппы. Смежные классы. Разложение группы по подгруппе. Нормальные подгруппы. Фактор-группы.
  
−
'''Лекция 8'''. Перестановки. Симметрическая группа перестановок. Теорема Кэли. Орбита и стабилизатор элемента. Лемма Бернсайда.
+
'''Лекция 9'''. Перестановки. Симметрическая группа перестановок. Теорема Кэли. Орбита и стабилизатор элемента. Лемма Бернсайда.
  
−
'''Лекция 9'''. Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа. Примеры.
+
'''Лекция 10'''. Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа. Примеры.
  
 
Коллоквиум по теме "Группы".
 
Коллоквиум по теме "Группы".
Строка 47: Строка 37:
 
'''Часть 3. Конечные поля'''.
 
'''Часть 3. Конечные поля'''.
  
−
'''Лекция 10'''. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.
+
'''Лекция 11'''. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.
  
−
'''Лекция 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.
  
 
Коллоквиум по теме "Конечные поля".
 
Коллоквиум по теме "Конечные поля".
 +
--->
  
 
'''Литература'''
 
'''Литература'''

Текущая версия на 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»