|
|
| Строка 6: |
Строка 6: |
| | | | |
| | ==Лекции== | | ==Лекции== |
| − |
| |
| − | '''Часть 1. Функции k-значной логики'''.
| |
| − |
| |
| − | '''Лекция 1'''. Функции k-значной логики. Формулы. Тождества. Представимость функций k-значной логики в 1-й и 2-й формах.
| |
| − |
| |
| − | '''Лекция 2'''. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота. Теорема о полноте системы Поста. Функция Вебба.
| |
| − |
| |
| − | '''Лекция 3'''. Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции.
| |
| − |
| |
| − | '''Лекция 4'''. Выразимость и полнота в P_k, их алгоритмическая разрешимость для конечных множеств. Алгоритм распознавания полноты в P_k.
| |
| − |
| |
| − | '''Лекция 5'''. Замкнутые классы. Отношения. Сохранение функцией отношения. Замкнутость класса всех функций, сохраняющих заданное отношение. Классы функций, сохраняющих некоторые отношения.
| |
| − |
| |
| − | '''Лекция 6'''. Предполные классы. Описание предполных классов. Теорема Кузнецова о предполных классах в P_k.
| |
| − |
| |
| − | '''Лекция 7'''. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теорема Янова. Теорема Мучника. Мощность множества замкнутых классов в P_k.
| |
| − |
| |
| − | Коллоквиум по теме "Функции k-значной логики".
| |
| − |
| |
| − | <!---'''Часть 2. Группы'''.
| |
| − |
| |
| − | '''Лекция 8'''. Группы. Подгруппы. Смежные классы. Разложение группы по подгруппе. Нормальные подгруппы. Фактор-группы.
| |
| − |
| |
| − | '''Лекция 9'''. Перестановки. Симметрическая группа перестановок. Теорема Кэли. Орбита и стабилизатор элемента. Лемма Бернсайда.
| |
| − |
| |
| − | '''Лекция 10'''. Раскраски. Эквивалентность раскрасок по группе. Теорема Пойа. Примеры.
| |
| − |
| |
| − | Коллоквиум по теме "Группы".
| |
| − |
| |
| − | '''Часть 3. Конечные поля'''.
| |
| − |
| |
| − | '''Лекция 11'''. Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Критерий неприводимости многочленов степени 2 и 3.
| |
| − |
| |
| − | '''Лекция 12'''. Построение конечных полей из p^n элементов, где p - простое число, n \ge 1. Нахождение обратного элемента в конечном поле. Мультипликативная группа конечного поля. Примитивный элемент конечного поля.
| |
| − |
| |
| − | '''Лекция 13'''. Число неприводимых многочленов над простым полем. Расширения полей. Существование и единственность конечного поля с p^n элементами, где p - простое число, n \ge 1.
| |
| − |
| |
| − | Коллоквиум по теме "Конечные поля".
| |
| − | --->
| |
| − |
| |
| − | '''Литература'''
| |
| − |
| |
| − | Основная:
| |
| − |
| |
| − | # Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
| |
| − | # Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
| |
| − | # Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
| |
| − | # Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., Физматлит, 2004.
| |
| − | <!---# [[Media:ivdm-sem.pdf|Задачи для семинарских занятий]] по теме "Группы. Теория Пойа".
| |
| − | # [[Media:ivdm-sem3.pdf|Задачи для семинарских занятий]] по теме "Конечные поля".--->
| |
| − | Дополнительная:
| |
| − |
| |
| − | # Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2016. Глава 1.
| |
| − | # Марченков С.С. Функциональные системы с операцией суперпозиции. М.: Физматлит, 2004. Глава 1.
| |
| − | # Яблонский С.В., Гаврилов Г.П., Набебин А.А. Предполные классы в многозначных логиках. М.: МЭИ, 1997. Часть 1.
| |
| − | # Lau D. Function Algebras on Finite Sets. Springer, 2006.
| |
| − | # Горшков С.П., Тарасов А.В. Сложность решения систем булевых уравнений. М.: Курс, 2017.
| |
| | | | |
| | ==Семинары== | | ==Семинары== |
Курс "Избранные вопросы дискретной математики" читается в 5-м семестре (36 ч лекций и 18 ч семинаров). Отчетность - экзамен.
