Похожие работы
|
Программа курса «Дискретная математика» - страница №1/1
ПРОГРАММА КУРСА
«Дискретная математика»
для студентов 1 курса специальностей «Компьютерные науки» и «Компьютерная безопасность»
1 семестр
I. Теория множеств
-
Понятие множества. Равенство и включение множеств. Пустое и универсальное множества. Булевы операции, их свойства. Упорядоченные пары и кортежи. Декартово произведение, свойства. Булеан множества, свойства. Индексные множества. Бесконечные объединения, пересечения и произведения.
-
Отношения между множествами. Бинарные отношения (БО) на множестве. Матрица БО. Свойства БО: рефлексивность, транзитивность, симметричность, антисимметричность, линейность. Связь свойств матрицы и свойств БО.
-
Операции над БО: булевы операции, обращение, умножение, симметричное, транзитивное и рефлексивно-транзитивное замыкания. Связь с операциями над булевыми матрицами. Свойство транзитивного замыкания. Критерий транзитивности.
-
Отношения эквивалентности. Разбиения множества и порождаемые ими БО. Теорема об отношениях эквивалентности и разбиениях.
-
Отношения порядка. Упорядоченные множества (ЧУМ). Отношение покрытия, диаграммы Хассе. Минимальные и максимальные, наименьшие и наибольшие элементы ЧУМ, их свойства. Условия индуктивности, минимальности и обрыва убывающих цепей, их эквивалентность. Отношения линейного и полного порядка.
-
Отображения (функции) как отношения, их матрицы. Инъективность, сюръективность, биективность, их сохранение при суперпозиции.
-
Мощность множества. Конечные и бесконечные множества, критерий бесконечности множества. Мощности числовых множеств. Сравнение мощностей. Теорема Бернштейна-Кантора. Теорема Кантора о булеане. Иерархия алефов, континуум-гипотеза.
-
Изоморфизм ЧУМ. Понятие об ординалах. Прямое произведение ЧУМ.
-
Парадоксы теории множеств. Система аксиом Цермело-Френкеля.
II. Комбинаторика и элементы общей алгебры
-
Количество элементов множества и число способов выбора. Правила сложения и умножения. Построение биекций. Принцип двойного подсчета. Принцип Дирихле.
-
Перестановки. Формулы для числа перестановок без повторений / с повторениями. Перестановка как функция. Орбиты элементов. Циклы. Теорема о разложении на циклы. Симметрические группы. Группа симметрий квадрата. Изоморфизм групп. Теорема Кэли.
-
Биномиальные коэффициенты. Примеры: число подмножеств, число инъекций, число врезок, число решений диофантова уравнения, число путей в решетке. Свойства: симметрия, суммы и взвешенные суммы, четные/нечетные подмножества, бином Ньютона, треугольник Паскаля. Полиномиальные коэффициенты.
-
Наддиагональные пути в квадратной решетке. Числа Каталана, вывод формулы. Правильные расстановки скобок, триангуляции выпуклых многоугольников.
-
Принцип включения-исключения (ПВИ). Число сюръекций. Разбиения: числа Стирлинга второго рода, числа Белла. Функция Эйлера. Число перемещений.
-
Рекуррентные соотношения. Теорема Лагранжа о линейных рекуррентных соотношениях (без д-ва). Вывод явной формулы для чисел Фибоначчи.
-
Порядок роста функции. Сравнение функций, O-, Ω- и Θ-символика. Примеры вычисления порядка роста: число правильных расстановок скобок, число бинарных слов без подслова 00 и без подслов 00,111.
-
Конкатенация и ее свойства. Коммутирующие слова. Свободная полугруппа. «Вложение» N* в {0,1}*. Гомоморфизм. Гомоморфный образ. Теорема о гомоморфных образах свободной полугруппы.
-
Построение свободной группы: эквивалентность слов, операция на классах слов, редуцированные слова, единственность редуцированного слова в классе.
-
Смежные классы по подгруппе. Теорема Лагранжа. Нормальные подгруппы.
Примечание. Вопросы по общей алгебре (2, 8-10 из второго раздела) входят и в программу летнего экзамена.
|