База ответов ИНТУИТ

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

<<- Назад к вопросам

Рассмотрим некоторые задачи. Какие отношения, введенные в этих задачах, являются ациклическими?

(Ответ считается верным, если отмечены все правильные варианты ответов.)
Варианты ответа
в олимпийских играх спортсмен после проигрыша выбывает из турнира. Пара спортсменов [f, g] принадлежит отношению r, если спортсмен f выиграл у спортсмена g(Верный ответ)
на множестве исторических событий можно ввести отношение "предшествует". Пара событий [f, g] принадлежит отношению r, если событие f предшествует по времени событию g(Верный ответ)
в групповых турнирах спортсмены встречаются между собой. Пара спортсменов [f, g] принадлежит отношению r, если спортсмен f выиграл у спортсмена g
в языках программирования, таких как Eiffel, в теле метода может быть вызван другой метод, так что естественным образом вводится отношение "вызывает". Пара методов [f, g] принадлежит отношению r, если метод f вызывает метод g
при сборке изделий (автомобиля, самолета, корабля) детали изделия собираются из других деталей, так что естественным образом вводится отношение "является частью". Пара деталей [f, g] принадлежит отношению r, если деталь f является частью детали g(Верный ответ)
Похожие вопросы
Какие утверждения справедливы для ациклического отношения и отношения порядка?
Рассмотрим два фрагмента программ:

-- fragment 1

from x := low until x >= high loop   Result := Result + f(x)   x := x + stepend
-- fragment 2 
from x := low; i := 0 until x >= high loop    Result := Result + f(x)    i := i + 1; x := low + i * stepend
Какие высказывания справедливы для этих фрагментов?
Рассмотрим язык программирования с двумя операторами - присваивания и цикла. Присваивание рассматривается в классическом варианте variable := expression и считается терминальным, не определяемым далее понятием. Грамматика языка такова:
\text{Оператор }\triangleq\text{ Присваивание | Цикл}\\ \text{Цикл }\triangleq \text{ until (Условие) Оператор}
Какие утверждения являются справедливыми относительно правил этой грамматики?
Пусть для конечного множества элементов A ={a_1, a_2,… a_n} задано ациклическое отношение r множеством пар [a_k, a_j], принадлежащих отношению. На множестве А можно построить n! различных последовательностей этих элементов - перечислений элементов. Какие утверждения справедливы относительно этих перечислений и их топологической отсортированности?
Какие утверждения справедливы для задачи "Ханойская башня"?
Какие утверждения справедливы о сложности решения задачи о топологической сортировке?
Какие утверждения справедливы относительно представления исходных данных задачи?
Пусть функция h является решением уравнения неподвижной точки F = h(F). Это позволяет дать не рекурсивное определение функции F, аналогично тому, как определяется предел последовательности. Рассмотрим последовательность графов и связанных с ними функций F_0, F_1, … , F_n. Какие утверждения не являются справедливыми относительно такого определения F?
Какие утверждения не справедливы для класса, спроектированного в ходе решения задачи о топологической сортировке?
Какие утверждения являются справедливыми?