рефераты бесплатно
Рефераты бесплатно, курсовые, дипломы, научные работы, курсовые работы, реферат, доклады, рефераты, рефераты скачать, рефераты на тему, сочинения,рефераты литература, рефераты биология, рефераты медицина, рефераты право, большая бибилиотека рефератов, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент и многое другое.
ENG
РУС
 
рефераты бесплатно
ВХОДрефераты бесплатно             Регистрация

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

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

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


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 (х) не визначена, якщо xDom(f). Множина х  Dom (f) називається множиною значень, чи образом (range), функції f і позначається через Ran (f). Якщо А и В – множиниі, то будемо говорити, що f є функція з A в В, якщо Dom (f)A и Ran(f)В. Коли Dom(f)=A, буде застосовуватися позначення f: Ar.

Функція називається ін’єктивною, якщо з х, у 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)=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/xDom(g) і g(x)Dom(f)}, значення якої, коли вона визначена, є f (g(x)). Цю функцію позначають через fg.

Через 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 функцію NN, значення якої усюди дорівнює т, ми позначаємо жирним символом т.

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

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

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

М (x1,…, хn, у), якщо і тільки якщо f (x1,…, xn)  у.

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

Страницы: 1, 2, 3, 4


© 2010.