Работа в Word
<<  Тема 4.4. Списки Нумерованные и маркированные списки  >>
Списки
Списки
Списки
Списки
Голова – первый элемент списка, любой объект Пролога
Голова – первый элемент списка, любой объект Пролога
Пример:
Пример:
Есть другая нотация: L=[ a | Хвост ] | имеет более общий смысл [a, b,
Есть другая нотация: L=[ a | Хвост ] | имеет более общий смысл [a, b,
Итог: Список – это структура данных, которая либо пуста, либо состоит
Итог: Список – это структура данных, которая либо пуста, либо состоит
Операции над списками
Операции над списками
Принадлежность списку
Принадлежность списку
принадлежит(X, [ X | Хвост)
принадлежит(X, [ X | Хвост)
Конкатенация
Конкатенация
Пример:
Пример:
? – конк( До, [май | После], [янв, фев, март, апр, май, июнь, …дек])
? – конк( До, [май | После], [янв, фев, март, апр, май, июнь, …дек])
Отношение принадлежит можно переопределить через конк: принадлежит1(X
Отношение принадлежит можно переопределить через конк: принадлежит1(X
Добавление элемента
Добавление элемента
Удаление элемента
Удаление элемента
удалить( X, [X | Хвост], Хвост)
удалить( X, [X | Хвост], Хвост)
Отношение удалить можно использовать чтобы добавлять элементы
Отношение удалить можно использовать чтобы добавлять элементы
Подсписок
Подсписок
? – Подсписок( s, [a,b,c])
? – Подсписок( s, [a,b,c])
Перестановки
Перестановки
Перестановка ( [],[])
Перестановка ( [],[])
Моделирование недетерминированного автомата
Моделирование недетерминированного автомата
b a S1 S2 a пусто b пусто S4 S3 b Пример недетерминированного автомата
b a S1 S2 a пусто b пусто S4 S3 b Пример недетерминированного автомата
Дуги, помеченные меткой пусто, - спонтанные переходы, они выполняются
Дуги, помеченные меткой пусто, - спонтанные переходы, они выполняются
первый символ оставшаяся часть цепочки S S1 X (a) цепочка S S1 пусто
первый символ оставшаяся часть цепочки S S1 X (a) цепочка S S1 пусто
Некоторый автомат можно описать при помощи трех отношений: Унарного
Некоторый автомат можно описать при помощи трех отношений: Унарного
Конечное(s3)
Конечное(s3)
Модель программируется в виде бинарного отношения допускается (
Модель программируется в виде бинарного отношения допускается (
допускается ( S, [ ]) :- конечное ( S)
допускается ( S, [ ]) :- конечное ( S)
?-допускается(s1, [a,a,a,b])
?-допускается(s1, [a,a,a,b])

Презентация на тему: «Списки». Автор: Шульгина. Файл: «Списки.ppt». Размер zip-архива: 76 КБ.

Списки

содержание презентации «Списки.ppt»
СлайдТекст
1 Списки

Списки

Григорьева И.В.

2 Списки

Списки

Списки – последовательность из произвольного числа элементов. [энн, теннис, том, лыжи] Все структурные объекты – деревья. пустой атом [] (nil) список голова непустой хвост

3 Голова – первый элемент списка, любой объект Пролога

Голова – первый элемент списка, любой объект Пролога

Хвост – остальная часть списка, обязательно должен быть списком. пустой хвост голова непустой хвост .(Голова, Хвост) Таким образом можно представлять списки любой длины.

4 Пример:

Пример:

(энн, .(теннис, .(том, .(лыжи, [])))) . . энн . теннис . том [] лыжи L=[a, b, c], тогда Хвост=[d,c] и L=.(a, Хвост)

5 Есть другая нотация: L=[ a | Хвост ] | имеет более общий смысл [a, b,

Есть другая нотация: L=[ a | Хвост ] | имеет более общий смысл [a, b,

c] = [a | [b, c]] = [a, b | [ c ]] = [a, b, c |[]]

6 Итог: Список – это структура данных, которая либо пуста, либо состоит

Итог: Список – это структура данных, которая либо пуста, либо состоит

из двух частей: головы и хвоста. Хвост сам является списком. Список в Прологе – специальный частный случай двоичного дерева. В Прологе существуют специальные средства для списковой нотации. [Элемент1, Элемент2, …] или [Голова | Хвост] или [Элемент1, Элемент2, …| Остальные]

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

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

Проверка, является ли некоторый объект элементом списка; Конкатенация двух списков; Добавление нового объекта в список или удаление некоторого объекта из него;

8 Принадлежность списку

Принадлежность списку

принадлежит (X, L), X – объект, L – список. Цель принадлежит(X, L) истинна если встречается в L. принадлежит(b, [a,b,c]) – верно принадлежит(b, [a, [b, c]] – не верно принадлежит([b,c], [a,[b,c]]) - верно X принадлежит L, если 1) X – голова L, или 2) X принадлежит хвосту L.

9 принадлежит(X, [ X | Хвост)

принадлежит(X, [ X | Хвост)

принадлежит (X, [Голова | Хвост]):- принадлежит(X, Хвост)

10 Конкатенация

Конкатенация

конкатенация (L1, L2, L3), L1, L2 – исходные списки, L3 – результирующий. конкатенация([a,b], [c,d], [a,b,c,d]) – верно конкатенация([a,b], [c,d], [a,b,a,c,d]) - неверно Определение конкатенация содержит два случая L1=[], тогда L2=L3, то есть конкатенация([], L, L). L1 – не пуст, то он имеет вид [X | L1], тогда конк( [ X | L1], L2, [ X | L3 ] ) :- конк (L1, L2, L3)

X

L1

L2

X

L3

[X | L1]

[X | L3]

11 Пример:

Пример:

– конк([a,b,c], [1,2,3],L). L=[a,b,c,1,2,3] ? – конк( [a,[b,c],d], [a,[],b], L). L=[a, [b,c], d, a, [], b] Можно использовать для разбиения заданного списка на две части: ? – конк(L1, L2, [a,b,c]). L1=[] L2=[a,b,c]; L1=[a] L2=[b,c]; L1=[a,b] L2=[c]; L1=[a,b,c] L2=[];

12 ? – конк( До, [май | После], [янв, фев, март, апр, май, июнь, …дек])

? – конк( До, [май | После], [янв, фев, март, апр, май, июнь, …дек])

До = [янв, фев, март, апр] После = [июнь, июль, …, дек]. ? – конк(_, [Месяц1, май, Месяц2 | _ ], [янв, …, дек]). Месяц1 = апр Месяц2 = июнь ? – L1=[a,b,z,z,c,z,z,z,d,e], конк(L2, [z,z,z | _ ], L1). L1 = [a,b,z,z,c,z,z,z,d,e] L2 = [a,b,z,z,c]

13 Отношение принадлежит можно переопределить через конк: принадлежит1(X

Отношение принадлежит можно переопределить через конк: принадлежит1(X

L) :- конк(L1, [ X | L2], L). или принадлежит1(X,L) :- конк(_, [ X | _ ], L). «X принадлежит L, если список L можно на два списка таким образом, чтобы X являлся головой второго из них» Процедурный смысл: Для проверки, является ли X частью L, нужно Проверить, не совпадает ли голова L c X Проверить, не принадлежит ли X хвосту L.

14 Добавление элемента

Добавление элемента

Добавить (X, L, [ X | L] ).

15 Удаление элемента

Удаление элемента

удалить ( X, L, L1), где L1 совпадает с L, у которого удален элемент X. Отношение имеет два случая: Если X является головой списка, тогда результатом удаления будет хвост списка. Если X в хвосте списка, тогда его нужно удалить оттуда

16 удалить( X, [X | Хвост], Хвост)

удалить( X, [X | Хвост], Хвост)

удалить( X, [ Y | Хвост], [Y | Хвост1]):- удалить(X, Хвост, Хвост1) ? – удалить(a, [a,b,a,a], L). L=(b,a,a) L=(a,b,a) L=(a,b,a)

17 Отношение удалить можно использовать чтобы добавлять элементы

Отношение удалить можно использовать чтобы добавлять элементы

– удалить(a, L, [1,2,3]). L=[a,1,2,3] L=[1,a,2,3] L=[1,2,a,3] L=[1,2,3,a] внести(X, Список, БольшойСписок):- удалить(X, БольшойСписок, Список). пренадлежит2( X, Список):- удалить(X, Список, _).

18 Подсписок

Подсписок

Подсписок(s,l), список S содержится в списке L в качестве подсписка. Подсписок ([c,d,e],[a,b,c,d,e,f]) – верно подсписок ([c,e],[a,b,c,d,e,f]) – неверно S является подсписком L, если L можно разбить на два списка L1 и L2 и L2 можно разбить на два списка S и L3. Подсписок(s,l):- конк(l1, L2, L), конк(s,l3,l2).

19 ? – Подсписок( s, [a,b,c])

? – Подсписок( s, [a,b,c])

S=[] s=[a] s=[a,b] s=[a,b,c] s=[b] …

20 Перестановки

Перестановки

перестановка(,), аргументы – списки, один из которых является перестановкой другого. ? – перестановка ([a,b,c], P) P=[a,b,c]; P=[a,c,b]; P=[b,a,c]; Два случая в зависимости от вида первого списка: Если первый список пуст, то второй должен быть пустым. Если первый список не пуст, тогда он имеет вид [ X | L ], перестановку такого списка можно построить так: вначале получить список L1 – перестановку L, внести X в произвольную позицию L1.

21 Перестановка ( [],[])

Перестановка ( [],[])

перестановка ( [X,L],P):- перестановка(l, L1), внести(x, L1, P). Перестановка2 ([], []). перестановка2 (L,[ X | P ]):- удалить (X, L, L1), перестановка2(l1, P). ? – Перестановка(l, [a,b,c]).

22 Моделирование недетерминированного автомата

Моделирование недетерминированного автомата

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

23 b a S1 S2 a пусто b пусто S4 S3 b Пример недетерминированного автомата

b a S1 S2 a пусто b пусто S4 S3 b Пример недетерминированного автомата

24 Дуги, помеченные меткой пусто, - спонтанные переходы, они выполняются

Дуги, помеченные меткой пусто, - спонтанные переходы, они выполняются

без чтения входной цепочки. Состояние, обведенное двойным кругом, - конечное состояние. Говорят, что автомат допускает входную цепочку, если в графе переходов существует путь такой, что: (1) Он начинается в начальном состоянии, (2) Он оканчивается в конечном состоянии, и (3) Метки дуг, образующих путь, соответствуют полной входной цепочке.

25 первый символ оставшаяся часть цепочки S S1 X (a) цепочка S S1 пусто

первый символ оставшаяся часть цепочки S S1 X (a) цепочка S S1 пусто

(б) Допущеные цепочки: (а) при чтении первого символа X; (б) при совершении спонтанного перехода.

26 Некоторый автомат можно описать при помощи трех отношений: Унарного

Некоторый автомат можно описать при помощи трех отношений: Унарного

отношения конечное, которое определяет конечное состояние автомата. Трехаргументного отношения переход, которое определяет переход из состояния в состояние, при этом переход(S1, X, S2) означает переход из состояния S1 в S2, если считан входной символ X. Бинарного отношения спонтанный(S1, S2) означающего, что возможен спонтанный переход из S1 в S2.

27 Конечное(s3)

Конечное(s3)

Переход( s1, a, s1). Переход( s1, a, s2). Переход( s1, b, s1). Переход( s2, b, s3). Переход( s3, b, s4). Cпонтанный (s2, s4). Cпонтанный (s3, s1).

28 Модель программируется в виде бинарного отношения допускается (

Модель программируется в виде бинарного отношения допускается (

Состояние, Цепочка), которое можно определить при помощи трех предложений: Пустая цепочка [ ] допускается из состояния S, если S – конечное состояние. Непустая цепочка допускается из состояния S, если после чтения первого ее символа автомат может перейти в состояние S1, и оставшаяся часть цепочки допускается из S1. Цепочка допускается из состояния S, если автомат может сделать спонтанный переход из S в S1, с затем допустить всю входную цепочку из S1.

29 допускается ( S, [ ]) :- конечное ( S)

допускается ( S, [ ]) :- конечное ( S)

% Допуск пустой цепочки допускается ( S, [X | Остальные]) :- % Допуск чтением первого символа переход (S, X, S1), допускается ( S1, Остальные). допускается ( S, Цепочка) :- % Допуск выполнения спонтанного перехода спонтанный (S, S1), допускается ( S1, Цепочка).

30 ?-допускается(s1, [a,a,a,b])

?-допускается(s1, [a,a,a,b])

?-допускается(S, [a,a,b]). ?-допускается(s1, [X1, X2, X3]). ?-Line = [_,_,_], допускается( s1, Line). Добавив в нашу модель переход cпонтанный(s1, s3). Получим «спонтанный цикл». ?-допускается(s1, [a]).

«Списки»
http://900igr.net/prezentacija/informatika/spiski-69433.html
cсылка на страницу

Работа в Word

38 презентаций о работе в Word
Урок

Информатика

130 тем
Слайды