Избранные вопросы дискретной математики

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

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

Лекции

Часть 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. Произведение неприводимых многочленов над простым полем. Число неприводимых нормированных многочленов над простым полем. Корни неприводимых многочленов над полем в его расширении. Существование и единственность поля из p^n элементов, где p - простое число, n \ge 1.

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

Литература

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.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).

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

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