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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Программа курса)
(→‎Лекции)
 
(не показаны 186 промежуточные версии 1 участника)
Строка 1: Строка 1:
−
==Программа курса==
+
Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
−
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре. Форма отчетности - экзамен. Экзамен проходит письменно. За экзаменационную работу студент получает определенное количество баллов.
+
  
−
В течение семестра по курсу проходят два письменных коллоквиума. За каждый коллоквиум студент получает дополнительные или штрафные баллы.
+
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.
  
−
Оценка на экзамене по курсу выставляется по следующему правилу: количество баллов, полученное студентом за экзаменационную работу, увеличивается на дополнительные баллы за коллоквиумы или уменьшается на штрафные баллы за коллоквиумы; по вычисленному значению выводится оценка по критериям экзамена (критерии станут известны позднее).
+
==Объявления==
  
−
Первый коллоквиум состоится на 6-й лекции 10 октября. Темы коллоквиума: прочитанные пять лекций. При написании коллоквиума не разрешается пользоваться никакими материалами.
+
==Лекции==
  
−
Второй коллоквиум состоится на 12-й лекции 21 ноября. Темы коллоквиума: прочитанные шестая-одиннадцатая лекции. При написании коллоквиума не разрешается пользоваться никакими материалами.
+
'''Часть 1. Функции k-значной логики'''.
  
−
Курс читает [[Селезнева Светлана Николаевна|Селезнева С.Н.]]
+
'''Лекция 1'''. Функции k-значной логики. Формулы. Тождества. Представимость функций k-значной логики в 1-й и 2-й формах.
  
−
==Архив лекций==
+
'''Лекция 2'''. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.
−
[[Media:dm_lection1.pdf|Лекция 1]]: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.
+
  
−
[[Media:dm_lection2.pdf|Лекция 2]]: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.
+
'''Лекция 3'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
  
−
[[Media:dm_lection3.pdf|Лекция 3]]: Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб, его длина и ширина. Булеан.
+
'''Лекция 4'''. Выразимость и полнота в P_k, их алгоритмическая разрешимость для конечных множеств. Алгоритм распознавания полноты в P_k.
  
−
[[Media:dm_lection4.pdf|Лекция 4]]: Теорема Анселя о разбиении булева куба на цепи. Оценки числа монотонных булевых функций. Расшифровка монотонных булевых функций.
+
'''Лекция 5'''. Замкнутые классы. Отношения. Сохранение функцией отношения. Замкнутость класса всех функций, сохраняющих заданное отношение. Классы функций, сохраняющих некоторые отношения.
  
−
[[Media:dm_lection5.pdf|Лекция 5]]: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества булева куба и длины полиномиальных нормальных форм булевых функций.
+
'''Лекция 6'''. Предполные классы. Описание предполных классов. Теорема Кузнецова о предполных классах в P_k.
  
−
[[Media:dm_lection6.pdf|Лекция 6]]: Коллоквиум 1.
+
'''Лекция 7'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теорема Янова. Теорема Мучника. Мощность множества замкнутых классов в P_k.  
  
−
[[Media:dm_lection7.pdf|Лекция 7]]: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.
+
Коллоквиум по теме "Функции k-значной логики".
  
−
[[Media:dm_lection8.pdf|Лекция 8]]: Линейные однородные и неоднородные рекуррентные уравнения.
+
<!---'''Часть 2. Группы'''.
  
−
[[Media:dm_lection9.pdf|Лекция 9]]: Группы. Изоморфизм групп. Симметрическая группа перестановок. Теорема Кэли.
+
'''Лекция 8'''. Группы. Подгруппы. Смежные классы. Разложение группы по подгруппе. Нормальные подгруппы. Фактор-группы.
  
−
[[Media:dm_lection10.pdf|Лекция 10]]: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.
+
'''Лекция 9'''. Перестановки. Симметрическая группа перестановок. Теорема Кэли. Орбита и стабилизатор элемента. Лемма Бернсайда.
  
−
[[Media:dm_lection11.pdf|Лекция 11]]: Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай). Примеры.
+
'''Лекция 10'''. Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа. Примеры.
  
−
Лекция 12 (21.11): Коллоквиум 2.
+
Коллоквиум по теме "Группы".
  
−
Лекция 13 (28.11): Кольца. Кольцо многочленов.
+
'''Часть 3. Конечные поля'''.
  
−
Лекция 14 (5.12): Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.
+
'''Лекция 11'''. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.
  
−
Лекция 15 (12.12): Линейные коды.
+
'''Лекция 12'''. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля.
  
−
Лекция 16 (19.12): Функции k-значной логики и способы их представления.
+
'''Лекция 13'''. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.
  
−
==Вопросы к экзамену по курсу «Избранные вопросы дискретной математики»==
+
Коллоквиум по теме "Конечные поля".
−
'''(осенний  семестр 2009/2010 учебного года, группы 318, 319, лектор — доцент С.Н. Селезнева)'''
+
--->
  
−
'''Часть A. Вопросы, при ответе на которые, можно пользоваться конспектами (некоторое время, при этом ответ не состоит в чтении конспекта). Определения и теоремы должны быть сформулированы до того, как конспект будет открыт.'''
+
'''Литература'''
  
−
* Алгоритм  распознавания полноты конечных систем функций k-значной логики.
+
Основная:
−
* Теорема Кузнецова о функциональной полноте.
+
−
* Существенные функции. Леммы о существенных функциях: о трех наборах, основная и о квадрате.
+
−
* Критерий полноты  Яблонского систем функций k-значной логики.
+
−
* Операции над о.-д. функциями. Замкнутость класса о.-д. функций относительно операций суперпозиции и обратной связи.
+
−
* Леммы о преобразовании периодических последовательностей о.-д. функцией. Несводимость операции обратной связи к операции суперпозиции.
+
−
* Леммы о преобразовании машинных кодов: основного в l-кратный, решетчатого в основной и квазиосновного в основной.
+
−
* Операция суперпозиции. Теорема о замкнутости класса вычислимых функций относительно операции суперпозиции.
+
−
* Операция примитивной рекурсии. Теорема о замкнутости класса вычислимых функций относительно операции примитивной рекурсии.
+
−
* Операция минимизации. Теорема о замкнутости класса вычислимых функций относительно операции минимизации.
+
−
* Класс примитивно-рекурсивных функций. Примитивная рекурсивность функции Пеано и ее обобщений. Классы частично-рекурсивных и общерекурсивных функций.
+
−
* Теорема о схеме одновременной примитивной рекурсии.
+
−
* Формула Клини. Теорема о соотношении классов частично-рекурсивных и вычислимых функций.
+
−
* Кольцо многочленов над полем. Теорема о делении многочленов с остатком. Делимость многочленов. Теорема о наибольшем общем делителе двух многочленов.
+
−
* Неприводимость многочленов над полем. Теорема о неприводимом делителе произведения многочленов. Теорема о каноническом разложении многочлена на неприводимые сомножители.
+
−
* Теорема о фактор-кольце кольца целых чисел.
+
−
* Теорема о фактор-кольце кольца многочленов над простым полем.
+
−
* Теорема Анселя о разбиении куба <math>B_n</math> на цепи. Теорема об оценках числа монотонных булевых функций.
+
 
   
 
   
−
'''Часть B. Вопросы, при ответе на которые пользоваться конспектами не предполагается. Ответ почти без подготовки.'''
+
# Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
 +
# Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
 +
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 +
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
 +
<!---# [[Media:ivdm-sem.pdf|Задачи для семинарских занятий]] по теме "Группы. Теория Пойа".
 +
# [[Media:ivdm-sem3.pdf|Задачи для семинарских занятий]] по теме "Конечные поля".--->
 +
Дополнительная:
  
−
* Теоремы о  I-й и II-й формах записи функций k-значной логики.
+
# Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2016. Глава 1.
−
* Полные системы. Полнота системы Поста. Функция Вебба.
+
# Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. Глава 1.
−
* Шефферовы функции. Критерий шефферовости.
+
# Яблонский С.В., Гаврилов Г.П., Набебин А.А. Предполные классы в многозначных логиках. М.: МЭИ, 1997. Часть 1.
−
* Теоремы Янова и Мучника. Следствия из них.
+
# Lau D. Function Algebras on Finite Sets. Springer, 2006.
−
* Теорема о полноте системы полиномов в Pk.
+
# Горшков С.П., Тарасов А.В. Сложность решения систем булевых уравнений. М.: Курс, 2017.
−
* Детерминированные функции (д. функции). Мощность класса д. функций. Задание д. функций нагруженными деревьями.
+
−
* Ограниченно-детерминированные функции (о.-д. функции). Способы их задания. Мощность класса о.-д. функций.
+
−
* Полнота систем о.-д. функций. Существование аналога функции Шеффера.
+
−
* Машины Тьюринга (МТ). Машинные коды: основной, l-кратный, решетчатый, квазиосновной. Задача поиска левой единицы в основном коде.
+
−
* Лемма о моделировании на решетке.
+
−
* Класс примитивно-рекурсивных функций. Примитивная рекурсивность некоторых функций (знака, сложения, умножения, целой части от деления, и т.д.). Классы частично-рекурсивных и общерекурсивных функций.
+
−
* Алгебраическая операция, нейтральный элемент, симметричный элемент. Группа, абелева группа. Конечная группа, порядок группы, таблица Кэли. Симметрическая группа перестановок. Подгруппа. Теорема Кэли.
+
−
* Теорема Лагранжа о порядке подгруппы конечной группы.
+
−
* Эквивалентность элементов относительно группы перестановок. Орбита и стабилизатор элемента. Лемма о порядке стабилизатора элемента. Лемма Бернсайда о числе орбит.
+
−
* Раскраски, эквивалентность раскрасок относительно группы перестановок. Теорема Пойа о числе орбит раскрасок.
+
−
* Кольцо, целостное кольцо, поле. Кольцо многочленов над некоторым кольцом. Теорема о целостности кольца многочленов над полем.
+
−
* Значение многочлена в точке, корень многочлена. Критерий неприводимости многочленов степени, не выше 3.
+
−
* Теорема о конечном целостном кольце.
+
−
* Характеристика кольца. Теорема о характеристике конечного поля.
+
−
* Идеал кольца, главный идеал. Эквивалентность элементов кольца и класс вычетов по модулю идеала. Фактор-кольцо по модулю идеала.
+
−
* Частично-упорядоченные множества (ЧУМ). Минимальные и максимальные, наименьший и наибольший элементы. Длина и ширина конечного ЧУМ. Теорема Дилуорса о ширине конечного ЧУМ.
+
−
* Теоремы о длине и ширине куба <math>B_n</math>.
+
  
−
'''Литература'''
+
==Семинары==
−
+
−
* Яблонский С. В. Введение в дискретную математику. М., Наука, 2001.
+
−
* Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988.
+
−
* Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М., Мир, 1968, с. 53-57.
+
−
* Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М., Мир, 1966, с. 61-107.
+
−
+
−
==Типовые задачи==
+
  
−
* Записать  функцию k-значной логики в I-й или II-й форме, построить ее полином или доказать, что она не задается полиномом по mod k; исследовать систему функций k-значной логики на полноту.
+
<!---'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.
−
* Построить диаграмму Мура о.-д. функции; доказать полноту системы о.-д. функций.
+
−
* Применить операцию примитивной рекурсии или операцию минимизации; доказать примитивную рекурсивность функции.
+
−
* Построить группу перестановок и найти ее цикловой индекс; найти число неэквивалентных раскрасок относительно группы перестановок.
+
−
* Исследовать многочлен на неприводимость; найти сумму, произведение элементов или обратный элемент в конечном поле.
+
  
−
'''Литература'''
+
[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).
−
+
 
−
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 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.
+
На дом: [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).
−
* Лидл Р. Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988.
+
 
 +
'''Занятие 2'''. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам.
 +
 
 +
[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.
 +
 
 +
'''Занятие 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'''. Группы, подгруппы, теорема Кэли. Цикловой индекс группы перестановок.
 +
 
 +
[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).--->
  
 +
==О проведении экзамена==
  
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

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

Семинары

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

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