Учебная программа

Утверждаю

зав. кафедрой алгебры

___________________

«___»_________2009г.

Брянский государственный университет им. Академика

Учебная программа

По курсу «Основы дискретной математики», для студентов ФМФ (3 курс 5 семестр, учебный год).

Общий объем курса 68 часов, из них 34 часа лекций, 34 часа практических занятий.

Программу разработал .

Лекция 1.	Множество. Операции над множествами. Равные множества. Подмножество. Свойства операций над множествами. Метод встречных включений.	Практическое занятие 1.	Множества. Метод встречных включений. [2] 1.5, 1.7 (1,3,5), 1.10 (1,3), 1.11 (1,3,5,7,9,1), [5] 1 (1,3,5,7,9). Д/з. [2] 1.7 (2,4), 1, 1.11 (2,4,6,8), [5] 1 (2,4,6,8,10).
Лекция 2.	Перестановки. Размещения. Сочетания. Свойства. Перестановки с повторением. Размещения с повторением. Сочетания с повторением. Свойства.	Практическое занятие 2.	Комбинаторные конфигурации без повторений и с повторениями.
Лекция 3.	Прямое произведение множеств. Бинарное отношение. Свойства. Отношение эквивалентности. Отношение порядка.	Практическое занятие 3.	Свойства бинарных отношений. Отношение порядка. Отношение эквивалентности.
Лекция 4.	Граф. Виды графов. Изоморфизм графов. Представление графов. Матрицы графов. Обходы графов. Операции над графами.	Практическое занятие 4.	Изоморфизм графов. Представление графов. Поиск в глубину и ширину.
Лекция 5.	Функциональное отношение. Область и кообласть. Отображение. Инъективное и сурьективное отображения. Биекция.	Практическое занятие 5.	Функция. Свойства.
Лекция 6.	Композиция функций. Тождественное отображение. Обратное отображение. Теорема об обратной функции.	Практическое занятие 6.	Композиция функций. Обратная функция.
Лекция 7.	Алгебраическая операция. Группоид, полугруппа, моноид, группа.	Практическое занятие 7.	Алгебраическая операция. Группа.
Лекция 8.	Полукольцо. Аксиомы Пеано. Полукольцо натуральных чисел. Метод математической индукции.	Практическое занятие 8.	Метод математической индукции.
Лекция 9.	Кольцо. Подкольцо. Критерий подкольца. Свойства колец.	Практическое занятие 9.	Контрольная работа № 1.
Лекция 10.	Поле. Подполе. Критерий подполя. Свойства полей.	Практическое занятие 10.	Кольцо. Подкольцо. Критерий подкольца. Поле. Подполе. Критерий подполя.
Лекция 11.	Высказывание. Операции над высказываниями. Формулы АВ. Булевы функции. Нормальные формы формул АВ.	Практическое занятие 11.	Формулы АВ. Булевы функции. Нормальные формулы.
Лекция 12.	СДНФ, СКНФ. Полиномы Жегалкина. Представление булевой функции полиномом Жегалкина.	Практическое занятие 12.	СДНФ. СКНФ. Полиномы Жегалкина.
Лекция 13.	Классы булевых функций. Полные системы булевых функций. Теорема Поста. k-значные логики.	Практическое занятие 13.	Полные системы булевых функций. Теорема Поста.
Лекция 14.	Числа Фибоначчи. Рекуррентные соотношение. Решение рекуррентных соотношений первого порядка.	Практическое занятие 14.	Решения рекуррентных соотношений первого порядка.
Лекция 15.	Деревья. Характеристическая теорема о деревьях. Код Прюфера.	Практическое занятие 15.	Деревья. Код Прюфера. Остов минимального веса. Алгоритм Дейкстры. Путь минимального веса. Алгоритм Краскала.
Лекция 16.	Остов минимального веса. Алгоритм Дейкстры. Путь минимального веса. Алгоритм Краскала.	Практическое занятие 16.	Сети. Поток. Алгоритм нахождения максимального потока.
Лекция 17.	Сети. Поток. Максимальный поток. Теорема Форда-Фалкерсона.	Практическое занятие 17.	Контрольная работа № 2.

Рекомендованная литература:

Куликов и теория чисел. М.: Высшая школа, 19с. Шнеперман задач по алгебре и теории чисел. Мн.: Высшая школа, 19с. , Соминский по высшей алгебре. СПб.: Изд. «Лань», 20с. Анищенко рекомендации для студентов заочников 4 курса физико-математического факультета. Брянск 1989 г. , Иноземцева рекомендации для студентов заочников 1 курса ФМФ. Брянск 1991. Горбачев рекомендации для студентов заочников 3 курса ФМФ. Брянск 1988.