Застосування теорії індуктивних функцій

Як перший приклад розглянемо задачу котра вже траплялася нам раніше.

Задача 10.1. Напишіть програму, що вводить послідовність цілих чисел, і друкує кількість її максимальних елементів.

Розв’язок. В даній задачі , , . Взявши a=1, b=2, x =2, знаходимо , але Із заперечення критерію індуктивності робимо висновок, що не є індуктивною.

Для побудови її індуктивного розширення F застосуємо стандартний прийом. Спробуємо визначити значення функції на подовженому ланцюгу через її значення на вихідній і елемент . Відомо, що це неможливо зробити ( - не є індуктивною), але наша мета – зрозуміти якої саме інформації не вистачає і додати ї, утворивши функцію . Розглянемо тепер функцію . В тому випадку, якщо вона індуктивна, потрібне розширення побудоване. Інакше повторимо попередні дії і спробуємо виразити через з використанням додаткової інформації . Отримуємо наступного кандидата на роль індуктивного розширення – функцію . При необхідності даний процес може бути продовжений і далі, а його завершення гарантується теоремою про існування індуктивного розширення. В даному випадку.

маємо ,

Ми бачимо, що у якості необхідно взяти функцію , яка обчислює максимальне значення елементів на ланцюжку. Тоді для отримуємо

Ця функція, проте, не визначена на пустому ланцюжку, тому також визначна тільки на . Скориставшись тим, що діапазон представлення цілих чисел на ЕОМ обмежений, в даному випадку можна до визначити F зі збереженням функції переобчислення наступним чином: Integer.MIN_VALUE ( для мови Java). Дійсно, якщо припустити, що найбільшим елементом на порожньому ланцюжку являється представлене мінімальне на ЕОМ ціле число, то , а функція визначається формулою

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

,

то побудоване нами розширення виявиться мінімальним. Тепер можна написати програму, що реалізовує побудований алгоритм.

Текст програми.

public class NumMaxSeq2 { public static void main(String[] args) { int y1 = 0, y2 = Integer.MIN_VALUE; try { while (true) { int x = Xterm.inputInt("x -> "); if (x == y2) { y1 += 1; } else if(x > y2) { y1 = 1; y2 = x; } } } catch (Exception e) { Xterm.println("\nn = " + y1); } }}

Будь-яка помилка при введенні розглядається тут, як завершення послідовності чисел. Імена змінних, наявних в програмі, збігаються з використаними при побудові алгоритму, обчислення виконується за допомогою команд "int y1 = 0, y2 = Integer.MIN_VALUE;", функція G реалізована за допомогою оператора if - else, в якому опущений випадок (так як тоді не потрібно змінювати ні , ні ), а застосування відображення зводиться до друку тільки значення з обчислених та Наступне завдання нам також знайомо.

Задача 10.2. Напишіть програму, яка визначає номер першого елементу, рівного , у послідовності цілих чисел. В тому випадку, якщо число в послідовності не зустрічається покладіть рівним нулю.

Рішення. Маємо , де , а . Якщо , , , то , але , отже не є індуктивною.

Побудуємо її індуктивне розширення . Помітимо, що ,

отже, в якості можно узяти пару , де функція . Ця функція вже індуктивна, оскільки , а перетворення має вигляд

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

Побудоване нами розширення мінімальним не являється, оскільки значення (1,0) не може бути набуте функцією ні на жодному ланцюжку.

Ось програма, що не використовує наявності стаціонарних значень.

Текст програми.

public class First1{ public static void main(String[] args) throws Exception { int x0 = Xterm.inputInt("x0 ->"); int y1 = 0, y2 = 0; try { while (true) { int x = Xterm.inputInt("x -> "); y2 += 1; if ((y1 == 0) && (x == x0)) y1 = y2; } } catch (Exception e) { Xterm.println("\nn = " + y1); } }}

Імена програмних змінних співпадають з використаними при побудові алгоритму, обчислення виконується за допомогою команд "int y1=0, y2=0;", реалізація функції очевидна, а застосування відображення зводиться до друку тільки значення .

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

Текст програми.

public class First2 { public static void main(String[] args) throws Exception { int x0 = Xterm.inputInt("x0 -> "); int y1 = 0, y2 = 0; try { while (y1 == 0) { int x = Xterm.inputInt("x -> "); y2 += 1; if (x == x0) y1 = y2; } } catch(Exception e){ System.exit(0); } Xterm.println("\nn = " + y1); }}

По досягненню кінця послідовності, що вводиться, ця програма не виконує ніяких спеціальних дій (оператор ";" у блоці "catch"). У цій ситуації, як і у разі прийняття функцією будь-якого із стаціонарних значень (), управління просто передається на оператор друку. Вирішимо ще одне завдання.

Задача 10.3. Напишіть програму, яка вводить послідовність дійсних чисел, та друкує середне арифметичне її елементів (для не порожньої послідовності).

Рішення. За умовою завдання , де . Якщо , , (ланцюжок з двох нулів), то , але , отже не являється індуктивною.

Побудуємо її індуктивне разширення . Позначивши через суму елементів послідовності , отримуємо .

Отже, у якості можна узяти пару . Для , де , перетворення задається формулою .

Проектована програма буде простіша, якщо ми зможемо продовжити на зі збереженням . Спробуємо підібрати відповідну пару таку, щоб та . Оскільки,

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

Текст програми.

public class AverSeq{ public static void main(String[] args) { double y1 = 0., y2 = 0.; try { while (true) { double x = Xterm.inputDouble("x -> "); y1 = (y1*y2 + x) / (y2 + 1.); y2 += 1; } } catch(Exception e) { Xterm.println("\nf = " + y1); } }}

Розглянемо завдання дещо іншого типу.

Задача 10.4. Напишіть програму, яка визначає кількість входжень взірця у послідовність символів.

Рішення. Нехай - безліч усіх символів, тоді функція . Якщо , , , то , але , отже не є індуктивною.

Помітивши, що , будуватимемо її індуктивне розширення.

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

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

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

Отримана рівність показує, що - індуктивне розширення , проте воно досить складно і свідомо не яаляється мінімальним, оскільки , і не являються незалежними. У трійки величин є всього чотири допустимі стани, які можна позначити одним числом

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

Для доказу індуктивності досить показати перетворення :

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

Хай , і або , або . Якщо , то в якості можна узяти порожній ланцюжок. Інакше без обмеження спільності можна вважати, що . Ланцюжок закінчується на перших символу зразка , тому якщо в якості узяти останніх символу цього зразку, то +1 , що і завершує доведення мінімальності .

Текст програми.

import java.io.*;public class ABCDSeq { public static void main(String[] args) { DataInputStream in = new DataInputStream(System.in); int f = 0, n = 0; try { while (true) { char x = (char)in.readByte(); if (x=='\n') continue; if (x=='d' && n==3) { f += 1; n = 0; } else if (x=='c' && n==2) { n = 3; } else if (x=='b' && n==1) { n = 2; } else if (x=='a') { n = 1; } else{ n = 0; } } } catch(Exception e) { Xterm.println("f = " + f); } }}

У цій програмі використовується метод "readByte", який дозволяє вводити символи. При цьому символ '\n' також виявляється введеним після того, як користувач натискає клавішу Enter на клавіатурі. Цей символ необхідно ігнорувати, що і реалізується в програмі оператором "if (x=='\n') continue".

Не використані нами раніше оператори "import java.io.*" та "DataInputStream in = new DataInputStream (System.in) " потрібні для виклику методу "readByte". У всьому іншому програма повністю відповідає проведеному перед її побудовою дослідженню.

Завдання для самостійного вирішення

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

Задача 10.5. Напишіть програму, яка визначає кількість мінімальних елементів у послідовності непозитивних цілих чисел.

Вказівіка. В даному випадку для довизначення індуктивного розширення на порожньому ланцюжку немає необхідності використовувати величини Integer MIN_VALUE або Integer MAX_VALUE.

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

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

Вказівка. Продиференцирував по рівність та підставив потім отримаєте співвідношення , які допоможуть побудувати індуктивне розширення вихідної функції.

Завдання 10.8. Напишіть програму, що визначає правильність формули над алфавітом з чотирьох символів . Формула вважається правильною, якщо вона може бути отримана за допомогою наступної НФБН: .

ВКАЗІВКА. Розгляньте наступне індуктивне розширення функції f, де

визначені наступним чином:

= може бути продовжена до правильної формули,

= різниця числа лівих і правих дужок у ,

= останній елемент .

Задача 10.9. Напишіть програму яка визначає номер останнього елемента рівного у послідовності цілих чисел. У тому випадку якщо число у послідовності не зустрічається покладіть

 

 

Джерела

 

 

1. Глибовець М. М. Основи комп’ютерних алгоритмів. Монографія, Київ: Видавничий дім “КМ Академія”, 2003. – С. 452.

2. Глибовець М. М., Глибовець А.М., Проценко В.С. Практикум з мови програмування Сі. Навчальний посібник, Київ, Видавничий дім “КМ Академія”, 2010. - с.365.

3. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков. -- М., Наука, 1988

4. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. -- M.: Изд. дом <<Вильямс>>, 2000.

5. Бадд Т. Об’єктно-ориентированное программирование в действии. -- СПб.: Питер Паблишинг, 1997.

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

7. Грис Д. Наука программирования. -- М.: Мир, 1984.

8. Роганов Е.А. Основі інформатики и программирования. –М.: МГИУ, 2001.–315с.

9. Кнут Д. Искусство программирования, 3-е изд., Т.1. Основные алгоритмы. -- M.: Изд. дом <<Вильямс>>, 2000.

10. Кнут Д. Искусство программирования, 3-е изд., Т.2. Получисленные алгоритмы. -- M.: Изд. дом <<Вильямс>>, 2000.

11. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -- M.: МЦНМО, 2000.