Войти на сайт

или
Регистрация

Навигация


1. Алгоритмічні проблеми

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

Більш загально, алгоритм, чи ефективна процедура, – це механічне правило чи автоматичний метод, чи програма для виконання деяких математичних операцій. Приведемо ще кілька прикладів операцій, для яких легко можна вказати алгоритми:

(1.1) (а) по даному п знайти n-e просте число;

(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. В даний час, однак, така процедура невідома.)

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

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

Визначення будуть дані в термінах простого «ідеалізованого комп'ютера», що виконує програми. Ясно, що процедури, що можуть бути пророблені реальним комп'ютером, є прикладами ефективних процедур. Однак кожен окремий реальний комп'ютер обмежений як величиною чисел, що надходять на вхід, так і розміром доступного робочого простору (для запам'ятовування проміжних результатів); саме в цьому відношенні наш «комп'ютер» буде ідеалізованим відповідно до неформальної ідеї алгоритму. Програми нашої обчислювальної машини будуть кінцевими, і ми скажимо, щоб обчислення, що завершуються, виконувалися за кінцеве число кроків. Входи і виходи ми обмежимо натуральними числами; це не є істотним обмеженням, оскільки операції, що включають інші види об'єктів, можуть бути закодовані як операції над натуральними числами. (Більш докладно ми зупинимося на цьому в § 5.)


Информация о работе «Алгоритмічні проблеми»
Раздел: Математика
Количество знаков с пробелами: 54576
Количество таблиц: 5
Количество изображений: 0

Похожие работы

Скачать
33080
5
4

... число эпох функционирования алгоритма, или определение его сходимости, обычно путем сравнивания приспособленности популяции на нескольких эпохах и остановки при стабилизации этого параметра. 3. Непрерывные генетические алгоритмы. Фиксированная длина хромосомы и кодирование строк двоичным алфавитом преобладали в теории генетических алгоритмов с момента начала ее развития, когда были получены ...

Скачать
18213
1
5

... в состояние qj, заменяя содержимое ячеек соответственно символами аb1 - аbк, то после этого ленты соответственно сдвигаются в направлениях k1... kk. До сих пор принималось, что различные алгоритмы осуществляются на различных машинах Тьюринга, отличающихся набором команд, внутренним и внешним алфавитами. Однако, можно построить универсальную машину Тьюринга, способную выполнять любой алгоритм ...

Скачать
26020
3
4

... M2(n) = O(l n), C2(n) = O(l n). Оскільки l = log2n, M2(n)=O(n log2 n)), C2(n)=O(n log2 n), Але З(n) = C1(n) + C2(n), M(n) = M1(n) + M2(n). Тому що C1(n) < C2(n), M1(n) < M2(n), остаточно одержуємо оцінки складності алгоритму TreeSort за часом: M(n) = O(n log2 n), C(n) = O(n log2 n), У загальному випадку, коли n не є ступенем 2, сортуюче дерево будується трохи інакше. “Зайвий” елемент ...

Скачать
10075
2
1

... U4 сравнения двух целых чисел оставляем читателю в качестве упражнения. Замечание: исходное слово надо задать в форме  * Для нормальных алгоритмов Маркова справедлив тезис, аналогичный тезису Тьюринга. Тезис Маркова: Для любой интуитивно вычислимой функции существует алгоритм, ее вычисляющий. Построение алгоритмов из алгоритмов. До сих пор, строя ту или иную МТ, или НАМ мы каждый раз ...

0 комментариев


Наверх