Зубенко, Омельчук - Програмування. Поглиблений курс
.pdf
Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ
Зовнішня пам'ять містить також пристрої введення-виведення, які забезпечують обмін інформацією між суб'єктами інформаційної час- тини. Це можуть бути різного роду термінали, клавіатура, миша, при- строї друку тощо.
Центральний процесор. Зупинимось детальніше на структурі ЦП, загальну схему якого зображено на рис. 2.3.
Безпосередньо команди виконує арифметико-логічний пристрій (АЛП). Порядок, за яким виконуються команди, задає пристрій керу- вання (ПК). Важлива роль відводиться регістру – лічильнику команд – PC (англ. – Program Counter), в якому формується адреса наступної для виконання команди.
Алгоритм виконання машинної програми наведено на рис. 2.4. Він до- сить схематичний – деякі операції можуть виконуватися паралельно тощо.
Регістр стану процесора – PS (англ. – processor status) містить ін-
формацію про поточний стан процесора й деякі побічні результати виконання останньої команди. Ця інформація використовується для керування роботою процесора (може впливати на вибір наступної команди тощо). ЦП має також власну робочу пам'ять у вигляді зага- льних регістрів R0, R1, …, Rn і регістр-покажчик системного стеку SP (англ. – Stack Pointer), в якому зберігається адреса вершини стеку. Системний стек – це службова ділянка ОП, що використовується для підтримки процесу виконання програм.
Загальна схема ЦП:
Регістр стану процесора
PS
Регістр R0
РегістрR1
АЛП
.
.
.
Пристрій
керування
Лічильник команд PC
Покажчик cистемного
cтеку SP
Рис. 2.3
151
ПРОГРАМУВАННЯ
Алгоритм виконання машинної програми подає така схема:
Установка в РС адреси першої команди
програми
Вибір із програми команди за адресою
(РС) та її декодування
стоп? +
_
Виконання команди
Формування нового значення РС
Рис. 2.4
2.3.2. СТРУКТУРА Й ФУНКЦІЇ ОПЕРАЦІЙНИХ СИСТЕМ
Процесор, пам'ять і зовнішні пристрої є основними ресурсами комп'ютера. Будь-яка програма потребує для підготовки й виконання певних ресурсів. Машинну програму в стадії виконання назвемо про- цесом. Керування ресурсами, зокрема планування й розподіл їх між процесами, здійснює операційна система.
Операційна система (ОС)– це комплекс машинних програм, призначений для автоматизованого керування ресурсами комп'ютера й забезпечення зв'язку між ним і користувачем.
152
Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ
Окрім автоматизованого керування, ОС надає користувачу засоби для оперативного керування комп'ютером, розробки програм, вве- дення-виведення даних тощо. Структуру ОС можна зобразити так:
|
|
|
Структура ОС |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Системи |
|
|
Керування |
|
Командний |
|
Утиліти |
|
програмування |
|
|
ресурсами |
|
процесор |
|
|
|
|
|
|
(ядро ОС) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Командний процесор надає засоби для оперативного керування робо- тою комп'ютера і є спеціальним мовним інтерпретатором, що реалізує спеціальні команди, за допомогою яких можна змінювати параметри ОС, керувати зовнішніми пристроями, обробляти файли, розробляти програ- ми, запускати системні й прикладні програми на виконання тощо.
Системи програмування призначені для автоматизації процесу програмування й виконання програм. Вони реалізують мови про- грамування і складаються з текстових редакторів, трансляторів (компіляторів та інтерпретаторів), компонувальників, завантажни- ків програм тощо.
Утиліти – обслуговуючі програми, що здійснюють введення- виведення й реорганізацію даних. Типовими з них є програми роботи з файлами, сортування й архівації даних, фільтри, антивірусні про- грами тощо.
Розглянемо детальніше процес створення й виконання програм:
|
|
|
|
|
|
Заванта- |
Створення |
|
Препроце- |
|
Компону- |
|
|
одиниць |
|
сування й |
|
вання |
|
ження |
трансляції |
|
трансляція |
|
об'єктних |
|
програми |
програми |
|
коду |
|
модулів |
|
в ОП і |
|
|
|
|
|
|
виконання |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Програми складаються з однієї чи кількох одиниць трансляції. Одиниця трансляції – це програма чи її частина у вигляді текстових файлів, що допускає автономну трансляцію. Спочатку за допомогою текстового редактора формуються одиниці трансляції програми. По- тім до них послідовно застосовуються препроцесор (за необхідності) і транслятор мови програмування.
Якщо процесором є інтерпретатор, то на вхід йому передаються вхідні дані, а трансляція (інтерпретація) полягає в побудові машинної
153
ПРОГРАМУВАННЯ
програми, завантаженні її (або її фрагментів) у ОП і виконанні на за- даних вхідних даних.
Якщо ж процесором є компілятор, то в результаті компіляції на ви- ході спочатку буде отримано об'єктний (бінарний) код програми, який подається на вхід редактора зв'язків, або компонувальника, який із цьо-
го об'єктного коду та об'єктних кодів стандартних функцій компонує образ задачі – машинну програму з відносними (віртуальними) адреса- ми, що розміщується попередньо в зовнішній пам'яті. На відміну від ін- терпретатора компілятор не завантажує й не виконує програму.
Усі компілятори мають бібліотеки стандартних функцій, призначе- ні для виконання найважливіших загальних задач. Під час компіляції компілятор зазначає виклики стандартних функцій, потім програма- компонувальник пов'язує об'єктний код програми з об'єктними кода- ми бібліотечних функцій.
Щоб виконати образ задачі, його необхідно завантажити в ОП і пе- редати керування на першу команду. Під час завантаження віртуа- льні адреси образу задачі замінюються абсолютними адресами ОП.
Кожна з фаз створення програми ініціалізується певною командою командного процесора ОС.
Уся пам'ять, що надається машинній програмі для її виконання, розподіляється на чотири логічні області (рис. 2.5). Перша містить машинний код програми; у другій зберігаються глобальні дані; у стеку
– автоматичні дані й параметри виклику функцій, адреси повернення з виклику функцій тощо; у купі – решта програмних даних; у службо- вій частині ОП – ядро ОС та інша службова інформація, необхідна для керування процесами.
Стек
Купа
Глобальні дані
Код програми
Службова частина ОП
Рис. 2.5
154
Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ
У сучасних ОС системи програмування забезпечуються інтегрова- ним графічним інтерфейсом і називаються інтегрованим середови-
щем розробки.
2.3.3. МАШИННІ ТИПИ ДАНИХ
Машинні типи даних становлять основу базових типів мов програ- мування. Це дані, якими безпосередньо оперують машинні команди. До них належать: беззнакові цілі, цілі, дійсні, літери, адреси (у тому числі й адреси машинних команд). Для подання даних машинних ти- пів зазвичай використовують двійкову позиційну систему числення.
Позиційні системи числення. Cистеми числення (СЧ) – це де-
скриптологічні системи, призначені для подання чисел. В інформати- ці застосовують різні системи числення. Наприклад, у теорії винятко- во важлива роль належить індуктивному визначенню натуральних чисел. Однак для організації конкретних обчислень перевагу надають зображенню чисел у позиційних системах числення. Кожна з таких систем використовує певну основу – довільне натуральне p ≥ 2 . Сис-
тему з основою p будемо позначати СЧ p . Вона є узагальненням зви- чайної десяткової системи. Алфавіт СЧ p складають p літер-цифр
Σ |
p |
= c |
,c ,...,c |
p −1} |
і допоміжні літери |
{".","+ ","− "}. У випадку p >10 |
|
{ 0 |
1 |
|
|
перші 10 цифр є звичайними десятковими від 0 до 9, для решти ви- бираються свої фіксовані імена. Наприклад, для запису чисел з осно- вою 16 шістнадцяткові цифри від 10 до 15 позначаються латинськи- ми літерами A, B, C, D, E та F.
Ціле число у СЧ p має вигляд слова в алфавіті Σp . Далі під цілим та
іншими числами будемо розуміти залежно від контексту або їхній за- пис, або значення. Нехай n = akak −1...a0 – ціле число. Тоді ai Σp ,
1 ≤ i ≤ k , називається i -м розрядом числа n , a0 – молодшою, а ak –
старшою його цифрами. Щоб підкреслити приналежність числа до даної системи, будемо індексувати число її основою p. Наприклад,
пишемо 2510 та 2516 , що означає відповідно число 25 у десятковій і
шістнадцятковій системах. Відсутність знака перед числом, або якщо йому передує знак " +", означає додатне число. Знак "-" перед числом є ознакою від'ємного числа.
155
ПРОГРАМУВАННЯ
|
|
Значенням |
числа |
np |
вважається десяткова сума полінома |
|
|
|
k |
|
, де ci |
та p |
трактуються як відповідні десяткові чис- |
np = ∑ ci pi |
|
|||||
|
|
i =0 |
10 |
|
|
|
ла. Продовжуючи попередній приклад, отримаємо:
2510 = 5 ×100 + 2×101 = 2510 , 2516 = 5 ×160 + 2×161 = 3710 .
Раціональні числа мають дві форми подання – з фіксованою й рухо-
мою точками. Число з фіксованою точкою (ФТ-число) має вигляд слова в алфавіті цифр, усередині якого (або на початку чи в кінці) розміщено
точку. Наприклад, 0.2510 , .2516 3.142810 , 101.12 , 1111.2 – ФТ-числа.
Нехай |
x = akak −1...a0 .b−1b−2...b−l – довільне ФТ-число. Тоді слово |
|
akak −1...a0 |
називається цілою, а .b−1b−2...b−l |
– дробовою його частиною. |
Значенням числа x = akak −1...a0. b−1b−2...b−l |
є десяткова сума цілої й |
|
дробової його частин. Значенням дробової частини числа x є сума
|
−l |
|
p−i |
, де b |
та p трактуються як десяткові числа. Наприклад, |
∑ b |
−i |
||||
|
|
|
i |
|
|
i =−1 |
|
10 |
|
|
|
0.2510 = 2×10−1 + 5 ×10−2 = 0.2 + 0.05 = 0.2510 , 0.2516 = 2×16−1 + 5 ×16−2 = 0.125 + 0.01953125 = 0.1445312510 ,
101.12 =101+.12 =1×20 + 0 ×21 +1×22 +1×2−1 = 5 + 0.5 = 5.510 .
Як і цілим, дробовим числам може передувати знак. Число з рухо- мою точкою (РТ-число) складається з мантиси m і порядку. Манти- сою може бути ціле число або число з фіксованою точкою. Порядок має вигляд e ±n , де літера e – формальна ознака порядку, а n – на- туральне число. Таким чином, РТ-число має вигляд m e ±n . Напри-
клад, 1e + 22 , −1.25e + 216 , 3.1428e −10010 – РТ-числа.
Значенням РТ-числа m e ±n є значення мантиси, помножене на масштабний множник, який задається порядком. Якщо мантиса ціла, то вона перетворюється до еквівалентного ФТ-числа, а масштабний множник – це степінь основи із заданим порядком. Наприклад:
1e +1002 =1.0 ×24 =16.0 ,
−0.25e + 216 = −0.14453125 ×162 = −37.0 ,
−3.1428e − 50 = −0.00...031428 .
10 123
49
156
Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ
Потрібно сказати кілька слів про прагматику чисел і позиційних систем числення. З одного боку, числа служать кількісною мірою множин і окремих об'єктів, їх можна порівнювати й виконувати над ними арифметичні дії, які моделюють реальні й дуже важливі кількі- сні співвідношення між предметами та їхніми сукупностями. Не ви- падково більшість моделей, з якими мають справу природничі (а на- разі все частіше й гуманітарні) науки, є числовими або зводяться до числових. З іншого боку, як було зазначено у вступі, числа в позицій- них системах виявились зручними для механізації та автоматизації основних арифметичних операцій і відношень між ними.
Арифметичні операції додавання, віднімання, множення й ділення в позиційній системі з основою p виконуються за тими самими пра-
вилами, що й у десятковій системі.
Розглянемо як приклад додавання двох чисел з основою p
np = akak −1...a0 та mp = blbl −1...b0 .
Нехай
k > l , si = ai +bi , 0 ≤ i ≤ l , si = ai , si′+1 = (si′ < p → si +1|si +1 +1), l +1 ≤ i ≤ k , t = (sk′ < p → k |k +1).st′ = (t = k → sk′ |1).
Тоді
np + mp = ∑k ai pi + i =0
l
= ∑ ((si < p → si |si −
i =0
l |
l |
|
k |
s pi |
= |
|
∑ b pi = |
∑ s pi + |
∑ |
||||
i |
i =0 |
i |
i =l +1 |
i |
|
|
i =0 |
|
|
|
|||
p)pi + pi +1) + |
k |
|
= |
t |
|
|
∑ s pi |
∑ s′pi . |
|||||
|
|
i =l +1 |
i |
|
i =0 |
i |
|
|
|
|
|
||
Відоме правило додавання у стовпчик базується саме на цих співвід-
ношеннях і реалізує пошук цифр si′ |
|
|
p + m |
p . |
Додамо, напри- |
||||
суми n |
|||||||||
клад, двійкові числа 100102 та 111102 і шістнадцяткові F 5 та 66 : |
|||||||||
|
а) + 100102 |
б) + F 5 |
|
|
|
|
|
|
|
|
111102 |
66 |
|
|
|
|
|
|
|
|
100000 |
15B |
′ |
|
|
|
|
|
|
|
У другому |
прикладі k = l =1, |
|
= B(=11) , |
s1 = F + 6 = 21, |
||||
′ |
s0 = s0 |
|
|||||||
= 21−16 = 5, |
|
′ |
=1. |
|
|
|
|||
s1 |
t = k +1 = 2 та k < t . Отже, s2 |
|
|
|
|||||
Аналогічно додаванню обґрунтовуються правила для решти ариф- метичних операцій.
Переведення чисел з однієї системи в іншу. У маніпуляціях із машинними даними важливу роль відіграє перекодування даних, тобто перехід від однієї СЧp до іншої СЧq так, щоб зберігалась інформація.
157
ПРОГРАМУВАННЯ
Такі перекодування отримали назву переведення чисел з однієї системи в іншу. Будемо їх позначати (p) → (q ), де p,q – основи відповідних СЧ.
Для перетворень вигляду (p) → (10) достатньо скористатися ви- значенням значення числа з основою p і обчислити відповідну суму.
Для довільного переведення (p) → (q ) теж скористаємося десятко- вою системою. Нехай np = akak −1...a0 – довільне ціле в системі СЧ p і
необхідно знайти його еквівалент nq |
= blbl −1...b0 у системі СЧq . Зна- |
|||||||||||||
|
|
|
|
|
k |
|
|
|
|
|
|
l |
|
|
|
|
|
= |
∑ a |
pi |
|
|
|
= |
|
∑ b qi |
у результаті мають збігатися. |
||
чення n |
p |
|
та n |
q |
||||||||||
|
|
|
i |
|
|
|
|
|
i |
|
|
|||
|
|
|
|
i =0 |
10 |
|
|
|
|
i =0 |
10 |
|||
Покладемо u = n |
p . З урахуванням того, що u |
та q відомі, фактично |
||||||||||||
необхідно розв'язати рівняння |
|
|
|
|
|
|
|
|
||||||
|
|
u = b ql +... +b q1 |
+b |
= (b ql −1 +... +b )q +b |
|
(*) |
|
|||||||
відносно bi . |
|
|
l |
|
1 |
0 |
|
l |
1 |
0 |
|
|
||
|
|
|
що 0 ≤b0 <q , то з визначень цілочислового ді- |
|||||||||||
Якщо взяти до уваги, |
||||||||||||||
лення |
( ÷ ) |
і |
операції |
взяття |
|
залишку |
(%) |
|
випливає, що |
|||||
(b ql −1 |
+... +b ) = u ÷q , b |
= u%q . |
Аналогічно |
знаходять |
b . Нехай |
|||||||||
l |
1 |
|
|
|
0 |
|
|
|
|
|
|
|
|
1 |
u =u q . Тоді u |
=(b ql −2 |
+...+b )q +b = (u q)q +u %q |
та |
|
b =u %q . Про- |
|||||||||
1 |
|
1 |
l |
|
2 |
1 |
1 |
1 |
|
|
1 |
1 |
||
цес пошуку bi |
буде продовжуватися, доки ui не перетвориться на 0. |
|||||||||||||
Таким чином, можна сформулювати правило для переведення ці-
лих (p)→ (q ):
Щоб перевести довільне ціле системи з основою p у систему з основою q , необхідно знайти частку й залишок від ділення даного числа на основу q . Залишок є молодшою цифрою шуканого числа.
Повторювати дію для нових часток, дописуючи ліворуч черговий за- лишок до слова з уже знайдених залишків, і припинити, коли остан- ня частка стане 0.
Що можна сказати про довжину нового числа nq = blbl −1...b0 , тобто l +1? Позначимо m цифру q −1 . Найменшим і найбільшим числами з
(l +1)-розрядами у СЧ |
q |
є відповідно ql і число r = mm...m зі значен- |
|
14243 |
|
|
|
l +1 |
158
Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ
|
|
|
|
|
l |
|
|
|
|
l |
|
|
|
|
|
|
|||||
ням r |
= |
∑ mqi |
|
= m |
|
∑ qi |
|
. За |
формулою суми геометричної |
||||||||||||
|
|
|
|
i =0 |
10 |
|
i =0 |
10 |
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
ql +1 −1 |
|
= ql +1 −1. Тоді ql ≤ n |
|
< ql +! . Після лога- |
||||
прогресії маємо |
r |
= |
m |
|
|
|
|
q |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
q −1 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
рифмування |
цієї |
|
|
нерівності |
отримаємо |
|
l ≤ logq n |
q < l +1, |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
l ≤ logq nq < l +1 та l = logq nq . Отже, кількість цифр у числі nq до- |
|||||||||||||||||||||
рівнює |
|
|
|
|
+ 1. |
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
logq nq |
|
|
|
|
|
|
|
|
|
|
|||||||||||
Наведемо кілька прикладів переведень чисел з однієї системи в іншу. Приклад 2.5. Переведемо числа 2510 та A716 у двійкову систему.
Після |
переведення ці числа матимуть |
log |
2 |
25 + 1 |
= 5 та |
|||
|
|
|
|
|
|
|
|
|
log |
2 |
167 + 1 |
= 8 розрядів. Відповідні процеси |
переведення відобра- |
||||
|
|
|
|
|
|
|
|
|
жено в стовпчиках таблиці. У лівому стовпчику розташовані частки
(ui ), у правому – |
|
залишки-цифри |
|
(bi ). У результаті маємо: |
|||||
2510 = 110012 та A716 = 101001112 : |
|
|
|
|
|
||||
|
|
|
|
|
|
||||
|
A716 = 167( = u0 ) |
1 |
(= b0 ) |
|
|||||
|
83 |
(= u1 = u /2) |
1 |
(= b1) |
|
||||
|
(= u2 = u1 /2) |
|
|
(= b2 ) |
|
||||
|
41 |
1 |
|||||||
|
|
(= u3 = u2 /2) |
|
|
(= b3 ) |
|
|||
|
20 |
0 |
|
||||||
|
(= u4 = u3 /2) |
|
|
(= b4 ) |
|
||||
|
10 |
0 |
|||||||
|
(= u5 = u4 /2) |
|
|
(= b5 ) |
|
||||
|
5 |
1 |
|||||||
|
(= u6 = u5 /2) |
|
|
(= b6 ) |
|
||||
|
2 |
0 |
|||||||
|
(= u7 = u6 /2) |
|
|
(= b7 ) |
|
||||
|
1 |
1 |
|||||||
|
(= u8 = u7 /2) |
|
|
|
|
|
|||
|
0 |
|
|
|
|
|
|||
|
2510 =25( = u0 ) |
|
1 |
(= b0 ) |
|
||||
|
12 |
(= u1 = u /2) |
|
0 |
(= b1) |
|
|||
|
(= u2 |
= u1 /2) |
|
0(= b2 ) |
|
||||
|
6 |
|
|||||||
|
(= u3 |
= u2 /2) |
|
(= b3 ) |
|
||||
|
3 |
|
1 |
||||||
|
|
(= u4 |
= u3 /2) |
|
|
(= b4 ) |
|
||
|
1 |
|
1 |
|
|||||
|
(= u5 |
= u4 /2) |
|
|
|
|
|
||
|
0 |
|
|
|
|
|
|||
■ |
|
|
|
|
|
|
|
|
|
159
ПРОГРАМУВАННЯ
Розглянемо правило переведення дробових частин раціональних чи- сел. Нехай yp = .b−1b−2...b−l – довільний дріб у системі СЧ p і необхідно знайти його еквівалент .b−1b−2...b−l … у системі СЧq . На жаль, точний
еквівалент дробу в новій системі може мати зліченну кількість розрядів після крапки, тобто виявитися періодичним. Наприклад,
.13 = (.333...)10 . Тому в загальному випадку може йтися лише про на-
ближення до еквівалента числа. Тоді або обмежуються s першими розрядами еквівалента для певного s , або роблять те саме, але з округ-
ленням. Покладемо u = yp . Знову необхідно розв'язати рівняння відно-
сно |
b |
, але вже інше: |
u = b q−1 |
+... +b |
q−s +... (**). Нехай x |
та {x} |
|
−i |
|
−1 |
−s |
|
|
означають цілу й дробову частини дійсного числа. Помножимо обидві
частини (**) |
на q . Тоді uq = b |
−1 |
+b |
q−1 +... +b |
q−s +1 |
+... та b |
= uq , |
|||||||
|
|
|
q−l +1 +... = {uq}. |
|
−2 |
−s |
|
−1 |
|
|||||
b q−1 +... +b |
−l |
Покладемо u |
= {uq } . |
Аналогічно знахо- |
||||||||||
−2 |
|
|
|
|
= {u q} |
|
|
1 |
|
|
|
|
||
димо b |
= u q |
та u |
2 |
і т. д., доки u |
не набуде значення 0 або |
|||||||||
−2 |
|
1 |
|
|
|
1 |
|
|
i |
|
|
|
|
|
будуть отримані перші s |
розрядів. Таким чином, можна сформулюва- |
|||||||||||||
ти правило для переведення правильних дробів (p)→ (q ): |
|
|||||||||||||
Щоб перевести довільний дріб .b−1b−2...b−l |
системи з основою p у си- |
|||||||||||||
стему з основою q , необхідно помножити дане число на нову основу q
і взяти цілу й дробову частини отриманого добутку. Ціла частина є старшим розрядом шуканого дробу. Повторювати процес для дробової частини добутку, додаючи праворуч кожного разу нову цілу частину до слова з раніше знайдених цілих частин, і припинити, коли чергова дробова частина стане 0 або будуть отримані перші s розрядів.
Приклад 2.6. Переведемо число .2510 у двійкову та п'ятіркову сис- теми, а число .A716 – у двійкову. У наближеннях треба взяти три роз- ряди після коми. Спочатку знайдемо значення дробів: .25 = 0.25 ,
.A716 =10 ×16−1 + 7 ×16−2 = 0.625 + 0.02734375 = 0.65234375 . Відпові-
дні процеси переведення відображені у стовпчиках таблиці, де в лі- вих стовпчиках розташовані дробові частини відповідних добутків (ui ), а в правих – їхні цілі частини-цифри (bi ). У результаті маємо
.2510 ≈ .1115 , .2510 = .012 і .A716 = .010011112 .
160