|
|
| (не показаны 184 промежуточных версий 1 участника) |
| Строка 1: |
Строка 1: |
| − | ==О курсе==
| + | Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]] |
| − | Курс "Избранные вопросы дискретной математики" читается в 5-м семестре. Форма отчетности - экзамен. Экзамен проходит письменно. За экзаменационную работу студент получает определенное количество баллов. | + | |
| | | | |
| − | В течение семестра по курсу проходят три письменных коллоквиума. За каждый коллоквиум студент получает дополнительные или штрафные баллы.
| + | Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен. |
| | | | |
| − | Оценка на экзамене по курсу выставляется по следующему правилу: количество баллов, полученное студентом за экзаменационную работу, увеличивается на дополнительные баллы за коллоквиумы или уменьшается на штрафные баллы за коллоквиумы; по вычисленному значению выводится оценка по критериям экзамена (критерии станут известны позднее).
| + | ==Объявления== |
| | | | |
| − | Первый коллоквиум состоится на 6-й лекции 10 октября. Темы коллоквиума: прочитанные пять лекций. При написании коллоквиума не разрешается пользоваться никакими материалами.
| + | ==Программа курса== |
| | | | |
| − | Второй коллоквиум состоится на 12-й лекции 21 ноября. Темы коллоквиума: прочитанные шестая-одиннадцатая лекции. При написании коллоквиума не разрешается пользоваться никакими материалами.
| + | '''Тема 1. Основы теории множеств.''' Множества, операции над множествами. Мощность множества, конечные множества. Отношения, виды отношений. [1] Гл. 1, разделы 1.1, 1.3; Гл. 3, разделы 3.1, 3.3, 3.5. |
| | | | |
| − | Третий коллоквиум состоится на 16-й лекции 19 декабря. Темы коллоквиума: прочитанные тринадцатая-пятнадцатая лекции. При написании коллоквиума не разрешается пользоваться никакими материалами.
| + | Упражнения. [1] Гл. 1, разделы 1.2, 1.4; Гл. 3, разделы 3.2, 3.4, 3.6. |
| | | | |
| − | Курс читает [[Селезнева Светлана Николаевна|Селезнева С.Н.]]
| + | '''Тема 2. Функции k-значной логики. Формулы.''' Функции k-значной логики. Таблицы значений, векторы значений. Формулы, эквивалентные формулы, тождества. Эквивалентные преобразования формул, доказательства тождеств. [2] Гл. 1, раздел 1; [3] Гл. 3, стр. 88--89. Упражнения. [3] Гл. 3, N 1.1, 1.2, 1.6, 1.7, 1.8. |
| | | | |
| − | ==Лекции==
| + | '''Тема 3. Функции k-значной логики. Нормальные формы.''' Представление функций k-значной логики 1-й и 2-й формами. Полные системы. Система Поста. Полнота системы Поста. [2] Гл. 1, раздел 2(до стр. 15); [3] Гл. 3, раздел 1, стр. 91--92. Упражнения. [3] Гл. 3, N 1.11, 1.12. |
| − | [[Media:dm_lection1.pdf|Лекция 1]]: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.
| + | |
| | | | |
| − | [[Media:dm_lection2.pdf|Лекция 2]]: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм. | + | '''Тема 4. Функции k-значной логики. Полиномы.''' Полиномы по модулю k. Представление функций k-значной логики полиномами по модулю k. Вычисление коэффициентов полиномов функций k-значной логики. [2] Гл. 1, раздел 2(стр. 15--16); [3] Гл. 3, раздел 2, стр. 93--95. Упражнения. [3] Гл. 3, N 2.7, 2.8, 2.11, 2.12, 2.23. |
| | | | |
| − | [[Media:dm_lection3.pdf|Лекция 3]]: Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб, его длина и ширина. Булеан.
| + | '''Коллоквиум 1''' по темам 2--4. |
| | | | |
| − | [[Media:dm_lection4.pdf|Лекция 4]]: Теорема Анселя о разбиении булева куба на цепи. Оценки числа монотонных булевых функций. Расшифровка монотонных булевых функций.
| + | ==Литература== |
| | | | |
| − | [[Media:dm_lection5.pdf|Лекция 5]]: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества булева куба и длины полиномиальных нормальных форм булевых функций. | + | #Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010. |
| | + | #[[Media:ИзбрГлавыДискрМатем_2015.pdf|Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015.]] |
| | + | #Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. |
| | + | #[[Media:fsbook_marchenkovss.pdf|Марченков С.С. Функциональные системы. М.: МАКС Пресс, 2012.]] |
| | | | |
| − | [[Media:dm_lection6.pdf|Лекция 6]]: Коллоквиум 1.
| + | <!---'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k. |
| | | | |
| − | [[Media:dm_lection7.pdf|Лекция 7]]: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений. | + | [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). |
| | | | |
| − | [[Media:dm_lection8.pdf|Лекция 8]]: Линейные однородные и неоднородные рекуррентные уравнения.
| + | На дом: [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). |
| | | | |
| − | [[Media:dm_lection9.pdf|Лекция 9]]: Группы. Изоморфизм групп. Симметрическая группа перестановок. Теорема Кэли.
| + | '''Занятие 2'''. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам. |
| | | | |
| − | [[Media:dm_lection10.pdf|Лекция 10]]: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда. | + | [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). |
| | | | |
| − | [[Media:dm_lection11.pdf|Лекция 11]]: Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай). Примеры. | + | На дом: [4] Гл. III 2.13(7, 8, 9, 10), 2.16(2, 4), 2.19(5, 9, 10, 11, 12), 2.14, 2.15. |
| | | | |
| − | [[Media:dm_lection12.pdf|Лекция 12]]: Коллоквиум 2.
| + | '''Занятие 3'''. Проверка полноты систем функций. Критерий полноты. Система полиномов. Базисы. |
| | | | |
| − | [[Media:dm_lection13.pdf|Лекция 13]]: Кольца. Теорема о конечном целостном кольце. Кольцо многочленов. | + | [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). |
| | | | |
| − | [[Media:dm_lection14.pdf|Лекция 14]]: Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.
| + | На дом: [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'''. Группы, подгруппы, теорема Кэли. Цикловой индекс группы перестановок. |
| | | | |
| − | [[Media:dm_lection15.pdf|Лекция 15]]: Функции k-значной логики и способы их представления. Полные системы. Полнота системы Поста. | + | [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). |
| | | | |
| − | [[Media:dm_lection16.pdf|Лекция 16]]: Коллоквиум 3.
| + | На дом: [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'''. Раскраски. Теорема Пойа (частный случай). |
| − | '''(осенний семестр 2013/2014 учебного года, группа 318, лектор — доцент С.Н. Селезнева)''' | + | |
| | | | |
| − | * Выборки. Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
| + | [5] 2.8(2, 3, 6), 2.12(1, 2 (1-2)), 2.13(1, 2). |
| − | * Теоремы о свойствах последовательности биномиальных коэффициентов. Полиномиальные коэффициенты. Теорема о верхней оценке биномиального коэффициента и ее следствие. Теорема об асимптотике некоторой суммы биномиальных коэффициентов.
| + | |
| − | * Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб. Теоремы о длине и ширине булева куба. Изоморфизм ЧУМ, булеан.
| + | |
| − | * Теорема Анселя о разбиениии булева куба на цепи. Теорема о числе монотонных булевых функций. Теорема о расшифровке монотонных булевых функций.
| + | |
| − | * Покрытие множества и покрытие матрицы. Градиентное покрытие. Лемма о градиентном покрытии. Теорема об оценках мощности затеняющего множества булева куба. Оценки длины полиномиальных нормальных форм булевых функций.
| + | |
| − | * Функция Мёбиуса на ЧУМ. Функция Мёбиуса на булевом кубе и булеане. Формула обращения Мёбиуса. Формула включений-исключений. Задача о подсчете числа перестановок-беспорядков.
| + | |
| − | * Последовательности. Однородные линейные рекуррентные уравнения (ЛОРУ). Частные и общие решения ЛОРУ. Теорема о линейной комбинации частных решений ЛОРУ. Характеристический многочлен ЛОРУ. Теоремы о частном решении ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ). Теоремы об общем решении ЛНРУ.
| + | |
| − | * Группы, виды групп. Изоморфизм групп. Симметрическая группа перестановок и ее свойства. Подгруппы. Теорема Кэли. Представления Кэли.
| + | |
| − | * Подгруппы, смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы, фактор-группа. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.
| + | |
| − | * Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай, только формулировка).
| + | |
| − | * Кольца, виды колец. Теорема о конечном целостном кольце. Кольцо многочленов. Теорема о наследовании свойств кольца в кольце многочленов над этим кольцом. Подкольцо. Идеал кольца. Главный идеал кольца. Кольцо главных идеалов. Деление с остатком многочленов над полем. Теорема о кольце многочленов над полем как кольце главных идеалов. Вычеты по модулю идеала. Фактор-кольцо.
| + | |
| − | * Неприводимые и приводимые многочлены над полем. Корень многочлена. Критерий неприводимости над полем многочленов степени два и три. Теорема о фактор-кольце кольца многочленов над полем по модулю главного идеала. Поле остатков неприводимого многочлена над конечным полем, операции сложения и умножения в нем. Вычисление обратного элемента по алгоритму Евклида. Понятие расширения поля. Мультипликативная группа конечного поля и ее свойства (только формулировка теоремы).
| + | |
| − | * Функции конечнозначных логик. Элементарные функции k-значной логики. Способы задания функций k-значных логик: таблицы, формулы. Теоремы о представимости функций k-значных логик в I-й и II-й формах. Теорема о представимости функций k-значных логик полиномами. Операция замыкания. Замкнутый класс и полная система. Теорема о полноте системы Поста и ее следствия.
| + | |
| − |
| + | |
| − | '''Литература'''
| + | |
| − |
| + | |
| − | * Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
| + | |
| − | * Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
| + | |
| − | * Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М.: Мир, 1968, с. 53-57.
| + | |
| − | * Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М.: Мир, 1966, с. 61-107.
| + | |
| | | | |
| − | ==Задачи==
| + | На дом: [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'''. Раскраски. Теорема Пойа (общий случай). |
| − | * Найти значение суммы комбинаторных чисел или доказать комбинаторное тождество.
| + | |
| − | * Применить формулу включений-исключений для нахождения искомого значения.
| + | |
| − | * Найти длину или ширину заданного конечного ЧУМ или построить ЧУМ с заданными свойствами.
| + | |
| − | * Найти градиентное покрытие заданной матрицы и оценить его мощность.
| + | |
| − | * Решить данное ЛОРУ или ЛНРУ.
| + | |
| − | * Найти цикловой индекс группы перестановок.
| + | |
| − | * Найти число орбит раскрасок (возможно, с ограничениями) относительно данной группы перестановок.
| + | |
| − | * Определить приводимость или неприводимость многочлена над полем.
| + | |
| − | * Выяснить, является ли заданное фактор-кольцо кольца многочленов по модулю главного идеала полем.
| + | |
| − | * Построить таблицы сложения и умножения элементов поля остатков неприводимого многочлена над конечным полем.
| + | |
| − | * По алгоритму Евклида найти обратный элемент в поле остатков неприводимого многочлена над конечным полем.
| + | |
| − | * Записать данную функцию k-значной логики в I-й, II-й формах или полиномом.
| + | |
| − | * Выяснить, представима ли заданная функция k-значной логики (при составном k) полиномом.
| + | |
| | | | |
| − | '''Литература'''
| + | [5] 2.9(1-4), 2.10(2, 4), 2.11(1, 2), 2.16(1, 3), 2.17(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.
| + | |
| − | * Лидл Р. Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988.
| + | |
| | | | |
| | + | На дом: [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).---> |
| | + | |
| | + | ==О проведении экзамена== |
| | | | |
| | | | |
| | [[Категория:Лекционные курсы кафедры МК]] | | [[Категория:Лекционные курсы кафедры МК]] |
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.
Упражнения. [1] Гл. 1, разделы 1.2, 1.4; Гл. 3, разделы 3.2, 3.4, 3.6.
