Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 8 ] |
|
Автор | Сообщение | ||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
atlakatl |
|
||||||||||||||||||||||||||||||||||||||||||||||||||
Пусть мы хотим получить первые члены знакоположительной последовательности с помощью линейки с минимальным количеством делений. Первое деление [math]0[/math], остальные надо получить. Замеряя расстояние между любыми двумя делениями, мы можем получить на линейке с [math]n[/math] делениями [math]qR=\frac{n \cdot (n-1)}{ 2 }[/math] первых членов. Пример: натуральный ряд: [math]n=3[/math] линейка с делениями [math]p=(0, 1, 3)[/math]: [math](1=1-0; 2=3-1; 3=3-0)[/math] - абсолютное приближение чисел от 1 до 3. Пойдёт, конечно, и [math]p=(0, 2, 3)[/math] [math]n=4[/math] линейка с делениями [math]p=(0, 1, 4, 6)[/math] - абсолютное приближение чисел от 0 до 6. Дальше точного соответствия не получается: число делений растёт арифметически, а желающих получиться членов последовательности - квадратично. Потому примем самый "аналитический" критерий оптимальности - [math]\Delta S=min(\sum\limits_{0}^{qR-1}(p_i-a_i )^2)[/math], где [math]a_i[/math] - приближаемая последовательность.
Как получать оптимальные решения для больших qP? - А большое начинается уже где-то в районе [math]qP>20[/math] - проклятие размерности, ничего мистического. Так если мы возьмём для перебора по 5 значений для каждого [math]p_i[/math], получим [math]5^{20}=9.537e13[/math] вычислений функции. Ну и смотрим на саму функцию. Прежде всего, это классическая много-много-fiele-many-багато-molto-экстремальная функция. К тому же с разрывной производной. К счастью, выбранный нами КО [math]\Delta S[/math] допускает эффективную итерацию. Большинство последовательностей приближаются ею за пару сотен шагов с точностью только порядка процента отличающуюся от оптимального значения. Дальнейшие приближения идут по типу: делаем большой случайный шаг - и ищем итерациями оптимум в данном районе. Нашли, сравнили старый и новый - если новый лучше, переехали в него. Функция что называется реально вычислимая. Я считал приближение для такой неудобной последовательности как простые числа. Приближение вполне удовлетворительное. Программа считает на PascalABC, но интересующиеся могут перевести её на любой иной язык. Отсюда вытекает целый ряд задач. 1. Самая увлекательная из них: найти такую последовательность из OEIS для приближения, что приближающая последовательность, укрупнённая до целых путём [math]p_i=qP \cdot p_i[/math] - получатся именно целые числа - сама вдруг обнаружится в OEIS - по совсем другому поводу. конечно. 2. Найти самую плохо приближающуюся последовательность - задача имеет смысл, подумайте. 3. Получить аналитические функции, приближающие последовательности [math]p_i[/math] для известных последовательностей при их [math]{a_i \stackrel{ f }{\to} + \infty }[/math] 4. Использовать "трудные" последовательности из OEIS для отработки и тестирования программ и алгоритмов поиска глобального экстремума. Последняя задача имеет широкое практическое значение. |
|||||||||||||||||||||||||||||||||||||||||||||||||||
Вернуться к началу | |||||||||||||||||||||||||||||||||||||||||||||||||||
swan |
|
|
Я понял примерно 10% текста. Но возможно вы ищете это
|
||
Вернуться к началу | ||
swan |
|
|
Я понял примерно 10% текста. Как ваши соображения соотносятся с этим?
|
||
Вернуться к началу | ||
atlakatl |
|
|
swan
Отличия от линейки Голомба (ЛГ): 1. Деления линейки целые, моя последовательность [math]p_i[/math] в общем случае действительная. 2. ЛГ абсолютно точно аппроксимирует сколько возможно первые члены натурального ряда. [math]p_i[/math] допускает отклонения от ряда и без потерь аппроксимирует все возможные [math]qP \cdot (qP-1)[/math] членов. 3. ЛГ аппроксимирует только натуральный ряд. Мой алгоритм решает любую положительную последовательность. 4. Я за час смогу переделать программу, чтоб она считала ЛГ. А чтоб она считала хорошо, мне нужна неделя. |
||
Вернуться к началу | ||
bimol |
|
|
atlakatl
Пока нет программы, можно привести в качестве примера аппроксимацию простых чисел |
||
Вернуться к началу | ||
atlakatl |
|
|
bimol
Программу я мог бы выложить, подскажите только куда. А аппроксимация вот она: [math]qP=3, dS=0 0 2 5 qP=4, dS=0.5 0 7.5 10.75 12.75 qP=5, dS=1.4 0 7.2 10.6 12.6 29.6 qP=6, dS=13.3333333333333 0 16.6666666666667 35.3333333333333 40.6666666666667 44.8333333333333 47.5 qP=7, dS=27.7142857142857 0 8 14.5714285714286 27.5714285714286 31 69.1428571428571 73.7142857142857 qP=8, dS=57.25 0 6.375 9.875 13.75 42.75 68.5 88.5 109.25 qP=9, dS=154.777777777778 0 6.88888888888889 15.1111111111111 31.5555555555556 36.8888888888889 84.8888888888889 103.111111111111 143.444444444444 146.111111111111 qP=10, dS=243.2 0 4.4 46.1 70.7 105.9 156.5 169.3 178.7 185.7 196.7 qP=11, dS=284.363636363636 0 17.0909090909091 60.1818181818182 70 116.363636363636 153.454545454545 221.363636363636 226.818181818182 242 250.181818181818 256.545454545455 qP=12, dS=427.833333333333 0 4.41666666666667 7.91666666666667 14 43 111.5 174.666666666667 194.166666666667 240 265.333333333333 288.5 319.5 qP=13, dS=651.923076923076 0 13.2307692307692 39.6923076923077 54 77.2307692307692 112 235.076923076923 252.153846153846 282.307692307692 303.538461538462 385.769230769231 390.230769230769 396.769230769231 qP=14, dS=1399.71428571429 0 7.85714285714286 15.9285714285714 28.2142857142857 37.3571428571429 110.785714285714 195.928571428571 256.5 298.071428571429 345.214285714286 394.785714285714 419.5 462.642857142857 473.214285714286 qP=15, dS=3508.66666666666 0 8 36 60.1333333333333 69.6 100.533333333333 262.266666666667 278.666666666667 346.4 434.133333333333 448 454.266666666667 530.933333333333 574.866666666667 580.2 qP=16, dS=7225.375 0 9.625 21.125 93.75 149.375 164 253.875 270.625 367.875 445.25 579.875 602.25 625.6875 632.0625 661 668.625 qP=17, dS=16912.5294117647 0 11.9411764705882 19.3529411764706 58.3529411764706 91.1764705882353 214.588235294118 269.058823529412 277.764705882353 313.176470588235 450.470588235294 616.588235294118 640.470588235294 666.470588235294 682.705882352941 756.470588235294 770.941176470588 784.470588235294 qP=18, dS=30978 0 8.44444444444444 16.4444444444444 39 53.4444444444444 65.5555555555556 207.777777777778 318.333333333333 423.333333333333 495.222222222222 572.777777777778 657.833333333333 661.722222222222 753.444444444444 785.444444444444 844.111111111111 885.777777777778 906.333333333333 qP=19, dS=51354.3157894737 0 16.9473684210526 37.0526315789474 117.263157894737 135.947368421053 144.789473684211 208.526315789474 286.315789473684 439.157894736842 600.210526315789 640.842105263158 693.052631578947 764.631578947368 797.473684210526 974.947368421053 984.947368421053 1017.05263157895 1031.15789473684 1041.68421052632 qP=20, dS=93345.5 0 17.85 25.95 34.7 44.5 173 233.4 263.9 358.1 610.7 634.1 688.2 768.8 892.5 994.8 1057 1069.4 1106.2 1158.4 1173.5[/math] Так ряд [math](0, 2, 5)[/math] строит [math]2=2-0; 3=5-2; 5=5-0[/math] - абсолютно точно первые три простых. Дальше только приближённо, но всё равно оптимально: [math]0; 7.5; 10.75; 12.75[/math] строит [math]2=12.75-10.75; 3 \approx 10.75-7.5; 5 \approx 12.75-7.5; 7 \approx 7.5; 11 \approx 10.75; 13 \approx 12.75[/math] |
||
Вернуться к началу | ||
bimol |
|
|
А если взять такое приближение 0.5, 8, 11, 13 ?
|
||
Вернуться к началу | ||
atlakatl |
|
|
У линейки всегда должен быть 0. Вы фактически имеете его ввиду при формировании простых 11 и 13 - когда на самом деле следует отнять из них Ваш член 0.5. И тогда невязка становится больше оптимальной: 0.75.
Интуиция на таких функциях не работает. Попробуйте, не заглядывая в ответ, расставить 10 точек оптимальным образом. - Приближает первые 45 простых. |
||
Вернуться к началу | ||
За это сообщение пользователю atlakatl "Спасибо" сказали: bimol |
||
[ Сообщений: 8 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Перевод и разбор статей из OEIS
в форуме Размышления по поводу и без |
21 |
1100 |
28 ноя 2015, 15:22 |
|
Проверка принадлежности числа к OEIS.A146085
в форуме Ряды |
1 |
206 |
09 авг 2021, 17:56 |
|
Оптимальная выплавка | 0 |
309 |
01 июн 2015, 04:24 |
|
Оптимальная оценка | 0 |
535 |
29 ноя 2015, 16:47 |
|
Оптимальная длинна дорожки?
в форуме Алгебра |
4 |
149 |
27 апр 2021, 18:12 |
|
Оптимальная фильтрация (фильтры Калмана)
в форуме Теория вероятностей |
0 |
266 |
25 май 2016, 22:49 |
|
Оптимальная стратегия и теория вероятности
в форуме Комбинаторика и Теория вероятностей |
2 |
204 |
18 дек 2020, 11:22 |
|
Оптимальная конфигурация зарядов в шаре | 2 |
227 |
12 окт 2021, 12:02 |
|
Лимиты Последовательностей
в форуме Пределы числовых последовательностей и функций, Исследования функций |
1 |
263 |
31 окт 2014, 21:47 |
|
Предел последовательностей
в форуме Пределы числовых последовательностей и функций, Исследования функций |
2 |
312 |
28 ноя 2015, 00:03 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |