§5.2. Бітові обчислення.

Очевидно, що модель програм, які не розгалужуються заснована на рівномірній ваговій функції. Ця вага придатна коли всі обчислювані величини мають “розумний“ розмір. Існує проста модифікація моделі програм, які не розгалужуються, котра відповідає логарифмічній ваговій функції. Ця модель, яка називається бітовим обчисленням, по суті є тією ж програмою, яка не розгалужується, але в ній

1). всі змінні приймають значення 0 або1, тобто це біти,

2). використовуються логічні операції замість арифметичних (and позначається через , or – через , exclusive or – через , not – через ).

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

При бітових обчисленнях порядок величин позначається через . Бітова модель корисна, коли мова йде про основні операції, такі, як арифметичні, котрі є початковими в інших моделях. Наприклад, для моделі програм, які не розгалужуються множення двох n-розрядних двійкових цілих чисел можна здійснити за кроків, тоді як для бітової моделі найкращий відомий результат – це кроків.

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

Приклад 5.2. Нехай маємо програму для додавання дворозрядних чисел . Вихідні змінні – це такі числа , що . Програма, яка не розгалужується

обчислює

,

,

.

Показано, що додавання двох n-розрядних чисел виконується за кроків.

§5.3. Операції з двійковими векторами.

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

Проте, у тих не багатьох алгоритмах, де застосовується модель з двійковими векторами ,довжина векторів буде значно більшою від числа бітів, потрібних для подання задачі. Величина більшості цілих чисел, що містяться в даному алгоритмі, буде такого ж порядку, що й розмір задачі. Наприклад, розв’язуючи задачу вибору шляху в графі із 100 вершинами можна було б для подання наявності або відсутності шляху із даної вершини v в кожну з вершин використати двійкові вектори довжини 100, а саме і-ту позицію у векторі для вершини v займає 1 тоді й тільки тоді, коли існує шлях із v в . В тій же задачі можна також використати цілі числа для обрахунку й індексації, наприклад, і вони, ймовірно, мали б розмір числа 100. таким чином, для цілих чисел було б потрібно 7 бітів, тоді як для векторів –100 бітів.

Хоч це порівняння й кидає деяку тінь на обчислення з двійковими векторами, більшість обчислювальних машин виконують логічні операції на двійкових векторах, які утворюють повне машинне слово, за одну команду. Тому двійкові вектори довжини 100 можна було б обробляти за три або чотири кроки (замість одного для чисел). Проте на результати про часову й ємнісну складність алгоритмів при застосуванні моделі з двійковими векторами, ми повинні дивитися cum grano salis (з крупинкою солі, в переносному розумінні – з іронією), оскільки розмір задачі, при якому модель становиться нереалістичною, у цьому випадку набагато менший, ніж у випадку моделей РАМ й алгоритмів, які не розгалужуються. Порядок величин при застосуванні моделі з двійковими векторами позначають через .