Предмет Математическая логика и теория алгоритмов
1. В неориентированном графе G эйлеров цикл существует тогда и только тогда, когда
Выберите один ответ:
a. число вершин нечетной степени равно 2
b. число вершин нечетной степени равно 0 или 2
c. нет вершин нечетной степени
d. число вершин нечетной степени равно 4
Вопрос 2
Какой математик заложил основы теории графов как математической науки?
Выберите один ответ:
a. Леонард Эйлер
b. Рене Декарт
c. Пифагор
d. Евклид
Вопрос 3
Какое из утверждений является верным?
Выберите один ответ:
a. Каждый тождественно истинный предикат является выполнимым.
b. Каждый не тождественно ложный предикат является тождественно истинным.
c. Каждый выполнимый предикат является тождественно истинным.
d. Каждый опровержимый предикат является тождественно ложным.
Вопрос 4
В каком случае дизъюнкция двух высказываний является ложной?
Выберите один ответ:
a. Оба исходных высказывания ложны
b. Дизъюнкция всегда истинна
c. Оба высказывания истинны
d. Хотя бы одно высказывание ложно
Вопрос 5
Что означает команда 2 <- q2 для машины Тьюринга?
Выберите один ответ:
a. заменить символ на 2, переместить каретку влево на одну ячейку и перейти в состояние q2.
b. найти символ 2 и заменить его символом q2.
c. найти символ 2, переместить его влево на одну ячейку, заменяя полученную пустую ячейку символом q2.
d. заменить символ на q2, переместить каретку влево на одну ячейку и записать в нее 2.
Вопрос 6
В каком случае импликация двух высказываний p->q является ложной?
Выберите один ответ:
a. Импликация всегда истинна
b. Когда р - ложно, а q - истинно
c. Когда р - истинно, а q - ложно
d. Когда оба высказывания ложны
Вопрос 7
Высказывание - это
Выберите один ответ:
a. предложение, которое ложно
b. повествовательное предложение, истинность которого установить невозможно
c. повествовательное предложение, которое либо истинно, либо ложно
d. предложение, которое истинно
Вопрос 8
В неориентированном графе G эйлерова цепь существует тогда и только тогда, когда
Выберите один ответ:
a. число вершин нечетной степени равно 0 или 2
b. число вершин нечетной степени равно 4
c. число вершин нечетной степени равно 0
d. число вершин нечетной степени равно 2
Вопрос 9
Какое из предложений является одноместным предикатом?
Выберите один ответ:
a. sin x + 7
b. x + y = 5
c. Париж является столицей Франции.
d. Город х является столицей России.
Вопрос 10
Множество вершин такое, что из любой вершины этого множества есть путь в любую другую вершину этого множества, причем ни из какой вершины этого множества нельзя проложить путь в какую-либо вершину, не принадлежащую этому множеству, называется
Выберите один ответ:
a. Связностью.
b. Компонентой связности.
c. Псевдографом.
d. Подграфом.
Вопрос 11
Связный граф без циклов называется
Выберите один ответ:
a. Псевдографом.
b. Планарным.
c. Деревом.
d. Подграфом.
Вопрос 12
Какое из предложений является двухместным предикатом?
Выберите один ответ:
a. - 3 < - 7
b. Река х впадает в Черное море.
c. x - 2 = 1
d. х2 + y2 = 4
Вопрос 13
В каком случае строгая дизъюнкция двух высказываний является истинной?
Выберите один ответ:
a. Строгая дизъюнкция всегда истинна
b. Когда оба высказывания ложны
c. Когда оба высказывания истинны
d. Когда лишь одно из высказываний истинно
Вопрос 14
Матрица смежности неориентированного графа
Выберите один ответ:
a. Не является квадратной.
b. Не является симметричной.
c. Единичная.
d. Симметрична.
Вопрос 15
Если каждому элементу множества А сопоставлен единственный элемент множества В и при этом всякий элемент множества В сопоставляется одному и только одному элементу множества А, то говорят, что между элементами множеств А и В установлено
Выберите один ответ:
a. взаимодействие
b. равенство
c. соответствие
d. взаимно однозначное соответствие
Вопрос 16
Какие виды циклов используются в теории алгоритмов?
Выберите один ответ:
a. Цикл со счётчиком, цикл с предусловием и цикл с послеусловием
b. Цикл с предусловием и цикл с послеусловием
c. Цикл со счётчиком, цикл с предусловием и цикл с внутренним условием
d. Цикл со счётчиком, цикл с предусловием, цикл с послеусловием, бесконечный цикл
Вопрос 17
При представлении алгоритмов используются следующие базовые структуры:
Выберите один ответ:
a. следование, ветвление, цикл, нормализация
b. следование, ветвление, цикл, условие
c. только цикл
d. следование, ветвление, цикл
Вопрос 18
Если функция всюду определена и частично рекурсивна, то она называется
Выберите один ответ:
a. общерекурсивной.
b. всюду рекурсивной.
c. рекурсивной.
d. примитивно рекурсивной.
Вопрос 19
В каком случае отрицание высказывания является истинным?
Выберите один ответ:
a. Когда исходное высказывание ложно
b. Когда исходное высказывание истинно
c. Отрицание всегда ложно
d. Отрицание всегда истинно
Вопрос 20
Какое из перечисленных предложений является высказыванием?
Выберите один ответ:
a. Москва красивее Парижа
b. Будет ли сегодня дождь?
c. Москва - столица Франции
d. х + 2 = 5
Вопрос 21
Формулы F и H равносильны тогда и только тогда, когда формула F <-> H является
Выберите один ответ:
a. Тождественно ложной.
b. Опровержимой.
c. Тавтологией.
d. Выполнимой.
Вопрос 22
В каком случае конъюнкция двух высказываний является истинной?
Выберите один ответ:
a. Оба исходных высказывания истинны
b. Хотя бы одно высказывание истинно
c. Конъюнкция всегда ложна
d. Оба высказывания ложны
Вопрос 23
Какое из утверждений является верным и получено Эйлером?
Выберите один ответ:
a. Число нечетных вершин (вершин нечетной степени) графа должно быть нечетно.
b. Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
c. Граф с более чем двумя четными вершинами невозможно начертить одним росчерком.
d. Если все вершины графа нечетной степени, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Вопрос 24
В каком случае эквиваленция двух высказываний является истинной?
Выберите один ответ:
a. Когда либо оба истинны, либо оба ложны
b. Когда хотя бы одно из высказываний истинно
c. Только тогда, когда оба истинны
d. Только тогда, когда оба ложны
Вопрос 25
Тезис Чёрча. Числовая функция тогда и только тогда алгоритмически (или машинно) вычислима, когда она
Выберите один ответ:
a. частично рекурсивна.
b. рекурсивна.
c. примитивно рекурсивна.
d. общерекурсивна.
Вопрос 26
Матрица смежности ориентированного графа
Выберите один ответ:
a. Не является квадратной.
b. Может и не быть симметричной.
c. Всегда симметрична.
d. Единичная.
Вопрос 27
Тезис Чёрча-Тьюринга: любой алгоритм может быть представлен как программа
Выберите один ответ:
a. для марковских подстановок
b. на языке Паскаль
c. для машины Тьюринга
d. для машины Чёрча
Вопрос 28
Сколько компонент связности у связного графа?
Выберите один ответ:
a. Две.
b. Одна.
c. Бесконечное множество.
d. Ни одной.
Вопрос 29
Граф называется связным, если
Выберите один ответ:
a. Существует пара вершин, которые можно соединить некоторым путем.
b. Любые две вершины соединены ребром.
c. Существует путь, соединяющий какие-нибудь две вершины.
d. Из любой вершины есть путь в любую другую вершину, причем путь может состоять из любого количества ребер.
Вопрос 30
Дано слово "1234567890". Результатом применения марковской подстановки (456, ?) является
Выберите один ответ:
a. 123?4567890
b. 123456?7890
c. 123?7890
d. 1237890

22 из 30