МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ

имени ВЛАДИМИРА ДАЛЯ

Барабаш В. В.

Чалая Е. Ю.

Курс лекций

По дискретной математике

(2 Семестр)

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

У Т В Е Р Ж Д Е Н О

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

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

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

Луганск 2008

УДК 62-501. 7

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

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

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

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

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

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

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

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

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

§1. Правила комбинаторики. Основные комбинаторные формулы.

Существует два общих правила комбинаторики: правило сложения и правило умножения.

Правило умножения:

Пусть составляются всевозможные строки длины. Пусть первая компонента строки может быть выбрана числом способов, равным. После того, как первая компонента выбрана и независимо от того, как она выбрана, вторая компонента выбирается числом способов, равным. Далее аналогично. Последняя компонента выбирается числом способов, равным. Тогда количество всех построенных строк равно произведению:.

Правило сложения:

Если некоторый элемент можно выбратьразличными способами, а другой элементвыбираетсяспособами, то объект «» можно выбратьспособами.

Замечание: Правило сложения, как и правило умножения, можно обобщить на случай слагаемых.

Можно также отметить, что знак умножения в соответствующем правиле соответствует союзу «и» русского языка. А знак сложения – союзу «или». Причём, союз «или» применяется во взаимоисключающем смысле.

Для дальнейшего изложения необходимо ввести следующее вспомогательное понятие.

Определение 1: Пусть дано конечное множество изэлементов. Всякий набор изэлементов данного множества (при этом элементы в наборе могут и повторяться) будем называть-расстановками.

Через понятие расстановки вводятся основные определения комбинаторики: сочетания, размещения и перестановки. При этом каждое из этих понятий может быть с повторениями и без повторений.