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

                                                                      x 1. rEKURSIWNYE FUNKCII

   dLQ ODNOMESTNOJ FUNKCII g(x) FUNKCI@
                                      f(x) = y g(y) = x]
BUDEM OBOZNA^ATX ^EREZ f ;1 (x) I NAZYWATX OBRATNOJ DLQ f (SRAWNITE S OPREDELENIQMI OBRATNOJ
FUNKCII, IZWESTNYMI wAM IZ KURSOW ALGEBRY, ANALIZA).
  1.7. ~ASTI^NO REKURSIWNYE FUNKCII. tEZIS ~ER^A.
oPREDELENIE 1. ~ISLOWAQ FUNKCIQ f NAZYWAETSQn PRIMITIWNO REKURSIWNOJ ESLI ONA MOVET
                                                                             ,
BYTX POLU^ENA IZ PROSTEJIH FUNKCIJ s(x)
 o(x)
 Im (x1
 : : :
 xn) KONE^NYM ^ISLOM OPERACIJ POD-
STANOWKI I PRIMITIWNOJ REKURSII.
oPREDELENIE 2. ~ASTI^NAQ FUNKCIQ f NAZYWAETSQ
                                           n
                                              ^ASTI^NO REKURSIWNOJ ESLI ONA MOVET
                                                                             ,
BYTX POLU^ENA IZ PROSTEJIH FUNKCIJ s(x)
 o(x)
 Im (x1
 : : :
 xn) KONE^NYM ^ISLOM OPERACIJ POD-
STANOWKI, PRIMITIWNOJ REKURSII I MINIMIZACII.
   oTMETIM, ^TO WSQKAQ ^ASTI^NO REKURSIWNAQ FUNKCIQ QWLQETSQ WY^ISLIMOJ FUNKCIEJ, TAK
KAK NAMI POKAZANA WY^ISLIMOSTX PROSTEJIH FUNKCIJ I POKAZANO, ^TO PRIMENENIE OPERATO-
ROW PODSTANOWKI, PRIMITIWNOJ REKURSII I MINIMIZACII K WY^ISLIMYM FUNKCIQM DAET FUNK-
CII WY^ISLIMYE. w SWQZI S \TIM WOZNIKAET WOPROS: \wSQKAQ LI WY^ISLIMAQ FUNKCIQ QWLQETSQ
^ASTI^NO-REKURSIWNOJ?" dO SIH POR NE POSTROENO PRIMEROW WY^ISLIMYH FUNKCIJ, NE QWLQ@-
]IHSQ ^ASTI^NO REKURSIWNYMI. ~ISTO LOGIKO-MATEMATI^ESKOGO DOKAZATELXSTWA TOGO, ^TO WSQKAQ
WY^ISLIMAQ FUNKCIQ QWLQETSQ ^ASTI^NO REKURSIWNOJ, NE MOVET BYTX, TAK KAK PONQTIE WY^IS-
LIMOJ FUNKCII | INTUITIWNOE PONQTIE. a. ~ER^, ANALIZIRUQ IDEI I REZULXTATY, OTNOSQ]IESQ
K TEORII REKURSIWNYH FUNKCIJ I TEORII ALGORITMOW WOOB]E, PRIEL K SLEDU@]EJ ESTESTWENNO-
NAU^NOJ GIPOTEZE, IZWESTNOJ POD NAZWANIEM
tEZIS ~ER^A. kLASS WY^ISLIMYH ^ASTI^NYH FUNKCIJ SOWPADAET S KLASSOM ^ASTI^NO REKUR            -
SIWNYH FUNKCIJ.
   1.8. nOWYE TERMINY. sWOJSTWA ALGORITMA: DISKRETNOSTX, DETERMINIROWANNOSTX, \LE-
MENTARNOSTX AGOW, NAPRAWLENNOSTX, MASSOWOSTX. ~ISLOWAQ FUNKCIQ. ~ASTI^NAQ ^ISLOWAQ FUNK-
CIQ. wY^ISLIMYE FUNKCII. pROSTEJIE FUNKCII: FUNKCIQ SLEDOWANIQ, NULX-FUNKCIQ, PROEKTI-
RU@]IE FUNKCII. oSNOWNYE WY^ISLIMYE OPERATORY: SUPERPOZICII (PODSTANOWKI), PRIMITIWNOJ
REKURSII, MINIMIZACII. pRIMITIWNO REKURSIWNYE FUNKCII. ~ASTI^NO REKURSIWNYE FUNKCII.
tEZIS ~ER^A.
   1.9. kONTROLXNYE WOPROSY.
  1. pERE^ISLITE OTLI^ITELXNYE PRIZNAKI ALGORITMA. pOQSNITE SMYSL KAVDOGO IZ NIH.
  2. pERE^ISLITE IZWESTNYE wAM ALGORITMY IZ KOLXNOJ MATEMATIKI. iZ KURSOW ALGEBRY, ANA-
     LIZA I GEOMETRII.
  3. dAJTE OPREDELENIE FUNKCII, ^ASTI^NOJ FUNKCII, ^ISLOWOJ FUNKCII, ^ASTI^NOJ ^ISLOWOJ
     FUNKCII I WY^ISLIMOJ FUNKCII.
  4. w SWQZI S ^EM WOZNIKLA NEOBHODIMOSTX UTO^NENIQ PONQTIQ ALGORITMA?
  5. pERE^ISLITE PROSTEJIE FUNKCII. pOQSNITE, PO^EMU KAVDAQ IZ PROSTEJIH FUNKCIJ QW-
     LQETSQ WY^ISLIMOJ?
  6. dAJTE OPREDELENIE OPERATORA SUPERPOZICII. pOKAVITE, ^TO \TOT OPERATOR, PRIMENENNYJ K
     WY^ISLIMYM FUNKCIQM, DAET WY^ISLIMU@ FUNKCI@.
  7. kAKIE FUNKCII MOVNO POLU^ITX IZ FUNKCII SLEDOWANIQ MNOGOKRATNYMI PRIMENENIQMI
     OPERATORA SUPERPOZICII?
                                              129