Xreferat.com » Рефераты по математике » Алгоритмічні проблеми

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

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

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

(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.)


2. Необхідні поняття, факти і нотація із інших математичних дисциплін


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

1. Множини

Для позначення множин звичайно будуть використовуватися прописні букви А, В, С…. Тут хАлгоритмічні проблемиА позначає, що х є елементом множини А чи належить множині А, а хАлгоритмічні проблемиА означає, що х не належить множині А. Позначення {х/… х…}, де…х… є деяке твердження, що включає х, означає множину всіх об'єктів х, для яких…х… вірно. Так, {х/х є парним натуральним числом} є множина {0,2, 4,6,…}.

Якщо А, В суть множини, то запис A Алгоритмічні проблеми В означає, що А міститься (як частина) в В (чи А є підмножиною В); запис ААлгоритмічні проблемиВ означає, що ААлгоритмічні проблемиВ, але ААлгоритмічні проблемиВ (тобто А є власною підмножиною В). Об'єднання множин А, В, є множина {х| хАлгоритмічні проблемиА чи хАлгоритмічні проблемиВ (чи відразу двом множинам А, В)} і позначається А U В; перетин А, В є множина {х/хАлгоритмічні проблемиА і хАлгоритмічні проблемиВ} і позначається через ААлгоритмічні проблемиВ. Різниця (чи відносне доповнення) множин А, В є множина {х / хАлгоритмічні проблемиА і хАлгоритмічні проблемиВ} і позначається АВ.

Порожня множина позначається через 0. Стандартний символ N позначає множину натуральних чисел {0, 1, 2, 3,…}. Якщо А – множина натуральних чисел (тобто ААлгоритмічні проблемиN), то А позначає доповнення до А до N, тобто NА. Через N+ позначається множина додатніх натуральних чисел {1,2,3,…}, а множина цілих чисел позначається через Z.

Упорядкована пара елементів х, у позначається (х, у); таким чином, (х, у)Алгоритмічні проблеми(у, х). Картезіанським, чи декартовым, добутком множин А и В називається множина {(х, у)/хАлгоритмічні проблемиА, уАлгоритмічні проблемиВ}, і позначається вона через ААлгоритмічні проблемиВ.

Більш узагальнено, запис (х1…, хn) позначає упорядкований n-набір (п-ку) елементів х1,…, хn; часто цей n-набір позначається однією жирною буквою х. Якщо А1,…, Аn суть множини, те А1Алгоритмічні проблеми…Алгоритмічні проблемиАn позначає множину n-ок {(х1,…, хn) /х1 Алгоритмічні проблемиА1 і х2 Алгоритмічні проблемиА2…хnАлгоритмічні проблемиАn}. Добуток ААлгоритмічні проблемиААлгоритмічні проблеми…Алгоритмічні проблемиА (п разів) скорочено позначають як Аn; а А1 означає просто А.

2. Функції

Ми припускаємо, що читач знайом з основним поняттям функції і розходженням між функцією f і окремим значенням f(х) на даному х, на якому функція визначена. Областю (визначення) функції f називається множина {x/f(x) визначена} і позначається Dom(f); ми будемо говорити, що f (х) не визначена, якщо xАлгоритмічні проблемиDom(f). Множина {f (х) | х Алгоритмічні проблеми Dom (f)} називається множиною значень, чи образом (range), функції f і позначається через Ran (f). Якщо А и В – множиниі, то будемо говорити, що f є функція з A в В, якщо Dom (f)Алгоритмічні проблемиA и Ran(f)Алгоритмічні проблемиВ. Коли Dom(f)=A, буде застосовуватися позначення f: AАлгоритмічні проблемиr.

Функція називається ін’єктивною, якщо з х, уАлгоритмічні проблеми Dom (f) і хАлгоритмічні проблемиу випливає f(х) Алгоритмічні проблемиf (у). Для ін’єктивної функції f через f -1 позначається функція, зворотня до f, тобто така єдина функція g, що Dom (g)=Ran (f) g (f(x))=x для всіх хАлгоритмічні проблемиDom (f). Функція f з А в В називається сюр’єктивною, якщо Ran(f)=B.

Якщо f: A Алгоритмічні проблеми В и функція f ин’єктивна (сюр’єктивна), то f називається ін'єкцією (з А в В) (сюр’єкцією (з А в В)). Функція, що є одночасно ін'єкцією і сюръекцией, називається биекцией.

Припустимо, що f є функцією, а Х – множина. Обмеженням f на Х називається функція з областю визначення ХАлгоритмічні проблемиDom(f), значення якої в кожному х Алгоритмічні проблеми Х Алгоритмічні проблеми Dom (f) дорівнює f(x).

Обмеження f на Х позначається через f|X. Ran (f|X) позначається через f(X). Якщо Y – множина, то прообразом Y відносно f називається множина f-1(Y)={x|f(x)Алгоритмічні проблемиY}. (Помітимо, що прообраз визначений навіть тоді, коли функція не ин’єктивна.)

Якщо f, g-функції, то будемо говорити, що g продовжує f, коли Dom (f) Алгоритмічні проблеми Dom (g) і f(х) = g (х) для всіх х Алгоритмічні проблеми Dom (f); у коротшому запису: f=g/Dom(f). Це відношення функцій f, g записується як f Алгоритмічні проблеми g.

Композиція двох функцій f і g є функція з областю визначення {x/xАлгоритмічні проблемиDom(g) і g(x)Алгоритмічні проблемиDom(f)}, значення якої, коли вона визначена, є f (g(x)). Цю функцію позначають через fАлгоритмічні проблемиg.

Через f0 позначаємо ніде не визначену функцію; тобто Dom(f0)=Ran(f0)=0. Очевидно, що f0=g|0 для будь-якої функції g.

В обчисленнях нам часто будуть зустрічатися функції чи вирази, що включають функції, що не усюди визначені. У таких випадках дуже зручне наступне позначення. Нехай a(x) і b(х) – вирази, що включають змінні х=(х1,…, хn). Тоді запис а(x) Алгоритмічні проблемиb(x) означає, що для кожного х вираження а(x) і b(x) або одночасно визначені і рівні, або обидва не визначені. Так, наприклад, для функцій f і g запис f(x)Алгоритмічні проблемиg(x) означає, що f=g; і для довільного числа y запис f(x) Алгоритмічні проблеми y означає, що f(x) визначена і дорівнює y (оскільки y завжди визначене).

Функції від натуральних чисел. У більшій частині цієї книги ми будемо мати справу з функціями від натуральних чисел, тобто з функціями з Nn в N для різних п, здебільшого для п = 1 чи 2.

Функція f з Nn в N називається п-місною функцією. Значення f на п-кі (x1,…, хn) Алгоритмічні проблемиDom (f) записується як f(x1,…, xn) чи f(x), якщо x представляє (x1,…, xn). У багатьох книгах і статтях термін часткова функція використовується для позначення функції з Nn у N, область визначення якої не обов'язково збігається з Nn. Для нас слово функція означає часткову функцію. Проте при нагоді ми будемо писати «часткова функция», щоб підкреслити її можливу «не усюди визначеність». Тотальною функцією з Nn у N ми називаємо функцію з Nn у N), область визначення якої є всі Nn. l

Ми затушовуємо розходження між функціями і їхнім значеннями в різних крапках, особливо у випадку теоретико-числових функцій у двох досить стандартних і недвозначних ситуаціях. По-перше, ми допускаємо такі фрази як «Нехай f(x1,…, xn) – функція…», що означає, що f є n-місною функцією. По-друге, ми часто описуємо функцію в термінах її значення, що задається деякою формулою. Наприклад, «функція х2» означає «одномісна функція f, значення якої в кожному х Алгоритмічні проблеми N є х2»; аналогічно «функція х + у» означає «двомісна функція», значення якої в кожній парі (х, у) Алгоритмічні проблеми N2 є х+ у.

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

3. Відношення і предикати

Якщо А – множина, то властивість М(х1,…, хn), що виконується на деяких n-ках з Аn і не виконується (чи помилкове) на всіх інших n-ках з An, називається п-місним відношенням, чи предикатом на А.

Наприклад, властивість х<у є двомісне відношення (чи предикат) на N; 2 < 3 виконується (чи істинно), тоді як 9 < 5 не виконується (чи хибно). Інший приклад: кожна n-місна функція f з Nn у N приводить до (п + 1) – місцевого предиката М (х, у), що задається умовою:

М (x1,…, хn, у), якщо і тільки якщо f (x1,…, xn) Алгоритмічні проблеми у.

Відношення еквівалентності і порядку. (Читач, не знайомий з цими поняттями, може при бажанні відкласти читання цього параграфа доти, поки він не буде потрібен в гл. 9.) У гл. 9 ми зустрінемося із двома спеціальними видами відносин на множині А.

(a) Бінарне відношення R на множині А називається відношенням еквівалентності, якщо для всіх х, у, zАлгоритмічні проблемиА виконуються три наступні властивості:

(i) (рефлективність) R (х, х);

(іі) (симетрія) R (х, y)Алгоритмічні проблеми R (у, х);

(iii) (транзитивність) якщо R (x, y) і R (у, z), то R (х, z). Говорячи, що х, y еквівалентні (у деякому спеціальному змісті), ми маємо на увазі відношення R (х, у). Потім ми визначаємо клас еквівалентності х як множина {у | R (х, у)}, що складається з всіх елементів, еквівалентних х.

(b) Двомісне відношення R на множині А називається частковим порядком, якщо для всіх х, у, z Алгоритмічні проблеми A.

(i) (іррефлексивность) не R (х, х);

(іі) (транзитивність) якщо R (х, у) і R (y, z), те R (x, z).

Частковий порядок звичайно позначається символом <, і ми віддаємо перевагу запису х < у запису < (х, у). Часто визначають частковий порядок, вводячи спочатку предикат < (позначающий < чи =) із властивостями:

(i) хАлгоритмічні проблемих;

(ii) якщо xАлгоритмічні проблемиy і уАлгоритмічні проблемих, те х=у;

(iii) відношення Алгоритмічні проблеми транзитивно, а потім визначаючи х < у як хАлгоритмічні проблеми у и х Алгоритмічні проблемиу.

4. Логічні позначення

Ми скрізь вживаємо стандартні логічні позначення. Символ Алгоритмічні проблеми позначає еквівалентність по визначенню, Алгоритмічні проблеми означає логічне слідування, а Алгоритмічні проблеми позначає «випливає з». СимволиАлгоритмічні проблеми, Алгоритмічні проблеми використовуються в значенні «для всіх» і «існує» відповідно.


3. Операторні та предикатні алгоритми – І


(Рекурсивні функції на області натуральних чисел N)

Розглянемо математичне визначення [1,2] класів функцій та предикатів, що вважаються точним аналогом інтуїтивного поняття алгоритму (взагалі кажучи, часткового).

1. Введемо зчисленні множини символів або послідовностей символів (слів, ідентифікаторів і т. п.) із довільної конструктивної множини:

а) індивідні: x, y, z, x0, y0, z0, x1, y1, z1,… xj, yj, zj,…;

б) функціональні: f, g, h, f0, g0, h0, f1, g1, h1,… fj, gj, hj,…;

в) предикатні: P, Q, R, P0, Q0, R0, P1, Q1, R1,… Pj, Qj, Rj,…;

г) константи: a, b, c, a0, b0, c0, a1, b1, c1,… aj, bj, cj,…;

д) мітки: q, i, j, q0, i0, j0, q1, i1, j1,… qk, ik, jk,…

Кожній функціональному та предикатному символу U однозначно ставиться у відповідність натуральне число n, яке називається арністю даного символа. Цей символ позначається через U(n), або U (x1, x2., xn) та т. п., і називається n-арним символом. Вважається, що ідеалізований об'єкт – 0-арний функціональний символ U(0) співпадає з символом константи.

Схемою оператора присвоювання називається вираз виду:


z(i) = f(m) (x(1)., x(m)). (1)

Схемою оператора пересилки називається вираз виду:


z(k) = y(j) (2)


Схемою прісвоювання константи називається вираз виду:


z(k) = a, або z(k) = fj(0) (3)


Схемою умови називається вираз виду:


P(s) (x(1)..x(s)) (4)


Схемою програми (СП) S називатимемо об'єкт виду


q0 Ф[0] (i0, j0)

q1 Ф[1] (i1, j1)

……………. (5)

qs Ф[s] (is, js)

В (1) Qs = Qs1 u Qs2, де Qs1 = q0, q1..qs, і


Qs2=i0, j0., is, js – підмножини множин міток. Як правило, якщо не вказане уточнення, будемо вважати, що qi – qj, якщо i – j, (qi, qj належать Q1). Мітки із Q1 називаються мітками передачі управління, а мітки із (Qs – Qs1) – кінцевими мітками.

Для всіх k є [0_s], Ф[k] – це одна із схем (1) – (4).

Сукупність всіх індивідних змінних СП (5) називається пам "яттю схеми S. Сукупність константанктних, функціональних, предикатних символів і пам" яті S називається сигнатурою, або базисом, схеми S.

Конструкція вигляду

qr Ф[r] (ir, jr)

із (5) називається схемою команди.

Схемою операторного алгоритму (СОА), або схемою операторної процедури, називається об"єкт виду:


SA= (x1, x2., xn; S; y), (6)


де x1., xn, y – змінні, S – СП вигляду (5).

Схемою предикатногоо алгоритму (СПА), або схемою предикатної процедури, називається об"єкт виду:


SP= (x1, x2., xn; S; q [.t.], q [.f.]), (7)


де x1., xn, – змінні, S – СП вигляду (5), а q [.t.], q [.f.]) – кінцеві мітки СП S.

Зауважимо, що пам "яттю алгоритмів (6), (7) називається об" єднання пам"ятті S і змінних

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: