Компьютерные науки - 3 2013-2014

МТ-202

P1.3
Напишите предикат factor(N,Res), который истинен, если переменная Res содержит факториал неотрицательного целого числа N.

P1.4
Напишите бинарный предикат, истинный, если второй аргумент есть двойной факториал первого.

P1.5
Напишите предикат, принимающий истинные значения на чётных целых числах.

P1.6
Напишите предикат, имеющий истинные значения на простых числах.

P1.7
Напишите предикат sirakuz(N,A0), который при своем доказательстве выводит N членов «сиракузской последовательности» с начальным членом A0.

P2.1
Напишите два предиката, принимающих список и элемент. Первый предикат должен быть истинным, если заданный элемент является первым в списке. Второй предикат истинен, если заданный элемент является вторым в списке.

P2.2
Не используя стандартный предикат reverse, напишите предикат, принимающий два списка и истинный, если второй список есть обращение первого.

P2.3
Напишите предикат, принимающий истинные значения на симметричных списках.

P2.4
Напишите предикат, принимающий два списка и истинный, если второй список получается из первого выкидыванием составных чисел.

P2.5а
Не используя стандартный предикат prefix, напишите предикат, принимающий два списка и истинный, если первый список есть начало второго.

P2.5б
Используя написанный предикат, напишите предикат, принимающий два списка и истинный, если первый список входит во второй.

P2.6
Напишите предикат, принимающий три числовых списка, отсортированных по возрастанию, и истинный, если третий список есть слияние первых двух (то есть, содержит элементы первых двух в соответствующем количестве).

P2.7а
Напишите предикат numlst/2(N,Lst), истинный, если Lst есть список цифр неотрицательного целого числа N, перечисленных от старших к младшим. Предикат должен работать в виде numlst/2(+N,+Lst)

P2.7б
Напишите предикат numlst/2(N,Lst), истинный, если Lst есть список цифр неотрицательного целого числа N, перечисленных от старших к младшим. Предикат должен работать в виде numlst/2(+N,?Lst)

P2.7в
Напишите предикат numlst/2(N,Lst), истинный, если Lst есть список цифр неотрицательного целого числа N, перечисленных от старших к младшим. Предикат должен работать в виде numlst/2(?N,?Lst). Придумайте разумное поведение предиката для случая, когда оба аргумента свободны.

P2.8
Напишите собственную реализацию быстрой сортировки заданного списка (предикат, принимающий два списка и истинный, если второй есть отсортированная версия второго).

P2.9
Напишите предикат, принимающий два списка и истинный, если второй список есть максимальный по длине непрерывный возрастающий подсписок первого списка.

P3.1
Напишите предикат addHead/3(?Elem,?List1,?List2), который принимает элемент и два списка списков и является истинным, если элементы List2 суть элементы List1 с приписанным в начале элементом Elem.

P3.2
Используя решение предыдущей задачи, напишите предикат subsets/2, принимающий два списка и истинный, если второй список содержит в каком-либо порядке полный набор подмножеств первого списка, представленных в виде списков, элементы внутри которых также идут в каком-либо порядке.

P3.3
Задача о рюкзаке имеет следующий смысл. Имеется n предметов, про каждый из которых известен его вес и стоимость. Имеется рюкзак с максимальной грузоподъёмностью w. Какова максимальная стоимость вещей из имеющихся, которые можно унести в таком рюкзаке?

Пусть в базе данных определены предикаты thing(Name,Weight,Price), каждый из которых описывает одну вещь из имеющегося набора. Также пусть определён предикат sack(MaxWeight), задающий максимальную грузоподъёмность имеющегося рюкзака. Напишите предикат pack(Things,MaxPrice) истинный, если Things есть отсортированный по возрастанию список имён вещей, составляющих какой-либо оптимальный набор, а MaxPrice — стоимость этого набора.

Примечание: На данный момент неизвестны решения данной задачи, принципиально
отличающиеся от полного перебора, поэтому разумно использовать решение предыдущей задачи.

P3.4а
Используя файл kinship.pro, напишите предикат brother(X,Y): X является родным братом Y

P3.4б
Используя файл kinship.pro, напишите предикат sister(X,Y): X является родной сестрой Y

P3.4в
Используя файл kinship.pro, напишите предикат married(X,Y): X и Y женаты (или были женаты считается, что в каждом браке имеются дети и все дети от законных браков)

P3.4г
Используя файл kinship.pro, напишите предикат husband(X,Y): X является мужем Y

P3.4д
Используя файл kinship.pro, напишите предикат cousin(X,Y): X и Y являются двоюродными братьями/сёстрами

P3.4е
Используя файл kinship.pro, напишите предикат grandson(X,Y): X является внуком Y

P3.4ж
Используя файл kinship.pro, напишите предикат pred(X,Y): X является предком Y

P3.4з
Используя файл kinship.pro, напишите предикат num_of_children(X,N): N - количество детей X

P3.4и
Используя файл kinship.pro, напишите предикат nephews(X,Y): X есть список племянников и племянниц Y

P3.4к
Используя файл kinship.pro, напишите предикат family(X): X есть список вида [отец, мать, все их общие дети, ...].

P4.1
Напишите предикат comp(Elem1,Elem2,CompFunc), принимающий два элемента и имя бинарного предиката. Предикат comp считается истинным, если является истинным предикат CompFunc(Elem1,Elem2).

P4.2
Напишите предикат filterOdd(List1,List2), принимающий два списка и истинный, если второй список получен из первого выкидыванием всех чётных чисел.

P4.3
Напишите предикат filter(List1,List2,FiltFunc), принимающий два списка и унарный предикат. Предикат filter считается истинным, если второй список получен из первого выкидыванием всех элементов, не удовлетворяющих предикату FiltFunc.

P4.4
Напишите предикат foldl(X0,Func,Lst,Res). Здесь Func(+A,+B,?C) — тернарный предикат, определённый на числах и осуществляющий преобразование A,B → C, X0 — число, Lst — список чисел. Предикат истинен, если Res есть результат цепочки вычислений Func(X0, Lst[1], X1), Func(X1, Lst[2], X2), ..., Func(Xn_minus_2, Lst[n-1], Xn_minus_1), Func(Xn_minus_1, Lst[n], Res).

P4.5а
Напишите предикат sira(+X,?N), принимающий два числа (X — натуральное, N — неотрицательное целое) и истинный, если число X есть минимальное натуральное число, переходящее в 1 по правилам сиракузской последовательности за N шагов.

P4.5б
Напишите предикат sira(-X,+N), принимающий два числа (X — натуральное, N — неотрицательное целое) и истинный, если число X есть минимальное натуральное число, переходящее в 1 по правилам сиракузской последовательности за N шагов.

P4.6а
Напишите динамический предикат sumOfDivs/2(+N,?X), истинный, если X есть сумма собственных делителей натурального числа N (считается, что N > 1); при своём вычислении предикат должен пополнять базу данных.

МТ-201

P1.3
Напишите предикат factor(N,Res), который истинен, если переменная Res содержит факториал неотрицательного целого числа N.

P1.4
Напишите бинарный предикат, истинный, если второй аргумент есть двойной факториал первого.

P1.5
Напишите предикат, принимающий истинные значения на чётных целых числах.

P1.6
Напишите предикат, имеющий истинные значения на простых числах.

P1.7
Напишите предикат sirakuz(N,A0), который при своем доказательстве выводит N членов «сиракузской последовательности» с начальным членом A0.

P2.1
Напишите два предиката, принимающих список и элемент. Первый предикат должен быть истинным, если заданный элемент является первым в списке. Второй предикат истинен, если заданный элемент является вторым в списке.

P2.2
Не используя стандартный предикат reverse, напишите предикат, принимающий два списка и истинный, если второй список есть обращение первого.

P2.3
Напишите предикат, принимающий истинные значения на симметричных списках.

P2.4
Напишите предикат, принимающий два списка и истинный, если второй список получается из первого выкидыванием составных чисел.

P2.5а
Не используя стандартный предикат prefix, напишите предикат, принимающий два списка и истинный, если первый список есть начало второго.

P2.5б
Используя написанный предикат, напишите предикат, принимающий два списка и истинный, если первый список входит во второй.

P2.6
Напишите предикат, принимающий три числовых списка, отсортированных по возрастанию, и истинный, если третий список есть слияние первых двух (то есть, содержит элементы первых двух в соответствующем количестве).

P2.7а
Напишите предикат numlst/2(N,Lst), истинный, если Lst есть список цифр неотрицательного целого числа N, перечисленных от старших к младшим. Предикат должен работать в виде numlst/2(+N,+Lst)

P2.7б
Напишите предикат numlst/2(N,Lst), истинный, если Lst есть список цифр неотрицательного целого числа N, перечисленных от старших к младшим. Предикат должен работать в виде numlst/2(+N,?Lst)

P2.7в
Напишите предикат numlst/2(N,Lst), истинный, если Lst есть список цифр неотрицательного целого числа N, перечисленных от старших к младшим. Предикат должен работать в виде numlst/2(?N,?Lst). Придумайте разумное поведение предиката для случая, когда оба аргумента свободны.

P2.8
Напишите собственную реализацию быстрой сортировки заданного списка (предикат, принимающий два списка и истинный, если второй есть отсортированная версия второго).

P2.9
Напишите предикат, принимающий два списка и истинный, если второй список есть максимальный по длине непрерывный возрастающий подсписок первого списка.

P3.1
Напишите предикат addHead/3(?Elem,?List1,?List2), который принимает элемент и два списка списков и является истинным, если элементы List2 суть элементы List1 с приписанным в начале элементом Elem.

P3.2
Используя решение предыдущей задачи, напишите предикат subsets/2, принимающий два списка и истинный, если второй список содержит в каком-либо порядке полный набор подмножеств первого списка, представленных в виде списков, элементы внутри которых также идут в каком-либо порядке.

P3.3
Задача о рюкзаке имеет следующий смысл. Имеется n предметов, про каждый из которых известен его вес и стоимость. Имеется рюкзак с максимальной грузоподъёмностью w. Какова максимальная стоимость вещей из имеющихся, которые можно унести в таком рюкзаке?

Пусть в базе данных определены предикаты thing(Name,Weight,Price), каждый из которых описывает одну вещь из имеющегося набора. Также пусть определён предикат sack(MaxWeight), задающий максимальную грузоподъёмность имеющегося рюкзака. Напишите предикат pack(Things,MaxPrice) истинный, если Things есть отсортированный по возрастанию список имён вещей, составляющих какой-либо оптимальный набор, а MaxPrice — стоимость этого набора.

Примечание: На данный момент неизвестны решения данной задачи, принципиально
отличающиеся от полного перебора, поэтому разумно использовать решение предыдущей задачи.

P3.4а
Используя файл kinship.pro, напишите предикат brother(X,Y): X является родным братом Y

P3.4б
Используя файл kinship.pro, напишите предикат sister(X,Y): X является родной сестрой Y

P3.4в
Используя файл kinship.pro, напишите предикат married(X,Y): X и Y женаты (или были женаты считается, что в каждом браке имеются дети и все дети от законных браков)

P3.4г
Используя файл kinship.pro, напишите предикат husband(X,Y): X является мужем Y

P3.4д
Используя файл kinship.pro, напишите предикат cousin(X,Y): X и Y являются двоюродными братьями/сёстрами

P3.4е
Используя файл kinship.pro, напишите предикат grandson(X,Y): X является внуком Y

P3.4ж
Используя файл kinship.pro, напишите предикат pred(X,Y): X является предком Y

P3.4з
Используя файл kinship.pro, напишите предикат num_of_children(X,N): N - количество детей X

P3.4и
Используя файл kinship.pro, напишите предикат nephews(X,Y): X есть список племянников и племянниц Y

P3.4к
Используя файл kinship.pro, напишите предикат family(X): X есть список вида [отец, мать, все их общие дети, ...].

P4.1
Напишите предикат comp(Elem1,Elem2,CompFunc), принимающий два элемента и имя бинарного предиката. Предикат comp считается истинным, если является истинным предикат CompFunc(Elem1,Elem2).

P4.2
Напишите предикат filterOdd(List1,List2), принимающий два списка и истинный, если второй список получен из первого выкидыванием всех чётных чисел.

P4.3
Напишите предикат filter(List1,List2,FiltFunc), принимающий два списка и унарный предикат. Предикат filter считается истинным, если второй список получен из первого выкидыванием всех элементов, не удовлетворяющих предикату FiltFunc.

P4.4
Напишите предикат foldl(X0,Func,Lst,Res). Здесь Func(+A,+B,?C) — тернарный предикат, определённый на числах и осуществляющий преобразование A,B → C, X0 — число, Lst — список чисел. Предикат истинен, если Res есть результат цепочки вычислений Func(X0, Lst[1], X1), Func(X1, Lst[2], X2), ..., Func(Xn_minus_2, Lst[n-1], Xn_minus_1), Func(Xn_minus_1, Lst[n], Res).

P4.5а
Напишите предикат sira(+X,?N), принимающий два числа (X — натуральное, N — неотрицательное целое) и истинный, если число X есть минимальное натуральное число, переходящее в 1 по правилам сиракузской последовательности за N шагов.

P4.5б
Напишите предикат sira(-X,+N), принимающий два числа (X — натуральное, N — неотрицательное целое) и истинный, если число X есть минимальное натуральное число, переходящее в 1 по правилам сиракузской последовательности за N шагов.

P4.6а
Напишите динамический предикат sumOfDivs/2(+N,?X), истинный, если X есть сумма собственных делителей натурального числа N (считается, что N > 1); при своём вычислении предикат должен пополнять базу данных.