1. Алгорітмічні проблеми
Навчаючі аріфметіці в початковій школі, ми познайоміліся з додаванням и множення двох чисел. Нам у явній ФОРМІ не кажу, что в будь-якої парі чисел існують добуток и сума, а вказано Способи и правила їхнього знаходження. Такі Способи и правила є прикладами алгорітмів, и обчислювальних (ефективна) процедур. Їхнє! Застосування НЕ вімагає чг вінахідлівості чг кмітлівості, учню звітність, Було Тільки слідуваті інструкціям вчителя.
Більш загально, алгоритм, чі ефективна процедура, - це механічне правило чг автоматичний метод, чі программа для Виконання Деяк математичних операцій. Пріведемо ще кілька прікладів операцій, для якіх легко можна вказаті алгоритми:
(1.1) (А) за даним п найти ne просте число;
(b) діференціювання полінома;
(c) знаходження найбільшого Загальне дільніка двох натуральних чисел (алгоритм Евкліда);
(d) для двох даніх чисел х, у вірішіті, чі є х кратних у.
Неформально и схематично алгоритм подань на малий. 1а. На вхід подається інформація чг об'єкт, что підлягає обробці (Наприклад, поліном у прікладі (1.1) (b), парі натуральних чисел у прикладах (1.1) (с) і (d)), а виходом є результат ОБРОБКИ Операції над входом (так, для (1.1) (b) це похідна полінома, а для (1.1) (d) - відповідь В«такВ» чи В«ніВ»). Вихід віробляється автоматично чорним ящиком-який может буті комп'ютером або школяр, что Діє по інструкції, чі даже Дуже РОЗУМНА добро тренованім собакою. Алгоритм є процедура (чі способ обчислення), здійснювана чорним ящиком для одержании виходе з входу.
Если алгоритм, чі ефективна процедура, вікорістовується для обчислення значень чіслової Функції, то ця функція назівається Ефективно обчислюваною, чі алгорітмічно обчислюваною, чі просто обчислюваною. Наприклад, Функції ху,
В
Чорний ящик
Вхід вихід
В
НСД (Х, у) = Найбільший загальний дільнік чисел х і у і f (n) = Прості числа віраховувані в неформальному змісті, як вже відзначалося Вище.
Розглянемо, з Іншого боці, Наступний функцію:
В
1, ЯКЩО в Десяткова розкладанні числа pi знайдеться
g (n) == Рівно п ПІДРЯД йдущіх цифр 7;
0 у осоружному випадка.
алгоритм Предикативно Операторний знання
Більшість математіків вважають, что g є Цілком В«законноюВ» функцією. Альо чг віраховувана функція g? Існує механічна процедура для послідовного породження цифр у Десяткова розкладанні pi, того напрошується В«процедураВ» для обчислення Функції g. В«При заданому п почніть обчіслюваті Десяткова розклад pi по одній ціфрі за один такт годині и відзначайте з'явиться сімок. Если на якому-небудь кроці з'явиться відрізок, что Складається Рівно з п сімок, Зупини процес обчислення и покладете g (n) = 0. Если такий відрізок НЕ буде виявлений, то покладете g (n) = 0 В».
Недоліком цієї В«процедуриВ» є та обставинні, что ЯКЩО для Деяк п НЕ існує відрізка з п - сімок, тоді ні на якому кроці процеса ми не можемо Зупинити и сделать Висновок про ті, что цею факт має місце. На шкірному даним кроці ми Можемо очікуваті, что така послідовність сімок может зустрітіся в ще недослідженній нескінченній частіні розкладання pi. Таким чином, ця В«процедураВ» буде продовжуватіся Нескінченно довго для усяк входу п, такого, что g (n) = 0; того вона НЕ є ефективного процедурою. (Можливо, что існує ефективна процедура для обчислення g, засновалося, імовірно, на Деяк теоретичності властівостях числа pi. У Данії годину, однак, така процедура невідома.)
цею приклад віявляє Дві характерні РІСД Поняття ефектівної процедури, а самє что така процедура відбувається за Деяк послідовність кроків (КОЖЕН крок віконується за кінцевій годину) І що КОЖЕН вихід з'являється после кінцевого числа кроків.
Дотепер ми неформально опісувалі Поняття алгоритму (чі ефектівної процедури) i зв'язаного з ним Поняття обчіслюваної Функції. Ці Поняття мают потребу в уточненні, дере чем смороду стануть основою для математичної Теорії обчіслюваності.
Визначення будут дані в термінах простого В«ідеалізованого комп'ютераВ», что Виконує програми. Ясно, что процедури, что могут буті пророблені Реальних комп'ютером, є прикладами Ефективно процедур. Однак КОЖЕН окремий реальний комп'ютер обмеженності як завбільшки чисел, что надходять на вхід, так и розміром доступного РОБОЧЕГО простору (для запам'ятовування проміжніх результатів); самє в цьом відношенні наш В«комп'ютерВ» буде ідеалізованім відповідно до неформ...
