Дискретная математика. Кулабухов С.Ю. - 128 стр.

gLAWA   VII.   oSNOWY TEORII ALGORITMOW

                                   Tg , Tg Th , Tg Th Th , : : :, Tg T| h :{z: :Th}
                                                                          m+1
BUDET RABOTATX WE^NO. tAKIM OBRAZOM, FUNKCIQ f TAKVE WY^ISLIMA I NAMI POKAZANO, FAKTI^ESKI,
^TO PRIMENENIE OPERATORA PRIMITIWNOJ REKURSII K WY^ISLIMYM FUNKCIQM DAET W REZULXTATE
FUNKCI@ WY^ISLIMU@.
pRIMER 1. pOKAVEM, ^TO FUNKCIQ f(x
 y) = x + y MOVET BYTX POLU^ENA IZ PROSTEJIH PRI
POMO]I SUPERPOZICII I PRIMITIWNOJ REKURSII. pOLOVIM:
                                          g(x) = I11 (x)

                                          h(x
 y
 z) = s(I33 (x
 y
 z)):
   tOGDA:
                                       f(x
 0) = g(x)

                                f(x
 z + 1) = h(x
 z
 f(x
 z)):
   uBEDITESX W \TOM SAMOSTOQTELXNO.
   1.6. oPERATOR MINIMIZACII. bUDEM GOWORITX, ^TO n-MESTNAQ, n 2 N, ^ASTI^NAQ FUNK-
CIQ f POLU^ENA IZ n-MESTNOJ ^ASTI^NOJ FUNKCII g PRI POMO]I OPERATORA MINIMIZACII I OBO-
ZNA^ATX
                               f(x1 
 : : :
 xn) = y g(x1 
 : : :
 xn;1
 y) = xn ]

ESLI WYPOLNENO USLOWIE: f(x1 
 : : :
 xn) OPREDELENO I RAWNO y TOGDA I TOLXKO TOGDA, KOGDA
                 g(x1 
 : : :
 xn;1
 0)
 g(x1
 : : :
 xn;1
 1)
 : : :
 g(x1
 : : :
 xn;1
 y ; 1)
OPREDELENY I NE RAWNY xn, A g(x1 
 : : :
 xn;1
 y) = xn.
   lEGKO PONQTX, ^TO WSQKAQ n-MESTNAQ ^ASTI^NAQ FUNKCIQ g I OPREDELENNYJ WYE OPERATOR
MINIMIZACII OPREDELQ@T ODNOZNA^NO NEKOTORU@ n-MESTNU@ ^ASTI^NU@ FUNKCI@ f.
   oTMETIM, ^TO ESLI T | ALGORITM, WY^ISLQ@]IJ ZNA^ENIQ FUNKCII g, A BUKWA H OBOZNA^AET
ALGORITM SRAWNENIQ DWUH NATURALXNYH ^ISEL, TO
                                               (TH)(TH)(TH) : : :
ESTX ALGORITM, WY^ISLQ@]IJ FUNKCI@ f. dEJSTWITELXNO, ESLI ZNA^ENIE FUNKCII f(x1 
 : : :
 xn)
OPREDELENO I RAWNO y, TO POSLE ISPOLNENIQ SLEDU@]EJ ^ASTI
                                              (TH)(TH){z: : :
 (TH)}
                                              |
                                                        y+1
UKAZANNOGO WYE ALGORITMA BUDET WY^ISLENO ZNA^ENIE y. eSLI VE f(x1 
 : : :
 xn) NE OPREDELENO,
TO \TO ZNA^IT, ^TO LIBO g(x1 
 : : :
 xn;1
 i) (i 2 N0 ) NE OPREDELENO, LIBO ZNA^ENIQ g(x1 
 : : :
 y)
OPREDELENY DLQ L@BOGO y 2 N0 I, WMESTE S TEM, g(x1 
 : : :
 xn;1
 y) 6= xn DLQ L@BOGO y 2 N0 . |TO
ZNA^IT, ^TO W PERWOM SLU^AE i-Q KOMPONENTA (TH) ALGORITMA
                                            (TH)(TH)(TH) : : : 

BUDET RABOTATX WE^NO, A WO WTOROM SLU^AE KAVDAQ KOMPONENTA \TOGO ALGORITMA NA OPREDELENNOM
AGE ZAKON^IT SWO@ RABOTU, NO TAK KAK SRAWNENIE DWUH NATURALXNYH ^ISEL NIKOGDA NE DAST VE-
LAEMOGO REZULXTATA, TO WESX \TOT ALGORITM BUDET RABOTATX WE^NO. tAKIM OBRAZOM, NAMI DOKAZANO,
^TO PRIMENENIE OPERATORA MINIMIZACII K WY^ISLIMOJ FUNKCII DAST FUNKCI@ WY^ISLIMU@.
pRIMER 1. pOKAVEM, ^TO
                                    x ; y = z y + z = x]:
dEJSTWITELXNO, ESLI x  y
 TO WSE ^ISLA y + 0
 y + 1
 : : : OPREDELENY I ODNO IZ NIH RAWNO x. eSLI
y + r = x, TO r = x ; y. eSLI VE x < y, TO NI ODNO IZ ^ISEL y + 0
 y + 1
 : : : NE SOWPADAET S x I
POTOMU
                                            x ; y = z y + z = x]
NE OPREDELENA.
                                                        128