Избранные вопросы дискретной математики — различия между версиями
(→Архив лекций) |
(→Вопросы к экзамену по курсу «Избранные вопросы дискретной математики») |
||
| Строка 46: | Строка 46: | ||
==Вопросы к экзамену по курсу «Избранные вопросы дискретной математики»== | ==Вопросы к экзамену по курсу «Избранные вопросы дискретной математики»== | ||
| − | '''(осенний семестр | + | '''(осенний семестр 2013/2014 учебного года, группа 318, лектор — доцент С.Н. Селезнева)''' |
| − | ''' | + | ''' ''' |
| − | * | + | * |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | ''' | + | ''' ''' |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| + | * | ||
'''Литература''' | '''Литература''' | ||
| − | * Яблонский С. В. Введение в дискретную математику. М. | + | * Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001. |
* Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988. | * Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988. | ||
* Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М., Мир, 1968, с. 53-57. | * Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М., Мир, 1968, с. 53-57. | ||
* Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М., Мир, 1966, с. 61-107. | * Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М., Мир, 1966, с. 61-107. | ||
| − | + | ||
==Типовые задачи== | ==Типовые задачи== | ||
Версия 22:22, 23 ноября 2013
Содержание
Программа курса
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре. Форма отчетности - экзамен. Экзамен проходит письменно. За экзаменационную работу студент получает определенное количество баллов.
В течение семестра по курсу проходят два письменных коллоквиума. За каждый коллоквиум студент получает дополнительные или штрафные баллы.
Оценка на экзамене по курсу выставляется по следующему правилу: количество баллов, полученное студентом за экзаменационную работу, увеличивается на дополнительные баллы за коллоквиумы или уменьшается на штрафные баллы за коллоквиумы; по вычисленному значению выводится оценка по критериям экзамена (критерии станут известны позднее).
Первый коллоквиум состоится на 6-й лекции 10 октября. Темы коллоквиума: прочитанные пять лекций. При написании коллоквиума не разрешается пользоваться никакими материалами.
Второй коллоквиум состоится на 12-й лекции 21 ноября. Темы коллоквиума: прочитанные шестая-одиннадцатая лекции. При написании коллоквиума не разрешается пользоваться никакими материалами.
Курс читает Селезнева С.Н.
Лекции
Лекция 1: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.
Лекция 2: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.
Лекция 3: Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб, его длина и ширина. Булеан.
Лекция 4: Теорема Анселя о разбиении булева куба на цепи. Оценки числа монотонных булевых функций. Расшифровка монотонных булевых функций.
Лекция 5: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества булева куба и длины полиномиальных нормальных форм булевых функций.
Лекция 6: Коллоквиум 1.
Лекция 7: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.
Лекция 8: Линейные однородные и неоднородные рекуррентные уравнения.
Лекция 9: Группы. Изоморфизм групп. Симметрическая группа перестановок. Теорема Кэли.
Лекция 10: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.
Лекция 11: Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай). Примеры.
Лекция 12 (21.11): Коллоквиум 2.
Лекция 13 (28.11): Кольца. Кольцо многочленов.
Лекция 14 (5.12): Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.
Лекция 15 (12.12): Линейные коды.
Лекция 16 (19.12): Функции k-значной логики и способы их представления.
Вопросы к экзамену по курсу «Избранные вопросы дискретной математики»
(осенний семестр 2013/2014 учебного года, группа 318, лектор — доцент С.Н. Селезнева)
Литература
- Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
- Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988.
- Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М., Мир, 1968, с. 53-57.
- Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М., Мир, 1966, с. 61-107.
Типовые задачи
- Записать функцию k-значной логики в I-й или II-й форме, построить ее полином или доказать, что она не задается полиномом по mod 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.
