Математические основы квантовой информатики (стр. 9 )

21. Неархимедова геометрия – совокупность геометрических предложений, вытекающих из групп аксиом: инцидентности, порядка, конгруэнтности и параллельности системы аксиоматики Гильберта евклидовой геометрии, и не связанных с аксиомами непрерывности (с аксиомами Архимеда и полноты). По Гильберту, основными (неопределяемыми) понятиями являются объекты: точки, прямые и плоскости и отношения между ними, выражаемые словами: "принадлежит", "между", "конгруэнтен". Природа основных объектов и отношений между ними может быть какой угодно, лишь бы эти объекты и отношения удовлетворяли указанным аксиомам.

В узком смысле неархимедова геометрия описывает геометрические свойства прямой, на которой не верна аксиома Архимеда (неархимедова прямая). Для исследования геометрических соотношений в неархимедовой геометрии вводится исчисление отрезков - неархимедова числовая система, рассматриваемая как специальная комплексная числовая система. Определяются понятия отрезка, отношения отрезков, сложение и умножение отрезков. В частности, вводится дезаргова числовая система (Жерар Дезарг – французский геометр 17 века) - неархимедова система, в которой умножение отрезков некоммутативно. С помощью этих числовых систем в неархимедовой геометрии строится теория подобия фигур, теория площадей и т. д. Неархимедова геометрия имеет замечательные свойства. Например, в отличие от евклидовой геометрии, p-адический шар состоит из конечного числа шаров меньшего радиуса, при этом нет пустот между меньшими шарами.

В 1900 г. систематически развил и изложил неархимедову геометрию ученик Д. Гильберта М. Ден (1878-1952). 

См. также: Аксиома Архимеда, p-адические числа.

22. Норма вектора – в евклидовом пространстве то же, что и длина (или модуль) вектора. В евклидовом n-мерном пространстве длина вектора рассчитывается как корень из скалярного произведения этого вектора на себя.

В общем случае норма обобщает понятие длины вектора или абсолютного значения числа. В произвольном векторном (линейном) пространстве L над полем вещественных или комплексных чисел нормой вектора x (или числа x) называется число , удовлетворяющее следующим четырём аксиомам:

1.  - вещественное число.

2.  = ×- норма от произведения равна произведению норм.

3.  = 0.

4.  ≤ + - правило треугольника.

Вектор с единичной нормой ( = 1) называется нормальным или нормированным. Любой ненулевой вектор x можно нормировать, если разделить его на свою норму.

Каждое рациональное число можно единственным образом представить в виде несократимой дроби:

,

где p – простое число;

γ – некоторое целое число;

m – целое число;

n – натуральное число:

p, m, n – взаимно простые (целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1).

Тогда ‖x‖p = p-γ – p-адическая норма, в чём легко убедиться путём простой проверки на выполнимость указанным выше аксиомам.

В кантовой механике норма вектора состояния (модуль волновой функции) определяет вероятность обнаружить систему в некотором состоянии. Поэтому норма вектора состояния изолированной системы должна сохраняться. Соответствующие операторы эволюции такой системы называются унитарными, а преобразование – унитарным.

См. также: Унитарное преобразование, p-адические числа, Волновая функция.

Литература

Теория чисел. –М.: Просвещение, 1966.

-Режим доступа: http:///d. php? id=10256

23. О-нотация - система обозначений для оценивания трудоёмкости алгоритмов, позволяющая учитывать в функции f(n) лишь наиболее значимые элементы. Например, в функции f(n) = 5n2 + 2n – 7 при достаточно больших n первое слагаемое значительно превосходит остальные слагаемые, и скорость роста функции определяется первым слагаемым. Оценка поведения функции записывается в виде: O(n2). Таким образом, O-нотация позволяет оценить характер изменения функции с ростом n.

Все основные функции делятся на ряд групп в зависимости от скорости их роста (в порядке возрастания скорости):

- постоянные функции, которые с ростом n не меняются, О(1);

- функции с логарифмической скоростью роста О(log2n);

- функции с линейной скоростью роста О(n);

- функции с линейно–логарифмической скоростью роста О(n*log2n);

- функции с квадратичной скоростью роста О(n2);

- функции со степенной скоростью роста  О(na) при а>2;

- функции с показательной или экспоненциальной скоростью роста  О(2n);

- функции с факториальной степенью роста  О(n!).

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

При малых n “лучшие” алгоритмы могут вести себя хуже, чем “плохие”. Например, показательная функция растёт медленнее, чем логарифмическая, линейная или факториальная.

Алгоритмы класса О(2n) и О(n!) следует использовать с большой осторожностью, учитывая катастрофический рост их трудоемкости уже при n >100. Например, если число базовых операций определяется соотношением 2n, то при n = 100 это число будет примерно равно 1030 , и если одна базовая операция выполняется за 1 микросекунду, то это потребует около 1024 секунд, т. е. 1016 лет. Задачи с такой трудоемкостью часто встречаются на практике, и их точное решение невозможно даже на сверхбыстрых суперкомпьютерах!

Если в программе используется несколько алгоритмов, трудоёмкость программы в целом оценивается следующим образом. При последовательном выполнении алгоритмов с оценками O(f1), O(f2), …, O(fk) общая трудоёмкость определяется трудоёмкостью алгоритма с максимальным значением:
O (программы) = max (O(f1), O(f2), . . ., O(fk))
При вложенном выполнении общая трудоёмкость есть произведение оценок вложенных друг в друга алгоритмов: O(программы) = O(f1)∙O(f2)∙…O(fk).

См. также Алгоритм.

24. Оператор - это математический символ, означающий правило, по которому одному вектору гильбертова пространства сопоставляется другой вектор . Любое действие над вектором можно записать в виде оператора. Понятие оператора является обобщением понятия функции. Например, в случае функции сопоставляются точки на числовой оси . Оператор называется линейным, если выполняются следующие два условия:

;

,

где α – постоянный множитель.

Действие оператора на дискретную функцию можно представить в виде:

. Совокупность элементов называется матрицей оператора . Если функция непрерывна, то сумма превращается в несобственный интеграл:

,