ИГА. Понятие базы данных

• Название: Понятие базы данных
• Дата: 05.04.2022
• Размер: 0.77 Mb.
• Имя файла: ИГА.docx
• Тип: Документы; #445246
• страница: 15 из 37

Алгоритмы на графах.

В некоторых матричных алгоритмах обработки графов используются так называемые матрицы путей. Определим понятие пути в ориентированном графе. Под путем длиной k из вершины i в вершину j мы будем понимать возможность попасть из вершины i в вершину j за k переходов, каждому из которых соответствует одна дуга. Одна матрица путей m _k содержит сведения о наличии всех путей одной длины k в графе. Единичное значение в позиции (i,j) означает наличие пути длины k из вершины i в вершину j.



Рис.4.24. Матрицы путей

Матрица m₁ полностью совпадает с матрицей инцидентности. По матрице m ₁ можно построить m ₂ . По матрице m ₂ можно построить m ₃ и т. д. Если граф является ациклическим, то число мариц путей ограничено. В противном случае матрицы будут повторяться до бесконечности с некоторым периодом, связанным с длиной циклов. Матрицы путей не имеет смысла вычислять до бесконечности. Достаточно остановиться в случае повторения матриц.

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

M _tr = m ₁ OR m ₂ OR m ₃ ┘

В результате матрица будет содержать все возможные пути в графе.



Рис. 4.25. Транзитивное замыкание в графе

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

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

Сформулируем алгоритм в матричном виде

1. 
   Для i от 1 до n выполнить шаги 1-2
   
2. 
   Если строка M(i ,*) = 0, то обнулить столбец i
   
3. 
   Если столбец M(*, i) = 0, то обнулить строку i
   
4. 
   Если матрица изменилась, то выполнить шаг 1
   
5. 
   Если матрица нулевая, то стоп, граф ациклический, иначе матрица содержит вершины, входящие в циклы
   

Рис. 4.26. Поиск циклов в графе

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

Сравнительная характеристика декларативных и процедурных языков программирования.

Пролог - язык программирования, используемый для решения задач, в которых действуют объекты и отношения между этими объектами. Пролог базируется на ограниченном наборе механизмов, включающих в себя сопоставление образцов, древовидном представлении структур данных и автоматический возврат. Пролог удивительно хорошо приспособлен для решения задач, в которых фигурируют объекты (в частности структуры) и отношения между ними. Пролог предназначен для обработки символьной информации. Пролог программу можно расширять, добавляя в них новые предложения. Программа на прологе состоит из предложений, которые могут быть фактами, правилами или вопросами. Программа на прологе состоит из предложений. Предложения трех видов: факты, правила, вопросы. Все предложения строятся из термов. Терм является синтаксической единицей. В основе нахождения решения - механизм обратного логического вывода (нахождение запроса от цели). Механизм поиска с возвратом- backtracking (обеспечивается поиск всех возможных решений). PROLOG – PROgramming in LOGic.

Особенности Lisp’a: 1) Представление программы и данных производится одинаково - через списки. Это позволяет программе обрабатывать другие программы и даже саму себя; 2) Лисп, как правило, является интерпретирующим языком, не позволяя создавать EXE-файлы; 3) Лисп безтиповый язык, это значит, что символы не связываются по умолчанию с каким-либо типом; 4) Лисп имеет необычный синтаксис. Из-за большего числа скобок LISP расшифровывают как Lots of Idiotic Silly Parentheses. 5) Программы, написанные на Лиспе, во много раз короче, чем написанные на процедурных языках. Лисп, как и другой любой язык программирования, использует переменные. Переменные Лиспа динамические - создание переменной и определение ее типа осуществляется в момент присвоения переменной значения; в программе, таким образом, совершенно отсутствует секция определения данных. Основные типы данных Лиспа: строковые, целые и действительные переменные (простой тип) и список (сложный). LISP – LISt Processing.

Хар-ка	LISP	PROLOG
тип языка	функциональный	логический
типы данных	атомы, списки	атомы, структуры
обработка	значение функции	связь переменных
данных	передача по значению	через унификацию
		по ссылке
управление	вычисление функций	рекурсия
программой	вычисления рекурсии
	условные	бэктрекинг
	циклы
структуры	функции	правила
программы	LET-блоки	факты
действия	локальные	область одно
переменных	свободные	предложение
транслятор	интерпретатор	интерпретатор
	компилятор	компилятор
длина программы	3	1
скорость	2	5
Область	символьная обработка	ЭС
	ИИ	ИИ
		прототипы

Управление поиском решений. Простые и составные объекты данных. Функции, определение функций.
Простые объекты

1) целые и вещественные числа; 2) литеры; 3) символы и строки.

Целые и вещественные числа. Синтаксис целых чисел прост, как это видно из следующих примеров: 1, 1313, 0, -97. Не все целые числа могут быть представлены в машине, поэтому диапазон целых чисел ограничен интервалом между некоторыми минимальным и максимальным числами, определяемыми конкретной реализацией Пролога. Обычно реализация допускает диапазон хотя бы от -16 383 до 16 383, а часто, и значительно более широкий.

Синтаксис вещественных чисел зависит от реализации. Мы будем придерживаться простых правил, видных из следующих примеров: 3.14, -0.0035, 100.2. При обычном программировании на Прологе вещественные числа используются редко. Причина этого кроется в том, что Пролог - это язык, предназначенный в первую очередь для обработки символьной, а не числовой информации, в противоположность языкам типа Фортрана, ориентированным на числовую обработку. При символьной обработке часто используются целые числа, например, для подсчета количества элементов списка; нужда же в вещественных числах невелика. Кроме отсутствия необходимости в использовании вещественных чисел в обычных применениях Пролога, существует и другая причина избегать их. Мы всегда стремимся поддерживать наши программы в таком виде, чтобы их смысл был предельно ясен. Введение вещественных чисел в некоторой степени нарушает эту ясность из-за ошибок вычислений, связанных с округлением во время выполнения арифметических действий. Например, результатом вычисления выражения 10000 + 0.0001 - 10000 может оказаться 0 вместо правильного значения 0.0001.

Литеры. Прописные буквы A, B, …, Z; строчные буквы a, b, …, z.

Символы и строки: + - * / < > = : . & _ .

Составные объекты. Составные объекты данных позволяют рассматривать информацию, состоящую из нескольких частей, как единое целое, в то же время предоставляя возможность получать доступ к отдельным частям этой информации. Например, дата рождения человека может быть представлена как единый объект, и в то же время, дата состоит из трех частей, числа, месяца и года. Такую составную структуру можно представить как единое целое, использовав функтор, например, birthday. Имя функтора выбирается произвольно. Тогда структура будет выглядеть следующим образом: birthday (25, “мая”, 1980). Секция описания доменов будет выглядеть следующим образом:

DOMAINS

day=birthday (integer, symbol, integer) % day – имя нового нестандартного домена. Имя

name=string % домена может совпадать с именем функтора.

Такое описание домена позволит определить предикат, в котором в качестве аргумента можно использовать данные, принадлежащие домену day. Далее следует пример программы с использованием данного домена.

PREDICATES : congratulation (name, day)

print print2

CLAUSES : congratulation (“Анна”, birthday (25, “мая”, 1980)).

congratulation (“Иван”, birthday (17, “декабря”, 1957)).

congratulation (“Петр”, birthday (30, “июля”, 2001)).

print:- congratulation (Name, birthday (Day, Month, Year)), write (“С днем рождения ”, Day, Month, Year, ”, ”, Name,”!”), nl, fail.

print.

print2:- congratulation (Name, Birthday), write (“С днем рождения ”, Birthday, ”, ”, Name,”!”), nl, fail.

print2.

GOAL : print, print2.

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

Многоуровневые составные объекты данных.

Составные объекты данных позволяют рассматривать информацию, состоящую из нескольких частей, как единое целое, в то же время предоставляя возможность получать доступ к отдельным частям этой информации. Например, информация о человеке может быть представлена как единый объект, и в то же время, информация состоит из трех нескольких частей: имени, даты рождения (которая в свою очередь является одноуровневым составным объектом, состоящим из числа, месяца, года), адреса (который также является одноуровневым составным объектом, состоящим из улицы и номера дома). Такую составную структуру можно представить как единое целое, использовав функтор, например, info. Имя функтора выбирается произвольно. Тогда структура будет выглядеть следующим образом: info(“Ivan”, date(25, “мая”, 1980), address(“Lenina”, 3)). Секция описания доменов будет выглядеть следующим образом:

DOMAINS

info = info (string, date, address)

date = date (integer, string, integer)

address = address (string, integer)

PREDICATES

i (info)

print

d (date)

print2

CLAUSES

i (info (“Ivan”, date(25, “мая”, 1980), address(“Lenina”, 3)) ).

d (date (5, “april”, 2005) ).

……………………..

print :- i (X), write(X), fail.

print.

print2 :- i (_, date(_, _, Y), _), write(Y), fail.

print2.

GOAL

print, print2.

Определение функций и их вычисление в Лиспе основано на лямбда-исчислении Черча, предполагающем для этого простой и точный формализм. В лямбда-исчислении Черча функция записывается в следующем виде: lambda(x1,x2,….xn).fn в лиспе лямбда-выражение имеет вид: (LAMBDA(x1,x2,…xn)fn). Символ LAMBDA означает что мы имеем дело с определением функции. Символы xi являются формальными параметрами определения, которые именуют аргументы в описывающем вычисления теле функции fn. Входящий в состав формы список, образованный из параметров, называют лямбда-списком.

Телом функции является произвольная форма, значение которой может вычислить интерпретатор Лиспа, например: константа, связанный со значением символ или композиция из вызовов функций.

Лямбда-выражение - это определение вычислений и параметров функции в чистом виде без фактических параметров, или аргументов. Для того, чтобы применить такую функцию к некоторым аргументам, нужно в вызове функции поставить лямбда-определение на место имени функции: (лямбда-выражение а1,а2….аn)

Здесь ai – формы, задающие фактические параметры, которых вычисляются как обычно.

Например: ((lambda(x y)(+ x y) 2 3)). Такую форму вызова называют лямбда-вызовом.

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