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

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

Номер 1

Что используют большинство вычислительных устройств в качестве основных объектов?

Ответ:

(1) только двоичные наборы, целые и символы

(2) только множества

(3) только последовательности

(4) только деревья

Номер 2

Что используется в качестве основных объектов в вычислительной комбинаторике?

Ответ:

(1) целые

(2) вещественные числа

(3) строки

(4) комплексные числа

Номер 3

Что называется основанием системы счисления?

Ответ:

(1) в системе счисления с основанием r каждое положительное целое число имеет единственное представление в виде конечной последовательности (d₀,d₁,d₂,d₃,...,d_k), в которой каждое d_i - целое, удовлетворяющее условию 0≤d_i<r и d_k≠0. Нуль представляется последовательностью (0), r называется основанием системы (r>1)

(2) в системе счисления с основанием d_i каждое положительное целое число имеет единственное представление в виде конечной последовательности (d₀,d₁,d₂,d₃,...,d_k), в которой каждое d_i - целое, удовлетворяющее условию 0≤d_i<r и d_k≠0. Нуль представляется последовательностью (0), d_i называется основанием системы (r>1)

(3) в системе счисления с основанием k каждое положительное целое число имеет единственное представление в виде конечной последовательности (d₀,d₁,d₂,d₃,...,d_k), в которой каждое d_i - целое, удовлетворяющее условию 0≤d_i<r и d_k≠0. Нуль представляется последовательностью (0), k называется основанием системы (r>1)

(4) в системе счисления с основанием (d₀,d₁,d₂,d₃,...,d_k) каждое положительное целое число имеет единственное представление в виде конечной последовательности (d₀,d₁,d₂,d₃,...,d_k), в которой каждое d_i - целое, удовлетворяющее условию 0≤d_i<r и d_k≠0. Нуль представляется последовательностью (0), (d₀,d₁,d₂,d₃,...,d_k) называется основанием системы (r>1)

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

Номер 1

Рациональнее исследовать классы алгоритмов или изучать отдельные алгоритмы?

Ответ:

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

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

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

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

Номер 2

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

Ответ:

(1) путем систематического поиска во множестве деревьев решений, поскольку для любого заданного n в качестве кандидатов требуется рассмотреть лишь конечное число деревьев решений

(2) путем случайного выбора во множестве деревьев решений

(3) путем выбора первого дерева во множестве деревьев решений

(4) путем выбора последнего дерева во множестве деревьев решений

Номер 3

Когда имеет практическое значение техника исчерпывающего поиска?

Ответ:

(1) только для малых значений n

(2) только для больших значений n

(3) только для четных значений n

(4) только для нечетных значений n

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

Номер 1

Можно ли тестированием определить существование лучшего алгоритма для решения той же самой задачи?

Ответ:

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

(2) да

(3) нет

(4) можно многократным тестированием

Номер 3

Какая разница между двумя вопросами: "Какими свойствами обладает данный алгоритм?" и "Какие свойства должен иметь любой алгоритм, решающий данную проблему?"

Ответ:

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

(2) разницы нет

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

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

Комбинаторные алгоритмы для программистов - тест 2