рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ - раздел Математика, Министерство Образования И Науки Украины Восточноукраинский Национал...

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

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

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

 

 

Барабаш В. В.

Чалая Е. Ю.

 

КУРС ЛЕКЦИЙ

 

 

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

(для студентов специальности «Прикладная математика», «Компьютерные системы и сети»)   У Т В Е Р Ж Д Е Н О

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

 

 

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

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

 

Правила комбинаторики.

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

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

Размещения.

1) Размещения без повторений. Определение 2: Пусть имеется различных предметов. Расстановки из элементов по… В данном определении существенной является следующая позиция: две расстановки различны, если они отличаются хотя бы…

.

Доказать теорему можно индукцией по числу .

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

Количество комбинаций в секретном замке, число телефонных номеров, число автомобильных номеров, код Морзе, генетический код.

Разгадка генетического кода – крупнейшее достижение биологии ХХ века. Информация записана в гигантских молекулах ДНК (дезоксирибонуклеиновой кислоты). Различные молекулы ДНК отличаются порядком 4-х азотистых оснований. Эти основания определяют порядок построения белков организма из двух десятков аминокислот, причём каждая аминокислота зафиксирована кодом из 3-х азотистых оснований.

В одной хромосоме содержится несколько десятков миллионов азотистых оснований. Число различных комбинаций, в которых они могут идти друг за другом столь велико, что ничтожной доли этих комбинаций хватит для зашифровки всего многообразия живых организмов за время существования жизни на земле, оно равно , где – число оснований в хромосоме.

 

Перестановки.

1) Перестановки без повторений. Определение 3: Пусть - конечное множество из элементов. Перестановками из… Согласно определению:

Сочетания.

1) Сочетания без повторений. Определение 3: Сочетания из элементов по элементов () – это расстановки,… Теорема 4: Число сочетаний находится по следующей формуле:

Свойства сочетаний. Бином Ньютона.

Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых… 1. . 2. .

Определение 1: Коэффициенты бинома Ньютона называются биномиальными коэффициентами.

  1 n = 0 1 1 n = 1

Числа Фибоначчи.

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

При решении многих комбинаторных задач применяют метод сведения данной задачи к задаче касающегося меньшего числа элементов. Например, можно вывести… . Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа.

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

Метод рекуррентных соотношений позволяет решать многие комбинаторные задачи. Но в ряде случаев рекуррентные соотношения трудно составить, а иногда… Здесь необходимо знать: понятие ряда, сумма ряда, степенной ряд, сходимость… Определение 1: Пусть дана числовая последовательность: . Образуем степенной ряд с этими коэффициентами: . Если этот…

Теория графов.

 

Введение

Зарождение теории графов в XVIII веке было связано с математическими головоломками, и довольно долго учение о графах рассматривалось как несерьезная тема, прикладное значение которой было связано с играми и развлечениями. В этом отношении судьба теории графов схожа с судьбой теории вероятностей, которая также первоначально рассматривалась в связи с ее применениями к азартным играм.

В начале XX века графы стали применяться в топологии, и даже в первой половине XX века теория графов считалась главой топологии, этого современного раздела математики. Позже выявились связи теории графов с другими разделами современной математики (например, алгебра, комбинаторика и др.), а различные приложения теории графов к широкому кругу проблем сегодня даже трудно перечислить: это, например, исследования операций и управления, задачи экономики, теории информации, социологии и т.д.

Современная теория графов достигла достаточно высокого уровня формализации и удовлетворяет требованиям математической строгости.

Настоящая глава посвящена первоначальному знакомству с некоторыми направлениями в теории графов.

 

 

Основные понятия и определения теории графов.

 

Прежде чем приступить к точным определениям, поясним их наглядно. Любое конечное множество точек (вершин), некоторые из которых соединены попарно стрелками (в теории графов эти стрелки называются дугами), можно рассматривать как граф (рис. 1). Например, граф может изображать сеть улиц в городе, вершины графа — перекрестки, стрелками обозначены улицы с разрешенным направлением движения. (Улицы могут быть с односторонним и двусторонним движением.) Отметим здесь два момента. Во-первых, не любой граф можно изобразить на плоскости так, чтобы дуги пересекались только в вершинах (рис. 2). Во-вторых, две вершины могут быть соединены несколькими дугами, идущими в одном направлении (например, таким свойством может обладать схема железных дорог). Такие дуги будем называть кратными, а граф, содержащий кратные дуги, часто называют мультиграфом (рис. 3). Если подчеркивается, что в данном графе нет кратных дуг, то он называется графом без кратных дуг.

Рис. 2
Рис. 1

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

 

Рис. 3

Покажем, каким образом введенное определение формализует понятие графа, интуитивно описанное выше.

Дугу (стрелку), соединяющую вершины , , мы обозначим через , где - начало дуги, - ее конец, а - номер дуги. Например, граф, изображенный на рис. 1, может быть аналитически описан соотношениями:

. (*)

Отметим, что при нумерации дуг не требуется, чтобы были использованы все номера, начиная с единицы и до числа дуг между данными вершинами. Например, граф на рис. 1 может быть описан так:

. (**)

Графы, заданные соотношениями (*) и (**), будем считать различными. Для формализации «идентичности» этих графов вводится ниже понятие изоморфизма.

Как уже сказано в определении 1, элементы множества называются дугами.

Определение 2: Дуга вида называется петлей.

На рис. 3 присутствует петля . Несколько сложнее понятие ребра. Иногда на графе в какой-либо прикладной задаче нет необходимости задавать направление связи между вершинами и . При изображении в этом случае связь рисуют без стрелки и говорят о ребре, соединяющем и (рис. 4, а). Будем считать такие ребра объединением дуг и с одинаковыми номерами.

Определение 3:Ребром называется подмножество вида .

Иллюстрацией может служить рис. 4, б. Видно, что если на графе две вершины связываются дугами с противоположными направлениями, то эти две дуги могут быть заменены одним ребром.

Определение 3: Граф называется симметрическим, если для любых номеров из того, что дуга следует, что дуга .

Рис. 4

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

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

Определение 4: Полностью неориентированным графом называется пара объектов , где - конечное множество вершин, а - конечное подмножество прямого произведения , состоящее из элементов вида , где содержит ровно два элемента.

У полностью неориентированных графов все дуги – есть ребра (нет направляющих стрелок ни на одной дуге).

Дадим формальное определение графа без кратных дуг.

Определение 5:Графом без кратных дуг называется граф , удовлетворяющий условию: для любых существует самое большее один элемент такой, что .

Это означает, что каждая дуга, соединяющая ребра, встречается только один раз. Для описания графов без кратных дуг можно воспользоваться упрощающей символикой - дугу графа обозначать . Таким образом, можно дать другое определение графа без кратных дуг, эквивалентное приведенному выше.

Определение 5*: Графом без кратных дуг называется пара объектов , где - конечное множество, а .

Покажем, что граф без кратных дуг определяет некоторое отображение (которое также будем обозначать буквой ) . Каждому элементу сопоставим подмножество следующим образом. Считаем, что тогда и только тогда, когда . Верно и обратное: любое отображение определяет граф. Можно дать ещё одно эквивалентное определение.

Определение 5**: Графом без кратных дуг называется пара объектов , где — конечное множество, а — отображение.

В дальнейшем будут рассматриваться и полностью неориентированные графы без кратных ребер. Ребра такого графа будем часто обозначать или, эквивалентно и говорить о неупорядоченной паре вершин .

Определение 6: Дугу и вершину назовем инцидентными, если или (вершина является либо первой, либо второй проекцией дуги ). Ребро и вершину назовем инцидентными, если инцидентны дуга и . Дугу , такую, что , назовем исходящей из , а если , то входящей в . Две вершины и называются смежными, если существует дуга, соединяющая либо с , либо с .

Определение 7:Путём в графе называется такая конечная последовательность дуг , , что . Если, кроме того, , то путь называется контуром. Путь называется простым, если из неравенства следует , и элементарным, если последовательность вершин не содержит совпадающих элементов, кроме, может быть, крайних.

Интерпретация пути (и контура) в графе очевидна. Путь является простым, если при движении вдоль него одна и та же дуга никогда не приходится дважды, и элементарным, если при этом никакая вершина не встречается дважды.

Пусть теперь - симметрический граф.

Определение 8:Цепью в симметрическом графе называется такая последовательность ,ребер графа , что существует путь в , удовлетворяющий условию для . Цепь называется циклом, если соответствующий путь есть контур. Цепь называется простой (элементарной), если соответствующий путь простой (элементарный).

Очевидно, что для любой цепи , существует ровно один путь , такой, что . Это доказывает корректность определений простой и элементарной цепи.

Определение 9: Граф называется суграфом графа , если . Граф называется подграфом графа , если . Наконец, граф называется частью графа , если .

Таким образом, суграф получается из графа удалением некоторого числа дуг (с сохранением вершин). Подграф получается из графа удалением некоторого числа вершин вместе со всеми дугами, инцидентными удаленной вершине. Часть графа получается из графа применением конечного числа обеих описанных операций.

Определение 10: Наименьший симметрический граф такой, что является суграфом , называется симметризованным графом графа .

Определение 11: Граф называется сильно связным, если для любых двух вершин ,существует путь такой, что .

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

Из этих определений прямо следует, что понятия связности и сильной связности совпадают для симметрических графов.

Определение 13: Подграф графа называется компонентой связности графа , если а) связен, б) обладает свойством максимальности, т. е. если - некоторый другой связный подграф и , то графы и совпадают.

Определение 14: Будем говорить, что ребро является перешейком в симметрическом графе , если при удалении этого ребра количество компонент связности графа увеличивается на единицу.

Очевидно, что ребро является перешейком тогда и только тогда, когда не существует простого цикла, содержащего это ребро.

Определение 15: Полустепенью исхода вершины называется число исходящих из нее дуг. Полустепенью захода вершины называется число входящих в нее дуг. Степенью вершины называется число .

Замечание: Иногда в симметрических графах степенью вершины будет называться число инцидентных ей ребер. Из контекста всегда будет ясно значение числа в каждом случае.

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

Определение 17: Пусть — граф, . Матрицей смежности называется матрица , в которой элемент равен количеству дуг из вида .

Определение 18: Графы и называются изоморфными, если существуют взаимно однозначные отображения , такие, что .

Пример. Графы и , изображенные на рис. 5, изоморфны; их изоморфизм определяется подстановкой второго порядка:

.

У изоморфных графов матрицы смежности очень похожи. Их можно получить одну из другой с помощью конечного числа перестановок строк и столбцов.

 

 

Задачи, послужившие основой теории графов.

 

Задача о кенигсбергских мостах.

На рис. 6 схематически изображена карта города Кенигсберга, относящаяся к XVIII в. Город был расположен на берегах и двух островах реки Преголи. Острова между собой и с берегами были связаны семью мостами. Жители города любили размышлять над проблемой: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту только один раз?

Полностью неориентированный граф , отвечающий задаче, представлен на рис. 7. Вершины соответствуют правому и левому берегам реки, вершины - островам, ребра графа — мостам. На языке графов, задача формулируется следующим образом: существует ли в графе простой цикл, содержащий все ребра (эйлеров цикл).

Л. Эйлер сформулировал и доказал необходимое и достаточное условие того, чтобы в произвольном полностью неориентированном связном графе существовал эйлеров цикл.

Теорема 1: Эйлеров цикл в симметрическом связном графе существует тогда и только тогда, когда степени всех его вершин — четные числа.

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

Достаточность можно доказать индукцией по числу ребер графа. При числе ребер, равном двум, как нетрудно видеть, теорема справедлива. Пусть утверждение теоремы верно для всех графов с числом ребер, непревосходящем числа . Для графа с числом ребер рассмотрим произвольный простой цикл. Хотя бы один такой цикл обязательно существует для графов с четными степенями вершин. Если в графе не имеется ни одного простого цикла, то любое его ребро — перешеек. Удаляя какое-либо ребро графа, инцидентное, скажем, вершинам и , разбиваем граф на две компоненты связности. Каждое ребро в этих компонентах связности — также перешеек. После удаления ребра степени вершин и стали нечетными. Склеим компоненты связности по вершинам , и. Новая вершина, как и все остальные, в полученном связном графе имеет четную степень. Число ребер в получившемся графе равно . По предположению индукции в нем существует эйлеров цикл. Но это противоречит предположению, что в каждой компоненте связности все ребра — перешейки. Если рассматриваемый простой цикл содержит все ребра, то теорема доказана. В противном случае найдутся вершины , принадлежащие парам смежных ребер цикла, такие, что из каждой исходит по крайней мере одно ребро, не входящее в построенный цикл. В силу условия теоремы число ребер, исходящих из вершины и не принадлежащих циклу , обязательно четно.

Например, в графе, изображенном на рис. 8,:имеем:

где есть вершины , , .

Рассмотрим подграф графа , построенный с помощью ребер, не входящих в цикл . Подграф состоит, быть может, из нескольких компонент связности. Степени всех вершин — четные числа. Каждая компонента связности подграфа удовлетворяет предположению индукции, так как содержит меньше, чем ребро. Следовательно, в каждой компоненте существует; эйлеров цикл, содержащий, по крайней мере, одну из вершин . Присоединяя к циклу эйлеровы циклы подграфов , получаем эйлеров цикл графа .

 

Задача о четырех красках.

Формулировка этой задачи чрезвычайно проста и не соответствует всей глубине и сложности проблемы: можно ли на любой политико-административной карте раскрасить страны так, чтобы никакие две страны, имеющие общую границу, не были раскрашены одинаковой краской, и чтобы были использованы всего четыре краски? Уточним, что если две страны граничат по точке, то они не считаются имеющими общую границу.

В терминах теории графов задача может быть поставлена следующим образом. Дан произвольный полностью неориентированный плоский граф . Можно ли каждую вершину графа раскрасить с помощью одной из четырех красок так, чтобы никакие две смежные вершины (вершины, соединенные хотя бы одним ребром) не были раскрашены в один цвет. Конечно, нетрудно привести примеры графов, которые раскрашиваются в одну, две, три или четыре краски. В §6 будет доказана теорема о том, что любой плоский граф может быть раскрашен с помощью пяти красок. Тем не менее, проблема четырех красок до сих пор не решена. Удалось лишь доказать, что такую раскраску можно осуществить для всех плоских графов с числом вершин, не превосходящим 38.

Задача эта приобрела известность с 1878 г., когда английский математик Кэли привел ее формулировку на заседании английского королевского научного общества; добавив, что не мог ее решить, хотя и размышлял над ней длительное время. С тех пор многие выдающиеся математики пробовали свои силы в решении этой задачи. Удивительно, что для графов, нарисованных на торе, листе Мёбиуса или бутылке Клейна, соответствующая задача решена, т. е. установлено необходимое и достаточное число красок для раскрашивания.

 

 

Алгоритмические задачи.

 

Задачи о кратчайших путях.

1. Путь с наименьшим числом дуг. Пусть задан произвольный граф . Требуется построить такой путь, соединяющий две заданные вершины и , который содержит наименьшее число дуг (путь кратчайшей длины, если считать, что длины всех дуг одинаковы).

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

Алгоритм решения.

2°. Если и , то присвоить каждой такой вершине метку 1. 3°. Пусть — множество вершин, имеющих метку . Вершинам множества при присвоить… 4°. Процесс присвоения вершинам меток прекратить, как только вершина получит некоторую метку .

Обоснование алгоритма.

Для этого заметим, что на любом этапе метки при , а метка , что можно доказать по индукции. В самом деле, при первом применении правила 3° будет… Предположим, что после того, как применено правило 3° раз , станет… Ясно, что при каждом изменении метка вершины графа уменьшается на положительную величину, не меньшую, чем минимальная…

Алгоритм построения Эйлерова цикла.

Как фактически построить его? Оказывается, что достаточно выполнять следующие правила. Алгоритм. 1°. Выбрать произвольно некоторую вершину .

Обоснование алгоритма.

Пусть ребер, инцидентных вершине — нечетное число, большее единицы. Докажем, что среди них хотя бы одно ребро не является перешейком. Допустим… Рассмотрим компоненту связности , содержащую вершину (и не содержащую вершину… Итак, наше допущение ведет к противоречию. Более того, мы убедились, что среди ребер, инцидентных вершине в графе,…

Потоки на транспортных сетях.

Определение 1: Транспортная сеть есть совокупность двух объектов: 1. Связного графа , обладающего свойствами: 1°) в графе отсутствуют петли,

Алгоритм Форда - Фалкерсона для нахождения потока наибольшей величины.

2°. Построить произвольный поток на транспортной сети (например, положить ). 3°. Просмотреть пути, соединяющие вход сети c выходом . Если поток полный, то…

Обоснование алгоритма.

Процесс присвоения меток в силу того, что каждый раз получают метку еще неотмеченные вершины, конечен. И, наконец, в п. 5° поток обладает большей… Получаемая по правилу 3° функция — поток. Это непосредственно следует из того,… Пусть процесс, описанный в п. 4°б), приводит к тому, что вершина не получает метки. Обозначим через множество…

Теорема 1: Для заданной транспортной сети величина наибольшего потока равна наименьшей пропускной способности разрезов, т. е. .

В качестве примера применения алгоритма Форда - Фалкерсона рассмотрим транспортную сеть и полный поток , для которого (рис. 11). Применяя правила 4°…   3. Задача о назначении на должность (комбинаторная прикладная задача).

Цикломатическое число графа. Деревья.

Во многих прикладных задачах существенны свойства графов, связанные с существованием в графе замкнутых цепей (циклов). К рассмотрению этих вопросов… Прежде чем рассматривать алгоритмические задачи, связанные с циклами, введем… Определение 1: Пусть граф имеет компонент связности. Цикломатическим числом графа называется число где — число вершин…

Эйлерова характеристика. Плоские графы.

Определение 1: Пусть задан набор отрезков гладких кривых на плоскости, причем выполнны следующие условия: 1) отрезки и не имеют общих точек, кроме, быть может, концевых (в частности ,… 2) граф изоморфен , где граф определен равенством: . Здесь — это множество концевых точек отрезков на плоскости, .

Теорема 2: Графы и , где множество состоит из элементов вида , не допускают плоской реализации.

Пусть — число ребер, ограничивающих грань с номером ; имеем и , то есть . Полученное противоречие доказывает первую часть теоремы. Допустим, что допускает плоскую реализацию. Тогда из теоремы 1 имеем… Пусть имеют тот же смысл, что и раньше. Очевидно, и поэтому выполнено неравенство: .

Теорема 3: (Понтрягин - Куратовский). Для того чтобы граф был плоским, необходимо и достаточно, чтобы он не содержал в качестве подграфов графы или из условия теоремы 2.

Доказательство достаточности в этой теореме здесь не приводится. Отметим, что аналогичных критериев реализуемости графа уже для тора не найдено. Если произвольный граф не допускает плоской реализации, то он, возможно, допускает реализацию пространственную, т. е. может быть изображён без самопересечений ребер на пространственном объекте (шаре, торе и др.).

 

 

Теорема о пяти красках.

 

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

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

 

Оценка хроматического числа плоского графа.

Вопрос о том, достаточно ли для любой карты четырех красок, до сих пор не решен. Это так называемая проблема четырех цветов. Примеры плоских графов,… Теорема 1: Любой плоский граф 5-хроматичен. Прежде чем доказывать теорему 1, докажем лемму, которая имеет чисто технический характер и будет использоваться при…

Графы правильных многогранников.

Теория графов позволяет решать задачи из традиционных разделов математики, например, исследовать некоторые свойства правильных многогранников. При… Правильные многогранники (платоновы тела) – это выпуклые многогранники,… Вместо объёмных изображений правильных многогранников можно использовать их плоские изображения (графы). Графы…

Теория конечных автоматов

Введение.

Теория конечных автоматов исследует тематические модели, приближенно отражающие физические или абстрактные явления, причем эти модели могут быть из области психологии, административного управления, связи, лингвистики, теории ЭВМ и т.д. С помощью конечных автоматов можно исследовать нервную систему животных или человека и проектировать ЭВМ.

Универсальная ЭВМ состоит из 5 устройств:

1) устройство ввода;

2) устройство памяти;

3) арифметическое устройство;

4) устройство управления;

5) устройство вывода.

Последовательность действий машины определяется программой, которая выполняется последовательно. Сама программа может предусматривать пропуск или повторение информации, хранящейся в памяти, т.е. от внутреннего состояния машины.

ЭВМ бывают цифровые и аналоговые. Мы здесь рассматриваем цифровые. Все сигналы в такой машине двузначны, т. е. принимают значения из множества .

Материальные носители и преобразования сигналов – конечны. Множество состояний любой машины также конечно.

 

 

Определение автомата Мили.

Автомат Мура.

Определение: Конечным автоматом называется набор из 5 объектов , где: - входной алфавит; ­ выходной алфавит;

Покрытие и эквивалентность.

Морфизмы.

Пусть - конечный автомат. Тогда по любой входной строке длины r и по любому начальному состоянию однозначно определяется строка длины r внутренних… Пример. Автомат задан диаграммой:

Определение 4: Морфизмом называется такое отображение , что и и . Если сюрьективно, то морфизм называется эпиморфизмом. Если - биекция, то морфизм называется изоморфизмом.

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

Доказательство:Доказательство можно провести индукцией по числу с индуктивным шагом:

;

.

Следствие: Любой эпиморфизм определяет покрытие автомата автоматом . Изоморфизм автоматов и с общим входным и выходным алфавитами есть биекция , такая, что для всякого начального состояния и всякой входной строки автоматы и выдают одну и ту же выходную строку, проходя через соответствующие промежуточные состояния.

Пример. Автоматы, представленные следующими ориентированными графами, изоморфны.

 

Эквивалентные состояния автоматов.

В этом параграфе мы решим следующую задачу: по данному описанию автомата построить новый автомат , который покрывает (возможно, эквивалентен ) и… Существует эффективный метод решения этой задачи, если функции всюду… Определение 1: Состояния и называются - эквивалентными, если для всякой входной строки длины имеем: . В этом случае…

Теорема 1: Если , то либо , либо для подходящей строки имеем .

Теорема 2: Если , но для всех , то для подходящего элемента . Эту теорему можно переформулировать так: если , то для подходящего элемента… Если мы уже определили , то состоит из и таких упорядоченных пар , что для некоторого имеем: . В общем случае нужно…

Машина Тьюринга.

Понятие конечного автомата возникло из близкого понятия, введенного в 1936 г. логиком Тьюрингом. Тьюринг рассмотрел гипотетическую машину, имеющую… Особенности машины Тьюринга, отличающие ее от конечного автомата, состоят в… 1) лента машины Тьюринга бесконечна;

Не полностью описанные автоматы.

До сих пор мы рассматривали полностью описанные автоматы. Практически функции и обычно бывают лишь частично определены. Системы обычно проектируются… Сначала казалось, что следует как-нибудь заполнить безразличные позиции в… Однако для многих не полностью описанных автоматов процедура такого вида не приводит к минимизации.

Алгоритмы и рекурсивные функции.

 

Введение.

Уже в математике древнего мира появились вычислительные процессы чисто механического характера, с помощью которых, действуя по инструкциям, можно было из заданных величин получать искомые. Такие правила, инструкции в математике стали называть алгоритмами. Примерами алгоритмов являются, например, правила сложения, вычитания, умножения и деления многозначных натуральных чисел, записанных в десятичной системе исчисления, алгоритм Евклида для нахождения наибольшего общего делителя натуральных чисел, решение системы линейных уравнений методом последовательного исключения неизвестных, отыскание целых корней многочленов с целыми коэффициентами и т.д.

В наше время отмечают следующие характерные черты алгоритмов:

1) Дискретность алгоритма, т.е. вычисления согласно алгоритму производят по шагам, с четким предписанием: 1)…, 2)…, и т.д. (по программе).

2) Детерминированность алгоритма, т.е. величины, получаемые в процессе вычисления на любом последующем шаге, однозначно определяются величинами, полученными на предшествующем шаге.

3) Элементарность шагов алгоритма, т.е. правила, инструкции, по которым выполняется каждый шаг, должны быть четкими, понятными, не допускающие неопределенности.

4) Направленность алгоритма, т.е. должно быть указано, что считается результатом алгоритма и в том случае, если указанный вычислительный процесс не дает результата.

5) Массовость алгоритма, т.е. возможность применения для решения бесконечного числа однотипных задач.

Отмеченные характерные черты алгоритма, конечно, не дают математически строгого определения алгоритма, т.к. точный смысл ряда терминов, встречающихся в них, не установлен.

И хотя понятие алгоритма в математике возникло очень давно, и у математиков не возникало споров относительно того, является ли какая-то описанная вычислительная процедура алгоритмом или нет, точного определения алгоритма не существовало до середины тридцатых годов ХХ века. Дело в том, что для построения конкретного алгоритма, точное определение алгоритма не обязательно, но для доказательства того, что для решения какой-то задачи не существует алгоритма, необходимо строгое определение его.

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

На этом пути, продолжая работы Д. Гильберта, К. Геделя, Черч и Клини дали строгое определение рекурсивной и частично рекурсивной функции, которые являются формализацией интуитивного понятия алгоритма. С помощью этих понятий Черч доказал алгоритмическую неразрешимость проблемы тождественной истинности для формул исчисления предикатов первой степени.

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

 

 

Основные понятия и определения.

 

Алфавит, слова.

Введем понятие ленты, разделенной на равные участки, называемые ячейками или клетками. Будем считать ленту конечной в любой данный момент, но неограниченно надстраиваемой в обе стороны, так, что у каждой ячейки есть соседние справа и слева. Одно из возможных состояний ячеек будем называть исходным. Ячейки, находящиеся в этом состоянии, будем называть пустыми.

Произвольное конечное множество букв назовем алфавитом. Конечная последовательность ячеек, занятых некоторыми буквами назовем словом. Длиной слова называется число занятых ячеек. Пусть А, В – слова, записанные в алфавите, не содержащем самих символов А и В. Тогда АВ – слово, получающееся, если сначала выписать слово А, а затем приписать справа слово В. Слово АВ называется композицией (или произведением) слов А и В. Удобно ввести еще пустое слово, композиция которого с любым словом считается по определению равной этому последнему слову. Пустое слово не следует путать с пустой ячейкой.

Слово А называется подсловом слова В, если В можно представить в виде , где С и D – некоторые (возможно пустые) слова. Слово А может входить несколько раз в слово В, при этом говорят о первом, втором и т.д. вхождении слова А в слово В.

 

Функции. Термы.

Если некоторым элементам множества Х поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана частичная функция из множества X во множество Y. Множество тех элементов из Х, у которых есть соответствующие образы во множестве Y, называется областью определения функции, а те элементы из Y, которые соответствуют некоторым элементам из Х, называются множеством значений функции.

Если область определения функции совпадает с множеством Х, то функцию называют всюду определенной.

Две функции f и g из Х в Y называются равными, если они имеют одну и ту же область определения и значения их совпадают в каждой точке области определения. Частичные функции из множества во множество Y называют частичными функциями от n переменных или n-местными функциями (частичными) из Х в Y. Частичная функция из прямого произведения в Х, называется n-местной частичной операцией на Х.

Для записи различных выражений пользуются особым формальным языком. Алфавит этого языка состоит из символов трех групп.

Символы первой группы называются предметными символами. В качестве таких символов обычно употребляют буквы a, b, x, y, … или те же буквы с индексами.

Символы второй группы называются функциональными, будем их обозначать , и т.д. Буква n – местный функциональный символ. Верхний индекс опускают, если известно, от какого числа переменных этот функциональный символ зависит.

Символы третьей группы – это левая и правая скобка и запятая.

Слова особого вида, записанные в этом алфавите, называются термами.

Термы длины 1 – это однобуквенные слова, составленные из букв, являющихся предметными переменными. Далее пользуемся индукцией. Пусть для некоторого термы длины, меньшей S, определены. Тогда слово длины S называется термом, если оно имеет вид , где - термы меньшей длины, а f – это n – местный функциональный символ. Например, если а, х – предметные символы, а f, g – одноместный и двуместный функциональные символы, то слова x, f(a), g(x, a), g(f(x), g(a, x)) являются термами длины 1, 4, 6, 14 соответственно.

По определению, задать значение предметного символа – это значит указать некоторое непустое множество, называемое основным множеством и сопоставить с рассматриваемым символом некоторый элемент этого множества, который называется значением данного символа.

Задать значение n-местного функционального символа – это значит сопоставить с ним какую-нибудь частичную n–местную операцию, определенную на основном множестве.

Теперь по индукции можно определить значение терма.

Если в качестве значений функциональных символов взяты частичные операции, определенные не всюду на основном множестве, то и значение терма может оказаться неопределенным. При записи термов пользуются сокращениями. Если, например, x, y – предметные символы, f – символ двуместной операции, то терм f(x, y) обычно пишут в виде xfy. В частности, если двуместные операции обозначаются символами +, ×, -, то термы ,сокращенно обозначают . Дальше всюду под числами понимаем 0 и натуральные числа 0, 1, 2, 3, …

Множество этих чисел будем обозначать N. Частичные функции, определённые на прямом произведении , направленные в N будем называть k-местными числовыми частичными функциями. Для краткости будем называть их просто функциями. Символы +, *, - будем считать двуместными функциональными символами, фиксированными значениями которых являются обычные арифметические операции. Во множестве натуральных чисел первые две операции всюду определены, а операция вычитания – частичная. Далее нам будут необходимы следующие числовые функции , имеющие по определению следующие значения:

,

,

.

Эти функции будем называть простейшими. Верхние индексы говорят, от какого числа переменных эти функции зависят. Поэтому вместо символов , будем писать S, O. Результатом функции S есть первоначальное число, увеличенное на единицу. Функция О обнуляет исходную числовую последовательность. А последняя функция J выбирает из предъявленной числовой последовательности число, стоящее на определённом месте. Эти функции можно комбинировать, получая более сложные функции.

 

Кодирование.

Теория алгоритмов имеет дело со словами в конечном алфавите. Однако многие объекты нельзя рассматривать как слова в некотором алфавите. К таким объектам, например, можно отнести рациональные числа, алгебраические числа и т.д. Тем не менее, некоторые из таких объектов могут быть закодированы в подходящем конечном алфавите. Например, взяв алфавит из двух символов 0, 1, можно закодировать любое натуральное число, взяв его двоичную запись. При двоичном кодировании не всякое слово в алфавите 0, 1 служит кодом натурального числа (например, 001).

 

 

Примитивно рекурсивные функции.

Операции над числовыми функции назовем операторами. В этом параграфе мы определим ряд операторов, обладающих тем свойством, что, применяя их к… Частичные функции, которые можно получить при помощи этих операторов из… Основная гипотеза Черча состоит в том, что класс частично рекурсивных функций совпадает с классом функций, допускающих…

Частично рекурсивные функции.

Оператор минимизации. Рассмотрим некоторую n - местную частичную функцию . Допустим, что существует… Фиксируем какие-нибудь значения для первых аргументов функции и рассмотрим уравнение

Машины Тьюринга.

Важный и широкий класс алгоритмов был описан Тьюрингом и Постом в 1936 - 1937 г. Алгоритмы этого класса осуществляются особыми машинами, называемыми… Машины Тьюринга копируют работу человека, вычисляющего по заданной… В 1936 г. Пост и Тьюринг одновременно и не зависимо друг от друга ввели в рассмотрение гипотетическую (не…

Список литературы.

 

1) Н. Я. Виленкин, Комбинаторика, «Наука», М., 1969.

2) М. Холл, Комбінаторика (пер. с англ.).

3) В. В. Белов, Е. М. Воробьев, В. Е. Шаталов, Теория графов, «Высшая школа», М., 1976.

4) О. Оре, Графы и их приложения, «Мир», 1965.

5) О. Оре, Теория графов (пер. с англ.), «Наука», 1968.

6) А. Гилл, Введение в теорию конечных автоматов, М., «Наука», 1966.


Учебное издание

 

курс лекций

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

2 семестр

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

 

 

Составители:

Вячеслав Викторович БАРАБАШ

Елена Юрьевна ЧАЛАЯ

 

Авторский оригинал-макет

 

Издательство Восточноукраинского национального
университета имени Владимира Даля

 

Адрес издательства :91034, г. Луганск, кв. Молодежный, 20а

Телефон:8 (0642) 41-34-12, факс. 8 (0642) 41-31-60

E-mail: uni@snu.edu.ua http: www.snu.edu.ua

 

– Конец работы –

Используемые теги: курс, лекций, дискретной, математике0.077

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Курс офтальмологии КУРС ЛЕКЦИЙ ТЕМАТИЧЕСКИЙ ПЛАН ЛЕКЦИЙ 1. Введение. Офтальмология и ее место среди других медицинских дисциплин. История офтальмологии. Анатомо-физиологические особенности органа зрения. 2. Зрительные функции и методы их исследования
Курс офтальмологии... КОРОЕВ О А...

Курс лекций к экспериментальной программе: Теория и методика начального курса математики
Педагогический колледж... Курс лекций к экспериментальной программе Quot Теория и методика...

Краткий курс механики в качестве программы и методических указаний по изучению курса Физика Краткий курс механики: Программа и методические указания по изучению курса Физика / С
Федеральное агентство железнодорожного транспорта... Омский государственный университет путей сообщения...

КОНСПЕКТ ЛЕКЦИЙ по курсу Архитектурное материаловедение Конспект лекций по курсу Архитектурное материаловедение
ФГОУ ВПО ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ... ИНСТИТУТ Архитектуры и искусств... КАФЕДРА ИНЖЕНЕРНО строительных ДИСЦИПЛИН...

КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Фесенко Т Н...

Курс лекций По дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... ИНСТИТУТ ЭКОНОМИКИ УПРАВЛЕНИЯ И ИНФОРМАЦИОННЫХ СИСТЕМ В СТРОИТЕЛЬСТВЕ... ИЭУИС...

МАСТЕРСКАЯ ПРАКТИЧЕСКОГО ПСИХОЛОГА КУРС ЛЕКЦИЙ Введение в общую психодиагностику. Курс лекций
ИНСТИТУТ ИНФОРМАТИЗАЦИИ СОЦИАЛЬНЫХ СИСТЕМ... МАСТЕРСКАЯ ПРАКТИЧЕСКОГО ПСИХОЛОГА...

Курс лекций: Элементы дискретной математики
Рис... Если A Igrave В то разность А В называется дополнением множества А до... U А Egrave В Говорят при этом что множество U разбито на два множества на А и Аналогичному разбиению можно подвергнуть множество А или множество или то и...

КУРС ЛЕКЦИЙ по дисциплине Железобетонные конструкции Курс лекций. Для специальностей «Архитектура» и «Промышленное и гражданское строительство»
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ... ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ...

Лекция 1: Введение в курс Экономика организаций предприятий КРАТКИЙ КУРС ЛЕКЦИЙ
Лекция Введение в курс Экономика организаций предприятий Объект предмет структура... Лекция Предприятие и предпринимательство в рыночной... Основные понятия о предприятии Организационно правовые и организационно экономические формы...

0.036
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам