|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilya Rogov 2:5030/1334.1024 05 Feb 2003 01:23:04
To : Vitaly Lugovsky
Subject : Урощение формул
--------------------------------------------------------------------------------
Давным-давно, 03 Feb 03 06:15, когда земля была ещё тёпленькая
и по ней бегали мамонты, Vitaly Lugovsky и Ilya Rogov говорили про Re: Урощение
формул:
>> Покажи мне его бесконечность. Обоснуй.
VL> Элементарно. Хотя бы на примере:
VL> x = x+0 = x+x*0 = x + x - x = sqrt(x^2) = ...
Кхм-кхм. Во-первых - в четвёртом случае мы получим abs(x); во-вторых - зачем
упрощать формулу "x" ?? Как я понимаю, мы должны выбирать из эквивалентных
выражений то, которое либо короче, либо содержит наименьшее число операций. Всё,
что ты вывел из "х" не подходит ни туда, ни сюда.
VL> Если пример не убедил - могу и строгое доказательство привести, для
VL> арифметики, логики, или чего угодно ещё.
Строгое доказательство - эт карашо. Давай.
>> Согласен. Есстественно они не просто заменяются друг на друга, а
>> некоторым определённым образом. Hапример, с использованнием заданных
>> стратегий.
VL> А стратегия - это и есть порядок обхода дерева. Выбор из
VL> бесконечного числа вариантов только потенциально перспективных.
О! Шушпанчик ! Тьфу, т.е. консенсус :-)))
>> И ещё раз - обоснуй, почему правила и стратегии необходимо
>> применить бесконечно много раз.
VL> Я не понял твоего вопроса.
Ещё раз (ну так, на всякий случай) объясняю свой вопрос: у нас есть
символьное выражение "A". Мы хотим перевести его в какую-либо другую форму.
(Кста, никто не говорил, что эта новая форма будет наилучшей из всех возможных.)
Я предполагаю, что это можно сделать путём конечного числа применений правил,
выбранных нашими стратегиями.
VL> Или ты ни хрена не понял из моих объяснений.
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 ?? А я вот думаю, что нет.
Ilya Rogov
... Бредить помогали вопли моих соседей
---
* Origin: Когда Бог делал время - он сделал его достаточно (2:5030/1334.1024)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
