Математические методы моделирования 1-9
Математические методы моделирования программного обеспечения (Тесты 1-9).
после каждого ответа - Отзыв, в котором верный ответ выделен по тексту.
Промежуточный тест 1
Вопрос 1
Машина Тьюринга представляет собой
Выберите один ответ:
автомат с конечным числом состояний и ограниченной памятью, представленной конечной лентой
автомат с конечным числом состояний и неограниченной памятью, представленной бесконечной лентой
автомат с бесконечным числом состояний и ограниченной памятью, представленной конечной лентой
автомат с бесконечным числом состояний и неограниченной памятью, представленной бесконечной лентой
Вопрос 2
Для недетерминированной машины Тьюринга характерно, что
Выберите один ответ:
для каждого входного слова имеется один путь, по которому может развиваться вычисление
для каждого входного слова имеется несколько путей, по которым может развиваться вычисление
для каждой комбинации состояния и ленточного символа в таблице программы управления МТ записано не более одного правила
комбинация текущего состояния автомата и символа на ленте допускает только один переход
Вопрос 3
Что характерно для недетерминированной машины Тьюринга?
Выберите один ответ:
Для каждого входного слова имеется один путь, по которому может развиваться вычисление
Для каждой комбинации состояния и ленточного символа в таблице программы управления МТ записано не более одного правила
Для каждой комбинации состояния и ленточного символа в таблице программы управления МТ может быть записано более одного правила
Комбинация текущего состояния автомата и символа на ленте допускает только один переход
Вопрос 4
Полиноминальная сложность алгоритма обозначается
Выберите один ответ:
О(c^n), где с – константа
О(n)
О(n^c), где с – константа
О(1)
Вопрос 5
Укажите класс языков, принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочих лентах.
Выберите один ответ:
NSPACE(f(n))
NTIME(f(n))
DSPACE(f(n))
DTIME(f(n))
Вопрос 6
Для недетерминированной машины Тьюринга характерно, что
Выберите один или несколько ответов:
для каждой комбинации состояния и ленточного символа в таблице программы управления МТ может быть записано более одного правила
Для каждой комбинации состояния и ленточного символа в таблице программы управления МТ может быть записано НЕ более одного правила
для каждого входного слова имеется несколько путей, по которым может развиваться вычисление
комбинация текущего состояния автомата и символа на ленте может допускать несколько переходов
Вопрос 7
Что характерно для недетерминированной машины Тьюринга?
Выберите один или несколько ответов:
Комбинация текущего состояния автомата и символа на ленте может допускать несколько переходов
Для каждой комбинации состояния и ленточного символа в таблице программы управления МТ может быть записано более одного правила
Для каждого входного слова имеется один путь, по которому может развиваться вычисление
Для каждой комбинации состояния и ленточного символа в таблице программы управления МТ записано не более одного правила
Вопрос 8
Класс языков – это множество языков, допустимых детерминированной машиной Тьюринга с полиномиальным ограничением пространства, обозначается
Выберите один ответ:
DTIME
NSPACE
NTIME
PSPACE
Вопрос 9
Класс языков – это множество языков, допустимых недетерминированной машиной Тьюринга с полиномиальным ограничением пространства, обозначается
Выберите один ответ:
NTIME
NPSPACE
NSPACE
DTIME
Вопрос 10
Для детерминированной машины Тьюринга характерно, что
Выберите один или несколько ответов:
для каждого входного слова имеется несколько путей, по которым может развиваться вычисление
комбинация текущего состояния автомата и символа на ленте может допускать несколько переходов
комбинация текущего состояния автомата и символа на ленте допускает только один переход
для каждого входного слова имеется один путь, по которому может развиваться вычисление
