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

Алгоритмы для всех

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 3.603 RSS
←   Декабрь 2005   →
 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


За последние 60 дней ни разу не выходила


Открыта: 07-06-2000

Автор
Сергей Пушкарев

Статистика

3.603 подписчиков
0 за неделю
←   Все выпуски   →

Алгоритмы для всех


Информационный Канал Subscribe.Ru
5"12"16
Вы читаете выпуск #79 рассылки "Алгоритмы для всех"

Алгоритм косой. 

Причина, по которой данное предписание называется КОСЫМ алгоритмом (см. пме125),
а не просто оным, заключается в том, что переход между базовыми (основными, крупными)
его шагами не есть простой переход (из стандартного набора "А ПОТОМ", "А ДЛЯ
ЭТОГО НУЖНО", "А ТАКЖЕ", "ИЛИ", "А ЭТО ОЗНАЧАЕТ", "А ПЕРЕД ЭТИМ"), а содержит
(пме155) в себе неявное (не приведенное здесь, - потому что я его не могу (пока?)
выявить (пме156)) препятствие (сн6, 14, 125). Т.е., движение тут идет не строго
сверху вниз (как в обычном вертикальном
алгоритме (сн7) (от шага вниз к следующему шагу), а влево (от шага к препятствию)
и вниз (от препятствия к следующему шагу, - средству преодоления препятствия).
"Результирующий вектор" получается направленным по диагонали.

Вот так (смотрите и печатайте со шрифтом типа "Курьер"):

 рис.1                      рис.2    
Обычный                 Косой алгоритм
алгоритм       а) полная форма      б) свернутая форма

  шаг       шаг -> препятствие            шаг
   |                    |             =>     \
   V                    V                     V
следующий     следующий шаг (средство     следующий
   шаг        преодоления препятствия)       шаг

При даче свернутой формы косого алгоритма (рис. 2б) в обычном тексте его "косотА"
:) , естественно, никак не передается (снк25), и внешне он выглядит как обычный
алгоритм (снк24). Но при выполнении это может привести (снк42) к трудностям (снк43)
из-за того, что препятствия вообще искажают целе-средственные связи, и из-за
того, что эти препятствия здесь (пме126) - невидимые.

Все обозренные :-) Половинкиным (МПНс6-42) и Джонсом (Джонс"1986) методы, насколько
я могу судить, являются косыми алгоритмами и неизбежно будут порождать шаблоны
(см. снк42).

Первый раз я использовал понятие косого предписания, кажется, в Пушкарев"2002"9в31%31
 .

Впрочем, название "косой", пожалуй, не совсем точно. Я вчера (3"2"5) делал заголовок
для своего стендового доклада. Мне нужно было разнести текст заголовка на четыре
страницы так, чтоб потом на стенде, состыковав их, получить вновь целый заголовок.
(Помню, когда-то была программа "Banner" специально для такой цели.) Если убрать
ненужные подробности, дерево будет выглядеть так:

1) сделать 4 страницы с заголовком доклада, А ДЛЯ ЭТОГО НУЖНО #2, А ПОТОМ #9
2) сделать через соответствующую опцию в WinWord'е, А ДЛЯ ЭТОГО НУЖНО
3) ПРЕОДОЛЕТЬ ПРЕПЯТСТВИЕ: я не нашел в нем такой возможности, А ДЛЯ ЭТОГО НУЖНО
4) сделать через PowerPoint, А ДЛЯ ЭТОГО НУЖНО
5) ПРЕОДОЛЕТЬ ПРЕПЯТСТВИЕ: он распечатал только 1 страницу из середины заголовка,
А ДЛЯ ЭТОГО НУЖНО
6) сделать через макет в ArcView, А ДЛЯ ЭТОГО НУЖНО
7) ПРЕОДОЛЕТЬ ПРЕПЯТСТВИЕ: она распечатала только начало заголовка (1 страницу),
А ДЛЯ ЭТОГО НУЖНО
8) сделать в WinWord'е вручную: получилось, 
9) повесить на стенд

Изобразив эти шаги в форме, описанной выше, получим:

|
V
2 -> 3
     |
     V
     4 -> 5
          |
          V
          6 -> 7
               |
               V
               8

Убрав из виду препятствия, получим:

2
 \
  V
   4
    \
     V
      6
       \
        V
         8

И недовольство мое этой картинкой вызвано тем, что я понял, что шаги 2, 4, 6
и 8, вообще говоря, являются АЛЬТЕРНАТИВНЫМИ способами. И, следовательно, должны
(Ну, вы помните: "Кому должна я, я всем прощаю!" :) (Пушкарев"2002"10"27ст1%53))
располагаться на одном уровне (пме98). Т.е. так:

|
V
2 -> 4 -> 6 -> 8

Возвращая на место препятствия, получаем такую картинку:

|
V
2     4     6    8
 \   ^ \   ^ \   ^
  V /   V /   V /
   3     5     7

Или такую:

    3     5     7
|  ^ \   ^ \   ^ \
V /   V /   V /   V
2      4     6     8


Удобнее (для держания в голове (пме238)), пожалуй, будет считать, что "местА"
для действий и препятствий чередуются "полосами". Вот так:

--------------------- 
действие
--------------------- 
препятствие
---------------------
действие
---------------------
препятствие
---------------------
 ...

(Хотя, МБ, точнее будет представление в хэмминговом (двоичном многомерном), а
не в декартовом пространстве.)

И рассматриваемое здесь дерево изобразим так:

              |
              V
действие      2   4   6   8
____________  |  ^|  ^|  ^|
              V / V / V / |
препятствие   3   5   7   |
____________              |
                          V
действие                  9


Т.е., имеет место "полоса препятствий" :-) , которую не всеми способами можно
преодолеть.

Если я теперь снова спрячу препятствия, то получу не косую линию из стрелок,
а угол:

|
V
2 -> 4 -> 6 -> 8
               |
               V
               9

И, соответственно, рассматриваемые здесь алгоритмы, МБ, точнее будет назвать
"угловыми" или "угловатыми".

Хотя название "косой", наверно, можно и оставить... Только имея теперь под ним
в виду "кОсость" :-) ВООБРАЖАЕМОГО "результирующего вектора".

Кстати, то, что я понаписал и понарисовал выше в этом разделе, я в своей работе
не использовал (ну, МБ, единственно, чтоб название скорректировать), не использую
и, скорее всего, использовать не буду. Это написано с целью ОБЪЯСНЕНИЯ ВАМ некоторых
других действительно полезных (НМВ :-) ) вещей. И, НЯМС, большая часть не-художественной
литературы занята именно подобным объяснянием от тех, кому есть что сказать и
подражанием (мимикрия :-) ) этому объяснянию от тех, кому сказать нечего. Хотя
достаточно лишь дать
предписание, использованное самим автором в его РЕАЛЬНОЙ работе. Всего делов-то!
:-)

Примечания.

98. Нет, стоп. Пожалуй, про уровень я тут зря. Уровень, конечно, будет одинаковый,
но здесь важно не это, а одинаковость порядкового номера шага, что ли...

125. 3"3"26 Вообще говоря, третий базовый шаг здесь сам есть преодоление препятствия,
- в явном виде. А между первым (выявление граничной цели) и вторым (постановка
идеальной задачи) переход у меня происходит совершенно гладко, - как и в обычных
моих алгоритмах. Никакого "ухаба" я не чувствую. Неужели я (втайне от себя! :)
) излечил алгоритм ПА от "косизнЫ"!? :)

"- Шутите! - сказала Эллочка нежно. - Это мексиканский тушкан.
- Быть этого не может. Вас обманули. Вам дали гораздо лучший мех. Это шанхайские
барсы. Ну да! Барсы! Я знаю их по оттенку. Видите, как мех играет на солнце!..
Изумруд! Изумруд!.." (Ильф, Петров"1993с152о8-9)

Похоже, я малость поторопился, назвав свою версию косым алгоритмом... Версия
ГСА -, однозначно, косой алгоритм, а вот моя-а-а... Ладно, оставим вопрос открытым.

В своих рабочих алгоритмах я выношу (примерно, с сентября 2002 года) все препятствия
в дерево предписаний, отходящее от данного алгоритма (пме232). В принципе, можно
и алгоритм ПА таким образом изобразить попробовать... Посмотрим. МБ, в следующей
версии...

126. В общем, относите эти мои рассуждения к версии ГСА: в своей версии я препятствия
сделал видимыми.

155. А, может, и не содержит... :) См. пме125.

156. Или потому, что такие препятствия в моей версии ПА вообще отсутствуют...
"Трудно найти черную кошку в темной комнате. Особенно, если ее там нет." (Китайская
пословица) :) См. пме125.

232. Поскольку удобнее работать, когда алгоритм имеет структуру строго вида 

"<название алгоритма (= цель выполнения алгоритма)>
, А ДЛЯ ЭТОГО НУЖНО 
{<шаг # такой-то>, А ПОТОМ}"

, - не "захламленную" :-) ни препятствиями, ни переходами других типов. (Фигурные
скобки там означают множество.)

238. Шаблоны, шаблоны строю... :) - См. пме168.

В-головЕ-тый.

Находящийся в голове. :-) 

Образован добавлением суффикса и окончания "-тый", позаимствованных у некоторых
причастий ("мыТЫЙ", "выпиТЫЙ"...) (снк44), к дополнению (мЕста) "в голове". В
принципе, суффикс "т" там не обязателен (н-р, "по-дням-ый" :-) ), - вставляю
его там, где того требует благозвучие (см. тж пме8).

Вне-головЫ-тый.

Находящийся вне головы. :-) См. предыдущий раздел.

========================

Продолжение следует. 

----------------


Сергей Пушкарев, pushkaryov@newmail.ru
Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора		 Подписан адрес:
Код этой рассылки: people.algorithm
Архив рассылки		 Отписаться
Вспомнить пароль
В избранное