Лабораторная работа n 4 использование структур и рекурсии при решении задач проектирования в системе турбо пролог - shikardos.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Лабораторная работа №3 «использование структур и рекурсии при решении... 1 38.24kb.
Лабораторная работа №1 2 Варианты заданий 2 Пример решения задачи... 4 489.46kb.
Резонанс в электрической цепи переменного тока 1 22.08kb.
Распознавание типов мыслительной деятельности по ээг при решении... 1 348.92kb.
Лабораторная работа №1. Сетевое оборудование и монтаж 1 188.06kb.
Урок по теме «Решение логических задач» 1 30.48kb.
Программа «Воспитательная работа в системе Школы полного дня» 1 159.7kb.
Лабораторная работа №3 Вольтамперометрическое определение ионов меди... 1 46.38kb.
«Решение примеров и составных задач» 1 38.99kb.
Урок физики в 9 классе Тема урока №1: Радиоактивность как свидетельство... 1 57.77kb.
Исследование операций и системный анализ пособие по проведению лабораторных... 1 249.68kb.
Модель многопроходного поглощения внешнего эц-излучения на начальной... 1 19.7kb.
- 4 1234.94kb.
Лабораторная работа n 4 использование структур и рекурсии при решении задач проектирования - страница №1/1

Министерство образования Российской Федерации
Тульский государственный университет
КАФЕДРА ЭЛЕКТРОННЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИН
БАЗЫ ЗНАНИЙ И ЭКСПЕРТНЫЕ СИСТЕМЫ

ЛАБОРАТОРНАЯ РАБОТА N 4



ИСПОЛЬЗОВАНИЕ СТРУКТУР И РЕКУРСИИ

ПРИ РЕШЕНИИ ЗАДАЧ ПРОЕКТИРОВАНИЯ

В СИСТЕМЕ ТУРБО ПРОЛОГ

Методические указания

для студентов направления

(специальности) 552800,552812,220100

Тула 1992

1. ЦЕЛЬ РАБОТЫ
Ознакомление с основными способами представления данных в виде составных объектов и списков, с реализацией рекурсивных и итерационных алгоритмов обработки списков, а также получение навыков использования составных объектов.
2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Предикаты в Прологе имеют вид R(t1,...,tk) (k>0), где R – это k-местное отношение, а ti - термы, т.е. константы (числа или имена, начинающиеся со строчной буквы), переменные (имена, начинающиеся с прописной буквы или символа подчеркивания), выражения вида f(t1,...,tm) (m>0), где f есть m-арный функциональный символ (функтор), а ti - произвольные термы. Терм f(t1,...,tm) называется составным термом.

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

Реляционная БД может быть представлена в виде набора отношений. Например, при автоматизированном распределении задач (программ) по уровням памяти вычислительного комплекса (ВК) исходные параметры задач объединяются в отношение task. Это отношение для конфигурации ВК с двумя магнитными дисками описывается следующей реляционной схемой, в которой указывается сущность каждого атрибута отношения:
task (Имя_задачи,Вариант_задачи,Объем_задачи,

Загрузка_диска_1_свопингом_задачи,

Загрузка_диска_1_выполнением_задачи,

Загрузка_диска_2_свопингом_задачи,

Загрузка_диска_2_выполнением_задачи)

Один из способов структурирования этого отношения - описание загрузки каждого диска составным термом (рис.1).
/* файл dbf5.pro - БАЗА ДАННЫХ */

domains


rd1,rd2=rd(rs,r)

name=string

variant,volume=integer

rs,r=real

predicates

task(name,variant,volume,rd1,rd2)

list

clauses


/* Статическая база данных */

task("задача_1",1,10,rd(0.1,0.04),rd(0,0.05)).

task("задача_2",1,12,rd(0.2,0.05),rd(0,0.01)).

task("задача_3",1,8,rd(0.2,0.03),rd(0,0)).

task("задача_4",1,4,rd(0,0.03),rd(0.2,0)).

task("задача_5",1,6,rd(0,0),rd(0.15,0.07)).

task("задача_1",2,2,rd(0.1,0),rd(0,0.09)).

list:-


write(" name var vol rs1 r1 rs2 r2"),

task(Name,Var,Vol,rd(Rs1,R1),rd(Rs2,R2)),nl,

writef("%8%3%4%6.2%6.2%6.2%6.2",Name,Var,Vol,Rs1,R1,Rs2,R2),

fail.


list:- !.
Рис. 1. Статическая база данных, содержащая

структурированные данные


Язык Пролог очень удобен для извлечения необходимой информации из структурированной БД. В этом случае можно ссылаться на объекты, не указывая в деталях всех их компонент. Можно задавать только структуру интересующих нас объектов и оставлять конкретные компоненты без точного описания или лишь с частичным описанием. Например, вопрос
Goal:. task(X,1,_,rd(0,_),_)
приводит к выдаче на экран имен задач первого варианта, которые при свопинге могут загружаться с диска 2, а вопрос

Goal:. task(X,1,V,_,_),V<=10


выясняет наличие в базе данных задач первого варианта, объем которых не превышает 10 единиц.

Предположим, что вариант задачи определяет число дисков в конфигурации ВК. В этом случае можно удалить атрибут "вариант задачи" из отношения task. Число составных объектов rd(rs,r) в предикате task будет однозначно определять вариант любой задачи. Целесообразно также составные объекты rd(rs,r) в каждом предикате объединить в список (рис.2). Для новой БД, использующей списки составных объектов, предыдущие два вопроса можно записать в следующем виде:


task(X,_,[rd(0, _ ), _ )

task(X,V,[ _ , _ ]), V<=10


Чтобы найти в базе данных все задачи, предназначенные для выполнения в ЭВМ с двумя и более дисками, необходимо задать вопрос
Goal:. task(X, _ ,[ _ , _ | _ ] )
Таким образом, в Прологе можно указывать интересующие нас объекты не только по их содержимому, но и по их структуре.

Можно также создать набор процедур, который служил бы утилитой, делающей взаимодействие с базой данных более удобным. Например, с помощью отношения name(X) пользователь может указать имена всех задач в базе данных или наличие в ней конкретной задачи. В этом случае ему не требуется знать состав и структуру объектов предиката task. Аналогичные функции пользовательского интерфейса выполняют процедуры


volume(X,V), rd(X,Rdd), list_rd(X,L).
В Прологе список - это структура данных, которая либо пуста, либо состоит из двух частей: головы и хвоста (остатка списка). Голова является эллементом списка, а хвост всегда является списком. Например, [] - пустой список, а [X|Y] – список состоящий из головы Х и хвоста Y. Из выражения [X|Y]=[a,b,c] следует X=a, Y=[b,c], а из выражения [X|Y]=[a] следует X=a, Y=[]. Головой может быть список, входящий в исходный список в качестве элемента. Например, из выражения [X|Y]=[[a,b],c,[d,e]] следует X=[a,b], Y=[c,[d,e]]. Список [X|Y] можно представить в виде составного терма.(X,Y), где функтор . соответствует функции cons (конструктор списка) языка Лисп. В этом случае список [a,b,c] можно представить в виде древовидной структуры .(a,.(b,.(c,[]))). Однако, вследствие своей громоздкости эта форма записи списков практически не используется в языке Пролог.

/* файл dbf6.pro */

/* БАЗА ДАННЫХ */

domains


rdd=rd(rs,r)

rdlist=rdd*

intlist=integer*

name=symbol

variant,volume=integer

rs,r=real

predicates

task(name,volume,rdlist)

list(variant)

name(name)

volume(name,volume)

rd(name,rdd)

member(rdd,rdlist)

list_rd(name,rdlist)

clauses

/* Статическая база данных */



task(z1_1,10,[rd(0.1,0.04)]).

task(z2_1,12,[rd(0.2,0.05)]).

task(z3_1,8,[rd(0.2,0.03)]).

task(z4_1,4,[rd(0.1,0.03)]).

task(z5_1,6,[rd(0.05,0.0)]).

task(z1_2,10,[rd(0.1,0.04),rd(0.0,0.05)]).

task(z2_2,12,[rd(0.2,0.05),rd(0.0,0.01)]).

task(z3_2,8,[rd(0.2,0.03),rd(0.0,0.0)]).

task(z4_2,4,[rd(0.0,0.03),rd(0.1,0.0)]).

task(z5_2,6,[rd(0.0,0.0),rd(0.05,0.07)]).

Рис. 2. Статическая база данных, использующая списки

для представления объектов

name(X):- /* X - имя задачи */

task(X,_,_).

volume(X,V):- /* V - объем задачи */

task(X,V,_).

rd(X,Rdd):- /* Rdd - структурированная */

task(X,_,List), /* загрузка диска */

member(Rdd,List).

list_rd(X,L):-

task(X,_,[rd(Rs1,R1)]),

L=[rd(Rs1,R1)].

list_rd(X,L):-

task(X,_,[rd(Rs1,R1),rd(Rs2,R2)]),

L=[rd(Rs1,R1),rd(Rs2,R2)].

member(X,[X|_]).

member(X,[_|L]):-

member(X,L).

list(1):-

write("name vol rs1 r1"),

task(Name,Vol,[rd(Rs1,R1)]),nl,

writef("%4%4%6.2%6.2",Name,Vol,Rs1,R1),

fail.

list(2):-



write("name vol rs1 r1 rs2 r2"),

task(Name,Vol,[rd(Rs1,R1),rd(Rs2,R2)]),nl,

writef("%4%4%6.2%6.2%6.2%6.2",Name,Vol,Rs1,R1,Rs2,R2),

fail.


list( _ ):- !.
Рис. 2. Окончание
Простейшей операцией над списком является проверка принадлежности некоторого объекта списку. Представим отношение принадлежности как member(X,L), где X - объект, а L - список. Цель member(X,L) истина, если элемент X встречается в L. Составление программы для отношения принадлежности может быть основано на следующих соображениях: Х есть голова L либо Х принадлежит хвосту L. На Турбо Прологе это можно записать в виде двух предложений, первое из которых есть простой факт, а второе - правило:
member(X,[X|_]).

member(X,[_|Ls]):-

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

Для преобразования фактов в списки в Прологе используется встроенный предикат findall (найти все), имеющий вид findall(X,P,L). Он определяет список термов L, которые конкретизируют переменную Х как аргумент предиката (цели) Р и делают истинным предикат Р. Например, на вопрос


Goal: findall(V,task( _ ,V,[ _ ]), L)
программа dbf6.pro выдаст список L, содержащий значения объекта "объем задачи" для задач, выполняемых в конфигурации ВК с одним диском, т.е. L=[10,12,8,4,6]. Если не существует ни одного объекта Х, удовлетворяющего цели Р, то findall все равно имеет успех и выдает L=[]. В Прологе имеется также встроенный предикат bagof, который аналогичен findall, но вместо выдачи пустого списка вырабатывается неуспешное завершение выполнения предиката.

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

- тривиальные, или "граничные" случаи;

- "общие" случаи, в которых одно решение получается из другого решения исходной задачи.

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

В Прологе рекурсия может использоваться как в рекурсивных, так и в итерационных алгоритмах. Предложение Пролога называется итерационным, если в теле предложения содержится только один рекурсивный вызов, а остальные подцели являются системными (встроенными) предикатами и располагаются перед рекурсивным вызовом.

Для реализации итерационных алгоритмов, требующих сохранения промежуточных результатов, процедуры Пролога дополняются аргументами, называемыми накопителями. Например, программа суммирования списка целых чисел, представленная на рис.4, использует вспомогательный предикат sumvinti/3 с дополнительным аргументом для накопления, начальное значение 0 которого устанавливается при исходном обращении к процедуре sumvinti/3. Sum означивают результатом вычислений в заключительном вызове процедуры при унификации с базисным фактом.
/* sumvint(L,Sum) - число Sum равно сумме всех элементов */

/* списка L, состоящего из целых чисел */


sumvint([X|Ls],Sum):-

sumvint(Ls,Tsum), Sum=X+Tsum.

sumvint([],0).
Рис. 3. Программа суммирования списка целых чисел
/* sumvinti(L,Sum) - число Sum равно сумме всех элементов */

/* списка L, состоящего из целых чисел */


sumviniti(Ls,Sum):-

sumviniti(Ls,0,Sum).

sumviniti([X|Ls],Temp,Sum):-

Temp1=Temp+X, sumvinti(Ls,Temp1,Sum).

sumvinti([],Sum,Sum).
Рис. 4. Итерационный вариант программы суммирования

списка целых чисел


Скалярным произведением двух векторов Х и Y называется сумма x1*y1+...+xn*yn. На рис. 5 и 6 приведены рекурсивный и итерационный варианты программ скалярного произведения векторов, представленных в виде списков. Если второй вектор содержит только двоичные цифры (0 и 1), то скалярное произведение представляет собой сумму элементов первого вектора, соответствующих единицам второго вектора (сумму по маске). На рис. 7 и 8 приведены рекурсивный и итерационный варианты программ суммирования элементов первого списка по маске, заданной во втором списке. Если же необходимо суммировать элементы списка, соответствующие нулевым элементам маски, то маску необходимо предварительно проинвертировать. Рекурсивная программа инвертирования двоичного списка приведена на рис.9.
/* mulvint(Xs,Ys,Res) - Res есть скалярное произведение */

/* векторов, представленных списками целых чисел Xs и Ys */


mulvint([X|Xs],[Y|Ys],Rez):-

mulvint(Xs,Ys,Rez1),Rez=X*Y+Rez1.

mulvint([],[],0).
Рис. 5. Программа вычисления скалярного произведения векторов
/* mulvinti(Xs,Ys,Rez) - Res есть скалярное произведение */

/* векторов, представленных списками целых чисел Xs и Ys */


mulvinti(Xs,Ys,Res):-

mulvinti(Xs,Ys,0,Rez).

mulvinti([X|Xs],[Y|Ys],Temp,Rez):-

Temp1=X*Y+Temp,mulvinti(Xs,Ys,Temp1,Rez).

mulvinti([],[],Rez,Rez).
Рис. 6. Программа итерационного вычисления

скалярного произведения векторов


/* mulvbin(Xs,Ys,Rez) - Rez есть сумма элементов списка Xs */

/* выделенных двоичной маской в списке Ys */


mulvbin([X|Xs],[1|Ys],Rez):-

mulvbin(Xs,Ys,Rez1),Rez=X+Rez1.

mulvbin([_|Xs],[0|Ys],Rez):-

mulvbin(Xs,Ys,Rez1),Rez=Rez1.

mulvbin([],[],0).
Рис.7. Программа сумирования списка по двоичной маске
/* mulvbin1(Xs,Ys,Res) - Res есть сумма элементов списка Xs */

/* выделенной двоичной маской в списке Ys */


mulvbini(Xs,Ys,Rez):-

mulvbini(Xs,Ys,0,Rez).

mulvbini([X|Xs],[1|Ys],Temp,Rez):-

Temp1=X+Temp,mulvbini(Xs,Ys,Temp1,Rez).

mulvbini([ _ |Xs],[0|Ys],Temp,Rez):-

Temp1=Temp,mulvbini(Xs,Ys,Temp1,Rez).

mulvbini([],[],Rez,Rez).
Рис. 8. Итерационный вариант программы сумирования списка

в соответствии с двоичной маской


/* invbin(Xs,Ys) - преобразование списка Xs в инвертированный Ys */
invbin([0|Xs],[Y|Ys]):-

invbin(Xs,Ys),Y=1.

invbin([1|Xs],[Y|Ys]):-

invbin(Xs,Ys),Ys=0.

invbin([],[]).
Рис. 9. Программа инвертирования двоичного списка
Для выделения максимального числа из списка целых чисел также могут использоваться как рекурсивный, так и итерационный алгоритмы. Более общей является программа, выделяющая максимальный элемент из элементов первого списка, соответствующих единичным значениям второго списка. Рекурсивный и итерационный варианты такой программы приведены на рис. 10 и 11. Все приведенные на рис. 3 - 11 вычислительные процедуры входят в состав программы dbf7.pro.
/* maxvbin(Xs,Ys,Max) - Max есть максимальный элемент из списка */

/* Xs в соответствии с двоичной маской в списке Ys */


maxvbin([X|Xs],[1|Ys],Max):-

maxvbin(Xs,Ys,Max1),X>=Max1,Max=X.

maxvbin([X|Xs],[1|Ys],Max]):-

maxvbin(Xs,Ys,Max1),X

maxvbin([_|Xs],[0|Ys],Max):-

maxvbin(Xs,Ys,Max1),Max=Max1.

maxvbin([],[],0).
Рис. 10. Программа выделения максимального элемента

списка по двоичной маске
/* maxvbini(Xs,Ys,Max) - Max есть максимальный элемент из списка */

/* Xs в соответствии с двоичной маской в списке Ys */


maxvbini([X|Xs],[1|Ys],M):-

maxvbini(Xs,Ys,X,M).

maxvbini([_|Xs],[0|Ys],M):-

maxvbini(Xs,Ys,M).

maxvbini([],[],0).

maxvbini([X|Xs],[Y|Ys],Z,M):-

X<=Z,maxvbini(Xs,Ys,Z,M).

maxvbini([X|Xs],[1|Ys],Z,M):-

X>Z,maxvbin(Xs,Ys,X,M).

maxvbini([_|Xs],[0|Ys],Z,M):-

maxvbini(Xs,Ys,Z,M).

maxvbini([],[],M,M).


Рис. 11. Итерационный вариант программы выделения

максимального элемента списка по двоичной маске
На рис.12 приведена программа dbf8.pro, в которой генерируются все 32 варианта распределения пяти задач по двум уровням памяти. Для каждого варианта вычисляются и выводятся на экран значения выходных параметров:
Vmem - суммарный объем задач, резидентных в оперативной памяти;

Vreg - объем транзитной области (области свопинга) в оперативной памяти;

Rsw - суммарная загрузка дисков свопингом задач.
/* файл dbf8.pro */

domains


rdd=rd(rs,r)

rdlist=rdd*

intlist=integer*

rlist=real*

rlistlist=rlist*

name=symbol

num_dsk,volume=integer

rs,r=real

predicates

task(name,volume,rdlist)

mulvbin(intlist,intlist,integer)

mulrvbin(rlist,intlist,rs)

invbin(intlist,intlist)

maxvbin(intlist,intlist,integer)

perebor(num_dsk)

form_list(num_dsk,intlist,rlistlist)

bin(integer)

calculate(intlist,intlist,rlistlist,volume,volume,rs)

sumrs(rlistlist,intlist,rs)

clauses


task(z1_1,10,[rd(0.1,0.04)]).

task(z2_1,12,[rd(0.2,0.05)]).

task(z3_1,8,[rd(0.2,0.03)]).

task(z4_1,4,[rd(0.1,0.03)]).

task(z5_1,6,[rd(0.05,0.0)]).

task(z1_2,10,[rd(0.1,0.04),rd(0.0,0.05)]).

task(z2_2,12,[rd(0.2,0.05),rd(0.0,0.01)]).

task(z3_2,8,[rd(0.2,0.03),rd(0.0,0.0)]).

task(z4_2,4,[rd(0.0,0.03),rd(0.1,0.0)]).

task(z5_2,6,[rd(0.0,0.0),rd(0.05,0.07)]).


Рис. 12. Программа проектирования, использующая

полный перебор вариантов решений

mulvbin([X|Xs],[1|Ys],Rez):-

mulvbin(Xs,Ys,Rez1),Rez=X+Rez1.

mulvbin([_|Xs],[0|Ys],Rez):-

mulvbin(Xs,Ys,Rez1),Rez=Rez1.

mulvbin([],[],0).

mulrvbin([X|Xs],[1|Ys],Rez):-

mulrvbin(Xs,Ys,Rez1),Rez=X+Rez1.

mulrvbin([_|Xs],[0|Ys],Rez):-

mulrvbin(Xs,Ys,Rez1),Rez=Rez1.

mulrvbin([],[],0).

invbin([0|Xs],[Y|Ys]):-

invbin(Xs,Ys),Y=1.

invbin([1|Xs],[Y|Ys]):-

invbin(Xs,Ys),Y=0.

invbin([],[]).

maxvbin([X|Xs],[1|Ys],Max):-

maxvbin(Xs,Ys,Max1),X>=Max1,Max=X.

Maxvbin([X|Xs],[1|Ys],Max):-

maxvbin(Xs,Ys,Max1),X

maxvbin([_|Xs],[0|Ys],Max):-

maxvbin(Xs,Ys,Max1),Max=Max1.

maxvbin([],[],0).

/* Процедура полного перебора вариантов */

bin(0).bin(1).

perebor(X):-

write(" П Р О Е К Т Н Ы Е Р Е Ш Е Н И Я"),nl,

write(" число дисков - ",X),nl,

write("z1 z2 z3 z4 z5 Vmem Vreg Rsw"),nl,

fail.


perebor(X):-

form_list(X,Lv,Ls),

A=0,B=0,bin(C),bin(D),bin(E),

L=[A,B,C,D,E],

calculate(L,Lv,Ls,Vmem,Vreg,Rsw),

writef("%2%3%3%3%3%6%6%8.2",A,B,C,D,E,Vmem,Vreg,Rsw),nl,

fail.

perebor(_):- !.


Рис. 12. Продолжение

form_list(1,Lv,Ls):-

findall(V,task(_,V,[_]),Lv),

findall(Rs1,task(_,_,[rd(Rs1,_)]),Ls1),

Ls=[Ls1].

form_list(2,Lv,Ls):-

findall(V,task(_,V,[_,_]),Lv),

findall(Rs1,task(_,_,[rd(Rs1,_),_]),Ls1),

findall(Rs2,task(_,_,[_,rd(Rs2,_)]),Ls2),

Ls=[Ls1,Ls2].

calculate(L,Lv,Ls,Vmem,Vreg,Rsw):-

invbin(L,Linv),

mulvbin(Lv,Linv,Vmem),

maxvbin(Lv,L,Vreg),

sumrs(Ls,L,Rsw).

sumrs([X|Xs],L,Rsw):-

sumrs(Xs,L,Rsw1),

mulrvbin(X,L,Rsw2),

Rsw=Rsw1+Rsw2.

sumrs([],_,0).


Рис. 12. Окончание
Для получения списка проектных решений для конфигурации ВК с двумя дисками необходимо задать вопрос
Goal: perebor(2)
При проверке первого правила процедуры perebor на экран монитора выводится шапка таблицы решений. Выполнение второго правила процедуры perebor приводит к вычислению ряда производных целей. Цель form_list задает преобразование фактов базы данных в списки объемов задач Lv и загрузки дисков свопингом задач Ls. Предикаты bin являются недетерминированными и используются для генерирования вариантов решений. Для каждого варианта формируется список L двоичных значений уровней памяти задач. При вычислении цели calculate используются процедуры инвертирования списка уровней памяти, суммирования списков целых и действительных чисел, нахождения максимального числа в списке. Полученные в результате выполнения цели calculate выходные параметры проектируемой системы выводятся на экран монитора с помощью предиката форматного вывода writef.

3.ОБОРУДОВАНИЕ
Персональный компьютер типа IBM PC, операционная система MS DOS, система програмирования Турбо Пролог версии 2.0, каталог AVT/LBR, содержащий исходные файлы программ на языке Турбо Пролог.
4.ЗАДАНИЕ НА РАБОТУ
Произвести загрузку, компиляцию и выполнение в диалоговом режиме программ dbf5.pro, dbf6.pro, dbf7.pro, dbf8.pro. Для просмотра хода вычисления заданных целей использовать средства трассировки системы Турбо Пролог. Изменить и выполнить отладку программ в соответствии с требованиями раздела 5. Изменение программы dbf8.pro производится в соответствии с вариантом задания, полученным от преподавателя. В результате изменений программа dbf8.pro должна находить оптимальное проектное решение в соответствии с критерием оптимальности. Программа оптимизации не должна использовать динамическую базу данных.

В каждом задании, конкретный вариант которого определяется двоичным кодом номера задания, указываются A, B, C, D:

A - вид задания объема оперативной памяти (ОП) и предельно допустимой загрузки для каждого магнитного диска в конфигурации проектируемого ВК. A {0,1}, где

0 - используется задание в виде фактов статической БД;

1 - задаются как входные параметры целевого предиката perebor;

B - вид частного критерия оптимальности:

В {0,1}, где

0 - минимизация суммарной загрузки дисков свопингом задач;

1 - минимизация используемого объема ОП;

С - указатель точки вызова процедуры вычисления загрузки каждого диска выполнением задач: С {0,1}, где

0 - вызов в процедуре calculate;

1 - вызов в процедуре form_list;

D - указатель результатов работы программы, выводимых на экран монитора: D {0,1}, где

0 - выводится оптимальное решение;

1 - выводится список допустимых решений и отдельно – оптимальное решение.
5. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
5.1. Просмотреть содержимое корневых каталогов каждого из дисководов. Сделать активным устройство, содержащее каталог AVT, перейти в каталог \AVT\LBR и запустить Турбо Пролог командой prolog.

5.2. После появления на экране информации о версии системы нажать клавишу F10. Ознакомиться с рабочим экраном интегрированной среды системы Турбо Пролог. Используя клавишу F6, изменить размеры окон так, чтобы окна диалога и редактирования стали одинаовыми.

5.3. Загрузить в редактор программу dbf5.pro. Для просмотра текста программы воспользоваться клавишей F5. После восстановления окон на экране командой Run (клавиша Alt-R) произвести компиляцию и выполнение загруженной программы. Задать в режиме диалога следующие цели:
list

task(X,1,_,rd(0,_),_)

task(X,1,V,_,_),V<10
5.4. Загрузить в редактор программу dbf6.pro. После просмотра текста программы произвести ее компиляцию и выполнение. Задать в режиме диалога следующие цели:
list(1)

list(2)


task(X,_,[ _ ])

task(X,_,[ _ , _ ])

task(X,_,[rd(0, _ ), _ ])

task(X,V,[ _ , _ ]),V<10

task(X, _ ,[ _ , _ | _ ])

name(z4_2)

name(X)

volume(X,V),V<10



rd(z4_2,R)

list_rd(z4_2,L)


5.5. Загрузить в редактор программу dbf7.pro. После просмотра текста программы произвести ее компиляцию и выполнение. Задать в режиме диалога следующие цели:
L=[12,8,10],sumvint(L,Sum1),Sumvinti(L,Sum2).

L1=[12,8,10],L2=[1,2,3],mulvint(L1,L2,Rez1), mulvinti(L1,L2,Rez2).

L1=[12,8,10],L2=[1,0,1],mulvbin(L1,L2,Rez1), mulvbini(L1,L2,Rez2).

L1=[1,0,1],invbin(L,Linv).

L1=[8,12,10],maxvint(L1,Max1),maxvinti(L1,Max2).

L1=[8,12,10],L2=[1,0,1],

maxvbin(L1,L2,Max1),maxvbini(L1,L2,Max2).
5.6. Установить значение Trace параметра Trace меню Options->Compiler Directives. Клавишей Alt-R запустить компиляцию и пошаговое вычисление целей, указанных в п.5.5. Внимательно следить за изменениями в окнах системы Турбо Пролог после каждого нажатия клавиши F10. Для завершения выполнения программы следует нажать Esc или Alt-T.

5.7. Загрузить в редактор программу dbf8.pro, содержащую процедуру полного перебора вариантов проектных решений. Для просмотра текста программы воспользоваться клавишей F5. После восстановления окон на экране произвести компиляцию и выполнение программы. В качестве цели указать сначала perebor(1), а затем perebor(2). Заменить bin(A), bin(B) на выражение А=0, В=0 (или наоборот) и повторно выполнить программу dbf8.pro.

5.8. Получить у преподавателя вариант задания на изменение программы dbf8.pro. После внесения изменений выполнить отладку программы. Окончательный вариант программы и результаты ее работы показать преподавателю.


  1. ОФОРМЛЕНИЕ ОТЧЕТА

Отчет должен содержать:

- перечень целей, вычисленных при выполнении лабораторной работы;

- текст измененной программы dbf8.pro;



  • параметры оптимального решения.




  1. КОНТРОЛЬНЫЕ ВОПРОСЫ

7.1. Какие предикаты называются недетерминированными? Как сделать недетерминированный предикат детерминированным и наоборот?

7.2. Как описываются структуры в разделе domains программы?

7.3. Какие процедуры выполняют функции пользовательского интерфейса при работе с базой данных?

7.4. В чем различие рекурсивных и итерационных алгоритмов обработки списков?

7.5. Объясните работу рекурсивной процедуры sumrs программы dbf8.pro.


БИБЛИОГРАФИЧЕСКИЙ СПИСОК


  1. Стерлинг Л., Шапиро Э. Искуcство программирования на языке Пролог: Пер. с англ. - М.: Мир, 1990. - 235 с.

  2. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. - М.:Мир, 1990. - 560 с.

  3. 3. Доорс Дж. и пр. Пролог – язык программирования будущего/ Дж. Доорс, А.Р. Рейблейн, С. Вапера: Пер. с англ. - М.: Финансы и статистика, 1990. - 144 с.

  4. 4. Янсон А. Турбо Пролог в сжатом изложении: Пер. с нем. - М.: Мир, 1991. - 94 с.

Разработал: канд. техн. наук, доц. Г.Б.Берсенев


Рассмотрено Нормоконтроллер,

на заседании кафедры ЭВМ ответственный по

Протокол N _3___________ стандартизации на

от "16" декабря_ 1992 г. кафедре

Зав. кафедрой ЭВМ ____ Т.И. Матикашвили

__________ В.М. Игнатьев "16" декабря_ 1992 г.


Методические указания переутверждены по дисциплине "Базы знаний и экспертные системы" как электронный документ, протокол N 4 от 17 ноября 1999 г.


Зав. кафедрой ЭВМ В.С. Карпов