Введение в алгоритмы

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

Номер 1

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

Ответ:

(1) правило

(2) алгоритм

(3) структура

Номер 2

К свойствам алгоритмических процессов следует отнести

Ответ:

(1) дискретность

(2) детерминированность

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

Номер 3

Алгоритмические процессы являются

Ответ:

(1) потенциально конечными

(2) аддитивными

(3) дискретными

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

Номер 1

У разных реализаций одного и того же алгоритма должен быть

Ответ:

(1) терминальный граф

(2) изоморфный граф

(3) контекстный граф

Номер 2

Алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения, носят название

Ответ:

(1) циклические

(2) рекурсивные

(3) коммутативные

Номер 3

Алгоритмы, предназначенные для вычислительных машин, способных выполнять несколько операций одновременно, называются

Ответ:

(1) параллельные

(2) маркированные

(3) модульные

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

Номер 1

Алгоритм, который пытается выдать лучшие результаты путём постоянной подстройки под входные данные, носит название

Ответ:

(1) аддитивный алгоритм

(2) адаптивный алгоритм

(3) априорный алгоритм

Номер 2

Какой тип алгоритмов применяют при сжатии без потерь?

Ответ:

(1) адаптивный

(2) когнитивный

(3) деструктивный

Номер 3

Алгоритм Хаффмана является

Ответ:

(1) вариативным

(2) адаптивным

(3) рекуррентным

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

Номер 1

Алгоритм для нахождения наибольшего общего делителя двух целых чисел носит название?

Ответ:

(1) алгоритм Диффи-Хеллмана

(2) алгоритм Коши

(3) алгоритм Евклида

Номер 2

Алгоритм для нахождения наибольшей общей меры двух однородных величин носит название

Ответ:

(1) алгоритм Крамера

(2) алгоритм Евклида

(3) алгоритм Марка

Номер 3

Что представляет собой соотношение Безу?

Ответ:

(1) наименьшее общее кратное

(2) наибольший общий делитель

(3) наибольшее общее кратное

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

Номер 1

К задачам теории алгоритмов относят

Ответ:

(1) формальное доказательство алгоритмической неразрешимости задач

(2) асимптотический анализ сложности алгоритмов

(3) классификацию алгоритмов в соответствии с классами сложности

Номер 2

К ветвям теории алгоритмов следует отнести

Ответ:

(1) классическую теорию алгоритмов

(2) теорию асимптотического анализа алгоритмов

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

Номер 3

Оценка функции трудоёмкости алгоритма называется

Ответ:

(1) степенью

(2) глубиной

(3) сложностью

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

Номер 1

Машина Тьюринга является

Ответ:

(1) терминальной вычислительной машиной

(2) абстрактной вычислительной машиной

(3) комплексной вычислительной машиной

Номер 2

Машина Тьюринга является расширением

Ответ:

(1) терминального автомата

(2) аддитивного автомата

(3) конечного автомата

Номер 3

Управляющее устройство машины Тьюринга работает согласно:

Ответ:

(1) правилам аддитивности

(2) правилам перехода

(3) правилам модульности

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

Номер 1

Если каждой комбинации состояния и ленточного символа в таблице соответствует правило, машина Тьюринга называется

Ответ:

(1) априорной

(2) комплексной

(3) детерминированной

Номер 2

На Машине Тьюринга можно имитировать

Ответ:

(1) аддитивный алгоритм Лагранжа

(2) машину Поста

(3) нормальные алгоритмы Маркова

Номер 3

Исполнители, для которых возможна имитация машины Тьюринга, называются

Ответ:

(1) полными по Тьюрингу

(2) универсальными по Тьюрингу

(3) статическими по Тьюрингу

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

Номер 1

Тезис Чёрча - Тьюринга гласит, что любая интуитивно вычислимая функция является

Ответ:

(1) невычислимой

(2) частично вычислимой

(3) абсолютно вычислимой

Номер 2

Физический тезис Чёрча - Тьюринга гласит, что любая функция, которая может быть вычислена физическим устройством, может быть вычислена

Ответ:

(1) алгоритмом Коши

(2) машиной Тьюринга

(3) с помощью ряда Эйлера

Номер 3

Положение о том, что любая интуитивно вычислимая функция является частично вычислимой, лежит в основе

Ответ:

(1) теоремы Кронекера

(2) тезиса Чёрча - Тьюринга

(3) аксиомы Гёделя

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

Номер 1

Непустое множество дискретной природы носит название

Ответ:

(1) контейнер

(2) алфавит

(3) модуль

Номер 2

Элементы алфавита называют

Ответ:

(1) символами

(2) маркерами

(3) идентификаторами

Номер 3

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

Ответ:

(1) строка

(2) слово

(3) модуль

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

Номер 1

Число символов в слове называют

Ответ:

(1) величиной

(2) размером

(3) длиной

Номер 2

Слово длины 0 называется

Ответ:

(1) пустым

(2) априорным

(3) модульным

Номер 3

Множество всех слов в алфавите с операцией конкатенации образует

Ответ:

(1) полипоид

(2) моноид

(3) аксоид

Введение в алгоритмы - тест 1