Онлайн ТЕСТ Математическая логика и теория алгоритмов

Помогу с прохождением онлайн теста

Вопрос No1
Теория алгоритмов получила бурное развитие...
в связи с созданием быстродействующих электронных вычислительных и управляющих машин.
в связи с появлением письменности.
в связи с разработкой теории чисел.
в связи с появлением счётов.
в связи с указом императора Петра I.

Вопрос No2
Для того чтобы сделать более понятной структуру сложных высказываний, пользуются специальным языком –
языком исчисления предикатов (ИП) первого порядка.
языком исчисления предикатов (ИП) второго порядка.
языком исчисления предикатов (ИП) второго порядка.
языком резольвируемых предложений.
языком формальной аксиоматической теории “T”.

Вопрос No3
Пустая формула не имеет никакого значения и не является истинной ни при какой интерпретации и, по определению является...
противоречием.
предложением.
квантором.
тавтологией.
эквиваленцией.

Вопрос No4
Способ построения научной теории в виде системы аксиом (постулатов) и правил вывода, позволяющих формальным логическим путем получать утверждения (теоремы) данной теории, называется...
аксиоматическим методом.
методом резольвируемых предложений.
дедуктивным методом.
модификацией тривиального метода.
методом резолюций.

Вопрос No5
В чём заключается такое свойство алгоритма, как “Дискретность”...
Преобразование начальных данных происходит пошагово. На каждом шаге из данных по правилам получается новая совокупность данных.
На каждом шаге результат работы алгоритма однозначно определяется совокупностью данных предыдущего шага.
Для алгоритма есть критерий, позволяющий определить, что является результатом работы алгоритма.
Описание действий на каждом шаге алгоритма должно быть достаточно простым.
Применимость алгоритма не к одной задаче, а к целому классу задач.

Вопрос No6
Задача построения всех подмножеств данного множества имеет...
экспоненциальную сложность.
полиномиальную сложность.
линейную сложность.
константную сложность.

Вопрос No7
Под высказыванием принято понимать...
языковое предложение, о котором имеет смысл говорить, что оно истинно или ложно
основанный на четких правилах формальный аппарат оперирования со знаниями определенного вида, позволяющий дать точное описание некоторого класса задач, а для отдельных подклассов этого класса и алгоритм решения
формулу рассматриваемого исчисления
язык, описывающий некоторую предметную область
процесс логического вывода, представляющий собой переход от посылок к заключениям, следствиям на основе применения правил логики

Вопрос No8
В одноленточной машине Тьюринга выделенная ячейка памяти...
содержит символ внутреннего алфавита, задающий состояние машины Тьюринга.
разделена на ячейки, которая используется для ввода и вывода данных, а также для записи промежуточных результатов.
способна читать символы, содержащиеся в ячейках ленты, писать символы в эти ячейки и оставаться на месте или передвигаться на одну ячейку вправо или влево.
обеспечивает перемещение головки относительно ленты.

Вопрос No10
Внутренним алфавитом машины является...
совокупность символов, обозначающих состояния внутренней памяти.
совокупность правил, то чтобы решить проблему интерпретации (понимания) правил, необходимо задать конструкцию интерпретирующего устройства.
состояния внутренней памяти.
совокупность всех команд, которые может выполнять машина.
полная информация о внутреннем состоянии машины, о содержимом ячеек ленты и о ячейке, которую обозревает головка машины.

Вопрос No11
Исчисление предикатов, в котором кванторы могут связывать только предметные переменные, но не могут связывать функторы, предикаты или иные множества объектов, называется...
исчислением высших порядков
прикладным
чистым
модификацией тривиального метода
аксиоматическим методом

Формула “A” называется опровержимой (условно-ложной формулой)...
если при некоторых значениях переменных списка (X1,X2,...,Xk) она принимает значение “Л”.
если при любых значениях (интерпретации) переменных списка (X1,X2,...,Xk) она принимает значение “И”.
если при некоторых значениях переменных списка (X1,X2,...,Xk) она принимает значение “И”
если при любых значениях переменных списка (X1,X2,...,Xk) она принимает значение “Л”.
если она имеет значение “И” при всех интерпретациях, при которых формула “А” имеет значение “И”.

Вопрос No13
Формальная аксиоматическая теория называется непротиворечивой,...
если в ней не существует вывода формулы “A” такой, что одновременно доказуемы формулы “A” и “!A” (где “!A” – отрицание высказывания “A”).
если в ней доказуема любая тавтология.
если никакая из аксиом не выводима из остальных по правилам теории вывода.
если добавление любой невыводимой формулы в качестве схемы аксиом приводит к противоречивой системе.
если существует алгоритм, который для любой формулы теории определяет, является ли эта формула теоремой.
если существует алгоритм, который для любой формулы “F” выдает ответ «Да», если “F” – теорема, и может быть не выдает никакого ответа, если “F” не является теоремой.

Вопрос No14
Если можно решить полную NP-задачу, то...
можно решить и все NP-задачи.
это не дает сведений о разрешимости всех NP-задачи.
алгоритм ее решения нельзя упростить.
алгоритм ее решения можно упростить.

Вопрос No15
Формальная теория разрешима,...
если существует алгоритм, который для любой формулы теории определяет, является ли эта формула теоремой.
если в ней доказуема любая тавтология.
если в ней не существует вывода формулы “A”такой, что одновременно доказуемы формулы “A” и “!A” (где “!A” – отрицание высказывания “A”).
если никакая из аксиом не выводима из остальных по правилам теории вывода.
если добавление любой невыводимой формулы в качестве схемы аксиом приводит к противоречивой системе.
если существует алгоритм, который для любой формулы “F” выдает ответ «Да», если “F” – теорема, и может быть не выдает никакого ответа, если “F” не является теоремой.

Вопрос No16
Формулы “А” и “В” логически эквивалентны...
если они являются логическим следствием друг друга. Логически эквивалентные формулы имеют одинаковые значения при любой интерпретации.
если формула “В” имеет значение “И” при всех интерпретациях, при которых формула “А” имеет значение “И”.
если при любых значениях (интерпретации) переменных списка (X1,X2,...,Xk) они принимают значение “И”.
если при некоторых значениях переменных списка (X1,X2,...,Xk) они принимают значение “И”.
если при любых значениях переменных списка (X1,X2,...,Xk) они принимают значение “Л”.

Вопрос No17
Задача называется NP-задачей, если...
ее можно полиномиально преобразовать в любую данную NP-задачу.
ее нельзя полиномиально преобразовать в любую данную NP-задачу.
ее можно линейно преобразовать в любую данную NP-задачу.
она не преобразуется в другую NP-задачу.

Вопрос No18
Для определения временной сложности алгоритма вместо общего числа шагов алгоритма можно также использовать...
количество операций определенного вида.
экспоненциальную сложность алгоритма.
количество строк в реализации программы.
количество символов в реализации программы.

Вопрос No19
Исчисление предикатов, которое содержит предметные константы и (или), функторы и (или) предикаты и связывающие их собственные аксиомы, называется...
прикладным
чистым
исчислением высших порядков
модификацией тривиального метода
аксиоматическим методом

Вопрос No20
Система аксиом формально непротиворечивой теории называется независимой,...
если никакая из аксиом не выводима из остальных по правилам теории вывода.
если в ней доказуема любая тавтология.
если в ней не существует вывода формулы “A” такой, что одновременно доказуемы формулы “A” и “!A” (где “!A “– отрицание высказывания “A”).
если добавление любой невыводимой формулы в качестве схемы аксиом приводит к противоречивой системе.
если существует алгоритм, который для любой формулы теории определяет, является ли эта формула теоремой.
если существует алгоритм, который для любой формулы “F” выдает ответ «Да», если “F” – теорема, и может быть не выдает никакого ответа, если “F” не является теоремой.

Вопрос No21
Алгебраический метод более базируется...
на применении законов булевой алгебры. Поскольку разные формулы могут принимать одинаковые значения, то для проверки “И” можно использовать наиболее простую формулу, например ДНФ (или КНФ), для которых известны методы построения и вычисления значений формулы.
на проверке значений формулы при всевозможных значениях (интерпретациях) ее переменных. Однако при большом количестве переменных такой метод становится очень громоздким.
на способе построения научной теории, при котором какие-то положения теории избираются в качестве исходных (аксиом), а все остальные выводятся из нее чисто логическим путем, посредством доказательств.
на переходе от посылок к заключениям, следствиям на основе применения правил логики.
на в преобразовании начальных данных происходит пошагово. На каждом шаге из данных по правилам получается новая совокупность данных.
Вопрос No22
Выберите формулы, выражающие закон коммутативности...
A&B ≡ B&A; AvB ≡ BvA.
(A&B)&C ≡ A&(B&C); (AvB)vC ≡ Av(BvC).
Av(B&C) ≡ (AvB)&(AvC); A&(BvC) ≡ (A&B)v(A&C).
A&A ≡ A; AvA ≡ A.
Av(A&B) ≡ A; A&(AvB) ≡ A.

Вопрос No23
Языковое предложение, о котором имеет смысл говорить, что оно истинно или ложно называется...
высказыванием.
теоремой.
гипотезой.
интерпретацией.
заключением.

Вопрос No24
Общерекурсивной функцией называется...
всюду определённая частично рекурсивная функция.
полностью определенная функция.
любая вычислимая функция.
функция, областью определения которой являются натуральные числа.

======================================
Комментарии: Оценка: отлично
Дата оценки: 02.11.2024

Не нашли ответ на свой вопрос теста?
Помогу с другим вариантом, онлайн тестом, другой работой или дисциплиной
Выполняю семестр "под ключ"

E-mail: sibguti06@mail.ru