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