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




Скачать 54.42 Kb.
НазваниеДискретная математика
Дата13.03.2013
Размер54.42 Kb.
ТипРеферат
Дискретная математика

2 курс 1 семестр


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


Структура и содержание дисциплины


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


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


№п/п

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

Содержание раздела

(дидактические единицы)

1

Введение

Различие между дискретной и непрерывной математикой. Понятие дискретного множества. Счет и перечисление (перебор) как основные методы дискретной математики.


2

Конечные суммы

Способы записи конечных сумм. Основные правила преобразования конечных сумм. Понятие явной формулы. Вычисление конечных сумм: метод выделения, суммирование разностей, метод двойного суммирования.


3

Элементы комбинаторики

Понятие перечислительной задачи, примеры. Основные свойства конечных множеств: правило суммы, правило произведения; его комбинаторная интерпретация. Решение простейших перечислительных задач.

Основные комбинаторные конфигурации: выборки, размещения, перестановки, перестановки с повторениями, сочетания, сочетания с повторениями. Явные формулы для их числа. Простейшие задачи на размещение шаров по ящикам.

Метод включения-исключения. Число элементов конечного множества, не удовлетворяющих ни одному из n заданных на этом множестве свойств. Число размещений m различимых шаров по n различимым ящикам, при условии того, что ящики не могут быть пустыми. Число размещений m различимых шаров по n неразличимым ящикам, при условии того, что ящики не могут быть пустыми. Разбиения множеств.

Лемма Бернсайда. Применение леммы Бернсайда при комбинаторных подсчетах.

Теорема Шпернера. Теорема Эрдеша - Ко - Радо. Теорема о выборе Холла.


4

Рекуррентные соотношения

Понятие рекурсивной процедуры и рекуррентного соотношения. Числа Фибоначчи. Примеры задач, приводящие к рекуррентному соотношению. Рекуррентные соотношения и конечные суммы. Решение рекуррентного соотношения вида .

Биномиальные коэффициенты. Рекуррентное соотношение для биномиальных коэффициентов. Треугольник Паскаля. Явная формула для биномиальных коэффициентов. Бином Ньютона. Комбинаторная интерпретация биномиальных коэффициентов. Полиномиальная формула. Метод траекторий.

Числа Стирлинга первого и второго рода, их свойства. Теорема обращения.


5

Производящие функции

Производящие функции. Применение производящих функций для решения рекуррентных соотношений (явная формула для чисел Фибоначчи). Алгебра Коши. Применение производящих функций для комбинаторных подсчетов. Применение производящих функций для вычисления комбинаторных сумм.

Правильно построенные скобочные структуры. Последовательность Каталана. Явная формула для чисел Каталана. Примеры задач, приводящих к числам Каталана.


6

Элементы теории графов

Основные понятия теории графов. Способы задания графа. Изоморфизм графов. Понятие инварианта графа. Примеры простейших инвариантов графа. Степень вершины графа. Лемма о рукопожатиях и ее следствие.

Связные графы. Подграфы. Компоненты связности. Число компонент связности у графа, имеющего p вершин и q ребер. Необходимое условие связности графа. Достаточное условие связности графа

Деревья. Характеризационная теорема. Теорема Кэли о числе деревьев, заданных на фиксированном n-множестве. Соответствие Прюфера. Число деревьев с фиксированным числом висячих вершин.

Эйлеровы графы. Критерий эйлеровости. Полуэйлеровы графы. Критерий полуэйлеровости. Уникурсальные кривые. Гамильтоновы графы. Теорема Дирака.

Укладка графа в топологическое пространство. Планарные и плоские графы. Теорема Эйлера для связных плоских графов, ее следствия. Понятие эйлеровой характеристики. Непланарность графов и . Теорема Понтрягина – Куратовского (без док-ва)..

Раскраска вершин графа. Хроматическое число и хроматический многочлен графа. Двудольные графы. Теорема Кенига. Понятие карты. Раскрашивание карт. Теорема о четырех красках (без док-ва). Неравенство Хивуда. Теорема Вагнера. Гипотеза Хадвигера.

Теорема Турана. Числа Рамсея. Теорема Эрдеша – Шекереса. Существование чисел Рамсея (теорема Рамсея).




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



  1. Арифметика чисел Фибоначчи.

  2. Комбинаторика чисел Каталана.

  3. Обобщения треугольника Паскаля.

  4. Алгоритм Евклида и его модификации.

  5. Алгоритм Евклида и числа Фибоначчи; теорема Ламэ.

  6. Суммы и рекуррентности; числа Бернулли.

  7. Рекуррентные форулы в задачах на разбиения.

  8. Производящие функции и разбиения чисел.

  9. Графы и метрики.

  10. Алгоритмы на графах.



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

__экзамен__


ПЕРЕЧЕНЬ ВОПРОСОВ К ЭКЗАМЕНУ



  1. Основные понятия теории графов. Степень вершины графа, теорема о сумме степеней вершин графа.



  1. Связные графы. Компоненты связности.

  2. Двудольные графы. Теорема Кенига.

  3. Способы представления графов. Матрицы смежности и инциндентности. Число различных графов на n фиксированных вершинах. Изоморфные графы. Простейшие инварианты графа

  4. Планарные и плоские. Теорема Эйлера. Теорема Понтрягина-Куратовского.

  5. Раскраска планарных графов. Хроматическое число и хроматический многочлен графа. Теорема о четырех красках.

  6. Эйлеровы графы. Критерий эйлеровости. Полуэйлеровы графы. Критерий полуэйлеровости. Уникурсальные кривые.

  7. Гамильтоновы графы. Теорема Дирака..

  8. Треугольник Паскаля и биномиальные коэффициенты.

  9. Числа Фибоначчи и их свойства.

  10. Производящие функции и решение рекуррентных соотношений.

  11. Некоторые методы суммирования.

  12. Неравенство Хивуда. Теорема Вагнера. Гипотеза Хадвигера.

  13. Числа Рамсея. Теорема Эрдеша-Шекереса. Теорема Рамсея.



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


  1. Основная литература:




  • Виленкин Н.Я, Виленкин А.Н., Виленкин П.А. Комбинаторика. М.: МЦНМО, 2006

  • Дистель Р. Теория графов, Новосибирск, 2002.

  • Ф. Харари Теория графов, М.: Изд-во Мир, 1973.

  • Жданов С.А., Матросов В.Л., Стеценко В.А. Сборник задач по дискретной математике.




  1. Дополнительная литература:




  • Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.

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

  • Сачков В.И. Комбинаторные методы дискретной математики. М.: Наука, 1977.

  • Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.

  • Матросов В.Л., Стеценко В.А. Лекции по дискретной математике. М.: МПГУ, 1997.

  • Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. М.: Изд-во Наука, 1977.



Похожие:

Дискретная математика iconАннотация рабочей программы «Дискретная математика»
Дискретная математика принадлежит Базовой части Профессионального цикла дисциплин ( Б. 1) подготовки студентов направления 010400...
Дискретная математика iconПензенский государственный университет факультет вычислительной техники Кафедра "Дискретная математика" Дискретная математика
На основе Государственного образовательного стандарта высшего профессионального образования и предыдущих рабочих программ
Дискретная математика iconПензенский государственный университет институт информатики и вычислительной техники Кафедра "Дискретная математика" Дискретная математика
На основе Государственного образовательного стандарта высшего профессионального образования и предыдущих рабочих программ
Дискретная математика iconПензенский государственный университет институт информатики и вычислительной техники Кафедра "Дискретная математика" Дискретная математика
На основе Государственного образовательного стандарта высшего профессионального образования и предыдущих рабочих программ
Дискретная математика iconПрограмма дисциплины дискретная математика для направления 080500. 62 «Бизнес-информатика»
Требования к студентам: Изучение курса «Дискретная математика» не требует предварительных знаний, выходящих за пределы программ общеобразовательной...
Дискретная математика iconДжеймс А. Дискретная математика и комбинаторика [Текст] / Джеймс А. Андерсон
Индивидуальное домашнее задание по дисциплине «Дискретная математика» для студентов групп ас – 08, аи – 08, пм – 08, ук – 08, см...
Дискретная математика iconРабочая программа учебной дисциплины «Дискретная математика»
Дисциплина «Дискретная математика» входит в базовую часть (Б2) математического и естественнонаучного цикла. Для изучения дисциплины...
Дискретная математика iconПрограмма дисциплины Дискретная математика для социологов
Курс «Дискретная математика для социологов» предназначен для студентов 1-го курса бакалавриата факультета социологии. Он является...
Дискретная математика iconПримерная программа наименование дисциплины «Дискретная математика» Рекомендуется для направлений подготовки
Изучение дисциплины "Дискретная математика" должно воспитывать у слушателей творческое мышление, навыки самостоятельного решения...
Дискретная математика iconАннотация рабочей программы дисциплины Дискретная математика
Дисциплина ( Б. 2) «Дискретная математика» принадлежит базовой части математического и естественнонаучного цикла дисциплин подготовки...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница