Cтраница 1
К алгоритму трассировки лучей. [1] |
Неадаптивные алгоритмы не изменяют своих действий в зависимости от истории поведения распределенной системы. [2]
Определение 11.1 Неадаптивный алгоритм сортировки - это алгоритм, в котором последовательность выполняемых операций зависит только от числа входных данных, а не от значений ключей. [3]
Простейшей моделью для изучения неадаптивных алгоритмов сортировки является абстрактная машина, которая способна осуществлять доступ к данным только с помощью операций сравнения-обмена. Сеть сортировки построена из атомарных модулей сравнения-обмена ( compare-exchange modules) или компараторов ( comparators), которые соединены между собой линиями связи таким образом, что становится возможным выполнение полной сортировки общего вида. [4]
Лишь немногие из алгоритмов, которые мы успели обсудить в главах 6 - 10, являются неадаптивными алгоритмами - все они используют операцию operator либо проверяют ключи каким-то другим способом, после чего выполняют действия в зависимости от значений ключей. Исключением является пузырьковая сортировка ( см. раздел 6.4), в условиях которой используются только операции сравнения-обмена. Версия Пратта сортировки методом Шелла ( см. раздел 6.6) служит еще одним примером неадаптивного метода сортировки. [5]