uzluga.ru
добавить свой файл
Теоретические вопросы из билетов к зачету (I семестр):

(http://kadm.math.usu.ru)


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

  2. Упорядоченные пары и кортежи. Декартово произведение, свойства.

  3. Бинарные отношения на множестве. Основные свойства бинарных отношений. Примеры.

  4. Основные типы бинарных отношений: эквивалентность, частичный порядок, линейный порядок.

  5. Отношение эквивалентности. Классы эквивалентности. Фактор-множество. Связь отношения эквивалентности и разбиения.

  6. Матрица бинарного отношения. Связь свойств бинарного отношения и свойств его матрицы. Связь с операциями над булевыми матрицами.

  7. Отображения (функции) как отношения. Обратное отображение как отношение. Инъективность, сюръективность, биективность. Ядро отображения.

  8. Отношение частичного порядка. Отношение покрытия. Диаграммы ч.у.м.

  9. Минимальные и максимальные, наименьшие и наибольшие элементы ЧУМ, их свойства.

  10. Изоморфное вложение ч.у.м. Теорема о представлении ч.у.м.

  11. Условия фундированности, индуктивности и артиновости. Как эти условия связаны между собой?

  12. Вполне упорядоченные множества. Принцип полной индукции.

  13. Ординалы. Ординальная сумма и ординальное произведение.

  14. Аксиома выбора. Теорема Цермелло.

  15. Мощность множества. Отношение равномощности. Кардинальное число. Сравнение кардинальных чисел. Теорема Кантора-Бернштейна.

  16. Бесконечные множества. Критерий Дедекинда бесконечности множества. Счетные множества. Теорема о счетных множествах.

  17. Континуальные множества. Теорема о континуальных множествах.

  18. Теорема Кантора о булеане. Иерархия кардиналов. Континуум-гипотеза.

  19. Парадоксы теории множеств. Способы их избежать.

  20. Сочетания. Бином Ньютона. Треугольник Паскаля. Свойство симметрии биномиальных коэффициентов.

  21. Размещения без повторений, с повторениями. Перестановки без повторений, с повторениями. Полиномиальные коэффициенты.

  22. Перестановки как функции. Орбиты элементов. Циклы. Теорема о разложении на циклы.

  23. Симметрические группы. Группа симметрий квадрата. Изоморфизм групп. Теорема Кэли.

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

  25. Принцип включения-исключения. Число сюръекций. Разбиения: числа Стирлинга второго рода, числа Белла.

  26. Рекуррентные соотношения. Решение линейных рекуррентных соотношений с постоянными коэффициентами. Числа Фибоначчи.

  27. Конкатенация и ее свойства. Коммутирующие слова. Полугрупповой код.

  28. Свободная полугруппа. Гомоморфизм. Теорема о гомоморфных образах свободной полугруппы.

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

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

Литература.


  1. В.А. Баранский, В.В. Кабанов. Общая алгебра и ее приложения. Екатеринбург, 2008.

  2. Ю.М. Важенин. Множества, логика, алгоритмы. Екатеринбург, 1995.

  3. Н.К. Верещагин, А. Шень. Начала теории множеств. Часть 1. http://www.mccme.ru/free-books/