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

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

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

Пусть для конечного множества элементов A ={a_1, a_2,… a_n} задано ациклическое отношение r множеством пар [a_k, a_j], принадлежащих отношению. На множестве А можно построить n! различных последовательностей этих элементов - перечислений элементов. Какие утверждения справедливы относительно этих перечислений и их топологической отсортированности?

(Ответ считается верным, если отмечены все правильные варианты ответов.)
Варианты ответа
перечисление a_1, a_2,… a_n задает топологически отсортированную последовательность для отношения r, если каждая пара из r содержится в множестве пар полного порядка, определенного перечислением(Верный ответ)
перечисление a_1, a_2,… a_n топологически отсортировано для отношения r, если для любого элемента перечисления a_k не существует a_j, где j>k, такого, что пара [a_j, a_k] принадлежит r(Верный ответ)
для перечисления a_1, a_2,… a_n, задающего топологическую сортировку, для любого элемента перечисления a_j существует элемент a_k, являющийся предшественником a_j в отношении r
каждое перечисление a_1, a_2,… a_n задает полный порядок. Пара [a_k, a_j] принадлежит этому порядку, если j>k(Верный ответ)
Похожие вопросы
Пусть функция h является решением уравнения неподвижной точки F = h(F). Это позволяет дать не рекурсивное определение функции F, аналогично тому, как определяется предел последовательности. Рассмотрим последовательность графов и связанных с ними функций F_0, F_1, … , F_n. Какие утверждения не являются справедливыми относительно такого определения F?
Пусть аргументом функции h является множество пар целых чисел. Пусть также функция h:
  • добавляет в множество пару [0,0];
  • если в множестве есть пара [i, S] и i<n, то в множество добавляется пара [i+1, S+ i +1]
    •  Для какой рекурсивно определенной функции F(n), где n>=0, функция h является решением уравнения неподвижной точки F = h(F)?
    Рассмотрим конечное множество из пяти элементов. Пусть на этом множестве задано отношение r, содержащее только одну пару элементов. Сколько различных топологически отсортированных отношением r последовательностей можно построить?
    Рекурсивное определение можно рассматривать как уравнение неподвижной точки F = h(F). Пусть функция h является решением этого уравнения. Какие утверждения справедливы для этой функции?
    Рекурсивное определение функции F можно рассматривать как уравнение неподвижной точки F = h(F). Какие утверждения справедливы для этого уравнения?
    Рекурсивное определение напоминает фокус. Рассмотрим рекурсивное определение известной в математике функции:
    F(n) = n – 10,\text{ если }n > 100\\ F(n) = F(F(n + 11),\text{ если }n <= 100
    Совершенно очевидно, какие значения принимает эта функция при n> 100. А каковы ее значения при n< 101? Оказывается, для таких n функция имеет одно и то же значение. Какое?
    Структуры данных, используемые в алгоритме топологической сортировки, работают не с самими элементами множества, а с их номерами. Какие утверждения справедливы относительно возможного типа сортируемых элементов в предлагаемой реализации алгоритма?
    Какими свойствами обладает отношение строгого полного (тотального) порядка на множестве А? Отношение полного строгого порядка:
    Пусть Т - полное бинарное дерево (каждый узел не являющийся листом дерева имеет двух потомков) число листьев в котором равно 2^m. Для обхода дерева применяется инфиксная процедура обхода (обойти левое дерево, обойти корень, обойти правое дерево). Каким по счету будет посещен корень дерева, если счет узлов начинается с 1)?
    Гарри Поттер ищет важную для него информацию. Он надеется, что она может быть в одной из книг библиотеки Хогварда, содержащей N книг. Гарри наугад выбирает книгу и просматривает ее содержимое, на что у него уходит T минут. При неудаче он повторяет поиск, выбирая новую книгу. Для такого алгоритма поиска каковы значения времени поиска: минимальное, максимальное, в среднем?