Cтраница 2
Интуитивно кажется, что процесс сравнения одного блока в хвосте последовательности в сущности не зависит от процесса сравнения следующего блока и что наихудший случай вычисления времени безотносителен к позиции хвостового блока. Чтобы проверить это предположение, мы должны доказать, что в процессе сравнения блоков в начале хвоста М не может переупорядочить свои записи таким образом, чтобы ускорить сравнение более дальних блоков. [16]
Часто вспомогательный барабан лебедки не используется. Вместо хвостового блока устанавливается лебедка с тяговым усилием 50 кН для возврата тягового каната со сцепным приспособлением. При надвиге вагонов главной лебедкой барабан вспомогательной лебедки отключается от привода. [17]
Рассмотрим каждый базовый сегмент, заметим пучок в дереве, которому он соответствует, и найдем последовательность хвостовых блоков, которая ведет к минус-точке в этом пучке. Затем подадим базовый сегмедт М, за которым следует соответствующая последовательность хвостовых блоков, и заметим конфигурацию, в которой М оказалась. [18]
Когда считываются нули и единицы хвостового блока, машина записывает их на третью ленту и образует соответствующую последовательность выходов из нулей. Как только блок заканчивается двойкой, машина начинает сравнивать только что записанный хвостовой блок с каждым из ранее записанных базовых блоков. Каждый хвостовой блок обрабатывается аналогично. [19]
Время, которое нужно М, чтобы произвести k 1 выходов, указанных в 3), зависит от конкретных базового сегмента и хвостового блока и конкретного отображения. Максимум этого времени по всем базовым сегментам из Ah и по всем хвостовым блокам длины k называется временем сравнения, связанным с данным отображением. Заметим, что это отображение Ftl определенно существует. Только лишь конечное число отображений удовлетворяет 1) и 2), и только лишь конечное число входных последовательностей потребуется рассмотреть при проверке 3) и при определении минимального времени сравнения. [20]
Но по определению Fk есть отображение, для которого максимум количества времени, которое М должна потратить на первом хвостовом блоке, наименьший. Таким образом, если машина М использует свое собственное отображение, чтобы подготовиться для проверки хвостовых блоков, то она в самом худшем случае не может иметь на первом хвостовом блоке меньше времени вычисления, чем в случае с Fk - Другими словами, должна существовать входная последовательность в множестве Ak, на которой машина М потратит по крайней мере wk единиц времени на первом хвостовом блоке. [21]
Общее число хвостовых блоков в члене из Ah есть 2й, или приблизительно ra / logra. Теорема 1 устанавливает, что общее время вычисления в худшем случае должно быть пропорционально произведению числа хвостовых блоков, подлежащих сравнению, и максимального числа квадратов на ленте, нужных для записи всей существенной информации о базовом сегменте. Таким образом, невозможно улучшить вполне очевидный способ записи всех наборов, которые присутствуют в базовом сегменте, а потом просмотреть эту запись для каждого вновь поступившего хвостового блока. [22]
Число битов, необходимых для выяснения, который из Ь существенно различных базовых сегментов присутствует, приблизительно равно 2, а это приблизительно равно ra / logra. Это число квадратов есть максимальное число сдвигов ленты, которые должны быть сделаны, чтобы сравнить один хвостовой блок. [23]
Перед проведением разведочных канав с использованием скрепера почвенный слой целесообразно снимать и складировать бульдозером или вручную в ленточные отвалы, расположенные за боковыми контурами выработки. В процессе ликвидации засыпку канавы неплодородным слоем выполняют из торцевых отвалов обратным скреперованием без перестановки скреперной лебедки и хвостового блока, но с перецепкой или заменой скрепера. [24]
Сначала мы должны показать, что не все пучки содержат минус-точку. Заметим, что каждая точка в пучке соответствует конфигурации М, в частности конфигурации, в которой М должна получить символы хвостового блока и вычислить соответствующий этому блоку выход. Если все ветви, исходящие из некоторой точки пучка, помечены знаком минус, то конфигурация, соответствующая этой точке, должна быть такой, чтобы машина потратила меньше чем w единиц времени на следующем хвостовом блоке вне зависимости от набора, содержащегося в этом блоке. [25]
Но по определению Fk есть отображение, для которого максимум количества времени, которое М должна потратить на первом хвостовом блоке, наименьший. Таким образом, если машина М использует свое собственное отображение, чтобы подготовиться для проверки хвостовых блоков, то она в самом худшем случае не может иметь на первом хвостовом блоке меньше времени вычисления, чем в случае с Fk - Другими словами, должна существовать входная последовательность в множестве Ak, на которой машина М потратит по крайней мере wk единиц времени на первом хвостовом блоке. [26]
Но по определению Fk есть отображение, для которого максимум количества времени, которое М должна потратить на первом хвостовом блоке, наименьший. Таким образом, если машина М использует свое собственное отображение, чтобы подготовиться для проверки хвостовых блоков, то она в самом худшем случае не может иметь на первом хвостовом блоке меньше времени вычисления, чем в случае с Fk - Другими словами, должна существовать входная последовательность в множестве Ak, на которой машина М потратит по крайней мере wk единиц времени на первом хвостовом блоке. [27]
Отклоняющее устройство состоит из двух поддерживающих ( горизонтальных) и двух отклоняющих роликов. Отклоняющее устройство необходимо для предотвращения касания тягового и вспомогательного канатов приемного устройства и обеспечения нормальной навивки их на барабаны лебедки. Хвостовой блок огибается вспомогательным канатом и присоединен коушем к тяговому канату. [28]
Когда считываются нули и единицы хвостового блока, машина записывает их на третью ленту и образует соответствующую последовательность выходов из нулей. Как только блок заканчивается двойкой, машина начинает сравнивать только что записанный хвостовой блок с каждым из ранее записанных базовых блоков. Каждый хвостовой блок обрабатывается аналогично. [29]
Чтобы сравнить хвостовой блок с одним из записанных базовых блоков, машина должна просмотреть два набора, сравнивая их символ за символом. Однако хвостовой блок может сравниваться со всеми записанными базовыми блоками, и читающая головка, которая рассматривает хвостовой набор, должна возвращаться к началу этого набора для следующего сравнения. К этому времени мы должны добавить время, необходимое на возвращение соответствующей читающей головки к началу записанных базовых блоков, чтобы машина была в позиции для сравнения следующего хвостового блока. [30]