uzluga.ru
добавить свой файл
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 из второго раздела) входят и в программу летнего экзамена.