Входная лента

Cтраница 2

В течение просмотра имеется k / 2 входных лент и одна лента вывода. При наиболее эффективном просмотре слияния запись будет выполняться непрерывно и параллельно со всеми операциями считывания и внутренними операциями. [16]

Машина с произвольным доступом к памяти. [17]

Всякий раз, когда символ считывается с входной ленты, ее читающая головка сдвигается на одну клетку вправо. Выход представляет собой ленту, на которую машина может только записывать; она разбита на клетки, которые вначале все пусты. При выполнении команды записи в той клетке выходной ленты, которую в текущий момент обозревает ее головка, печатается целое число и головка затем сдвигается на одну клетку вправо. Как только выходной символ записан, его уже нельзя изменить. [18]

Конечный автомат. [19]

Будем предполагать, что программа записана на входной ленте. Автомат считывает с нее входные символы один за другим. По прочтении каждого входного символа выпечатывается выходной символ на выходной ленте и автомат переходит в следующее состояние прежде чем считать следующий символ программы. [20]

В процессе выполнения оператора слияния с участием т входных лент каждый элемент массива независимо от т должен йыть один раз считан с ленты и один раз записан на ленту. Это значит, что сложность выполнения оператора слияния не зависит от количества входных лент т и целиком определяется длиной объединенного массива. [21]

Вообще говоря, РАМ-программа определяет отображение из множества входных лент в множество выходных лент. [22]

У автоматов с магазинной памятью, кроме бесконечной вправо входной ленты, есть специальная вспомогательная лента, также бесконечная вправо. При движении вспомогательной ленты влево на ней записываются вспомогательные символы, а при движении этой ленты вправо эти символы считываются и стираются. Первым всегда считывается последний записанный символ. В таком автомате невозможно считать символ с ленты памяти, не стерев его. [23]

Машина находится в заключительной ситуации, если на входной ленте обозревается первая слева пустая ячейка, рабочая лента пуста, машина находится в заключительном состоянии. [24]

Из формулы (7.8) особенно ясно, что увеличение количества входных лент резко увеличивает результативность и эффективность группы операторов слияния. [25]

Для того чтобы на каждом этапе слияние с М-1 входных лент было осуществимо, нужно, чтобы распределение ( Si) упорядоченных участков с наибольшими номерами было одинаковым на всех входных лентах. [26]

Первое вычисление: М пытается интерпретировать некоторую начальную часть входной ленты wwb как описание машины Тьюринга MI и затем переходит к моделированию того, что сделала бы эта машина с входной лентой wwb. Если М завершает вычисление, а Мг - допускает од, то М отвергает ее, и обратно. Если од не описывает машины Тьюринга и вычисление не может проходить дальше, то вычисление останавливается и w отвергается. [27]

ДМА называют 2ДМА с k независимыми читающими головками на входной ленте. [28]

Блок-схема алгоритма упорядочения с несколькими выходными лентами. [29]

Блок 7 формирует начальные участки, равномерно записывая их на входные ленты. [30]

Страницы: 1 2 3 4