Модель обчислення

Алгоритми, які будуть далі наводитися, будуть створюватися незалежно від конкретної машини, компілятора, операційної системи чи мови програмування. Програму повинна розуміти машина, а алгоритм повинна розуміти людина. Тому при написанні алгоритмів деталі на низькому рівні будуть опускатися, оскільки їх обробка є роботою програмістів, які реалізовують алгоритм.

Модель обчислення визначає набір допустимих елементарних операцій та вартість цих операцій. Для кожної елементарної операції призначимо фіксовану вартість, яка не буде однаковою для всіх елементарних операцій.

Модель дійсної машини з довільним доступом (дійсна RAM – Random Access Machine) в кожній комірці пам’яті може зберігати єдине дійсне число та характеризується наступними елементарними операціями, що мають одиничну вартість:

1. Арифметичні операції: +, -, *, /.

2. Операції порівняння двох дійсних чисел: <, <=, =, >=, >.

3. Непряма адресація пам’яті лише з цілочисельними адресами.

При необхідності будуть використовуватися логічні, алгебраїчні та тригонометричні операції.

Дійсна RAM має нескінченну пам’ять, її команди виконуються послідовно (паралелізм не допускається). Кожна команда є елементарною операцією, яка виконується над двома значеннями, що знаходяться в пам’яті машини.

Означення. Задача A може бути перетворена в задачу B (задача А зводиться до задачі В), якщо:

1. Вхідні дані задачи А перетворюються у вхідні дані задачі В;

2. Розв’язується задача В;

3. Результат розв’язку задачі В перетворюється у правильний розв’язок задачі А.

Якщо кроки 1 та 3 можна виконати за час O(r(N)), де N – розмір задачі A, то кажуть, що задача А є r(N) звідною до В і позначають так: . Звідність не є симетричним відношенням. Якщо задачі А та В взаємно перетворюємі, то вони називаються еквівалентними.