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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Лекции)
(→‎Литература)
 
(не показаны 132 промежуточных версий 1 участника)
Строка 1: Строка 1:
 
Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
 
Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
  
−
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Форма отчетности - экзамен.
+
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.
  
 
==Объявления==
 
==Объявления==
  
−
==Лекции==
+
==Программа курса==
  
−
'''Часть 1. Конечнозначные функции'''.
+
'''Тема 1. Основы теории множеств.''' Множества, операции над множествами. Мощность множества, конечные множества. Отношения, виды отношений. [1] Гл. 1, разделы 1.1, 1.3; Гл. 3, разделы 3.1, 3.3, 3.5.  
  
−
'''[[Media:ivdm-l1-selezn.pdf|Лекция 1]]'''. Конечнозначные функции. Элементарные k-значные функции. Способы задания k-значных функций: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.
+
Упражнения. [1] Гл. 1, разделы 1.2, 1.4; Гл. 3, разделы 3.2, 3.4, 3.6.
  
−
'''[[Media:ivdm-l2-selezn.pdf|Лекция 2]]'''. Алгоритм распознавания полноты в P_k. Замкнутые классы. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. Предполные классы.
+
'''Тема 2. Функции k-значной логики. Формулы.''' Функции k-значной логики. Таблицы значений, векторы значений. Формулы, эквивалентные формулы, тождества. Эквивалентные преобразования формул, доказательства тождеств. [2] Гл. 1, раздел 1; [3] Гл. 3, стр. 88--89. Упражнения. [3] Гл. 3, N 1.1, 1.2, 1.6, 1.7, 1.8.
  
−
'''[[Media:ivdm-l3-selezn.pdf|Лекция 3]]'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
+
'''Тема 3. Функции k-значной логики. Нормальные формы.''' Представление функций k-значной логики 1-й и 2-й формами. Полные системы. Система Поста. Полнота системы Поста. [2] Гл. 1, раздел 2(до стр. 15); [3] Гл. 3, раздел 1, стр. 91--92. Упражнения. [3] Гл. 3, N 1.11, 1.12.
  
−
'''[[Media:ivdm-l4-selezn.pdf|Лекция 4]]'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Классы функций, сохраняющих предикат, их замкнутость. Соответствие Галуа.
+
'''Тема 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.
  
−
'''Часть 2. Теория Пойа'''.
+
==Литература==
  
−
'''[[Media:ivdm-l5-selezn.pdf|Лекция 5]]'''. Группы. Изоморфизм групп. Симметрическая группа перестановок. Подгруппы. Теорема Кэли.
+
#Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010.
 +
#[[Media:ИзбрГлавыДискрМатем_2015.pdf|Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015.]]
 +
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 +
#[[Media:fsbook_marchenkovss.pdf|Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012.]]
  
−
'''[[Media:ivdm-l6-selezn.pdf|Лекция 6]]'''. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы.
+
<!---'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.
  
−
'''[[Media:ivdm-l7-selezn.pdf|Лекция 7]]'''. Действие группы на множестве. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.
+
[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).
  
−
'''[[Media:ivdm-l8-selezn.pdf|Лекция 8]]'''. Раскраски. Эквивалентность раскрасок относительно группы. Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа.
+
На дом: [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'''. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам.  
  
−
'''Часть 3. Конечные поля'''.
+
[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).
  
−
'''[[Media:ivdm-l9-selezn.pdf|Лекция 9]]'''. Кольца. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Наследование свойств кольца в кольце многочленов. Деление с остатком многочленов над полем.
+
На дом: [4] Гл. III 2.13(7, 8, 9, 10), 2.16(2, 4), 2.19(5, 9, 10, 11, 12), 2.14, 2.15.
  
−
'''[[Media:ivdm-l10-selezn.pdf|Лекция 10]]'''. Идеалы, главные идеалы колец. Кольцо главных идеалов. Теорема о главном идеале кольца главных идеалов. Кольцо многочленов как кольцо главных идеалов. Построение конечных полей из p^n элементов, где p - простое число, n \ge 2.
+
'''Занятие 3'''. Проверка полноты систем функций. Критерий полноты. Система полиномов. Базисы.  
  
−
'''[[Media:ivdm-l11-selezn.pdf|Лекция 11]]'''. Критерий неприводимости многочленов степени 2 или 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).
  
−
'''[[Media:ivdm-l12-selezn.pdf|Лекция 12]]'''
+
На дом: [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).--->
 +
 
 +
==О проведении экзамена==
  
−
'''Литература'''
 
−
 
−
* Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
 
−
* Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
 
−
* Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 
−
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
 
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

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