#Проектное решение

#Алгоритм Крускала
====
Алгоритм жадности
====
Алгоритм Хаффмана
====
Алгоритм «разделяй и властвуй»
++++
Выберите все неверные утверждения.
====
МТ снабжена потенциально бесконечной памятью
====
Машина Тьюринга - точное математическое описание алгоритма
====
#В каждой ячейке может быть записано несколько символов внешнего алфавита МТ
====
МТ управляется программой
++++
Преимущества алгоритмов класса P
====
для большинства задач из класса P константа k меньше 6;
====
класс P инвариантен по модели вычислений (для широкого класса моделей);
====
класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином).
====
#Все ответы верны
++++
Какое из определений является верным для NP-задачи (nonlinear polynomial -нелинейный полиномиальный):
====
класс задач, которые невозможно решить на недетерминированной машине Тьюринга (НМТ) за неполиномиальное время
====
#это задача, решение которой можно проверить на детерминированной машине Тьюринга за полиномиальное время
====
класс задач, которые возможно решить на детерминированной машине Тьюринга (ДМТ) за полиномиальное время. То есть, эта задача решается эффективно традиционными компьютерами (которые и являются ДМТ).
====
Верного ответа нет
++++
Задача называется NP-полной –
====
#если она принадлежит классу NP и любая другая задача из NP сводится к ней за полиномиальное время
====
если она принадлежит классу NP и не является NP-полной. Для некоторых NP задач (изоморфизм графов, минимизация булевой функции, ...) не доказана (на данный момент) их принадлежность классу NP-полных.
====
если для неё существует такая NP-полная задача, которая сводиться к C за полиномиальное время (алгоритмическая сводимость по Куку).
++++