Задача Aможе бути

Вид материала

Задача

Подобный материал:

• Xtensible Markup Language це розширювана мова розмітки тексту, запропонована W3C, 72.52kb.
• На підставі інноваційного розвитку, 650.39kb.
• Программа курса лекций «Математические методы и модели исследования операций», 27.98kb.
• Т. М. Боровська кандидат технічних наук, доцент І. С. Колесник, 118.17kb.
• Впровадження педагогічних ідей С. Русової в роботу днз, 63.57kb.
• Разновозрастная итоговая проектная задача 1-4 классы, 87.27kb.
• Міністерство внутрішніх справ україни, 408.84kb.
• Склад злочину поняття І значення складу злочину, 796.48kb.
• Про українця, який відмовився бути бідним, та мецената, який не відмовився бути українцем, 78.45kb.
• Розвиток ідей метакомп’ютингу та особливості його використання, 47.18kb.

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


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


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


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

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

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

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

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

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


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

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

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

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


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