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

1) алфавит

2) буква

3) слово

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

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

2) буквами

3) словами

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

1) алфавит

2) буква

3) слово

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

1) Ø

2) Ʌ

3) 0

4) ..

1) abbbb

2) bbabb

3) babbb

4) bbbba

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1)

2)

3)

4)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) S0

2) q0

3) S1

4) q1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) O(log n)

2) O(n)

3) O(n2)

4) O(n*log n)

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

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

3) среднего

4) любого

1) P классу

2) NP-трудным

3) NP-полным

4) E классу

1) n3

2) n3/2

3) 2n

4) n2

1) n3

2) n2*log n

3) 2n

4) n2

1) классом E

2) NP-полными

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

4) классом P

1) P класс

2) NP класс

3) E класс

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

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

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

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

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

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

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

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

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

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

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

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

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

1) P класса

2) NP-трудной

3) NP-полной

4) E класса

1) P класса

2) NP-трудной

3) NP-полной

4) E класса

1) P класса

2) NP-трудной

3) NP-полной

4) E класса

1) O(n)

2)

3) O(n2)

4) O(n*log n)

1) O(n)

2)

3) O(n2)

4) O(n*log n)

1) P класса

2) NP-трудной

3) NP-полной

4) E класса