NP-задачи

NP-задачи

University

10 Qs

quiz-placeholder

Similar activities

6ta generación de computadoras

6ta generación de computadoras

University

10 Qs

Reshaping & vStack&hstack( )

Reshaping & vStack&hstack( )

9th Grade - University

10 Qs

На сколько ты знаешь C#

На сколько ты знаешь C#

University

10 Qs

Artificial intelligence + Game development on Construct 3

Artificial intelligence + Game development on Construct 3

6th Grade - University

15 Qs

Статистика Катысты шама

Статистика Катысты шама

1st Grade - University

10 Qs

Знаешь ли ты CSS?

Знаешь ли ты CSS?

University

10 Qs

Data Analytics and Artificial Intelligence

Data Analytics and Artificial Intelligence

University

10 Qs

Excel 3

Excel 3

1st Grade - University

11 Qs

NP-задачи

NP-задачи

Assessment

Quiz

Computers

University

Practice Problem

Hard

Created by

Dmitry Grigoriev

Used 1+ times

FREE Resource

AI

Enhance your content in a minute

Add similar questions
Adjust reading levels
Convert to real-world scenario
Translate activity
More...

10 questions

Show all answers

1.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Что значит NP в информатике?

Non-Polynomial

Non-Predictable

Non-Parallel

Non-Programmable

2.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Какая разница между задачами P и NP?

P может быть решена за полиномиальное время, а NP - нет

Задачи P проще, чем NP

NP может быть решена за полиномиальная время, а P - нет

Нет разницы

3.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Как можно решить оптимально NP задачу в общем случае?

Перебирать все варианты и проверять их

Используя жадный алгоритм

Используя динамический алгоритм

Она не разрешима

4.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Какая задача относится к NP-полным?

Сортировка

Кратчайший путь в графе

Коммивояжера

Подсчет факториала

5.

MULTIPLE CHOICE QUESTION

1 min • 1 pt

Пусть S - NP-полная задача, а Q и R - две другие задачи, о которых неизвестно, что они находятся в NP. Q - за полиномиальное время приводится к S, а S - за полиномиальное время приводится к R. Какое из следующих утверждений верно?

R - NP-полная

R - NP задача

Q - NP-полная

Q - NP задача

6.

MULTIPLE CHOICE QUESTION

1 min • 1 pt

Пусть X - задача, относящаяся к классу NP. Тогда что из следующего верно?

Для X не существует алгоритма за полиномиальное времени

Если X может быть решено детерминированно за полиномиальное время, то P = NP

X - NP-полная, если она сводится к другим задачам

X - не имеет решения

Все не верно

7.

MULTIPLE CHOICE QUESTION

45 sec • 1 pt

Проблема 3-SAT и 2-SAT вычислимости:

Обе полиномиальны

Обе NP-полные

NP-полная и полиномиальная соответственно

Невычислимая и NP-полная соответственно

Access all questions and much more by creating a free account

Create resources

Host any resource

Get auto-graded reports

Google

Continue with Google

Email

Continue with Email

Classlink

Continue with Classlink

Clever

Continue with Clever

or continue with

Microsoft

Microsoft

Apple

Apple

Others

Others

Already have an account?