Алгоритми

Потреби суспільства в узагальненні багатьох підходів до роз­в’язання різноманітних задач зумовили створення теорії алгоритмів. Бурхливий розвиток науки і техніки в останні століття, спроби філософів найточніше описати різноманітні аспекти людського буття дали світові науку наук – логіку розвитку, яка породжувала задачі, що стимулювали появу нових ідей і методів їх розв’язання. Складність і вели­кий об’єм обчислень зумовили створення спеціалізованих обчислюваль­них пристроїв. Вони прой­шли складний шлях розвитку. Серед них можна виділити один із найпотуж­ніших класів – це електронно-обчислювальні машини (ЕОМ). Проникнення ЕОМ у різні сфери практичної діяльності людей значно вплинуло на еволюцію теорії алгоритмів, на вибір нових напрямів її застосування. Вона перетворилась у певну школу мислення й аналізу для широкого кола програмістів, дала основу мові алгоритмів, яка об’єднує різні напрями досліджень у програмуванні, полегшує розповсюдження ідей. Теорія алгоритмів є важливою частиною прикладної математики,
а по­няття алгоритму та форм його задання посідає чільне місце в теорії алгоритмів.

Як відомо, слово алгоритм прийшло з Персії, запропонував його автор книги з математики Abu Jafar Mohammed ibn Musa al Khowarizmi. Він визначав його як деякий спеціальний метод вирішення поставленої проблеми.

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

Умовно можна виділити три основні етапи розвитку теорії алго­ритмів.

На першому етапі відбувалося накопичення фактів людиною, що засвоювала знання про природу і стихійно формувала та закріплювала власні алгоритми поведінки.

Другий етап становлення алгоритмічного апарату пов’язаний з розвит­ком математичних наук. Для нього є характерним чітке задання мате­ма­тичних алгоритмів розв’язання різних прикладних задач і опис значних алгоритмічних проблем, що не піддавались розв’язанню традиційними методами, наприклад трисекція кута.

Третій період бере відлік з початку ХХ ст. Було побудовано формаль­ну класичну теорію алгоритмів, яка уточнювала можливості тео­ретич­ного обчислення для практичного застосування в кібернетиці й про­гра­му­ван­ні. Теорію алгоритмів можна поділити на класичну і прикладну. У кла­сичній теорії алгоритмів існує безліч формальностей для опису алгоритмів. Серед них можна виділити найзначніші: арифметичне чис­лення предикатів Гьоделя, машини Поста і Тьюринга, автомати Маркова, схеми Янова, блок-схеми.

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

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

Приклад і властивості алгоритму

Задача 2.1.

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

Алгоритм 2.1:

П1: Покласти ціле число рівним двом і перейти на крок П2.

П2: Якщо ділиться без остачі на , то завершити роботу алгоритма, видавши в якості результату ; інакше перейти на крок П3.

П3: Збільшити значення на одиницю і перейти на крок П2.

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

		= 2
П1:	П1:	П1:
П2:	П2:	П2:
П3:
П2:

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

Основні властивості будь-якого алгоритму - це завершеність, визначеність, вхід (введення), вихід (висновок) і ефективність. Розглянемо їх послідовно більш докладно.

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

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

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

Вихід (вихід). Алгоритм завжди зобов'язаний мати одну чи кілька вихідних величин. У разі алгоритму 7.1 такою величиною є число . Алгоритми, що не мають вихідних даних, марні на практиці, і ми не будемо їх вивчати.

Ефективність. Від алгоритму потрібно, щоб він був ефективним. Це означає, що всі операції, які необхідно зробити в алгоритмі, повинні бути досить простими, щоб їх в принципі можна було виконати точно і за скінчений час за допомогою олівця і паперу. В алгоритмі 7.1 виконуються лише такі операції: порівнюються два цілих числа, одне позитивне число ділиться на інше, змінній присвоюється значення цілого числа два, її значення збільшується на одиницю.
Всі ці операції є ефективними у вказаному вище значенні. Але ті ж самі операції не були б ефективними, якщо б значеннями величин, які фігурують в алгоритмі, були б довільні дійсні числа, виражені нескінченними десятковими дробами, так як подібні величини не можна навіть записати на папері за скінчений час.

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

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

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

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

Розглянемо такий приклад. Нехай потрібно дослідити розв’язання повного квадратного рівняння

Алгоритм дослідження можна описати українською мовою за допомогою такої послідовності кроків:

0. Ввести значення a, b, c.

1. Обчислити дискримінант .

2. Якщо , тоді надрукувати повідомлення «рівняння має один роз­в’я­зок: ».

В іншому разі, якщо тоді надрукувати повідомлення «рівняння має два корені: і ».

Інакше (якщо ) надрукувати повідомлення «рівняння не має дійсних коренів».

3. Кінець алгоритму.

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

Наш алгоритм можна описати блок-схемою, яку зображено на рис. 2.1.

Блок-схема є зв’язним орієнтованим графом, вузли якого можуть бути блоками чотирьох типів: блок ініціалізації (ввести значення a, b, c), функціональні блоки (обчислити , вивести…), предикатні блоки (, ) і блок закінчення обробки інформації (кінець). Кожен блок належить певному шляху з початкового блоку в кінцевий. Передачу керування між блоками визначають напрямленими стрілками. Предикатний блок використовують для розгалуження керу­вання (умовної передачі керування). Він функціонує так: якщо предикат, що стоїть в середині ромба, справджується (набуває значення «істина», позначається «і»), то керування передається одному блоку, якщо ж пре­ди­кат не справджується (набуває значення «хибність», позначається «х»), тоді керування передається іншо­му блоку.

Для дослідження цієї задачі на ЕОМ слід описати алгоритм дослі­дження за допомогою якоїсь мови програмування. Таке задання нази­вають програмою.

Структура програми більшості мов програмування типова і має загаль­ний характер. Розглянемо запис програми 1.1 дослідження розв’язання пов­ного квадратного рівняння в мові програмування Паскаль.

program EХ1_1;

var A, B, C, D: real;

Begin

read (A, B, C);

D:= B*B – 4*A*C;

if D = 0 then

writeln (‘Рівняння має один розв’язок x = ‘, –B/(2*A))

Else

if D > 0 then

writeln (‘Рівняння має два корені x ₁ = ‘, (–B + D)/(2*A),

‘ i x ₂ = ‘, (–B – D)/(2*A))

Else

writeln (‘Рівняння не має дійсних коренів’);

end.

Програма 1.1. Дослідження розв’язку повного квадратного рівняння

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

Програми Паскаль, як і програми більшості мов програмування, скла­даються з таких основних частин: заголовка (program), блока опису кон­­стант (const), блока конструювання типів (type), блока опису змінних (var), блока опису процедур та функцій і блока виконань (begin–end).

Заголовок програми, в нашому прикладі іменується EХ1_1, викори­стовується для ідентифікації програми і може містити опис пристроїв введення-виведення інформації.

Блок опису змінних використовують для визначення розмірів ділянок пам’яті, де процесор оброблятиме інформацію для отримання кінцевого результату. У цьому випадку змінні A, B, C, D виступають у ролі засобів доступу до ділянок пам’яті (імен), а опис real визначає розмір пам’я­ті, що виділяється для змінної зазначеного типу у разі отримання даної програми на виконання процесором.

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

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

Блок виконань містить інструкції, що описують послідовність дій, які процесор здійснюватиме над пам’яттю для отримання кінцевого результату алгоритму.

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

Традиційно програми можна поділити на два класи: прикладні та системні. Прикладні програми використовують для розв’язання конкретних прикладних задач. Системні програми полегшують роботу користувача на комп’ютері. До системних програм належить і набір програм, який дістав назву операційна система (ОС).

ОС забезпечує взаємодію між користувачем і комп’ютером, а також між програмою і різними компонентами апаратури комп’ютера. Загальне керування комп’ютером здійснюють за допомогою мови директив. У кожній ОС є набір службових програм (утиліт), які використовують для полегшення роботи у разі написання програм. Одна з типових конфігурацій ОС для комп’ютера має такі складові компоненти: файлову систему; драйвери зов­нішніх пристроїв; процесор командної мови.

2.2. Обчислювальні машини

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

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

Будь-яка аналогова система має істотно неперервну осно­ву, числа задаються фізичними величинами (промінь світла, струм тощо).

Для ілюстрації основної відмінності між цифровим і аналоговим принципом обробки інформації розглянемо класичний приклад з музичними інструментами. Баян можна назвати дискретною системою, тому що в ній довільну фіксовану ноту можна або грати, або ні, бо кожна нота (клавіша) дискретно відділена від наступної. Скрипка ж буде аналоговою системою, оскільки на скрипці висота тону може змінюватися без­пе­рервно.

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

Цифрові обчислювальні машини (ЦОМ) можна поділити на певні класи відповідно до організації загальних принципів обчислень. Наприклад, можна виділити одноадресні, двоадресні, n-адресні обчислювальні ма­шини. Ця відмінність ґрунтується на різниці в числі адрес у командних словах обчислювальної машини. Іншим прикладом поділу є два ве­ли­кі класи ЦОМ: послідовні та паралельні. Цей поділ використовує та­кий кри­терій: ЦОМ можуть виконувати одночасно одну або кілька операцій.

Загальну схему ЦОМ ілюструє рис. 2.2.

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

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

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

Команди слід записувати у пристрій запам’ятовування у вигляді машинних «слів», що задають в числовому вигляді. Числа, які машина обробляє, мають бути заданими у вигляді машинних слів. Інакше кажучи, машинні слова задають команди і дані.

Проведіть аналогії загальної схеми функціонування ЕОМ із загальною схемою функціонування деякого виробничого комплексу.

Різні обчислювальні машини можуть використовувати різні коди для задання команд: десятковий, двійковий, вісімковий, шістнадцятковий тощо. Детально на цих кодах не зупинятимемося, тільки зазначимо, що довільне слово, число можна закодувати послідовністю двійкового коду 0 і 1.

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

Як ілюстрацію такого принципу розглянемо умовну триадресну обчислю­вальну машину, тобто машину, в якій командне слово містить три адре­си: адреси двох чисел, що обробляються, і адресу, куди заносять результат обробки. Припустимо, ми вибрали таке кодування арифметичних операцій для триадресної машини: додавання (01), віднімання (02), множення (03), ділення (04), умовний перехід (05), завантаження (06), друк (07).

Розглянемо таку просту арифметичну задачу. Нехай потрібно пере­множити числа2 і 3, потім відняти 1 та надрукувати результат. Перше, що слід зробити,- розмістити числа 2, 3, 1 у вільних регістрах па­м’яті. Нехай такими будуть регістри з номерами 500, 501, 502. Для позначення цієї дії використаємо запис 06/500(2), 06/501(3), 06/502(1). Для триадресної ма­шини команди мають таку структуру:

І / A 1/ A 2/ A 3,

де І - код команди, А 1, А 2, А 3 - адреси регістрів.

Тоді для реалізації нашої задачі потрібно написати програму:

03/500/501/500

02/500/502/503

07/503

Одноадресна і двохадресна машини працюють за іншим принципом.
У них використовується пристрій накопичувального типу, який називають суматором. У таких машинах команди заносять усі числа обробки
в суматор. Є спеціальні команди, які повертають числа із суматора у за­гальну пам’ять.

Для кращого зберігання операндів і операцій в пам’яті обчислювальної машини Ньюел у 1961 р. запропонував використовувати списки. Базовим елементом списку є елемент, зображений на рис. 2.3.

Список можна використати для «зв’язування» різних елементів пам’я­ті, які «фізично» містяться в непослідовних фрагментах пам’яті ЦОМ. Так вираз можна описати списком, зображеним на рис. 2.4.

Є ще один тип обчислювальних пристроїв, який стоїть трішки виокрем­лено – це нейрокомп’ютер. З початку створення обчислювальних пристроїв спеціалісти намагалися створити такий пристрій, який би моделював роботу мозку людини. Оскільки в ньому головну роль виконує нейрон, можна знайти ключ до моделювання розумової діяльності людини в моделюванні роботи нейрону мозку. Для багатьох цілей нейрон можна розглядати як елемент з певним критичним значенням. Це означає, що він або ж дає на виході деяку постійну величину, якщо сума його входів досягає певного значення, або ж залишається пасивним.

Мак-Каллок і Піттс довели, що будь-яку обчислювальну функцію можна реалізувати за допомогою спеціально організованої мережі ідеаль­­них нейронів, логічні властивості яких з високою вірогідністю можна приписати реальному нейрону. Ця мережа матиме наступні вади. По-перше, проблема полягає в тому, чи можна знайти якийсь розумний принцип реорганізації мережі, який давав би змогу випадково об’єдна­ній спочатку групі ідеальних нейронів самоорганізовуватись в «обчислювальний пристрій», здатний розв’язувати довільну за­да­чу. По-друге, потріб­но використовувати велику кількість нейронів. Так, мо­дель роботи мозку му­рашки потребує використання близько 20 000 ней­ронів, що на практиці реалізувати неможливо.

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

Причина цього в наступному:

1) характер взаємозв’язків між нейронами дає змогу робити розв’я­зання багатьох задач, а також реалізацію різних функцій – у паралельний спосіб;

2) у нейронній мережі пам’ять не локалізована в одному місці (як в послідовних машинах), а розподілена по всій структурі; у біологічних системах пам’ять реалізується підсиленням або послабленням зв’язків між нейронами, а не зберіганням двійкових символів;

3) біологічні мережі реагують не на всі, а тільки на визначені зовнішні подразнення; кожен нейрон виступає як елемент прийняття рішення і елемент зберігання інформації; перевага такої структури – «жит­тєздат­ність» (вихід з ладу декількох нейронів не спричинює значної зміни даних, що зберігаються, або руйнування всієї системи);

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

В основу зв’язків у нейрокомп’ютерах покладено асоціативний принцип. Асоціативні зв’язки пронизують все мислення людини. Наприклад, результат операції у нас є в пам’яті, і ми кожного разу його не обчислюємо, на противагу комп’ютеру. Існує думка, що процеси мислення є не що інше як розповсюдження певного збудження, як деяка ланцюгова реакція. Навіть найпримітивніші процеси навчання принципово залежать від послідовності подій у часі. Це й закладено в природу нейронних систем. Тому їм притаманне реагування тільки на жорстко визначене зовнішнє подразнення. Наприклад, домашні тварини «навчаються» ігнорувати повторні несуттєві зовнішні подразнення («цокання» годинника), але посилюють сприйняття подразнень, які можуть мати серйозні наслідки (звук гальм автомобіля).

Тому майбутнє – за комп’ютерами, які ґрунтуються на аналізі зв’язків,
а не обробці символів. М. Мінський говорив, якщо комп’ютер має діяти по­дібно до мозку, тоді і його конструкція має бути також подібною до мозку.

Моделі нейронних мереж і схеми з адресацією за змістом мають і не­до­ліки. Внаслідок нефіксованої організації вони можуть плутати різні об’єкти. Це аналогічно звиканню, посиленню чуттєвості до асоціацій, які лежать в основі психологічних особливостей людини. Інакше кажучи, довільний комп’ютер, що претендує на «розумність», повинен мати такі особливості.

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

Робота інтерпретатора ґрунтується на тому, що для задання кожної операції в машині використовують особистий символ, так що увесь набір операцій програми можна задати простими символами. Вони інтерпретуються і послідовно обробляються машиною.

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

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

Слово комп’ютер походить від англійського слова to compute, яке означає «здійснювати обчислення». Інша назва комп’ютерів - електрон­ні обчислювальні машини. Вона підкреслює два ключових аспекти. По-перше, комп’ютер - це сукупність апаратних засобів, призначених для обчислень і перетворення інформації. По-друге, основними елементами комп’ютерів є електронні прилади.

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

Найпростіші засоби для виконання простих арифметичних операцій були відомі людям у глибоку давнину. Перші механічні пристрої (арифмометри) створено в середині ХVII ст. Паскалем і Лейбніцом. У XIX ст. Чарльз Беббідж уперше сформулював ідею створення універсальної обчислювальної машини. Він розробив детальний проект, який не був закінчений через відсутність необхідної технічної бази.

Значний внесок у розробку принципів функціонування комп’ютерів зробив Алан Тьюринг, який у 1937 р. описав гіпотетичну машину з уні­версаль­ними можливостями. Ця машина Тьюринга, яку можна розглядати як одну з можливих формалізацій поняття «алгоритм», стала теоретич­ною основою сучасних комп’ютерів. Перша електронно-обчислювальна ма­шина ENIAC створена у 1943–46 рр. Дж. У. Моклі та Дж. П. Екертом з Пенсільванського університету. Величезний внесок у розвиток обчис­лювальної техніки зроблено працею Дж. фон Неймана. Початок серій­но­го виробництва ЕОМ пов’язують зі створенням у 1951 р. ЕОМ UNIVAC. Роботи над створенням першої вітчизняної ЕОМ МЕЛМ (малої електронної лічильної машини) були розпочаті в Інституті електротехніки АН УРСР у 1947–1948 рр. в м. Києві групою науковців під керівництвом С. О. Лебєдєва. У 1951 р. машину було прийнято до експлуатації.

Як подальші віхи в розвитку обчислювальної техніки можна відзначити такі: поява операційних систем; виникнення мов програмування високого рівня; розвиток мережних технологій і масове розповсюдження персональ­них комп’ютерів.

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

Універсальний цифровий комп’ютер може реалізувати будь-який алгоритм. Інформація, яку обробляє комп’ютер, зберігається в його пам’яті у вигляді послідовності нулів та одиниць. Пам’ять складається з електронних схем, кожна з яких може перебувати в одному з двох стійких ста­нів, один з них беруть за 0, а інший - за 1. Мінімальною одиницею інформа­ції є біт. Біт - один двійковий розряд, за допомогою якого можна закоду­вати одне з двох можливих значень: 0 або 1.

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

Цифрові універсальні комп’ютери можна класифікувати за потужністю. Виділяють такі основні групи цих комп’ютерів.

Суперкомп’ютери. Для них характерна наявність великої (десятки, сотні або тисячі) кількості процесорів, які сумісно розв’язують ту чи іншу задачу, тим чи іншим способом взаємодіючи між собою; у цьому разі забезпечується дуже висока сумарна потужність. Типове призначення - виконання надскладних розрахунків. Найпростіші суперкомп’ютери мож­на використовувати як корпоративні мережні сервери. У цьому разі їх називають майнфреймами. Як приклади суперкомп’ютерів можна навести IBM System/390, T/9000, RS/6000. Ще більшу потужність забезпечують суперкомп’ютери фірм Intel, Fujitsu, Hitachi, Cray-SGI. Одна із останніх розробок Intel об’єднує 9200 процесорів Pentium Pro, займає площу 160 м² і має масу 40 т. Пристрій для охолодження важить 272 т. Оперативна па­м’ять становить 573 ГБ, швидкодія - понад триль­йон операцій за секунду.

ЕОМ класу міні займають проміжне положення між великими ЕОМ
і персональними комп’ютерами. Мають невелику кількість процесорів (від 1 до 8–12) та порівняно невеликі розміри і невисоку ціну. Використовуються як професійні робочі станції або як корпоративні мережні сервери.

Персональні комп’ютери. Їх можна визначити як комп’ютери, призначені для індивідуального користування. Поділяють їх на настільні
та портативні. Останнім часом з’явився новий клас - пер­сональні помічники, такі як Psion виробництва компанії Sharp, Newton Messag Pad фірми Apple Computer, Omni Go фірми Hewlett-Packard. Це мобільні комп’ю­тери, мініатюрні за розміром (300–4000 г), з порівняно невеликою оперативною пам’яттю (1–2 МБ) та малою тактовою частотою (7–9 МГц).

2.3. Основи фон-нейманівської архітектури

Значна частина сучасних комп’ютерів функціонує за принципами, сформульованими в середині 1940-х рр. Дж. фон Нейманом. Він виділив пристрої, які мають входити до складу комп’ютера: керуючий; арифметико-логічний; оперативну пам’ять; зовнішню пам’ять (зовніш­ні запам’ятовуючі пристрої, зовнішні носії інфор­мації); введення; виведення.

Роботу універсальної фон-нейманівської ЕОМ у найзагальніших рисах можна описати так.

Програми та дані, що зберігаються на зовнішніх носіях, вводять за допомогою пристроїв введення і пересилають до оперативної пам’яті. Обчислення здійснюють арифметико-логічним пристроєм. Інформацію, що є в оперативній пам’яті, за потреби передають до ариф­метико-логіч­ного пристрою для обробки; проміжні результати об­числень знову пере­дають в оперативну пам’ять. Результати роботи обчис­лювальної машини виводять на зовнішні носії за допомогою пристроїв виведення. Всі операції в ЕОМ здійснюють під управлінням керуючого пристрою.

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

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

Фон-нейманівська архітектура має багато «вузьких місць». Уже наприкінці 1950-х рр. намітилися тенденції відходу від фон-нейманівської архітектури. Зокрема, ці тенденції були пов’язані з розвитком багатопроцесорних систем. Нині можна вважати, що класична фон-нейманів­ська архітектура в основному вичерпала свої можливості.

Типовий центральний процесор фон-нейманівського комп’ютера має таку структуру. Регістри процесора використовують для тимчасового зберігання даних. В одному регістрі можна зберігати 2–4 байти інфор­мації. Кількість розрядів, або бітів, в одному регістрі називають його розрядністю. Регістр адреси пам’яті містить адресу комірки пам’яті,
з якої або в яку слід переслати дані. Регістр даних пам’яті містить дані, що мають бути зчитані в оперативну пам’ять. Програмний лічильник містить адресу комірки пам’яті, в якій зберігається команда, що виконується. Регістр команд містить команду, яку слід виконувати.

Типовий цикл виконання команди складається з трьох кроків: вибірки, декодування, безпосереднього виконання. На початку вибору чергової ко­ман­ди в програмному лічильнику міститься її адреса. Цю адресу пересилають до регістра адреси, а керуючий пристрій надсилає до оперативної пам’яті сигнал зчитування. Інформацію, зчитану з оперативної пам’яті, пересилають з пам’яті в регістр даних пам’яті, а звідти - в регістр команд. Аналогічним способом зчитують операнди команди.

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

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

Обмін даними між процесором та оперативною пам’яттю здійснюється через шину пам’яті. Фізично шина складається з певної кількості провідників. Через один провідник можна одночасно передати один біт інформації. Кількість таких провідників називають розрядністю шини. Один провідник інколи називають лінією. Шина пам’яті складається з двох частин: шина даних, адресна шина. Шину даних використовують для передачі даних, адресну шину - для передачі адреси.

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

Лекція 3.