Представлення чисел в ЕОМ. Формалізоване поняття алгоритму

32-розрядні процесори можуть працювати з оперативною пам’яттю ємністю до 232-1, а адреси можуть записуватися в діапазоні 00000000 – FFFFFFFF. Однак у реальному режимі процесор працює з пам’яттю до 220-1, а адреси потрапляють в діапазон 00000 – FFFFF. Байти пам’яті можуть об’єднуватися в поля як фіксованою, так і змінної довжини. Словом називається поле фіксованої довжини, що складається з 2 байтів, подвійним словом – поле з 4 байтів. Адреси полів бувають парні і непарні, при цьому для парних адрес операції виконуються швидше.

Числа з фіксованою точкою в ЕОМ представляються як цілі двійкові числа, і займаний ними обсяг може становити 1, 2 або 4 байти.

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

x = 10n – \ x \, де n – розрядність числа.

У двійковій системі числення додатковий код виходить шляхом інверсії розрядів, т. Е., Заміною одиниць нулями і навпаки, і збільшенням одиниці до молодшого розряду.

Кількість бітів мантиси визначає точність представлення чисел, кількість бітів машинного порядку визначає діапазон представлення чисел з плаваючою крапкою.

Формалізоване поняття алгоритму

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

У математиці функція називається однозначної, якщо для будь-якого набору аргументів існує закон, за яким визначається єдине значення функції. В якості такого закону може виступати алгоритм; в цьому випадку функція називається обчислюваною.

Рекурсивні функції – це підклас вичіслімих функцій, а алгоритми, що визначають обчислення, називаються супутніми алгоритмами рекурсивних функцій. Спочатку фіксуються базові рекурсивні функції, для яких супутній алгоритм тривіальний, однозначний; потім вводяться три правила – оператори підстановки, рекурсії та мінімізації, за допомогою яких на основі базових функцій виходять більш складні рекурсивні функції.

Базовими функціями і їх супутніми алгоритмами можуть виступати:

1) функція n незалежних змінних, тотожно рівна нулю. Тоді, якщо знаком функції є ?n, то незалежно від кількості аргументів значення функції слід покласти рівним нулю;

2) тотожна функція n незалежних змінних виду ? ni. Тоді, якщо знаком функції є ? ni, то значенням функції слід взяти значення i-го аргументу, вважаючи зліва направо;

3) ?-функція одного незалежного аргументу. Тоді, якщо знаком функції є ?, то значенням функції слід взяти значення, наступне за значенням аргументу.

Посилання на основну публікацію