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

  • Просмотров 6796
  • Скачиваний 62
  • Размер файла 80
    Кб

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 є цілком «законною» функцією. Але чи вираховувана