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

gLAWA           VII
oSNOWY TEORII ALGORITMOW


   x   1.       rEKURSIWNYE FUNKCII
       iNTUITIWNOE PONQTIE ALGORITMA oTLI^ITELXNYE PRIZNAKI ALGORITMA wY^ISLIMYE FUNK
                                      .                             .                 -

       CII nEOBHODIMOSTX UTO^NENIQ PONQTIQ ALGORITMA pROSTEJIE FUNKCII oPERATORY SUPER
            .                                       .                   .             -

       POZICII PODSTANOWKI PRIMITIWNOJ REKURSII I MINIMIZACII pRIMITIWNO REKURSIWNYE I
                 (       ),                                  .

       ^ASTI^NO REKURSIWNYE FUNKCII tEZIS ~ER^A
                                  .           .




   1.1. iNTUITIWNOE PONQTIE ALGORITMA. pOD ALGORITMOM PONIMA@T KONE^NU@ POSLE-
DOWATELXNOSTX PREDPISANIJ (INSTRUKCIJ), TO^NOE ISPOLNENIE KOTORYH PRIWODIT K REENI@ PO-
STAWLENNOJ ZADA^I (DOSTIVENI@ POSTAWLENNOJ CELI).
   oTLI^ITELXNYMI PRIZNAKAMI ALGORITMA QWLQ@TSQ SLEDU@]IE.
   1. dISKRETNOSTX. aLGORITM PREDSTAWLQET SOBOJ SISTEMU POAGOWYH (DISKRETNYH) PREDPISA-
NIJ. iSPOLNENIE \TIH PREDPISANIJ (AGOW) OSU]ESTWLQETSQ DISKRETNO, TO ESTX PREDPOLAGAETSQ,
^TO KAKOE-TO PREDPISANIE (AG) NE MOVET BYTX WYPOLNENO, NAPRIMER, NAPOLOWINU ILI NA ODNU
TRETX. kAVDYJ AG QWLQETSQ W KAVDYJ (DISKRETNYJ) MOMENT WREMENI ISPOLNENNYM POLNOSTX@,
LIBO NE ISPOLNENNYM SOWSEM.
   2. dETERMINIROWANNOSTX. sISTEMA POLU^AEMYH (KONSTRUIRUEMYH) WELI^IN (OB_EKTOW) POS-
LE ISPOLNENIQ n-OGO AGA ODNOZNA^NO OPREDELQETSQ SISTEMOJ WELI^IN (OB_EKTOW), POLU^ENNYH
(SKONSTRUIROWANNYH) POSLE ISPOLNENIQ KAVDOGO IZ PREDYDU]IH (n ; 1) AGOW.
   3. |LEMENTARNOSTX AGOW. zAKON (PRAWILO) POLU^ENIQ SISTEMY WELI^IN (OB_EKTOW) IZ PRED-
ESTWU@]IH SISTEM WELI^IN (OB_EKTOW) DOLVEN BYTX DOSTATO^NO PROSTYM.
   4. nAPRAWLENNOSTX (OPREDELENNOSTX). eSLI ZAKON (PRAWILO) POLU^ENIQ SISTEMY WELI^IN
(OB_EKTOW) IZ PREDESTWU@]IH SISTEM NE DAET REZULXTATA, TO, DOLVNO BYTX UKAZANO, ^TO SLEDUET
S^ITATX REZULXTATOM ALGORITMA W \TOM SLU^AE.
   5. mASSOWOSTX. dOPUSTIMOJ SISTEMOJ WELI^IN (OB_EKTOW) QWLQETSQ NEKOTOROE BESKONE^NOE
MNOVESTWO.
   oTMETIM, ^TO W OPISANII ALGORITMA I EGO SWOJSTW FIGURIRUET MASSA TERMINOW, TO^NYJ SMYSL
KOTORYH NE USTANOWLEN. tAKIM OBRAZOM, PONQTIE ALGORITMA, OPREDELENNOE WYE, NELXZQ S^ITATX
STROGIM. w DALXNEJEM WWEDENNOE WYE PONQTIE ALGORITMA BUDEM NAZYWATX INTUITIWNYM.
   wY^ISLITELXNYE PROCESSY ^ISTO MEHANI^ESKOGO HARAKTERA STALI WOZNIKATX NA SAMYH RANNIH
STUPENQH RAZWITIQ MATEMATIKI. |TO, NAPRIMER, ALGORITMY POLU^ENIQ DESQTI^NOJ ZAPISI SUMMY
(RAZNOSTI, PROIZWEDENIQ, ^ASTNOGO) PO DESQTI^NYM ZAPISQM SLAGAEMYH (UMENXAEMOGO I WY^I-
TAEMOGO, SOMNOVITELEJ, DELIMOGO I DELITELQ) ALGORITM NAHOVDENIQ nod DWUH CELYH ^ISEL
(DWUH MNOGO^LENOW) ALGORITMY GEOMETRI^ESKIH POSTROENIJ S POMO]X@ ZADANNYH INSTRUMENTOW
I TAK DALEE. nEMALO ALGORITMOW I W OBYDENNOJ OKRUVA@]EJ NAS VIZNI. wSQKIJ IZLOVENNYJ NA
PRIOBRETENNOM wAMI PAKETE SPOSOB PRIGOTOWLENIQ IZ DANNYH POLUFABRIKATOW NEKOEGO PRODUKTA,
PRIGODNOGO K UPOTREBLENI@ W PI]U, ESTX NE ^TO INOE, KAK ALGORITM. wSQKAQ INSTRUKCIQ POLXZO-
WANIQ TEM ILI INYM BYTOWYM PRIBOROM (NAPRIMER, TELEFONOM-AWTOMATOM) ESTX ALGORITM I TAK
DALEE.
   s^ITAQ TEPERX PONQTIE ALGORITMA INTUITIWNO IZWESTNYM, OPREDELIM PONQTIE WY^ISLIMOJ
FUNKCII. oPREDELENIE \TOGO PONQTIQ TAKVE SLEDUET S^ITATX NESTROGIM (INTUITIWNYM).
   ~ISLOWOJ FUNKCIEJ (^ASTI^NOJ ^ISLOWOJ FUNKCIEJ) BUDEM NAZYWATX WSQKU@ FUNKCI@ (^AS-
TI^NU@ FUNKCI@) OT n PEREMENNYH, n 2 N, ZADANNU@ NA MNOVESTWE WSEH NEOTRICATELXNYH CELYH
^ISEL N0 SO ZNA^ENIQMI W N0 . tAKIM OBRAZOM, ^ISLOWAQ FUNKCIQ (^ASTI^NAQ ^ISLOWAQ FUNKCIQ)
                                              125