. Найдите асимптотическую оценку количества функ- ций от n переменных, которые зависят от всех своих аргументов су- щественно. Иначе говоря, надо придумать такие верхнюю и нижнюю оценки на это количество, чтобы их отношение стремилось к 1 при n → ∞.

задан 27 Сен '17 23:28

10|600 символов нужно символов осталось
0

Такой оценкой будет $%2^{2^n}$% -- общее число б.ф. от $%n$% переменных. Почти у всех этих функций все $%n$% переменных будут существенными. В самом деле, если $%i$%-я переменная фиктивна, то её можно удалить, получая б.ф. от $%n-1$% переменной. Отсюда следует оценка сверху вида $%n2^{2^{n-1}}$% для числа тех функций, где не все переменные существенны. Очевидно, что отношение к общему числу функций есть бесконечно малая величина: $%n2^{-2^{n-1}}\to0$% при $%n\to\infty$%. Поэтому оценка будет асимптотически точной.

ссылка

отвечен 27 Сен '17 23:54

Но ведь оно должно стремиться к 1 по условию задачи,имеется ввиду найти,такие a(n) и b(n),что a(n)<c<b(n),где с-точное количество функций существенно зависящих от своих переменных и a(n)/b(n)=1 при n → ∞.

(28 Сен '17 0:04) Kot

@danek: я это и сделал. Общее число функций равно 2^{2^n}. Пусть среди них x(n) хороших и y(n) плохих. Я показал, что плохих функций мало, то есть y(n)/2^{2^n} стремится к нулю. Значит, доля хороших функций x(n)/2^{2^n} стремится к 1 ввиду x(n)+y(n)=2^{2^n}. Оценка, тем самым, асимптотически точная. Она заключена между 2^{2^n}-n2^{2^{n-1}} и 2^{2^n}.

(28 Сен '17 0:17) falcao

Понял,спасибо большое

(28 Сен '17 0:19) Kot
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×154

задан
27 Сен '17 23:28

показан
709 раз

обновлен
28 Сен '17 0:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru