2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 00:34 


26/03/13

39
Друзья, напишите пожалуйста, где искать решение, или как решить такую задачу.

Допустим у меня есть телефонный провод между двумя городами длинной 1000 км.
В какомто месте произошел разрыв провода.
Что бы найти разрыв, я например могу сначала разделить провод пополам и прозвонить, определить в какой половине находится разрыв, потом поврежденную половину разделитть опять пополам и опять прозвонить и в итоге дойти, скажем до 8 участка провода длиной примерно 8 метров в котором будет разрыв.
Или я могу делить провод на трети каждый раз.
Или сначача искать участки разрыва деля каждый раз пополам и прозванивая, а потом искать третями итд.
Вопрос: На сколько частей надо каждый раз делить провод и прозванивать, чтоб наименьшим количеством разделений и прозвонов найти меленький участок (Наппример 8 метров) который будет содержать разрыв?

Если кто знает, подскажите где почитать решения подобных задач? Очень интересно!

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 01:01 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Оптимальнее всего делить на $e$ частей. Ну а ближайшее целое — три.

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 02:19 
Заслуженный участник
Аватара пользователя


28/07/09
1178
Целевая функция здесь $f(n) = \frac{n-1}{\ln{n}}$, где $n$ -- на сколько частей каждый раз делим участок.
Минимум будет при $n = 2$, поэтому бисекция является оптимальной.

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 04:43 
Заслуженный участник


28/12/12
7740
Можно запустить волну и померить время до прихода отраженной. Нынешние осциллографы дают точность единицы наносекунд.

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 08:16 
Аватара пользователя


22/07/08
1373
Предместья
DimaM в сообщении #1203834 писал(а):
Нынешние осциллографы дают точность единицы наносекунд.

Можно и не нынешний...
Есть такой прибор:"Измеритель неоднородности линий"(aka "Рефлектометр") , называется Р5-10 (или более старый Р5-5).
Он как раз для того, чтобы не резать, где не надо...
(Генератор импульсов + осциллограф) в одном корпусе...

-- Пн мар 27, 2017 07:34:18 --

Poika в сообщении #1203802 писал(а):
Допустим у меня есть телефонный провод между двумя городами длинной 1000 км.

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

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 10:23 


26/03/13

39
Лукомор, спасибо за ответ!
Просто меня интересует вопрос не как телефониста, а как матиматика. Просто как математическая задача. Как наименьшим числом измерений дойти до поврежденного участка. Подумайте сами, ведь вопрос интресный!

-- 27.03.2017, 11:25 --

Aritoborian,
Спасибо за ответ!
Еали можешь обьяани поподробней пожалуйста, или скажи какую теорию почитать на эту тему? Откуда такое решение?

-- 27.03.2017, 11:26 --

Legioner93,
Спасибо за ответ!
Но я так и не понял почему такая функция. Напиши пожалуйста откуда она и где можно про нее почитать?

 !  profrotter:
Замечание за фамильярность.

(Подробно)

Forum Administration в сообщении #27356 писал(а):
I. Нарушения и санкции
1) Нарушением считается:
е) Провокационные и вызывающие сообщения, фамильярность (у нас принято обращаться друг к другу на "Вы"), хамство, оскорбления в адрес участников дискуссии и иных лиц (в том числе не являющихся участниками форума), разжигание флейма, обсуждение в тематических разделах ников*, аватаров*, подписей* собеседников.

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 13:21 
Аватара пользователя


22/07/08
1373
Предместья
Poika в сообщении #1203859 писал(а):
Как наименьшим числом измерений дойти до поврежденного участка. Подумайте сами, ведь вопрос интресный!

На этот вопрос ответил уже Aritaborian, исчерпывающе...

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 13:30 
Заслуженный участник
Аватара пользователя


28/07/09
1178
Poika
Прозваниваем участок длиной $1$. Каждый раз делим участок на $n$ частей и прозваниваем $(n-1)$ кусков. Действие прекращаем, когда локализуем разрыв на участке длиной $\varepsilon$. Всего подтребуется прозвонов $$f(n) = \underbrace{(n-1) + (n-1) + \cdots + (n-1)}_{\log_{\frac{1}{n}} \varepsilon} = - (n - 1) \frac{\ln \varepsilon}{\ln n} \sim  \frac{n - 1}{\ln n}$$

Эта функция строго возрастает при положительных $n$, поэтому минимальное число прозвонов будет при $n = 2$ (меньшие $n$ невозможны). То есть получили классическую бисекцию.

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 13:55 


05/09/16
11463
Лукомор в сообщении #1203897 писал(а):
На этот вопрос ответил уже Aritaborian, исчерпывающе...

Мне кажется тут вопрос немного другой: если мы делим не $1:1$, а в другой пропорции, затем случайно выбираем какую часть проверять, то как матождание количества шагов (за один шаг берем деление отрезка, выбор где проверять,и саму проверку) будет зависеть от пропорции, т.е. будет ли оно минимально если делить ровно пополам, а не $1:e$ например.


upd Зачеркнул лишнее, т.к. проверка на каждом шаге всегда показывает в какой части разрыв.

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 14:01 


26/03/13

39
wrest
Простите, я не очень понял, что Вы имеете ввиду...=(

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 14:24 


05/09/16
11463
Poika в сообщении #1203911 писал(а):
Простите, я не очень понял, что Вы имеете ввиду...=(

Ваш алгоритм может быть изменен:
Poika в сообщении #1203802 писал(а):
Допустим у меня есть телефонный провод между двумя городами длинной 1000 км.
В какомто месте произошел разрыв провода.
Что бы найти разрыв, я например могу сначала разделить провод

... но не пополам, т.е. на 500-ом километре, а например на 300-ом километре.
Тогда, если повезло и разрыв между 0 и 300 (вероятность везения 0,3), то останется обследовать 300. А если не повезло, то разрыв между 300 и 1000 (вероятность невезения 0,7) и обследовать останется 700.

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 14:30 


26/03/13

39
wrest
Целесообразно ли тогда измерять сначала 300? Или лучше начать всетаки с 500 чтоб измерить наименьшим количеством измерений?

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 15:10 
Заслуженный участник


20/08/14
11063
Россия, Москва
Так это вопрос что именно Вам надо: или гарантированно минимальное количество измерений (и тогда деление пополам) или как можно быстрее в среднем найти точку разрыва (тогда делить желательно в пропорции золотого сечения, $1:1618$ и сначала измерять короткий участок). Второй способ быстрее лишь в среднем, или с некоторой вероятностью, в худшем случае он медленнее первого.

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 15:16 
Аватара пользователя


22/07/08
1373
Предместья
wrest в сообщении #1203915 писал(а):
Тогда, если повезло и разрыв между 0 и 300 (вероятность везения 0,3)

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

 Профиль  
                  
 
 Re: Задачка про поиск точки разрыва на проводе
Сообщение27.03.2017, 15:37 


26/03/13

39
Dmitriy40
Спасибо! Подскажите пожалуйста в каком учебнике можно почитать про это? Про золотое сечение слышу первый раз

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

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



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

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


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

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