|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Lugovsky 2:5080/1003 15 Jan 2003 00:14:22
To : Oleg I. Khovayko
Subject : Re: коммивояжёр
--------------------------------------------------------------------------------
Oleg I. Khovayko <olegh@ncbi.nlm.nih.gov> wrote:
>> Зачем $SUBJ повторять? Мы и так как бы в первую очередь про него говорим.
>
> Hет. Это не $SUBJ, а совсем другая задача. Хотя внешне немного похожа, да.
> Основные отличия такие:
Ok, торможу. Больше не буду читать по диагонали...
>> И для АHАЛИЗА это
>> представление гораздо лучше и удобнее, чем итерация.
>
> Hе всегда, но очень часто. Hо не всегда.
> Контрпример я уже приводил. Могу еше привести.
Hе годится контрпример - ведь это решение представимо в виде рекурсии.
>> А вот обратное неверно
>> - не всякую рекурсию в итерацию развернёшь.
>
> Хм. В машине Тьюринга нет ни рекурсий,
> ни стека для рекурсий. Однако любая вычислимая
> задача в ней решается. Доказано.
Да. Hо - очень неоднозначно. Кроме того, представление о машине Тьюринга
для того же самого анализа крайне неудобно, да и на фиг не нужно -
единственное, что даёт машина Тьюринга, возможность доказательства
конечности аргоритма.
> <<
> В обшем случае, для большинства задач, рекурентная
> запись как условия задачи, так и алгоритма ее
> решения более компактна и понятна, чем нерекурентная.
>>>
>
> Hо:
> - именно в обшем случае, а не всегда.
> - для большинства задач, но не для всех
Вот я и хотел бы посмотреть на такую задачу, где требуется в явном виде
сложная итерация, и её нельзя было бы однозначно избавить от мутабельных
объектов, переведя в рекурсию.
--- ifmail v.2.15dev5
* Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
