2014 dxdy logo

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

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




 
 Модели числовых последовательностей
Сообщение24.08.2020, 10:54 
Друзья, хочу обратиться за консультацией по следующему вопросу:

Проблематика: зачастую возникает потребность автоматизации обработки числовых последовательностей.
Хотелось бы придумать метаязык для описания моделей последовательностей, которые будут проверяться при поступлении исходных данных.

Пример, который решается просто: Поиск наличия общего итога в числовой последовательности.
Исходные данные, могут содержать общий итог, который может быть как первым, так и последним элементом последовательности.
Решение:
- находим $MaxValue = \max(FirstValue{set} | LastValue{set})$
- рассчитываем сумму всех элементов кроме без $Total = \sum({set}) - MaxValue$
- если $MaxValue = Total$, то считаем что есть вероятность наличия общего итога

Пример, который не получается решить: Поиск наличия подитогов в числовой последовательности.

Прошу помощи, в какую сторону копать чтобы понять, как можно определить, есть ли в последовательности чисел вероятность наличия подитогов?

 
 
 
 Re: Модели числовых последовательностей
Сообщение24.08.2020, 10:59 
Аватара пользователя
Непонятно, причем тут язык. Вы хотите проверить, верно ли, что последовательность разбивается на части, в каждой из которых первый или последний элемент является суммой остальных? Или что?

 
 
 
 Re: Модели числовых последовательностей
Сообщение24.08.2020, 12:00 
mihaild в сообщении #1480492 писал(а):
Непонятно, причем тут язык. Вы хотите проверить, верно ли, что последовательность разбивается на части, в каждой из которых первый или последний элемент является суммой остальных? Или что?


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

Да, верно, необходимо проверять, разбивается ли последовательность на части, для которых первый или последний элемент является суммой всех остальных. Какие математические (статистические) формулы/выражения могут это проверить. Или тут нужны не формулы/выражения, а что-то совсем другое?

 
 
 
 Re: Модели числовых последовательностей
Сообщение24.08.2020, 12:13 
Аватара пользователя
Если точное равенство - то это алгоритмическая задача. Решается, например, динамикой (для каждого отрезка смотрим, удовлетворяет ли он сам нужному свойству, или разбивается ли на удовлетворяющие).

 
 
 
 Re: Модели числовых последовательностей
Сообщение24.08.2020, 12:38 
mihaild в сообщении #1480508 писал(а):
Если точное равенство - то это алгоритмическая задача. Решается, например, динамикой (для каждого отрезка смотрим, удовлетворяет ли он сам нужному свойству, или разбивается ли на удовлетворяющие).


Важное дополнение, что числовая последовательность может быть длиной от 10 тыс до 100 млн значений.
Перебирать все варианты отрезков проблематично по ресурсам сервера и времени таких обработок.

 
 
 
 Re: Модели числовых последовательностей
Сообщение24.08.2020, 13:31 
Аватара пользователя
Ага, то есть квадрат не подходит, хотим быстрее.
Могут ли некоторые подитоги идти до соответствующего им отрезка, а некоторые после? Могут ли значения быть отрицательными? Если нет - то просто проверяем два варианта (сумма слева/справа), два прохода с доп. памятью на один элемент.

 
 
 
 Posted automatically
Сообщение24.08.2020, 13:47 
 i  Тема перемещена из форума «Экономика и Финансовая математика» в форум «Computer Science»
Причина переноса: связь этого с экономикой, если и имеется, для решения задачи явно несущественна.

 
 
 
 Re: Модели числовых последовательностей
Сообщение25.08.2020, 11:15 
Приношу извинения, что недостаточно подробно описал задачу.

Принимаем следующие соглашения:
1. Последовательность состоит из положительных или отрицательных чисел имеющих точность 4 знака после запятой.
Могут принимать значения от -1 * 10^12 до 1 * 10^12
2. Числовая последовательность может иметь от 10 тыс до 100 млн значений
3. Подитоги групп чисел для всей последовательности могут быть указаны только в конце группы

 
 
 
 Re: Модели числовых последовательностей
Сообщение25.08.2020, 11:22 
Аватара пользователя
Если числа были указаны точно (или известны правила округления - т.е. можно детерменированно восстановить сумму), то решается в один проход с линейной доп. памятью - бежим по последовательности, и запоминаем какие суммы префиксов возможны.

 
 
 
 Re: Модели числовых последовательностей
Сообщение25.08.2020, 12:14 
mihaild в сообщении #1480650 писал(а):
Если числа были указаны точно (или известны правила округления - т.е. можно детерменированно восстановить сумму), то решается в один проход с линейной доп. памятью - бежим по последовательности, и запоминаем какие суммы префиксов возможны.


А можно для "школьников" подробнее описать проход по пунктам?

 
 
 
 Re: Модели числовых последовательностей
Сообщение25.08.2020, 12:37 
Аватара пользователя
По пунктам - запрещено правилами.
Пусть $k$-й отрезок заканчивается в позиции $i$, $k-1$-й - в позиции $j$, и сумма элементов от начала до $i$-го равна $s$. Чему равна сумма элементов от начала до $j$-го?

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


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