Программа курса «Дискретная математика»



Скачать 25.82 Kb.
Дата03.12.2012
Размер25.82 Kb.
ТипПрограмма курса
ПРОГРАММА КУРСА

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

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

Похожие:

Программа курса «Дискретная математика» iconПрограмма дисциплины Дискретная математика для социологов для направления 040200. 62 Социология подготовки бакалавра
Требования к студентам: Учебная дисциплина “Дискретная математика для социологов” (4-й и 5-й модули учебного плана 1-го курса факультета...
Программа курса «Дискретная математика» iconПрограмма дисциплины «Дискретная математика»
...
Программа курса «Дискретная математика» iconПрограмма дисциплины Дискретная математика для социологов для направления 040200. 62 «Социология» подготовки бакалавра Автор: Дагаев Д. А
Курс «Дискретная математика для социологов» предназначен для студентов 1-го курса бакалавриата факультета социологии. Он является...
Программа курса «Дискретная математика» iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа курса «Дискретная математика» iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа курса «Дискретная математика» iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа курса «Дискретная математика» iconРабочей программы дисциплины дискретная математика
Дискретная математика и математическая логика входят в цикл профессиональных дисциплин в базовой части. Для их успешного изучения...
Программа курса «Дискретная математика» iconРабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика Квалификация выпускника
Целями освоения дисциплины «Дискретная математика» являются получение теоретических знаний по основам дискретной математики
Программа курса «Дискретная математика» iconУчебная программа Дисциплины б2 «Дискретная математика» по направлению 010300 «Фундаментальная информатика и информационные технологии»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Программа курса «Дискретная математика» iconУчебная программа Дисциплины б4 «Дискретная математика» по специальности 090302 «Информационная безопасность телекоммуникационных систем»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org