Инструменты, алгоритмы и структуры данных

Упражнение 1:

Номер 1

Каким свойством не обладает корректно определенный рекурсивный метод?

Ответ:

(1) содержит хотя бы одну ветвь, не являющуюся рекурсивной

(2) все ветви метода являются рекурсивными - содержат рекурсивные вызовы

(3) каждый рекурсивный вызов отличается контекстом вызова

(4) как правило, для рекурсивного метода можно задать вариант - аналог варианта цикла, что позволяет доказывать завершаемость рекурсивных методов

Номер 2

Какие свойства являются необходимыми свойствами корректного рекурсивного метода?

Ответ:

(1) содержит хотя бы одну ветвь, не являющуюся рекурсивной

(2) все ветви метода являются рекурсивными - содержат рекурсивные вызовы

(3) каждый рекурсивный вызов отличается контекстом вызова

(4) как правило, для рекурсивного метода можно задать вариант - аналог варианта цикла, что позволяет доказывать завершаемость рекурсивных методов

Номер 3

Какие свойства справедливы для варианта рекурсивного метода

Ответ:

(1) вариантом рекурсивного метода является целочисленное неотрицательное выражение

(2) вариант связывается с каждым рекурсивным вызовом

(3) для всех внутренних рекурсивных вызовов вариант имеет одно и то же значение.

(4) предусловие метода должно гарантировать, что вариант имеет целочисленное и неотрицательное значение при каждом вызове метода

(5) если метод был вызван с вариантом, имеющим значение v, то для каждого внутреннего рекурсивного вызова ассоциированное с ним значение варианта неотрицательно и строго меньше v

Упражнение 2:

Номер 1

Какие утверждения справедливы относительно связи между циклами и рекурсией?

Ответ:

(1) в классических функциональных языках есть рекурсия, но нет циклов

(2) алгоритмы над рекурсивными структурами данных нельзя описать без использования рекурсии

(3) любой метод, содержащий циклы, можно достаточно просто заменить рекурсивным методом с рекурсивными вызовами, но без циклов

(4) любой рекурсивный метод можно заменить методом, содержащим циклы, но без рекурсии, применяя универсальную технику работы со стеками

(5) только, используя стеки, можно рекурсию заменить циклами

Номер 2

Все рекурсивные вызовы в рекурсивном методе должны отличаться контекстом вызова - это необходимое условие корректно определенного рекурсивного метода. А что определяет контекст вызова?

Ответ:

(1) фактические аргументы, задаваемые при вызове метода

(2) локальные переменные, объявленные в методе

(3) поля класса, в котором объявлен метод, представляющие глобальную информацию для метода

(4) сущность RESULT, определенная в языке Eiffel по умолчанию для всех методов, вычисляющих некоторую функцию

Номер 3

Необходимыми условиями корректно определенного рекурсивного метода является существование у метода ветви без рекурсии и разные контексты у каждого рекурсивного вызова. Рассмотрим метод с циклом:
 cicle
   do 
     from Init until Exit loop Body end
   end

Заменим его методом
  recursive
    do Init; loop_eqviv end
  с вызовом рекурсивного метода:
      loop_eqviv
   do 
     if not Exit then
        Body; loop_eqviv
     end
   end

Какие утверждения справедливы относительно корректности такой замены?

Ответ:

(1) такая замена некорректна, поскольку не выполняется необходимое условие существования у рекурсивного метода не рекурсивной ветви

(2) у метода loop_eqviv существует не рекурсивная ветвь. Когда выполняется условие выхода, то можно полагать, что выполняется ветвь без рекурсии (пустая в данном случае), завершающая выполнение метода

(3) такая замена некорректна, поскольку не выполняется необходимое условие изменения контекста при каждом вызове рекурсивного метода

(4) контекст у рекурсивного метода меняется автоматически

(5) контекст каждого вызова будет меняться только при выполнении условий, предполагаемых по умолчанию для этой схемы замены цикла рекурсией:

Все модули Init, Exit, Body определены над полями класса - глобальной для метода информацией;

Init задает начальный контекст вызова;

Каждое выполнение Body изменяет контекст и уменьшает значение варианта метода, гарантируя завершаемость.

(6) завершаемость метода cicle гарантирует завершаемость метода loop_eqviv

Упражнение 3:

Номер 1

Креативное понятие - это творческое понятие, несущее новую информацию, которая не может быть выведена из уже известных понятий. Укажите, какие понятия относятся к креативным понятиям?

Ответ:

(1) теорема

(2) аксиома

(3) определение, не включающее рекурсию

(4) определение, включающее рекурсию

Номер 2

Для рекурсивно определенной функции можно дать другое определение, не использующее рекурсию, основанное на подходе "снизу -вверх". Для простоты будем полагать, что рассматривается функция одного целочисленного аргумента. Какие утверждения справедливы для такого подхода?

Ответ:

(1) функцию можно задать ее графом - множеством пар math

(2) рекурсивное определение можно рассматривать как уравнение неподвижной точки math

(3) в уравнении неподвижной точки math

функция

- это некоторая универсальная функция, заданная на графе функции

(4) в уравнении неподвижной точки math

функция

- это функция, заданная на графе функции и представляющая решение уравнения

Номер 3

Рекурсивное определение функции  можно рассматривать как уравнение неподвижной точки . Какие утверждения справедливы для этого уравнения?

Ответ:

(1) решением уравнения неподвижной точки является функция math

, которая, будучи примененной к графу функции math

оставляет этот граф (множество пар) неизменным.

(2) рекурсивное определение math

позволяет построить функцию math

(3) функция math

, также как и функция math

, является рекурсивной

(4) если известно решение уравнения неподвижной точки - функция math

, то можно функцию math

определить без использования рекурсии

Упражнение 4:

Номер 1

Рекурсивное определение можно рассматривать как уравнение неподвижной точки . Пусть функция  является решением этого уравнения. Какие утверждения справедливы для этой функции?

Ответ:

(1) аргументом функции math

является рекурсивная функция, ее значением является также рекурсивная функция

(2) аргументом функции math

является пара math

- значением является другая пара math

(3) аргументом функции math

является граф функции math

- множество пар math

- значением является множество пар, которое функция строит по исходному множеству

(4) аргументом функции math

является граф функции - множество пар math

- значением является пара math

, которую функция строит по исходному множеству

Номер 2

Как выглядит граф функции "91", придуманной Маккарти?

Ответ:

(1) { [0, -10], [1, -9], [2, -8], … [100, 90], [101, 91], [102, 91], [103, 91], …}

(2) { [0, 11], [1, 12], [2, 13], … [80, 91], [81, 91], [82, 91], [83, 91], …}

(3) { [0, 91], [1, 91], [2, 91], … [100, 91], [101, 91], [102, 92], [103, 93], …}

(4) { [0, 91], [1, 91], [2, 91], … [100, 91], [101, 91], [102, 91], [103, 91], …}

Номер 3

Пусть аргументом функции  является множество пар целых чисел. Пусть также функция :
 добавляет в множество пару [0,0];
если в множестве есть пара  и , то в множество добавляется пара 
 Для какой рекурсивно определенной функции , где , функция  является решением уравнения неподвижной точки ?

Ответ:

(1) функции Фибоначчи

(2) функции Маккарти "91"

(3)

(4)

Упражнение 5:

Номер 1

Пусть членами семьи являются муж, жена, их родители и их дети. Определим рекурсивно понятие родственника. Члены семьи являются родственниками - родственниками уровня 0. Это не рекурсивная ветвь определения. Определим теперь рекурсивно понятие родственника - родственника некоторого уровня. Некто N является родственником уровня , если он не является родственником уровня k или более низкого уровня, но является родственником уровня 0 любого из родственников уровня k. К какому уровню по отношению к Вам  относится внук брата дедушки?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

Номер 2

Пусть функция  является решением уравнения неподвижной точки . Это позволяет дать не рекурсивное определение функции , аналогично тому, как определяется предел последовательности. Рассмотрим последовательность графов и связанных с ними функций .  Какие утверждения не являются справедливыми относительно такого определения ?

Ответ:

(1)

- пустое множество

(2)

- множество пар вида math

(3)

(4) функция math

добавляет пары в множество math

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

(5) поскольку функция math

добавляет пары и строит новые пары в множество math

, то свойство math

никогда выполняться не может

(6) по определению граф math

и соответственно сама функция math

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

Номер 3

Рассмотрим рекурсивное определение понятия "идентификатор":
 
 Пусть алфавит языка содержит две буквы - x и y и одну цифру -1. Индуцируя построение идентификаторов в стиле неподвижной точки, на нулевом уровне можно построить два идентификатора в соответствии с нерекурсивной частью определения, а сколько идентификаторов можно построить, принадлежащих уровню 2:

Ответ:

(1) 4

(2) 8.

(3) 16

(4) 18

(5) 24

Упражнение 6:

Номер 1

Какие утверждения справедливы относительно контракта рекурсивного метода? Для рекурсивного метода следует:

Ответ:

(1) всегда задавать вариант

(2) включать вариант в описание метода как комментарий при условии, что вариант известен

(3) всегда задавать инвариант

(4) в предложении require задавать предусловие метода. Метод должен гарантировать выполнение предусловия для всех внутренних рекурсивных вызовов

(5) в предложении ensure задавать постусловие метода. Метод должен гарантировать выполнение постусловия при завершении любого из внутренних рекурсивных вызовов

Номер 2

В контракт рекурсивного метода может входить инвариант метода. Какие утверждения справедливы относительно инварианта?

Ответ:

(1) если инвариант существует, то его следует включать в описание метода как комментарий

(2) если инвариант существует, то в описании метода он может быть задан как формальными булевскими выражениями, так и в виде комментария

(3) инвариант должен включаться в предусловие и постусловие метода

(4) та часть инварианта, которая задана формальными булевскими выражениями, должна включаться в предусловие и постусловие метода

(5) та часть инварианта, которая задана комментарием, не должна включаться в предусловие и постусловие метода

Номер 3

Какие утверждения справедливы относительно выполнения предусловия и постусловия рекурсивного метода?

Ответ:

(1) при вызове рекурсивного метода клиент обязан гарантировать выполнение предусловия метода

(2) клиент обязан гарантировать выполнение предусловия для всех внутренних рекурсивных вызовов

(3) для всех внутренних рекурсивных вызовов метод обязан гарантировать выполнение предусловия

(4) сам метод обязан гарантировать выполнение предусловия только в случае прямой рекурсии, когда вызов метода осуществляется непосредственно в теле самого метода

(5) при косвенной рекурсии гарантировать выполнение предусловия обязан метод, непосредственно вызывающий рекурсивный метод

Упражнение 7:

Номер 1

Пусть метод pвызывает метод q, тот вызывает метод r с косвенной рекурсией, - метод r вызывает метод s, который в свою очередь вызывает метод r. Какие утверждения справедливы относительно завершения методов в цепочке вызовов?

Ответ:

(1) первым может завершиться экземпляр метода s

(2) первым может завершиться экземпляр метода r

(3) первым может завершиться экземпляр метода q

(4) первым может завершиться экземпляр метода p

(5) первый, пришедший в стек, экземпляр метода r завершится позже первого, пришедшего в стек, экземпляра метода s

(6) последним завершится экземпляр метода p

Номер 2

Поскольку рекурсивный метод прямо или косвенно вызывает сам себя, то в цепочке вызовов этот метод будет присутствовать в нескольких экземплярах. Какие утверждения справедливы относительно понятия "экземпляр метода"?

Ответ:

(1) каждый экземпляр метода имеет собственную копию программного кода

(2) каждый экземпляр метода имеет собственную копию данных, называемую контекстом метода

(3) фактические аргументы, заданные в момент вызова, входят в контекст метода

(4) локальные переменные метода входят в его контекст

(5) поля класса входят в контекст метода

(6) для хранения контекста метода в момент его вызова создается запись активации, которая сохраняется в стеке вызовов

(7) при завершении работы метода запись активации удаляется из стека

Номер 3

Пусть метод p вызывает метод q, тот вызывает метод r с косвенной рекурсией, - метод r вызывает метод s, который в свою очередь вызывает метод r. Какие утверждения справедливы относительно процесса вызова методов?

Ответ:

(1) когда при выполнении тела метода происходит вызов метода, то вызывающий метод приостанавливает свою работу до тех пор, пока не завершится вызванный им метод. Так создается цепочка вызовов методов

(2) каждый метод в цепочке вызовов существует в единственном экземпляре

(3) нерекурсивные методы, такие как p и q, в цепочке вызовов существуют в единственном экземпляре

(4) рекурсивные методы, такие как p и q, в цепочке вызовов всегда существуют в множестве экземпляров

(5) рекурсивные методы, такие как p и q, в цепочке вызовов, как правило, существуют в множестве экземпляров

Упражнение 8:

Номер 1

В контекст рекурсивного метода, дающего решение задачи о Ханойской башне, входят 5 величин - 4 аргумента метода (имена трех башен и число переносимых дисков) и одна локальная переменная. При оптимальной реализации рекурсивного метода достаточно сохранять в записи активации?

Ответ:

(1) только имя исходной башни

(2) только имя целевой башни

(3) только число переносимых дисков

(4) только локальную переменную, следящую за номером рекурсивного вызова

(5) необходимо сохранять все 5 величин

Номер 2

В контекст рекурсивного метода, дающего решение задачи о Ханойской башне, входят 5 величин - 4 аргумента метода (имена трех башен и число переносимых дисков) и одна локальная переменная. Сколько величин достаточно сохранять в записи активации при оптимальной реализации рекурсивного метода?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

Номер 3

При выполнении рекурсивного метода создаются экземпляры метода, каждому из которых требуется информация, характеризующая данный экземпляр. Число экземпляров может быть большим, так, например, в задаче о Ханойской башне при n, равном, двадцати, более миллиона одновременно существующих экземпляров. Какие утверждения справедливы относительно способов представления информации, необходимой экземпляру метода?

Ответ:

(1) для хранения всей информации, необходимой экземпляру метода, в момент его вызова создается специальная запись - запись активации, размещаемая в стеке. Когда экземпляр заканчивает свою работу, запись выталкивается из стека, освобождая память

(2) сократить объем данных, хранимых в записи активации, можно за счет увеличения времени работы метода, - когда экземпляру требуется некоторое данное, то можно вычислять его значение, не храня его в записи активации. Этот прием называется "вычислить, а не хранить"

(3) прием "вычислить, а не хранить" всегда применим

(4) сократить объем данных, хранимых в записи активации, можно за счет увеличения времени работы метода. Требуемое экземпляру данное следует хранить в поле класса -общей памяти всех экземпляров. Когда экземпляру требуется некоторое данное, то значение, хранимое в поле, преобразуется в соответствии с требованиями экземпляра. Когда экземпляр заканчивает свою работу, то выполняется "обратное преобразование", восстанавливающее исходное значение. Этот прием называется "преобразования в общей памяти"

(5) прием "преобразования в общей памяти" всегда применим

Инструменты, алгоритмы и структуры данных - тест 9