Математическая логика и теория алгоритмов. Самохин А.В. - 16 стр.

16                                          çÌÁ×Á I. íÎÏÖÅÓÔ×Á É ÍÏÝÎÏÓÔÉ

         ÞÉÓÌÏ ÓÞ¾ÔÎÙÈ ÍÎÏÖÅÓÔ× {0} × N, {1} × N, . . . (ÜÌÅÍÅÎÔÁÍÉ i-ÇÏ ÍÎÏÖÅ-
         ÓÔ×Á ÂÕÄÕÔ ÐÁÒÙ, ÐÅÒ×ÙÊ ÞÌÅÎ ËÏÔÏÒÙÈ ÒÁ×ÅÎ i). ðÏÜÔÏÍÕ N2 ÓÞ¾ÔÎÏ.
         áÎÁÌÏÇÉÞÎÙÍ ÏÂÒÁÚÏÍ ÍÎÏÖÅÓÔ×Ï N3 ÔÒÏÅË ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ ÒÁÚÂÉ-
         ×ÁÅÔÓÑ ÎÁ ÓÞ¾ÔÎÏÅ ÞÉÓÌÏ ÍÎÏÖÅÓÔ× {i} × N × N. ëÁÖÄÏÅ ÉÚ ÎÉÈ ÓÏÓÔÏÉÔ
         ÉÚ ÔÒÏÅË, ÐÅÒ×ÙÊ ÞÌÅÎ ËÏÔÏÒÙÈ ÆÉËÓÉÒÏ×ÁÎ É ÐÏÔÏÍÕ ÒÁ×ÎÏÍÏÝÎÏ ÍÎÏ-
         ÖÅÓÔ×Õ N2 , ËÏÔÏÒÏÅ ÓÞ¾ÔÎÏ. ôÏÞÎÏ ÔÁË ÖÅ ÍÏÖÎÏ ÐÅÒÅÊÔÉ ÏÔ ÓÞ¾ÔÎÏÓÔÉ
         ÍÎÏÖÅÓÔ×Á Nk Ë ÓÞ¾ÔÎÏÓÔÉ ÍÎÏÖÅÓÔ×Á Nk+1.
     •   íÎÏÖÅÓÔ×Ï ×ÓÅÈ ËÏÎÅÞÎÙÈ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ
         ÓÞ¾ÔÎÏ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ ÄÁÎÎÏÊ
         ÄÌÉÎÙ ÓÞ¾ÔÎÏ (ËÁË ÍÙ ÔÏÌØËÏ ÞÔÏ ×ÉÄÅÌÉ), ÔÁË ÞÔÏ ÉÎÔÅÒÅÓÕÀÝÅÅ
         ÎÁÓ ÍÎÏÖÅÓÔ×Ï ÒÁÚÂÉ×ÁÅÔÓÑ ÎÁ ÓÞ¾ÔÎÏÅ ÞÉÓÌÏ ÓÞ¾ÔÎÙÈ ÍÎÏÖÅÓÔ×.
     •   ÷ ÐÒÅÄÙÄÕÝÅÍ ÐÒÉÍÅÒÅ ÎÅ ÏÂÑÚÁÔÅÌØÎÏ ÇÏ×ÏÒÉÔØ Ï ÎÁÔÕÒÁÌØÎÙÈ ÞÉ-
         ÓÌÁÈ ¡ ÍÏÖÎÏ ×ÚÑÔØ ÌÀÂÏÅ ÓÞ¾ÔÎÏÅ (ÉÌÉ ËÏÎÅÞÎÏÅ) ÍÎÏÖÅÓÔ×Ï. îÁÐÒÉ-
         ÍÅÒ, ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÔÅËÓÔÏ×, ÉÓÐÏÌØÚÕÀÝÉÈ ÒÕÓÓËÉÊ ÁÌÆÁ×ÉÔ (ÔÁËÏÊ
         ÔÅËÓÔ ÍÏÖÎÏ ÓÞÉÔÁÔØ ËÏÎÅÞÎÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØÀ ÂÕË×, ÐÒÏÂÅÌÏ×,
         ÚÎÁËÏ× ÐÒÅÐÉÎÁÎÉÑ É Ô. Ð.), ÓÞ¾ÔÎÏ; ÔÏ ÖÅ ÓÁÍÏÅ ÍÏÖÎÏ ÓËÁÚÁÔØ Ï ÍÎÏ-
         ÖÅÓÔ×Å (×ÓÅÈ ÍÙÓÌÉÍÙÈ) ËÏÍÐØÀÔÅÒÎÙÈ ÐÒÏÇÒÁÍÍ É Ô. Ä.
     •   þÉÓÌÏ ÎÁÚÙ×ÁÀÔ ÁÌÇÅÂÒÁÉÞÅÓËÉÍ, ÅÓÌÉ ÏÎÏ Ñ×ÌÑÅÔÓÑ ËÏÒÎÅÍ ÎÅÎÕÌÅ×Ï-
         ÇÏ ÍÎÏÇÏÞÌÅÎÁ Ó ÃÅÌÙÍÉ ËÏÜÆÆÉÃÉÅÎÔÁÍÉ. íÎÏÖÅÓÔ×Ï ÁÌÇÅÂÒÁÉÞÅÓËÉÈ
         ÞÉÓÅÌ ÓÞ¾ÔÎÏ, ÔÁË ËÁË ÍÎÏÇÏÞÌÅÎÏ× ÓÞ¾ÔÎÏÅ ÞÉÓÌÏ (ÍÎÏÇÏÞÌÅÎ ÚÁÄÁ¾ÔÓÑ
         ËÏÎÅÞÎÏÊ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØÀ ÃÅÌÙÈ ÞÉÓÅÌ ¡ ÅÇÏ ËÏÜÆÆÉÃÉÅÎÔÏ×), Á
         ËÁÖÄÙÊ ÍÎÏÇÏÞÌÅÎ ÉÍÅÅÔ ËÏÎÅÞÎÏÅ ÞÉÓÌÏ ËÏÒÎÅÊ (ÎÅ ÂÏÌÅÅ n ÄÌÑ ÍÎÏ-
         ÇÏÞÌÅÎÏ× ÓÔÅÐÅÎÉ n).
     •   íÎÏÖÅÓÔ×Ï ÐÅÒÉÏÄÉÞÅÓËÉÈ ÄÒÏÂÅÊ ÓÞ¾ÔÎÏ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÔÁËÁÑ ÄÒÏÂØ
         ÍÏÖÅÔ ÂÙÔØ ÚÁÐÉÓÁÎÁ ËÁË ËÏÎÅÞÎÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÓÉÍ×ÏÌÏ×
         ÉÚ ËÏÎÅÞÎÏÇÏ ÍÎÏÖÅÓÔ×Á (ÚÁÐÑÔÁÑ, ÃÉÆÒÙ, ÓËÏÂËÉ); ÎÁÐÒÉÍÅÒ, ÄÒÏÂØ
         0,16666. . . ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ËÁË 0,1(6). á ÔÁËÉÈ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÅÊ
         ÓÞ¾ÔÎÏÅ ÍÎÏÖÅÓÔ×Ï.
  úÁÄÁÞÁ 28. äÏËÁÖÉÔÅ, ÞÔÏ ÌÀÂÏÅ ÓÅÍÅÊÓÔ×Ï ÎÅÐÅÒÅÓÅËÁÀÝÉÈÓÑ ÉÎ-
ÔÅÒ×ÁÌÏ× ÎÁ ÐÒÑÍÏÊ ËÏÎÅÞÎÏ ÉÌÉ ÓÞ¾ÔÎÏ. (õËÁÚÁÎÉÅ: × ËÁÖÄÏÍ ÉÎÔÅÒ×ÁÌÅ
ÎÁÊľÔÓÑ ÒÁÃÉÏÎÁÌØÎÁÑ ÔÏÞËÁ.)
   úÁÄÁÞÁ 29. ( Á) äÏËÁÖÉÔÅ, ÞÔÏ ÌÀÂÏÅ ÍÎÏÖÅÓÔ×Ï ÎÅÐÅÒÅÓÅËÁÀÝÉÈÓÑ
×ÏÓØ;ÒÏË ÎÁ ÐÌÏÓËÏÓÔÉ ËÏÎÅÞÎÏ ÉÌÉ ÓÞ¾ÔÎÏ. (÷ÏÓØ;ÒËÁ ¡ ÏÂßÅÄÉÎÅÎÉÅ
Ä×ÕÈ ËÁÓÁÀÝÉÈÓÑ ÏËÒÕÖÎÏÓÔÅÊ ÌÀÂÙÈ ÒÁÚÍÅÒÏ×.) ( Â) óÆÏÒÍÕÌÉÒÕÊÔÅ É ÄÏ-
ËÁÖÉÔÅ ÁÎÁÌÏÇÉÞÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÄÌÑ ÂÕË× ô.
   úÁÄÁÞÁ 30. äÏËÁÖÉÔÅ, ÞÔÏ ÍÎÏÖÅÓÔ×Ï ÔÏÞÅË ÓÔÒÏÇÏÇÏ ÌÏËÁÌØÎÏÇÏ
ÍÁËÓÉÍÕÍÁ ÌÀÂÏÊ ÆÕÎËÃÉÉ ÄÅÊÓÔ×ÉÔÅÌØÎÏÇÏ ÁÒÇÕÍÅÎÔÁ ËÏÎÅÞÎÏ ÉÌÉ ÓÞ¾Ô-
ÎÏ.