2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 функции "пол" и "потолок"
Сообщение05.10.2013, 23:00 


26/03/12
74
Здравствуйте. Имеется пара задачек на функции $\lfloor\cdot\rfloor$ и $\lceil\cdot\rceil$, а именно:

1. в равенстве $x = \lceil y \cdot z \rceil$, где $y $ - целое неотрицательное число, а $z$ - рациональная константа, вынести $y$ за знак потолка.

2. даны $x$ и $x'$ - дробные числа из открытого интервала $(0, 1)$, причем $x' = x + \Delta x$, а также натуральное число $v$. Необходимо определить максимально допустимое значение $\Delta x$, при котором выполняется равенство: $\lfloor x\cdot 2^v \rfloor = \lfloor x'\cdot 2^v \rfloor$.

Подскажите пожалуйста, разрешимы ли эти задачки в такой постановке (в особенности интересует первая задача) и если разрешимы, то как их решить или хотя бы с чего начать решение...

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение05.10.2013, 23:08 
Заслуженный участник


27/04/09
28128
А вы сделайте небольшую таблицу значений $\lceil yz \rceil$ в зависимости от $y$, взяв числитель и знаменатель $z$ небольшими — например, $z = \frac25$, а потом $z = \frac43$. Может, какую-то закономерность подметите.

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение06.10.2013, 19:45 


26/03/12
74
Спасибо за совет. Попробую. Но все же хотелось бы узнать, может быть есть по этому поводу какие-то результаты в теории чисел? Чтобы и обоснование было, и велосипед не сочинять.

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение06.10.2013, 20:02 
Заслуженный участник


27/04/09
28128
Сначала лучше увидеть, тогда будет понятно, как это выражается и почему.

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение09.10.2013, 22:27 


26/03/12
74
построил таблички, при первом взгляде закономерность какую-либо определить не удалось. как можно вынести целочисленный множитель за знак пола?

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение10.10.2013, 18:14 
Заслуженный участник


27/04/09
28128
Хм. Похоже, $y$ и нельзя вынести. Для пола получается ($\mathrm{\text{НОД}}(p,q)=1$)$$\left\lfloor\frac{pn}q\right\rfloor = p\left\lfloor\frac nq\right\rfloor + \left\lfloor(n\bmod q)\frac pq\right\rfloor.$$
Посмотрите Кнута, Грэхема, Паташника «Конкретная математика». Там на тему полов и потолков целая глава.

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение11.10.2013, 08:35 


26/03/12
74
книжку эту я смотрел, но подходящего не нашел. а по второй задачке может быть что-то подскажите?

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение11.10.2013, 18:25 
Заслуженный участник
Аватара пользователя


18/01/13
12065
Казань
Вторая задача. Если $x, v$ -постоянны, то левая часть равенства также постоянна. Тогда для $x'y$ можно записать неравенства.

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение11.10.2013, 19:03 


26/03/12
74
Представим числа $x$ и $x'$ в виде взвешенных сумм разрядов:
$$
 (1)  \qquad   x=\sum\limits_{i=0}^{\infty}{{{b}_{i}}\cdot {{2}^{-i}}}, \quad {x}'=\sum\limits_{i=0}^{\infty }{{{d}_{i}}\cdot {{2}^{-i}}},
$$
Пусть ${d}_{\rho }$ – первый ошибочный разряд в двоичном представлении ${x}'$. Тогда если $\Delta x<{{2}^{-v}}$, то ${{b}_{i}}={{d}_{i}},i=0,1,...,v$, а $\rho \ge v+1$. Умножение чисел (1) на степень двойки ${{2}^{v}}$ не приводит к изменению значений разрядов ${{b}_{i}}$ и ${{d}_{i}}$, а меняет лишь значения их весов. При этом
$$(2)  \qquad   x\cdot {{2}^{v}}=\sum\limits_{i=1}^{\infty }{{{d}_{i}}\cdot {{2}^{-i+v}}}, \quad{x}'\cdot {{2}^{v}}=\sum\limits_{i=1}^{\infty }{{{d}_{i}}\cdot {{2}^{-i+v}}}.$$
Таким образом, индекс ошибочного разряда остается неизменным. При округлении в соответствии с функцией $\left\lfloor \cdot  \right\rfloor $ все слагаемые сумм (2), начиная с $i=j=v+1$ отбрасываются (заменяются нулями), при этом отбрасывается также и ошибочное слагаемое, если оно имеет вес $\rho \ge v+1$. И напротив, если $\rho \le v$, то его значение попадет в результатную целую часть $\left\lfloor {{x}'} \right\rfloor $. Таким образом, искомое неравенство:
$$\Delta x<{{2}^{-v}}.$$

Подскажите пожалуйста, верны ли эти рассуждения?

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение11.10.2013, 21:03 
Заслуженный участник
Аватара пользователя


18/01/13
12065
Казань
Все еще непонятно. Вы $\Delta x$ подбираете сразу для всех $x$, или для каждого? А то у вас в условии все названо "заданным": и $x$, и $v$, и даже $x'$.
Если $x,x'$ даны, то $\Delta x$ - это их разность, что тут максимизировать?

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение11.10.2013, 21:29 


26/03/12
74
приношу извинения за некорректную формулировку. В оригинале задача звучит так:

определить максимальное отклонение $\Delta x$, при котором $\lfloor x\cdot 2^v \rfloor = \lfloor x'\cdot 2^v \rfloor$, где $x' = x + \Delta x$ для всех $x \in (0, 1)$. Показатель $v$ --- целое неотрицательное число.

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение11.10.2013, 21:43 
Заслуженный участник
Аватара пользователя


18/01/13
12065
Казань
Ваше условие можно переписать в виде $k\le x\cdot2^v <x'\cdot 2^v<k+1$, где $k$ - общее значение целых частей. Отсюда следует ограничение на $\Delta x$. Но для доказательства обратного соотношения нужно потребовать еще, что $x'<1$, без этого ограничения $\Delta x=0$.

-- 11.10.2013, 21:47 --

Кстати, среди значений $\Delta x$ нет максимального, есть только супремум.

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение11.10.2013, 21:50 


26/03/12
74
извините, что-то не соображу, какое следует ограничение на $\Delta x$ из написанного вами условия? Можно его как-то выразить через $v$? Для определенности будем полагать, что $x' < 1$. И еще хотелось бы узнать, в приведенных мною выше рассуждениях есть какой-то смысл?:)

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение11.10.2013, 21:53 
Заслуженный участник
Аватара пользователя


18/01/13
12065
Казань
Ну, не хотелось бы давать полного решения... Два числа $x\cdot2^v,x'\cdot2^v$ лежат в одном промежутке длиной 1. Какой может быть разность между ними?

-- 11.10.2013, 22:00 --

Ваше рассуждение в общем верно, только трудно читать. И оно какое-то нестрогое. Какие-то взвешенные суммы, когда это просто двоичное разложение. Мне кажется, все можно сделать короче и яснее, без рядов.
а уж если пользуетесь рядами, упомяните, что коэффициенты не могут быть все равны 1, начиная с некоторого.

 Профиль  
                  
 
 Re: функции "пол" и "потолок"
Сообщение11.10.2013, 22:13 


26/03/12
74
Полагаю $\sup \Delta x = 2^{-v}$. Про какое обратное соотношение вы говорили? Имеется ввиду необходимое условие? Да, здесь ясно, что если $x' > 1$, то исходное условие изначально нарушится.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group