Реферат Курсовая Конспект
КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ - раздел Математика, Министерство Образования И Науки Украины Восточноукраинский Национал...
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ
имени ВЛАДИМИРА ДАЛЯ
Барабаш В. В.
Чалая Е. Ю.
КУРС ЛЕКЦИЙ
Комбинаторика.
Комбинаторика – это раздел математики, в котором рассматриваются вопросы о том, сколько различных комбинаций можно составить из заданных объектов, подчиненных некоторым условиям.
Комбинаторика возникла в XVI веке. Первые задачи комбинаторики касались азартных игр – сколькими способами можно получить данное число очков, бросая две или три кости, или сколькими способами можно вытянуть двух королей из карточной колоды и т.д. Подобные вопросы и явились движущей силой развития комбинаторики и теории вероятностей. Яркий свет в комбинаторике оставили Паскаль, Я. Бернулли, Лейбниц, Эйлер и другие математики. В ХХ веке, в связи с созданием ЭВМ и повышением интереса к дискретной математике комбинаторика переживает бурный рост. Комбинаторные задачи возникают в анализе и алгебре, геометрии и топологии, в различных разделах математики и в приложениях.
Правила комбинаторики.
.
Доказать теорему можно индукцией по числу .
Примеры: количество телефонных номеров, автомобильных номеров, комбинаций в секретном замке, генетический код. Во всех этих ситуациях в расстановках элементы могут повторяться.
Количество комбинаций в секретном замке, число телефонных номеров, число автомобильных номеров, код Морзе, генетический код.
Разгадка генетического кода – крупнейшее достижение биологии ХХ века. Информация записана в гигантских молекулах ДНК (дезоксирибонуклеиновой кислоты). Различные молекулы ДНК отличаются порядком 4-х азотистых оснований. Эти основания определяют порядок построения белков организма из двух десятков аминокислот, причём каждая аминокислота зафиксирована кодом из 3-х азотистых оснований.
В одной хромосоме содержится несколько десятков миллионов азотистых оснований. Число различных комбинаций, в которых они могут идти друг за другом столь велико, что ничтожной доли этих комбинаций хватит для зашифровки всего многообразия живых организмов за время существования жизни на земле, оно равно , где – число оснований в хромосоме.
Числа Фибоначчи.
Теория графов.
Введение
Зарождение теории графов в XVIII веке было связано с математическими головоломками, и довольно долго учение о графах рассматривалось как несерьезная тема, прикладное значение которой было связано с играми и развлечениями. В этом отношении судьба теории графов схожа с судьбой теории вероятностей, которая также первоначально рассматривалась в связи с ее применениями к азартным играм.
В начале XX века графы стали применяться в топологии, и даже в первой половине XX века теория графов считалась главой топологии, этого современного раздела математики. Позже выявились связи теории графов с другими разделами современной математики (например, алгебра, комбинаторика и др.), а различные приложения теории графов к широкому кругу проблем сегодня даже трудно перечислить: это, например, исследования операций и управления, задачи экономики, теории информации, социологии и т.д.
Современная теория графов достигла достаточно высокого уровня формализации и удовлетворяет требованиям математической строгости.
Настоящая глава посвящена первоначальному знакомству с некоторыми направлениями в теории графов.
Основные понятия и определения теории графов.
Прежде чем приступить к точным определениям, поясним их наглядно. Любое конечное множество точек (вершин), некоторые из которых соединены попарно стрелками (в теории графов эти стрелки называются дугами), можно рассматривать как граф (рис. 1). Например, граф может изображать сеть улиц в городе, вершины графа — перекрестки, стрелками обозначены улицы с разрешенным направлением движения. (Улицы могут быть с односторонним и двусторонним движением.) Отметим здесь два момента. Во-первых, не любой граф можно изобразить на плоскости так, чтобы дуги пересекались только в вершинах (рис. 2). Во-вторых, две вершины могут быть соединены несколькими дугами, идущими в одном направлении (например, таким свойством может обладать схема железных дорог). Такие дуги будем называть кратными, а граф, содержащий кратные дуги, часто называют мультиграфом (рис. 3). Если подчеркивается, что в данном графе нет кратных дуг, то он называется графом без кратных дуг.
|
|
Определение 1:Мультиграфом или просто графом называется пара объектов: , где - конечное множество вершин, а - конечное подмножество прямого произведения . При этом называется множеством вершин, а - множеством дуг графа . Число указывает на количество дуг (кратность).
|
Покажем, каким образом введенное определение формализует понятие графа, интуитивно описанное выше.
Дугу (стрелку), соединяющую вершины , , мы обозначим через , где - начало дуги, - ее конец, а - номер дуги. Например, граф, изображенный на рис. 1, может быть аналитически описан соотношениями:
. (*)
Отметим, что при нумерации дуг не требуется, чтобы были использованы все номера, начиная с единицы и до числа дуг между данными вершинами. Например, граф на рис. 1 может быть описан так:
. (**)
Графы, заданные соотношениями (*) и (**), будем считать различными. Для формализации «идентичности» этих графов вводится ниже понятие изоморфизма.
Как уже сказано в определении 1, элементы множества называются дугами.
Определение 2: Дуга вида называется петлей.
На рис. 3 присутствует петля . Несколько сложнее понятие ребра. Иногда на графе в какой-либо прикладной задаче нет необходимости задавать направление связи между вершинами и . При изображении в этом случае связь рисуют без стрелки и говорят о ребре, соединяющем и (рис. 4, а). Будем считать такие ребра объединением дуг и с одинаковыми номерами.
Определение 3:Ребром называется подмножество вида .
Иллюстрацией может служить рис. 4, б. Видно, что если на графе две вершины связываются дугами с противоположными направлениями, то эти две дуги могут быть заменены одним ребром.
Определение 3: Граф называется симметрическим, если для любых номеров из того, что дуга следует, что дуга .
|
Из определения видно, что множества вида для симметрического графа образуют разбиение множества . Множество классов этого разбиения обозначается и называется множеством ребер симметрического графа . Подчеркнем, что определяется только для симметрических графов.
В дальнейшем, допуская вольность речи в случаях, где это не может привести к разночтениям. Вместо слов «ребро » будем говорить «ребро ».
Определение 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. Путь с наименьшим числом дуг. Пусть задан произвольный граф . Требуется построить такой путь, соединяющий две заданные вершины и , который содержит наименьшее число дуг (путь кратчайшей длины, если считать, что длины всех дуг одинаковы).
Если граф содержит небольшое число вершин и дуг, а задачу решает человек, то искомый путь может быть непосредственно «увиден», т. е. найден без применения каких-либо явно осознаваемых правил. При значительном количестве вершин и дуг в графе возникает необходимость в четком описании способа решения задачи.
Теорема 3: (Понтрягин - Куратовский). Для того чтобы граф был плоским, необходимо и достаточно, чтобы он не содержал в качестве подграфов графы или из условия теоремы 2.
Доказательство достаточности в этой теореме здесь не приводится. Отметим, что аналогичных критериев реализуемости графа уже для тора не найдено. Если произвольный граф не допускает плоской реализации, то он, возможно, допускает реализацию пространственную, т. е. может быть изображён без самопересечений ребер на пространственном объекте (шаре, торе и др.).
Теорема о пяти красках.
В § 2 уже встречалась задача о раскраске графов. Напомним ее постановку. Пусть дана географическая карта страны, в которой имеется несколько областей. Требуется окрасить каждую область так, чтобы любые две области, граничащие между собой, были окрашены в различные цвета. При этом «граничащими» областями называются области, которые граничат по некоторой линии (а не в точке). Во введении было показано, что эта задача может быть сведена к задаче о раскраске плоского графа: имея некоторое число красок, раскрасить каждую вершину одной из этих красок таким образом, чтобы любые две смежные вершины имели различную окраску.
Задача об определении минимального числа красок, нужных для правильной раскраски графа, которую мы здесь рассмотрим, является одной из первых задач теории графов. В этой главе слово «граф» будет обозначать полностью неориентированный граф без кратных ребер.
Теория конечных автоматов
Введение.
Теория конечных автоматов исследует тематические модели, приближенно отражающие физические или абстрактные явления, причем эти модели могут быть из области психологии, административного управления, связи, лингвистики, теории ЭВМ и т.д. С помощью конечных автоматов можно исследовать нервную систему животных или человека и проектировать ЭВМ.
Универсальная ЭВМ состоит из 5 устройств:
1) устройство ввода;
2) устройство памяти;
3) арифметическое устройство;
4) устройство управления;
5) устройство вывода.
Последовательность действий машины определяется программой, которая выполняется последовательно. Сама программа может предусматривать пропуск или повторение информации, хранящейся в памяти, т.е. от внутреннего состояния машины.
ЭВМ бывают цифровые и аналоговые. Мы здесь рассматриваем цифровые. Все сигналы в такой машине двузначны, т. е. принимают значения из множества .
Материальные носители и преобразования сигналов – конечны. Множество состояний любой машины также конечно.
Определение автомата Мили.
Покрытие и эквивалентность.
Определение 4: Морфизмом называется такое отображение , что и и . Если сюрьективно, то морфизм называется эпиморфизмом. Если - биекция, то морфизм называется изоморфизмом.
Теорема 2: Пусть эпиморфизм автомата на . Тогда для любой входной строки и любого начального состояния входная строка автомата совпадает с входной строкой автомата , если начальное состояние равно .
Доказательство:Доказательство можно провести индукцией по числу с индуктивным шагом:
;
.
Следствие: Любой эпиморфизм определяет покрытие автомата автоматом . Изоморфизм автоматов и с общим входным и выходным алфавитами есть биекция , такая, что для всякого начального состояния и всякой входной строки автоматы и выдают одну и ту же выходную строку, проходя через соответствующие промежуточные состояния.
Пример. Автоматы, представленные следующими ориентированными графами, изоморфны.
Алгоритмы и рекурсивные функции.
Введение.
Уже в математике древнего мира появились вычислительные процессы чисто механического характера, с помощью которых, действуя по инструкциям, можно было из заданных величин получать искомые. Такие правила, инструкции в математике стали называть алгоритмами. Примерами алгоритмов являются, например, правила сложения, вычитания, умножения и деления многозначных натуральных чисел, записанных в десятичной системе исчисления, алгоритм Евклида для нахождения наибольшего общего делителя натуральных чисел, решение системы линейных уравнений методом последовательного исключения неизвестных, отыскание целых корней многочленов с целыми коэффициентами и т.д.
В наше время отмечают следующие характерные черты алгоритмов:
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).
Список литературы.
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
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов