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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Вопросы к экзамену)
(Объявления)
(не показана 41 промежуточная версия 1 участника)
Строка 1: Строка 1:
 
Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
 
Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
  
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций + 18 ч семинаров). Форма отчетности - экзамен.
+
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.
  
 
==Объявления==
 
==Объявления==
  
Результаты пересдачи по ИВДМ от 10.02.2017 г.: Дудко - неуд (8 баллов); Кинжикеева Д. - хорошо (26 баллов); Кузевич А. - неуд (6 баллов); Плакида Я. - неуд (5 баллов).  
+
27 ноября состоится коллоквиум по теме "Конечные группы и теория Пойа" на 1-й паре с 8-45 до 10-20 в ауд. 504. Лекция состоится на 3-й паре с 12-50 до 14-25 в ауд. 609.
  
Выставление оценок и апелляция состоятся 13 февраля (в понедельник) с 14-25 до 14-35 в к. 595.
+
[[Media:ivdm-kolok17.docx|Результаты коллоквиумов]]
  
 +
==Лекции==
  
[[Media: ivdm-318-2017.doc|Результаты экзамена по ИВДМ от 15.01.2017 г.]]
+
'''Часть 1. Конечнозначные функции'''.
  
Выставление оценок и апелляция состоятся 16 января (в понедельник) с 12-30 до 13-30 в к. 595.
+
'''[[Media:ivdm-l1-selezn.pdf|Лекция 1]]'''. Конечнозначные функции. Элементарные k-значные функции. Способы представления k-значных функций: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.
  
==Семинары==
+
'''[[Media:ivdm-l2-selezn.pdf|Лекция 2]]'''. Алгоритм распознавания полноты в P_k. Замкнутые классы. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. Предполные классы.
  
[[Media:ivdm-s.pdf|Задачи для семинарских занятий]]
+
'''[[Media:ivdm-l3-selezn.pdf|Лекция 3]]'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
  
==Лекции==
+
'''[[Media:ivdm-l4-selezn.pdf|Лекция 4]]'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Классы функций, сохраняющих предикат, их замкнутость. Соответствие Галуа.
[[Media:dm_lection1.pdf|Лекция 1]]: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.
+
  
[[Media:dm_lection2.pdf|Лекция 2]]: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.
+
Коллоквиум по теме "Конечнозначные функции".
  
[[Media:dm_lection3.pdf|Лекция 3]]: Частично упорядоченные множества (ЧУМ). Диаграмма ЧУМ. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Единичный n-мерный куб, его длина и ширина.  
+
'''Часть 2. Теория Пойа'''.
  
[[Media:dm_lection4.pdf|Лекция 4]]: Теорема Анселя о разбиении n-мерного куба на цепи. Оценки числа монотонных функций алгебры логики. Расшифровка монотонных функций алгебры логики.
+
'''[[Media:ivdm-l5-selezn.pdf|Лекция 5]]'''. Группы. Изоморфизм групп. Симметрическая группа перестановок. Подгруппы. Теорема Кэли.
  
[[Media:dm_lection5.pdf|Лекция 5]]: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества n-мерного куба и длины полиномиальных нормальных форм функций алгебры логики.
+
'''[[Media:ivdm-l6-selezn.pdf|Лекция 6]]'''. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы.
  
[[Media:dm_lection6.pdf|Лекция 6]]: Коллоквиум 1.
+
'''[[Media:ivdm-l7-selezn.pdf|Лекция 7]]'''. Действие группы на множестве. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.
  
[[Media:dm_lection7.pdf|Лекция 7]]: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.
+
'''[[Media:ivdm-l8-selezn.pdf|Лекция 8]]'''. Раскраски. Эквивалентность раскрасок относительно группы. Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа.
  
[[Media:dm_lection8.pdf|Лекция 8]]: Линейные однородные и неоднородные рекуррентные уравнения.
+
Коллоквиум по теме "Теория Пойа".
  
[[Media:dm_lection9.pdf|Лекция 9]]: Группы. Изоморфизм групп. Симметрическая группа перестановок. Теорема Кэли.
+
'''Часть 3. Конечные поля'''.
  
[[Media:dm_lection10.pdf|Лекция 10]]: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.
+
'''[[Media:ivdm-l9-selezn.pdf|Лекция 9]]'''. Кольца. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Наследование свойств кольца в кольце многочленов. Деление с остатком многочленов над полем.
  
[[Media:dm_lection11.pdf|Лекция 11]]: Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай). Примеры.
+
'''[[Media:ivdm-l10-selezn.pdf|Лекция 10]]'''. Идеалы, главные идеалы колец. Кольцо главных идеалов. Теорема о главном идеале кольца главных идеалов. Кольцо многочленов как кольцо главных идеалов. Построение конечных полей из p^n элементов, где p - простое число, n \ge 2.
  
[[Media:dm_lection12.pdf|Лекция 12]]: Коллоквиум 2.
+
'''[[Media:ivdm-l11-selezn.pdf|Лекция 11]]'''. Критерий неприводимости многочленов степени 2 или 3. Расширения полей. Вычисления в полях, алгоритм Евклида. Теорема о мультипликативной группе конечного поля.
  
[[Media:dm_lection15.pdf|Лекция 13]]: Функции k-значной логики и способы их представления. Полные системы. Полнота системы Поста.
+
'''[[Media:ivdm-l12-selezn.pdf|Лекция 12]]'''.
  
[[Media:dm_lection13.pdf|Лекция 14]]: Кольца. Теорема о конечном целостном кольце. Кольцо многочленов.
+
Коллоквиум по теме "Конечные поля".
  
[[Media:dm_lection14.pdf|Лекция 15]]: Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.
+
'''Литература'''
 +
 +
# Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
 +
# Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
 +
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 +
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
 +
# [[Media:ivdm-sem.pdf|Задачи для семинарских занятий]] по теме "Группы. Теория Пойа".
 +
# [[Media:ivdm-sem3.pdf|Задачи для семинарских занятий]] по теме "Конечные поля".
  
[[Media:dm_lection16.pdf|Лекция 16]]: Коллоквиум 3.
+
==Семинары==
  
==Вопросы к экзамену==
+
'''Занятие 1'''. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.
'''(осенний  семестр 2016/2017 учебного года, группа 318, лектор — доцент С.Н. Селезнева)'''
+
  
* Выборки. Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
+
[4] Гл. III 1.1(3, 6, 10, 12), 1.5, 1.11(2, 4, 8, 11), 2.7(1, 3, 6, 9), 2.12(1, 2), 2.8(1, 3).
* Теоремы о свойствах последовательности биномиальных коэффициентов. Полиномиальные коэффициенты. Теорема о верхней оценке биномиального коэффициента и ее следствие. Теорема об асимптотике некоторой суммы биномиальных коэффициентов.
+
* Частично упорядоченные множества (ЧУМ). Диаграмма ЧУМ. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. n-мерный куб. Теоремы о длине и ширине n-мерного куба. Изоморфизм ЧУМ.
+
* Теорема Анселя о разбиениии n-мерного куба на цепи. Теорема о числе монотонных функций алгебры логики. Теорема о расшифровке монотонных функций алгебры логики.
+
* Покрытие множества и покрытие матрицы. Градиентное покрытие. Лемма о градиентном покрытии. Теорема об оценках мощности затеняющего множества n-мерного куба. Оценки длины полиномиальных нормальных форм функций алгебры логики.
+
* Функция Мёбиуса на ЧУМ. Функция Мёбиуса на n-мерном кубе. Формула обращения Мёбиуса. Формула включений-исключений. Задача о подсчете числа перестановок-беспорядков.
+
* Последовательности. Однородные линейные рекуррентные уравнения (ЛОРУ). Частные и общие решения ЛОРУ. Теорема о линейной комбинации частных решений ЛОРУ. Характеристический многочлен ЛОРУ. Теоремы о частном решении ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ). Теоремы об общем решении ЛНРУ.
+
* Группы, виды групп. Изоморфизм групп. Симметрическая группа перестановок и ее свойства. Подгруппы. Теорема Кэли. Представления Кэли.
+
* Подгруппы, смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы, фактор-группа. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.
+
* Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа (общий случай, только формулировка).
+
* Функции конечнозначных логик. Элементарные функции k-значной логики. Способы задания функций k-значных логик: таблицы, формулы. Теоремы о представимости функций k-значных логик в I-й и II-й формах. Теорема о представимости функций k-значных логик полиномами. Операция замыкания. Замкнутый класс и полная система. Теорема о полноте системы Поста и ее следствия.
+
* Кольца, виды колец. Теорема о конечном целостном кольце. Кольцо многочленов. Теорема о наследовании свойств кольца в кольце многочленов над этим кольцом. Подкольцо. Идеал кольца. Главный идеал кольца. Кольцо главных идеалов. Деление с остатком многочленов над полем. Теорема о кольце многочленов над полем как кольце главных идеалов. Вычеты по модулю идеала. Фактор-кольцо.
+
* Неприводимые и приводимые многочлены над полем. Корень многочлена. Критерий неприводимости над полем многочленов степени два и три. Теорема о фактор-кольце кольца многочленов над полем по модулю главного идеала. Поле остатков неприводимого многочлена над конечным полем, операции сложения и умножения в нем. Вычисление обратного элемента по алгоритму Евклида. Понятие расширения поля. Мультипликативная группа конечного поля и ее свойства (только формулировка теоремы).
+
+
'''Литература'''
+
+
* Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
+
* Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
+
* Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М.: Мир, 1968, с. 53-57.
+
* Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М.: Мир, 1966, с. 61-107.
+
  
'''Задачи'''
+
На дом: [4] Гл. III 1.1(4, 7, 11, 13), 1.6, 1.11(5, 10), 1.12, 2.7(2, 8, 10), 2.12(3, 5), 2.8(2), 2.9, 2.11(1, 2).
  
* Подсчитать число объектов с заданными свойствами.
+
'''Занятие 2'''. Функции, сохраняющие множество и сохраняющие разбиение. Сведение к заведомо полным системам.  
* Найти значение суммы комбинаторных чисел или доказать комбинаторное тождество.
+
* Применить формулу включений-исключений для нахождения искомого значения.
+
* Найти длину или ширину заданного конечного ЧУМ или построить ЧУМ с заданными свойствами.
+
* Найти градиентное покрытие заданной матрицы и оценить его мощность.
+
* Решить данное ЛОРУ или ЛНРУ.
+
* Найти цикловой индекс группы перестановок.
+
* Найти число орбит раскрасок (возможно, с ограничениями) относительно данной группы перестановок.
+
* Определить приводимость или неприводимость многочлена над полем.
+
* Выяснить, является ли заданное фактор-кольцо кольца многочленов по модулю главного идеала полем.
+
* Построить таблицы сложения и умножения элементов поля остатков неприводимого многочлена над конечным полем.  
+
* По алгоритму Евклида найти обратный элемент в поле остатков неприводимого многочлена над конечным полем.
+
* Записать данную функцию k-значной логики в I-й, II-й формах или полиномом.
+
* Выяснить, представима ли заданная функция k-значной логики (при составном k) полиномом.
+
  
'''Литература'''
+
[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).
+
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 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.
+
  
==О проведении экзамена==
+
На дом: [4] Гл. III 2.13(7, 8, 9, 10), 2.16(2, 4), 2.19(5, 9, 10, 11, 12), 2.14, 2.15.
Экзамен проходит письменно. При написании экзаменационной работы не разрешается пользоваться никакими материалами. За экзаменационную работу студент получает определенное количество баллов.
+
  
В течение семестра по курсу проходят три письменных коллоквиума. При написании коллоквиума не разрешается пользоваться никакими материалами. За каждый коллоквиум студент получает определенные баллы (н/я или 0 - (-3) балла, 1-4 - (-2) балла, 5-9 - (-1) балл, 10-14 - 0 баллов, 15-19 - (+1) балл, 20-24 - (+2) балла, 25 - (+3) балла).
+
'''Занятие 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).
  
Экзаменационная работа состоит из 14 заданий. Задания 1-5 - стандартные задачи (перечень типов предлагаемых задач ниже). Проверяется, насколько студент усвоил методы решения задач по курсу. Каждая задача оценивается в 3 балла. Задания 6-10 - определения и формулировки теорем с дополнительным вопросом. Дополнительный вопрос проясняет, насколько студент понимает определение или формулировку теоремы, может ли привести их частный случай или пояснить на примере. Каждое из заданий 6-10 оценивается в 3 балла. Задания 11-13 - доказательства теорем курса или их частей и частных случаев. Проверяется, как студент усвоил доказательства основных утверждений курса. Каждое из заданий 11-13 оценивается в 3 балла. Задание 14 - нестандартная задача. Проверяется, насколько студент может применять полученные в курсе знания при решении новых задач. Задание 14 оценивается в 4 балла. Продолжительность написания экзаменационной работы - 2 астрономических часа (120 минут).
+
На дом: [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'''. Группы, подгруппы, теорема Кэли. Цикловой индекс группы перестановок.
* 36-43 баллов - "отлично";
+
 
* 27-35 баллов - "хорошо";
+
[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).
* 17-26 баллов - "удовлетворительно";
+
 
* менее 17 баллов - "неудовлетворительно".
+
На дом: [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.6(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.6(2, 4), 3.7(2, 4).
 +
 
 +
'''Занятие 8'''. Вычисления в конечных полях.
 +
 
 +
[6]
 +
 
 +
На дом: [6]
 +
 
 +
==О проведении экзамена==
  
[[Media: Exam-ivdm.pdf|Примерный вариант экзаменационной работы с решениями заданий]]
+
Экзамен устный. В билете два теоретических вопроса и задача. Ответ на вопросы билета без подготовки. При ответе на первый вопрос можно пользоваться любыми бумажными источниками (конспектами лекций, распечатками, книгами). При ответе на второй вопрос никакими источниками пользоваться не разрешается. Задача на одну из трех тем. В течение семестра по каждой из этих тем состоятся коллоквиумы. На каждом из них можно получить одну из трех оценок: 1 (освобождение от задачи), 0,5 или 0 (дополнительная задача). При наличии дополнительных задач по итогам коллоквиумов студент решает эти задачи до того, как возьмет билет.
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Версия 15:02, 20 ноября 2017

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

Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.

Объявления

27 ноября состоится коллоквиум по теме "Конечные группы и теория Пойа" на 1-й паре с 8-45 до 10-20 в ауд. 504. Лекция состоится на 3-й паре с 12-50 до 14-25 в ауд. 609.

Результаты коллоквиумов

Лекции

Часть 1. Конечнозначные функции.

Лекция 1. Конечнозначные функции. Элементарные k-значные функции. Способы представления k-значных функций: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.

Лекция 2. Алгоритм распознавания полноты в P_k. Замкнутые классы. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. Предполные классы.

Лекция 3. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.

Лекция 4. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом. Классы функций, сохраняющих предикат, их замкнутость. Соответствие Галуа.

Коллоквиум по теме "Конечнозначные функции".

Часть 2. Теория Пойа.

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

Лекция 6. Подгруппы. Смежные классы, индекс подгруппы в группе. Теорема Лагранжа о порядке подгруппы конечной группы. Нормальные подгруппы. Фактор-группы.

Лекция 7. Действие группы на множестве. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда.

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

Коллоквиум по теме "Теория Пойа".

Часть 3. Конечные поля.

Лекция 9. Кольца. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Наследование свойств кольца в кольце многочленов. Деление с остатком многочленов над полем.

Лекция 10. Идеалы, главные идеалы колец. Кольцо главных идеалов. Теорема о главном идеале кольца главных идеалов. Кольцо многочленов как кольцо главных идеалов. Построение конечных полей из p^n элементов, где p - простое число, n \ge 2.

Лекция 11. Критерий неприводимости многочленов степени 2 или 3. Расширения полей. Вычисления в полях, алгоритм Евклида. Теорема о мультипликативной группе конечного поля.

Лекция 12.

Коллоквиум по теме "Конечные поля".

Литература

  1. Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
  2. Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
  3. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
  4. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
  5. Задачи для семинарских занятий по теме "Группы. Теория Пойа".
  6. Задачи для семинарских занятий по теме "Конечные поля".

Семинары

Занятие 1. Тождества в k-значной логике. Представления k-значных функций в 1-й и 2-й формах и полиномами по модулю k.

[4] Гл. III 1.1(3, 6, 10, 12), 1.5, 1.11(2, 4, 8, 11), 2.7(1, 3, 6, 9), 2.12(1, 2), 2.8(1, 3).

На дом: [4] Гл. III 1.1(4, 7, 11, 13), 1.6, 1.11(5, 10), 1.12, 2.7(2, 8, 10), 2.12(3, 5), 2.8(2), 2.9, 2.11(1, 2).

Занятие 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.6(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.6(2, 4), 3.7(2, 4).

Занятие 8. Вычисления в конечных полях.

[6]

На дом: [6]

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

Экзамен устный. В билете два теоретических вопроса и задача. Ответ на вопросы билета без подготовки. При ответе на первый вопрос можно пользоваться любыми бумажными источниками (конспектами лекций, распечатками, книгами). При ответе на второй вопрос никакими источниками пользоваться не разрешается. Задача на одну из трех тем. В течение семестра по каждой из этих тем состоятся коллоквиумы. На каждом из них можно получить одну из трех оценок: 1 (освобождение от задачи), 0,5 или 0 (дополнительная задача). При наличии дополнительных задач по итогам коллоквиумов студент решает эти задачи до того, как возьмет билет.