Сборник задач для семинаров (1131859), страница 2
Текст из файла (страница 2)
? list(a.X.nil)3. ? list(a.b)4. ? elem(X,a.b.c.nil)75. ? elem(a,X)Упражнение 5.3. Постройте SLD-резолютивные вычисления для каждого из запросов,приведенных в упражнении 5.2, обращенных к программам, описывющим предикаты list иelem.Упражнение 5.4. Постройте всевозможные SLD-резолютивные вычисления для запросаG= ? R(Y),P(Z), обращенного к программе P, выделяя в каждом целевом утверждении самуюлевую подцель. Каково множество вычисленных ответов на запрос G к программе P?P: R(Y) ← P(Y),Q(Y);P(a) ← ;P(b) ← ;Q(a) ← ;Q(f(X)) ← Q(X);Упражнение 5.5.
Построить логические программы, описывающие следующие свойства иотношения на множестве списков.1. head(L, X) : Заголовком списка L является элемент X;2. tail(L, X) : Хвостом списка L является список X;3. pref ix(L, X) : Префиксом (начальным подсписком) списка L является список X;4. sublist(L, X) : Список X является подсписком списка L;5. less(X, Y ) : Длина списка X меньше длины списка Y ;6.
subset(X, Y ) : Список X состоит только из элементов, содержащихся в списке Y ;7. concat(X, Y, Z) : Список X является конкатенацией (последовательным соединением)списков Y и Z;8. reverse(X, Y ) : Список X является обращением списка Y , т. е. X состоит из тех жеэлементов, что и список Y , но в списке X эти элементы следуют друг за другом вобратном порядке;9. period(X, Y ) : Список X является периодической последовательностью, полученной врезультате многократного повторения списка Y ;Упражнение 5.6. Натуральные числа X и Y представлены в двоичной системе счисления и их двоичные записи представлены в виде списков.
Построить логические программы,описывающие следующие отношения на множестве натуральных чисел.1. less(X, Y ) : Число X меньше числа Y ;2. sum(X, Y, Z) : Число Z равно сумме чисел X и Y ;86Встроенные функции и предикатыУпражнение 6.1. Используя встроенные предикаты равенства, неравенства и сравнениячисел, написать логические программы решения следующих задач1.
Упорядочить целочисленный список L1 .Запрос ? make_ordered(L1 , L2 ).2. Построить бесповторный список L2 , состоящий из всех элементов, содержащихся в списке L1 .Запрос ? single(L1 , L2 ).3. Построить бесповторный список L3 , состоящий из всех элементов, содержащихся как всписке L1 , так и в списке L2 .Запрос ? common(L1 , L2 , L3 ).Упражнение 6.2.
Используя оператор вычисления значений, построить логические программы, решающие следующие задачи.1. Вычислить длину X списка LЗапрос length(L, X);2. Вычислить сумму X элементов целочисленного списка L;Запрос sum(L, X);3. Вычислить кратность Y вхождения элемента X в список L;Запрос mult(L, X, Y );4. Вычислить самый распространенный элемент X в списке L;Запрос most_of t(L, X);5. Вычислить список всех простых чисел, не превосходящих заданного числа X;Запрос prime(L, X);6. Вычислить наибольший общий делитель Z двух целых чисел X и Y ;Запрос GCD(X, Y, Z);97Операторы отсечения и отрицания.Упражнение 7.1. Вычислить ответы на запрос G : ? A(X) к программе ΠA(Y )A(X)B(U )B(V )E(a2 )E(a3 )E(Z)D(U, a1 )D(U, U )D(X, a2 )C(Z, a3 )←−←−←−←−←−←−←−←−←−←−←−B(Y ), C(a2 , Y );D(a1 , X), C(X, Y );D(U, V ), !, E(V );E(a5 );;;;C(U, f (U ));;;;Упражнение 7.2.
Используя оператор отсечения написать программы решения следующихзадач:1. Вычисления наибольшего из двух чисел.Запрос ? max(X, Y, Z).2. Вычисления пересечения L3 множеств L1 и L2 , представленных бесповторными списками.Запрос ? common(L1 , L2 , L3 ).3. Вычисления всех элементов целочисленного списка L1 , квадраты которых не содержатся в этом списке.Запрос ? nonsquare(L1 , L2 ).Упражнение 7.3. Вычислить ответы на запрос G : ? A(X) к программе ΠA(Y )B(a)B(b)D(U )C(a)C(b)E(a, b)E(b, a)←−←−←−←−←−←−←−←−B(Y ), not(D(Y ));;;C(Y ), !, E(U, Y );;;;;Упражнение 7.4. Используя оператор not, написать логические программы решения следующих задач1. Вычисления максимального элемента списка L.Запрос ? max(L, x).102.
Вычисления списка самого длинного слова в тексте L.Запрос ? max_occur(L1 , L2 ).3. Вычисления кратчайшего пути между двумя вершинами в ориентированном графе,представленном списком дуг Γ.Запрос ? short_path(v1 , v2 , Γ, L).Упражнение 7.5. Представляя граф G посредством пары списков, — списка вершин V исписка ребер E, — написать логические программы решения теоретико-графовых задач.1. Для заданного графа G и пары вершин x, y выяснить, существует ли путь, соединяющийx и y в G. Запрос ? reach(V, E, x, y).2. Проверить выполнение программы для запросов? reach(a.b.c.d.nil, (a.b.nil).(b.c.nil), (c.a.nil), (b.d.nil).nil, a, d)3. Для заданного графа G и пары вершин x, y построить кратчайший путь, соединяющийx и y.
Запрос ? short_path(V, E, x, y, L).4. Для заданного графа G построить наименьшую его правильную раскраску.11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
