NP-задачи
University
•10 Qs
Similar activities
Анализ и разработка алгоритмов
University
•6 Qs
Нейронные сети. Машинное обучение
University
•12 Qs
Тенденции развития и перспективы корпоративных сетей
University
•10 Qs
Большое Повторение C#
5th Grade - University
•15 Qs
Элементарная информатика
University
•6 Qs
L11 - Графовые сети
University
•9 Qs
Влад
University
•10 Qs
Разработка, оформление и оптимизация программного кода
University
•10 Qs
NP-задачи
Quiz
•
Computers
•
University
•
Hard
Dmitry Grigoriev
Used 1+ times
FREE Resource
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-полная соответственно
Create a free account and access millions of resources
Similar Resources on Wayground
10 questions
ИИ или Человек
Quiz
•
University
10 questions
Класи початок з pygame
Quiz
•
University
15 questions
АОКТ
Quiz
•
University
15 questions
Избираем модул - ИТ 12.клас
Quiz
•
12th Grade - University
7 questions
3rd presentation
Quiz
•
University
15 questions
Искусственный интеллект
Quiz
•
1st Grade - Professio...
11 questions
Вводное занятие КЛИК
Quiz
•
6th Grade - University
15 questions
[Python For All] Quiz 5 - Numpy
Quiz
•
University
Popular Resources on Wayground
18 questions
Writing Launch Day 1
Lesson
•
3rd Grade
11 questions
Hallway & Bathroom Expectations
Quiz
•
6th - 8th Grade
11 questions
Standard Response Protocol
Quiz
•
6th - 8th Grade
40 questions
Algebra Review Topics
Quiz
•
9th - 12th Grade
4 questions
Exit Ticket 7/29
Quiz
•
8th Grade
10 questions
Lab Safety Procedures and Guidelines
Interactive video
•
6th - 10th Grade
19 questions
Handbook Overview
Lesson
•
9th - 12th Grade
20 questions
Subject-Verb Agreement
Quiz
•
9th Grade