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

Скачать 53.57 Kb.

Название	Дискретная математика
Дата публикации	25.02.2015
Размер	53.57 Kb.
Тип	Реферат

100-bal.ru > Математика > Реферат

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

Преподаватель: Стеценко В.А., доцент кафедры ТИДМ, к.ф.м.н., доцент
Структура и содержание дисциплины

Общая трудоемкость дисциплины составляет 4 зачетных единицы, 144 часа, в том числе 72 аудиторных часа

№п/п	Наименование раздела дисциплины	Содержание раздела (дидактические единицы)
1	Введение	Различие между дискретной и непрерывной математикой. Понятие дискретного множества. Счет и перечисление (перебор) как основные методы дискретной математики.
2	Конечные суммы	Способы записи конечных сумм. Основные правила преобразования конечных сумм. Понятие явной формулы. Вычисление конечных сумм: метод выделения, суммирование разностей, метод двойного суммирования.
3	Элементы комбинаторики	Понятие перечислительной задачи, примеры. Основные свойства конечных множеств: правило суммы, правило произведения; его комбинаторная интерпретация. Решение простейших перечислительных задач. Основные комбинаторные конфигурации: выборки, размещения, перестановки, перестановки с повторениями, сочетания, сочетания с повторениями. Явные формулы для их числа. Простейшие задачи на размещение шаров по ящикам. Метод включения-исключения. Число элементов конечного множества, не удовлетворяющих ни одному из n заданных на этом множестве свойств. Число размещений m различимых шаров по n различимым ящикам, при условии того, что ящики не могут быть пустыми. Число размещений m различимых шаров по n неразличимым ящикам, при условии того, что ящики не могут быть пустыми. Разбиения множеств. Лемма Бернсайда. Применение леммы Бернсайда при комбинаторных подсчетах. Теорема Шпернера. Теорема Эрдеша - Ко - Радо. Теорема о выборе Холла.
4	Рекуррентные соотношения	Понятие рекурсивной процедуры и рекуррентного соотношения. Числа Фибоначчи. Примеры задач, приводящие к рекуррентному соотношению. Рекуррентные соотношения и конечные суммы. Решение рекуррентного соотношения вида . Биномиальные коэффициенты. Рекуррентное соотношение для биномиальных коэффициентов. Треугольник Паскаля. Явная формула для биномиальных коэффициентов. Бином Ньютона. Комбинаторная интерпретация биномиальных коэффициентов. Полиномиальная формула. Метод траекторий. Числа Стирлинга первого и второго рода, их свойства. Теорема обращения.
5	Производящие функции	Производящие функции. Применение производящих функций для решения рекуррентных соотношений (явная формула для чисел Фибоначчи). Алгебра Коши. Применение производящих функций для комбинаторных подсчетов. Применение производящих функций для вычисления комбинаторных сумм. Правильно построенные скобочные структуры. Последовательность Каталана. Явная формула для чисел Каталана. Примеры задач, приводящих к числам Каталана.
6	Элементы теории графов	Основные понятия теории графов. Способы задания графа. Изоморфизм графов. Понятие инварианта графа. Примеры простейших инвариантов графа. Степень вершины графа. Лемма о рукопожатиях и ее следствие. Связные графы. Подграфы. Компоненты связности. Число компонент связности у графа, имеющего p вершин и q ребер. Необходимое условие связности графа. Достаточное условие связности графа Деревья. Характеризационная теорема. Теорема Кэли о числе деревьев, заданных на фиксированном n-множестве. Соответствие Прюфера. Число деревьев с фиксированным числом висячих вершин. Эйлеровы графы. Критерий эйлеровости. Полуэйлеровы графы. Критерий полуэйлеровости. Уникурсальные кривые. Гамильтоновы графы. Теорема Дирака. Укладка графа в топологическое пространство. Планарные и плоские графы. Теорема Эйлера для связных плоских графов, ее следствия. Понятие эйлеровой характеристики. Непланарность графов и . Теорема Понтрягина – Куратовского (без док-ва). Раскраска вершин графа. Хроматическое число и хроматический многочлен графа. Двудольные графы. Теорема Кенига. Понятие карты. Раскрашивание карт. Теорема о четырех красках (без док-ва). Неравенство Хивуда. Теорема Вагнера. Гипотеза Хадвигера. Теорема Турана. Числа Рамсея. Теорема Эрдеша – Шекереса. Существование чисел Рамсея (теорема Рамсея).

ТЕМАТИКА РЕФЕРАТОВ, КУРСОВЫХ РАБОТ

Арифметика чисел Фибоначчи.
Комбинаторика чисел Каталана.
Обобщения треугольника Паскаля.
Алгоритм Евклида и его модификации.
Алгоритм Евклида и числа Фибоначчи; теорема Ламэ.
Суммы и рекуррентности; числа Бернулли.
Рекуррентные формулы в задачах на разбиения.
Производящие функции и разбиения чисел.
Графы и метрики.
Алгоритмы на графах.

3). Промежуточная аттестация

___экзамен___
ПЕРЕЧЕНЬ ВОПРОСОВ К ЭКЗАМЕНУ

Основные понятия теории графов. Степень вершины графа, теорема о сумме степеней вершин графа.
Связные графы. Компоненты связности
Двудольные графы. Теорема Кенига.
Способы представления графов. Матрицы смежности и инциндентности. Число различных графов на n фиксированных вершинах. Изоморфные графы. Простейшие инварианты графа
Планарные и плоские. Теорема Эйлера. Теорема Понтрягина-Куратовского.
Раскраска планарных графов. Хроматическое число и хроматический многочлен графа. Теорема о четырех красках.
Эйлеровы графы. Критерий эйлеровости. Полуэйлеровы графы. Критерий полуэйлеровости. Уникурсальные кривые.
Гамильтоновы графы. Теорема Дирака..
Треугольник Паскаля и биномиальные коэффициенты.
Числа Фибоначчи и их свойства.
Производящие функции и решение рекуррентных соотношений.
Некоторые методы суммирования.
Неравенство Хивуда. Теорема Вагнера. Гипотеза Хадвигера.
Числа Рамсея. Теорема Эрдеша-Шекереса. Теорема Рамсея.

8. Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:

Виленкин Н.Я, Виленкин А.Н., Виленкин П.А. Комбинаторика. М.: МЦНМО, 2006
Дистель Р. Теория графов, Новосибирск, 2002.
Ф. Харари Теория графов, М.: Изд-во Мир, 1973.
Жданов С.А., Матросов В.Л., Стеценко В.А. Сборник задач по дискретной математике.

б) дополнительная литература:

Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.
Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978.
Сачков В.И. Комбинаторные методы дискретной математики. М.: Наука, 1977.
Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
Матросов В.Л., Стеценко В.А. Лекции по дискретной математике. М.: МПГУ, 1997.
Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. М.: Изд-во Наука, 1977.

в) программное обеспечение и Интернет-ресурсы

WolframMathWorld http://mathworld.wolfram.com/
PlanetMath encyclopedia http://planetmath.org/encyclopedia
Wikipedia\, the free encyclopedia http://en.wikipedia.org/wiki/Main_Page

Добавить документ в свой блог или на сайт

Похожие:

	Рабочая программа Дискретная математика Дискретная математика: рабочая программа / А. Ю. Вальков, З. Н. Хакимова. – Спб.: Ивэсэп, 2012. – с		Программа дисциплины «Дискретная математика» для направления 010500.... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки
	Литература по математике (алгебра, геометрия, математический анализ,... Математика on line. В помощь студенту. Основные математические формулы по алгебре, геометрии, тригонометрии, высшей математике, исторические...		Литература Белоусов А. И., Ткачев С. Б. Дискретная математика. М: Изд-во мгту им. Н. Э. Баумана, 2006. 744 с
	Рабочая программа дисциплины дискретная математика (наименование)...		Бюллетень новых поступлений в нб ргу за 3 квартал 2010 г Дискретная математика [Текст] : учебное пособие / А. А. Шестаков [и др.]. М. Рготупс, 2004. 188 с. 80-00
	Вопросы к экзамену по дисциплине “Дискретная математика” Полнота множества функции. Понятие замкнутого класса функций: важнейшие замкнутые классы		Программа по формированию навыков безопасного поведения на дорогах... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов первого года обучения по направлению...
	Радиофизический факультет Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...		Вопросы к государственному экзамену по информатике Дискретная математика. Теория алгоритмов. Математическая логика. Численные методы. Теоретические основы информатики. Исследование...
	Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Криптография и криптоанализ. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, направления...		Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Дополнительные главы дискретной математики. Учебно-методический комплекс. Рабочая программа для студентов очной формы...
	Рабочая программа по дисциплине «Дискретная математика» Государственное образовательное учреждение высшего профессионального образования Московский государственный институт электроники...		Программа по формированию навыков безопасного поведения на дорогах... Акимов О. Е. Дискретная математика. Логика, группы, графы изд., доп М.: Лаб. Базовых Знаний, 2003
	Тюменский государственный университет «утверждаю»: Проректор по учебной работе Вычислительные, программные, информационные системы и компьютерные технологии", "Математический анализ и приложения", "Математическое...		Общие экономические понятия Белоусов А. И., Ткачев С. Б. Дискретная математика: Учеб для вузов / Под ред. В. С. Зарубина и А. П. Крищенко. – 4-е изд. М. Изд-во...

Школьные материалы