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

Программа курса

Курс "Избранные вопросы дискретной математики" читается в 5-м семестре. Форма отчетности - экзамен. Экзамен проходит письменно. За экзаменационную работу студент получает определенное количество баллов.

В течение семестра по курсу проходят два письменных коллоквиума. За каждый коллоквиум студент получает дополнительные или штрафные баллы.

Оценка на экзамене по курсу выставляется по следующему правилу: количество баллов, полученное студентом за экзаменационную работу, увеличивается на дополнительные баллы за коллоквиумы или уменьшается на штрафные баллы за коллоквиумы; по вычисленному значению выводится оценка по критериям экзамена (критерии станут известны позднее).

Первый коллоквиум состоится на 6-й лекции 10 октября. Темы коллоквиума: прочитанные пять лекций. При написании коллоквиума не разрешается пользоваться никакими материалами.

Второй коллоквиум состоится на 12-й лекции 21 ноября. Темы коллоквиума: прочитанные шестая-одиннадцатая лекции. При написании коллоквиума не разрешается пользоваться никакими материалами.

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

Лекции

Лекция 1: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры.

Лекция 2: Биномиальные и полиномиальные коэффициенты, их свойства. Метод производящих функций (конечный случай). Оценки биномиальных коэффициентов и их сумм.

Лекция 3: Частично упорядоченные множества (ЧУМ). Диаграмма Хассе. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи. Теорема Дилуорса. Булев куб, его длина и ширина. Булеан.

Лекция 4: Теорема Анселя о разбиении булева куба на цепи. Оценки числа монотонных булевых функций. Расшифровка монотонных булевых функций.

Лекция 5: Покрытия множества и покрытия матрицы. Лемма о градиентном покрытии. Оценки мощности затеняющего множества булева куба и длины полиномиальных нормальных форм булевых функций.

Лекция 6: Коллоквиум 1.

Лекция 7: Функция Мёбиуса. Формула обращения Мёбиуса. Принцип включений-исключений.

Лекция 8: Линейные однородные и неоднородные рекуррентные уравнения.

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

Лекция 10: Подгруппы. Смежные классы. Теорема Лагранжа. Орбита и стабилизатор элемента. Лемма Бернсайда.

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

Лекция 12 (21.11): Коллоквиум 2.

Лекция 13 (28.11): Кольца. Кольцо многочленов.

Лекция 14 (5.12): Поля. Теорема о поле из p^n элементов, где p -- простое число, n > 1.

Лекция 15 (12.12): Линейные коды.

Лекция 16 (19.12): Функции k-значной логики и способы их представления.

Вопросы к экзамену по курсу «Избранные вопросы дискретной математики»

(осенний семестр 2009/2010 учебного года, группы 318, 319, лектор — доцент С.Н. Селезнева)

Часть A. Вопросы, при ответе на которые, можно пользоваться конспектами (некоторое время, при этом ответ не состоит в чтении конспекта). Определения и теоремы должны быть сформулированы до того, как конспект будет открыт.

• Алгоритм распознавания полноты конечных систем функций k-значной логики.
• Теорема Кузнецова о функциональной полноте.
• Существенные функции. Леммы о существенных функциях: о трех наборах, основная и о квадрате.
• Критерий полноты Яблонского систем функций k-значной логики.
• Операции над о.-д. функциями. Замкнутость класса о.-д. функций относительно операций суперпозиции и обратной связи.
• Леммы о преобразовании периодических последовательностей о.-д. функцией. Несводимость операции обратной связи к операции суперпозиции.
• Леммы о преобразовании машинных кодов: основного в l-кратный, решетчатого в основной и квазиосновного в основной.
• Операция суперпозиции. Теорема о замкнутости класса вычислимых функций относительно операции суперпозиции.
• Операция примитивной рекурсии. Теорема о замкнутости класса вычислимых функций относительно операции примитивной рекурсии.
• Операция минимизации. Теорема о замкнутости класса вычислимых функций относительно операции минимизации.
• Класс примитивно-рекурсивных функций. Примитивная рекурсивность функции Пеано и ее обобщений. Классы частично-рекурсивных и общерекурсивных функций.
• Теорема о схеме одновременной примитивной рекурсии.
• Формула Клини. Теорема о соотношении классов частично-рекурсивных и вычислимых функций.
• Кольцо многочленов над полем. Теорема о делении многочленов с остатком. Делимость многочленов. Теорема о наибольшем общем делителе двух многочленов.
• Неприводимость многочленов над полем. Теорема о неприводимом делителе произведения многочленов. Теорема о каноническом разложении многочлена на неприводимые сомножители.
• Теорема о фактор-кольце кольца целых чисел.
• Теорема о фактор-кольце кольца многочленов над простым полем.
• Теорема Анселя о разбиении куба

на цепи. Теорема об оценках числа монотонных булевых функций.

Часть B. Вопросы, при ответе на которые пользоваться конспектами не предполагается. Ответ почти без подготовки.

• Теоремы о I-й и II-й формах записи функций k-значной логики.
• Полные системы. Полнота системы Поста. Функция Вебба.
• Шефферовы функции. Критерий шефферовости.
• Теоремы Янова и Мучника. Следствия из них.
• Теорема о полноте системы полиномов в Pk.
• Детерминированные функции (д. функции). Мощность класса д. функций. Задание д. функций нагруженными деревьями.
• Ограниченно-детерминированные функции (о.-д. функции). Способы их задания. Мощность класса о.-д. функций.
• Полнота систем о.-д. функций. Существование аналога функции Шеффера.
• Машины Тьюринга (МТ). Машинные коды: основной, l-кратный, решетчатый, квазиосновной. Задача поиска левой единицы в основном коде.
• Лемма о моделировании на решетке.
• Класс примитивно-рекурсивных функций. Примитивная рекурсивность некоторых функций (знака, сложения, умножения, целой части от деления, и т.д.). Классы частично-рекурсивных и общерекурсивных функций.
• Алгебраическая операция, нейтральный элемент, симметричный элемент. Группа, абелева группа. Конечная группа, порядок группы, таблица Кэли. Симметрическая группа перестановок. Подгруппа. Теорема Кэли.
• Теорема Лагранжа о порядке подгруппы конечной группы.
• Эквивалентность элементов относительно группы перестановок. Орбита и стабилизатор элемента. Лемма о порядке стабилизатора элемента. Лемма Бернсайда о числе орбит.
• Раскраски, эквивалентность раскрасок относительно группы перестановок. Теорема Пойа о числе орбит раскрасок.
• Кольцо, целостное кольцо, поле. Кольцо многочленов над некоторым кольцом. Теорема о целостности кольца многочленов над полем.
• Значение многочлена в точке, корень многочлена. Критерий неприводимости многочленов степени, не выше 3.
• Теорема о конечном целостном кольце.
• Характеристика кольца. Теорема о характеристике конечного поля.
• Идеал кольца, главный идеал. Эквивалентность элементов кольца и класс вычетов по модулю идеала. Фактор-кольцо по модулю идеала.
• Частично-упорядоченные множества (ЧУМ). Минимальные и максимальные, наименьший и наибольший элементы. Длина и ширина конечного ЧУМ. Теорема Дилуорса о ширине конечного ЧУМ.
• Теоремы о длине и ширине куба

.

Литература

• Яблонский С. В. Введение в дискретную математику. М., Наука, 2001.
• Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М., Мир, 1988.
• Ансель Ж. О числе монотонных булевых функций от n переменных. В кн. Кибернетический сборник. Новая серия. Вып. 5. М., Мир, 1968, с. 53-57.
• Де Брейн Н. Дж. Теория перечисления Пойа. В сб. ст. Прикладная комбинаторная математика, под ред. Э. Бакенбаха. М., Мир, 1966, с. 61-107.

Типовые задачи

• Записать функцию k-значной логики в I-й или II-й форме, построить ее полином или доказать, что она не задается полиномом по mod 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.