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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Объявления)
(Лекции)
(не показаны 27 промежуточные версии 1 участника)
Строка 1: Строка 1:
Курс читает [[Селезнева Светлана Николаевна|Селезнева С.Н.]]
+
Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
 +
 
 +
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.
  
 
==Объявления==
 
==Объявления==
  
[[Media:ivdm-2015.docx|Результаты экзамена 20.01.2016 г. (группа 318)]]
+
==Лекции==
  
==О курсе==
+
'''Часть 1. Конечнозначные функции'''.
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре. Форма отчетности - экзамен. Экзамен проходит письменно. При написании экзаменационной работы не разрешается пользоваться никакими материалами. За экзаменационную работу студент получает определенное количество баллов.
+
  
В течение семестра по курсу проходят три письменных коллоквиума. При написании коллоквиума не разрешается пользоваться никакими материалами. За каждый коллоквиум студент получает определенные баллы (н/я или 0 - (-3) балла, 1-4 - (-2) балла, 5-9 - (-1) балл, 10-14 - 0 баллов, 15-19 - (+1) балл, 20-24 - (+2) балла, 25 - (+3) балла).
+
'''[[Media:ivdm-l1-selezn.pdf|Лекция 1]]'''. Конечнозначные функции. Элементарные k-значные функции. Способы представления k-значных функций: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.
  
Оценка на экзамене по курсу выставляется по следующему правилу: количество баллов, полученное студентом за экзаменационную работу, складывается с баллами за коллоквиумы; по вычисленному значению выводится оценка по критериям экзамена. На пересдаче баллы за коллоквиумы не учитываются, оценка за экзамен выводится только по баллам за экзаменационную работу.
+
'''[[Media:ivdm-l2-selezn.pdf|Лекция 2]]'''. Алгоритм распознавания полноты в P_k. Замкнутые классы. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. Предполные классы.
  
Экзаменационная работа состоит из 14 заданий. Задания 1-5 - стандартные задачи (перечень типов предлагаемых задач ниже). Проверяется, насколько студент усвоил методы решения задач по курсу. Каждая задача оценивается в 3 балла. Задания 6-10 - определения и формулировки теорем с дополнительным вопросом. Дополнительный вопрос проясняет, насколько студент понимает определение или формулировку теоремы, может ли привести их частный случай или пояснить на примере. Каждое из заданий 6-10 оценивается в 3 балла. Задания 11-13 - доказательства теорем курса или их частей и частных случаев. Проверяется, как студент усвоил доказательства основных утверждений курса. Каждое из заданий 11-13 оценивается в 3 балла. Задание 14 - нестандартная задача. Проверяется, насколько студент может применять полученные в курсе знания при решении новых задач. Задание 14 оценивается в 4 балла. Продолжительность написания экзаменационной работы - 2 астрономических часа (120 минут).
+
'''[[Media:ivdm-l3-selezn.pdf|Лекция 3]]'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
  
Критерии оценок:
+
'''[[Media:ivdm-l4-selezn.pdf|Лекция 4]]'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Классы функций, сохраняющих предикат, их замкнутость. Соответствие Галуа.
* 36-43 баллов - "отлично";
+
* 27-35 баллов - "хорошо";
+
* 17-26 баллов - "удовлетворительно";
+
* менее 17 баллов - "неудовлетворительно".
+
  
[[Media: Exam-ivdm.pdf|Примерный вариант экзаменационной работы с решениями заданий]]
+
Коллоквиум по теме "Конечнозначные функции".
  
==Лекции==
+
'''Часть 2. Теория Пойа'''.
[[Media:dm_lection1.pdf|Лекция 1]]: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.
+
  
[[Media:dm_lection2.pdf|Лекция 2]]: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.
+
'''[[Media:ivdm-l5-selezn.pdf|Лекция 5]]'''. Группы. Изоморфизм групп. Симметрическая группа перестановок. Подгруппы. Теорема Кэли.
  
[[Media:dm_lection3.pdf|Лекция 3]]: Частично упорядоченные множества (ЧУМ). Диаграмма ЧУМ. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Единичный n-мерный куб, его длина и ширина.  
+
'''[[Media:ivdm-l6-selezn.pdf|Лекция 6]]'''. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы.
  
[[Media:dm_lection4.pdf|Лекция 4]]: Теорема Анселя о разбиении n-мерного куба на цепи. Оценки числа монотонных функций алгебры логики. Расшифровка монотонных функций алгебры логики.
+
'''[[Media:ivdm-l7-selezn.pdf|Лекция 7]]'''. Действие группы на множестве. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.
  
[[Media:dm_lection5.pdf|Лекция 5]]: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества n-мерного куба и длины полиномиальных нормальных форм функций алгебры логики.
+
'''[[Media:ivdm-l8-selezn.pdf|Лекция 8]]'''. Раскраски. Эквивалентность раскрасок относительно группы. Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа.
  
[[Media:dm_lection6.pdf|Лекция 6]]: Коллоквиум 1.
+
Коллоквиум по теме "Теория Пойа".
  
[[Media:dm_lection7.pdf|Лекция 7]]: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.
+
'''Часть 3. Конечные поля'''.
  
[[Media:dm_lection8.pdf|Лекция 8]]: Линейные однородные и неоднородные рекуррентные уравнения.
+
'''[[Media:ivdm-l9-selezn.pdf|Лекция 9]]'''. Кольца. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Наследование свойств кольца в кольце многочленов. Деление с остатком многочленов над полем.
  
[[Media:dm_lection9.pdf|Лекция 9]]: Группы. Изоморфизм групп. Симметрическая группа перестановок. Теорема Кэли.
+
'''[[Media:ivdm-l10-selezn.pdf|Лекция 10]]'''. Идеалы, главные идеалы колец. Кольцо главных идеалов. Теорема о главном идеале кольца главных идеалов. Кольцо многочленов как кольцо главных идеалов. Построение конечных полей из p^n элементов, где p - простое число, n \ge 2.
  
[[Media:dm_lection10.pdf|Лекция 10]]: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.
+
'''[[Media:ivdm-l11-selezn.pdf|Лекция 11]]'''. Критерий неприводимости многочленов степени 2 или 3. Расширения полей. Вычисления в полях, алгоритм Евклида. Теорема о мультипликативной группе конечного поля.
  
[[Media:dm_lection11.pdf|Лекция 11]]: Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай). Примеры.
+
'''[[Media:ivdm-l12-selezn.pdf|Лекция 12]]'''.
  
[[Media:dm_lection12.pdf|Лекция 12]]: Коллоквиум 2.
+
Коллоквиум по теме "Конечные поля".
  
[[Media:dm_lection15.pdf|Лекция 13]]: Функции k-значной логики и способы их представления. Полные системы. Полнота системы Поста.
+
'''Литература'''
 +
 +
# Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
 +
# Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
 +
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 +
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
  
[[Media:dm_lection13.pdf|Лекция 14]]: Кольца. Теорема о конечном целостном кольце. Кольцо многочленов.
+
==Семинары==
  
[[Media:dm_lection14.pdf|Лекция 15]]: Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.
+
'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.
  
[[Media:dm_lection16.pdf|Лекция 16]]: Коллоквиум 3.
+
[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).
'''(осенний  семестр 2015/2016 учебного года, группа 318, лектор — доцент С.Н. Селезнева)'''
+
  
* Выборки. Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
+
'''Занятие 2'''. Функции, сохраняющие множество, и функции, сохраняющие разбиение. Полнота.  
* Теоремы о свойствах последовательности биномиальных коэффициентов. Полиномиальные коэффициенты. Теорема о верхней оценке биномиального коэффициента и ее следствие. Теорема об асимптотике некоторой суммы биномиальных коэффициентов.
+
* Частично упорядоченные множества (ЧУМ). Диаграмма ЧУМ. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. n-мерный куб. Теоремы о длине и ширине n-мерного куба. Изоморфизм ЧУМ.
+
* Теорема Анселя о разбиениии n-мерного куба на цепи. Теорема о числе монотонных функций алгебры логики. Теорема о расшифровке монотонных функций алгебры логики.
+
* Покрытие множества и покрытие матрицы. Градиентное покрытие. Лемма о градиентном покрытии. Теорема об оценках мощности затеняющего множества n-мерного куба. Оценки длины полиномиальных нормальных форм функций алгебры логики.
+
* Функция Мёбиуса на ЧУМ. Функция Мёбиуса на n-мерном кубе. Формула обращения Мёбиуса. Формула включений-исключений. Задача о подсчете числа перестановок-беспорядков.
+
* Последовательности. Однородные линейные рекуррентные уравнения (ЛОРУ). Частные и общие решения ЛОРУ. Теорема о линейной комбинации частных решений ЛОРУ. Характеристический многочлен ЛОРУ. Теоремы о частном решении ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ). Теоремы об общем решении ЛНРУ.
+
* Группы, виды групп. Изоморфизм групп. Симметрическая группа перестановок и ее свойства. Подгруппы. Теорема Кэли. Представления Кэли.
+
* Подгруппы, смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы, фактор-группа. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.
+
* Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай, только формулировка).
+
* Функции конечнозначных логик. Элементарные функции k-значной логики. Способы задания функций k-значных логик: таблицы, формулы. Теоремы о представимости функций k-значных логик в I-й и II-й формах. Теорема о представимости функций k-значных логик полиномами. Операция замыкания. Замкнутый класс и полная система. Теорема о полноте системы Поста и ее следствия.
+
* Кольца, виды колец. Теорема о конечном целостном кольце. Кольцо многочленов. Теорема о наследовании свойств кольца в кольце многочленов над этим кольцом. Подкольцо. Идеал кольца. Главный идеал кольца. Кольцо главных идеалов. Деление с остатком многочленов над полем. Теорема о кольце многочленов над полем как кольце главных идеалов. Вычеты по модулю идеала. Фактор-кольцо.
+
* Неприводимые и приводимые многочлены над полем. Корень многочлена. Критерий неприводимости над полем многочленов степени два и три. Теорема о фактор-кольце кольца многочленов над полем по модулю главного идеала. Поле остатков неприводимого многочлена над конечным полем, операции сложения и умножения в нем. Вычисление обратного элемента по алгоритму Евклида. Понятие расширения поля. Мультипликативная группа конечного поля и ее свойства (только формулировка теоремы).
+
+
'''Литература'''
+
+
* Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
+
* Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
+
* Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М.: Мир, 1968, с. 53-57.
+
* Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М.: Мир, 1966, с. 61-107.
+
 
+
==Задачи==
+
 
+
* Подсчитать число объектов с заданными свойствами.
+
* Найти значение суммы комбинаторных чисел или доказать комбинаторное тождество.
+
* Применить формулу включений-исключений для нахождения искомого значения.
+
* Найти длину или ширину заданного конечного ЧУМ или построить ЧУМ с заданными свойствами.
+
* Найти градиентное покрытие заданной матрицы и оценить его мощность.
+
* Решить данное ЛОРУ или ЛНРУ.
+
* Найти цикловой индекс группы перестановок.
+
* Найти число орбит раскрасок (возможно, с ограничениями) относительно данной группы перестановок.
+
* Определить приводимость или неприводимость многочлена над полем.
+
* Выяснить, является ли заданное фактор-кольцо кольца многочленов по модулю главного идеала полем.
+
* Построить таблицы сложения и умножения элементов поля остатков неприводимого многочлена над конечным полем.
+
* По алгоритму Евклида найти обратный элемент в поле остатков неприводимого многочлена над конечным полем.
+
* Записать данную функцию k-значной логики в I-й, II-й формах или полиномом.
+
* Выяснить, представима ли заданная функция k-значной логики (при составном 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
  
 +
На дом: [4] Гл. III
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Версия 12:29, 10 сентября 2017

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

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

Объявления

Лекции

Часть 1. Конечнозначные функции.

Лекция 1. Конечнозначные функции. Элементарные k-значные функции. Способы представления k-значных функций: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.

Лекция 2. Алгоритм распознавания полноты в P_k. Замкнутые классы. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. Предполные классы.

Лекция 3. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.

Лекция 4. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Классы функций, сохраняющих предикат, их замкнутость. Соответствие Галуа.

Коллоквиум по теме "Конечнозначные функции".

Часть 2. Теория Пойа.

Лекция 5. Группы. Изоморфизм групп. Симметрическая группа перестановок. Подгруппы. Теорема Кэли.

Лекция 6. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы.

Лекция 7. Действие группы на множестве. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.

Лекция 8. Раскраски. Эквивалентность раскрасок относительно группы. Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа.

Коллоквиум по теме "Теория Пойа".

Часть 3. Конечные поля.

Лекция 9. Кольца. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Наследование свойств кольца в кольце многочленов. Деление с остатком многочленов над полем.

Лекция 10. Идеалы, главные идеалы колец. Кольцо главных идеалов. Теорема о главном идеале кольца главных идеалов. Кольцо многочленов как кольцо главных идеалов. Построение конечных полей из p^n элементов, где p - простое число, n \ge 2.

Лекция 11. Критерий неприводимости многочленов степени 2 или 3. Расширения полей. Вычисления в полях, алгоритм Евклида. Теорема о мультипликативной группе конечного поля.

Лекция 12.

Коллоквиум по теме "Конечные поля".

Литература

  1. Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
  2. Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
  3. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
  4. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.

Семинары

Занятие 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. Функции, сохраняющие множество, и функции, сохраняющие разбиение. Полнота.

[4] Гл. III

На дом: [4] Гл. III