Программа дисциплины дискретная математика




НазваниеПрограмма дисциплины дискретная математика
Дата публикации17.10.2016
Размер9.76 Kb.
ТипПрограмма дисциплины
КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ


"УТВЕРЖДАЮ"

Проректор

__________ В.С.Бухмин

ПРОГРАММА ДИСЦИПЛИНЫ


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


Цикл ЕН.В.

Специальность: 010400 – Физика

Направление: 510400 - Физика

Принята на заседании кафедры Теории относительности и гравитации

(протокол № 6 от "5" июня 2009 г.)

Заведующий кафедрой
________________ (А.В. Аминова)

Утверждена Учебно-методической комиссией физического факультета КГУ.

(протокол №___ от "__"__________200__ г.)

Председатель комиссии
____________________ (Д.А. Таюрский)

Рабочая программа дисциплины "Дискретная математика" предназначена для студентов 2 курса

по специальности: 010400 – Физика

по направлению: 510400 - Физика

АВТОР: Иваньшин П.Н.

^ КРАТКАЯ АННОТАЦИЯ: Курс лекций «Дискретная математика» состоит из разделов: Теория графов и Основы теории чисел.

1. Требования к уровню подготовки студента, завершившего изучение дисциплины «Дискретная математика».

Студенты, завершившие изучение данной дисциплины, должны:

  • знать основные положения теории графов и теории чисел;

  • овладеть методами решения соответствующих задач;

  • уметь использовать эти методы при работе с конкретными приложениями и программами.



^ 2. Объем дисциплины и виды учебной работы (в часах)

Форма обучения очная

Количество семестров 1

Форма контроля: 4 семестр зачет



п/п

Виды учебных занятий

Количество часов







4 семестр

1.

Всего часов по дисциплине

150

2.

Самостоятельная работа

116

3.

Аудиторных занятий

34




в том числе: лекций

34




семинарских (или лабораторно-практических) занятий






  1. Содержание дисциплины.


^ ТРЕБОВАНИЯ ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО СТАНДАРТА К ОБЯЗАТЕЛЬНОМУ МИНИМУМУ СОДЕРЖАНИЯ ПРОГРАММЫ

Индекс

Наименование дисциплины и ее основные разделы

Всего часов

ЕН.В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





^ ОСНОВНАЯ ЛИТЕРАТУРА



  1. Басакер Р., Саати Т. Конечные графы и сети Конечные графы и сети. М.: Наука, 1974. 368c.

  2. Берж К. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.

  3. Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.

  4. Оре О. Теория графов. — 2-е изд.. — М.: Наука, 1980. — С. 336.

  5. Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с.

  6. Харари Ф. Харари Ф. Теория графов Харари Ф. . — М.: Харари Ф. Мир Харари Ф. , 1973. Харари Ф. Харари Ф.

  7. Diestel R. Diestel R. Graph Theory, Electronic Edition Diestel R. . — NY: Springer-Verlag, 2005. — С. 422 Diestel R. Diestel R.

  8. Виноградов И.М. Основы теории чисел. - М.: Наука, 1972. - 178 с.

  9. Бухштаб А.А. Теория чисел. - М.: Просвещение, 1966. - 384

  10. О. Оре Приглашение в теорию чисел: Пер с англ. Изд. 2-е, стереотипное. — М.: Едиториал УРСС, 2003. — 128 с.

  11. Clark W.E. Elementary number theory.

Похожие:

Программа дисциплины дискретная математика iconДискретная математика, часть 3
Машина Тьюринга для копирования двоичного слова произвольной длины в прямом порядке
Программа дисциплины дискретная математика iconАннотация к программе учебной дисциплины математика
Рабочая программа учебной дисциплины является частью основной профессиональной образовательной программы в соответствии с фгос по...
Программа дисциплины дискретная математика iconРабочая программа по курсу “Теория компиляции.” ( наименование дисциплины по учебному плану )
Рабочая программа составлена на основании Государственного стандарта высшего профессионального образования по направлению подготовки...
Программа дисциплины дискретная математика iconРабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование...
Рабочая программа составлена на основании Государственного стандарта высшего профессионального образования по направлению подготовки...
Программа дисциплины дискретная математика iconДискретная математика Расчетно-графическое задание – 1 курс, 2008 г
...
Программа дисциплины дискретная математика iconРабочая программа учебной дисциплины математика
Примерная программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта (далее фгос)...
Программа дисциплины дискретная математика iconРабочая учебная программа по предмету одп. 14 «Математика» на 317...
Программа учебной дисциплины «Математика» предназначена для изучения математики в учреждениях начального профессионального образования,...
Программа дисциплины дискретная математика iconСписок вопросов к экзамену по курсу "Дискретная математика" мат мех.,...
Функции, сохраняющие константы. Самодвойственные функции. Монотонные функции. Линейные функции. Критерий полноты: теорема Поста
Программа дисциплины дискретная математика iconПояснительная записка Настоящая рабочая программа разработана применительно...
Математика 5 – 11 кл./ Мпи ( Математика, психология, интеллект), автор Э. Г. Гельфман, рекомендованной Департаментом образовательных...
Программа дисциплины дискретная математика iconРабочая программа дисциплины название учебной дисциплины
Рабочая программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта (далее – фгос)...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
dopoln.ru
Главная страница