Cтраница 4
Частичным подобием этого может служить ныне разра батываемая машина ILLIAC IY, хотя она будет еще програм мироваться последовательной входной лентой. [46]
Разбор выражения. [47] |
Акцептор с магазинной памятью-это автомат с магазинной памятью и следующим условием: если вслед за считыванием последнего символа с входной ленты автомат считывает а из магазина, то считанная строка называется принятой; иначе - отвергнутой. [48]
Многоленточная машина Тьюринга имеет конечное число рабочих лент, на каждой из которых находится по одной головке, и отдельную входную ленту с только читающей головкой с двусторонним движением. Рабочие ленты бесконечны вправо и влево. Первоначально рабочие ленты пусты, а головка на входной ленте расположена на крайне левом символе входного слова. Машина допускает входное слово, приходя в допускающее состояние и останавливаясь. [49]
В литературе часто приводится определение емкостной сложности машины Тьюринга, при котором не учитывается число клеток, просмотренных на входной ленте - ведь на входной ленте нельзя изменять символы. Поскольку здесь нас интересуют лишь большие емкостные сложности, то результат для сложностей, меньших п, не стоит дополнительных деталей, нужных для него, и мы его опускаем. [50]
Идея построения такой процедуры состоит в том, что начальные упорядоченные группы распределяются по входным лентам неравномерно, и поэтому входные ленты в процессе выполнения операторов слияния освобождаются неодновременно. Освободившаяся входная лента назначается выходной для следующих операторов слияния, а лента, выполнявшая до этого функции выходной ленты - входной. Размер упорядоченных участков на ленте, переназначенной из выходных во входные, естественно, будет отличаться от размеров упорядоченных участков на других входных лентах, и поэтому последовательное применение указанного алгоритма приведет к тому, что количество упорядоченных участков на всех входных лентах будет разным и размеры упорядоченных участков тоже будут отличаться друг от друга. Неравенство друг другу размеров сливаемых участков будет, естественно, снижать результативность и эффективность операторов слияния. [51]
Запросы для данного класса обработки ( например, класса А) всегда хранятся на лентах ( или дисках), называемых входными лентами ( или дисками), которые подключаются на период обработки заданий данного класса. Требования на обработку для других классов ( например, классов В и X) откладываются. [52]
Ввод с удвоенной буферизацией. Совмещение чтения-записи. [53] |
Фрэнд [14] установил, что абсолютную гарантию от зависания при чтении может дать только ( / 1) буфер для каждой из / входных лент. Эта конфигурация обеспечивает непрерывное чтение в течение просмотра и гарантирует, что оно не станет источником задержки. [54]
Завершив объединение очередных участков, сегмент выходной ленты подготавливается к записи на вторую выходную ленту, а во входные сегменты записываются очередные сегменты входных лент. [55]
Группу операторов слияния, исполняемых, начиная с момента освобождения одной из входных лент, назначаемой выходной, и вплоть до освобождения какой-либо другой входной ленты, будем называть этапом слияния. [56]