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

гд Т(Х), Ц G,M) в котором: X - название лингвистической переменной, Т(Х) - множество лингвистических значений переменной X, и - универсальное множество, G - синтаксические правила, порождающие названия переменной, т.е. пра­ вила определения синтаксических значений, М - семантические правила, которые ставят в соответствие каждой нечет­ кой переменной ее смысл М(Х), т.е. характеристическую функцию дляХ Указать, какое из следующих утверждений истинно 1) и - нечеткое множество, аТ(Х) - обычное множество; 2) и - обычное множество, а Т(Х) - нечеткое множество; 3) и - нечеткое множество v^T(X) - нечеткое множество; 4) и и Т(Х) - обычные множества; 5) и - обычное конечное множество, а Т(Х) - обычное бесконечное мно­ жество. 6. Пусть]х[ обозначает наименьшее целое q, такое что q>x. Указать, каково ми­ нимальное число символов нужно для представления числа п, заданного в деся­ тичной системе счисления: 1) п 2) 1п(п) 3) ]log(n)[ 4) ln(log(n)) 5) ]ln(n)[ 7. Укажите, какой наименьший порядок (из записанных) имеет размер представления в ЭВМ графа с п вершинами и т ребрами: 1) 0(пхт) 2) 0(1п(п)) 3) 0(т ) 4) 0(тхlog2(n)) 5) 0(п ) 8. Рассмотрим задачу о минимальном соединении. Дано п городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной. На языке теории графов эта задача формулируется следующим образом. Дан полный граф с п вершинами и известны длина каждо­ го ребра. Требуется найти остовный подграф (связный подграф без циклов, со­ держащий все вершины исходного графа), имеющий минимальную длину, т.е. имеющий минимальную сумму длин ребер. Эту задачу можно решить, перебирая все остовные подграфы данного пол­ ного графа и выбирая тот остовный подграф, который имеет минимальную длину. Известно, что число всех остовных подграфов полного графа равно Кроме алгоритма перебора всех остовных подграфов данного графа, указанную задачу можно решить так называемым жадным алгоритмом, число шагов кото­ рого есть 0(п log(n)). Указать, какое из следующих утверждений истинно: 1) задача о минимальном соединении имеет экспоненциальную временную сложность; 256