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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Лекции)
(Вопросы к экзамену)
Строка 50: Строка 50:
 
'''(осенний  семестр 2013/2014 учебного года, группа 318, лектор — доцент С.Н. Селезнева)'''
 
'''(осенний  семестр 2013/2014 учебного года, группа 318, лектор — доцент С.Н. Селезнева)'''
  
''' '''
+
* Выборки. Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
 
+
* Теоремы о свойствах последовательности биномиальных коэффициентов. Полиномиальные коэффициенты. Теорема о верхней оценке биномиального коэффициента и ее следствие. Теорема об асимптотике некоторой суммы биномиальных коэффициентов.
*  
+
* Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб. Теоремы о длине и ширине булева куба. Изоморфизм ЧУМ, булеан.
 +
* Теорема Анселя о разбиениии булева куба на цепи. Теорема о числе монотонных булевых функций. Теорема о расшифровке монотонных булевых функций.
 +
* Покрытие множества и покрытие матрицы. Градиентное покрытие. Лемма о градиентном покрытии. Теорема об оценках мощности затеняющего множества булева куба. Оценки длины полиномиальных нормальных форм булевых функций.
 +
* Функция Мёбиуса на ЧУМ. Функция Мёбиуса на булевом кубе и булеане. Формула обращения Мёбиуса. Формула включений-исключений. Задача о подсчете числа перестановок-беспорядков.
 +
* Последовательности. Однородные линейные рекуррентные уравнения (ЛОРУ). Частные и общие решения ЛОРУ. Характеристический многочлен ЛОРУ. Теорема о линейной комбинации частных решений ЛОРУ. Теоремы о частном решении ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ). Теоремы об общем решении ЛНРУ.
 +
* Группы, виды групп. Изоморфизм групп. Симметрическая группа перестановок и ее свойства. Подгруппы. Теорема Кэли. Представления Кэли.
 +
* Подгруппы, смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы, фактор-группа. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.
 +
* Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай, только формулировка).
 +
* Кольца, виды колец. Теорема о конечном целостном кольце. Кольцо многочленов. Теорема о наследовании свойств кольца в кольце многочленов над этим кольцом. Подкольцо. Идеал кольца. Главный идеал кольца. Кольцо главных идеалов. Деление с остатком многочленов над полем. Теорема о кольце многочленов над полем как кольце главных идеалов. Вычеты по модулю идеала. Фактор-кольцо.
 +
* Неприводимые и приводимые многочлены. Теорема о фактор-кольце кольца многочленов над полем по модулю главного идеала. Вычисления в конечных полях, алгоритм Евклида. Расширения полей. Мультипликативная группа конечного поля.
 +
* Функции конечнозначных логик. Элементарные функции $k$-значной логики. Способы задания функций $k$-значной логики. Теоремы о представимости функций k-значных логик в I-й и II-й формах. Теорема о представимости функций k-значных логик полиномами. Операция замыкания. Замкнутый класс и полная система. Теорема о полноте системы Поста и ее следствия.
 
   
 
   
''' '''
 
 
*
 
 
'''Литература'''
 
'''Литература'''
 
   
 
   
 
* Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
 
* Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
* Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988.
+
* Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
* Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М., Мир, 1968, с. 53-57.
+
* Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М.: Мир, 1968, с. 53-57.
* Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М., Мир, 1966, с. 61-107.
+
* Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М.: Мир, 1966, с. 61-107.
  
 
==Задачи==
 
==Задачи==

Версия 23:01, 7 января 2014

О курсе

Курс "Избранные вопросы дискретной математики" читается в 5-м семестре. Форма отчетности - экзамен. Экзамен проходит письменно. За экзаменационную работу студент получает определенное количество баллов.

В течение семестра по курсу проходят три письменных коллоквиума. За каждый коллоквиум студент получает дополнительные или штрафные баллы.

Оценка на экзамене по курсу выставляется по следующему правилу: количество баллов, полученное студентом за экзаменационную работу, увеличивается на дополнительные баллы за коллоквиумы или уменьшается на штрафные баллы за коллоквиумы; по вычисленному значению выводится оценка по критериям экзамена (критерии станут известны позднее).

Первый коллоквиум состоится на 6-й лекции 10 октября. Темы коллоквиума: прочитанные пять лекций. При написании коллоквиума не разрешается пользоваться никакими материалами.

Второй коллоквиум состоится на 12-й лекции 21 ноября. Темы коллоквиума: прочитанные шестая-одиннадцатая лекции. При написании коллоквиума не разрешается пользоваться никакими материалами.

Третий коллоквиум состоится на 16-й лекции 19 декабря. Темы коллоквиума: прочитанные тринадцатая-пятнадцатая лекции. При написании коллоквиума не разрешается пользоваться никакими материалами.

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

Лекции

Лекция 1: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.

Лекция 2: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.

Лекция 3: Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб, его длина и ширина. Булеан.

Лекция 4: Теорема Анселя о разбиении булева куба на цепи. Оценки числа монотонных булевых функций. Расшифровка монотонных булевых функций.

Лекция 5: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества булева куба и длины полиномиальных нормальных форм булевых функций.

Лекция 6: Коллоквиум 1.

Лекция 7: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.

Лекция 8: Линейные однородные и неоднородные рекуррентные уравнения.

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

Лекция 10: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.

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

Лекция 12: Коллоквиум 2.

Лекция 13: Кольца. Теорема о конечном целостном кольце. Кольцо многочленов.

Лекция 14: Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.

Лекция 15: Функции k-значной логики и способы их представления. Полные системы. Полнота системы Поста.

Лекция 16: Коллоквиум 3.

Вопросы к экзамену

(осенний семестр 2013/2014 учебного года, группа 318, лектор — доцент С.Н. Селезнева)

  • Выборки. Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
  • Теоремы о свойствах последовательности биномиальных коэффициентов. Полиномиальные коэффициенты. Теорема о верхней оценке биномиального коэффициента и ее следствие. Теорема об асимптотике некоторой суммы биномиальных коэффициентов.
  • Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб. Теоремы о длине и ширине булева куба. Изоморфизм ЧУМ, булеан.
  • Теорема Анселя о разбиениии булева куба на цепи. Теорема о числе монотонных булевых функций. Теорема о расшифровке монотонных булевых функций.
  • Покрытие множества и покрытие матрицы. Градиентное покрытие. Лемма о градиентном покрытии. Теорема об оценках мощности затеняющего множества булева куба. Оценки длины полиномиальных нормальных форм булевых функций.
  • Функция Мёбиуса на ЧУМ. Функция Мёбиуса на булевом кубе и булеане. Формула обращения Мёбиуса. Формула включений-исключений. Задача о подсчете числа перестановок-беспорядков.
  • Последовательности. Однородные линейные рекуррентные уравнения (ЛОРУ). Частные и общие решения ЛОРУ. Характеристический многочлен ЛОРУ. Теорема о линейной комбинации частных решений ЛОРУ. Теоремы о частном решении ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ). Теоремы об общем решении ЛНРУ.
  • Группы, виды групп. Изоморфизм групп. Симметрическая группа перестановок и ее свойства. Подгруппы. Теорема Кэли. Представления Кэли.
  • Подгруппы, смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы, фактор-группа. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.
  • Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай, только формулировка).
  • Кольца, виды колец. Теорема о конечном целостном кольце. Кольцо многочленов. Теорема о наследовании свойств кольца в кольце многочленов над этим кольцом. Подкольцо. Идеал кольца. Главный идеал кольца. Кольцо главных идеалов. Деление с остатком многочленов над полем. Теорема о кольце многочленов над полем как кольце главных идеалов. Вычеты по модулю идеала. Фактор-кольцо.
  • Неприводимые и приводимые многочлены. Теорема о фактор-кольце кольца многочленов над полем по модулю главного идеала. Вычисления в конечных полях, алгоритм Евклида. Расширения полей. Мультипликативная группа конечного поля.
  • Функции конечнозначных логик. Элементарные функции $k$-значной логики. Способы задания функций $k$-значной логики. Теоремы о представимости функций k-значных логик в I-й и II-й формах. Теорема о представимости функций k-значных логик полиномами. Операция замыкания. Замкнутый класс и полная система. Теорема о полноте системы Поста и ее следствия.

Литература

  • Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
  • Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
  • Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М.: Мир, 1968, с. 53-57.
  • Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М.: Мир, 1966, с. 61-107.

Задачи

Литература

  • Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 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.