|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Lugovsky 2:5080/1003 06 Feb 2003 05:37:13
To : Ilya Rogov
Subject : Re: Урощение формул
--------------------------------------------------------------------------------
Ilya Rogov <Ilya.Rogov@p1024.f1334.n5030.z2.fidonet.org> wrote:
> >> Покажи мне его бесконечность. Обоснуй.
> VL> Элементарно. Хотя бы на примере:
> VL> x = x+0 = x+x*0 = x + x - x = sqrt(x^2) = ...
>
> Кхм-кхм. Во-первых - в четвёртом случае мы получим abs(x);
Забыл сказать, x - положительное целое. ;)
> во-вторых - зачем
> упрощать формулу "x" ??
Затем, что разворачивание x может помочь упростить всё выражение.
Посмотри, как системы символьной алгебры работают - чуть ли не бОльшая часть
правил упрощения содержит развёртку.
> Как я понимаю, мы должны выбирать из эквивалентных
> выражений то, которое либо короче, либо содержит наименьшее число операций.
Hет. Короче должен быть окончательный результат. Hо путь к нему вовсе не
обязательно будет содержать только всё более короткие выражения. Ты что,
в школе плохо учился? Задач на упрощение формул мало решал?
> VL> Если пример не убедил - могу и строгое доказательство привести, для
> VL> арифметики, логики, или чего угодно ещё.
>
> Строгое доказательство - эт карашо. Давай.
Ok. Чуть позже кину.
> >> И ещё раз - обоснуй, почему правила и стратегии необходимо
> >> применить бесконечно много раз.
> VL> Я не понял твоего вопроса.
>
> Ещё раз (ну так, на всякий случай) объясняю свой вопрос: у нас есть
> символьное выражение "A". Мы хотим перевести его в какую-либо другую форму.
> (Кста, никто не говорил, что эта новая форма будет наилучшей из всех
> возможных.) Я предполагаю, что это можно сделать путём конечного числа
> применений правил, выбранных нашими стратегиями.
Конечно же можно. Hо число путей от представления A к эквивалентному
представлению B - бесконечное. Учитывая раскрутку выражений. Как выбрать
один из бесконечного числа путей?
> VL> Вот тебе задачка для затравки: есть выражение A, есть доказанно
> VL> тождественное ему выражение B, сложность коего (оцениваемая функцией
> VL> c(B)) меньше, чем c(A). Каким образом определить, что данное выражение
> VL> B имеет наименьшее значение c(x) из всех {x: A -> x} (множества всех
> VL> выражений, тождественных A)?
>
> Конкретно эту задачу можно решить лишь перебором всех {x: A -> x} (хотя я в
> этом не уверен, буду думать).
Полного перебора не надо. Можно упорядочить по сложности, и смотреть только
на те выражения, у которых сложность та же или меньшая.
> Hо, ты считаешь, что именно эта задача решается
> при упрощении выражения в тех же Matlab/Matcad/Derive ?? А я вот думаю, что
> нет.
Я знаю, что эта задача не решается в общем случае. Вообще. Это задача о
КОЛИЧЕСТВЕ ИHФОРМАЦИИ. Офигенно фундаментальная штука, на которой построена
вся естественнонаучная методология.
--- ifmail v.2.15dev5
* Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
