2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сколько наборов параметров нужно проверить для линейности
Сообщение22.12.2009, 23:50 
Есть задача, точнее вопрос (там ничего не надо считать, а просто подумать и написать ответ)
Условие такое:
Имеется "чёрный ящик", вычисляющий функцию f от n переменных. На скольких наборах надо вычислить значения функции, чтобы проверить, что она нелинейна?

(Имеется ввиду следующее: есть пустая таблица от n переменных (т.е. вписаны наборы, но не вписаны значения)

Выбираем какой-то набор и "кладем" его в ящик, выдается значение функции. Вопрос этой задачи -- после скольких наборов вы сможете точно сказать, что функция нелинейна, какова бы она не была?)

загвоздка в том, что я не помню критерий линейности (можно по многочлену Жегалкина. но он тут не нужен), скажите пожалуйста этот критерий или вообще ответ! огромное спасибо!! )))

 
 
 
 Re: Помогите с дискреткой!!!! HELP!!!
Сообщение23.12.2009, 00:27 
Аватара пользователя
Выберем какую-нибудь линейную функцию. Построим по ней другую функцию, совпадающую с выбранной всюду, кроме одного набора параметров. А на этом наборе параметров она от неё отличается. Но какой именно это набор параметров, нам не известно. Пусть построенная функция и есть та функция, которую мы проверяем на линейность методом "черного ящика". Сколько попыток нам придется сделать для установления нелинейности в "наихудшем" случае?

 
 
 
 Re: Помогите с дискреткой!!!! HELP!!!
Сообщение24.12.2009, 14:15 
Именно... Но спасибо, я разобрался, ответ тривиален, на всех наборах, т.е. на $2^n$, т.к. если функция линейна она имеет четное количество единиц (либо ни одного, как исключение), и если нам не будет известно хотя бы одно значение, мы не сможем определить линейность/нелинейность.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group