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