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

UptoLike

ВУЗ: 

ИСОиП ДГТУ | Шахты

Составители: 

Рубрика: 

   x   4.   aLGORITMI^ESKI NERAZRE IMYE PROBLEMY
     aLGORITMI^ESKIE PROBLEMY nEWY^ISLIMYE FUNKCII rEKURSIWNYE MNOVESTWA pROBLEMA
                                .                                .                .

     OB]EZNA^IMOSTI FORMUL ALGEBRY PREDIKATOW dIOFANTOWY URAWNENIQ
                                                     .                        .


   aLGORITMI^ESKAQ PROBLEMA | \TO PROBLEMA, W KOTOROJ TREBUETSQ NAJTI EDINYJ METOD (ALGO-
RITM) DLQ REENIQ BESKONE^NOJ SERII ODNOTIPNYH ZADA^. tAKIE PROBLEMY WOZNIKALI I REALISX
W RAZLI^NYH OBLASTQH MATEMATIKI NA PROTQVENII WSEJ EE ISTORII. pRIMERY TAKIH PROBLEM RAS-
SMATRIWALISX W x 1.
   uVE OTME^ALOSX, ^TO W NA^ALE XX WEKA U MATEMATIKOW NA^ALI POQWLQTXSQ PODOZRENIQ, ^TO NE-
KOTORYE ALGORITMI^ESKIE PROBLEMY NE IME@T REENIQ. w SWQZI S \TIM WOZNIKLA NEOBHODIMOSTX
DATX TO^NOE OPREDELENIE SAMOMU PONQTI@ ALGORITMA. mY POZNAKOMILISX S NESKOLXKIMI SPOSO-
BAMI TAKOGO UTO^NENIQ, I W \TOM PARAGRAFE PRIWEDEM PRIMERY ALGORITMI^ESKI NERAZREIMYH
PROBLEM.
    4.1. nEWY^ISLIMYE FUNKCII. pUSTX K^R , KWT, KNW | KLASSY ^ASTI^NYH ^ISLOWYH
FUNKCIJ: WSEH ^ASTI^NO REKURSIWNYH, WSEH WY^ISLIMYH PO tX@RINGU I WSEH NORMALXNO WY^IS-
LIMYH SOOTWETSTWENNO. w SOOTWETSTWII S TEOREMOJ 2.5.1 I P. VII.3.4. WSE \TI KLASSY SOWPADA@T:
                                     K^R = KWT = KNW
    eSLI KIW | KLASS WSEH INTUITIWNO WY^ISLIMYH ^ASTI^NYH ^ISLOWYH FUNKCIJ, TO W SOOT-
WETSTWII S TEZISOM ~ER^A (TEZISOM tX@RINGA, PRINCIPOM NORMALIZACII mARKOWA) IMEEM:
                                  KIW = K^R = KWT = KNW :
    uSLOWIMSQ ^ASTI^NYE ^ISLOWYE FUNKCII PREDSTAWLQTX \SLOWARNYMI" FUNKCIQMI W ALFAWITE
f0 1g. nAPRIMER, ESLI
                                      f(x1  x2 : : : xn) = y
TO SOOTWETSTWU@]U@ SLOWARNU@ FUNKCI@, KOTORU@ OBOZNA^IM TOJ VE BUKWOJ f, OPREDELIM TAK:
                        f(11 : : :1} 0 11
                          | {z            : : :1} 0 : : :0 |11 {z
                                       | {z                    : : :1}) = 11 : : :1} :
                                                                          | {z
                                x1         x2               xn            y
   eSLI f | NORMALXNO WY^ISLIMAQ FUNKCIQ, TO ESTX f 2 KNW , TO SU]ESTWUET N. A. m., OPREDE-
LQEMYJ SHEMOJ
                                          B1 ! C11 
                                 8
                                       >
                                       >
                                          B2 ! C22 
                                       >
                                       <
                                     >
                                     >    : : : : : : : : :: : :
                                          Bs ! Cs s
                                     >
                                     :

W NEKOTOROM RASIRENII f0 1g Xf ALFAWITA f0 1g, GDE i 2 f Ig, KOTORYJ SLOWO
                             S


                               11 : : :1} 0 11
                               | {z         | {z: : :1} 0 : : :0 |11 {z
                                                                     : : :1}
                                     x1         x2                   xn
PERERABATYWAET W SLOWO
                                                11 : : :1} :
                                                | {z
                                            y=f (x1 :::xn )
   dLQ KAVDOJ NORMALXNO WY^ISLIMOJ FUNKCII f SHEMA N. A. m. SODERVIT KONE^NOE ^ISLO POD-
STANOWOK, KAVDAQ IZ KOTORYH SODERVIT KONE^NOE ^ISLO SIMWOLOW. tAKIM OBRAZOM, MNOVESTWO Xf ,
KONE^NO, DLQ WSQKOJ NORMALXNO WY^ISLIMOJ FUNKCII. tAK KAK OBOZNA^ENIE SIMWOLOW Xf NE IMEET
ZNA^ENIQ (LIX BY ONI BYLI OTLI^NY OT UVE ISPOLXZUEMYH SIMWOLOW 0 1 ! \ "  ?), TO WZQW W
KA^ESTWE Xf DLQ WSEH f ODNO I TO VE S^ETNOE MNOVESTWO X = fx1 x2 : : :g, WSQKIJ N. A. m., WY^IS-
LQ@]IJ NEKOTORU@ NORMALXNO WY^ISLIMU@ FUNKCI@, MOVNO ZAPISATX W WIDE SLOWA (KONE^NOJ
POSLEDOWATELXNOSTI SIMWOLOW) W ALFAWITE:
                                     I=X
                                            
                                                f0 1 ! \ " ?g
                                                  142

Страницы