Методические указания к лабораторным работам по курсу “




Скачать 328.11 Kb.
НазваниеМетодические указания к лабораторным работам по курсу “
страница2/5
Дата публикации01.04.2013
Размер328.11 Kb.
ТипМетодические указания
vbibl.ru > Биология > Методические указания
1   2   3   4   5
^

Операции над спиcками



2.1. Теоретические сведения

Списки - это простая, наиболее часто используемая в нечисловом программировании структура, представляющая собой последовательность, составленную из произвольного числа элементов. Например, [ann, ski, tom]. Список является рекурсивной структурой:


  • он либо пуст,

либо

  • состоит из головы и хвоста,

  • где хвост есть список


ann – голова, [ski и tom] – хвост. Пустой список обозначается []. Во многих реализациях Пролога существуют функтор «.», объединяющий голову и хвост - (ann, .(ski,.(tom,[])).

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

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

L=[HeadTail]
Основные операции над списками.

К числу основных операций над списками оббычно относят:


  1. Проверка принадлежности элемента списку.

  2. Сцепление (конкатенация) двух списков.

  3. Добавление/удаление элемента в/из списка.

  4. Отношение подсписок.

  5. Определение длины списка.

  6. Удаление всух дубликатов и т.д.


● Отношение принадлежности элемента Х к списку L можно представить:

  1. Х есть голова L, либо у Х принадлежbn хвосту. Итак

member [X, [XTail]).

member [X, [HT]): - member [X, T).

Конкатенация conc(L1, L2, L3) – м. б. 2 случая:

а) если первый аргумент пуст, второй и третий аргумент представляет собой один и тот же список

conc([], L, L).

б) Если первый элемент не пуст, он имеет голову, а хвост [HT1], и его ??? с произвольным списком м. б. представлено
H T1 L2

├───┼───────┤├────┤ conc([{XL1], L2, [XL3]: - conc(L1, L2, L3).




L3

H L3

├───┼─────────────┤




[H│L3]

Как работает такая процедура:

Пусть L1=[a,b], L2=[c].
сonc([H│T1], L2, [H│L3])conc([b│[]], [c], L3)conc([], [c], L3)L3=[c] . . .



[c]

Несмотря на его простоту, предикат предоставляет больше возможности, он позволяет получить возможные варианты разбиения списка на два других.
Goal: conc(L1, L2, [a, b, c]). L1=[], L2=[a, b, c]; L1=[a], L2=[b, c]. . .

Можно найти элемент непосредственно предшествующий и непосредственно следующий за данным. Пусть имеется список [a1, a2, a3, a4].
Goal: conc (-, [X1, a3, X2], [a1, a2, a3, a4]).

X1=a2, X2=a4
Можно, например, удалить из L1 всё, что следует за тремя последовательностями, вхождениями элемента 2.
L1=[a, b, 2, 2, 2, d, e]

Goal: L1=[ a, b, 2, 2, 2, d, e], conc (L2, [2, 2, 2│_], L1).

L1=. . ., L2=[ a, b, 2, 2, 2].
Этот же предикат позволяет запрограммировать отношения принадлежности.
member1(X, L): - conc(_, [X│_], L1).

Goal: member1(b, [a, b, c]).
member1(b, [a, b, c])


conc(_, [b, _], [a, b, c])

Попытка сопос- Второе предложение сопоставимо: авления с 1-м L1 = [X|_], [b|_] = L2'

Предложением [a,b,c] = [X|L3].

L1 = [], [b|L2] = Тогда X=a, L3' = [b,c]

[a, b,c] . Неуспех, conc(L1’ [b, L2], [b, c])

т.к. b  a Первое предложение сопоставимо:

L1'=[], [b|L2]=[b,c]. Тогда L2=[c]

No Yes

Операции над списками.


  • Добавить элемент add (X,L,[X|L]).

  • Удалить элемент. Это отношение можно определить исходя из следующих соображений:

  1. Если удаляется голова, то результатом будет хвост списка;

  2. Если X находится в хвосте списка, то его нужно удалить оттуда.

del(X,[X|T],T).

del(X,[Y|T],[Y|T1]):- del(X,T,T1).

Это отношение также недетерминировано. Если в списке несколько вхождений элемента, то del удалит их все при помощи возвратов. Каждая альтернатива будет удалять лишь одно вхождение.

Goal: del (a,[a,b,a,a],L).

L=[b,a,a]; L=[a,b,a]; L=[a,b,a]; no

Если использовать del в обратном направлении, можно добавить элемент в произвольные позиции. Каким должен быть список L, чтобы после удаления a , получился список [1,2,3] ?

Goal: del (a,L,[b,c,d]).

L=[a,1,2,3]; L=[1,a,2,3]; . . . no

  • Подсписок. Отношение имеют два аргумента – список L и список S, такой, что L содержится в S . Предикат Sublist

(S, L)основывается на следующей идее:


Sublist(S,L)
То есть S является подсписком L, если

1)можно разбить на списки L1 и L2 и

  1. L2 можно разбить на списки S и L3 . Для разбиения списков можно использовать предикат conc. Поэтому


sublist(S,L):-conc(L1,L2,L), conc(S,L3,L2).
Этот же предикат можно использовать для построения всех подсписков данного списка.
Определение длины списка

Domains

integerlist = integer*

counter=integer

Predicates

list_length(integerlist,counter,couter)

Clauses

list_length([],Lenght,Lenght).

list_length([H|T],Len_in,Len_out):-

New_Len=Lenin+1,

list_length(T,New_len,len_out).

Вызов предиката должен иметь форму
list_length([1,2,3],0,L).
Предикат conc позволяет решить задачу сопоставления с образцом (pattern recognition) в простейшей ее форме. Задача состоит в том, что выполняется сопоставление шаблона, содержащего один из метасиволов:
* - замещает любую последовательность сиволо, в том числе и пустую

? - замещает один непустой символ.
Например, abc*g и abcdfg сопоставимы, причем * = df.
Domains

list = simbol*

Predicates

cmp_lst(list,list)

concatL(list,list,list)

wr_lst(list)

Clauses

wr_lst([ ]).

wr_st([First|Tail]):-

write(First," "),

wr_lst(Tail).

cmp_lst([],[]):- write (“matched”), nl.

cmp_lst( ,[]):- write (“unmatched”), nl.

cmp_lst([], ):- write (“unmatched”), nl. cmp_lst([X1|L1],[X2|L2]):-

X1=X2, cmp_lst(L1,L2).

cmp_lst([“*”|L1],L2):-

concat(Ast,L1,L2),

write(“matched”), nl,

write(“*=”), wr_lst(Ast), nl.


  • Перестановки - предикат с двумя аргументами-списками, один из которых является перестановкой другого. Перестановка осуществляется с помощью механизма автоматического перебора.

  1. Если первый список пуст, то и второй должен быть пуст.

(2) Если первый список не пуст, тогда он имеет вид [X|L] и тогда сначала получить L1 - перестановку L, затем внести X в произвольную позицию L.

permut([],[]).

permut([X|L],P):- permut(L,L1), insert(X,L1,P).
Предикат insert можно определить:

insert(X,List,BigList):- del(X,BigList,List).

  • ^ Печать списка.

Прямой порядок

type_list([]).

type_list([H|T]):-write(H), nl, type_list(T).

Обратный порядок .

type_list_rev ([]).

type_list_rev([H|T]):-type_list_rev(T),

write(H), nl.

Удаление дубликатов происходит путём просмотра первоначального списка. После этого при выходе из рекурсии создаётся второй список путём добавления только тех элементов, которые ещё не были добавлены. Результатом является список, в котором все элементы удалены.

Если первый список пуст, список со всеми удалёнными дубликатами тоже пуст. Это условие завершения рекурсии.
remove_dups([],[]) :- !

remove_dups([H|T],T1) :- member(H|T),!,

remove_dups(T|T1).

remove_dups([H|T],[H|T1]) :- remove_dups(T,T1).
Если оказывается, что голова является элементом хвоста списка, то элемент дублируется, последнее предложение строит список возврата.
2.1. Задание на работу.


  1. Написать предикат, определяющий длину списка.

  2. Написать предикат, определяющий n-й элемент списка.

  3. Написать предикат translate(list, list), для перевода списка чисел от 0 до 9 в список из соответствующих слов. Использовать в качестве впомогательных отношения вида:

meaning(1, one).

meaning(2, two).

  1. Написать предикаты, even(list) и odd(list), которые заканчиваются успехом, если длина списка четная и нечетная соответственно.

  2. Написать предикат, который для заданного диапазона простых чисел строит список всех простых чисел в этом диапазоне.

  3. Написать предикат, дублирующий его элементы заданное число раз.

Например, dups([a, b, c], 2). Результат - [a,a,b,b,c,c,]

  1. Написать предикат split(Middle, L, L1, L2). Аргумент Middle является компаратором, L – исходный список, L1 и L2 – подсписки, элементы которых меньше и больше Middle соответственно.

  2. Написать предикат, который строит список всех множителей заданного положительного числа.

  3. Написать предикат, range_lst(N1, N1, X), который все целые строит список всех чисел, отвечающие условию N1< =X <= N2.

  4. Написать предикат, который вычисляет среднее арифметическое элементов целочисленного списка.

  5. Написать предикат, который определяет пересечение двух множеств, заданных списками.

  6. Написать предикат rest(Xs, Y, Zs), который заканчивается успехом, если Zs - списк элементов, расположенных после элемента Y в списке Xs.

13. Написать предикат adjacent(X,Y,Zs), который заканчивается успехом, если X и Y - смежные елементы списка Z.
3. Внешние базы данных Турбо-Пролога
3.1. Теоретические сведения
Внешние БД хранят значения в цепях БД. Цепи могут быть проиндексированы с помощью так называемых В+ деревьев. Цепи внешних БД схожи с внутренними базами данных. В цепях внешних БД могут храниться любые объекты Пролога – значения, списки и так далее.
Внешние БД хранятся отдельно от собственно программ Пролога. Для создания БД используется предикат

db_create(db_name,file_name,loc_place), где

db_name – логическое имя базы данных;

file name – имя файла;

loc_place – место хранения.
Для определения имён БД используется домен db_selector:

db_selector = external_db1; my_db
Внешняя БД может храниться : в файле, в RAM, в расширенной (EMS) памяти.
RAM – in memory,

file – in_file,

EMS – in_ems (Win16 only).
Например,

db_create(db_name, “DBASE.DBA”,in_file).

db_create(db_name, “people”, in_memory).
БД, хранимым в RAM или EMS дают условные файловые имена. Перед завершением программы БД слудует закрыть

db_close(db_name).

В дальнейшем, БД открывается с помощью предиката

db_open (db_name,file_name,st_place).
Факты (термы) вводятся в БД во время работы программы с пмощью предикатов:

chain_insert()

chain_insertz()

chain_insertafter()

Первые два аналогичны assert() и assertz() и имеют 5 аргументов: 1 – db_name, данные в db_create, 2 – цепь БД, 3 – домен, которому принадлежит факт, 4 – терм, который надо ввести, 5 – ссылочный номер помещаемого терма (в этой позиции должна быть свободная переменная).
Предикат chain_insertafter используется для введения после заданного. В этой связи несколько изменяется расстановка аргументов. Третьим его аргументом является ссылочный номер терма, после которого помещаеется данный терм базы данных внешнего домена, описывающий вводимые данные. Этот ссылочный номер м.б. получен, например, с помощью предикта chain_terms() (см. ниже).

Пример.
Domains

db_selector = birthday_file

person = p ( string, string )

date = d ( integer, integer, integer )

birthday = bday ( person, date )

GOAL

db_create(birthday_file, "BIRTHDAY.DBA", in_file)

chain_insertz(birthday_file , % Database name

birthday_chain , % Databse chaine

birthday , % domain of term to be inserted

bday(p(Claudio", "Gusman"), d(9,25,45))

Ref) , % Reference number returned
db_close(birthday_file).
Для поиска в БД используется предикат chain_terms(). Формат его такой же как и у chain_insert. Разница в том, что последние два аргумента возвращают значения.

Predicates

read_terms

Clauses

read_terms:-chain_terms(birthday_file,birthday_chain,

birthday,X,_),

X=dday(p(First,Last),d(M,D,Y)),

writef(“%s %s birthday is on %d/%d/%d,/n”,

FirstName,LastName,M,D,Y),fail; true.

goal

mahewindow(1,2,3, “Birthday”,0,0,25,80),

db_open(birthday_file, “BIRTHday.dba”,in_file),

read_terms,

db_close(birthday_file).
Предикат обращения к БД довольно громоздок, что затрудняет чтение текста программы. Можно написать предикат – “оболочку”

db_bday(FirstName,LastName,Date):-

chain_terms(birthday_file,birthday_chain,birthday,X,_),

X=bday(p(FirstName,LastName),Date).
Модификация термов БД
Для модификации БД используются предикаты term_replace() и term_delete(). Их формат иммет вид
term_delete(db_sel,str,ref), где

db_sel - логическое имя БД,

str - имя цепи,

ref - ссылочный номер удаляемого терма.
term_replace(db_sel,domain, ref,term) где

db_sel - логическое имя БД,

domain - домен, которому принадлежит замещаемый терм,

ref - ссылочный номер замещаемого терма,

term - новое значение терма.

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

  1. каждая страница содержит не более 2n элементов (ключей):

  2. каждая страница, кроме корневой содержит не менее n элементов;

  3. каждая страница является либо местом, то есть не имеет потомков, либо имеет m +1 потомков, где m – число ключей в странице;

  4. все листья находятся на одном уровне.




Ключи располагаются слева направо. Если спроектировать дерево на один уровень, вставляя потомков между ключами, находящимися на странице - предке .

В В+ деревьях каждая страница, если она не является листом, имеет 2-х потомков.
При создании / открытии БД необходимо создать / открыть В+ древо. Всякий раз, когда модифицируется цепь БД, необходимо изменить соответствующее В+ дерево. В+ дерево создается с помощью предиката
bt_create(db_name,b+_tree_name,b+_tree_selector,ke_lenght,

node_lenght), где
db_name – то же имя БД, что и в db_create();

b+_tree_name – имя В+ дерева (строка);

b+_tree_selector – используется для идентификации В+ дерева;

key_lenght – длина строки, содержащей ключ;

node_lenght – количество ключей, хранящихся в каждом узле дерева.(1. . 255).
В+ деревья можно открывать и закрывать.
bt_open(db_name,”Tree_name”,bt_sel)

bt_close(db_name,bt_sel)
external_open(Bt_sel):-existfile(”Parts.Два”),!,

db_open(parts,”Parts.Два”,in_life”),

bt_open(parts,”Parts_tree”,bt_sell).
external_open(Bt_sel):-db_create(parts,”Parts.Два”,in_file),

bt_create(parts,”Parts_tree”,Bt_sel,8,4).
Пример использования В+ деревьев.
%% An example of external database with two B+trees

Domains

db_selector = patients

name = string

diagnosis = string

patient = p(name, diagnosis)
Predicates

ext_open(bt_selector, bt_selector)

ext_close(bt_selector, bt_selector)

enter_patients(bt_selector, bt_selector)

insert_patient(name, decease, bt_selector, bt_selector)

search_patient(bt_selector)
Clauses

ext_open(Pt_sel, Dgs_sel):-

existfile("Patients.dba"), !,

db_open(patients, "Patients.dba", in_file),

bt_open(patients, "Pats_Tree", Pt_sel),

bt_open(patients, "Dgs_Tree", Dcs_sel).

ext_open(Pt_sel, Dcs_sel):-

db_create(patients, "Patients.dba", in_file),

bt_create(patients, "Pats_Tree", Pt_sel, 8, 4),

bt_create(patients, "Dgs_Tree", Dgs_sel, 8, 4).

ext_close(Pt_sel, Dgs_sel):-

bt_close(patients, Pt_sel),

bt_close(patients, Dgs_sel),

db_close(patients).

enter_patients(Pt_sel, Dgs_sel):-

clearwindow, write("Enter a name (Ret to quit): "),

readln(Name), Name <> "", write("Enter a diagnosis:"),

readln(Dec), insert_patient(Name, Dg, Pt_sel, Dgs_sel),

enter_patients(Pt_sel, Dgs_sel).

enter_patients(_,_):- clearwindow.
insert_patient(Name, Dg, Pt_sel, Dgs_sel):-

chain_inserta(patients, pat_chain, patient, p(Name, Dec),

Ref),

key_insert(patients, Pt_sel, Name, Ref),

key_insert(patients, Dgs_sel, Dg, Ref).

search_patient(Pt_sel):-

clearwindow, write("Enter a name to look up(Ret to quit):

"),

readln(Nm), Nm <> "",

Name = "Smith",

key_search(patients, Pt_sel, Name, Ref ),

ref_term(patients, patient, Ref, p(Name, Dec)),

write(Name, Dg), nl,!,

key_search(patients,Pt_sel,Name,Ref1),

ref_term(patients, patient, Ref1, p(Name, Dg)),

write(Name, Dec), nl,fail.

search_patient(_).
Goal

makewindow(1,2,3, "Patients DataBase", 0,0,25,80),

ext_open(Pt_sel, Dcs_sel), enter_patients(Pt_sel, Dgs_sel),

search_patient(Pt_sel), ext_close(Pt_sel, Dgs_sel).

3.2. Задание на работу.
Написать программу “Телефонній справочник” с использованием внешней базы данных. Меню программы содержит следующие команды:
^ List all %Вывести всех абонентов

Add new contact %Добавить нового абонента

Delete contact %Удалить абонента

List contacts by name mask %Вывести абонентов по

%шаблону

Find by name %Найти по имени

Find by phone %Найти по номеру
ПРИМЕЧАНИЕ.

Для вывода абонентов по шаблону можно воспользоваться предикатом cmp_lst(list,list).
a/*

A test of simple pattern recognition predicate

*/

%trace cmp_lst

domains

list=char*

str = string

% ch_lst = symbol*

predicates

cmp_lst(list,list)

concatL(list,list,list)

member(char,list)

convert(str, list)
/* Remove comment to run test */
goal

convert("a*cd", L), cmp_lst(L,['a','b','c','d']), write("Matched"), nl;

write("Not matched"), nl.
CLAUSES

convert("", []).

convert(Str, [Head |Tail]):-

frontchar(Str, Head, Str1),

convert(Str1, Tail).
clauses

concatL([],L,L).

concatL([X|L1],L2,[X|L3]):-

concatL(L1,L2,L3).

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

cmp_lst([],[]).

cmp_lst([],_):- fail.

cmp_lst(_,[]):- fail.

cmp_lst([X1|L1],[X2|L2]):-

X1 = X2,

cmp_lst(L1,L2).

cmp_lst(['*'|L1],L2):-

concatL(_,L1,L2).
Предикат convert используется для преобразования строки в список символов.
Для организации экранно-ориентированного меню можно воспользоваться либо файлом menu2.pro, расположенным в каталоге ///TPROLOG/EXAMPLE, либо циклом с использованием предиката

repeat.
^ 4. Бинарные деревья.
4.1. Теоретические сведения
Рекурсивное определение бинарного дерева:
1. Бинарное дерево либо пусто,

либо

2. Состоит из левого и правого поддеревьев.

3. Поддерево есть бинарное дерево.

4. Каждый узел бинарного дерева имеет не более одного левого бинарного поддерева и не более одного правого бинарного поддерева.
В терминах Пролога такая структура м.б. определена следующим образом:

domains

treetype= tree(string, treetype,treetype);

empty
Последнее используется для обозначения пустого дерева.

Скажем дерево вида
c a t h y

/ \

/ \

m i c h a e l m e l o d y

/ \ / \

charles hasel jim eleonor
м.б. описано как:
tree('Cathy',tree('Michael',tree('Charles',empty, empty),

tree('Hazel' ,empty, empty)),

tree('Melody', tree('Jim',empty, empty),

tree('eleanor' ,empty, empty)))


1   2   3   4   5

Похожие:

Методические указания к лабораторным работам по курсу “ iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания к лабораторным работам по курсу “ iconМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
Методические указания предназначены для усвоения теоретических основ и формирования практических навыков по выбору рациональных структур...

Методические указания к лабораторным работам по курсу “ iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания к лабораторным работам по курсу “ iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания к лабораторным работам по курсу “ iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания к лабораторным работам по курсу “ iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания к лабораторным работам по курсу “ iconМетодические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...

Методические указания к лабораторным работам по курсу “ iconМетодические указания к лабораторным работам по учебным дисциплинам...
«Электродинамика и распространение радиоволн», «Техническая электродинамика» (для студентов направлений подготовки 050901 «Радиотехника»,...

Методические указания к лабораторным работам по курсу “ iconПрактикум по компьютерному моделирования ядерных процессов с использованием...
Практикум по компьютерному моделирования ядерных процессов с использованием библиотеки geant4

Методические указания к лабораторным работам по курсу “ iconМетодические указания по анализу финансового 12 состояния организации 12
Методические указания предназначены для выполнения курсовых работ по дисциплине «Анализ хозяйственной деятельности» для студентов...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница