БИТОВЫЙ ЯЗЫК ПРОГРАММИРОВАНИЯ И ОЦЕНКИ АЛГОРИТМОВ I. Введение II. Битовый язык 1. Информационное поле 2. Команда битового языка 3. Пример программы 4. Физическая интерпретация 5. Механическая интерпретация III. Модификации битового языка 1. Первый шаг 2. Второй шаг 3. Третий шаг 4. Четвертый шаг 5. Транслятор битового языка 6. Пятый шаг IV. Формирование знаний 1. Исходные данные 2. Порождение информации 3. Другие способы сокращения записи V. Стоимость и объем алгоритмов VI. Информация переменной длины VII. Подпрограммы Обозначения 1. Извлечение бита, указанного параметрически 2. Назначение бита, указанного параметрически 3. Счетчик T0 4. Счетчик T1 5. Счетчик T2 6. Перенос информации 7. Сложение VIII. Задачи 1. Сравнение двух натуральных чисел 2. Сравнение двух вещественных чисел 3. Умножение двух целых чисел 4. Поиск максимального числа 5. Упорядочение набора натуральных чисел 6. Перенос внутри информации 7. Извлечение всей информации порциями 8. Упорядочение вещественных чисел 9. Сравнение длин двух отрезков на эвклидовой плоскости 10. Диаметр конечного множества точек на плоскости 11. Изоморфизм деревьев 12. Изоморфизм графов I. ВВЕДЕНИЕ Материал этой статьи опубликован в сильно урезанном варианте в сборнике: Новые информационные технологии в исследовании дискретных структур. РАН. Екатеринбург, 1998г. Стр. 288-290. Представляя более объемистое исследование (может быть, даже слишком большое для статьи), автор осознает, что оно всего лишь малая зацепка для, возможно, обширного направления. То, что здесь изложено, - это скорее материал для размышления, которое может как подтвердить избранные установки, так и отвергнуть их, открыв тем самым более перспективные пути исследований. Здесь мы еще далее углубляемся в теорию по части языков, но зато приближаемся к практике по части оценок всевозможных алгоритмов. Битовый язык - это логический конец идеи уменьшения транслятора, может быть, даже доведение этой идеи до абсурда. Но этот абсурд тоже надо знать, чтобы затем умело выбирать золотую середину. Среди множества абстрактных вычислительных машин и соответст- вующих им языков программирования предлагаемая здесь модель отличается тем, что язык состоит всего лишь из одного типа команд, а соответству- ющая машина не имеет ни ленты, ни регистров, ни многих других атрибу- тов, с которыми обычно ассоциируется вычислительная техника. Поэтому любые алгоритмы представляются здесь в виде однотипных элементарных операций и в этом плане они удобны для сравнения и оценок. Рассматриваемая абстрактная машина имеет наглядную физическую интерпретацию и моделируется на современной технике. А битовый язык, предназначенный в первую очередь для теоретических оценок, обеспечен транслятором и, в общем, позволяет создавать реальные программы. Кроме того, не исключено, что он может стать основой для разработки развитых языков программирования, стать унифицированной формой алгоритмов, стать шагом на пути автоматизации программирования. II. БИТОВЫЙ ЯЗЫК 1. Информационное поле Информационное поле - это конечное множество, каждому элементу которого может ставиться в соответствие либо число 0, либо число 1. Элементы информационного поля называются битами. Информационное поле можно представлять как память ЭВМ, а биты - как ячейки этой памяти. Однако слова "память", "ячейка" и другие технические термины используются здесь лишь в качестве аналогий, так как они вызывают вопросы о строении памяти, об адресации, формах дос- тупа и другие вопросы, которые для битового языка значения не имеют. Информация - это любое подмножество информационного поля, т.е. множество битов, каждый из которых принимает значение либо 0, либо 1. Информацию можно ассоциировать с массивом в памяти машины. Од- нако при этом не следует предполагать какой-либо упорядоченности или какого-либо компактного расположения информации где-либо. Хотя реально информация может храниться только на каком-то носителе, но для битово- го языка этот носитель не существенен. Информационное поле удобно связывать с конкретной задачей (а точнее, с соответствующей программой, которая будет определена ниже) и представлять это поле как часть машинной памяти, необходимой для реше- ния задачи. Целесообразно также различать состояния информационного поля (т.е. набор конкретных значений всех его битов), например, нача- льное состояние и конечное состояние, имея ввиду процесс решения зада- чи. Начальное состояние можно ассоциировать с исходными данными зада- чи, а конечное - с результатами вычислений. Операции будут производи- ться обычно не над всем информационным полем, а над его частями. Для этой цели и введено понятие информации как объекта операций. Далее предполагается, что информационное поле всегда имеет оп- ределенное состояние, т.е. на любом этапе все его биты имеют конкрет- ные значения, даже если никто не позаботился о том, чтобы эти значения присвоить. Таким образом, для процесса вычислений полностью исключают- ся из рассмотрения понятия, связанные с неопределенностью или незакон- ностью данных. Вместе с тем допустимо говорить, что состояние некото- рых битов или всего поля неизвестно внешнему наблюдателю и поведение программы для него непредсказуемо. Разумеется, оператору не лишне по- заботиться о введении исходных данных и организовать программу так, чтобы она выдавала полезные результаты. Элементы информационного поля здесь обозначаются малыми латин- скими буквами (а если нужно, то вводятся более сложные обозначения). Значения битов и информаций отражаются в виде равенств, например: a=1, abcd = 0110 . В последнем случае соответствие битов и их значений ука- зано позиционно и эквивалентно четырем равенствам: a=0, b=1, c=1, d=0. Вместо слов "обозначение бита" используется также "имя бита", тогда под именем информации понимается множество имен ее битов. Поэтому для записи вида abcd = 0110 удобно говорить, что слева стоит имя информа- ции, а справа - значение информации (или просто информация). 2. Команда битового языка Командой битового языка называется всякая упорядоченная четве- рка вида: (имя информации = информация, имя информации = информация). Программой на битовом языке называется всякое конечное множе- ство команд битового языка. Пример программы: (ab=01, c=1), (b=0, def=101). Наиболее суще- ственным здесь является то, что в каждой четверке на первом и третьем местах стоят символы, отличные от 0 и 1, а на втором и четвертом - то- лько нули и единицы. Совпадение количеств символов на 1-м и 2-м местах (а также на 3-м и 4-м) служит скорее для контроля, в принципе можно было его не требовать, а лишние символы просто не принимать во внима- ние. Чтобы прояснить назначение каждой команды, можно мысленно ста- вить слово "ЕСЛИ" перед первым равенством и слово "ТО" - перед вторым. Если искать схожее понятие в других языках, то каждая четверка - это условный оператор присваивания. А теперь - точное определение, как понимается выполнение прог- раммы. Разыскиваем команду, у которой первое равенство оказалось истин- ным на начальном состоянии информационного поля. Если таких команд нет, то программа считается выполненной. Если нашлась в точности одна ко- манда с указанным свойством, то состояние информационного поля меняет- ся в соответствии со вторым равенством этой команды (т.е. будем гово- рить, что команда выполняется), и далее аналогично разыскивается кома- нда, у которой первое равенство оказалось истинным на полученном состо- янии информационного поля. Если нашлось две или более команд с указан- ным свойством, то выполняется любая из них (но только одна). И так до тех пор, пока не исчерпаются команды, у которых первое равенство исти- нно на достигнутом состоянии информационного поля. Возможны случаи, при которых информационное поле ни за какое конечное количество шагов не приходит в состояние, где бы исчерпались выполнимые команды. Тогда программа зацикливается. Вот пример такой программы: (a=0, b=1), (a=1,b=1). Независимо от состояния информацион- ного поля хотя бы одно из равенств a=0 и a=1 окажется верным, и поэто- му всегда найдется команда, которая может быть выполнена. А вот пример программы, которая, наоборот, не может зациклиться: (a=0, a=1). Если в начальном состоянии информационного поля было a=0, то команда испол- нится ровно один раз, после чего станет a=1 и дальнейшее выполнение не возможно. А если изначально было a=1, то ни одна команда (а их всего одна в программе) не выполняется. А вот программа, для которой вопрос о зацикливании зависит от начального состояния информационного поля: (a=0, a=0). Подчеркнем, что множество команд в программе не предполагает какой-либо упорядоченности, а порядок их записи не имеет никакого от- ношения к выполнению программы. Выбор очередной команды зависит только от состояния информационного поля (которое в свою очередь зависит от выполнения предыдущих команд). Но даже в этом случае выполнение прог- раммы, вообще говоря, не детерминировано, поскольку на каждом шаге в принципе может оказаться более одной выполнимой команды. Возможны даже ситуации, когда выполнение одной команды так меняет информационное по- ле, что становится невозможным выполнение ряда других команд, которые поначалу были с ней равноправными кандидатами на исполнение. Однако изложенные правила ничуть не заставляют программиста писать недетерминированные программы. Как будет видно из дальнейшего, битовый язык (без привлечения новых понятий и конструкций) позволяет задать однозначную последовательность выполнения операций, а также про- моделировать циклы, передачи управления, условные переходы, подпрограм- мы и многие другие понятия ходовых языков, хотя сам битовый язык в та- ких понятиях не нуждается. Вместе с тем недетерминированность, используемая в рациональ- ных рамках, широко открывает двери для параллельных вычислений, опять же не требуя для этого специальных понятий и не требуя отдельного рас- смотрения параллельных и последовательных алгоритмов. Так если две команды не ведут к противоречивым результатам и не нарушают условий для выполнения друг друга, то вполне допустимо считать, что они выпол- няются параллельно (одновременно), поскольку результат не зависит от порядка их выполнения. Другое дело, что конкретная техника может быть не готова к одновременным операциям. Но если она готова, то битовый язык позволяет отразить и использовать ее преимущества. Битовый язык имеет ряд эквивалентных модификаций. На этом за- кончено определение модификации, которую можно назвать основной. 3. Пример программы Рассмотрим пример сравнения двух информаций ab и cd мощности 2 с записью в результат r единицы при побитовом совпадении во всех соот- ветствующих позициях и с записью нуля в противоположном случае. Прог- рамма может выглядеть так: (acp=000, p=1), (acp=110, p=1), (acp=100, pr=10), (acp=010, pr=10), (bdq=000, q=1), (bdq=110, q=1), (bdq=100, qr=10), (bdq=010, qr=10). Для ее запуска надо задать значения исходных информаций, нап- ример: ab=10, cd=01. Кроме того, для получения правильного результата надо положить pqr=001 (независимо от сравниваемых информаций). Таким образом, начальное состояние информационного поля: abcdpqr = 1001001. Для него истинными являются первые равенства только в 3-й и 8-й коман- дах. Будут эти команды выполняться одновременно или в какой-то после- довательности, - зависит от конкретной реализации битового языка на конкретной технике, но в любом случае они должны дать: pqr=110. После этого ни одна команда уже не может вступить в действие. Конечное сос- тояние информационного поля: abcdpqr = 1001110. Для той же задачи возможны другие программы, например: (abcdp=00000, pr=11), (abcdp=10000, pr=10), (abcdp=01000, pr=10), (abcdp=11000, pr=10), (abcdp=00100, pr=10), (abcdp=10100, pr=11), (abcdp=01100, pr=10), (abcdp=11100, pr=10), (abcdp=00010, pr=10), (abcdp=10010, pr=10), (abcdp=01010, pr=11), (abcdp=11010, pr=10), (abcdp=00110, pr=10), (abcdp=10110, pr=10), (abcdp=01110, pr=10), (abcdp=11110, pr=11). Здесь меньше информационное поле, не требуется задавать начальное зна- чение для r, и при выполнении будет задействована лишь одна четверка (что можно трактовать как меньшее время выполнения), зато гораздо бо- льше объем программы (количество четверок). Как и в других языках, программа на битовом языке еще не пред- определяется результатом, который она должна выдать. Как правило, она может быть улучшена по одним показателям за счет ухудшения других и, в общем, отражает все множество алгоритмов, которыми может решаться та или иная задача. Но программы на битовом языке отличаются значительной длиной. И это не удивительно ввиду минимальности типов команд. Для ра- цонализации записи есть эффективные средства, которые будут рассмотре- ны. Пока же напомним, что битовый язык строился как экстремальный по другому признаку - минимуму правил языка, не взирая ни на какие другие свойства, которыми бы при этом пришлось пожертвовать. 4. Физическая интерпретация Для физической интерпретации каждую четверку можно представ- лять как радиоприемник и передатчик, который может принимать сигнал только на частотах, задаваемых именем первой информации, и выдавать в этом случае сигналы на частотах, заданных именем второй информации. А информационное поле - как эфир с общедоступными сигналами. Ясно, что тогда вообще отпадает надобность в таких понятиях как передача управ- ления, ветвление, параллельное выполнение. Все четверки, которые мо- гут быть задействованы одновременно, - сразу все и будут выполняться. За счет такого одновременного выполнения сможет дальше повышаться ско- рость ЭВМ, если будут исчерпаны другие источники и будут достигнуты границы, определяемые скоростью света. Поэтому объем битовой программы, являющийся абстракцией сегодня, вполне может материализоваться завтра. Пока о такой машине можно только мечтать, но природа давно уже создала ее в виде мозга человека и животных. И есть основания считать, что все лучшие природные механизмы найдут свое отражение в ЭВМ. Поэто- му когда теоретики строят асимптотические оценки алгоритмов при уходя- щих в бесконечность значениях параметров и, значит, в расчете на тех- нику будущего, тогда надо по возможности выделять общие закономерности и не экстраполировать до бесконечности то, что уже завтра будет выбро- шено на свалку. Впрочем, указанную машину будущего вполне можно промоделиро- вать на современной технике. Для выполнения программы на битовом языке вовсе не обязательно каждый раз перебирать все четверки и сравнивать первую информацию из них с состоянием информационного поля. Достаточно один раз (это может сделать транслятор) упорядочить четверки, например, в словарном порядке информаций (к этому вопросу мы еще вернемся), и поиск сведется к минимуму. 5. Механическая интерпретация Приведем еще одну - механическую - интерпретацию языка, кото- рая в некоторых случаях более наглядна. В стену вбито множество гвоздей. На каждом гвозде может висеть одна бирка (что соответствует значению 1) или ничего не висеть (что отвечает значению 0). Каждый гвоздь как-то отмечен, например, цветом (или картинкой, или номером, или просто положением), по которому его можно отличить от всех остальных. Перед стеной толпится множество работников (или, скажем, автоматов). Каждый работник снабжен четкой инструкцией о том, что он должен делать. Например: (синий, красный, голубой = 011, зеленый, красный = 10) - означает, что как только на гвозде с синим цветом не окажется бирки, а на гвоздях с красным и голубым цветами окажутся, то надо немедленно повесить бирку на гвоздь с зеленым цветом и снять бирку с гвоздя с красным цветом. Битовый язык не требует, чтобы в такой интерпретации работники как-то упорядочивали деятельность между собой и не мешали друг другу, хотя реализация языка на конкретной технике, конечно, внесет какой-то порядок. Важно лишь чтобы не было ситуации, когда для некоторого работника возникла описанная у него в инструкции ситуация, а он (как и все остальные) ничего бы не делал, хотя вполне допустима ситуация, когда дело возникло сразу для двух и более работников, но один из них своим правильным действием изменил ситуацию и остальные остались не у дел. При правильно составленной программе конкретная реализация не должна повлиять на результат вычислений, но она может и должна влиять на скорость вычислений, учитывая тип ЭВМ. Она вправе организовать работников так, чтобы у стены одновременно вешали бирки только два работника (что может соответствовать наличию двух процессоров на ЭВМ) или одновременно тысяча работников (1000 процессоров). Поясним, что процессор в данном случае не есть работник, а скорее есть вахтер, который регулирует свой ручеек проходящих мимо него работников. III. МОДИФИКАЦИИ БИТОВОГО ЯЗЫКА 1. Первый шаг Итак, предельно простой язык может содержать всего лишь один вид команд (меньше некуда). Причем не имеет никакого значения порядок выписывания команд в программе. Каждая команда имеет вид: (имя = инфо- рмация, имя = информация). Однако это далеко не предел упрощений. Ясно, что круглые ско- бки здесь не по существу, и достаточно обходиться командами вида: имя = информация. Но тогда надо оговориться, что команды идут парами, а уже пары могут быть разбросаны как угодно. Рассмотренный пример сра- внения двух информаций примет вид: acp=000, p=1, acp=110, p=1, acp=100, pr=10, acp=010, pr=10, bdq=000, q=1, bdq=110, q=1, bdq=100, qr=10, bdq=010, qr=10. 2. Второй шаг Следующим шагом мы избавимся от понятий: имя бита и имя инфор- мации. Каждому биту информационного поля будет присвоен номер, и вмес- то имени бит будет опознаваться по его позиционной записи. В данном примере присвоим номера: a - 1, b - 2, c - 3, d - 4, p - 5, q - 6, r - 7. И вместо записи p=1, означающей что биту с именем p присваивается значение 1, будем писать 2222122 , где "2" означает, что бит с соответ- ствующим позиции номером не изменяется, а биту в пятой позиции присва- ивается единица. Проверяемое отношение acp=000 аналогично примет вид 0202022 , где "2" означает, что бит с соответствующим номером прове- рять не надо. Программа станет следующей: 0202022 , 2222122 , 1212022 , 2222122 , 1202022 , 2222120 , 0212022 , 2222120 , 2020202 , 2222212 , 2121202 , 2222212 , 2120202 , 2222210 , 2021202 , 2222210 . Порядок строк в такой записи не имеет значения, но внутри строки пере- становки изменили бы алгоритм. Впрочем, запись в виде строк тоже зна- чения не имеет. Главное, что символы (не считая разделителей) распре- делены по группам (в данном случае по 14 штук в группе), и их порядок в каждой группе менять нельзя. 3. Третий шаг Отсюда легко проглядывается следующий шаг упрощений: ставить разделитель только после каждой группы: 02020222222122, 12120222222122, 12020222222120, 02120222222120, 20202022222212, 21212022222212, 21202022222210, 20212022222210. 4. Четвертый шаг Теперь можно избавиться от понятия разделитель, введя, правда, четвертый символ наравне с 0, 1 и 2 . Обозначим его: 3. Получим: 020202222221223 121202222221223 120202222221203 021202222221203 202020222222123 212120222222123 212020222222103 202120222222103 Для удобства проверки здесь группы разделены пробелами (которые транс- лятору не нужны). Конечно, вместо разделителей можно было бы просто указать изначально, что символы надо читать по 14 штук, т.е. ввести в понятие текста программы особое место, куда будет помещаться информа- ция о длине групп и, возможно, об их количестве. Это сократило бы ис- ходный текст программы, но напомним, что такая цель (как и сокращение загрузочного модуля) сейчас не ставится. А сейчас цель: сократить ко- личество правил. 5. Транслятор битового языка В последней модификации битовый язык реализован автором на IBM -ской технике. Вот загрузочный модуль (объемом всего лишь 103 байта !), который обрабатывает исходный текст произвольной программы, сразу запу- скает программу на выполнение и выдает файл с итоговым состоянием ин- формационного поля: 186,93,0,139,250, 198,69,7,46,184, 0,61,205,33,137, 195,114,253,198,5, 64,180,60,43,201, 205,33,104,0,140, 7,6,31,73,180, 63,153,205,33,149, 176,51,43,255,242, 174,139,215,139,202, 209,233,139,218,139, 243,3,218,59,221, 127,32,43,255,172, 60,50,116,4,58, 5,117,237,71,59, 249,117,242,43,255, 172,60,50,116,2, 136,5,71,59,249, 117,244,235,214,180, 64,153,187,6,0, 205,33,195. Можете посмотреть коды в шестнадцатиричной системе. Р.Н.Шакиров предложил еще более компактный вариант объемом 68 байтов, шире использующий возможности командной строки. Конечно, эта версия не рассчитана на прямой выход к принтеру, графике и т.п. Соответствующие добавки может сделать транслятор или операционная система, если часть информационного поля отвести под бу- феры для внешних устройств и ввести там же, например, бит, возвещающий о готовности данных для принтера. Для первой модификации, а также для обслуживания других конст- рукций, рассматриваемых ниже, транслятор будет, конечно, больше. Но все же это будут килобайты (может быть, даже один), а не мегабайты. Причем речь идет об очень сложном процессоре с огромным количеством команд. Поэтому можно надеяться, что столь же микроскопичны будут тра- нсляторы для существенно отличных классов ЭВМ. Таким образом, битовый язык - это та точка, к которой достаточно свести другие языки и от ко- торой уже открыты пути к любым процессорам. Перевод с других языков на битовый не столь прост, поскольку на это они не рассчитывались. Но все же создание такого переводчика (преобразующего любой исходный текст, например, на СИ в текст на бито- вом языке) - это разовая и вполне реальная операция. Средства для это- го обсуждаются позже. 6. Пятый шаг Очевиден и следующий шаг: мы можем избавиться от символов 2 и 3. Для представления четырех различных символов достаточно комбинаций из значений двух битов: 0 - 00, 1 - 10, 2 - 01, 3 - 11. Тогда (для очередной модификации языка) исходный текст того же примера: 000100010001010101010110010111 и т.д. (приведена только одна группа). Это и есть наиболее абстрактная модификация битового языка. Здесь текст программы доведен в точности до понятия информации. (Разумеется, на любом другом языке текст тоже записывается в виде нулей и единиц. Для этого достаточно в нем заменить каждый символ на его 8-битовое представление. Однако у нас есть существенное отличие: за каждой парой битов отчетлива видна конкретная операция, т.е. форма исходного текста максимально приближена к выполняемым по нему операциям, и правила де- шифровки текста являются минимальными.) IV. ФОРМИРОВАНИЕ ЗНАНИЙ 1. Исходные данные Теперь - об исходных данных программы. Если мы хотим придать единство и законченность для каждой конкретной задачи с известными ис- ходными данными, то в исходном тексте все же надо выделить первую гру- ппу, в которой будет стоять начальное состояние информационного поля. Для этого, конечно, придется скорректировать правила работы транслято- ра. С другой стороны, это позволяет освободиться от понятий компонов- щика, загрузочного модуля и вообще выполнения программы; это приводит к понятию порождения одной информацией другой информации (вообще без- относительно к вычислительной технике) и, главное, наполняет это поня- тие реальным смыслом. А это позволяет разобраться в некоторых процес- сах формирования знаний. 2. Порождение информации Конечно, при работе с другими языками и даже при работе на счетах с костяшками тоже происходит порождение информации. Но правила языков и устройство ЭВМ практически необъятны, и отдавать все родите- льские права только небольшому исходному тексту было по крайней мере сомнительно. Правила работы со счетами просты, но много ли от них по- льзы? Пример со счетами тоже скорее говорит о решающей роли правил: есть громоздкие правила - есть и результат, просты правила - скромен и результат. Битовый язык программирования разрывает эту закономерность. При четко определенном раз и навсегда минимуме правил он позволяет описать любые алгоритмы, любые процессы, которые есть в природе или мыслятся теоретически. То, что любые сведения, любые закономерности можно выразить через набор нулей и единиц, - известно давно. Но как это сделать? Вот словами или формулами - это уже проверено, хоть и оставляет массу раз- ночтений и толкований. Правила формальных логик однозначны, но сами по себе они не объясняют, как надо подводить под них реальные задачи и понятия из других областей, и выбор подходящей модели далеко не одно- значен. Использование нулей и единиц в лучшем случае ограничивается переводом на них тех же слов или формул и всякий раз со своей дешифро- вкой от языка к языку, от одного типа ЭВМ к другому. Нули и единицы здесь только инструмент, временная запись тех же формул, а вовсе не базовая информация, из которой извлекались бы формулы. Конечно, до та- кой базовой информации еще далеко, и было бы преждевременно переделы- вать компактные и наглядные формулы в длинные программы на битовом языке. Но предложенная здесь унификация служит основой для совершенст- вования методов работы с информацией, для усложнения тех же правил, но усложнения целенаправленного и стандартизованного. Необходимо подчеркнуть, что усложнения не должны сводиться к добавлению новых конструкций, например, регистров, отдельных операций сложения или умножения, так как при этом в лучшем случае получится не- что вроде ассемблера или Си, где исходные битовые понятия затеряются и станут просто лишними. Усложнения должны состоять только в эквивалент- ном изменении формы, в модификациях, которые легко и, главное, одноз- начно переводятся в рассмотренные модификации битового языка. Одна, уже упоминавшаяся, форма состоит в упорядочении групп, из которых состоит программа. Это легко сделать для модификации, где используются только символы 0,1,2,3, а также для наиболее абстрактной модификации, где участвуют только 0 и 1. Это сводит к минимуму поиск очередной группы и, если шире, ставит битовый язык на реальные рельсы, приближая время выполнения программ на нем к времени для других язы- ков. Другое направление должно касаться сокращения записи программ. Собственно, первая рассмотренная модификация является таким шагом по отношению к последней, абстрактной модификации. Более радикальное сре- ство - перенумеровать все группы и по каждой позиции в группе задавать одной формулой значения бита сразу для всех групп. Кстати, составление таких формул из определенного круга можно поручить самой ЭВМ. Позже будут рассмотрены подпрограммы - общее и эффективное средство сокращения записи. А сейчас покажем, какие в принципе еще могут быть подходы. 3. Другие способы сокращения записи Рассмотрим тот же пример сравнения пар битов и второй постро- енный для него алгоритм. Введем обозначение: F(N,i,j) означает, что в позиции с i-ой по j-ую помещается двоичное представление натурально- го числа N, причем старшие недостающие разряды дополняются нулями. Тогда в принципе допустима такая запись: N=16, F(N,1,5), F(1,11,11), (12)=1000010000100001 Здесь первое равенство указывает максимальное значение параметра N (и одновременно количество групп). Далее указываются значения первых пяти членов групп (одновременно первых пяти битов информационного поля). Значения 12-го бита группы (и 6-го бита информационного поля), которые трудно выразить одной формулой, выписаны в позиционном соответствии шестнадцати группам, из которых состоит развернутая программа. Важно подчеркнуть, что при этом не вводятся новые команды язы- ка, а речь идет лишь о компактной записи старых команд. Эту запись всегда можно развернуть без всяких кривотолков. А также можно написать любой алгоритм без использования сокращенных записей. В этом состоит принципиальное отличие от развитых языков (Си, Фортрана), где каждый оператор сам по себе элементарен и только в редких случаях может быть выражен через другие, причем весьма нерациональным способом. Удаление ключевых команд из Си просто сделало бы язык неработоспособным. Вместе с тем, введение сокращенных записей является мощным средством для рационализации выполнения программы. В том же примере по состоянию первых четырех битов информационного поля без всяких пре- образований определяется номер группы, которая будет задействована. Согласно определению F этот номер просто записан в информационном поле на его первых четырех битах. По этому номеру производится прямой выход на нужную позицию набора 1000010000100001, в которой находится резуль- тат. Сокращение записи также открывает возможность работы с боль- шими массивами. И в общем, выводит битовый язык на уровень любых дру- гих языков, поскольку приемы сокращения бесконечны по своему разнооб- разию. Однако при этом всегда есть четкая форма, к которой могут быть приведены и с которой могут быть сверены программы. Кроме того, эта основа указывает реальный путь, по которому написание сложных программ на развитых языках можно поручить самой ЭВМ. Разумеется, это должны быть новые языки, построенные по принципу сокра- щений команд битового языка, а не на безудержном добавлении новых ко- манд, чем славятся современные процессоры и языки программирования. V. СТОИМОСТЬ И ОБЪЕМ АЛГОРИТМОВ Далее будем пользоваться понятиями, данными в определении би- тового языка. Алгоритм будем отождествлять с программой на битовом языке. Таким образом, алгоритм - это конечное множество команд вида (имя ин- формации = информация, имя информации = информация). Объемом алгоритма называется его общее количество команд. Ценой команды называется сумма мощностей двух ее информаций. В зависимости от начального состояния информационного поля ка- ждая команда, в которой первое равенство оказалось истинным, может посредством второго равенства задать новое состояние информационного поля. Всякая цепочка задействованных таким образом команд имеет цену, равную сумме цен этих команд. Стоимостью (ценой) алгоритма называется всякое число, которое не меньше любой такой суммы цен при всевозможных допустимых начальных состояниях информационного поля. Определение цены команды отражает тот реальный факт, что для работы с информацией ее сначала надо, как минимум, считать (опознать, сравнить), т.е. произвести определенные затраты, а по окончании опера- ции - куда-то записать. Если алгоритм не имеет задействованных четверок (при любом сос- тоянии информационного поля), то его цена равна нулю (но в качестве таковой подходит и 1, и 2). Алгоритм может вообще не иметь цены и "за- цикливаться". О таких случаях также должен позаботиться его автор. Цена алгоритма не однозначна и аналогична понятию верхняя гра- ница множества. По аналогии с понятием точной границы нетрудно ввести точную цену алгоритма, однако на практике ее удается найти только в немногих случаях, поэтому польза от введения этого понятия невелика. Объем алгоритма не есть объем исходного текста программы, ко- торую можно затем написать на том или ином языке, и даже не объем за- грузочного модуля, который сильно зависит еще и от конкретных машинных команд. Поэтому не должны вызывать удивление получаемые ниже большие объемы алгоритмов, поскольку они обусловлены здесь отсутствием разно- образия в командах. Развитые языки исправят этот недостаток. Так, пе- ресылка значительного количества информации может выглядеть на некото- рых языках очень кратко: A=B. Пересылка большого массива может уклады- ваться и в одну машинную команду. Но все это не отменяет значительного количества операций, реально стоящего за этими командами. Как правило, реальная задача имеет множество алгоритмов реше- ния, но среди них не удается выбрать лучший на все времена, потому что самый быстрый (табличный) алгоритм требует программу (память) непомер- ного объема, а самый компактный долго работает. Так что бессодержате- на постановка, в которой, не взирая на объем, требуется найти наиболее быстрый (наименьший по стоимости) алгоритм, поскольку формально такой (и как правило даже линейный) всегда существует, только пользы от него мало. Для корректности постановки можно добавить, например, ограниче- ние на объем алгоритма. А вообще в теоретическом и практическом плане наиболее содержательным и полезным является решение в виде серии алго- ритмов, каждый из которых в определенных обстоятельствах имеет преи- мущество перед остальными по названным или каким-либо другим показате- лям. Заметим, что предложенное понятие алгоритма не привязано к та- ким особенностям как передача управления, ветвление, циклы и уж тем более к работе с магнитной или бумажной лентой. Все это преходящие де- тали, которые мешают видеть главное. Вычислительная техника, как правило, предоставляет льготы то- лько очень ограниченному кругу операций, укладывающихся в 16-, 32- или 64-разряда. Как только информация выходит за эти пределы, алгоритмы приходится строить из меньших блоков или даже сводить их к битовым операциям по схемам, аналогичным тем, что здесь приводятся. Кроме того, как бы рационально ни были организованы на ЭВМ некоторые операции, они все равно обязаны прочитать и сформировать нужные биты, затратить на это энергию. Поэтому законы битовых операций неизбежно проявляют себя. И есть основания считать, что особенности вычислительной техники не могут существенно изменить (по крайней мере, в сторону улучшения) по- рядки алгоритмов, рассчитанные на битовом уровне. Во всяком случае на каждом из рассмотренных далее уровней есть возможность внести коррек- тивы в соответствии с устройством ЭВМ. Таким образом, предложенный подход дает основу для объективных оценок алгоритмов и позволяет отказаться от распространившихся в науке фантастичных предположений о вычислительной технике, которые неизбежно ведут к противоречию с практикой. Рассмотрим простейшие алгоритмы. При минимальных исправлениях они могут служить частями более сложных алгоритмов. Ниже символы a,b используются для входной информации, k=0 - счетчик, z - выходная инфо- рмация. Инверсия бита: (ak=00, ak=11), (ak=10, ak=01). Цена: 4, объем: 2. Логическое "ИЛИ" для двух битов: (abk=000, zk=01), (abk=100, zk=11), (abk=010, zk=11), (abk=110, zk=11). Цена: 5, объем: 4. А вот вариант с ценой 10, но меньшего объема: (abk=000, zk=01), (ak=10, zk=11), (bk=10, zk=11). Логическое "И" для двух битов: (abk=000, zk=01), (abk=100, zk= =01), (abk=010, zk=01), (abk=110, zk=11). Цена: 5, объем: 4. Сложение двух битов по модулю 2: (abk=000, zk=01), (abk=100, zk=11), (abk=010, zk=11), (abk=110, zk=01). Цена: 5, объем: 4. Сложение двух битов по модулю 2 с формированием бита переноса: (abk=000, zpk=001), (abk=100, zpk=101), (abk=010, zpk=101), (abk=110, zpk=011). Цена: 6, объем: 4. Сложение трех битов по модулю 2 с формированием бита переноса имеет цену 7. Сравнение двух битов: (abk=000, zk=11), (abk=100, zk=01), (abk=010, zk=01), (abk=110, zk=11). Цена: 5, объем: 4. Перенос бита: (ak=00, zk=01), (ak=10, zk=11). Цена 4, объем 2. В следующих алгоритмах натуральное число N задает мощность ин- формации, но само информацией не является и в операциях не участвует. Фактически за каждой из следующих операций стоит бесконечное количест- во алгоритмов (для каждого конкретного значения N), однако было бы не- удобно вводить для них бесконечное количество названий. Перенос информации. Для N=3, входной информации abc, счетчика kmn=000 и выходной def алгоритм можно записать так: (ak=00, dk=01), (ak=10, dk=11), (bm=00, em=01), (bm=10, em=11), (cn=00, fn=01), (cn=10, fn=11); его цена: 12. Для произвольного N цена: 4N объем: 2N. Сравнение двух информаций мощности N с записью в результат ед- иницы при побитовом совпадении во всех соответствующих позициях и с записью нуля в противоположном случае - стоит 5N и имеет объем 4N. Вот алгоритм при N=2 для входных ab, cd, pq=00, r=1 и выходном r: (acp=000, p=1), (acp=110, p=1), (acp=100, pr=10), (acp=010, pr=10), (bdq=000, q=1), (bdq=110, q=1), (bdq=100, qr=10), (bdq=010, qr=10). Сложение по правилам арифметики двух информаций мощности N. Т.е. складываются два числа в двоичной записи (недостающие разряды считаются нулями). Пусть N=3, abc и def - исходные слагаемые (младшие биты слева), klm=100, результат засылается в abc, для бита переноса используется p. Тогда алгоритм: (adk=001, apkl=0001), (adk=101, apkl=1001), (adk=011, apkl=1001), (adk=111, apkl=0101), (bepl=0001, bplm=0001), (bepl=1001, bplm=1001), (bepl=0101, bplm=1001), (bepl=1101, bplm=0101), (bepl=0011, bplm=1001), (bepl=1011, bplm=0101), (bepl=0111, bplm=0101), (bepl=1111, bplm=1101), (cfpm=0001, cm=00), (cfpm=1001, cm=10), (cfpm=0101, cm=10), (cfpm=1101, cm=00), (cfpm=0011, cm=10), (cfpm=1011, cm=00), (cfpm=0111, cm=00), (cfpm=1111, cm=10). Для произвольного N цена: 8N-3, объем: 8N-4. VI. ИНФОРМАЦИЯ ПЕРЕМЕННОЙ ДЛИНЫ На практике неудобно запасаться отдельными алгоритмами сложе- ния двухразрядных чисел, затем трехразрядных и т.д. Интерес представл- яет устройство, которые принимает информацию разной длины, например до 8 (или 16, 32, 64) битов. Обычно недостающие биты попросту дополняются нулями. Однако уже при переносе информации актуальна задача, когда ко- личество информации заранее неизвестно (не предопределено алгоритмом) и само является входной информацией. В этом случае в процессе расчета необходимо постоянно производить сверку с исходными параметрами для своевременного завершения операции. Чтобы не вводить утопические операции с актуально бесконечными количествами информации, предлагается следующая постановка, достаточ- ная для охвата любых реальных задач. Имеется одна или несколько вход- ных информации, задающих значения входных параметров N, M, ... , имеются входные информации длиной N, M, ... соответственно и, возможно, входные информации фиксированной длины, имеется аналогичная серия вход- ных параметров и соответствующих им выходных информаций переменной дли- ны; кроме того, заданы верхние границы для всех входных параметров: N0, M0, ... соответственно, которые входной информацией не являются (но с которыми алгоритм должен быть жестко связан). Требуется построить ал- горитм (при конкретных условиях задачи) и оценить его по стоимости и объему в зависимости от значений входных параметров и ограничений на них. Далее мы ограничимся одним входным параметром N и одним N0, что не меняет сути дела. Таким образом, оценка даже в простейшем случае зависит от двух аргументов: N и N0. Как это интерпретировать и нельзя ли все-таки сде- лать обобщенную функцию от одного аргумента? Перебирая все N от 1 до N0, всегда можно найти наихудшее значение стоимости. Обычно оно полу- чается при N=N0. Это и можно считать обобщенным показателем. Т.е. си- туация такова, как будто для алгоритма, работающего для фиксированного N, мы дополнительно потребовали работоспособность при всех меньших значениях входного параметра, причем без увеличения стоимости. И это вполне законное требование для всякой практической задачи, которая всегда должна быть рассчитана на достаточно широкий круг обрабатывае- мых данных. Поэтому именно оценку при N=N0 мы далее будем выбирать в качестве наиболее показатеьной и просто писать функцию от N. Вспоминая же исходный смысл N0, можно сказать, что такая обоб- щенная оценка отражает скорость вычислений в зависимости от роста ре- сурсов ЭВМ, позволяющих пропускать тот же алгоритм для все больших и больших значений входного параметра. При этом не предполагается каче- ственное изменение строения ЭВМ, которое просто ускорило бы сложение, пересылку данных и другие элементарные операции. Если же техника меня- ется и происходит ускорение элементарных операций, то нетрудно ввести соответсвующий коэффициент и заранее предсказать, как будут вести себя алгоритмы на новой технике. Поэтому именно обобщенный показатель явля- ется тем, для которого вполне обоснованы асимптотические оценки при значениях аргумента, уходящих в бесконечность. (Это, конечно, не отме- няет важности оценок для пары N,N0, но тогда надо помнить, что в этой ситуации нельзя устремлять N в бесконечность.) Параметр N может поступить в алгоритм в разных формах, от это- го будут зависеть оценки алгоритма да и сам алгоритм. Мы рассмотрим и сравним только две формы, из чего в общем будет ясно направление выбо- ра. Первая форма заключается в написании N нулей и единицы на конце. Вторая содержит L=log2(N0) битов (с округлением до большего целого) и представляет двоичную запись числа N. Рассмотрим алгоритмы переноса информации для первой формы. (Сам алгоритм переноса вряд ли представляет практическое значение, по- скольку ввиду важности и относительной простоты технически операция переноса может быть организована специальным образом и выпадать таким образом из общих правил. Но на этом примере видны проблемы, которые возникают при работе с информацией переменной длины даже в такой ходо- вой операции как сложение.) Исходную информацию назовем abcdef... , выходную - ABCDEF... , входной параметр N - klmn... , а также положим pqrstu...=000... Тогда первый алгоритм: (akp=010, Ap=01), (akp=110, Ap=11), (aklp=0010, Ap=01), (aklp=1010, Ap=11), (bklq=0010, Bq=01), (bklq=1010, Bq=11), (aklmp=00010, Ap=01), ... Цена: N*(N+4) , объем: N0*(N0+1). Второй алгоритм: (akp=010, Ap=01), (akp=110, Ap=11), (abklp=00010, ABp=001), (abklp=10010, ABp=101), (abklp=01010, ABp=011), (abklp=11010, ABp=111), (abcklmp=0000010, ABCp=0001), ... Здесь цена: 3N+2 , объем: 2**(N0+1)-2. Полученный здесь порядок цены является наилучшим из тех, о ко- торых можно даже мечтать. Однако на самом деле выгода от такого алго- ритма иллюзорна. И дело даже не в том, что объем алгоритма растет экс- поненциально. А в том, что форма представления числа (а числа - это самый ходовой объект алгоритмов) здесь сверхизбыточна. Число миллиард в такой форме представляется миллиардом нулей в то время, как вполне достаточно было бы 32 разрядов. Нет никакой выгоды от переноса милли- арда символов линейным алгоритмом, поскольку можно воспользоваться са- мым глупым алгоритмом и переносить только 32 символа. Столь же невыго- дно было складывать и умножать числа в таком громоздком представлении. А если и найдется область для их применения, то она может быть только очень узкой и только перевод чисел из одной формы в другую может съесть всю выгоду. Поэтому чтобы не отвлекаться на теоретические ситуации, имею- щие мало общего с практикой, мы должны принять, что числа в алгоритмах всегда фигурируют в позиционной двоичной записи. Т.е. во второй форме. Рассмотрим алгоритмы переноса информации для второй формы за- писи параметра N. Третий алгоритм (аналог второго): (apklmn...=00100..., Ap=01), (apklmn...=10100, Ap=11), (abpklmn...=0000100..., ABp=001), (abpklmn...=1000100..., ABp=101),... Цена: 2N+log2(N0)+3, объем: 2**(N0+1)-2. Формально нет причин, чтобы отвергнуть этот алгоритм. Как нет причин не считать решением задачи просто список ответов для всевозмож- ных начальных данных. Однако, как уже отмечалось, если исходить из та- бличных алгоритмов, то никаких практичных оценок мы не получим, а по- лучим только теоретические линейные оценки, от которых никакой пользы. Конечно, было бы опрометчиво выкинуть табличную идею вообше, поскольку именно таблично задаются логические операции над парой битов и многое тому подобное. Поэтому важно знать величину этой таблицы и видеть, на- сколько необходимым или даже единственным средством она является. Поэ- тому (имея ввиду четвертый алгоритм, где объем растет линейно), мы все же предпочли бы отказаться от третьего алгоритма. (Не умаляя его роли для конкретных задач, процессоров и ограниченных ситуаций.) Кроме того, если рассчитывать, что вычисленный объем станет реальностью для техники будущего (для которой собственно и имеют смысл асимптотические оценки), то третий алгоритм ведет к явному несоответс- твию между огромным объемом памяти и совершенно незначительными объе- мами информации, которыми можно оперировать. Рассмотрим четвертый алгоритм. В дополнение к прежним данным здесь понадобятся: входное значение z=0, отражающее запуск сравнения счетчика pqrstu... с klmn... ; x=0 - для отражения результата сра- внения и рабочая информация ФХЦЧШ... для учета битов, прошедших срав- нение. Заметим, что сравнение счетчика с N есть сравнение информаций фиксированной длины L. (zФХЦЧ... =11111..., z=0), (kpzФ=0010, Ф=1), (kpzФ=1110, Ф=1), (kpzФ=1010, xФ=01), (kpzФ=0110, xФ=01), (lqzХ=0010, Х=1), (lqzХ=1110, Х=1), (lqzХ=1010, xХ=01), (lqzХ=0110, xХ=01), (lrzЧ=0010, Ч=1), ... (azpqrst...=00000..., AxzpФЧЦЧ...=01110000...), (azpqrst...=10000..., AxzpФХЦЧ...=11110000...), (bzpqrst...=00100..., BxzpqФХЦЧ...=011010000...), (bzpqrst...=10100..., BxzpqФХЦЧ...=111010000...), (czpqrst...=00010..., CxzpqФХЦЧ...=011110000...), ... Здесь цена: N*(2+L+3+L+L)+N*(7L+4)-2 или 10*N*log2(N0)+19*N, а если оценивать по наихудшей ситуации N=N0, то 10*N0*log2(N0)+19*N0. Объем: 2*N0+4L+1 или 2*N0+4*log2(N0)+5. Возможен также перенос информации порциями фиксированной длины, что позволяет несколько улучшить коэффициенты в цене за счет незначи- тельного увеличения объема алгоритма. Аналогичные варианты алгоритмов с близкими оценками существуют для сложения, вычитания, логических операций и др. Их и предлагается взять за основу для дальнейших построений. Т.е. при базовой оценке стоимости: N0*ln(N0). Оценим отдельно поиск информации, указанной параметрически, поскольку здесь особый случай. Пусть задана информация abcde... длиной N и число K в двоичной форме: pqrst... На выходе должен быть z - K-й бит исходной информации. Предполагается, что K от 1 до N, а N не пре- восходит границы N0. На входе должен быть y=0. Тогда (aypqrst...=0000000..., yz=10), (aypqrst...=1000000..., yz=11), (bypqrst...=0100000..., yz=10), (bypqrst...=1010000..., yz=11),... Цена: log2(N0)+5, объем: 2*N0. Как отмечалось современная вычислительная техника не позволяет в чистом виде реализовать свободный доступ к информационному полю од- новременно для всех четверок, из которых составлен алгоритм. Для про- ведения очередного действия придется перебирать эти четверки. Насколь- ко больше от этого понадобится вычислений? Это количество пропорциона- льно объему алгоритма (или даже меньше того, если четверки удается упорядочить). Поэтому если, как предложено, взять за основу стоимость N0*ln(N0), то объем для алгоритмов переноса, сложения и т.п. линейно зависит от N0, т.е. не влияет на порядок стоимости. Исключение составляет поиск бита, указанного параметрически. Но здесь как раз возможно упорядочение, которое позволяет вписаться в нужные рамки. Кроме того, для моделирования можно просто воспользова- ться особенностями современной техники, которые обеспечат скорость в соответствии с указанной выше ценой этой операции. Главное, что сде- лать это надо только один раз (как, впрочем, для сложения и т.п.), а затем уже можно сколько угодно раз обращаться к этой операции. Таким образом, предложенные выше построения не есть чисто тео- ретические, они принципиально проверяемы вплоть до самых мелочей, при- чем на реальной современной технике. VII. ПОДПРОГРАММЫ В этом разделе рассматриваются простейшие алгоритмы в плане их практического оформления при программировании на битовом языке. Ес- ли рассматриваемые в следующем разделе задачи интересуют вас только с целью асимптотических оценок, то этот раздел можно пропустить. Вместе с тем подпрограммы дают основу для более точных оценок алгоритмов. Разные программы часто имеют схожие фрагменты, которые желате- тельно выписать отдельно, чтобы затем можно было достаточно формально вписывать их в разные программы. Для этой цели и можно ввести понятие подпрограммы как подмножества программы. Таким образом, в отличие от других языков подпрограмма для би- тового языка не есть команда этого языка, а есть всего лишь способ со- кращения записи исходного текста программы. Подпрограмма - это подмно- жество команд (т.е. четверок, если пользоваться основной модификацией языка), объединенных исключительно по внешнему признаку (по смыслу или вообще по желанию автора). Команды подпрограммы могут быть как угодно разбросаны по тексту программы и, вообще говоря, не имеют прямого от- ношения к ее выполнению. Разумеется, программисту не запрещается опре- делять подпрограмму, исходя из логики выполнения программы, и выписы- вать команды подпрограммы компактно, рядом друг с другом. И, что еще важнее, не запрещается ввести обозначения для наи- более ходовых подпрограмм, чтобы для краткости сначала писать програм- му с использованием этих обозначений, а затем лишь раз при надобности перевести ее в развернутый вид. Далее используется постановка, данная в предыдущем разделе, т. е. для каждого параметра N, задаваемого исходной информацией, существу- ет ограничение N0, которое входной информацией для программы не являе- тся. В отношении в подпрограммам (да и к программе) это означает сле- дующее. N0 - это указание транслятору, это число, от которого зависит текст (и объем) подпрограммы, но уже не зависит ее выполнение. От N, наоборот, не зависит объем подпрограммы (она должна обслуживать все значения N от 0 до N0), но зависит ход и результат расчета. Поясним так же один из приемов программирования на битовом языке, касающийся последовательности выполнения команд. Как подчерки- валось, порядок выписывания команд не имеет никакого отношения к поря- ку их выполнения. А как быть, если для некоторой задачи изначально за- дана последовательность действий? В этом случае нужно ввести вспомога- тельную информацию достаточной длины (чтобы вариантов различных ее значений было больше, чем последовательных шагов в решении задачи), приписать каждому шагу какое-нибудь состояние вспомогательной информа- ции, и в каждой четверке, соответствующей очередному шагу, в первом равенстве добавить проверку на это состояние, а во втором - установле- ние очередного состояния. Пусть, например, на первом шаге надо присво- ить a=5, на втором - инвертировать бит b, на третьем - c=7. Тогда вводим вспомогательную информацию pq=00, и программа может быть такой: (pq=00, apq=510), (bpq=010, bpq=101), (bpq=110, bpq=001), (pq=01, cpq=711). Здесь первому шагу отвечает значение pq=0, второму - pq=10, третьему - pq=01. Кроме того, на последнем шаге присвоено значение pq=11, отличное от всех предыдущих, чтобы ни в одной из команд первое равенство не могло стать истинным и чтобы программа вовремя останови- лась (не зациклилась). Удаляя излишества, программу можно упростить: (pq=00, ap=51), (bpq=010, bpq=101), (bpq=110, bpq=001), (pq=01, cq=71). ОБОЗНАЧЕНИЯ Далее малые буквы, как и ранее, будут использоваться для имен битов и имен информаций, а большие - для более широких целей, в частно- сти, для краткой записи тех же имен информаций. Числа представляются двоичной записью, младшие разряды - слева, старшие - справа. Для краткой записи сразу нескольких команд будем использовать обычные обозначения для определения множеств, но с некоторой формали- зацией, чтобы исключить разночтения. Будет применяться конструкция ви- да { (имя информации = выражение от текущей переменной, имя информации = выражение от текущей переменной) : имя текущей переменной = началь- ное значение, второе значение, многоточие, конечное значение }. Если второе значение пропущено, то подразумевается шаг 1. Например, запись {(abcd = J, def = J+2) : J=0,...,3} означает 4 команды: (abcd = 0000, def = 010), (abcd = 1000, def = 110), (abcd = 0100, def = 001), (abcd = 1100, def = 101). Иногда вместо "выражения от текущей переменной" будет стоять несколько выражений через запятую, а имя информации разбито на столько же частей запятыми. Это означает, что частям информации (определяемым частями ее имени) сопоставляются значения, вычисленные по соответству- ющим выражениям. Например, запись {(abc,d=J,1; de,f=J+2,1) : J=0,...1} означает: (abcd=0001, def=011), (abcd=1001, def=1111). В таких случаях для разделения первого и второго равенств вместо запятой будет исполь- зоваться ";". Поскольку количество символов на реальной технике ограничено и, кроме того, для длинных информаций неудобно вводить имя для каждого бита, то введем обозначение: имя бита(число в двоичной записи), кото- рое будет означать следующее. С каждым битом, получившим свое персона- льное имя по прежним правилам, связывается информация, в которой этот бит стоит на первой позиции. Чтобы не вводить массу имен для остальных битов данной информации, они будут идентифицироваться по имени первого бита и номерам соответствующих позиций. Нумерацию предлагается вести от нуля (а не от единицы). Так запись b(0) означает сам b, далее b(1) - соседний с ним бит (на второй позиции) и т.д. 1. Извлечение бита, указанного параметрически Пусть первый бит исходной информации имеет имя b, а остальные различаются по номерам как указано выше. Ее длина не превосходит N0. Номер извлекаемого бита задан информацией pqrst, т.е. ее длина фикси- рована. Извлеченный бит должен на выходе поступить в z. Кроме того, на входе должен быть признак y=0. Пусть для определенности N0=31. Тогда подпрограмма имеет 64 команды: (b(0)ypqrst=0000000, yz=10), (b(0)ypqrst=1000000, yz=11), (b(1)ypqrst=0010000, yz=10), (b(1)ypqrst=1010000, yz=11), (b(01)ypqrst=0001000, yz=10), ... Используя сокращения, ее можно записать: {(b(J)y,pqrst=00,J ; yz=10) : J=0,...,31}, {(b(J)y,pqrst=10,J ; yz=11) : J=0,...,31}. Если информация, указывающая номер извлекаемого бита, тоже идентифицируется по имени ее начального бита, то 64 команды примут вид (b(0)yp(0)p(1)p(01)p(11)p(001)=000000, yz=10), ... А в сокращенном ви- де {(b(J)y,p(0)p(1)p(01)p(11)p(001) = 00,J ; yz=10 : J=0,...,31}, {(b(J)yp(0)p(1)p(01)p(11)p(001) = 10,J ; yz=11 : J=0,...,31}. Для это- го набора команд (независимо сокращенная запись или нет), т.е. для под- программы введем обозначение A(b,32,p,5,yz). А вообще в круглых скобках под A на первом месте может стоять любое имя бита, например, a, b, c, p, q и т.д. На втором месте должно стоять десятичное число в явном виде или фиксированная константа, нап- ример, 50 или N0. Это число задает длину информации, в которой произ- водится поиск, и указывает для транслятора количество команд в подпро- грамме (оно вдвое больше этого числа, если иметь ввиду развернутую, а не сокращенную запись). На третьем месте находится имя начального бита информации, указывающей номер извлекаемого бита. На четвертом - число или константа, задающая длину информации, поименованной на третьем ме- сте. От этого числа не зависит количество команд, но зависит запись каждой команды. На пятом месте должна быть пара имен битов; во второй поступит результат, а первый на входе должен быть нулевым. Формально не требуется какой-либо согласованности между числа- ми на 2-м и 4-м местах. Однако неудачные сочетания ведут к нерациона- льным подпрограммам. Целесообразно отношение N4=[log2(N2)], где N2 и N4 - упомянутые числа, а квадратные скобки означают округление до бо- льшего целого. В этих обозначениях объем подпрограммы: 2*N2, а цена: N4+4. В зависимости от типа ЭВМ, в зависимости от конкретного транс- лятора введенная запись подпрограммы может разворачиваться в команды битового языка, приводиться к наиболее абстрактной форме, а может и непосредственно преобразовываться в коды процессора, может обращаться к своей внутренней подпрограмме, чтобы не повторять всякий раз одина- вые блоки и т.п. Число на втором месте может вообще оказаться излишним. Главное, что с введением подпрограммы зафиксирована точка, от которой теперь можно не только по формальным правилам двигаться вниз, но и ид- ти к дальнейшим надстройкам с целью удобного описания сложных алгорит- мов. 2. Назначение бита, указанного параметрически Обозначение имеет вид B(имя бита, число, имя бита, число, пара имен битов). В отличие от извлечения бита здесь z задано и не изменя- ется в подпрограмме. Пример: B(a,10,b,4,yz). За этой записью скрываются 20 команд: (yzb(0)b(1)b(01)b(11)=000000, ya(0)=10), (yzb(0)b(1)b(01)b(11)=010000, ya(0)=11), (yzb(0)b(1)b(01)b(11)=001000, ya(1)=10),... Или в сокращенной записи: {(yz,b(0)b(1)b(01)b(11)=00,J ; ya(J)=10) : J=0,...,9}, {(yz,b(0)b(1)b(01)b(11)=01,J ; ya(J)=11) : J=0,...,9}. 3. Счетчик T0 Счетчик включает в себя три вещи: установка начального значе- ния (нуля), добавление единицы, сравнение с конечным значением. Из них непременной является только вторая часть. Начальное значение можно ус- танавливать вовне, и оно будет входной информацией для счетчика. Сверка с конечным значением не всегда нужна, потому что выход из цикла может производиться по другим признакам. Но мы включим в счетчик все части. При желании нетрудно выбросить лишнее. Для наглядности сначала рассмотрим счетчик при ограничении N0=31. Т.е. для записи чисел достаточно L= [log2(N0)]+1 = 5 двоичных разрядов, а для имен информаций - по 5 символов. Пусть abcde - имя ин- формации, которая собственно и является счетчиком. В подпрограмме T0 значение для сравнения фиксировано, пусть для определенности это 7. Чтобы заработала (или не заработала первая часть (обнуление счетчика), нужен бит, управляющий этим процессом. Обозначим его x. До- говоримся, что обычно программа держит x=0, а когда понадобится открыть счетчик, полагает x=1. Таким образом, x - это входная информация для подпрограммы. Для обнуления счетчика в подпрограмме достаточно одной команды (x=0, abcdex=000001). В результате ее выполнения попутно (но и обязательно) получаем x=1, и работа подпрограммы по первой ее части за- кончена. Чтобы заработала вторая часть, тоже нужен управляющий бит. Обо- значим его y. И также пусть y=0 при работе программы, и y=1 при надоб- ности в изменении счетчика. Соответствующая часть подпрограммы может быть: (abcdey=000000, abcdey=100001), (abcdey=100000, abcdey=010001), ... (abcdey=011110, abcdey=111111). Всего 31 команда. Здесь не исполь- зуется то, что конечное значение равно 7. Так что приведенный фрагмент годится и для более общих ситуаций. Если же использовать конкретное конечное значение 7, то можно выкинуть все, что касается битов d и e, а также сократить количество команд до 8. На этом можно было и кончить, если не нужна третья часть под- программы. Иначе и вторую придет организовать по-другому. Во-первых, нужен бит для отражения результата сравнения, обозначим его z. Можно было бы потребовать, чтобы программа поставляла некое его начальное значение. Но, преследуя цель максимально нагрузить подпрограмму и со- ответственно разгрузить программу (которая и без того может быть очень сложна), значение z будем полностью формировать в подпрограмме. Таким образом, z - это выходной параметр подпрограммы. В этом случае вторая и третья часть подпрограммы при использовании фиксированного конечного значения 7 приобретут вид: (abcy=0000, abcyz=10010), (abcy=1000, abcyz=01010), ... , (abcy=0110, abcyz=11111). Для краткости (но ни в коем случае не в смысле введения новых команд) описанный набор команд можно обозначить T0(abcde,xyz,7). Еще раз подчеркнем, что хотя мы и называем такое обозначение и скрывающий- ся за ним набор команд подпрограммой (что в общем вполне созвучно по- нятию подмножества), но здесь понятие подпрограммы существенно отлича- ется от используемого в других языках. Например, здесь число 7 опреде- лило сам объем подпрограммы. Итак, за записью T0(abcde, xyz, 7) стоит множество из 8 команд: (x=0, abcdex=000001), (abcy=0000, abcyz=10010), (abcy=1000, abcyz=01010), (abcy=0100, abcyz=11010), (abcy=1100, abcyz=00110), (abcy=0010, abcyz=10110), (abcy=1010, abcyz=01110), (abcy=0110, abcyz=11111). Как только в информационном поле окажется x=0, то подпрограмма обнуля- ет abcde и полагает x=1. Если окажется y=0, то abc увеличивается на 1 и сравнивается с 7; при равенстве выдается z=1, иначе z=0. За записью T0(abcdef, xyz, 3) стоят 4 команды: (x=0, abcdefx=0000001), (aby=000, abyz=1010), (aby=100, abyz=0110), (aby=010, abyz=1111). При таком определении в скобках под T0 на первом месте может стоять только имя информации (т.е. набор символов - имен битов), на втором месте - три символа - имена двух входных и одного выходного би- тов, на третьем месте - только натуральное число (в десятичной записи), не превышающее N0. Причем длина имени на первом месте не должна быть меньше, чем разрядов в двоичной записи числа с третьего места. (Конечно, можно было дать другое определение T0, например, об- нулять столько битов, сколько по существу нужно для дальнейших опера- ций, но команд от этого меньше не станет, к тому же всегда есть возмо- ность вместо T0(abcdef, xyz, 3) написать T0(ab, xyz, 3). ) Объем T1: K, где K - конечное значение. Цена одного оборота: 3+2*(log2(K)+1), суммарная цена по всем оборотам: 5K+2*K*log2(K). 4. Счетчик T1 В отличие от T0 здесь конечное значение не фиксировано, а яв- ляется входной информацией, обозначение: pqrst. (Как и выше: N0=31, L=5.) Тогда за T1(abcde, xyz, pqrst) можно подразумевать: (x=0, abcdehjklmnox=0000011000001), (apjy=0010, awjkh=10010), (apjy=1010, awjk=0101), (apjy=0110, awjk=1001), (apjy=1110, awjkh=01010), (bqwky=00010, bwklh=10010), (bqwky=10010, bwkl=0101), (bqwky=01010, bwkl=1001), (bqwky=11010, bwklh=01010), (bqwky=00110, bwkl=0101), (bqwky=10110, bwklh=11010), (bqwky=01110, bwklh=01010), (bqwky=11110, bwkl=1101), ... (etwny=00010, enoh=1010),... (hoy=010, hjoyz=11010), (hoy=110, hjoyz=11011). Здесь попутно с обнулением счетчика задается значение h=1, ко- торое служит рабочим для формирования итогового z, и задается вспомо- гательная информация jklmno=100000, которая затем поможет регулировать процесс сравнения с конечным значением. После каждого оборота счетчика все эти переменные приводятся к такому же состоянию, как после обнуле- ния счетчика. Добавление единицы к счетчику и сравнение с конечным значением производятся совместно. w - это бит переноса. После работы с очередным разрядом единичка в информации jklmno продвигается вправо и в итоге оказывается jklmno=000001. По состоянию o=1 вступает в дейст- вие одна из двух команд, выписанных последними. Она переводит значение бита h в значение z и делает jo=10, подготавливая состояние для следу- ющего обращения к подпрограмме. В общем случае в скобках под T1 на первом месте должно стоять имя информации фиксированной длины L (например, 6), это и есть собстве- нно счетчик. На втором месте стоят три символа, например, xyz. На тре- тьем месте - имя информации, задающей конечное значение, ее длина тоже L. Если в информационном поле бит x принял значение 0, то подпрограмма обнуляет счетчик и выдает x=1. Если оказалось y=0, то подпрограмма до- бавляет к счетчику единицу и сравнивает его новое значение с конечным; при равенстве выдается yz=11, иначе yz=10. Объем T1: 1 + 4 + 8*(L-1) + 2 = 8*L-1, где L=log2(N0) с округ- лением до большего целого. Цена одного оборота: T1: 10*L+6, суммарная цена по всем оборотам: N0*(10*log2(N0)+16). 5. Счетчик T2 Этот счетчик по существу не отличается от T1, кроме как тем, что длинная информация идентифицируется по имени ее начального бита и на четвертом месте указывается (числом или фиксированной константой) длина этой информации. Пример: T2(a, xyz, p, 64). Здесь переменная счетчика и конеч- ное значение имеют длину 64 (т.е. могут быть от 0 до 2**64-1). 6. Перенос информации На этой подпрограмме показывается, как могут использоваться подпрограммы. Пусть a, b, c - имена начальных битов трех информаций, тре- тья информация содержит длину первых двух и сама для определенности имеет длину 32. Бит a указывает источник, b - получатель информации. Тогда запись M2(a,b,c,32) означает: T2(d, xyz, c, 32), A(a, 4294967296, d, 32, uw), B(b, 4294967296, d, 32, vw), (stx=001, su=10), (stu=101, stv=010), (stv=011, sy=10), (stz=110,st=00). Здесь для запуска необходимо: xuv=011, st=00. В этом начальном состоянии может сработать только обнуление счетчика, указанного именем бита d. Тогда оказывается x=1 , и может заработать только первая из че- тырех отдельно выписанных команд. Выдав u=0, она запустит подпрограмму извлечения бита из информации, представленной битом a. Подпрограмма A восстановит u=1 и выдаст искомое значение в бите w. Теперь может вклю- читься только вторая из отдельных команд, которая аналогично ведет к запуску подпрограммы B. После этого может заработать только предпослед- няя команда, которая активизирует подпрограмму счетчика. Если счетчик достиг конечного состояния, то z=1 и ввиду stuvxy=111111 ни одна коман- да не может вступить в действие, перенос информации закончен. В против- ном случае срабатывает последняя команда, за ней 4-я с конца и далее аналогично рассмотренному процессу. 7. Сложение Пусть a, b, c - имена начальных битов трех информаций. Требу- ется выдать в третьей арифметическую сумму первых двух. Длина всех трех информаций одинакова. Пусть для определенности она равна 30. Бу- дут также использоваться: p - извлеченый из 1-й информации бит, q - извлеченный из 2-й информации бит, m - бит переноса. Рабочая сумма би- тов p и q будет помещаться снова в p. Для запуска подпрограммы понадо- бится: xuvwm=01110, rst=000. Тогда за записью S0(a,b,c,30) стоит: T0(defgh, xyz, 30), A(a,30,d,5,up), A(b,30,d,5,vq), B(c,30,d,5,wp), (rstx=0001, ru=10), (rstu=1001, rsv=010), (rstvpqm=0101000, rp=10), (rstvpqm=0101100, rp=11), (rstvpqm=0101010, rp=11), (rstvpqm=0101110, rpm=101), (rstvpqm=0101001, rpm=110), (rstvpqm=0101101, rp=10), (rstvpqm=0101011, rp=10), (rstvpqm=0101111, rp=11), (rst=110, rsty=0010), (rstz=0010, t=0). Сначала срабатывает подпрограмма T0, а точнее: обнуление счет- чика defgh, который затем идентифицируется по имени своего начального бита. Следующими задействуются две первые команды из выписанных отде- льно: одна устанавливает u=0 и инициирует тем самым извлечение бита p подпрограммой A, а вторая - извлечение бита q. Эти шаги отражаются из- менениями показателя rst от 000 до 010. Затем срабатывает одна из оче- редных восьми команд, засылая p+q в p, определяя новое значение бита переноса m и увеличивая на единицу значение показателя rst. Предпосле- дняя (по записи) команда создает условия для запуска T0, а последняя сверяет z с 0, т.е. проверяет, не достиг ли счетчик конечного значения 30. Если достиг (z=1), то ни одна команда уже не может вступить в ра- боту. А если нет, то вновь оказывается rst=000, извлекается очередной бит из первой исходной информации и т.д. Здесь не ставится цель систематического изложения подпрограмм для битового языка. Однако на двух последних примерах видны методы ис- пользования подпрограмм, приемы образования новых подпрограмм, а также пути перевода на битовый язык понятий других языков. Например, если запись A=B+C на некотором языке означает сложение 16-разрядных чисел, то для перевода на битовый язык можно написать S0(A,B,C,16) ; правда, для запуска и включения этой подпрограммы в программу понадобятся упра- вляющие биты. Запись, конечно, будет длиннее, но никто не собирается поручать эту стандартную работу человеку. Это дело транслятора. Отсюда также не следует, что для интерпретации на конкретном процессоре надо разворачивать S0 в длинную серию битовых команд. Запись в виде подпро- грамм может непосредственно переводиться в коды процессора, если в нем есть команды соответствующего назначения. Управляющие биты при этом помогут определить порядок выполнения команд процессора (в зависимости от технической возможности распараллеливания, например) и в загрузоч- ный модуль входить не обязаны. Поэтому не следует думать, что при дво- йном переводе получится загрузочный модуль большего объема. Наоборот, разложение команд развитого языка на немногочисленные стандартные эле- менты битового языка может подсказать новые пути оптимизации программ. VIII. ЗАДАЧИ При рассмотрении задач предлагается руководствоваться следую- щими правилами на основе сделанного выше выбора простейших алгоритмов. Оценка стоимости алгоритма снизу может быть получена, исходя из объема входной и выходной информации. Например, если длина исходной информации равна N (и информация используется по существу, а не выда- ется результат, скажем, сразу по первому ее знаку), то цена алгоритма не может быть меньше N. Оценки сверху будут выдаваться в виде порядка, исходя порядков следующих алгоритмов. Для информаций длины N порядок ln(N) имеют: - извлечение и назначение бита, указанного параметрически; порядок N*ln(N) имеют: - перенос информации, - назначение информации, - сравнение двух информаций, - арифметическое сложение, - арифметическое вычитание, - логическое "ИЛИ", - логическое "И", - счетчик, принимающий целые значения от 0 до N (и произво- дящего на каждом шаге сравнение с конечным значением). (При этом в операциях переноса, назначения информации и др. имеется ввиду операция над всей информацией целиком. Если переносится, например, часть информации, указанная параметрически, то это другая задача.) Отличие предложенного подхода от распространенных в литературе состоит в следующем. За единицу измерения приняты операции над битами, а не над числами и, более того, цена зависит не только от того, сколь- ко информации участвует в операции, но и от того, из чего она берется. Следовательно, операции сложения, умножения и т.д. здесь окажутся зна- чительно дороже, что существенно повлияет на оценки сложных алгоритмов. Насколько оправдан такой подход? Действительно, на современной технике, как правило, неважно берем ли мы бит из большого массива или из малого, из начала памяти или из конца. А если и есть отличия, то они обуслов- лены техническими особенностями и в них трудно углядеть материал для развития теории. На ряде задач при четких ограничениях вполне уместно вводить крупные единицы измерения, но для асимптотических оценок сове- ршенно неверно объявлять константой то, что что на самом деле идет к бесконечности. Возьмем то же извлечение информации по адресу. Любому здраво- мыслящему человеку ясно, что длинный номер телефона запомнить и наб- рать труднее, чем короткий; что найти нужные сведения в толстой книге труднее, чем в тонкой; что найти по номеру незнакомый дом на длинной улице труднее, чем на короткой и т.п. И в основе этих трудностей лежит закон, что для идентификации объекта в большем объеме нужен и более сложный адрес, обработка которого естественно будет стоить дороже. Это однако нисколько не мешает многим специалистам принимать обработку ад- реса за единицу и продолжать до бесконечности то, что допустимо только на ограниченном объеме. Конечно, отличия, получаемые в экспериментах на тех же малых объемах, невелики и вроде бы подтверждают ненужность копания в битах. Возможно, в этом и состоит одна из причин, почему по миру распростра- нилось программное обеспечение, избыточное по объему в 100 раз и столь же неудовлетворительное по скорости. На самом деле более точные оценки неизбежно проявляют себя, а тщательная оптимизация вскрывает огромные резервы вычислительной техники. 1. Сравнение двух натуральных чисел Пусть числа не превосходят N и записаны в двоичной форме. Тогда для записи каждого числа достаточно log2(N) знаков (ок- ругление до большего целого) и согласно изложенным правила стоимость сравнения имеет порядок log2(N)*ln(log2(N)), т.е. ln(N)*ln(ln(N)). 2. Сравнение двух вещественных чисел Если один бит отводится на знак числа, N1 - на двоичные знаки целой части, N2 - на двоичные знаки дробной части, то стоимость имеет порядок N*ln(N), где N=N1+N2+1. 3. Умножение двух целых чисел Для отрицательных чисел может потребоваться дополнительные преобразования, которые однако не меняют порядок оценки. Поэтому будем считать числа неотрицательными и заданными в двоичной форме. Длина со- множителей N, произведения 2N. Сначала все биты результата обнуляются. Создается вспомогате- льное хранилище из 2N битов, в которое (в младшую часть) записывается первый сомножитель, а остаток заполняется нулями. Затем N раз произво- дятся следующие действия. Очередной бит второго сомножителя сравнивае- тся с нулем. При несовпадении содержимое вспомогательного хранилища добавляется к результату. И далее в любом случае содержимое хранилища сдвигается, точнее, умножается на 2. Затем: сравнение хранилища с тож- дественным нулем. Таким образом, порядок стоимости N*N*ln(N). 4. Поиск максимального числа Дано N натуральных чисел в двоичной записи, каждое не превос- ходит N. L=log2(N) Объем исходной информации N*log2(N) и оценка не может быть лу- чше N*log2(N) . Переносим в выходные данные 1-е из заданных чисел (последова- тельность не существенна, главное: перебрать их все). Затем каждое из оставшихся чисел сравнивается с выходным и, возможно, вписывается на место результата. Итого: N*ln(N)*ln(ln(N)). 5. Упорядочение набора натуральных чисел Форма задания - как в задаче 4. Для каждого K от 1 до N обнулим счетчик, который сможет прини- мать значения от 0 до N (всего порядок стоимости: N*ln(N)*ln(ln(N))). Очередное из исходных чисел есть некоторое K, и соответствующий счетчик увеличиваем на 1 (вклад по всем числам: N*ln(N)*ln(ln(N))). Итоговые значения счетчиков в принципе можно считать результатом упорядочения. Если требуется позиционно переписать исходные числа в порядке, напри- мер, неубывания, то по каждому K-му счетчику надо образовать в явном виде число K и переписать его в выходные данные столько раз, каково значение счетчика, что не меняет порядка стоимости. 6. Перенос внутри информации Длина исходной информации: N, длина перемещаемого отрезка: K, номер бита в начале отрезка: A1, номер бита в начале заполняемого уча- стка: A2. Все параметры не фиксированы и являются входной информацией. Работа счетчика от 1 до K стоит K*ln(K). Разовое изменение ад- реса источника: ln(N)*ln(ln(N)), по всему циклу: K*ln(N)*ln(ln(N)). Столько же для адреса приемника. Извлечение одного бита: ln(N), по всему циклу: K*ln(N). Столько же по назначению битов. Итого порядок: K*ln(N)*ln(ln(N)). Тот же для извлечения или назначения последовательных K битов указанных параметрически. (Заметим, что K здесь тоже входная информа- ция. Если бы K было фиксировано, то оценка другая: K*ln(N).) 7. Извлечение всей информации порциями Длина исходной информации: N, длина порции: K. Параметры не фиксированы. Извлечь надо последовательно всю информацию за M=N/K ша- гов (предполагается, что N кратно K). Работа внешнего счетчика от 1 до M стоит M*ln(M). Обнулим A - текущий номер позиции (относительно исходной информации) начала оче- редной порции (цена ln(N)). Образуем внутренний счетчик от 1 до K (це- на K*ln(K)). При одном шаге внутреннего счетчика разовое изменение A стоит ln(N)*ln(ln(N)), извлечение одного бита: ln(N). Всего: N*ln(N)*ln(ln(N)). Т.е. не зависит от длины порции. 8. Упорядочение вещественных чисел Форма задания чисел - как в задаче 2. K - их количество. Пред- полагается, что длина L=log2(K) записи K короче, чем N=N1+N2+1. Тогда лучше манипулировать номерами исходных чисел в наборе из K членов по L битов на каждый член. На первом шаге пишем единицу первым членом набора (стоимость имеет порядок L*ln(L) ). На очередном шаге надо сравнить i-ое вещест- венное число с минимальным и максимальным из перебранных, их номера стоят на краях заполненной части набора. Если число не оказалось экстр- емальным, то сравнивается с числом, чей номер находится в середине за- полненной части набора. И далее производится деление пополам (по возм- ожности). Всего нужно не более log2(i) сравнений вещественных чисел. Затем понадобится вставить i в набор, передвинув не более i членов по L битов каждый. Сравнение пары вещественных чисел дает вклад N*ln(N). Для i-го числа может понадобиться log2(i) сравнений, т.е. вклад в стоимость N*ln(N)*log2(i), а по всем числам: N*ln(N)*log2(K!). При этом произво- дятся операции, которые дают меньший вклад: счетчик по i оценивается в K*ln(K); вычисление номера очередного вещественного числа среди уже упорядоченных для сравнения с i-м - в K*ln(K), а по всем i - в K*K*ln(K) ; извлечение этого числа - N*ln(K*N)*ln(ln(K*N)), а по всем i - K*N*ln(K*N)*ln(ln(K*N)). Перемещение i*L битов стоит i*L*ln(K*L)*ln(ln(K*L)), а по всему циклу: K*K*ln(K)*ln(K)*ln(ln(K)). Вставка i в набор - дешевле. Таким образом, наибольший вклад дают чле- ны: N*ln(N)*ln(K!) и (K*ln(K))**2*ln(ln(K)). 9. Сравнение длин двух отрезков на эвклидовой плоскости Координаты концов заданы веществеными числами как в задаче 2. Требуется выделить из двух отрезков наибольший. Любопытно, что в такой постановке задача некорректна, посколь- ку не определено правило вычисления длин отрезков. Ссылка на эвклидову метрику здесь ничего не дает, так как нет взаимно однозначного соотве- тствия между вещественными числами и той формой, в какой они здесь представлены. Если расстояния между точками на плоскости измерять "ве- щественными" числами из задачи 2, то нетрудно привести пример, ког- да теоретически разные расстояния получат идентичные представления. Не поможет и попытка увеличить точность при подсчете расстояний, потому что для любой заданной точности найдутся примеры, неразличимые в рам- ках этой точности. Чтобы спуститься с теоретических небес к практике необходимо признать следующее. Разумеется, из двух отрезков один (или оба) всегда является наибольшим, но установление этого факта невозможно фиксирова- нным раз и навсегда объемом операций. От случая к случаю может требо- ваться все большее количество вычислений, и их объем ничем не ограни- чен, хотя и конечен в каждом конкретном случае. Если же мы хотим иметь конечные оценки (в зависимости, например, от числа заданных отрезков), то должны признать решением не ту абстракцию, добраться до которой не- реально, а то, что отличается от нее на приемлемую величину. В данной задаче эта величина должна быть сопоставима с ролью младшей единицы в избранной записи вещественных чисел. При этом надо осознавать, что при применении алгоритма на конкретной ситуации мы не получим не только точного значения расстояния, но можем получить в качестве наибольшего вовсе не тот отрезок, какой является наибольшим в абстрактном смысле. Вместе с тем, никто не запрещает увеличивать N2 и не ставит границ на приближении к точной абстракции. 10. Диаметр конечного множества точек на плоскости Задано K точек как в предыдущей задаче. Требуется найти пару точек, на которой достигается максимальное расстояние. С учетом услов- ностей, отмеченный в предыдущей задаче мы вправе пользоваться при по- строении алгоритма дополнительной величиной g - границей различимости вещественных чисел, т.е. таким положительным числом, что при работе алгоритма любое меньшее по модулю число может быть только нулем. Одна- ко не следует рассчитывать, что алгоритм способен обеспечить итоговую точность вычисления диаметра в пределах g. Такое требование некоррект- но, поскольку заранее исключает все неточные операции, которых в прин- ципе может понадобиться довольно много. Но законно требовать, чтобы итоговая точность отличалась от g на некоторую мультипликативную пос- тоянную или, по крайней мере, улучшалась с ростом N2 или, что то же, с уменьшением g. Возьмем на плоскости произвольную линию и спроектируем на нее заданные точки. Порядок цены при этом определяется работой счетчика и равен K*ln(K). Поворачивая эту линию, в принципе можно добиться, что наибольший отрезок даст и наибольшую проекцию той же длины. Однако с учетом имеющейся величины g нет надобности перебирать все углы поворо- та от 0 до 180 градусов, достаточно пройтись с шагом g/R радиан, чтобы погрешность от неточного угла дала вклад в проекцию точки не более g. Здесь R - это радиус круга, в котором содержатся все исходные точки. (На самом деле достаточно пройтись с гораздо большим шагом, равным квадратному корню из указанной величины, потому что для проекции наи- большего отрезка важны проекции не всех точек, а только своих двоих и только тогда, когда этот отрезок почти параллелен прямой.) Для этого понадобится счетчик от 0 до 4R/g, который от K не зависит. Итак, порядок K*ln(K). Таков же он для пространства любой ко- нечной размерности. Только в 3-мерном пространстве надо будет повора- чивать плоскость, чтобы свести дело к решению ограниченного количе- ства двумерных задач. При увеличении размерности пространства на еди- ницу объем вычислений всякий раз будет увеличиваться в одно и то же количество раз, не зависящее от K. 11. Изоморфизм деревьев Скорость алгоритма проверки изоморфизма деревьев (как и гра- фов) зависит от формы задания деревьев. Для любой заданной скорости нетрудно привести форму с избыточной информацией, при которой не суще- ствует алгоритма, обеспечивающего эту скорость. Поэтому в отрыве от понятия формы бессмысленно искать некий наилучший алгоритм. Мы рассмо- рим три формы с оценками N*ln(N), N*(ln(N))**2 и N*N*(ln(N))**3 соответственно, где N - количество вершин. а). Форма экстремального обхода Дерево можно задать в форме ОБХОДА, т.е. упорядоченого набора из 2*(N-1) нулей и единиц, в котором 0 отвечает первому проходу по ре- бру, а 1 - второму (обратному) проходу. Припишем к каждой K-ой позиции вес 2**(2N-K). По каждой позиции умножим вес на соответствующее значе- (0 или 1) в наборе и просуммируем по всем позициям. Получим вес, отве- чающий выбранному обходу дерева. Из всех обходов один имеет наименьший вес, при этом получим форму ЭКСТРЕМАЛЬНОГО ОБХОДА. Для задания дерева в таких формах достаточно 2N-2 битов информации. Для проверки изоморфизма двух деревьев, заданных в форме экст- ремального обхода, достаточно сравнить две информации длиной 2N-2, т.е. порядок цены N*ln(N). б). Каноническая форма Пусть дано дерево с N вершинами. Произвольно пронумеруем вер- шины от 1 до N и произвольно выберем среди них корневую. Тогда дерево можно задать набором из N целых чисел от 0 до N: в K-ой позиции (счет позиций с 1 до N) надо поместить номер вершины-отца для вершины с но- мером K, а если вершина корневая, то 0. Назовем эту форму задания де- рева ПРОСТОЙ. Припишем к каждой K-ой позиции вес N**(N-K). По каждой позиции умножим вес на номер вписанной в нее вершины-отца и просумми- руем по всем позициям. Получим вес, отвечающий выбранной нумерации ве- ршин деревьев и выбору корневой вершины. Из всех нумераций и выборов корневой вершины одна имеет наименьший вес. Полученную при этом форму задания дерева назовем КАНОНИЧЕСКОЙ. Для задания дерева в таких формах достаточно N*log2(N)+N битов информации. В канонической форме на первой позиции обязательно стоит 0 (т. е. корневая вершина получила первый номер), а на втором 1 (при N>1), которые на самом деле никакой информации не несут. Поэтому дерево (с точностью до изоморфизма) однозначно определяется остальными N-2 це- лыми числами от 1 до N-1. (Вершина с номером N обязательно окажется концевой.) Причем эти числа упорядочены по неубыванию и число в K-ой позиции не превосходит K-1. Для проверки изоморфизма двух деревьев в канонических формах достаточно сравнить N-2 указанных чисел, т.е. log2(2) + [log2(3)] + ... + [log2(N-1)] битов информации. Квадратные скобки означают округление до большего целого. Полученная сумма не превосходит N-3 + log2((N-1)!), т.е. в первом приближении N*ln(N). (На самом деле отсеивание лишней информации из канонической формы и введение серии вспомогательных форм позволяет получить для них количество информации N*ln(ln(N)), затем до N*(ln(ln(ln(N))) и т.д., а также получить бесконечное количество серий с еще более лучшими значе- ниями.) Итого порядок стоимости: N*ln(N)*ln(N). в). Простая форма Выбросим из дерева концевые вершины. Из того, что осталось, снова выбросим концевые вершины и т.д. В итоге останется одна или две вершины, которые можно назвать центральными для исходного дерева. Если у двух деревьев разное количество центральных вершин, то они не изоморфны. В противном случае задача сводится к проверке изомо- рфизма не более чем двух пар корневых деревьев. Алгоритм приведения к корневому дереву может быть таким. Соз- даются две вспомогательные информации длиной N. Первая из них обнуля- ется. Для каждого номера из исходной простой формы дерева ставим 1 в первую вспомогательную информацию на позицию с тем же номером. Для этого надо прочитать исходную форму порциями (цена: N*ln(N)*ln(ln(N)), см. задачу 6). Первую вспомогательную информацию переносим во вторую, а первую снова обнуляем. Опять читаем номер и ставим 1, но теперь и при последующих проходах это делается только для тех порций, которым во второй вспомогательной информации отвечает 1. Итого цена N*N*ln(N))*ln(ln(N)) за получение корня. Для каждой вершины составим список ее соседних вершины. Для этого достаточно один раз пройтись по простой форме (N*ln(N)*ln(ln(N))) и для каждого номера вписать два числа (тот же номер и номер позиции) в два соответствующих списка. Теперь надо разделить все вершины по уровням: корню - самый высокий, затем его сыновьям и т.д., и наконец нулевой уровень - самым дальним родственникам. Во вспомогательной информации длиной N*log2(N) ставим номер N в порции, отвечающей номеру корня. Выписываем отдельно соседей корня, а во вспомогательной информации одновременно ставим N-1 в порциях, отвечающих номерам соседей корня. Затем проходим по списку сыновей корня и составляем список внуков корня. И т.д. Все это уклады- вается в ту же цену N*ln(N)*ln(ln(N)), поскольку суммарная длина спис- ков соседей, а также суммарная длина списков сыновей, внуков и пр. имеет тот же порядок, как исходная информация для простой формы. Всем листьям присваивается тип 0. Каждой вершине первого уров- ня, не получившей тип, присваивается тип, равный количеству ее сыно- вей. Вершины первого уровня упорядочиваются по типам. Если у второго дерева аналогичный список оказался иной длины или с несоответствующими типами, то деревья не изоморфны. Каждой вершине второго уровня, не по- лучившей тип ранее (а он мог быть только нулевым), сопоставляется на- бор (который надо упорядочить по неубыванию) типов его сыновей. Множе- ство таких наборов надо упорядочить, например, словарно и перенумеро- вать его элементы. Эти номера станут типами вершин третьего уровня. И т.д. Либо на некотором шаге упорядоченные списки вершин окажутся различными для деревьев, либо в итоге корни получат одинаковый тип (что означает наличие изоморфизма). Из упомянутых операций наиболее трудоемким на каждом шаге яв- ляется словарное упорядочение наборов (где каждый набор есть упорядо- ченный список типов сыновей). Количество таких наборов (совпадающее с количеством вершин очередного уровня) обозначим K. Количество инфор- мации в каждом наборе не превышает M*ln(N), где M - количество вершин на предыдущем уровне. Как и в задаче об упорядочении вещественных чи- сел, операции с перестановкой местных номеров наборов оцениваются в (K*ln(K))**2*ln(ln(K)), что при суммировании для всего алгоритма дает (N*ln(N))**2*ln(ln(N)) и решающего значения не имеет. Сравнение пары наборов не превышает M*ln(N)*ln(M*ln(N)), для всего упорядочения на- боров M*ln(N)*ln(M*ln(N))*ln(K!), для всего алгоритма N*N*(ln(N))**3. 12. Изоморфизм графов Пусть граф не имеет кратных ребер. Перенумеруем его вершины от 1 до N и заполним симметричную матрицу N*N , где 1 означает наличие, а 0 - отсутствие соответствующего ребра. Кроме того, перенумеруем клетки матрицы от 1 до N*N по строкам, слева направо; и припишем каждой клет- ке вес 2**(N*N-i), где i - номер клетки. Умножим значение каждого эле- мента матрицы на вес соответствующей клетки и просуммируем по всей ма- трице. Получим вес матрицы, отвечающий выбранной нумерации вершин гра- фа. Из всех нумераций одна имеет наименьший вес, получающуюся при этом матрицу назовем канонической формой графа. Для проверки изоморфизма двух графов в канонических формах до- статочно сравнить N(N-1)/2 битов информации (множество нулей и единиц над главной диагональю), что по стоимости составляет N*N*ln(N). Покажем, что есть формы, задаваемые меньшим объемом информации (и дающие более быстрые алгоритмы). Заметим, что при канонической форме над главной диагональю в первой строке сначала идет набор единиц, затем набор из нулей (возмож- но: пустые), вторая строка содержит 4 набора (единицы, нули, единицы, нули), т.е. определяется тремя точками деления, в которых средняя сов- падает с точкой деления первой строки. Очередная строка имеет вдвое больше наборов: отрезки предыдущей строки делятся на две части. Поэто- му первая строка определяется количеством единиц в ней, т.е. [log(N)] битами, для задания второй строки теперь достаточно 2*[log(N-1)] битов и т.д. Логарифмы - двоичные, квадратные скобки означают округление до большего целого. (Выигрыш от всех строк в первом приближении составля- ет N*log(N) битов.) В заключение еще раз подчеркнем, что в рассмотренных задачах оценки даны при условиях, указанных в начале раздела. Существуют луч- шие оценки вплоть до линейных за счет резкого увеличения объемов алго- ритмов; такие алгоритмы безусловно имеют свою область применения, но последняя ограничена лишь небольшими значениями параметров, поэтому в практическом плане часто бывает бессмысленно изучать поведение таких алгоритмов при значениях параметров, уходящих в бесконечность. Здесь же выведены реальные и проверяемые оценки, причем в расчете на перспе- ктивы развития ЭВМ. Невесенко Н.В. 6 декабря 2002 г. © 2002 Suncloud.Ru