КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
"УТВЕРЖДАЮ"
Проректор
__________ В.С.Бухмин
ПРОГРАММА ДИСЦИПЛИНЫ
Дискретная математика
Цикл ЕН.В.
Специальность: 010400 – Физика
Направление: 510400 - Физика
Принята на заседании кафедры Теории относительности и гравитации
(протокол № 6 от "5" июня 2009 г.)
Заведующий кафедрой
________________ (А.В. Аминова)
Утверждена Учебно-методической комиссией физического факультета КГУ.
(протокол №___ от "__"__________200__ г.)
Председатель комиссии
____________________ (Д.А. Таюрский)
Рабочая программа дисциплины "Дискретная математика" предназначена для студентов 2 курса
по специальности: 010400 – Физика
по направлению: 510400 - Физика
АВТОР: Иваньшин П.Н.
^ Курс лекций «Дискретная математика» состоит из разделов: Теория графов и Основы теории чисел.
1. Требования к уровню подготовки студента, завершившего изучение дисциплины «Дискретная математика».
Студенты, завершившие изучение данной дисциплины, должны:
знать основные положения теории графов и теории чисел;
овладеть методами решения соответствующих задач;
уметь использовать эти методы при работе с конкретными приложениями и программами.
^
Форма обучения очная
Количество семестров 1
Форма контроля: 4 семестр зачет
№
п/п
|
Виды учебных занятий
|
Количество часов
|
|
|
4 семестр
|
1.
|
Всего часов по дисциплине
|
150
|
2.
|
Самостоятельная работа
|
116
|
3.
|
Аудиторных занятий
|
34
|
|
в том числе: лекций
|
34
|
|
семинарских (или лабораторно-практических) занятий
|
|
Содержание дисциплины.
^
Индекс
|
Наименование дисциплины и ее основные разделы
|
Всего часов
|
ЕН.В1
|
Дискретная математика. Теория графов.
Понятие графа. Орграф, мультиграф. Операции над графами. Связность графов. Цепи, маршруты, циклы. Связность, реберная связность. Расстояние в графах. Задача коммивояжера. Деревья. Классификация деревьев. Обходы графов. Гамильтоновы и Эйлеровы графы. Теоремы Дирака и Эйлера. Матрицы инцидентности и смежности. Реализация графов. Планарные графы. Формула Эйлера и ее следствия.Теорема Куратовского. Раскрашивание графов. Теоремы о 5-и и 4-х красках. Раскрашивание вершин, ребер и граней. Оценки раскрашиваемости.
Теория чисел. Простые числа. Делимость. Простые и составные числа. Основная теорема арифметики. Алгоритм Евклида. Свойства делителей. Совершенные числа. Числа Ферма и Мерсенна. Сравнения. Свойства сравнений. Системы вычетов. Линейные и квадратичные сравнения. Функции Эйлера и Ферма. Малая теорема Ферма. Большая теорема Ферма. Случаи степеней 3, 4.
|
150
|
|
|
|
Примечание: Если дисциплина, устанавливается вузом самостоятельно, то в данной таблице ставится прочерк.
^
№ п/п
|
Название темы и ее содержание
|
Количество часов
|
|
|
лекции
|
(лаб.-практ.) занятия
|
1
|
Понятие графа.
Орграф, мультиграф. Лемма о рукопожатиях. Операции над графами.
|
2
|
|
2
|
Связность графов.
Цепи, маршруты, циклы. Связность, реберная связность. Компоненты графа.
|
2
|
|
3
|
Расстояние в графах.
Понятия: радиус, диаметр, обхват, окружение и их свойства. Задача коммивояжера.
|
2
|
|
4
|
Деревья и леса.
Эквивалентные определения дерева.
Классификация деревьев. Существование остовного дерева.
|
2
|
|
5
|
Обходы графов.
Гамильтоновы и Эйлеровы графы. Теоремы Дирака и Эйлера.
|
2
|
|
6
|
Линейная алгебра на графах.
Матрицы инцидентности и смежности. Пространства циклов и разрезов графов. Индуцированные циклы и минимальные разрезы.
|
2
|
|
7
|
Реализация графов.
Реализация графов в R^3. Планарные графы. Теорема Куратовского. Формула Эйлера и ее следствия. Плоско-двойственные графы.
|
2
|
|
8
|
Раскрашивание графов
Теоремы о 5-и и 4-х красках. Раскрашивание вершин, ребер и граней. Оценки раскрашиваемости.
|
2
|
|
9
|
Простые числа.
Простые и составные числа. Делимость. Свойства делителей.
|
2
|
|
10
|
Основная теорема арифметики.
Существование и единственность разложения.
|
2
|
|
11
|
Алгоритм деления.
Алгоритм Евклида. Признаки делимости.
|
2
|
|
12
|
Совершенные числа.
Числа Ферма и Мерсенна. Теорема о связи чисел Мерсенна и совершенных чисел.
|
2
|
|
13
|
Сравнения.
Понятие сравнения, свойства сравнений. Кольцо Z_n и группа U_n. Системы вычетов.
|
2
|
|
14
|
Дальнейшие свойства сравнений.
Полиномиальные сравнения. Функции Эйлера и Ферма. Китайская теорема об остатках. Малая теорема Ферма.
|
4
|
|
15
|
Большая теорема Ферма.
Случаи степеней 2 (пифагоровы тройки), 3, 4.
|
2
|
|
16
|
Приложения теории чисел --- RSA-шифрование, вычисление осатков от деления, схема Диффи-Хелмана.
|
2
|
|
|
Итого часов
|
34
|
|
^
Басакер Р., Саати Т. Конечные графы и сети Конечные графы и сети. М.: Наука, 1974. 368c.
Берж К. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.
Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.
Оре О. Теория графов. — 2-е изд.. — М.: Наука, 1980. — С. 336.
Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с.
Харари Ф. Харари Ф. Теория графов Харари Ф. . — М.: Харари Ф. Мир Харари Ф. , 1973. Харари Ф. Харари Ф.
Diestel R. Diestel R. Graph Theory, Electronic Edition Diestel R. . — NY: Springer-Verlag, 2005. — С. 422 Diestel R. Diestel R.
Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 178 с.
Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384
О. Оре Приглашение в теорию чисел: Пер с англ. Изд. 2-е, стереотипное. — М.: Едиториал УРСС, 2003. — 128 с.
Clark W.E. Elementary number theory.
|
