Отправляет email-рассылки с помощью сервиса Sendsay

Бизнес on-line

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Бизнес on-line" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Декабрь 2002   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
bezumnyj.shlyapnik@yandex.ru

Статистика

10.778 подписчиков
+8.255 за неделю
←   Все выпуски   →

Softcraft: новости сайта и не только (039)


Информационный Канал Subscribe.Ru

Softcraft: новости сайта и не только(039)

http://www.softcraft.ru

Я приветствую всех своих подписчиков!

Так получилось, что последние обновления статей на сайте происходят парами, навевая, тем самым, ассоциации с детским стишком Агнии Барто: "Мы с Тамарой ходим парой...". Однако, если в двух предыдущих случаях "Твикс" подавался в связи поступлением материалов в одной упаковке, то в данной ситуации "спаривание" произошло в связи с практически одновременным выходом статей и близостью тематик. Предлагаются:

Статьи перекликаются между собой рассуждениями о рекурсиях и итерациях, аппеляцией к одному и тому же "раздражителю" (Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Ханойские башни и автоматы), а также общему источнику вдохновения, известному чуть ли ни с детства - ханойской башне.

Быть рекурсией прекрасно, ну а циклом лучше?

Интересно сопоставить мотивы статей.

Из заключения "Ханойских башен и автоматов" следует, что "Несмотря на то, что длина автоматных программ превышает размер традиционных, такие программы обладают тем преимуществом, что по их тексту может быть формально построен граф переходов, который является наиболее компактной и удобной для визуализации и документирования графической формой представления программ и их алгоритмов". Основной же идеей является демонстрация, на конкретной задаче, методов преобразования рекурсиивных функций в конкретную конечно автоматную модель реализуемую в дальнейшем с использованием SWITCH-технологии.

В "Раздражителе" проблема конечности состояний преодолевалась тем, что на рабочую память, используемую функциями выходов, не накладывается никаких ограничений. Это легко и вполне естественно позволяет моделировать самые сложные алгоритмы. Необходимость же получить на выходе нужную автоматную модель вполне объяснима целевыми задачами.

Общеизвестно, что преобразование непараметризированных левых и правых рекурсий в итерации протекает без каких-либо проблем. Непараметризированная и неконцевая рекурсия достаточно просто преобразуется в итерацию, если использовать стек. (Вспоминается программирование на когда-то нерекурсивных Бейсике и Фортране...) Да и стоит ли говорить о проблемах преобразования рекурсий в итерации и обратно? Математически они являются эквивалентным представлением рекуррентности, а процесс преобразования давно изучен и неплохо формализован.

"Фокус-покус и никакого..."

Моя статья о лабиринтах Ханойских башен была вызвана сомнением в высказанном авторами предположении о неконцевой рекурсии в Ханойских башнях. Поэтому я попытался показать, что исходная задача имеет рекурсии на концах, а их спецификой является наличие параметрических выражений, что и затрудняет прямое сведение к итерациям. Однако, подобное сведение возможно если подыскать формулу, обеспечивающую получение результатов, выполняемое ранее параметрическими выражениями. Именно сам подход я и считаю основной идеей статьи. Остальное: получение формулы, дополнительных (более быстрых) решений и сопоставление с автоматными решениями - это вполне естественное оформление материалов подобного плана.

Рассмотренный прием является универсальным и легко применим в других аналогичных ситуациях. Если для ханойской башни получить нужную формулу удалось не сразу, то во многих подобных ситуациях концевая параметрическая рекурсия преобразуется в итерацию достаточно быстро. Можете сами попробовать на функции, вычисляющей факторил как с использованием левой, так и правой рекурсии. Аргумент функции является параметром, преобразуемым в "формулу".

"Что такое хорошо и что такое плохо?"

Мотивами "Борьбы с рекурсией" явились следующие причины: "Первая - скорость работы алгоритмов, вторая - проблемы с реализацией рекурсии... ...насколько вообще актуальна проблема устранения рекурсии."

В результате провозглашается: "Что такое рекурсия, необходима ли...? ...нужна, если скорость работы программы имеет малое значение, если не нужно решать проблему параллельного функционирования программных модулей (прежде всего в рамках самого приложения), то устранением рекурсии вряд ли имеет смысл вообще заниматься.".

Параллельные миры

В мире существет много религий, о чем достаточно ясно выразился В. Высоцкий: "Кто верит в Аллаха, кто в Исууса, кто ни во что не верит, даже в черта, назло всем...". Программирование, как и многие другие сферы человеческой деятельности не избежало подобных разделений по методологиями парадигмам и прочим параметрам. Бывает, что детальное познание какого-то одного инструмента приводит истовой вере в его повсеместной необходимости. И это не обязательно автоматное программирование. Сторонники различных подходов зачастую разговаривают друг с другом на разных языках. Вполне естественно, что их доводы не только не разбиваются друг о друга: они просто сосуществуют независимо и параллельно в одном пространстве в соответствии с принципом суперпозиции.

По поводу написанного, каждый из авторов этих двух статей попытался высказать друг другу свои претензии. Чтобы "не выносить сор", я оставил его на сайте в виде очередных брюзжалок.

С наилучшими пожеланиями!

А.Л.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное