| engineerklub | Дата: Суббота, 15.10.2022, 07:10 | Сообщение # 1 |
 Генералиссимус
Группа: Администраторы
Сообщений: 29572
Статус: Offline
| Алгоритмы и алгоритмические языки. Билет 23
Тип работы: Работа Зачетная
Форматы файлов: Microsoft Word
Сдано в учебном заведении: ДО СИБГУТИ
Описание:
Билет №23
Введение в теорию алгоритмов
1.2 Эвристический алгоритм – это:
а) это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя.
б) набор команд (указаний), выполняемых последовательно во времени друг за другом.
в) алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
г) алгоритм, который дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
д) алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными.
е) алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.
1.3 Вспомогательный (подчиненный) алгоритм – это
а) это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя.
б) набор команд (указаний), выполняемых последовательно во времени друг за другом.
в) алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
г) алгоритм, который дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
д) алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными.
е) алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.
1.5 Циклический алгоритм – это:
а) это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя.
б) набор команд (указаний), выполняемых последовательно во времени друг за другом.
в) алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
г) алгоритм, который дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
д) алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными.
е) алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.
1.7 Вероятностный (стохастический) алгоритм – это:
а) это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя.
б) набор команд (указаний), выполняемых последовательно во времени друг за другом.
в) алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
г) алгоритм, который дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
д) алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными.
е) алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.
1.9 Множество М называется разрешимым
а) если существует алгоритм, позволяющий перечислить все элементы этого множества (возможно с повторениями).
б) тогда и только тогда, когда оно само и его дополнение эффективно перечислимы.
в) если для него существует алгоритм, решающий проблему вхождения слова x в М.
1.10 Множество М называется эффективно перечислимым, если
а) если существует алгоритм, позволяющий перечислить все элементы этого множества (возможно с повторениями).
б) тогда и только тогда, когда оно само и его дополнение эффективно перечислимы.
в) если для него существует алгоритм, решающий проблему вхождения слова x в М
СКАЧАТЬ
|
| |
| |
| engineerklub | Дата: Суббота, 15.10.2022, 07:11 | Сообщение # 2 |
|
Генералиссимус
Группа: Администраторы
Сообщений: 29572
Статус: Offline
| 1.11 Если множества М и L эффективно перечислимы, то
а) эффективно перечислимы множества M L и M L.
б) эффективно перечислимы множества M L и M L.
в) разрешимы множества M L и M L.
г) разрешимы множества M L и M L.
1.12 Свойство, означающее, что процесс решения задачи, определяемый алгоритмом, расчленен на отдельные элементарные шаги, соответствует
а) дискретности
б) детерминированности
в) результативности
г) массовости
Основы классической теории алгоритмов
2.3 Согласно тезису Чёрча-Клини:
а) каждая интуитивно вычислимая функция является частично рекурсивной.
б) каждая рекурсивная функция является вычислимой.
в) каждая интуитивно вычислимая функция является частично рекурсивной.
г) каждая интуитивно вычислимая функция является общерекурсивной.
2.4 Функция f(x1, x2,…, xn) называется общерекурсивной,
а) если она может быть получена за конечное число шагов из простейших функций при помощи операций суперпозиции, схем примитивной рекурсии и -оператора.
б) если она частично рекурсивна и всюду определена.
в) если она не может быть получена за конечное число шагов из простейших функций при помощи операций суперпозиции, схем примитивной рекурсии и -оператора.
г) если она частично рекурсивна и определена только в конкретном диапазоне значений.
2.5 В подходах к определению понятия алгоритма можно выделить … основных направления:
а) 3 б) 5 в) 2 г) 4
2.6 Слово р называется подсловом слова q,
а) если слово p можно представить в виде p=qr, где r - любое слово, в том числе и пустое.
б) если слово q можно представить в виде q=pr, где r - любое слово, в том числе и пустое.
в) если слово r можно представить в виде r=pq, где r - любое слово, в том числе и пустое.
2.8 Существует ли машина Тьюринга T0, решающая проблему остановки для произвольной машины Тьюринга T:
а) нет б) да.
2.9 Остановка МТ происходит, когда
а) выполнена последняя подстановка
б) в состоянии P0 машина остается на месте
в) не изменяется символ внутреннего алфавита
г) не изменяется символ внешнего алфавита, состояние МТ остается неизменным, сдвиг – нулевой.
2.11 . Фрагмент программы машины Поста 1.→2 2. ?(1, 3) определяет :
а) Движение влево до первой метки
б) Движение вправо до первой метки
в) Движение влево до первой пустой ячейки
г) Нахождение метки и её удаление.
2.13 Нормальный алгоритм Маркова стоит из:
а) множества состояний
б) команды движения каретки
в) системы подстановок
г) ленты
д) алфавита
Основы алгоритмической теории формальных языков
3.1Операция объединения или сложения двух цепочек символов, это
а) Конкатенация
б) Обращение
в) Итерация
г) Ассоциация
3.3 При графическом описании грамматики нетерминальный символ (или цепочка символов) обозначается
а) прямоугольником, в который вписано обозначение символа
б) овалом, кругом или прямоугольником с закругленными краями, внутрь которого вписана цепочка
в) жирной точкой или закрашенным кружком
3.6 Правило (или продукция) — это
а) совокупность элементарных конструкций языка
б) это упорядоченная пара цепочек символов()
в) описание способа построения предложений некоторого языка.
3.7 Существует … типа грамматик Хомскому
а)4
б)5
в)2
г)3
3.8 Тип 0: грамматики с фразовой структурой –
а) в него подпадают все без исключения формальные грамматики
б) не существует
в) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида:
СКАЧАТЬ
|
| |
| |
