Вход | Регистрация
Тесты онлайн, бесплатный конструктор тестов. Психологические тестирования, тесты на проверку знаний.

Список вопросов базы знаний

Методы оптимизации (магистр, курс 2)

  • Страница:
  • 1
  • 2
  • 3
  • 4
  • 5
Вопрос id:584595

Если задача Z ⊂ NP, то существует такой полином р(n), что задача

Z может быть решена детерминированным алгоритмом с временной сложностью

?)
?)
?)
?)
Вопрос id:584596

Какое из следующих утверждений истинно?

Свойство детерминированности алгоритма означает, что

А) Алгоритм всегда останавливается после фиксированного числа шагов

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

?) А – нет, В – нет
?) A – да, B – да
?) A – да, B - нет
?) A – нет, B – да
Вопрос id:584597

Какое из следующих утверждений истинно?

А) Алгоритм нахождения корней квадратного уравнения является дискретным и детерминированным

В) Алгоритм нахождения корней квадратного уравнения является конечным и массовым

?) A – нет, B – да
?) A – нет, B - нет
?) A – да, B – нет
?) А – да, В – да
Вопрос id:584598

Какое из следующих утверждений истинно?

А) Любая NP может быть сведена к NP-полной задаче

В) Любая NP может быть сведена к P-задаче

?) A – нет, B – нет
?) A – да, B – да
?) A – да, B - нет
?) A – нет, B - да
Вопрос id:584599

Какое из следующих утверждений истинно?

А) Понятие частично-рекурсивной функции - строгое математическое понятие

В) Понятие частично-рекурсивной функции – логическое понятие

?) А – да, В – нет
?) A – нет, B - да
?) A – да, B – да
?) A – нет, B – нет
Вопрос id:584600

Какое из следующих утверждений истинно?

А) Тезис Черча - это не теорема, а утверждение, которое связывает понятие алгоритма и строгое математическое понятие частично-рекурсивной функции

В) Тезис Черча нельзя доказать

?) A – нет, B - нет
?) A – нет, B – да
?) А – да, В – да
?) A – да, B – нет
Вопрос id:584601

Какое из следующих утверждений истинно?

А) Функция называется примитивно - рекурсивной, если она может быть получена из простейших функций обнуления и следования

В) Функция называется примитивно - рекурсивной, если она может быть получена из простейших функций обнуления и проектирования

?) A – да, B – да
?) А – нет, В – нет
?) A – нет, B – да
?) A – да, B - нет
Вопрос id:584602

Какое из следующих утверждений истинно?

А) Хотя класс частично-рекурсивных функций содержит только функции, определенные на множестве натуральных чисел, это не снижает общности представления об алгоритме.

В) Хотя класс частично-рекурсивных функций содержит только функции, определенные на множестве действительных чисел, это не снижает общности представления об алгоритме.

?) A – да, B – да
?) A – нет, B – да
?) А – да, В – нет
?) A – нет, B - нет
Вопрос id:584603

Какое из следующих утверждений истинно?

А) Для любой машины Тьюринга можно построить эквивалентную машину, работающую на левой полуленте

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

?) A – нет, B – да
?) A – да, B – да
?) А – да, В – нет
?) A – нет, B - нет
Вопрос id:584604

Какое из следующих утверждений истинно?

Функцию (2n+1)! необходимо представить рекурсивно. Схема примитивной рекурсии для этой функции имеет вид

А)

В)

?) A – нет, B - нет
?) A – да, B – нет
?) A – да, B – да
?) А – нет, В – да
Вопрос id:584605

Какое из следующих утверждений истинно?

А) Множество квадратов натуральных чисел рекурсивно перечислимо, так как оно задано уравнением

В) Множество квадратов натуральных чисел перечислимо, так как оно задано уравнением

?) А – да, В – да
?) A – нет, B - да
?) A – нет, B – нет
?) A – да, B – нет
Вопрос id:584606
Алгоритм выполняется детерминированно, если представляющая алгоритм последовательность действий
?) бесконечна
?) на одних и тех же данных всегда выполняется одинаково
?) на различных данных всегда выполняется одинаково
?) конечна
Вопрос id:584607
В качестве начальной информации на ленту машины Тьюринга можно подать
?) любую конечную систему знаков внешнего алфа­вита, расставленную произ­вольным образом по ячейкам
?) любую конечную систему знаков внешнего алфа­вита, расположенную в начале ленты
?) любую конечную систему знаков внутреннего алфа­вита, расставленную произ­вольным образом по ячейкам
?) любую бесконечную систему знаков внешнего алфа­вита, расставленную произ­вольным образом по ячейкам
Вопрос id:584608
В качестве простейших функций в формализации понятия алгоритма на основе частично рекурсивных функций используются
?) пять функций
?) четыре функции
?) две функции
?) три функции
Вопрос id:584609
В одном такте работы машины Тьюторинга управляющая головка может сдвигаться
?) только на одну клетку влево или оставаться на месте
?) только на одну клетку вправо или оставаться на месте
?) только на одну клетку вправо или влево на месте
?) только на одну клетку вправо или влево или оставаться на месте
Вопрос id:584610
Если при входном на ленте А после конечного числа тактов машина Тьюринга останавли­вается, то говорят что
?) машина применима к слову А
?) программа машины не корректна
?) входное слово ошибочно
?) машина не применима к слову А
Вопрос id:584611
Задача называется полной для данного класса, если
?) любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе
?) есть задачи из класса, которые сводятся к такой задаче, и притом сама задача лежит в классе
?) ни одна задача из класса сводится к такой задаче, и притом сама задача лежит в классе
?) любая задача из класса сводится к такой задаче, и притом сама задача не лежит в классе
Вопрос id:584612
Класс DTIME(f(n)) определяется как класс языков,
?) не принимаемых детерминированными машинами Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
?) принимаемых детерминированными машинами Тьюринга, заканчивающими свою работу за время, превосходящее f(n)
?) принимаемых не детерминированными машинами Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
?) принимаемых детерминированными машинами Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
Вопрос id:584613
Классами сложности называются множества вычислительных задач, одинаковых
?) по объему входной информации
?) по размеру используемой памяти
?) по сложности вычисления
?) по объему выходной информации
Вопрос id:584614
Множество М разрешимо тогда и только тогда, когда
?) его дополнение эффективно перечислимо
?) оно эффективно перечислимо
?) оно само и его дополнение эффективно перечислимы
?) оно само эффективно перечислимо, а его дополнение нет
Вопрос id:584615
Нуль- функция в формализации понятия алгоритма на основе частично рекурсивных функций имеет вид
?)
?)
?)
?)
Вопрос id:584616
Управляющая головка машины Тьюринга может
?) передвигаться вдоль ленты и может останавливаться напротив какой-либо клетки и воспринимать символ
?) передвигаться вдоль ленты и может останавливаться напротив какой-либо клетки, но не может воспринимать символ
?) не может передвигаться вдоль ленты и не может останавливаться напротив какой-либо клетки и воспринимать символ
?) передвигаться вдоль ленты и не может останавливаться напротив какой-либо клетки и воспринимать символ
Вопрос id:584617
Функции g и h в рекуррентных соотношениях для функции , если рекурсия проводится по х равны
?)
?)
?)
?)
Вопрос id:584618
Функция выбора в формализации понятия алгоритма на основе частично рекурсивных функций имеет вид
?)
?)
?)
?)
Вопрос id:584619
Функция следования в формализации понятия алгоритма на основе частично рекурсивных функций имеет вид
?)
?)
?)
?)
Вопрос id:584620
Одна из формулировок тезиса Черча звучит так
?) всякий алгоритм может быть реализован
?) всякий алгоритм является частично-рекурсивным
?) не всякий алгоритм может быть реализован частично-рекурсивной функцией
?) всякий алгоритм может быть реализован частично-рекурсивной функцией
Вопрос id:584621
NP-полные задачи – это
?) NР-задачи, для решения которых не существует детерминированного алгоритма, работающего за экспоненциальное время
?) NР-задачи, для решения которых не существует детерминированного алгоритма, работающего за полиномиальное время
?) Р-задачи, для решения которых не существует детерминированного алгоритма, работающего за полиномиальное время
?) Р-задачи, для решения которых не существует детерминированного алгоритма, работающего за экспоненциальное время
Вопрос id:584622
NP-полная задача -
?) задача из класса P, к которой можно свести любую задачу из класса NP за полиномиальное время
?) задача из класса NP, к которой можно свести любую другую задачу из класса NP за экспоненциальное время
?) задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время
?) задача из класса NP, к которой можно свести любую задачу из класса P за полиномиальное время
Вопрос id:584623
Алгоритм быстрой сортировки, в среднем требует только около ___ операций для того, чтобы отсортировать N элементов
?)
?) N log N
?)
?)
Вопрос id:584624
Алгоритм Маркова - это
?) математическая запись алгоритма
?) модель алгоритма, которая рассматривает алгоритм в виде набора инструкций для некоторой формальной вычислительной машины
?) модель алгоритма, которая рассматривает алгоритм в виде набора инструкций для персонального компьютера
?) языковый подход к понятию алгоритма, в основе которого лежит формализация процесса преобразования записей исходных данных в запись результатов
Вопрос id:584625
Большинство экспоненциальных алгоритмов - это алгоритмы
?) у которых сложность вычислений падает при увеличении длины входных данных
?) полного перебора
?) у которых сложность вычислений не зависит от длины входных данных
?) подсчета числа вариантов
Вопрос id:584626
В каждую ячейку ленты машины Тьюринга может быть
?) записано не более двух символов внешнего алфавита
?) записано не более двух символов внутреннего алфавита
?) записан один символ внутреннего алфавита
?) записан один символ внешнего алфавита
Вопрос id:584627
Внешний алфавит машины Тьюринга - это
?) конечное множество символов, которыми характеризуются состояния машины
?) бесконечное множество символов, которыми характеризуются состояния машины
?) конечное множество символов, которыми кодируется входная информация
?) бесконечное множество символов, которыми кодируется входная информация
Вопрос id:584628
Внешняя память машины Тьюринга – это
?) набор символов внешнего алфавита
?) набор символов внутреннего алфавита
?) бесконечная в обе стороны лента
?) конечная в обе стороны лента
Вопрос id:584629
Внутренний алфавит машины Тьюринга - это
?) конечное множество символов, которыми кодируется входная информация
?) бесконечный набор символов, характеризующих состояния машины
?) конечный набор символов, характеризующих состояния машины
?) бесконечное множество символов, которыми кодируется входная информация
Вопрос id:584630
Всякая задача, разрешимая за полиномиальное время детерминированным алгоритмом,
?) разрешима за экспоненциальное время недетерминированным алгоритмом
?) не разрешима за полиномиальное время недетерминированным алгоритмом
?) разрешима за экспоненциальное время детерминированным алгоритмом
?) разрешима за полиномиальное время недетерминированным алгоритмом
Вопрос id:584631
Две машины Тьюринга с одинаковой программой
?) различаются по составу внутреннего алфавита
?) неразличимы
?) различаются по составу внешнего алфавита
?) различимы
Вопрос id:584632
Для класса Р и NP-задач справедливо соотношение
?)
?)
?)
?)
Вопрос id:584633
Для любой машины Тьюринга в качестве размера задачи удобно выбрать
?) длину входной цепочки
?) время работы машины Тьюринга
?) длину выходной цепочки
?) величину используемой памяти
Вопрос id:584634
Если все возможные варианты запуска экземпляров недетерминированного алгоритма Т не получили решения, значит
?) задача имеет много решений
?) решение задачи не существует
?) задача имеет два решения
?) задача поставлена неверно
Вопрос id:584635
Если машина Тьюринга при входном слове А никогда не останавливается, то говорят что
?) машина не применима к слову А
?) программа машина составлена некорректно
?) слово А записано неверно
?) машина применима к слову А
Вопрос id:584636
Если сравнивать полиномиальные и экспоненциальные алгоритмы, то полиномиальные алгоритмы
?) не сравнимы с экспоненциальными, так как используются для разных задач
?) считаются более предпочтительными по сравнению с экспоненциальными
?) считаются менее предпочтительными по сравнению с экспоненциальными
?) считаются равноценны экспоненциальным
Вопрос id:584637
Задача называется трудно решаемой, если для ее решения
?) существует полиномиальный алгоритм ее решения
?) не существует экспоненциального алгоритма
?) не существует полиномиального алгоритма
?) существует экспоненциальный алгоритм ее решения
Вопрос id:584638
Класс DSPACE(f(n)) обозначает класс языков,
?) принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
?) принимаемых детерминированными машинами Тьюринга, использующих более f(n) ячеек памяти на рабочей ленте
?) принимаемых недетерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
?) не принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
Вопрос id:584639
Класс NSPACE(f(n)) определяют как класс языков,
?) принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
?) не принимаемых недетерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
?) не принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
?) принимаемых недетерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
Вопрос id:584640
Класс NTIME(f(n)) определяют как класс языков,
?) принимаемых недетерминированной машиной Тьюринга, заканчивающими свою работу за время, превосходящее f(n)
?) принимаемых недетерминированной машиной Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
?) не принимаемых недетерминированной машиной Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
?) принимаемых детерминированной машиной Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
Вопрос id:584641
Класс задач, для решения которых существует недетерминированный алгоритм, решающий эту задачу за полиномиальное время, называется классом
?) Р-задач
?) NP-задач
?) полиномиальных задач
?) экспоненциальных задач
Вопрос id:584642
Любой алгоритм обрабатывает исходные данные
?) конечной длины, причем эти данные представлены в бесконечном алфавите
?) бесконечной длины, причем эти данные представлены в конечном алфавите
?) конечной длины, причем эти данные представлены в двоичном алфавите
?) конечной длины, причем эти данные представлены в конечном алфавите
Вопрос id:584643
Машина Тьюринга - это автомат, который
?) имеет считывающую головку и управляющее устройство
?) имеет потенциально бесконечную в обе стороны ленту, считывающую головку
?) имеет конечную ленту, считывающую головку и управляющее устройство
?) имеет потенциально бесконечную в обе стороны ленту, считывающую головку и управляющее устройство
Вопрос id:584644
Машина Тьюринга – это
?) модель персонального компьютера
?) набор инструкций по решению задачи для реализации на ЭВМ
?) модель алгоритма, которая рассматривает алгоритм в виде набора инструкций для персонального компьютера
?) модель алгоритма, которая рассматривает алгоритм в виде набора инструкций для некоторой формальной вычислительной машины
  • Страница:
  • 1
  • 2
  • 3
  • 4
  • 5
Copyright testserver.pro 2013-2024 - AppleWebKit