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

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

Номер 1

Что является предметом теории комбинаторных алгоритмов?

Ответ:

(1) вычисления на дискретных математических структурах

(2) вычисления на непрерывных математических структурах

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

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

Номер 2

По какому направлению развиваются комбинаторные вычисления?

Ответ:

(1) интенсивно изобретаются новые алгоритмы

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

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

Номер 3

Какова одна из важных проблем в комбинаторных вычислениях?

Ответ:

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

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

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

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

Упражнение 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) многократным тестированием можно определить существование лучшего алгоритма для решения той же самой задачи

Номер 2

Какие фундаментальные проблемы существуют в анализе алгоритмов?

Ответ:

(1) проблем нет

(2) поиск свойств, которыми обладает данный алгоритм

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

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

Номер 3

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

Ответ:

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

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

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

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

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