Программа курса «Дискретная математика» - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Программа курса «Дискретная математика» - страница №1/1

ПРОГРАММА КУРСА

«Дискретная математика»

для студентов 1 курса специальностей «Компьютерные науки» и «Компьютерная безопасность»
1 семестр
I. Теория множеств

  1. Понятие множества. Равенство и включение множеств. Пустое и универсальное множества. Булевы операции, их свойства. Упорядоченные пары и кортежи. Декартово произведение, свойства. Булеан множества, свойства. Индексные множества. Бесконечные объединения, пересечения и произведения.

  2. Отношения между множествами. Бинарные отношения (БО) на множестве. Матрица БО. Свойства БО: рефлексивность, транзитивность, симметричность, антисимметричность, линейность. Связь свойств матрицы и свойств БО.

  3. Операции над БО: булевы операции, обращение, умножение, симметричное, транзитивное и рефлексивно-транзитивное замыкания. Связь с операциями над булевыми матрицами. Свойство транзитивного замыкания. Критерий транзитивности.

  4. Отношения эквивалентности. Разбиения множества и порождаемые ими БО. Теорема об отношениях эквивалентности и разбиениях.

  5. Отношения порядка. Упорядоченные множества (ЧУМ). Отношение покрытия, диаграммы Хассе. Минимальные и максимальные, наименьшие и наибольшие элементы ЧУМ, их свойства. Условия индуктивности, минимальности и обрыва убывающих цепей, их эквивалентность. Отношения линейного и полного порядка.

  6. Отображения (функции) как отношения, их матрицы. Инъективность, сюръективность, биективность, их сохранение при суперпозиции.

  7. Мощность множества. Конечные и бесконечные множества, критерий бесконечности множества. Мощности числовых множеств. Сравнение мощностей. Теорема Бернштейна-Кантора. Теорема Кантора о булеане. Иерархия алефов, континуум-гипотеза.

  8. Изоморфизм ЧУМ. Понятие об ординалах. Прямое произведение ЧУМ.

  9. Парадоксы теории множеств. Система аксиом Цермело-Френкеля.


II. Комбинаторика и элементы общей алгебры

  1. Количество элементов множества и число способов выбора. Правила сложения и умножения. Построение биекций. Принцип двойного подсчета. Принцип Дирихле.

  2. Перестановки. Формулы для числа перестановок без повторений / с повторениями. Перестановка как функция. Орбиты элементов. Циклы. Теорема о разложении на циклы. Симметрические группы. Группа симметрий квадрата. Изоморфизм групп. Теорема Кэли.

  3. Биномиальные коэффициенты. Примеры: число подмножеств, число инъекций, число врезок, число решений диофантова уравнения, число путей в решетке. Свойства: симметрия, суммы и взвешенные суммы, четные/нечетные подмножества, бином Ньютона, треугольник Паскаля. Полиномиальные коэффициенты.

  4. Наддиагональные пути в квадратной решетке. Числа Каталана, вывод формулы. Правильные расстановки скобок, триангуляции выпуклых многоугольников.

  5. Принцип включения-исключения (ПВИ). Число сюръекций. Разбиения: числа Стирлинга второго рода, числа Белла. Функция Эйлера. Число перемещений.

  6. Рекуррентные соотношения. Теорема Лагранжа о линейных рекуррентных соотношениях (без д-ва). Вывод явной формулы для чисел Фибоначчи.

  7. Порядок роста функции. Сравнение функций, O-, Ω- и Θ-символика. Примеры вычисления порядка роста: число правильных расстановок скобок, число бинарных слов без подслова 00 и без подслов 00,111.

  8. Конкатенация и ее свойства. Коммутирующие слова. Свободная полугруппа. «Вложение» N* в {0,1}*. Гомоморфизм. Гомоморфный образ. Теорема о гомоморфных образах свободной полугруппы.

  9. Построение свободной группы: эквивалентность слов, операция на классах слов, редуцированные слова, единственность редуцированного слова в классе.

  10. Смежные классы по подгруппе. Теорема Лагранжа. Нормальные подгруппы.


Примечание. Вопросы по общей алгебре (2, 8-10 из второго раздела) входят и в программу летнего экзамена.