22941

Конструктивні обєкти. Індуктивні визначення. Рекурсивні функціїї

Лекция

Информатика, кибернетика и программирование

Рекурсивні функціїї. При такому підході конструктивність того чи іншого об’єкту у тому числі і функції вже не є абсолютною субстанцією а тільки відносною і залежить від вибору системи подання. Загальне індуктивне визначення унарної функції ІВФ спирається на ІВ множини і має вигляд: БФ База індукції. Для кожного конструктора елементів з існує конструктор значень функції такий що для будьяких .

Русский

2013-08-04

854 KB

0 чел.

  

ТЕМА: Конструктивні об'єкти. Індуктивні визначення. Рекурсивні функціїї.

1. Конструктивні об’єкти.  Як вже зазначалось, характеристичною властивістю інформаційних систем є їх конструктивність.  Конструктивність об’єктів та відношень інформаційної системи означає, що вони можуть бути побудовані зі своїх складових за допомогою спеціальних операцій - конструкторів. Сукупність   атомних елементів та конструкторів, що дозволяють побудувати всі  об’єкти та відношення даної системи будемо  називати системою її подання. Принциповим є те, що на відміну від класичних алгебраїчних систем, де атомні елементи (твірні) та конструктори (основні операції) належать самій системі, системи подання інформаційних моделей, як правило, є зовнішніми по відношенню до них. Наприклад, вони  можуть належати певній мові програмування.  При такому підході  конструктивність того  чи іншого об’єкту (у тому числі і функції ) вже не  є абсолютною субстанцією,  а тільки  відносною і  залежить від вибору системи  подання. Взагалі, до конструктивних ми будемо відносити  будь-які індуктивно визначені об’єкти. Структура індуктивного визначення  (ІВ)   певної множини об’єктів М  має такий вигляд:

(Б) База індукції. Фіксується певна підмножина апріорі вибраних   базових (атомних) об’єктів.

(І) Індуктивний перехід. Вибирається певна сукупність  конструкторів – операцій на  M, замкнених відносно M. Замкненість конструктора відносно М означає, що результат його застосування гарантовано належить множині М при умові, що він був застосований до аргументів з  М.

(П) Повнота. Конструктори дозволяють за скінчену кількість кроків отримати  з  базових елементів кожен з об’єктів  множини M   і тільки їх.

Оскільки вся сукупність об’єктів в індуктивних визначеннях  повністю  описується пунктами (Б)  і (І), то, як правило, пункт (П) Повнота явно не формулюється. Індуктивно визначені множини  будемо називати просто індуктивними і позначати .  Іноді принцип Повноти послаблюють, замінюючи  на пункт

(ПС) Повнота Слабка. Конструктори дозволяють за скінчену кількість кроків отримати  з  базових елементів кожен з об’єктів  множини M( але можливо і не тільки їх).

Тоді потрібні конструктивні елементи відбираються за допомогою певного предикату-фільтру . Будемо називати такі фільтри       термінаторами. Елементи, які їм задовольняють, – термінальними, а всю сукупність термінальних елементів в  будемо позначати . Так, добре відома роль  в теорії формальних граматик та С СД (БНФ)  предикату-фільтру = ”. Наведемо кілька важливих прикладів конструктивних об’єктів.

Прикл.

1). Натуральні числа.  (ІВ).

(Б)    - натуральне число .

(І)   Конструктор  succ: породжує наступне за порядком число

в  N ,  тобто  ( succ(n)=n+1 ).

Дійсно,       0                                                           Б          

                   1=succ(0)                                             І         

                   2=succ(1) = succ(succ(0))                   І    

                     і т. д.

2. Слова. (ІВ) Нехай - довільна лінійно упорядкована сукупність, елементи якої назвемо символами, а  саму її алфавітом. Для  покладемо

                    .

Кортежі  з  будемо називати словами  над алфавітом   довжини   n. 

Сукупністю всіх слів над    будемо називати  множину . Порожнє слово має довжину 0 . Будемо позначати його  .

 ІВ слів над   має вигляд:

(Б)    -  порожнє  слово   та букви алфавіту  є базовими.  

(І)Конструктор  визначимо так:                    .

(ПВ) Фільтр-термінатор .

Як бачимо,  базові елементи - символи алфавіту - не входять до (односимвольні слова мають вигляд ).

Наведемо інше індуктивне визначення (ІВ) слів над  :

(Б)    - слово   над  .

( І)Для кожного  визначимо kонструктор  

                ,  .

 У цьому випадку  слово  будується у зворотньому порядку  .

3). Структурні схеми (блок-схеми в лінійній формі). (ІВ) Нехай  F=  -  певна сигнатура унарних функціональних символів.

(Б) Сигнатурні символи з - базові структурні схеми.

(І) Для структурних схем  P,    визначимо нові структурні       схеми:   begin   end ,     if P  then S else S fi,  while P  do S  od   .

Структурні схеми  вигляду (І)  використовуються для подання  структурних блок схем.

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

   (Б)  База індукції:    .

   (І)   Індуктивний перехід : для всіх конструкторів

                            .

   (П) Повнота:   .

З  Бази індукції (Б)  та Індуктивного переходу (І)    випливає  Повнота (П). Дійсно, покладемо . З   (Б) випливає, що  , а з  (І),  що .  Оскільки , то маємо .

Таким чином, щоб встановити   (П)  достатньо  перевірити  базу індукції  (Б)  та   правило індуктивного переходу  (І). Звичайна математична  індукції для натуральних чисел є частковим випадком структурної індукції.

Структурна індукція для  слів  має вигляд:

                     (Б)      .

                   (І)        або

                   (І)      .

                  (П)       .

Приклад застосування метода структурної індукції наведемо в наступному розділі.

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

(БС) База індукції. Фіксується  підмножина   базових об’єктів.

(ІС) Індуктивний перехід. Вибирається певна сукупність  конструкторів – багатосортних операцій на . Кожний аргумент конструктора та його результат належать певному фіксованому сорту. Результат  застосування конструктора гарантовано належить сорту-результату, при умові він був застосований до аргументів відповідного сорту (замкненість конструктора).

(ПС) Повнота. Конструктори дозволяють за скінчену кількість кроків вивести   з  аксіом кожен з об’єктів  множин , ,  і тільки їх.

Система множин  замкнена відносно певних конструкторів , якщо кожна з компонет  замкнена відносно них. Як і у випадку звичайних ІВ,  система  є найменшою замкненою відносно даних конструкторів системою множин, породжених  базою . Порівняння здійснюється     по компонентно.

 Нехай  , , - фільтри-термінатори,  визначені на сортах . Пункт  (ПС) Повнота  в індуктивних визначеннях систем множин теж може   замінюватись  на пункт:

(ПВС) Повнота Відносна. Конструктори дозволяють за скінчену кількість кроків отримати  з  базових елементів кожен з об’єктів  множин , ,   що задовольняють фільтрам-термінаторам .

2. Індуктивні визначення функцій. Конструктивні об’єкти допускають індуктивні визначення функцій та операцій (ІВФ). На таких визначеннях, як відомо, побудована значна частина конструктивної математики та програмування. Вони теж складаються з бази індукції (БФ), індуктивного переходу (ІФ) та повноти (ПФ). Розглянемо спочатку (ІВФ) на прикладі основних операцій на словах.

Операція  - конкатенація  слів:

   (БФ)   

(ІФ)  для  кожного .

Визначення коректне. Дійсно, знайдемо, наприклад, значення

                            І

                                   =             І

                                   =             І

                                   =                           Б

                                   =                                 І

                                   =                                       І.

Домовимося про деякі спрощення позначень. Так, слово   будемо позначати  традиційно  . Замість запису   будемо  вживати   або  .  Замість   будемо писати  a^w, замість    -  w^a,  або  просто  аw  та  відповідно  wa .    

Операція   повертає  перший символ (голову) слова, операція - останній символ слова:

   (БФ)     ,  

   (ІФ)      , ,.

     Операція  -  повертає хвіст слова, тобто слово без його голови:

   (БФ)         (І)     .

Операція  -  повертає слово без останнього символу:

   (БФ)         (ІФ)     ,  .

Функція  обчислює довжину слова:

   (БФ)          (ІФ)     .

Позначимо Bool множину булевих  значень, відповідно “хиба” та “істина”. Визначимо операцію   вибору так, що  і   для будь-яких  a, b.

Предикат  визначає  лексикографічний  порядок (нестрогий ) на  словах над алфавітом . Нагадаємо, що символи алфавіту  лінійно впорядковані : для будь-яких i,j. Тоді для  довільних   

    (БФ)     

   (ІФ)                 

Далі  лексикографічний порядок будемо позначати просто “”.

Наприклад,   для довільних символів  таких, що :

,   ( )  =   ( ) =   ( )  = ,

( ) =  ( ) =  = ,

( ) =   =  = .

Прикл. Доведення методом структурної індукції.  Доведемо асоціативність  операції  конкатенації. Покладемо  .

Перевіримо спочатку базу індукції (Б). Нехай - довільні слова над . Тоді  з  (Б) випливає , що        і       .     

А це означає, що  виконується. Нехай  - довільні  слова над  , а  - довільний символ. Перевіримо правило індуктивного переходу ( I).   У нашому випадку конструктор один – операція  pre.

                                           (I)

                                                           (I)

                                                           P

                                                            (I)  .

Отже ,  індуктивний перехід   ( I)  має місце. А за ним -  і повнота (П).

Нехай M= – довільна індуктивна множина. Загальне  індуктивне визначення унарної функції (ІВФ)  спирається на  ІВ  множини  і  має  вигляд:

(БФ) База індукції. , де  -“відома” функція, що задана апріорі на підмножині  .  

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

(ПФ) Повнота. Функція та конструктори дозволяють за скінчену кількість кроків отримати кожне зі значень функції  на  M   і тільки їх.

Індуктивно визначені функції будемо називати ІВ-функціями. Зазначимо, що деякі аргументи в конструкторі можуть бути фіктивними, а в якості конструктора може використовуватись  і сама функція . ІВ-функції у загальному випадку багатозначні. Однозначність ІВ-функції  гарантують наступні дві умови (але вони не є необхідними): 1) області значень будь-яких двох конструкторів та  не перетинаються і 2) для кожного  існує тільки одна сукупність складових така, що . Остання умова  виконується, наприклад,     у випадку взаємно однозначних конструкторів.

Прикл.  1) Наступне ІВФ спирається на це індуктивне визначення слів  і задає функцію  , що обчислює довжину слова:

  (БФ)           (ІФ)     .

2) Обчислення ваги  зваженого Б-дерева. Нехай - сукупність зважених вершин дерева.   ІВ Б-дерев:    (Б)      - порожнє Б-дерево;     (І) Для    та  довільних Б-дерев   вираз - Б-дерево.

Нехай БД - сукупність всіх зважених Б-дерев. Функція  задає вагу Б-дерева: (БФ)  (ІФ)   .

Як і у випадку індуктивних множин,  пункт  Повноти (ПФ) може  замінюватись  на Повноту Відносну. А саме,

(ПВФ) Повнота Відносна. Функція та конструктори  дозволяють за скінчену кількість кроків отримати кожне зі значень функції  на  M, що задовольняє певному фільтру-термінатору  . 

Аналогічний вигляд мають індуктивні визначення функції від кількох змінних та систем взаємно індуктивних функцій. Останні особливо важливі в застосуваннях. Обмежимося для простоти випадком бінарних функцій. Для арних функцій визначення будуть аналогічними. Нехай M та  – довільні індуктивні множини. Домовимося послідовність вигляду  ,…,  записувати скорочено . ІВФ  функції   має  вигляд:

(БФ) База індукції. , де  - “відома” функція, що задана на множині пар базових елементів множин  M та  . Функція може задавати значення функції  і на більш широкій області , при умові, що  вони є  надмножинами множини  .

(ІФ) Індуктивний перехід.  Для кожної  пари  конструкторів ,  елементів множин  M та   існує конструктор  значень функції такий, що для будь-яких ,:  

(ПФ) Повнота. Функція  g та конструктори  дозволяють за скінчену кількість кроків отримати кожне зі значень функції  на  M   і тільки їх.

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

(БФ) , (ІФ)  .

Єдиним конструктором  тут виступає  операція додавання.

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

(БФ)  

(ІФ)=  

Коректність ІВФ просто довести структурною індукцією по .

         Як і у випадку унарних функцій,  у якості конструктора може використовуватись  і сама функція . На відміну від унарних функцій, така можливість значно розширює можливості ІВФ.

Індуктивні визначення  систем функцій (ІВФС) розглянемо на прикладі бінарних функцій  вигляду  , де . ІВФС системи функцій   має  структуру:

(БФС) База індукції. , , де  - “відомі” функція, задані у загальному випадку на надмножинах пар базових елементів.

(ІФС) Індуктивний перехід.  Для кожної функції  , , та пари  конструкторів ,  існує конструктор  значень функції такий, що для будь-яких ,:  

(ПФС) Повнота. Функції  g та конструктори  дозволяють за скінчену кількість кроків отримати кожне зі значень функцій  , , на  парах аргументів  з  M  і тільки їх.

Усі наведені ІВФ мають одну спільну рису – значення функції на своїх аргументах при індуктивному переході визначаються за допомогою значень функції на складових її аргументів. Таку індукцію будемо називати індукцією типу  згортки. Іншим, дуальним, варіантом  індуктивних визначень функцій є індуктивних визначень функцій типу   розгортки, коли значення функції на  аргументах при індуктивному переході визначаються за допомогою значень функції на заданих або нових аргументах,  отриманих з заданих за допомогою конструкторів. У цьому випадку База індукції задає умову завершення індуктивних переходів по всьому фронту  області її визначення. Прикл. Функції Аккермана  (дуже швидко зростають).

(БФ) ,

(ІФ)  .

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

Загальне ІВФ функції   типу розгортки  має  вигляд:

(БФ) База індукції. , де  - “відома” функція, що задана на деякій підмножині пар .

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

(ПФ) Повнота. Функція  g та конструктори  дозволяють за скінчену кількість кроків отримати кожне зі значень функції  на M      і тільки їх.

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

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

Прикл.

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

(БФС) для всіх  ,  для всіх               і в  не має дільників менших від .

(ІФС)  Для будь-яких ,:  

              = ,

           =

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

2) Нехай ,,. У наступному  прикладі функція   генерує всі розв'язки відомої комбінаторної задачі про  ферзів. Інші функції  в системі: , , , ,  ,  ,  , є допоміжними. В задачі необхідно знайти всі позиції ферзів на шаховій дошці розміром , в яких вони не загрожують один одному. Конфігурації ферзів  подаються словами в алфавіті . Слово  подає конфігурацію трьох ферзів. Вони розташовані  у перших трьох вертикалях дошки: на 1-й вертикалі  ферзь стоїть на 6-й клітині (нумерація клітин вертикалі починається з 0), на 2-й вертикалі -  на 4-й позиції і на  третій вертикалі – на  1-й позиції. Функція BackTrack реалізує бектрекінг і генерує найближчу (у лексикографічному порядку)  до x вірну конфігурацію ферзів, розташованих у перших кількох підряд вертикалях. Якщо довжина чергової   вірною конфігурації є n, то вона долучається до списку. Відповідне ІВФС має вигляд:

(БФС) BackTrack,  ,  для  ,  для  ,  для довільного , .

(ІФС)  Для будь-яких  , , , :  

             , BackTrack  =  =

, , , , ,

= ,  = ,

= .

Корректність  визначень ІВФС та   ІВФС   можна перевірити структурною індукцією.

3) Обчислення кількості комутативних розбиттів числа   (РП 7.7 ). Нпр., . ( 1+2  та 2+1 не розрізнюються).

 Задамо індуктивно іншу функцію   ,  - кількість комутативних розбиттів числа  з доданками, що не перевищують . Очевидно, .

(БФ)  

(ІФ)  

Трансформація індуктивних специфікацій  функцій у МП.  Специфікацією функції називається її визначення (опис)  в певній ЗС.    

1) Сучасні МП високого рівня,  або прямо підтримують ІВ таких важливих структур даних як натуральні числа, послідовності однотипних елементів (числові, символьні та ін. ), Б-дерева,  списки (у тому числі і списки списків) и т.д. (мови Lisp, Меta IV, Z, RSL,   HOPE, МL, Python та ін. )  або дозволяють ефективно моделювати такі структури за допомогою покажчиків (Паскаль,  Сі, Сі, …).

2) МП високого рівня, як правило, допускають рекурсивні виклики процедур та функцій. Сі-функція називається рекурсивною, якщо її тіло містить власні виклики.   

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

Прикл. 

1)  /*  Швидке піднесення до степеня n>=0 */

    double spow1 (double a, unsigned int n )

      {

           if (n==0) return 1;

           if (n%2) return  a*spow1(a, n/2)*spow1(a, n/2);

           else  return spow1(a, n/2)*spow1(a, n/2);

      }

double spow2 (double a, unsigned int n )

      { double p;

            p= spow2(a, n/2);

           if (n==0) return 1;

           if (n%2) return ( a*y * y);

           else  return (y*y);

      }

2)    /*  Комутативне розбиття числа   ІВФ*/

        long q(long n, long m)

        {

           if (n==1 || m==1) return 1;

           return (m>= n ? 1+ q(n,n-1) : q(n-m,m)+ q(n,m-1));

         }

        

        long f(long n)

        { return q(n,n);

        }

3)    /*  розклад натурального числа на прості множники  ІВФ*/

        void g(long x, long y)

        {

           if (x==1) printf(“1”);

              else if  (x <y*y ) printf(“%dl”, x);

                            else if  (x%y==0) {printf(“%dl : ”, y); g(x/y, y);}

                                        else g(x,y+2);

         }

        

        long f(long x)

        { if  (x%2==0) {printf(“2 : ”); f(x/2);}

                                        else g(x,3);

        }

Нпр.,  виклик  f(24)    виведе на екран :

2:2:2:3:1

4)  Ханойські вежі (ІВФ).   Результуюча послідовність пар операцій буде подана у стандартному вихідному потоці stdout  у вигляді:

    …

  /*  Ханойські вежі  ІВФ*/

   void hanoi (short n,  short x, short y)

        {  

             if  (n<1 ||  x<1 ||  y<1 ||  x>3 ||  y>3 )  {printf(“Помилка в даних ”); return; }

             if  (n==1) printf(“<%d,% d> ”, x,y);

                      else { hanoi (n-1, x,6-x-y); printf(“<%d,% d> ”, x,y);  hanoi (n-1, 6-x-y, y); }

        }


 

А также другие работы, которые могут Вас заинтересовать

32039. Оценка финансового состояния ОАО «НГПЭ» 368 KB
  ОАО «НГПЭ» была зарегистрирован Новосибирской регистрационной палатой 19 января 2004 года по адресу г. Новосибирск, ул. Боровая партия д.12. ОАО «НГПЭ» занимается ведением геологоразведочных, геофизических и геохимических работ в области изучения недр на территории города Новосибирска и новосибирской области.
32043. Управління маркетинговою діяльністю підприємства (на прикладі ТОВ «Місто - Д») 579.68 KB
  Пропонуємо нову методику маркетингового аналізу та аудиту підприємства та застосування маркетингу, яка апробована при аналізі підприємства ТОВ «Місто - Д», провести модернізацію організаційної структури підприємства, провести вихід підприємства на ринки сусідніх областей, ввести ефективну систему маркетингового контролю. Це збільшить ефективність і швидкість роботи, збільшить прибутки, оптимізує загрузку на всіх працівників маркетингової служби, розширить діяльність підприємства.
32044. Формування маркетингової стратегії підприємства 889.5 KB
  Тема дипломної роботи: Формування маркетингової стратегії підприємства Затверджена наказом по університету № 127дс від 25 грудня 2009 р. Цільова установка та загальний напрямок дипломної роботи для робіт технічного профілю також вихідні дані: проаналізувати особливості формування маркетингової стратегії організації та запропонувати заходи з її вдосконалення. Теоретичні основи формування маркетингової стратегії 1. Етапи розробки маркетингової стратегії Розділ 2.
32045. Соотношение корня слова и основы слова 22 KB
  Соотношение корня слова и основы слова Все морфемы можно разделить на два больших класса: корни и аффиксы ffixus от лат – прикрепленный. Основа может состоять из одного корня например дом из корня со словообразовательным суффиксом одним или несколькими например домик красный ый окончание красненький ий окончание; из корня и приставки например пригород ; из корня приставки и суффикса например сделать ть суффикс инфинитива не входящий в основу выражает роль которую играет глагол в предложении.
32046. Организация Web-доступа в среде zLinux на сервере z9 BC 657 KB
  Целью работы является обеспечить webдоступ на сервер z9 BC используя программное обеспечение установленное на IBM z9 BC а именно HTTP сервер pche. Webсервер pche будет предоставлять доступ к ресурсам сервера пользователям подключенным к внутренней сети. Webсервер pche [7.1 Описание webсервера pche [7.
32047. Подготовка и защита выпускных квалификационных работ 328.5 KB
  Состав дипломной работы и требования к её выполнению. Выполнение исследовательских задач и написание основных разделов дипломной работы.40 Изложение и оформление дипломной работы.42 Оформление дипломной работы.