Учебные материалы по математике | Теория алгоритмов | Matematiku5
Вузы по математике Готовые работы по математике Как писать работы по математике Примеры решения задач по математике Решить задачу по математике online

Теория алгоритмов


ТЕОРИЯ АЛГОРИТМОВ

1. Всякое не пустое множество символов есть…

1) алфавит

2) буква

3) слово

4) высказывание

2. Символы алфавита называются…

1) алфавитами

2) буквами

3) словами

4) высказываниями

3. Конечная последовательность букв алфавита есть…

1) алфавит

2) буква

3) слово

4) высказывание

4. Пустое слово обозначается:

1) Ø

2) Ʌ

3) 0

4) ..

5. Если P обозначает слово abb и Q обозначает слово bb, то слово PQ обозначает?

1) abbbb

2) bbabb

3) babbb

4) bbbba

6. Нормальный алгоритм в алфавите считается заданным, если…

1) алфавит имеет конечное число букв

2) задана схема формул подстановок

3) входное слово есть в алфавите

4) если выходное слово есть в алфавите

7. Если область определения аргументов и область значений функции есть множество натуральных чисел, то функция называется…

1) геометрической

2) алгебраической

3) арифметической

4) физической

8. Замыкание алгоритма получается путем добавления…

1) бесконечных циклов

2) формулы подстановки Ʌ→● Ʌ

3) замкнутой формулы

4) пустого слова

9. , в алфавите . Нормальный алгоритм A# называется… A на алфавит A2.

1) естественным распространением

2) неестественным распространением

3) алфавитным распространением

4) алгоритмическим распространением

10. … алгоритмов A и B в алфавите A называют алгоритм C такой, что .

1) Импликация

2) Композиция

3) Конъюнкция

4) Дизъюнкция

11. Композиция алгоритмов A и B обозначается:

1)

2)

3)

4)

12. Команда машины Тьюринга «qj Si Sk qr»:

1) перезапись Sk на Si

2) перемещение в левый квадрат

3) перемещение в правый квадрат

4) остановка машины

13. Команда машины Тьюринга «qj Si L qr»:

1) перезапись Sk на Si

2) перемещение в левый квадрат

3) перемещение в правый квадрат

4) остановка машины

14. Команда машины Тьюринга «qj Si R qr»:

1) перезапись Sk на Si

2) перемещение в левый квадрат

3) перемещение в правый квадрат

4) остановка машины

15. Какое из условий необязательно для задания машины Тьюринга?

1) каждая 4-ка символов принадлежит к одному из 3-х типов команд

2) никакие две 4-ки не имеют совпадающие два первых символа

3) всегда есть 4-ка начинающаяся с q0

4) всегда есть 4-ка заканчивающаяся на q0

16. Множество всех символов типа Sm, входящих в команды машины Тьюринга, наз. …

1) внутренними состояниями

2) алфавитом заданной машины

3) аргументами машины

4) выходными значениями

17. Символы qi, входящие в команды машины Тьюринга, наз. …

1) внутренними состояниями

2) алфавитом заданной машины

3) аргументами машины

4) выходными значениями

18. В исходном состоянии машина Тьюринга находится в…

1) S0

2) q0

3) S1

4) q1

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

1) алгоритмически разрешимой

2) алгоритмически неразрешимой

3) математически разрешимой

4) математически неразрешимой

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

1) алгоритмически разрешимой

2) алгоритмически неразрешимой

3) математически разрешимой

4) математически неразрешимой

СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ

1. Сложность описания алгоритма зависит от…

1) выбора того или иного способа задания алгоритма

2) продолжительности алгоритма

3) разветвленности алгоритма

4) цикличности алгоритма

2. Сложность исходных данных понимается как…

1) количество уникальных символов

2) размер их записи

3) сложность их обработки

4) длительность их обработки

3. Сложность вычислений с помощью алгоритма понимается как…

1) продолжительность алгоритма

2) разветвленность алгоритма

3) цикличность алгоритма

4) функция от размера входа алгоритма

4. Временная сложность вычислений характеризует…

1) количество выполненных итераций

2) число операций наихудшего случая

3) количество решенных задач

4) затраченное время

5. Если вход размера n обрабатывается за время cn2 (c — const), то сложность этого алгоритма есть…

1) O(log n)

2) O(n)

3) O(n2)

4) O(n*log n)

6. Под временной сложностью задачи понимается временная сложность… алгоритма, известного для ее решения.

1) наихудшего

2) наилучшего

3) среднего

4) любого

7. Полиномиальные задачи относятся к…

1) P классу

2) NP-трудным

3) NP-полным

4) E классу

8. Какая временная сложность принадлежит P классу?

1) n3

2) n3/2

3) 2n

4) n2

9. Какая временная сложность принадлежит P классу?

1) n3

2) n2*log n

3) 2n

4) n2

10. Множество всех задач, для каждой из которых существует полиномиальный алгоритм, называется…

1) классом E

2) NP-полными

3) NP-трудными

4) классом P

11. Класс задач, которые можно решить недетерминированными алгоритмами, работающими в течение полиномиального времени, называется…

1) P класс

2) NP класс

3) E класс

4) нет правильного ответа

12. Что не входит в класс NP?

1) нахождение целочисленных решений СЛУ

2) выяснение гамильтоновости графа

3) нахождение сумму конечной последовательности

4) задача коммивояжера

13. Что не входит в класс NP?

1) умножение целых чисел

2) выяснение гамильтоновости графа

3) динамическое распределение памяти

4) задача коммивояжера

14. Если одновременно задача Z1 полиномиально сводится к задаче Z2 и Z2 полиномиально сводится к задаче Z1, то задачи Z1 и Z2 …

1) полиномиально равны

2) полиномиально эквивалентны

3) полиномиально неравны

4) полиномиально неэквивалентны

15. Как называется задача, если каждая задача из NP полиномиально сводится к ней?

1) P класса

2) NP-трудной

3) NP-полной

4) E класса

16. Как называется задача, если она входит в NP и каждая задача из NP полиномиально сводится к ней?

1) P класса

2) NP-трудной

3) NP-полной

4) E класса

17. Какого класса задача, если ее алгоритм имеет экспоненциальную временную сложность?

1) P класса

2) NP-трудной

3) NP-полной

4) E класса

18. Какая сложность относится к классу E?

1) O(n)

2)

3) O(n2)

4) O(n*log n)

19. Какая сложность относится к классу E?

1) O(n)

2)

3) O(n2)

4) O(n*log n)

20. Задачи какого класса менее сложные?

1) P класса

2) NP-трудной

3) NP-полной

4) E класса

Наташа

Автор

Наташа — контент-маркетолог и блогер, но все это не мешает ей оставаться адекватным человеком. Верит во все цвета радуги и не верит в теорию всемирного заговора. Увлекается «нефрохиромантией» и тайно мечтает воссоздать дома Александрийскую библиотеку.

Распродажа дипломных

 Скидка 30% по промокоду Diplom2020

А ты боишься COVID-19?

 Пройди опрос и получи промокод