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