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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Лекции)
 
(не показаны 139 промежуточные версии 1 участника)
Строка 1: Строка 1:
 
Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
 
Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
  
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций). Форма отчетности - экзамен.
+
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.
  
 
==Объявления==
 
==Объявления==
  
[[Media:ivdm-2015.docx|Результаты экзамена 20.01.2016 г. (группа 318)]]
+
==Лекции==
  
Апелляция и выставление оценок состоятся в субботу, 23 января, в 12 ч в ауд. 595.
+
'''Часть 1. Функции k-значной логики'''.
  
==Лекции==
+
'''Лекция 1'''. Функции k-значной логики. Формулы. Тождества. Представимость функций k-значной логики в 1-й и 2-й формах.
[[Media:dm_lection1.pdf|Лекция 1]]: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.
+
  
[[Media:dm_lection2.pdf|Лекция 2]]: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.
+
'''Лекция 2'''. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.
  
[[Media:dm_lection3.pdf|Лекция 3]]: Частично упорядоченные множества (ЧУМ). Диаграмма ЧУМ. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Единичный n-мерный куб, его длина и ширина.  
+
'''Лекция 3'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
  
[[Media:dm_lection4.pdf|Лекция 4]]: Теорема Анселя о разбиении n-мерного куба на цепи. Оценки числа монотонных функций алгебры логики. Расшифровка монотонных функций алгебры логики.
+
'''Лекция 4'''. Выразимость и полнота в P_k, их алгоритмическая разрешимость для конечных множеств. Алгоритм распознавания полноты в P_k.
  
[[Media:dm_lection5.pdf|Лекция 5]]: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества n-мерного куба и длины полиномиальных нормальных форм функций алгебры логики.
+
'''Лекция 5'''. Замкнутые классы. Отношения. Сохранение функцией отношения. Замкнутость класса всех функций, сохраняющих заданное отношение. Классы функций, сохраняющих некоторые отношения.
  
[[Media:dm_lection6.pdf|Лекция 6]]: Коллоквиум 1.
+
'''Лекция 6'''. Предполные классы. Описание предполных классов. Теорема Кузнецова о предполных классах в P_k.
  
[[Media:dm_lection7.pdf|Лекция 7]]: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.
+
'''Лекция 7'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теорема Янова. Теорема Мучника. Мощность множества замкнутых классов в P_k.  
  
[[Media:dm_lection8.pdf|Лекция 8]]: Линейные однородные и неоднородные рекуррентные уравнения.
+
Коллоквиум по теме "Функции k-значной логики".
  
[[Media:dm_lection9.pdf|Лекция 9]]: Группы. Изоморфизм групп. Симметрическая группа перестановок. Теорема Кэли.
+
<!---'''Часть 2. Группы'''.
  
[[Media:dm_lection10.pdf|Лекция 10]]: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.
+
'''Лекция 8'''. Группы. Подгруппы. Смежные классы. Разложение группы по подгруппе. Нормальные подгруппы. Фактор-группы.
  
[[Media:dm_lection11.pdf|Лекция 11]]: Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай). Примеры.
+
'''Лекция 9'''. Перестановки. Симметрическая группа перестановок. Теорема Кэли. Орбита и стабилизатор элемента. Лемма Бернсайда.
  
[[Media:dm_lection12.pdf|Лекция 12]]: Коллоквиум 2.
+
'''Лекция 10'''. Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа. Примеры.
  
[[Media:dm_lection15.pdf|Лекция 13]]: Функции k-значной логики и способы их представления. Полные системы. Полнота системы Поста.
+
Коллоквиум по теме "Группы".
  
[[Media:dm_lection13.pdf|Лекция 14]]: Кольца. Теорема о конечном целостном кольце. Кольцо многочленов.
+
'''Часть 3. Конечные поля'''.
  
[[Media:dm_lection14.pdf|Лекция 15]]: Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.
+
'''Лекция 11'''. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.
  
[[Media:dm_lection16.pdf|Лекция 16]]: Коллоквиум 3.
+
'''Лекция 12'''. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля.
  
==Вопросы к экзамену==
+
'''Лекция 13'''. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.
'''(осенний  семестр 2015/2016 учебного года, группа 318, лектор — доцент С.Н. Селезнева)'''
+
 
 +
Коллоквиум по теме "Конечные поля".
 +
--->
  
* Выборки. Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
 
* Теоремы о свойствах последовательности биномиальных коэффициентов. Полиномиальные коэффициенты. Теорема о верхней оценке биномиального коэффициента и ее следствие. Теорема об асимптотике некоторой суммы биномиальных коэффициентов.
 
* Частично упорядоченные множества (ЧУМ). Диаграмма ЧУМ. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. n-мерный куб. Теоремы о длине и ширине n-мерного куба. Изоморфизм ЧУМ.
 
* Теорема Анселя о разбиениии n-мерного куба на цепи. Теорема о числе монотонных функций алгебры логики. Теорема о расшифровке монотонных функций алгебры логики.
 
* Покрытие множества и покрытие матрицы. Градиентное покрытие. Лемма о градиентном покрытии. Теорема об оценках мощности затеняющего множества n-мерного куба. Оценки длины полиномиальных нормальных форм функций алгебры логики.
 
* Функция Мёбиуса на ЧУМ. Функция Мёбиуса на n-мерном кубе. Формула обращения Мёбиуса. Формула включений-исключений. Задача о подсчете числа перестановок-беспорядков.
 
* Последовательности. Однородные линейные рекуррентные уравнения (ЛОРУ). Частные и общие решения ЛОРУ. Теорема о линейной комбинации частных решений ЛОРУ. Характеристический многочлен ЛОРУ. Теоремы о частном решении ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ). Теоремы об общем решении ЛНРУ.
 
* Группы, виды групп. Изоморфизм групп. Симметрическая группа перестановок и ее свойства. Подгруппы. Теорема Кэли. Представления Кэли.
 
* Подгруппы, смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы, фактор-группа. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.
 
* Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай, только формулировка).
 
* Функции конечнозначных логик. Элементарные функции k-значной логики. Способы задания функций k-значных логик: таблицы, формулы. Теоремы о представимости функций k-значных логик в I-й и II-й формах. Теорема о представимости функций k-значных логик полиномами. Операция замыкания. Замкнутый класс и полная система. Теорема о полноте системы Поста и ее следствия.
 
* Кольца, виды колец. Теорема о конечном целостном кольце. Кольцо многочленов. Теорема о наследовании свойств кольца в кольце многочленов над этим кольцом. Подкольцо. Идеал кольца. Главный идеал кольца. Кольцо главных идеалов. Деление с остатком многочленов над полем. Теорема о кольце многочленов над полем как кольце главных идеалов. Вычеты по модулю идеала. Фактор-кольцо.
 
* Неприводимые и приводимые многочлены над полем. Корень многочлена. Критерий неприводимости над полем многочленов степени два и три. Теорема о фактор-кольце кольца многочленов над полем по модулю главного идеала. Поле остатков неприводимого многочлена над конечным полем, операции сложения и умножения в нем. Вычисление обратного элемента по алгоритму Евклида. Понятие расширения поля. Мультипликативная группа конечного поля и ее свойства (только формулировка теоремы).
 
 
 
'''Литература'''
 
'''Литература'''
 +
 +
Основная:
 
   
 
   
* Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
+
# Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
* Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
+
# Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
* Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М.: Мир, 1968, с. 53-57.
+
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
* Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М.: Мир, 1966, с. 61-107.
+
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 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.
  
* Подсчитать число объектов с заданными свойствами.
+
==Семинары==
* Найти значение суммы комбинаторных чисел или доказать комбинаторное тождество.
+
* Применить формулу включений-исключений для нахождения искомого значения.
+
* Найти длину или ширину заданного конечного ЧУМ или построить ЧУМ с заданными свойствами.
+
* Найти градиентное покрытие заданной матрицы и оценить его мощность.
+
* Решить данное ЛОРУ или ЛНРУ.
+
* Найти цикловой индекс группы перестановок.
+
* Найти число орбит раскрасок (возможно, с ограничениями) относительно данной группы перестановок.
+
* Определить приводимость или неприводимость многочлена над полем.
+
* Выяснить, является ли заданное фактор-кольцо кольца многочленов по модулю главного идеала полем.
+
* Построить таблицы сложения и умножения элементов поля остатков неприводимого многочлена над конечным полем.
+
* По алгоритму Евклида найти обратный элемент в поле остатков неприводимого многочлена над конечным полем.
+
* Записать данную функцию k-значной логики в I-й, II-й формах или полиномом.
+
* Выяснить, представима ли заданная функция k-значной логики (при составном k) полиномом.
+
  
'''Литература'''  
+
<!---'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.
+
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004. Гл. III 1.11, 2.7, 2.20, 2.21, 2.22, 2.23; гл. IV 2.1, 2.17, 2.18; гл. V 2.1, 2.2, 2.3, 2.4, 2.5; гл. VIII 4.1, 4.3, 4.4, 4.9, 4.10.
+
* Лидл Р. Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988.
+
  
==О проведении экзамена==
+
[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).
Экзамен проходит письменно. При написании экзаменационной работы не разрешается пользоваться никакими материалами. За экзаменационную работу студент получает определенное количество баллов.
+
  
В течение семестра по курсу проходят три письменных коллоквиума. При написании коллоквиума не разрешается пользоваться никакими материалами. За каждый коллоквиум студент получает определенные баллы (н/я или 0 - (-3) балла, 1-4 - (-2) балла, 5-9 - (-1) балл, 10-14 - 0 баллов, 15-19 - (+1) балл, 20-24 - (+2) балла, 25 - (+3) балла).
+
На дом: [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'''. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам.  
  
Экзаменационная работа состоит из 14 заданий. Задания 1-5 - стандартные задачи (перечень типов предлагаемых задач ниже). Проверяется, насколько студент усвоил методы решения задач по курсу. Каждая задача оценивается в 3 балла. Задания 6-10 - определения и формулировки теорем с дополнительным вопросом. Дополнительный вопрос проясняет, насколько студент понимает определение или формулировку теоремы, может ли привести их частный случай или пояснить на примере. Каждое из заданий 6-10 оценивается в 3 балла. Задания 11-13 - доказательства теорем курса или их частей и частных случаев. Проверяется, как студент усвоил доказательства основных утверждений курса. Каждое из заданий 11-13 оценивается в 3 балла. Задание 14 - нестандартная задача. Проверяется, насколько студент может применять полученные в курсе знания при решении новых задач. Задание 14 оценивается в 4 балла. Продолжительность написания экзаменационной работы - 2 астрономических часа (120 минут).
+
[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).
  
Критерии оценок:
+
На дом: [4] Гл. III 2.13(7, 8, 9, 10), 2.16(2, 4), 2.19(5, 9, 10, 11, 12), 2.14, 2.15.
* 36-43 баллов - "отлично";
+
 
* 27-35 баллов - "хорошо";
+
'''Занятие 3'''. Проверка полноты систем функций. Критерий полноты. Система полиномов. Базисы.
* 17-26 баллов - "удовлетворительно";
+
 
* менее 17 баллов - "неудовлетворительно".
+
[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'''. Группы, подгруппы, теорема Кэли. Цикловой индекс группы перестановок.
 +
 
 +
[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).--->
 +
 
 +
==О проведении экзамена==
  
[[Media: Exam-ivdm.pdf|Примерный вариант экзаменационной работы с решениями заданий]]
 
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

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

Семинары

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