Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Сопоставление алгоритмических моделей.



Все алгоритмические задачи принято делить на два больших класса: первый - это задачи, связанные с вычислением значения функции; второй - задачи, связанные с распознаванием принадлежности объекта заданному множеству (что равносильно получению ответа на вопрос: обладает ли объект заданным свойством? ). В первом случае алгоритм Q начинает работать с исходными данными - словом Р, составленным на основе алфавита А, и за конечное число шагов (преобразований) он должен остановиться и выдать результат Pk = fQ(P). Результат зависит (является функцией) от исходного слова, а также последовательности обработки, т.е. самого алгоритма. При этом вычисление понимается в широком смысле - как алфавитное преобразование.

В задачах, отнесенных ко второму классу, в результате выполнения алгоритма получается ответ на вопрос: «Истинно ли высказывание, что хÎ М »? или, что то же самое, проверяется истинность предиката хÎ Μ и выдается один из двух возможных результатов: ИСТИНА или ЛОЖЬ. Этот класс можно считать разновидностью первого, поскольку предикат - это функция, принимающая два значения в зависимости от условия. Тем не менее, разделение этих классов задач полезно, так как приводит к двум важным понятиям теории алгоритмов - вычислимая функция и разрешимое множество.

Функция называется вычислимой, если имеется алгоритм, вычисляющий ее значение.

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

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

 

59. Основные понятия теории графов. Степень вершины графа. Ориентированные графы, связные графы и компоненты связности. Понятие взвешенного графа. Способы задания графа.

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

Неориентированный граф (соответственно ориентированный граф, или орграф) G – это система G = (V, Е, F), состоящая из множества элементов V= {v}, называемых вершинами графа, множества элементов Е = {е}, называемых ребрами, и отображе­ния F: Е -> V2, ставящего в соответствие каждому элементу е Î Е неупорядоченную (соответственно упорядоченную) пару эле­ментов vt> v2 Î V, называемых концами ребра е.

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

VÈ Е образует множество элементов графа; при этом предпо­лагается, что ЕÇ V = 0. Отображение F определяет отношение инцидентности ребра с каждым из своих концов. Для графа G = (V, Е, F) употребляется также более короткое обозначение G = (V, Е) без указания инцидентностей, которые определяются кон­текстом. По количеству элементов графы делятся на конечные и бесконечные.

Если F (е) = (v1, v2) - упорядоченная пара (т.е. (v1, v2)¹ (v2, v1) при v1 = v2), то ребро е называется ориентированной дугой, ис­ходящей из вершины v, и входящей в вершину v2; v1 называется началом, a v2 -концом дуги е. Если F (е) = (v1, v2) - неупорядо­ченная пара, то ребро е называется неориентированным. Вся­кому графу G можно поставить в соответствие соотнесенный неориентированный граф G¢ с теми же множествами V и Е и ин­цидентностями, но все пары неупорядоченные.

Вершина, не инцидентная ни одному ребру, называется изо­лированной. Вершина, инцидентная ровно одному ребру, и само это ребро называются концевыми, или висячими. Ребро с совпа­дающими концами называется петлей. Две вершины, инцидент­ные одному и тому же ребру, называются соседними (или смеж­ными). Два ребра, инцидентные одной и той же вершине, назы­ваются смежными. Ребра, которым поставлена в соответствие одна и та же пара вершин, называются кратными, или парал­лельными.

Для различных задач одному и тому же объекту можно со­поставить граф по-разному. Так, фрагмент дорожной сети может быть представлен неориентированным ребром, изображающим наличие связи между его концами (населенными пунктами, го­родскими площадями или перекрестками); одной или двумя ду­гами, передающими одностороннее или двустороннее движение транспорта; несколькими дугами - отдельно для каждого ряда движения. Ребрам могут быть приписаны также числа, озна­чающие длину, рядность, уклон и другие численные или иные характеристики.

Два графа G1=(V1, E1, F 1) и G2= (V2, Е2, F 2) называются изоморфными, если существуют вза­имно однозначные отображения f: V1 < => V2 и g: E1 < => Е2, со­хра­няю­щие инцидентность, т.е. такие, что для всякого е Î Е1 равенство F 1(е) = (v1, v2) влечет за собой равенство F 2(gе) = (fv1, fv2).

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

1) Перечисление (список) ребер графа с указанием их концов и добавлением списка изолированных вершин.

2) Матрица инциденций графа с b вершинами и р ребрами - прямоугольная матрица А = ½ ½ aij½ ½ с b строками и р столбцами, строки которой соответствуют вершинам графа, а столбцы - ребрам, причем для неориентированного графа элемент матрицы aij равен 1, если вершина vi и ребро ej инцидентны, и равен 0 в противном случае. Для ориентированного графа aij = -1, если vi является началом дуги еj и aij = +1, если vi - конец дуги еj. В каж­дом столбце матрицы инциденций два ненулевых элемента, если ребро - не петля. Петле соответствует элемент, = 2.

3) Матрица достижимости вершин графа с b вершинами - квадратная матрица В = ½ ½ bij ½ ½ размерности b, строки и столбцы которой соответствуют вершинам графа, причем неот­рицательный элемент bij равен числу ребер, идущих из вершины vi в вершину vj. Для несмежных вершин соответствующий эле­мент матрицы равен 0.

4) Матрица смежности вершин графа, с b вершинами - квадратная матрица В = ½ ½ bij ½ ½ размерности b, строки и столбцы которой соответствуют вершинам графа, причем

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

4) Для наглядности граф часто представляют в виде геомет­рического объекта: вершинам соответствуют различные выде­ленные точки в пространстве (на плоскости), ребрам - отрезки кривых, связывающие соответствующие точки и не проходящие через выделенные точки, отличные от их концов. Отношению инцидентности вершин и ребер графа соответствует при этом геометрическая инцидентность выделенных точек и линий. Кроме того, предполагается, что кривые попарно не пересека­ются во внутренних точках. Такое представление графа называ­ется реализацией.

Полным графом называется граф без кратных ребер (и иногда без петель), в котором любые две вершины соединены ребром (ориентированным или неориентированным). Двудольным графом называется граф, вершины которого раз­биты на два непересекающихся класса: V = V1È V2, а ребра свя­зывают вершины только из разных классов - не обязательно все пары.

Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.

Две вершины А и В графа называются несвязными, если в графе не существует ни одного пути, связывающего их.

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

Граф называется несвязным, если хотя бы две его вершины несвязные, а " части" - компонентами связности. Каждая компонента представляет собой связный граф. Взвешенный (размеченный) граф – это граф, в котором с вершинами или линиями связана некоторая дополнительная информация. Эта информация называется весом вершины или линии.

 


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-04-10; Просмотров: 722; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.022 с.)
Главная | Случайная страница | Обратная связь