Теория алгоритмов

[Sonic86]

Я думаю, что отношение "$A$ - подзадача $B$" существенно зависит от кодировки задачи. В общем случае потребовалось бы уметь проверять сводимость задач друг к другу, что смахивает на проблему изоморфизма.
Например, если есть задача "Решить уравнение $f(x_1,...,x_n)=0$" в целых $x_i$, то что для нее м.б. подзадачей - вообще неясно, кроме простого варианта, когда мы разбиваем множество значений $(x_1,...,x_n)\in D$ на непересекающиеся множества $D_1\cup ...\cup D_k$ и решаем это уравнение на каждом $D_j$ отдельно.

Понятие "задача" я пока понимаю так: дан предикат $P(x_1,...,x_n)$, надо найти (в некотором смысле) один или все $(x_1,...,x_n)$, обращающие.
$P$ в тождество.
Вообще чтобы получить понятие в прикладной CS, надо сначала его определить где-то в математике.

[Sender]

Mihaylo в сообщении #1444907 писал(а):

Мы имеем две задачи, одна из которых претендует быть подзадачей другой. Как проверить, не предъявляя окончательный алгоритм большой задачи?

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

[Mihaylo]

Sonic86 в сообщении #1444909 писал(а):

Например, если есть задача "Решить уравнение $f(x_1,...,x_n)=0$" в целых $x_i$, то что для нее м.б. подзадачей - вообще неясно, кроме простого варианта,

Возьмите любой алгоритм, например, тот, который перебирает варианты решения в лоб. Подставили один некоторый набор $x_1,...,x_n$ в уравнение, получили некоторый результат положительный или отрицательный - неважно, но уже решили подзадачу.

[arseniiv]

Mihaylo в сообщении #1444907 писал(а):

Как проверить, не предъявляя окончательный алгоритм большой задачи?

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

Нужно ли чтобы найти произведение трёх чисел $abc$, имея изначально $a, b, c$, найти произведение $ab$? Иногда нужно, иногда не нужно. Иногда зависит от входных данных (допустим от изменения порядка умножения изменится точность ответа, а мы решили стараться её иметь побольше).

-- Вс мар 15, 2020 22:47:38 --

(Оффтоп)

arseniiv в сообщении #1444985 писал(а):

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

Синтаксис получился с инопланетным привкусом.

[Mihaylo]

arseniiv в сообщении #1444985 писал(а):

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

Пути решения $=$ алгоритмы.

Но вот, например, перемножение $a \cdot b$ - это ещё интуитивно воспринимается как подзадача $a \cdot b \cdot c$, а $\frac{a}{b}$ не очень. Есть ли критерий всё-таки? Или это кажется из-за того, что известен оптимальный алгоритм?

[eugensk]

Mihaylo в сообщении #1444907 писал(а):

Мы имеем две задачи, одна из которых претендует быть подзадачей другой.

Предположу, что вас интересует динамическое программирование, поищите гуглом. Много книг на либгене, этой теме больше лет чем структурному программированию.

[arseniiv]

Mihaylo в сообщении #1445191 писал(а):

Но вот, например, перемножение $a \cdot b$ - это ещё интуитивно воспринимается как подзадача $a \cdot b \cdot c$

Как я уже написал, зря. Потому что мы можем вычислять так: $a(bc)$.

[Mihaylo]

eugensk в сообщении #1445193 писал(а):

Предположу, что вас интересует динамическое программирование

Я знаю эту технику. Это частный простой случай. Хотелось бы обобщить.

arseniiv в сообщении #1445229 писал(а):

Как я уже написал, зря. Потому что мы можем вычислять так: $a(bc)$.

Есть два разных алгоритма, условно $(ab)c$ и $a(bc)$. Оба они в процессе выполняют подзадачи и эти подзадачи разные.

Теперь третий вариант алгоритма: делаем первый шаг $\frac{a}{b}$. Как доказать, что этот шаг неправильный? Как отмести такой алгоритм, с таким начальным шагом?

[eugensk]

Mihaylo в сообщении #1445375 писал(а):

Я знаю эту технику. Это частный простой случай. Хотелось бы обобщить.

То есть знаете как приём программирования. Почитайте всё же теорию, чтобы лучше ориентироваться в том "как доказать".

[Xaositect]

Mihaylo в сообщении #1445375 писал(а):

Теперь третий вариант алгоритма: делаем первый шаг $\frac{a}{b}$. Как доказать, что этот шаг неправильный? Как отмести такой алгоритм, с таким начальным шагом?

Ну $\frac{a}{b}(b^2c)$ вполне вычисляет то, что надо.
Больше того, я могу придумать (нереалистичную) модель, когда этот алгоритм будет самым эффективным - если начиная с некоторого числа цифр в числе умножение внезапно становится очень медленным, а сложность деления такого скачка не имеет, и при этом таши типичные данные имеют $a$ чуть выше этого предела, а $b$ и $c$ значительно меньше.
То есть надо все-таки привлекать теорию сложности. Проблема в том, что в теории сложности таких тонких результатов (какие промежуточные значения могут вычисляться оптимальными алгоритмами) практически нет.

[_Ivana]

У меня был реальный кейс, когда заменял

(a+b)/2

на

a+(b-a)/2

[Mihaylo]

Xaositect в сообщении #1445388 писал(а):

То есть надо все-таки привлекать теорию сложности.

А сложность ли это? Все пути расчета (алгоритмы) - одинакового класса сложности...

[mihaild]

Mihaylo в сообщении #1445564 писал(а):

Все пути расчета (алгоритмы) - одинакового класса сложности

Что вы тут понимаете под классом сложности?
(классически классы сложности вообще определяются для задач, а не для алгоритмов)

[Xaositect]

Это именно теория сложности, она занимается не только очень сложными задачами.
Есть, например, такой результат: если разрешается использовать только арифметические операции, то для вычисления общего многочлена степени $n$, то есть $\sum_{k = 0}^n a_k x^k$ как функции от $a_0, \dots, a_n$ и $x$, необходимо $n$ сложений и $n$ умножений, и единственный алгоритм, использующий $n$ сложений и $n$ умножений - это схема Горнера.

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

[Mihaylo]

Xaositect в сообщении #1445626 писал(а):

Это именно теория сложности, она занимается не только очень сложными задачами.

Вычисление времени выполнения $T[n]$ для конкретной вычислительной машины неинтересно в силу необщности результата. Других подходов я не слышал.
Ладно, допустим предъявлены два алгоритма $a(bc)$ и $\frac{a}{b}(b^2c)$ (пусть деление на ноль не рассматривается как проблема). Существует ли универсальное доказательство, что первый алгоритм эффективнее? Можно как-то задать ограничения для чисел $a, b, c$. Ну и важное: кроме этих чисел ничего не дано, нет готовых $\frac{a}{b}$ и $b^2$.
Наверное доказательство вполне простое - нужно просто посчитать количество эквивалентных операций в обоих алгоритмах и понять, что во втором алгоритме их столько же, но там есть еще лишние операции.
То есть сравнительный подход существует, но для этого нужно предъявить искомый алгоритм целиком и эталонный алгоритм.

Xaositect в сообщении #1445626 писал(а):

если разрешается использовать только арифметические операции

Да, понятно, но в частный случай уходить неинтересно. Интересно лишь для примера.