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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Литература)
 
(не показаны 12 промежуточные версии 1 участника)
Строка 5: Строка 5:
 
==Объявления==
 
==Объявления==
  
−
==Лекции==
+
==Программа курса==
  
−
'''Часть 1. Функции k-значной логики'''.
+
'''Тема 1. Основы теории множеств.''' Множества, операции над множествами. Мощность множества, конечные множества. Отношения, виды отношений. [1] Гл. 1, разделы 1.1, 1.3; Гл. 3, разделы 3.1, 3.3, 3.5.  
  
−
'''Лекция 1'''. Функции k-значной логики. Формулы. Тождества. Представимость функций k-значной логики в 1-й и 2-й формах.
+
Упражнения. [1] Гл. 1, разделы 1.2, 1.4; Гл. 3, разделы 3.2, 3.4, 3.6.
  
−
'''Лекция 2'''. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.
+
'''Тема 2. Функции k-значной логики. Формулы.''' Функции k-значной логики. Таблицы значений, векторы значений. Формулы, эквивалентные формулы, тождества. Эквивалентные преобразования формул, доказательства тождеств. [2] Гл. 1, раздел 1; [3] Гл. 3, стр. 88--89. Упражнения. [3] Гл. 3, N 1.1, 1.2, 1.6, 1.7, 1.8.
  
−
'''Лекция 3'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
+
'''Тема 3. Функции k-значной логики. Нормальные формы.''' Представление функций k-значной логики 1-й и 2-й формами. Полные системы. Система Поста. Полнота системы Поста. [2] Гл. 1, раздел 2(до стр. 15); [3] Гл. 3, раздел 1, стр. 91--92. Упражнения. [3] Гл. 3, N 1.11, 1.12.
  
−
'''Лекция 4'''. Выразимость и полнота в P_k, их алгоритмическая разрешимость для конечных множеств. Алгоритм распознавания полноты в P_k.
+
'''Тема 4. Функции k-значной логики. Полиномы.''' Полиномы по модулю k. Представление функций k-значной логики полиномами по модулю k. Вычисление коэффициентов полиномов функций k-значной логики. [2] Гл. 1, раздел 2(стр. 15--16); [3] Гл. 3, раздел 2, стр. 93--95. Упражнения. [3] Гл. 3, N 2.7, 2.8, 2.11, 2.12, 2.23.
  
−
'''Лекция 5'''. Замкнутые классы. Отношения. Сохранение функцией отношения. Замкнутость класса всех функций, сохраняющих заданное отношение. Классы функций, сохраняющих некоторые отношения.
+
'''Коллоквиум 1''' по темам 2--4.
  
−
'''Лекция 6'''. Предполные классы. Описание предполных классов. Теорема Кузнецова о предполных классах в P_k.
+
==Литература==
  
−
'''Лекция 7'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теорема Янова. Теорема Мучника. Мощность множества замкнутых классов в P_k.
+
#Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010.
−
 
+
#[[Media:ИзбрГлавыДискрМатем_2015.pdf|Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015.]]
−
Коллоквиум по теме "Функции k-значной логики".
+
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
−
 
+
#[[Media:fsbook_marchenkovss.pdf|Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012.]]
−
'''Часть 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.
+
−
<!---# [[Media:ivdm-sem.pdf|Задачи для семинарских занятий]] по теме "Группы. Теория Пойа".
+
−
# [[Media:ivdm-sem3.pdf|Задачи для семинарских занятий]] по теме "Конечные поля".--->
+
−
Дополнительная:
+
−
 
+
−
# Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2016. Глава 1.
+
−
# Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. Глава 1.
+
−
# Яблонский С.В., Гаврилов Г.П., Набебин А.А. Предполные классы в многозначных логиках. М.: МЭИ, 1997. Часть 1.
+
−
# Lau D. Function Algebras on Finite Sets. Springer, 2006.
+
−
# Горшков С.П., Тарасов А.В. Сложность решения систем булевых уравнений. М.: Курс, 2017.
+
−
 
+
−
==Семинары==
+
  
 
<!---'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.
 
<!---'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.

Текущая версия на 20:47, 21 октября 2025

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

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

Объявления

Программа курса

Тема 1. Основы теории множеств. Множества, операции над множествами. Мощность множества, конечные множества. Отношения, виды отношений. [1] Гл. 1, разделы 1.1, 1.3; Гл. 3, разделы 3.1, 3.3, 3.5.

Упражнения. [1] Гл. 1, разделы 1.2, 1.4; Гл. 3, разделы 3.2, 3.4, 3.6.

Тема 2. Функции k-значной логики. Формулы. Функции k-значной логики. Таблицы значений, векторы значений. Формулы, эквивалентные формулы, тождества. Эквивалентные преобразования формул, доказательства тождеств. [2] Гл. 1, раздел 1; [3] Гл. 3, стр. 88--89. Упражнения. [3] Гл. 3, N 1.1, 1.2, 1.6, 1.7, 1.8.

Тема 3. Функции k-значной логики. Нормальные формы. Представление функций k-значной логики 1-й и 2-й формами. Полные системы. Система Поста. Полнота системы Поста. [2] Гл. 1, раздел 2(до стр. 15); [3] Гл. 3, раздел 1, стр. 91--92. Упражнения. [3] Гл. 3, N 1.11, 1.12.

Тема 4. Функции k-значной логики. Полиномы. Полиномы по модулю k. Представление функций k-значной логики полиномами по модулю k. Вычисление коэффициентов полиномов функций k-значной логики. [2] Гл. 1, раздел 2(стр. 15--16); [3] Гл. 3, раздел 2, стр. 93--95. Упражнения. [3] Гл. 3, N 2.7, 2.8, 2.11, 2.12, 2.23.

Коллоквиум 1 по темам 2--4.

Литература

  1. Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010.
  2. Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015.
  3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
  4. Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012.


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

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