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




НазваниеДискретная математика
Дата03.02.2016
Размер8,4 Kb.
ТипРеферат
Дискретная математика

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


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


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

Общая трудоемкость дисциплины составляет 4 зачетных единицы, 144 часа, в том числе 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. Алгоритмы на графах.



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

______экзамен_______


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



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

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

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

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

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

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

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

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

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

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

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

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

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

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



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


а) основная литература:


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

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

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

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


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


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

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

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

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

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

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



Похожие:

Дискретная математика iconПрограмма дисциплины Дискретная математика для социологов
Курс «Дискретная математика для социологов» предназначен для студентов 1-го курса бакалавриата факультета социологии. Он является...
Дискретная математика iconРабочая программа по дисциплине «дискретная математика» для специальности 010200 Прикладная математика и информатика Форма обучения: очная
Рабочая программа составлена на основании гос впо 010200 – Прикладная математика и информатика, утвержденного в 2000 г
Дискретная математика iconПрограмма наименование дисциплины: Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках
Наименование дисциплины: Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках
Дискретная математика iconДискретная математика
Автор: д-р физ мат наук, профессор, зав кафедрой компьютерной безопасности и математических методов обработки информации Дурнев В....
Дискретная математика iconРабочая программа учебной дисциплины опд. Ф «Дискретная математика»
Соответствие гос (для федеральных дисциплин) или соответствия требованиям ооп (для региональных и вузовских) указание на недостаточно...
Дискретная математика iconПрограмма-минимум кандидатского экзамена по специальности 01. 01. 09 «Дискретная математика и математическая кибернетика» по физико-математическим наукам
...
Дискретная математика iconРабочая программа учебной дисциплины ен. Ф «Дискретная математика»
Рабочая программа учебной дисциплины обсуждена на заседании кафедры математики и математического моделирования факультета информационных...
Дискретная математика iconГоу впо «удмуртский государственный университет» Математический факультет Кафедра алгебры и топологии
Курс лекций и лабораторных работ строится как непосредственное продолжение основных понятий курсов «Дискретная математика», «Основы...
Дискретная математика iconПрограмма лекционного курса "Дискретная математика"
Понятие функции алгебры логики. Количество функций алгебры логики от n переменных. Элементарные функции алгебры логики
Дискретная математика icon«Дифференциальные уравнения и дискретная математика» 2012-2013 уч год
На зачёте проверяются умения и навыки решения задач. Ниже приведён список тем задач, которых мы касались на семинарах и лекциях....
Разместите кнопку на своём сайте:
Библиотека


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