Зачет по дисциплине: Алгоритмы и алгоритмические языки. Билет 95

Ответы на Итоговый тест по дисциплине Алгоритмы и алгоритмические языки
Вопросы теста:
Введение в теорию алгоритмов
1.1 Что из перечисленного НЕ является свойством алгоритма:
а) Дискретность б) Детерминированность в) Многозначность г) Понятность д) Массовость
1.2 Эвристический алгоритм – это :
а) это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя.
б) набор команд (указаний), выполняемых последовательно во времени друг за другом.
в) алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
г) алгоритм, который дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
д) алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными.
е) алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.
1.3 Вспомогательный (подчиненный) алгоритм – это
а) это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя.
б) набор команд (указаний), выполняемых последовательно во времени друг за другом.
в) алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
г) алгоритм, который дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
д) алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными.
е) алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.
1.4 Разветвляющийся алгоритм – это:
а) это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя.
б) набор команд (указаний), выполняемых последовательно во времени друг за другом.
в) алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
г) алгоритм, который дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
д) алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными.
е) алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.
1.7 Вероятностный (стохастический) алгоритм – это:
а) это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя.
б) набор команд (указаний), выполняемых последовательно во времени друг за другом.
в) алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
г) алгоритм, который дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
д) алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными.
е) алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.
1.9 Множество М называется разрешимым
а) если существует алгоритм, позволяющий перечислить все элементы этого множества (возможно с повторениями).
б) тогда и только тогда, когда оно само и его дополнение эффективно перечислимы.
в) если для него существует алгоритм, решающий проблему вхождения слова x в М.
1.11 Если множества М и L эффективно перечислимы, то
а) эффективно перечислимы множества M  L и M  L.
б) эффективно перечислимы множества M  L и M  L.
в) разрешимы множества M  L и M  L.
г) разрешимы множества M  L и M  L.
1.12 Свойство, означающее, что процесс решения задачи, определяемый алгоритмом, расчленен на отдельные элементарные шаги, соответствует
а) дискретности б) детерминированности в) результативности г) массовости
Основы классической теории алгоритмов
2.2 К числу простейших функций НЕ относят:
а) оператор позиционирования б) оператор аннулирования в) оператор сдвига г) оператор проектирования
2.5 В подходах к определению понятия алгоритма можно выделить ... основных направления:
а) 3 б) 5 в) 2 г) 4
2.6 Слово р называется подсловом слова q,
а) если слово p можно представить в виде p=qr, где r - любое слово, в том числе и пустое.
б) если слово q можно представить в виде q=pr, где r - любое слово, в том числе и пустое.
в) если слово r можно представить в виде r=pq, где r - любое слово, в том числе и пустое.
2.7 Машина Тьюринга представляет собой (абстрактное) устройство, состоящее из :
а) считывающей головки б) лентопротяжного механизма в) проектора г) управляющего устройства д) ленты
2.10 Команда машины Тьюринга состоит из
а) символа внешнего алфавита, символа внутреннего алфавита, сдвига
б) подстроки P, символа→, строки Q
в) номера состояния ленты МТ, символа алфавита и сдвига
г) номера команды, знака команды, номера следующей команды
2.11 . Фрагмент программы машины Поста 1.→2 2. ?(1, 3) определяет :
а) Движение влево до первой метки б) Движение вправо до первой метки в) Движение влево до первой пустой ячейки г) Нахождение метки и её удаление.
2.12 На каждом шаге алгоритм Маркова ищет подстановку
а) начиная с первой б) проверяет последнюю успешную подстановку в) проверяет подстановку, следующую за последней успешной.
2.13 Нормальный алгоритм Маркова стоит из: а) множества состояний б) команды движения каретки в) системы подстановок г) ленты д) алфавита
Основы алгоритмической теории формальных языков
3.3 При графическом описании грамматики нетерминальный символ (или цепочка символов) обозначается
а) прямоугольником, в который вписано обозначение символа
б) овалом, кругом или прямоугольником с закругленными краями, внутрь которого вписана цепочка
в) жирной точкой или закрашенным кружком
3.5 Грамматика — это
а) совокупность элементарных конструкций языка
б) это упорядоченная пара цепочек символов ( )
в) описание способа построения предложений некоторого языка.
3.6 Правило (или продукция) — это
а) совокупность элементарных конструкций языка
б) это упорядоченная пара цепочек символов ( )
в) описание способа построения предложений некоторого языка.
3.8 Тип 0: грамматики с фразовой структурой –
а) в него подпадают все без исключения формальные грамматики
б) не существует
в) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: A2->2, где 12V * , A VN, V + ; грамматики G(VT,VN,P,S), V = VNVT имеют правила вида ->, где , V + , ||>=||
г) к типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные.
д) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: A->, где A VN, V + .
3.10 Тип 2: контекстно-свободные (КС) грамматики
а) в него подпадают все без исключения формальные грамматики
б) не существует
в) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: A2->2, где 12V * , A VN, V + ; грамматики G(VT,VN,P,S), V = VNVT имеют правила вида ->, где , V + , ||>=||
г) к типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные.
д) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: A->, где A VN, V + .
3.11 Тип 3: регулярные грамматики
а) в него подпадают все без исключения формальные грамматики
б) не существует
в) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: A2->2, где 12V * , A VN, V + ; грамматики G(VT,VN,P,S), V = VNVT имеют правила вида ->, где , V + , ||>=||
г) к типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные.
д) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: A->, где A VN, V + .
3.12 Тип 4: дискретные грамматики
а) в него подпадают все без исключения формальные грамматики
б) не существует
в) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: A2->2, где 12V * , A VN, V + ; грамматики G(VT,VN,P,S), V = VNVT имеют правила вида ->, где , V + , ||>=||
г) к типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные.
д) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: A->, где A VN, V + .
3.13 Набор правил, определяющий допустимые конструкции языка называется
а) Синтаксисом языка б) Семантикой языка в) Лексикой языка г) Алфавитом языка
3.14 Язык можно задать:
а) Перечислением всех допустимых цепочек языка.
б) Определением семантики всех допустимых цепочек
в) Определением метода распознавания цепочек языка
г) Указанием способа порождения цепочек языка (заданием грамматики языка)
д) Определением множества допустимых операций над цепочками
Основы теории сложности
4.1 O(1)константная сложность:
а) Большинство операций в программе выполняются только раз или только несколько раз. Время выполнения алгоритма не зависит от размера входных данных.
б) Алгоритмы, в которых элементы входных данных обрабатываются во вложенных циклах: двойные циклы - квадратичная сложность О(N2); циклы глубины 3 - кубическая сложность О(N3)
в) Алгоритмы, в которых каждый элемент входных данных требуется обработать лишь линейное число раз. Время работы программы линейно зависит от размера входных данных.
г) Алгоритмы, в которых большая задача делится на несколько небольших подзадач, они решаются по отдельности, но для получения общего решения нужно соединить решения отдельных задач (например, в алгоритме построения кода Хаффмана).
д) Алгоритмы, в которых большая задача делится на несколько небольших подзадач, они решаются по отдельности (например, в алгоритме построения кода Шеннона-Фано).
е) Такие алгоритмы чаще всего возникают в результате подхода, именуемого метод грубой силы.
4.2 O(N) линейная сложность:
а) Большинство операций в программе выполняются только раз или только несколько раз. Время выполнения алгоритма не зависит от размера входных данных.
б) Алгоритмы, в которых элементы входных данных обрабатываются во вложенных циклах: двойные циклы - квадратичная сложность О(N2); циклы глубины 3 - кубическая сложность О(N3)
в) Алгоритмы, в которых каждый элемент входных данных требуется обработать лишь линейное число раз. Время работы программы линейно зависит от размера входных данных.
г) Алгоритмы, в которых большая задача делится на несколько небольших подзадач, они решаются по отдельности, но для получения общего решения нужно соединить решения отдельных задач (например, в алгоритме построения кода Хаффмана).
д) Алгоритмы, в которых большая задача делится на несколько небольших подзадач, они решаются по отдельности (например, в алгоритме построения кода Шеннона-Фано).
е) Такие алгоритмы чаще всего возникают в результате подхода, именуемого метод грубой силы.
4.4 O(Log(N)) логарифмическая сложность:
а) Большинство операций в программе выполняются только раз или только несколько раз. Время выполнения алгоритма не зависит от размера входных данных.
б) Алгоритмы, в которых элементы входных данных обрабатываются во вложенных циклах: двойные циклы - квадратичная сложность О(N2); циклы глубины 3 - кубическая сложность О(N3)
в) Алгоритмы, в которых каждый элемент входных данных требуется обработать лишь линейное число раз. Время работы программы линейно зависит от размера входных данных.
г) Алгоритмы, в которых большая задача делится на несколько небольших подзадач, они решаются по отдельности, но для получения общего решения нужно соединить решения отдельных задач (например, в алгоритме построения кода Хаффмана).
д) Алгоритмы, в которых большая задача делится на несколько небольших подзадач, они решаются по отдельности (например, в алгоритме построения кода Шеннона-Фано).
е) Такие алгоритмы чаще всего возникают в результате подхода, именуемого метод грубой силы.
4.6 O(2N) экспоненциальная сложность:
а) Большинство операций в программе выполняются только раз или только несколько раз. Время выполнения алгоритма не зависит от размера входных данных.
б) Алгоритмы, в которых элементы входных данных обрабатываются во вложенных циклах: двойные циклы - квадратичная сложность О(N2); циклы глубины 3 - кубическая сложность О(N3)
в) Алгоритмы, в которых каждый элемент входных данных требуется обработать лишь линейное число раз. Время работы программы линейно зависит от размера входных данных.
г) Алгоритмы, в которых большая задача делится на несколько небольших подзадач, они решаются по отдельности, но для получения общего решения нужно соединить решения отдельных задач (например, в алгоритме построения кода Хаффмана).
д) Алгоритмы, в которых большая задача делится на несколько небольших подзадач, они решаются по отдельности (например, в алгоритме построения кода Шеннона-Фано).
е) Такие алгоритмы чаще всего возникают в результате подхода, именуемого метод грубой силы.
4.8 Если алгоритм имеет экспоненциальную сложность то
а) при увеличении N можем не получить решение задачи физически, т.к. это займёт очень много времени.
б) имеет место значительное преимущество при улучшении технических характеристик компьютера.
в) улучшение технических характеристик практически незаметно.

Уважаемый студент, дистанционного обучения,
Оценена Ваша работа по предмету: Алгоритмы и алгоритмические языки (ДВ 1.1)
Вид работы: Зачет
Оценка:Зачет
Дата оценки: 27.01.2019

Пушкарева Галина Витальевна