Какие задачи решают на кафедре дискретной матеметики

Ariada

Очень хочется знать: что известно по данным задачам, занимается ли этим кто-нибудь сейчас и если да, то кто.
Задача: дано n точек. Y - вектор длины n, в котором записаны значения точек (только 0 или 1). О - тоже самое, только данные измененные под действием какой-то булевой функции f.
Вопросы типа:
1) Дали m случайных пар (Y,O): 1. какое должно быть m, чтобы такого f не существовало.
2. какое среднее m, чтобы f определялось единственным образом.
2) Какое наименьшее число пар (Y,O) нам надо задать, чтобы функция определялась однозначно (пары мы выбираем такие, как хотим).
Ну или еще что-то подобное.

sergant5

Что, совсем никто ничего не знает?
Меня, например, очень даже устроют ответы типа: "я и мой научрук этим не занимаемся", "я не знаю никого, кто бы этим занимался", "что-то похожее когда-то слышал (или видел)", ну или что-то подобное. Только если это действительно так.

_shmel_

Ну, на последний вопрос, ответ - n . Берешь Y = (0,..,0,1,0,...,0) - все кроме одного места нули. O - неважно какое. меньше нельзя, тк в линейном пространстве линейная функция однозначно определяется на базисе, а он размерности n

_shmel_

насчет 1.1 Непонятно, что значит
какое должно быть m

Может быть тебе нужно минимальное m, при котором существуют m пар, для которых такой f не существует?

sergant5

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

sergant5

/* Может быть тебе нужно минимальное m, при котором существуют m пар, для которых такой f не существует? */
Именно это и нужно.
Так значит на дискре вот так с ходу умеют решать подобные задачи? А что-нибудь типа работ, теорем, утверждений есть по этой тематике?

_shmel_

ой, нет, я не с дискры, так что ничего сказать не могу... Но задачки не сложные на вид, чуть ли не школьные.

electricbird

>Но задачки не сложные на вид, чуть ли не школьные
интересно, что бы ты про "задачу о бильярдных шарах" выдал?
младшие классы?

_shmel_

Ну, пункт 1.2 наверно действительно не прост, а остальные пункты сложными не кажутся...
интересно, что бы ты про "задачу о бильярдных шарах" выдал?

ну и что это за задача?

natunchik

Реально не сложные.
Совсем даже простые.
Если ты вдруг объяснишь условие по-понятней (для n = 2, например то я тебе могу ету задачку решить. Все пункты.
На кафедрах дискры такими задачками, наверное, не занимаются, потому что они не интересные.

Ariada

Отвечаю примером для n=2, к=1, т. е. есть две точки, а функция изменения зависит только от одной. Ответ: если нам дают любые пары, то их надо минимум две. Однозначно функция определяется только в двух случаях. Первый: пары 1-0, 0-1 ;второй: пары 1-1, 0-0.
n=2, k=2 тоже считается, но описать намного сложнее. А вот остальное...
Если это возможно, и будет не сильно внапряг, то буду благодарна за любые мысли.

natunchik

Оппа. Я вообще перестал понимать о чем ты.
Что такое k?
Что такое пары?
До этого я представлял себе такую ситуацию: есть некая произвольная функция f: (n бит) -> (n бит). Типа, что-то делает с n-битником. Всего таких разных функций может быть (2^n)^(2^n) = 2^(n * 2^n). До фига, словом. И нам дается пара: входное слово, выходное слово. Однозначно функция определится как только мы зададим ее значения на всех входных словах - то есть скормим 2^n пар с разными первыми элементами. Более того, для любых 2^n таких пар существует такая функция (единственная). Противоречие может получиться только в случае если мы дали две пары с одинаковым первым n-битником и разными вторыми. В такой формулировке задача тривиальна.
Но тогда я не понимаю таких слов:
"О - тоже самое, только данные измененные под действием какой-то булевой функции f" - это как?
" m случайных пар (Y,O): 1" - а что значит это двоеточие и еденица?

Ariada

>До этого я представлял себе такую ситуацию: есть некая произвольная функция f: (n бит) -> (n бит). Типа, что-то делает с n-битником. Всего таких разных функций может быть (2^n)^(2^n) = 2^(n * 2^n). До фига, словом. И нам дается пара: входное слово, выходное слово.
Вот до этого места все правильно.
>Однозначно функция определится как только мы зададим ее значения на всех входных словах - то есть скормим 2^n пар с разными первыми элементами.
Вот здесь не поняла, но скорее всего ты где-то недопонял, а может быть и я.
> Более того, для любых 2^n таких пар существует такая функция (единственная). Противоречие может получиться только в случае если мы дали две пары с одинаковым первым n-битником и разными вторыми. В такой формулировке задача тривиальна.
Здесь ты полностью прав. На эту задачку я тоже нашла ответ и он именно такой: минимальное m = 2^k.
>Но тогда я не понимаю таких слов:
"О - тоже самое, только данные измененные под действием какой-то булевой функции f" - это как?
Это значит, что для каждой конкретной точки у нас есть вектор длины k (k<=n состоящий из 0 и 1, - это так называемый Y, а потом он изменяется под действием функции f и получается вектор О длины k, состоящий из 0 и 1.
>" m случайных пар (Y,O): 1" - а что значит это двоеточие и еденица?
Единица - это номер пункта у первого типа вопросов, здесь пары даны произвольные, в том числе и одинаковые могут попадаться и противоречивые.

natunchik

Дык тогда в чем вопрос?
Зацени: есть 2^n разных входных н-битников. Типа табличка. Данная конкретная булевская функция может выдать АБСОЛЮТНО ЛЮБОЙ (нлп!) из 2^n битников на выходе, и то, что она выдает на конкретном входе, никак не коррелирует с остальными входами. Пример построения ищи в книжках. Типа, один мультиплексор и куча констант решают!
Так вот. Пока ты не задашь функцию на ВСЕХ ее входных значениях (2^n остается неоднозначность.
Противоречие получить возможно только если у тебя в парах присутствуют (Y, O1 (Y, O2 O1 != O2.
Считать вероятности неинтересно.
Потому что это сводится к вопросу "А вот если у меня есть 2^n ячеек, и я по рандому их заполняю, какая вероятность, что я за К заполнений (или меньше) заполню их все" - для одного из пунктов, или к вопросу "А вот если у меня есть 2^n ячеек, и я по рандому их заполняю, какая вероятность, что я за К заполнений (или меньше) попытаюсь заполнить одну и ту же ячейку два раза". Считаются тривиально, точно тебе говорю!
ЗЫ: Если ты все еще не понимаешь убогости задачи, перечитай первые два абзацца много раз.

Ariada

Спасибо!
Поняла. Не совсем тупая .
Еще разок спасибо.
Оставить комментарий
Имя или ник:
Комментарий: