Cтраница 4
Для географической привязки вводимых карт могут использоваться опорные точки с точно известными географическими координатами, которые имеются на карте. ГИС функционирует в системе координат реального мира, но воспринимает ввод данных в декартовых координатах дигитайзера, поэтому и нужны опорные точки с их значениями широты и долготы, чтобы проецирование было возможно. Для пересчета координат, как в растровых, так и векторных системах, могут использоваться афинные, полиномиальные и более сложные преобразования, которые получаются в результате решения уравнений, получаемых из математических моделей проекций. [46]
Использование рациональных поверхностей вносит в решение задачи приближения нужную гибкость, ибо в их описании принимают участие свободные числовые параметры. Возможность выбора позволяет заметно влиять на форму искомых поверхностей, а также учитывать предписанные свойства. Важно и то, что рациональные поверхности сохраняют многие из свойств, которыми обладают соответствующие нерациональные ( полиномиальные) поверхности / А то обстоятельство, что рациональные поверхности ко всему еще и проек-тивно-инвариантны, является одним из наиболее привлекательных их свойств, весьма полезных при визуализации. [47]
Наибольшее внимание привлекает класс сложности BQP ( Bounded-error Quantum Polynomial-time), содержащий задачи, решаемые полиномиальными по времени квантовыми машинами Тьюринга с большой надежностью. Класс сложности ВРР ( Bounded-error Probabilistic Polynomial-time) содержит задачи, решаемые полиномиальными по времени классическими вероятностными машинами Тьюринга с большой надежностью. Интерес к классу BQP вызван тем, что в 90 - х годах удалось построить эффективные ( надежные, полиномиальные по времени) квантовые алгоритмы для ряда задач, для которых эффективные ( полиномиальные по времени и надежные) классические алгоритмы неизвестны. Задача факторизации и близкая к ней задача дискретного логарифма имеют важную, но специфическую область применения - создание систем шифрования с открытым ключом. Отметим, что на сегодняшний день пока не найдены широкие области теории и практики вычислений, где квантовые алгоритмы имеют значительное преимущество по сравнению с классическими алгоритмами. Открытым вопросом является построение эффективного квантового алгоритма для NP полных задач или доказательство того, что это невозможно. [48]
Без аксиомы С1 вывод MV-зави-симости из множества одних F-зависимостей был бы невозможен. В качестве упражнения читателю предлагается построить пример, в котором для заданного множества F-зависимостей и MV-зависимостей с помощью аксиомы С2 выводится F-зависимость, не выводимая только из аксиом Fl - F6 ( см. упр. Мы не приводим алгоритмов проверки вхождения для MV-зависимостей или F-и MV-зависимостей, хотя в обоих случаях такие алгоритмы, полиномиальные по времени, существуют. [49]
Сила комбинации этих двух весьма общих алгоритмов - метода эллипсоидов и жадного алгоритма ( см. Вставку 1C) - поистине удивительна. Разумеется, алгоритмы, полученные столь общими методами, оказываются бесполезными на практике; мы даже не отваживаемся оценить время их работы. Но такие полиномиальные алгоритмы, именно в силу своего существования, служат для нас сигналами, что для некоторых задач, по-видимому, имеет смысл искать экономные полиномиальные по времени алгоритмы, которые, конечно, должны в гораздо большей степени использовать специфику конкретной стоящей перед нами задачи. [50]
Наибольшее внимание привлекает класс сложности BQP ( Bounded-error Quantum Polynomial-time), содержащий задачи, решаемые полиномиальными по времени квантовыми машинами Тьюринга с большой надежностью. Класс сложности ВРР ( Bounded-error Probabilistic Polynomial-time) содержит задачи, решаемые полиномиальными по времени классическими вероятностными машинами Тьюринга с большой надежностью. Интерес к классу BQP вызван тем, что в 90 - х годах удалось построить эффективные ( надежные, полиномиальные по времени) квантовые алгоритмы для ряда задач, для которых эффективные ( полиномиальные по времени и надежные) классические алгоритмы неизвестны. Задача факторизации и близкая к ней задача дискретного логарифма имеют важную, но специфическую область применения - создание систем шифрования с открытым ключом. Отметим, что на сегодняшний день пока не найдены широкие области теории и практики вычислений, где квантовые алгоритмы имеют значительное преимущество по сравнению с классическими алгоритмами. Открытым вопросом является построение эффективного квантового алгоритма для NP полных задач или доказательство того, что это невозможно. [51]
Полиномиальные классы состоят из относительно легко разрешимых задач. Экспоненциальные классы содержат трудно разрешимые задачи, решение которых требует почти полного перебора вариантов. Поскольку вычислительные машины полиномиально эквивалентны ( отношение трудоемкости решения задач каждого класса на разных машинах не превышает полином некоторой степени от размерности задач класса), то разделение классов задач по сложности на полиномиальные и экспоненциальные представляет собой машиннонезависимую классификацию. Для отдельных классов дискретных задач полиномиальной сложности удается установить более детальную классификацию и указать степень полинома от размерности, оценивающего вычислительную сложность задач класса. [52]
Результаты по NP-полноте, доказанные в начале 1970 - х годов, показали, что огромное большинство задач комбинаторной оптимизации, возникающих в коммерции, науке и технике, практически невыполнимы, если не верно P NP; никакие методы их решения не могут полностью избежать комбинаторных взрывов. Один из возможных подходов исходит из того, что достаточно хороши решения, близкие к оптимальным: коммивояжер, вероятно, будет удовлетворен маршрутом, на несколько процентов длиннее оптимального. Следуя такому подходу, исследователи начали искать полиномиальные по времени алгоритмы, которые гарантируют почти оптимальные решения NP-полных комбинаторных задач. [53]