Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

2) задача о минимальном соединении имеет полиномиальную временную сложность; 3) алгоритм перебора всех остовных подграфов данного графа имеет поли­ номиальную временную сложность; 4) жадный алгоритм имеет линейную временную сложность; 5) жадный алгоритм имеет экспоненциальную временную сложность. 9. Проблема выяснения выполнимости произвольной формулы а логики высказываний (пропозициональной формы), представленной в конъюнктивной нормальной форме: 1) является алгоритмически неразрешимой; 2) не является np - полной задачей; 3) является np - полной задачей; 4) является задачей, не принадлежащей классу М^; 5) является задачей, не имеющей решения. 10. Указать, какое из следующих утверждений ложно: 1) задача является np - полной, если она входит в np и каждая задача из np полиномиально сводится к ней; 2) np класс задач содержит задачи, которые можно решить недетерми­ нированными алгоритмами, работающими в течение полиномиального времени; 3) задача является np трудной, если каждая задача из np полиномиально сводится к ней; 4) если одновременно задача Zj полиномиально сводится к задаче и полиномиально сводится к задаче Zj, то задачи Z^ и Z^ полиномиально эквивалентны; 5) задача имеет экспоненциальную временную сложность, если хотя бы один из алгоритмов её решения имеет экспоненциальную временную сложность. Ответы к тестам самоконтроля № вопроса теста № 1 2 3 4 5 6 7 8 9 10 теста V2 ответа на данный вопрос теста 1 4 2 1 4 2 4 2 5 3 3 2 5 2 4 5 1 2 2 3 5 4 3 1 5 3 2 4 2 5 3 4 2 4 5 1 2 4 3 2 4 4 1 5 5 2 5 2 4 1 3 5 1 2 5 6 2 4 3 5 4 3 4 2 3 5 257