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

Задача 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 визначає розмір пам’я­ті, що виділяється для змінної зазначеного типу у разі отримання даної програми на виконання процесором.

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

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

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

 

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

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

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

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

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

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

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

 

 

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

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

Цифрові обчислювальні машини (ЦОМ) можна поділити на певні класи відповідно до організації загальних принципів обчислень. Наприклад, можна виділити одноадресні, двоадресні, 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 МГц).