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

Правильный ответ:

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

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

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

поскольку функция добавляет пары и строит новые пары в множество , то свойство никогда выполняться не может

по определению граф и соответственно сама функция представляет объединение всех

• # В привычном для нас мире десятичной системы счисления незыблемой истиной считается, что 2 * 2 = 4. В двоичной системе счисления такая запись просто невозможна, поскольку нет ни цифр 2, ни 4. А в какой системе счисления с основанием p справедлива запись 2 * 2 = 11?
• # Укажите, какие утверждения справедливы для топологической сортировки:
• # Какие из структур данных относятся к распределителям?
• # Рекурсивное определение напоминает фокус. Рассмотрим рекурсивное определение известной в математике функции: Совершенно очевидно, какие значения принимает эта функция при . А каковы ее значения при ? Оказывается, для таких функция имеет одно и то же значение. Какое?
• # Наряду с четырьмя классическими стратегиями решения задач - последовательность, выбор, цикл и процедура - рекурсия представляет пятую классическую стратегию. Какое из утверждений не является справедливым для этой стратегии?