Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 37
Текст из файла (страница 37)
1, в противном случае — е„= О. г с(г) 1 2 2 3 3 5 4 5 11 6 19 7 29 8 47 9 71 () 10 127 11 191 12 379 13 607 14 1087 И 1903 16 3583 17 6271 18 11231 г с(г) 19 18287 20 34303 21 65131 22 110591 23 196591 24 357887 25 685951 26 П76431 27 2211837 Таблица 1 ЗНАЧЕНИЯ и ДЛЯ СПЕЦИАЛЬНЫХ АДДИТИЕНЫХ ЦЕПОЧЕК 453 553 599 645 707 741 455 557 611 659 709 749 457 561 619 667 711 759 479 569 623 669 713 779 503 571 631 677 715 787 509 573 637 683 717 803 551 581 643 691 739 809 23 163 229 319 371 413 43 165 233 323 373 419 59 179 281 347 377 421 77 ЮЗ 283 349 381 423 83 211 293 Зэ5 382 429 107 213 311 359 395 437 149 227 317 367 403 451 813 849 903 825 863 905 835 869 923 837 867 941 839 893 947 841 899 955 845 901 983 Пусть д(т) обозначает количество решений и уравнения 1(п) = т. В следующей таблице перечислено несколько первых значений этой функции согласно Фламыенкамну.
т й(т) т г((т) т д(т) т И(т) т т)(т) 1 1 6 15 11 246 16 4490 21 90371 2 2 7 26 12 432 17 8170 22 165432 3 3 8 44 13 772 18 14866 23 303475 4 5 9 78 14 1382 19 27128 24 558275 5 9 10 136 15 2481 20 49544 25 1028508 Конечно, п(т) должно быть возрастающей функцией от т, но не существует ясного способа доказательства этого кажущегося таким простым утверждения и тем более — определения асимптотического роста 6(т) для больших т.
Наиболее знаменитая проблема, связанная с аддитивными цепочками и все еще нерешенная, — гипотеза Шольца-Брауэра, гласящая, что 1(2а Ц < и 1+1(п) (49) Компьютерные вычисления показывают, что в действительности в (49) выполняется равенство для 1 < и < 24, Вычисления, проведенные Э. Г. Тюрбером [Иэсгеге Май.
16 (1976), 279-289), показали, что равенство справедливо также для и = 32. Множество исследований эдзитивных цепочек посвящено попыткам доказать (49). Адднтивиые цепочки для чисел 2"-1, которые имеют так много единиц в их двоичном представлении, вызывают особый интерес, поскольку они являются наихудшим случаем для бинарного метода. Арнольд П1ольц (АгпоЫ ВсЬо)э), придумавший название "алдитивные цепочки", поставил в 1937 году задачу (49) [,7а)иеэЬеэ9сЬ с)ег оеигэсЛеп МагЬетаВ7гег- Чехншйипя, А1не)1цпй П, 47 (1937), 41-42[; Альфред Брауэр (А)(ген Вгапег) в 1939 году доказал, что 1'(2" — 1) < и — 1+1'(и).
(50) Теоремы Хансена показывают, что 1(п) может быть меньше, чем 1'(и), так что, определенно, потребуется ь1ного работы, чтобы доказать или опровергнуть (49). В качестве шага в этом направлении Хансен определил концепцию 1о-Чспочкть которая лежит "между" 1- и 1'-цепочками. В 1е-цепочке некоторые элементы подчеркнуты; условие заключается в том, что а~ = а1+ вы где ау — наибольший подчеркнутый элемент, меньший, чем аь В качестве примера 1е-цепочки (конечно, не минимальной) рассмотрим 1,, я, 3, 5, й, 10, 12, Ай. Легко убедиться, что разность между каждым элементом и предшествующим ему подчеркнутым элементом принадлежит цепочке. Обозначим через 1о(п) минимальную длину 1о-цепочки для и.
Ясно, что 1(и) < 1е(п) < 1'(и). Цепочка, построенная в теореме Р, является 1о-цепочкой (см. упр. 22); следовательно, имеем 1е(п) < 1'(и) для некоторого и. Неизвестно, выполняется ли равен- стао 1(п) = 1о(п) во всех случаях. Если оно истинно, то предположение ШольцаБраузра должно быть справедливо вследствие еще одной теоремы Хансена. Теорема С 1о(2 1) < и 1 +1е(п) Доказательство. Пусть 1 = ае, а„..., а, = и — 1е-цепочка минимальной длины для и и пусть 1 = 6е, Ьх, ..., Ьх — — и — последовательность подчеркнутых элементов. (Можно считать, что п подчеркнуто.) Тогда 1о-цепочку для 2" — 1 можно получить следуюпхим образом.
а) Включить 1о(п) + 1 чисел 2" — 1 дзя О < 1 < т, подчеркнуть их тогда и только тогда, когда а~ будет подчеркнуто. Ь) Включить числа 2'(26' — 1) длЯ 0<7' <1 и 0 <1< Ьхе — Ь и подчеРкиУть их все. (Теперь всего имеется Ьх — Ьо+ ° + Ьх — (ч ~ = п — 1 чисел.) с) Рассортировать числа из (а) и (Ь) в порядке возрастания. Можно легко проверить, что это дает 1е-цепочку: числа из (Ь) равны некоторым удвоенным элементам нз (а) или (Ь); кроме того, данный элемент представляет собой предшествующий подчеркнутый элемент.
Если а; = 6 + аы где Ь вЂ” наибольший подчеркнутый элемент, меньший, чем ао то аь = а; — Ьз < 61+х — Ьх, поэтому 2'*(2~' — 1) = 2сч — 2" в цепочке подчеркнут и предшествует 2'* — 1. Поскольку 2сч — 1 равно (2"' — 2") +(2'" — 1), где оба этн значения содержатся в цепочке, имеем адаптивную цепочку со свойством 1е. $ Цепочка, соответствующая (51) и построенная в доказательстве теоремы О, такова: 1,2,3,б.Ы,И,К,31,69,)20,24Я,~Я,ЬЩ„1020,1023,ЮЯО, 4Я80, 4095, $16Я, 1Я20,ДД)4О,Я2К, ЦЯОО,25112Я,262145. Графическое представление.
Аддитнвная цепочка (1) естественным образом соответствует ориентированному графу, вершины которого помечены как а; для 0 < х < си в котором мы рисуем дуги ото ко, иота» к а; в качестве представления каждого шага а; = ах +ах из (2) .. Например, адаптивная цепочка 1, 2, 3, 6, 12, 15, 27, 39, 78, 79, которая может быть получена нз рис. 15, соответствует ориентированному ~риффу Если а; = ах + аь для более чем одной пары индексов (у, Й), выбираем определенные 7 и к для нашего построении. В целом„все вершины такого ориентированного графа, кроме первой, будут началом ровно двух дуг. Однако в действительности зто не важное свойство графа, потому что оно маскирует тот факт, что различные адаптивные цепочки, по сути, являются эквивалентными.
Если вершина имеет выходную степень 1, то она используется только в одном последующем шаге, и поэтому подобный шаг представляет собой сумму аэ+аь+а„, которая может быть вычислена либо как (ау+па) +а, либо как а, +(аь+а„,), либо как аа ч-(ау+а ). Какой именно вариант выбран, не важно, но соглашения об аддитнвных цепочках заставляют нас их различать. Можно избежать такой избыточности, удалив все вершины, выходная степень которых равна 1 и которые соединены дугами со своими предшественницей и преемницей.
Например, приведенный выше граф должен принять вид (52) Также можно удалить любую вершину, выходная степень которой равна О, за исключением., естественно, конечной вершины п, поскольку она соответствует неиспользуемому шагу в аддитивпой цепочке. Таким образом, каждая аддитивная цепочка дает приводимый ориентированный граф, который содержит одну вершину-источник, помеченную как 1, и одну вершину-сток. помеченную как и.
Каждая першина, кроме источника, имеет входную степень > 2, н каждая вершина, кроме стока, имеет ныходную степень > 2. И наоборот, любой такой ориентированный граф без ориентированных циклов соответствует минимум одной ацдитивной цепочке, поскольку можно топологпческн рассортировать вершины и записать И вЂ” 1 дополнительных шагов для каждой вершины входной степени И > О.
Длина адаптивной цепочки без учета неиспользуемых шагов может быть определена в процессе просмотра приведенного графа. Она равна (53) (число дуг) — (число вершин) + 1, поскольку удаление вершины выходной степени 1 удаляет также одну лугу. Две адлитивные цепочки эквивалентны, если они имеют один и тот же приведенный граф. Например, аддитивная цепочка 1, 2, 3, 6, 12, 15, 24, 39, 40, 79 эквивалентна цепочке, о которой шла речь в начале этого раздела, поскольку оиа также сводится к графу (52). Этот пример показывает, что незвездная цепочка может быть эквивалентна звездной цепочке.
Аддитивная цепочка эквиаалентна звездной цепочке тогда и только тогда, когда ее приведенный ориентированный граф может быть топологнческн рассортирован лишь одним-единственным образом. Важное свойство такого графического представления аддитивных цепочек указано Н. Пиппенгером (ч'. Р)ррещег); метка каждой вершины в точности равна количеству оришггированных путей от источника к данной вершине. Таким образом, задача поиска оптимальной алдитивной цепочки для и эквивалентна задаче минимизапнн величины (53) по всем ориентированным графам, имеющим одну вершину- источник и одну вершину-сток и в точности и, ориентированных путей от источника к стоку.
Такая характеристика имеет удивительное следствие в связи с симметричностью ориентированного графа. Если обратить направления всех дуг, источник и сток поменяются местами и получится другой ориентиронанный граф, соответствующий множеству алдитивных цепочек для того же значения и.
Эти аддитивные цепочки имеют такую же длину (53), как и первоначальная цепочка. Например, если развернуть все стрелки в (52) справа налево и пометить вершины в соответствии с числом путей от правой соседней вершины, получится 79 26 12 б 2 1 (54) Одной из звездных цепочек, соответствующих этому приведенному ориентированному графу, является 1, 2, 4, б, 12, 24, 26, 52, 78, 79.; ее можно назвать драаьнай по отношению к исход~юй адаптивной цепочке. В упр. 39 и 40 обсуждаются важные последствия такого графического представления и принципа д~зльностн.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
