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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Объявления)
(→‎Литература)
 
(не показаны 92 промежуточных версий 1 участника)
Строка 5: Строка 5:
 
==Объявления==
 
==Объявления==
  
−
Консультация по курсу состоится 13 января (в субботу) с 12 ч 30 мин в ауд. 507.
+
==Программа курса==
  
−
Появились результаты коллоквиума № 3. Работы можно посмотреть 29 декабря с 13 ч до 14 ч в к. 595 или после консультации 13 января.
+
'''Тема 1. Основы теории множеств.''' Множества, операции над множествами. Мощность множества, конечные множества. Отношения, виды отношений. [1] Гл. 1, разделы 1.1, 1.3; Гл. 3, разделы 3.1, 3.3, 3.5.  
  
−
[[Media:ivdm-kolok17.docx|Результаты коллоквиумов]]
+
Упражнения. [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.
  
−
'''Часть 1. Конечнозначные функции'''.
+
'''Тема 3. Функции k-значной логики. Нормальные формы.''' Представление функций k-значной логики 1-й и 2-й формами. Полные системы. Система Поста. Полнота системы Поста. [2] Гл. 1, раздел 2(до стр. 15); [3] Гл. 3, раздел 1, стр. 91--92. Упражнения. [3] Гл. 3, N 1.11, 1.12.
  
−
'''[[Media:ivdm-l1-selezn.pdf|Лекция 1]]'''. Конечнозначные функции. Элементарные k-значные функции. Способы представления k-значных функций: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.
+
'''Тема 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.
  
−
'''[[Media:ivdm-l2-selezn.pdf|Лекция 2]]'''. Алгоритм распознавания полноты в P_k. Замкнутые классы. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. Предполные классы.
+
'''Коллоквиум 1''' по темам 2--4.
  
−
'''[[Media:ivdm-l3-selezn.pdf|Лекция 3]]'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
+
==Литература==
  
−
'''[[Media:ivdm-l4-selezn.pdf|Лекция 4]]'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Классы функций, сохраняющих предикат, их замкнутость. Соответствие Галуа.
+
#Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010.
 +
#[[Media:ИзбрГлавыДискрМатем_2015.pdf|Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015.]]
 +
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 +
#[[Media:fsbook_marchenkovss.pdf|Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012.]]
  
−
Коллоквиум по теме "Конечнозначные функции".
+
<!---'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.
  
−
'''Часть 2. Теория Пойа'''.
+
[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-l5-selezn.pdf|Лекция 5]]'''. Группы. Изоморфизм групп. Симметрическая группа перестановок. Подгруппы. Теорема Кэли.
+
На дом: [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).
−
 
+
−
'''[[Media:ivdm-l6-selezn.pdf|Лекция 6]]'''. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы.
+
−
 
+
−
'''[[Media:ivdm-l7-selezn.pdf|Лекция 7]]'''. Действие группы на множестве. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.
+
−
 
+
−
'''[[Media:ivdm-l8-selezn.pdf|Лекция 8]]'''. Раскраски. Эквивалентность раскрасок относительно группы. Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа.
+
−
 
+
−
Коллоквиум по теме "Теория Пойа".
+
−
 
+
−
'''Часть 3. Конечные поля'''.
+
−
 
+
−
'''[[Media:ivdm-l9-selezn.pdf|Лекция 9]]'''. Кольца. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Наследование свойств кольца в кольце многочленов. Деление с остатком многочленов над полем.
+
−
 
+
−
'''[[Media:ivdm-l10-selezn.pdf|Лекция 10]]'''. Идеалы, главные идеалы колец. Кольцо главных идеалов. Теорема о главном идеале кольца главных идеалов. Кольцо многочленов как кольцо главных идеалов. Построение конечных полей из p^n элементов, где p - простое число, n \ge 2.
+
−
 
+
−
'''[[Media:ivdm-l11-selezn.pdf|Лекция 11]]'''. Критерий неприводимости многочленов степени 2 или 3. Расширения полей. Вычисления в полях, алгоритм Евклида. Теорема о мультипликативной группе конечного поля.
+
−
 
+
−
'''[[Media:ivdm-l12-selezn.pdf|Лекция 12]]'''. Произведение неприводимых многочленов над простым полем. Число неприводимых нормированных многочленов над простым полем. Корни неприводимых многочленов над полем в его расширении. Существование и единственность поля из p^n элементов, где p - простое число, n \ge 1.
+
−
 
+
−
Коллоквиум по теме "Конечные поля".
+
−
 
+
−
'''Литература'''
+
−
+
−
# Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
+
−
# Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
+
−
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
+
−
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
+
−
# [[Media:ivdm-sem.pdf|Задачи для семинарских занятий]] по теме "Группы. Теория Пойа".
+
−
# [[Media:ivdm-sem3.pdf|Задачи для семинарских занятий]] по теме "Конечные поля".
+
−
 
+
−
==Семинары==
+
−
 
+
−
'''Занятие 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(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).
+
  
 
'''Занятие 2'''. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам.  
 
'''Занятие 2'''. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам.  
Строка 72: Строка 38:
 
На дом: [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).
Строка 106: Строка 71:
 
[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).--->
  
 
==О проведении экзамена==
 
==О проведении экзамена==
  
−
Экзамен устный. В билете два теоретических вопроса и задача. Ответ на вопросы билета без подготовки. При ответе на первый вопрос можно пользоваться любыми бумажными источниками (конспектами лекций, распечатками, книгами). При ответе на второй вопрос никакими источниками пользоваться не разрешается. Задача на одну из трех тем. В течение семестра по каждой из этих тем состоятся коллоквиумы. На каждом из них можно получить одну из трех оценок: 1 (освобождение от задачи), 0,5 или 0 (дополнительная задача). При наличии дополнительных задач по итогам коллоквиумов студент решает эти задачи до того, как возьмет билет.
 
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

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