Математическая логика и теория алгоритмов

7. Укажите, какой наименьший порядок (из записанных) имеет размер представления в ЭВМ графа с п вершинами и т ребрами; 1) 0(«хот); 2) 0(1п(«)); 3) 0(га"); 4) 0(тх 1о§2(и)); 5) ОС/г"). 8. Рассмотрите задачу о минимальном соединении. Дано п горо­ дов. Нужно соединить все города телефонной связью так, чтобы об­ щая длина телефонных линий была минимальной. На языке теории графов эта задача формулируется следующим образом. Дан полный граф с п вершинами и известна длина каадого ребра. Требуется найти остовный подграф (связный подграф без циклов, содержащий все вершины исходного графа) имеющий минимальную длину, т.е. имеющий минимальную сумму длин ребер. Эту задачу можно решить, перебирая все остовные подграфы данного полного графа и выбирая тот остовный подграф который имеет минимальную длину. Известно, что число всех остовных подграфов полного графа равно Кроме алгоритма перебора всех остовных подграфов данного графа, указанную задачу можно решить так называемым жадным алгоритмом, число шагов которого есть 0(п log(/7)). Укажите, какое из следующих утверждений истинно; 1) задача о минимальном соединении имеет экспоненциальную временную сложность; 2) задача о минимальном соединении имеет полиномиальную временн>'ю сложность; 3) алгоритм перебора всех остовных подграфов данного графа имеет полиномиальную временную сложность; 4) жадный алгоритм имеет линейную'временную сложность; 5) жадный алгоритм имеет экспоненциальную временную слож­ ность. 9. Проблема выяснения выполнимости произвольной формулы а логики высказываний (пропозициональной формы), представленной в конъюнктивной нормальной форме: 329