Комбинаторика

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

КУРС ЛЕКЦИЙ

ЛИТЕРАТУРА

1. Н. Нефедова, В. А. Осипов Курс дискретной математики. 1992

2. С. В. Яблонский Введение в дискретную математику. 1979

3. О. П. Кузнецов, Г. М. Адельсон-Вельский Дискретная математика для инженеров. 1980

4. Л. М. Лихтарников, Т. Г. Сукачева Математическая логика. 1998

5. В. Г. Карпов, В. А. Мощенский Математическая логика и дискретная математика. 1977

6. И. Б. Сироджа. Примеры и задачи комбинаторики и теории графов. 1986

7. О. Оре Теория графов. 1980

8. А. Е. Соловьев, В. С. Галкин Основы дискретной математики.

9. Ф. А. Новиков Дискретная математика для программистов.

(2 семестр)

(для студентов специальности «Прикладная математика», «Компьютерные системы и сети»)

У Т В Е Р Ж Д Е Н О

на заседании кафедры

прикладной математики.

Протокол № 2 от 27. 09. 07.

Луганск 2008

УДК 62-501. 7

Курс лекций по дискретной математике (для студентов направления «Прикладная математика», а также «Компьютерные системы и сети») / Сост.: В. В. Барабаш, Е. Ю. Чалая, Луганск: изд. ВНУ им. В. Даля, 2008 - 88 с.

Приведены теоретические материалы, необходимые для изучения дисциплины «Дискретная математика». Рассмотрены основные разделы 2 семестра: комбинаторика, теория графов, теория конечных автоматов, элементы теории алгоритмов. В разделе «Комбинаторика» указаны основные комбинаторные правила и формулы, связь между числовой последовательностью, производящей функцией и рекуррентным соотношением, их использование в решении задач. В разделе «Теория графов» рассмотрены основные алгоритмические задачи теории графов, вопросы, связанные с различными видами циклов на графах. В разделе «Теория конечных автоматов» приведен алгоритм минимизации автомата, рассмотрены алгоритмические задачи, решаемые с применением машины Тьюринга. Приведены задачи для самостоятельной работы студентов.

Составители: Барабаш В. В., доцент.

Чалая Е. Ю., ассистент.

Отв. за выпуск Грибанов В. М., профессор.

Рецензент Ермаков А. И., доцент.

Комбинаторика – это раздел математики, в котором рассматриваются вопросы о том, сколько различных комбинаций можно составить из заданных объектов, подчиненных некоторым условиям.

Комбинаторика возникла в XVI веке. Первые задачи комбинаторики касались азартных игр – сколькими способами можно получить данное число очков, бросая две или три кости, или сколькими способами можно вытянуть двух королей из карточной колоды и т.д. Подобные вопросы и явились движущей силой развития комбинаторики и теории вероятностей. Яркий свет в комбинаторике оставили Паскаль, Я. Бернулли, Лейбниц, Эйлер и другие математики. В ХХ веке, в связи с созданием ЭВМ и повышением интереса к дискретной математике комбинаторика переживает бурный рост. Комбинаторные задачи возникают в анализе и алгебре, геометрии и топологии, в различных разделах математики и в приложениях.

Дата добавления: 2014-01-04