|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilya Rogov 2:5030/1334.1024 09 Feb 2003 05:20:34
To : Vitaly Lugovsky
Subject : Урощение формул
--------------------------------------------------------------------------------
Давным-давно, 06 Feb 03 04:37, когда земля была ещё тёпленькая
и по ней бегали мамонты, Vitaly Lugovsky и Ilya Rogov говорили про Re: Урощение
формул:
>> во-вторых - зачем упрощать формулу "x" ??
VL> Затем, что разворачивание x может помочь упростить всё выражение.
VL> Посмотри, как системы символьной алгебры работают - чуть ли не
VL> бОльшая часть правил упрощения содержит развёртку.
Кхм, про это не было написано. И я думаю, что стоит упрощать ВСЁ ВЫРАЖЕHИЕ
сразу, а не отдельные его части.
>> Как я понимаю, мы должны выбирать из эквивалентных выражений то,
>> которое либо короче, либо содержит наименьшее число операций.
VL> Hет. Короче должен быть окончательный результат. Hо путь к нему
VL> вовсе не обязательно будет содержать только всё более короткие
VL> выражения.
Я имел в виду конечный результат, а не первый шаг.
VL> Ты что, в школе плохо учился? Задач на упрощение формул мало решал?
Учился я, скорее всего, лучше тебя. И решал тоже больше. Будем пiпiцьkamи
мерицца ? :-))
>> Строгое доказательство - эт карашо. Давай.
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о, ты считаешь, что именно эта задача решается при упрощении
>> выражения в тех же Matlab/Matcad/Derive ?? А я вот думаю, что нет.
VL> Я знаю, что эта задача не решается в общем случае. Вообще. Это
VL> задача о КОЛИЧЕСТВЕ ИHФОРМАЦИИ. Офигенно фундаментальная штука, на
VL> которой построена вся естественнонаучная методология.
Эта задача и не решается.
Ilya Rogov
... Бредить помогали вопли моих соседей
---
* Origin: Когда Бог делал время - он сделал его достаточно (2:5030/1334.1024)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
