1

1. ЛІНІЙНІ ПРОГРАМИ

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

Передусім треба пам'ятати, що самі ЕОМ з'явилися на світ саме завдяки необхідності швидкого проведення обчислень.

Спроби створити механічну обчислювальну машину здійснювались ще в середні віки. Проект однієї з таких машин належить Леонардо да Вінчи (1452-1519).

Перша рахункова машина, про яку збереглися відомості, була побудована в 1623 р. німцем В.Шикардом. У 1642 р. французький вчений Б.Паскаль сконструював механічний обчислювач, що дозволяє складати і віднімати числа. У 1673 р. німецький вчений М.Лейбніц (1646-1716) розробив рахунковий пристрій - арифмометр, який виконував не тільки складання і віднімання, але й множення і ділення. М.Лейбніц говорив: "... негідно досконалості людської, подібно рабам, витрачати години на обчислення". Введенням в практику двійкової арифметики вчений заклав основу, на якій покояться всі кити сучасної обчислювальної техніки.

"Якби мені довелося вибирати в анналах історії наук святого - заступника кібернетики, то я вибрав би Лейбніца" - так оцінив заслуги німецького вченого основоположник кібернетики Норберт Вінер.

Лейбніц запропонував також арифметизацию логіки. Однак центральною фігурою "алгебраїчного етапу" логіки був англійський вчений Дж.Буль (1815-1864). Він створив свою алгебру - алгебру Буля - яка оперує тільки двома поняттями: Істинно і Хибно.

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

Уперше склад і призначення функціональних засобів автоматичної обчислювальної машини визначив в 1834 р. англійський математик і економіст Ч.Беббідж (1792-1871) в своєму нездійсненому проекті аналітичної машини. Велику допомогу Беббіджу надала його учениця Ада Августа Лавлейс - дочка відомого англійського поета Байрона. Леди Лавлейс вважається першою в історії програмісткою. Вона заклала основи теоретичного програмування, написавши перший підручник з цього предмета. Їй належить винахід оператора умовного переходу, саме вона ввела поняття робочої клітинки та циклу.

Перша релейна обчислювальна машина Z3 побудована Конрадом Цузе в 1940 р. в Німеччині. Перша електронно-обчислювальна машина на радіолампах ENIAC, винайдена в 1946 р. в США під керівництвом Д.Маучлі і Д.Еккерта.

Пройшло ще декілька років, поки не склалися основні принципи побудови ЕОМ - архітектура сучасних ЕОМ. Ці принципи були обгрунтовані видатним математиком Дж. фон Нейманом (1903-1957) в 1946г. Перша ЕОМ, заснована на цих принципах, - EDSAC була створена в Англії в 1949 р. М.Уїлксом.

Перша ЕОМ на території колишнього СРСР (МЕСМ) була створена в 1950 р. у Києві за проектом С.А.Лебедєва.

Саме слово "обчислення" було настільки важливим, що потрапило навіть в назву унікального винаходу XX віку - електронно-обчислювальна машина або на англійський манер, особливо поширений останнім часом, комп'ютер (computer), що в перекладі дає те ж саме значення - той, хто обчислює.

Досвід застосування ЕОМ досить швидко указав на несподівані і непередбачені можливості. З'ясувалося, що подібно числам можна ефективно перетворювати будь-яку іншу інформацію. Приймаючи до уваги один з найважливіших принципів побудови комп'ютера - принцип програмного управління, сформульований Дж. фон Нейманом, але очевидне відомий ще Ч.Беббіджу, ЕОМ слід би називати універсальним програмнокерованим автоматом для перетворення інформації. Але ми занадто консервативні, тому залишився термін обчислювальна машина, і навіть назва computer science - наука обчислень - для інформатики англійською мовою.

Займемося арифметичними програмами. При цьому треба пам'ятати, що більшість результатів збережуться і для неарифметичних програм.

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

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

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

1.1. Прості арифметичні алгоритми

1.1.1. Постійні і змінні величини

Зробимо позначення. Через Q визначимо множину всіх раціональних чисел, Z- всіх цілих, N- всіх натуральних, включаючи 0.

Натуральні і цілі числа будемо записувати в звичній десятковій позиційній системі числення. Серед різних способів запису раціональних чисел, спираючись на традицію, прийняту в мовах програмування, виберемо запис у вигляді десяткового неперіодичного дробу. З цих же міркувань будемо відділяти дробову частину від цілої крапкою, а не комою, як звичайно. Проблем зображення періодичних дробів, як і ірраціональних чисел, поки що не будемо торкатися.

Приклади запису чисел: 0, 1, +1, -1, 3.14159.

Як правило, в інформатиці прийняті позначення величин літерами. При цьому використовуються окремі літери, пронумеровані символи і навіть цілі слова.

Для позначення величин, а також інших об'єктів, в інформатиці використовується спеціальна конструкція, названа ідентифікатором (від латинського identifico- ототожнюю).

Ідентифікатор - це слово, складене з букв і цифр, на першому місці якого обов'язково знаходиться буква. Букви могли б бути довільними, але для визначеності обмежимося маленькими і великими латинськими буквами. Цифри будемо вживати арабські.

Приклади ідентифікаторів: х, pi, x1, v0, E2E4, sigma.

Складаючи алгоритм, корисно домовитися про величини, що його стосуються, та вказати їх приналежність: позначення і величину постійних, позначення і допустимі значення для змінних.

Визначення постійної будемо записувати як

конст c = a;

де c - ідентифікатор постійної, а - її значення. Наприклад, опис

конст pi = 3.14159265;

визначає константу з символічним ім'ям pi зі значенням 3.14159265.

Змінні приймають значення з однієї з числових множин Q, Z або N. Вираз

змін х: рац;

визначає ідентифікатор х як позначення для змінної, яка приймає довільні раціональні значення;

змін r: ціл;

- дає позначення r для змінної, яка буде приймати тільки

цілі значення;

змін n: нат;

- позначення n для змінної, яка буде приймати лише натуральні значення.

Послідовне визначення декількох констант буде мати стандартне скорочення

конст c1 = a1;...; cn = an;

зміст якого очевидний.

Аналогічне скорочення для позначення змінних

змін x1, ..., xk: рац;

y1, ..., yl: ціл;

z1, ..., zm: нат.

1.1.2. Пам'ять, введення і виведення

Тепер розглянемо будову найпростішого виконавця арифметичних алгоритмів, який визначимо через А₀.

Арифметичний виконавець А₀ має пам'ять Mem для зберігання величин , що стосуються алгоритму . Пам'ять складається з (необмеженого числа) клітинок, кожна з яких помічена унікальним ім'ям. У кожній клітинці може зберігатися одне число. Імена клітинок тому грають роль змінних, значеннями яких є числа, що знаходяться у клітнках. Крім того, виконавцеві А₀ відомі всі числові константи. Будемо вважати, що константа 0 знаходиться у клітинці, поміченій ідентифікатором "нуль", константа 0.1 - в клітинці "однадесята" і т.д. Попутно помітимо, що з'єднання декількох слів в одному імені - прийом вельми поширений. Для зручності читання таких ідентифікаторів до числа букв прийнято відносити знак підкреслення "_". Використовуючи знак підкреслення, останній ідентифікатор можна було б записати як "одна_десята".

Якщо в клітинці, відповідній змінній х, знаходиться число a, то будемо вважати, що значенням змінної х є число a. При цьому в клітинку, виділену для цілої змінної, не можна вмістити дробове число, а в клітинку, виділену для натуральної змінної, - від’ємне.

Графічне зображення змінної і її значення представлені на малюнку.

----x---

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

З пам'яттю взаємодіють наступні три команди, призначені для створення, зміни і зображення на вихідних пристроях значень змінних.

Нехай виконавець має спеціальний пристрій (його можна представити собі як звичайну клавіатуру або навіть як лист паперу і олівець), за допомогою якого можна записати довільне число. Назвемо цей пристрій пристроєм введення даних і позначимо In.

Команду введення даних будемо записувати

взяти (х),

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

Правило введення:

Якщо пристрій введення даних In не містить числа, виконавець алгоритму чекає, поки воно там не з'явиться.

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

Якщо число а належить області визначення змінної х, воно попадає у відповідну клітинку, інакше виконавець дає відмову.

Введення числа можна проілюструвати таким малюнком:

-----¬ ----------------¬

¦ In ¦ ¦ Mem ¦

¦----¦======>¦---------------¦

¦ а ¦ ¦ - х ¬ ¦

L----- ¦ ... ¦ ¦ ... ¦

¦ L---- ¦

L----------------

взяти (х)

-----¬ ----------------¬

¦ In ¦ ¦ Mem ¦

¦----¦======>¦---------------¦

¦ ¦ ¦ - х ¬ ¦

L----- ¦ ... ¦ а ¦. .. ¦

¦ L---- ¦

L----------------

Дія введення, як і інші дії виконавця, може бути не завжди успішним. Наприклад, безуспішною буде спроба надати натуральній змінній від’ємне значення або цілій - дробове. Реакція виконавця на безуспішність дії називається відмовою. У випадку відмови виконавець припиняє виконання даного алгоритму (більше не виконує ніяких його команд) і готовий виконувати будь-який інший алгоритм.

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

Команда, в деякій мірі симетрична введенню, - це виведення даних, тобто значення змінної х,

показати (х)

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

Правило виведення:

Нехай значення змінної х рівне b, тоді значення b буде відображено на пристрої Out. Значення змінної х при цьому не змінюється.

Графічно виконання виведення покажемо так:

----------------¬ ------¬

¦ Mem ¦ ¦ Out ¦

¦---------------¦======>¦-----¦

¦ - х ¬ ¦ ¦ ¦

¦ ... ¦ b ¦. .. ¦ L------

¦ L---- ¦

L----------------

показати (х)

----------------¬ ------¬

¦ Mem ¦ ¦ Out ¦

¦---------------¦======>¦-----¦

¦ - х ¬ ¦ ¦ b ¦

¦ ... ¦ b ¦. .. ¦ L------

¦ L---- ¦

L----------------

Команди введення і виведення - це команди, які задають значення аргументам алгоритму і повідомляють нам значення, отримані змінними, які позначають його результати.

1.1.3. Команда простого присвоєння

Крім пам'яті, пристроїв введення і виведення, виконавець арифметичних алгоритмів має арифметичний або операційний пристрій Op, призначений для виконання арифметичних дій.

Допустимо, що операційний пристрій може виконувати чотири арифметичних операції над раціональними числами

+ додавання;

- віднімання;

* множення;

/ ділення;

а також перші три і операції

div частки і

mod остачі від ділення

цілого і натуральних чисел.

Тепер ми можемо визначити основну команду арифметичного виконавця. Це команда простого присвоєння.

Нехай х - змінна, u і v - константи або змінні величини, w - одна з арифметичних операцій, тобто w Î {+, -, *, /, div, mod}.

Команду простого присвоєння будемо записувати так

х <- u w v

або, в окремих випадках, як

х <- u.

Правило простого присвоєння:

1) Присвоєння має вигляд: х <- c, де c - константа.

Якщо число c належить області визначення змінної х, то змінимо вміст пам'яті Mem, поклавши у клітинку, що відповідає змінній х, число c. Інакше дістанемо відмову.

2) Присвоєння має вигляд: х <- u, де u - змінна.

Обчислимо, використовуючи пам'ять Mem, значення а змінної u. Якщо число а належить області визначення змінної х, то змінимо вміст пам'яті Mem, поклавши у клітинку, що відповідає змінній х, число a. Інакше дістанемо відмову.

3) Присвоєння має вигляд: х <- u w v.

Обчислимо значення а і b величин u і v, відповідно, використовуючи пам'ять Mem. Якщо дія w визначена для аргументів а і b, то виконаємо її з допомогою операційного пристрою Op і отримаємо результат c = а w b, інакше матимемо відмову.

Змінимо вміст пам'яті Mem, поклавши у клітинку, що відповідає змінній х, число с.

Приклади простих присвоєнь: х <- х+1; v <- i*t; r <- s; s <- 1.

Графічно виконання простих присвоєнь можна зобразити, наприклад, так

х <- 5;

--------------------------¬ --------------------------¬

a) ¦ Mem ¦ b) ¦ Mem ¦

¦-------------------------¦ ¦-------------------------¦

¦ - 5 ¬ - х ¬ ¦ ==> ¦ - 5 ¬ - х ¬ ¦

¦ ... ¦ 5 ¦ ... ¦? ¦ ... ¦ ¦ ... ¦ 5 ¦ ... ¦ 5 ¦ ... ¦

¦ L---- L---- ¦ ¦ L---- L---- ¦

L-------------------------- L--------------------------

х <- u;

--------------------------¬ --------------------------¬

a) ¦ Mem ¦ b) ¦ Mem ¦

¦-------------------------¦ ¦-------------------------¦

¦ - u ¬ - х ¬ ¦ ==> ¦ - u ¬ - х ¬ ¦

¦ ... ¦ а ¦. .. ¦? ¦ ... ¦ ¦ ... ¦ а ¦. .. ¦ а ¦. .. ¦

¦ L---- L---- ¦ ¦ L---- L---- ¦

L-------------------------- L--------------------------

z <- х+у;

-- х -¬ -- у -¬ -- z -¬ -- х -¬ -- у -¬ -- z -¬

a) ¦ 1 ¦ ¦ 3 ¦ ¦? ¦ b) ¦ 1 ¦ ¦ 3 ¦ ¦ 4 ¦

L------ L------ L------ L------ L------ L------

¦ + ¦ ^

v v ¦

----------------¬ ----------------¬

¦ ¦ ¦ ==> ¦ ¦ ¦

¦ Op ¦ 1+3 ¦ ¦ Op ¦ 4 ¦

L---------------- L----------------

х <- х+у;

-- х -¬ -- у -¬ -- х -¬ -- у -¬

a) ¦ 1 ¦ ¦ 3 ¦ b) ¦ 4 ¦ ¦ 3 ¦

L------ L------ L------ L------

¦ + ¦ ^

v v ¦

----------------¬ ----------------¬

¦ ¦ ¦ ==> ¦ ¦ ¦

¦ Op ¦ 1+3 ¦ ¦ Op ¦ 4 ¦

L---------------- L----------------

Присвоєння вигляду х <- u, де u - змінна, назвемо пересилкою, а присвоєння вигляду х <- с, де с - константа,- ініціалізацією.

Присвоєння, взагалі кажучи, призначені для зміни значення змінної, яка знаходиться зліва. Але може трапитися і так, що нове значення співпадає зі старим. Зокрема, пересилка х <- х не міняє взагалі нічого. Будемо її вважати прикладом тотожньої команди, яку інакше будемо позначати

НічогоНеРобити

або скорочено

Нічого.

[ЗМІСТ] [Далі] [Назад]