Теорія алгоритмів

Метод. Крім масива ЛІВИЙСИН, ПРАВИЙСИН і НОМЕР, алгоритм використовує глобальну змінну РАХУНОК, значення якої- номер наступного вузла в відповідності з внутрішнім розпорядком. Початковим значенням змінної РАХУНОК є 1. параметр ВУЗОЛ спочатку рівний кореню.

А сам алгоритм такий:

Begin

РАХУНОК 1;

ВНУТПОРЯДОК(КОРІНЬ)

End

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

Рекрусивна процедура для внутрішнього порядку.

Procedure ВНУТПОРЯДОК(ВУЗОЛ)

Begin

1. if ЛІВИЙСИН(ВУЗОЛ)0 then

ВНУТПОРЯДОК(ЛІВИЙСИН(ВУЗОЛ));

2. НОМЕР(ВУЗОЛ)РАХУНОК;

3. РАХУНОКРАХУНОК+1

4. if ПРАВИЙСИН(ВУЗОЛ) 0 then

ВНУТПОРЯДОК(ПРАВИЙСИН(ВУЗОЛ))

End

Порівняти складність трансверсального та рекурсивного алгоритмів розв'язування звичайного диференціального рівняння другого порядку

Історично першою алгоритмічною системою була система, основана на використанні конструктивно вичислю вальних арифметичних функцій, отримавши спеціальну назву рекурсивні функції.

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

Чисельні функції, значення яких можна встановити безпосередньо деякого алгоритму, називаються вичисильними функціями. Функція називається рекурсивною, якщо існує ефективна процедура для її обчислення. Поняття ефективна процедура це інтуїтивне. Кажуть, що є ефективна процедура для виконання конкретних обчислень, якщо ці обчислення виконуються по механічним правилам, тобто по конкретному алгоритму.

Оскільки поняття алгоритм береться в інтуїтивному значенні, то і поняття обчислювальної функції виявляється інтуїтивним. Але при переході від алгоритмів до обчислювальних функцій виникає одна дуже важлива обставина: сукупність процесів, які попадають під інтуїтивне поняття алгоритму, дуже обширна і мало розглянута. Сукупність обчислювальних функцій для самих різних понять процесів виявилася тією ж самою і при цьому легко опутаною в звичайних математичних термінах.

Сукупність числових функцій, співпадаючих з сукупністю всіх обчислювальних функцій при самому широкому до цього часу поняття алгоритму, називається сукупність рекурсивних функцій.

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

Після нумерації вхідних і вихідних слів в довільному алфавітному операторі цей оператор перетворюється в функцію у=f(x), в якому аргумент х функція у приймають не позитвне цілочисельне значення. Функція f(x) може бути вичислена не для всіх значень х, але лише для тих, які входять в область обчислення цієї функції.

Подібні частково вичислювальні цілочисельне і цілозначенні функції називаються арифметичними функціями, серед них найбільш прості будемо називати елементарними арифметичними функціями:

- функція тотожна 0 Оⁿ(х₁,х_2,.....х_n)=0, обчислення для всіх негативних значень аргумента;

- тотожність функції,яка повторяє значення своїх аргументів: частий випадок :

- функція безпосереднього слідкування S¹(x)=x=1

також обчислення для всіх цілих значень свого аргументу.

Використовуючи в якості вихідної функції перераховані елементи арифметичної функції, можна з допомогою невеликого числа загальних конструктивних прийомів будувати все більш і більш складні арифметичні функції. В теорії рекурсивних функцій особливо важливе значення мають три операції: суперпозиції, примітивна рекурсія і найменший корінь. Розглянемо кожну з них.

Операція супер позиції полягає в підстановці одних арифметичних функцій замість аргументів других арифметичних функцій.

Операція суперпозиції позначається символом Sⁿ⁺¹ , де індекс зверху означає число функцій.

Операція примітивної рекурсії дозволяє будувати n+1 місцеву арифметичну функцію по двох заданих функціях, одна з яких є n-місцевою часткова функція f виникає з функції g і h примітивної рекурсії,якщо для всіх натуральних значень х_1,......,х_n, у має:

F(x_{1,……….,}x_n, 0)=g(x_{1,……….,}x_n):

F(x_{1,……….,}x_n, y+1)=h (x_{1,……….,}x_{n ,} y, f(x_{1,……….,}x_n,y)).

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

В зв'язку з цим операцію примітивної рекурсії будемо використовувати і для n=0, кажуть кажуть, що одночасно частична функція f виникає з постоянної одномісної функції, рівна числу а , і двомісцевій частинній функції h, якщо:

F(0)=a$

F(x+1)=h(x, f(x)).

Постає питання, чи для кожного існує функція F і чи буде вона єдиною. Область визначення функції- множина всіх натуральних чисел, тому відповідь на цих два питання позитивний.

Якщо F існує, то з вище описани формул знаходимо:

F(x_{1,……….,}x_n,0)=g (x_{1,……….,}x_n):

f(x_{1,……….,}x_n,m+1)=h(x_{1,……….,}x_n, m, f(x_{1,……….,}x_n,m))

і тому функція визначена однозначно. Таким чином для будь яких часткових n-місць функція g n +2- місць функція h/ n=0,1,2,...... існує тільки одна часткова n +1- місць функція f, яка виникає із g і h примітивної рекурсії. Символічно пишуть f=R(g,h).

Операція найменшого кореня,або операуія мінімізації, дозволяє вичислити нову арифметичну функцію від n змінних з допомогою раніше побудованихарифметичних функцій g(x_1……..,x_n , y) від n+1 змінних.

Для будь-якого набору значень змінних х₁=а₁....., х_n=а_n в якості відповідного значення f(а_1……..,а_n) шуканої функції f(x_1……..,x_n) приймається найменший цілий корінь у=а рівняння g(x_1……..,x_n , y)=0.

У разі неіснуючих цілих коренів у цього рівняння функція f(x_1……..,x_n) рахується не визначеною при відповідних наборі значень змінних.

Арифметичні функції, які можуть бути побудовані з елементарних арифметичних функцій з допомогою операцій суперпозиції називаються частично рекрусивними функціями. Якщо ці функції до того ж виявляються всюди вичисленими, то вони називаються загально рекрусивними функціями.

КОНТРОЛЬНА РОБОТА № 7

Довести алгоритмічну розв'язність лінійного диференціального рівняння з постійними коефіцієнтами

Життєдіяльність людини пов'язана з використанням та провадженням різноманітних явищ, процесів тощо. Кожному явищу властиві певні фізичні величини. Вони мають назви, параметри, характеристики. Часто їх можна визначати кількісно, міряти їх значення. Між різними величинами є взаємні зв'язки -- фізичні закони (наприклад, Ньютона -- в механічних явищах, Ома, Кірхгофа -- в електричних, Фехнера -- в фізіології). Математично закони подаються у вигляді формул. Формули отримуються й при розв'язуванні складених за цими законами рівнянь. Наприклад, значення в точці t = nT_d розв'язку звичайного диференціального рівняння

обчислюється за формулою ("згортки")

де ; T_d -- інтервал (період) відбору значень вхідного збурення х та відліків зникаючої функції a (ядра диференціального рівняння). При цьому потрібно знати n початкових значень х. На рис. 5 наведено граф-схему алгоритму цих обчислень. (Затримка на один такт обчислень аналітично позначається , де .) Пронумеровані точки позначають чарунки ("комірки") оперативної пам'яті обчислювача (значення коефіцієнтів а можуть також знаходитися в оперативній пам'яті).

Рис. 5. Граф трансверсального алгоритму ("згортки", номери відліків винесено в індекс, позначення T_d при цьому не наводиться)

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

Означення 8. Алгоритм, у відповідності з яким розв'язування задачі зведене до виконання за правилами алгебри арифметичних дій називаються обчислювальними.

За допомогою обчислювального алгоритму шукається одне значення функції.

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

Довести алгоритмічну розв'язність задачі знаходження найбільшого спільного дільника цілих чисел

Задача знаходження найбільшого спільного дільника постала при вирішенні проблеми вимірювань -- знаходження масштабу міри. Відомо, що вимірювання є певною процедурою, алгоритмом над вимірюваною величиною та мірою. При порівнянні об'єктів за значеннями їм властивої величини потрібно спочатку вирішити проблему вибору міри та знайти її значення. Для числових величин цю проблему вирішено постановкою та розв'язуванням задачі найбільшого спільного дільника.

Розглянемо цілі числа (натуральний ряд чисел). Всяке ціле, що ділить без остачі a, b,…,l, називається їх спільним дільником. З теорії подільності відома теорема про ділення з остачею:

Теорема 1. Всяке ціле а представляється єдиним чином за допомогою цілого b рівністю

Якщо взяти числа b та r₀, то отримаємо представлення . Далі, розглядаючи послідовно подібним чином числа , легко встановити, що коли r_n+1=0, то r_n буде найбільшим спільним дільником чисел a, b. алгоритм евклід рекурсивний диференціальний

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

арифметичний пристрій з регістрами для результату q₀ та x₀ і регістрами x₁, x₂ для операндів;

пристрій вводу;

пристрій виводу,

та (б) -- системою команд (множиною елементарних операцій арифметичного пристрою процесора):

перемножити операнди;

ділити з відкиданням дробової частини результату (функція ціла частина від числа) та присвоїти знак мінус;

присвоїти регістрові вміст іншого регістру;

перейти на (відповідний) крок (конкретний зміст дивись в наведеному алгоритмі);

ввести число у регістр з пристрою вводу;

вивести число на пристрій виводу;

ЛІТЕРАТУРА

Основна:

Яворський Б.І. Теорія алгоритмів/ Конспект лекцій. - Тернопіль: ТДТУ імені Івана Пулюя, 2000. - 32 с.

Яворський Б.І. Математичні основи представлення знань/ Конспект лекцій. - Тернопіль: ТДТУ ім. Івана Пулюя, 2001.-32 с.

Додаткова:

Алферова. З.В. Теория алгоритмов.- М.: Статистика, 1973.- 164 с.

Вирт. Н Алгоритмы + структуры данных = программы.- М.: Мир, 1985.-406 c.

Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. -СПб: Питер, 2000.-384 с.

Грин Д., Кнут Д. Математические методы анализа алгоритмов.- М.: Мир, 1987.- 120 с.

Громов Г.Р. Очерки информационной технологии. - М.: ИнфАрт, 1992. - 336 с.

Драан Я.П., Сікора Л.С., Яворський Б.І. Основи сучасної теорії стохастичних сигналів: енергетична концепція, математичний апарат, фізичне тлумачення. - Львів: ЕБТЕС, 1999.- 132 c.

Капітонова Ю.В., Кривий С.Л., Летичевський О.А. та ін. Основи дискретної математики.- Київ: Наукова думка, 2002.- 580 с.

Кириллов А.А. Элементы теории представлений. - М.: Наука,1972.-336 с.

Кузьмин И.В., Березюк И.Т., Фурманов К.К., Шаронов В.Б. Синтез вычислительных алгоритмов управления и контроля. - Л.: Техника, 1975. - 248 с.

Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 1984. - 224 с.

Проектирование интегрированных баз данных./ А.А. Стогний, В.Э. Вольфенгаген, В.А. Кушниров и. др. - К.: Техніка, 1987.- 143 c.

Сигорский В.П. Математический аппарат инженера. К.: Техника, 1975.- 768 с.

Экспертные системы. Принципы работы и примеры: Пер. с англ. / А. Брукинг, П. Джонс, Ф. Кокс, и др.; Под ред. Р. Форсайта - М.: Радио и связь, 1987.-234 с.

Яворський Б. І. Математичні основи радіоелектроніки./ В 3-х частинах. - Тернопіль: ТПІ, 1996. - 336 с.

ГОСТ 19428--74. Обработка данных и программирование схемы алгоритмов и программ/ Обозначения условные графические..-- М.: Издательство стандартов, 1975.-- 14 с.

Schalkoff R.J. Artificial Intelligence: an Engineering Approach.- New York: McGraw-Hill Publishing Co., 1990.- 646 p.

Размещено на http://www.allbest.ru/