Next: 2.4. ðÓÅ×ÄÏÓÌÕÞÁÊÎÙÅ ÇÅÎÅÒÁÔÏÒÙ
Up: 2. ëÒÉÐÔÏÇÒÁÆÉÑ É ÔÅÏÒÉÑ
Previous: 2.2. ëÒÉÐÔÏÇÒÁÆÉÑ É ÇÉÐÏÔÅÚÁ
Contents: óÏÄÅÒÖÁÎÉÅ
2.3. ïÄÎÏÓÔÏÒÏÎÎÉÅ ÆÕÎËÃÉÉ
çÏ×ÏÒÑ ÎÅÆÏÒÍÁÌØÎÏ,
ÏÄÎÏÓÔÏÒÏÎÎÑÑ
ÆÕÎËÃÉÑ - ÜÔÏ
ÜÆÆÅËÔÉ×ÎÏ ×ÙÞÉÓÌÉÍÁÑ ÆÕÎËÃÉÑ, ÄÌÑ ÚÁÄÁÞÉ ÉÎ×ÅÒÔÉÒÏ×ÁÎÉÑ
ËÏÔÏÒÏÊ ÎÅ ÓÕÝÅÓÔ×ÕÅÔ ÜÆÆÅËÔÉ×ÎÙÈ ÁÌÇÏÒÉÔÍÏ×. ðÏÄ
ÉÎ×ÅÒÔÉÒÏ×ÁÎÉÅÍ
ÐÏÎÉÍÁÅÔÓÑ ÍÁÓÓÏ×ÁÑ ÚÁÄÁÞÁ ÎÁÈÏÖÄÅÎÉÑ ÐÏ
ÚÁÄÁÎÎÏÍÕ ÚÎÁÞÅÎÉÀ ÆÕÎËÃÉÉ ÏÄÎÏÇÏ (ÌÀÂÏÇÏ) ÚÎÁÞÅÎÉÑ ÉÚ
ÐÒÏÏÂÒÁÚÁ (ÚÁÍÅÔÉÍ, ÞÔÏ ÏÂÒÁÔÎÁÑ ÆÕÎËÃÉÑ, ×ÏÏÂÝÅ ÇÏ×ÏÒÑ,
ÍÏÖÅÔ ÎÅ ÓÕÝÅÓÔ×Ï×ÁÔØ).
ðÏÓËÏÌØËÕ ÐÏÎÑÔÉÅ ÏÄÎÏÓÔÏÒÏÎÎÅÊ ÆÕÎËÃÉÉ - ÃÅÎÔÒÁÌØÎÏÅ ×
ÍÁÔÅÍÁÔÉÞÅÓËÏÊ ËÒÉÐÔÏÇÒÁÆÉÉ, ÎÉÖÅ ÍÙ ÄÁÅÍ ÅÇÏ ÆÏÒÍÁÌØÎÏÅ
ÏÐÒÅÄÅÌÅÎÉÅ.
ðÕÓÔØ
- ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ Ä×ÏÉÞÎÙÈ
ÓÔÒÏË ÄÌÉÎÙ . ðÏÄ ÆÕÎËÃÉÅÊ ÍÙ ÐÏÎÉÍÁÅÍ ÓÅÍÅÊÓÔ×Ï , ÇÄÅ
,
. äÌÑ ÐÒÏÓÔÏÔÙ ÉÚÌÏÖÅÎÉÑ ÍÙ ÐÒÅÄÐÏÌÁÇÁÅÍ, ÞÔÏ ÐÒÏÂÅÇÁÅÔ ×ÅÓØ
ÎÁÔÕÒÁÌØÎÙÊ ÒÑÄ É ÞÔÏ ËÁÖÄÁÑ ÉÚ ÆÕÎËÃÉÊ ×ÓÀÄÕ
ÏÐÒÅÄÅÌÅÎÁ.
æÕÎËÃÉÑ ÎÁÚÙ×ÁÅÔÓÑ ÞÅÓÔÎÏÊ, ÅÓÌÉ ÓÕÝÅÓÔ×ÕÅÔ ÐÏÌÉÎÏÍ
ÔÁËÏÊ, ÞÔÏ ÄÌÑ ×ÓÅÈ .
ïÐÒÅÄÅÌÅÎÉÅ 1. þÅÓÔÎÁÑ ÆÕÎËÃÉÑ ÎÁÚÙ×ÁÅÔÓÑ
ÏÄÎÏÓÔÏÒÏÎÎÅÊ,
ÅÓÌÉ
1. óÕÝÅÓÔ×ÕÅÔ ÐÏÌÉÎÏÍÉÁÌØÎÙÊ ÁÌÇÏÒÉÔÍ, ËÏÔÏÒÙÊ ÄÌÑ ×ÓÑËÏÇÏ
×ÙÞÉÓÌÑÅÔ .
2. äÌÑ ÌÀÂÏÊ ÐÏÌÉÎÏÍÉÁÌØÎÏÊ ×ÅÒÏÑÔÎÏÓÔÎÏÊ ÍÁÛÉÎÙ ôØÀÒÉÎÇÁ
×ÙÐÏÌÎÅÎÏ ÓÌÅÄÕÀÝÅÅ. ðÕÓÔØ ÓÔÒÏËÁ ×ÙÂÒÁÎÁ ÎÁÕÄÁÞÕ
ÉÚ ÍÎÏÖÅÓÔ×Á (ÏÂÏÚÎÁÞÁÅÔÓÑ
).
ôÏÇÄÁ ÄÌÑ ÌÀÂÏÇÏ ÐÏÌÉÎÏÍÁ É ×ÓÅÈ ÄÏÓÔÁÔÏÞÎÏ
ÂÏÌØÛÉÈ
÷ÅÒÏÑÔÎÏÓÔØ ÚÄÅÓØ ÏÐÒÅÄÅÌÑÅÔÓÑ ÓÌÕÞÁÊÎÙÍ ×ÙÂÏÒÏÍ ÓÔÒÏËÉ É
ÓÌÕÞÁÊÎÙÍÉ ×ÅÌÉÞÉÎÁÍÉ, ËÏÔÏÒÙÅ ÉÓÐÏÌØÚÕÅÔ × Ó×ÏÅÊ ÒÁÂÏÔÅ.
õÓÌÏ×ÉÅ 2 ËÁÞÅÓÔ×ÅÎÎÏ ÏÚÎÁÞÁÅÔ ÓÌÅÄÕÀÝÅÅ.
ìÀÂÁÑ ÐÏÌÉÎÏÍÉÁÌØÎÁÑ ×ÅÒÏÑÔÎÏÓÔÎÁÑ ÍÁÛÉÎÁ ôØÀÒÉÎÇÁ
ÍÏÖÅÔ ÐÏ ÄÁÎÎÏÍÕ ÎÁÊÔÉ ÉÚ ÕÒÁ×ÎÅÎÉÑ
ÌÉÛØ Ó ÐÒÅÎÅÂÒÅÖÉÍÏ ÍÁÌÏÊ ×ÅÒÏÑÔÎÏÓÔØÀ.
úÁÍÅÔÉÍ, ÞÔÏ ÔÒÅÂÏ×ÁÎÉÅ ÞÅÓÔÎÏÓÔÉ ÎÅÌØÚÑ ÏÐÕÓÔÉÔØ.
ðÏÓËÏÌØËÕ ÄÌÉÎÁ ×ÈÏÄÎÏÇÏ ÓÌÏ×Á ÍÁÛÉÎÙ ÒÁ×ÎÁ ,
ÅÊ ÍÏÖÅÔ ÎÅ È×ÁÔÉÔØ ÐÏÌÉÎÏÍÉÁÌØÎÏÇÏ (ÏÔ ) ×ÒÅÍÅÎÉ ÐÒÏÓÔÏ
ÎÁ ×ÙÐÉÓÙ×ÁÎÉÅ ÓÔÒÏËÉ , ÅÓÌÉ ÓÌÉÛËÏÍ ÓÉÌØÎÏ
``ÓÖÉÍÁÅÔ'' ×ÈÏÄÎÙÅ ÚÎÁÞÅÎÉÑ.
ñÓÎÏ, ÞÔÏ ÉÚ ÐÒÅÄÐÏÌÏÖÅÎÉÑ Ï ÓÕÝÅÓÔ×Ï×ÁÎÉÉ ÏÄÎÏÓÔÏÒÏÎÎÉÈ
ÆÕÎËÃÉÊ ÓÌÅÄÕÅÔ, ÞÔÏ P NP. ïÄÎÁËÏ, ÎÅ ÉÓËÌÀÞÅÎÁ
ÓÌÅÄÕÀÝÁÑ ÓÉÔÕÁÃÉÑ: P NP, ÎÏ ÏÄÎÏÓÔÏÒÏÎÎÉÈ ÆÕÎËÃÉÊ
ÎÅÔ.
óÕÝÅÓÔ×Ï×ÁÎÉÅ ÏÄÎÏÓÔÏÒÏÎÎÉÈ ÆÕÎËÃÉÊ Ñ×ÌÑÅÔÓÑ ÎÅÏÂÈÏÄÉÍÙÍ
ÕÓÌÏ×ÉÅÍ ÄÌÑ ÓÔÏÊËÏÓÔÉ ÍÎÏÇÉÈ ÔÉÐÏ× ËÒÉÐÔÏÇÒÁÆÉÞÅÓËÉÈ ÓÈÅÍ.
÷ ÎÅËÏÔÏÒÙÈ ÓÌÕÞÁÑÈ ÜÔÏÔ ÆÁËÔ ÕÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÄÏÓÔÁÔÏÞÎÏ
ÐÒÏÓÔÏ. ïÂÒÁÔÉÍÓÑ ÏÐÑÔØ Ë ÐÒÉÍÅÒÕ 1.
òÁÓÓÍÏÔÒÉÍ ÆÕÎËÃÉÀ ÔÁËÕÀ, ÞÔÏ
. ïÎÁ ×ÙÞÉÓÌÉÍÁ Ó ÐÏÍÏÝØÀ ÁÌÇÏÒÉÔÍÁ ÚÁ
ÐÏÌÉÎÏÍÉÁÌØÎÏÅ ×ÒÅÍÑ.
ðÏËÁÖÅÍ, ÞÔÏ ÅÓÌÉ - ÎÅ ÏÄÎÏÓÔÏÒÏÎÎÑÑ ÆÕÎËÃÉÑ, ÔÏ ËÒÉÐÔÏÓÉÓÔÅÍÁ
ÎÅÓÔÏÊËÁÑ. ðÒÅÄÐÏÌÏÖÉÍ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ ÐÏÌÉÎÏÍÉÁÌØÎÙÊ ×ÅÒÏÑÔÎÏÓÔÎÙÊ
ÁÌÇÏÒÉÔÍ , ËÏÔÏÒÙÊ ÉÎ×ÅÒÔÉÒÕÅÔ Ó ×ÅÒÏÑÔÎÏÓÔØÀ ÐÏ ËÒÁÊÎÅÊ ÍÅÒÅ
ÄÌÑ ÎÅËÏÔÏÒÏÇÏ ÐÏÌÉÎÏÍÁ . úÄÅÓØ - ÄÌÉÎÁ ËÌÀÞÁ .
ðÒÏÔÉ×ÎÉË ÍÏÖÅÔ ÐÏÄÁÔØ ÎÁ ×ÈÏÄ ÁÌÇÏÒÉÔÍÕ ËÌÀÞ É ÐÏÌÕÞÉÔØ Ó
ÕËÁÚÁÎÎÏÊ ×ÅÒÏÑÔÎÏÓÔØÀ ÎÅËÏÔÏÒÏÅ ÚÎÁÞÅÎÉÅ ÉÚ ÐÒÏÏÂÒÁÚÁ. äÁÌÅÅ
ÐÒÏÔÉ×ÎÉË ÐÏÄÁÅÔ ÎÁ ×ÈÏÄ ÁÌÇÏÒÉÔÍÁ É ÐÏÌÕÞÁÅÔ ÐÁÒÕ ËÌÀÞÅÊ
. èÏÔÑ ÎÅ ÏÂÑÚÁÔÅÌØÎÏ ÓÏ×ÐÁÄÁÅÔ Ó , ÔÅÍ ÎÅ
ÍÅÎÅÅ, ÐÏ ÏÐÒÅÄÅÌÅÎÉÀ ËÒÉÐÔÏÓÉÓÔÅÍÙ
ÄÌÑ ÌÀÂÏÇÏ
ÏÔËÒÙÔÏÇÏ ÔÅËÓÔÁ . ðÏÓËÏÌØËÕ ÎÁÊÄÅÎ Ó ×ÅÒÏÑÔÎÏÓÔØÀ ÐÏ
ËÒÁÊÎÅÊ ÍÅÒÅ , ËÏÔÏÒÁÑ × ËÒÉÐÔÏÇÒÁÆÉÉ ÎÅ ÓÞÉÔÁÅÔÓÑ ÐÒÅÎÅÂÒÅÖÉÍÏ
ÍÁÌÏÊ, ËÒÉÐÔÏÓÉÓÔÅÍÁ ÎÅÓÔÏÊËÁÑ.
äÌÑ ÄÒÕÇÉÈ ËÒÉÐÔÏÇÒÁÆÉÞÅÓËÉÈ ÓÈÅÍ ÐÏÄÏÂÎÙÊ ÒÅÚÕÌØÔÁÔ
ÄÏËÁÚÙ×ÁÅÔÓÑ ÎÅ ÓÔÏÌØ ÐÒÏÓÔÏ. ÷ ÒÁÂÏÔÅ éÍÐÁÌØÑÃÃÏ É ìÕÂÉ
[7] ÄÏËÁÚÁÎÁ ÎÅÏÂÈÏÄÉÍÏÓÔØ ÏÄÎÏÓÔÏÒÏÎÎÉÈ ÆÕÎËÃÉÊ ÄÌÑ
ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ÃÅÌÏÇÏ ÒÑÄÁ ÓÔÏÊËÉÈ ËÒÉÐÔÏÇÒÁÆÉÞÅÓËÉÈ ÓÈÅÍ.
éÚ ×ÓÅÇÏ ÓËÁÚÁÎÎÏÇÏ ÓÌÅÄÕÅÔ, ÞÔÏ ÐÒÅÄÐÏÌÏÖÅÎÉÅ Ï
ÓÕÝÅÓÔ×Ï×ÁÎÉÉ ÏÄÎÏÓÔÏÒÏÎÎÉÈ ÆÕÎËÃÉÊ Ñ×ÌÑÅÔÓÑ ÓÁÍÙÍ ÓÌÁÂÙÍ
ËÒÉÐÔÏÇÒÁÆÉÞÅÓËÉÍ ÐÒÅÄÐÏÌÏÖÅÎÉÅÍ, ËÏÔÏÒÏÅ ÍÏÖÅÔ ÏËÁÚÁÔØÓÑ
ÄÏÓÔÁÔÏÞÎÙÍ ÄÌÑ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ÓÔÏÊËÉÈ
ËÒÉÐÔÏÇÒÁÆÉÞÅÓËÉÈ ÓÈÅÍ ÒÁÚÌÉÞÎÙÈ ÔÉÐÏ×. îÁ ×ÙÑÓÎÅÎÉÅ ÔÏÇÏ,
Ñ×ÌÑÅÔÓÑ ÌÉ ÜÔÏ ÕÓÌÏ×ÉÅ É × ÓÁÍÏÍ ÄÅÌÅ ÄÏÓÔÁÔÏÞÎÙÍ,
ÎÁÐÒÁ×ÌÅÎÙ ÚÎÁÞÉÔÅÌØÎÙÅ ÕÓÉÌÉÑ ÓÐÅÃÉÁÌÉÓÔÏ×.
ôÒÕÄÎÏÓÔØ
ÚÁÄÁÞÉ ÐÏÓÔÒÏÅÎÉÑ ËÒÉÐÔÏÇÒÁÆÉÞÅÓËÉÈ ÓÈÅÍ ÉÚ ÏÄÎÏÓÔÏÒÏÎÎÉÈ
ÆÕÎËÃÉÊ ÍÏÖÎÏ ÐÏÑÓÎÉÔØ ÎÁ ÓÌÅÄÕÀÝÅÍ ÐÒÉÍÅÒÅ. ðÕÓÔØ -
ÏÄÎÏÓÔÏÒÏÎÎÑÑ ÆÕÎËÃÉÑ É ÎÁÍ ÔÒÅÂÕÅÔÓÑ ÐÏÓÔÒÏÉÔØ
ËÒÉÐÔÏÓÉÓÔÅÍÕ Ó
ÓÅËÒÅÔÎÙÍ ËÌÀÞÏÍ. ÷ ÔÁËÏÊ
ËÒÉÐÔÏÓÉÓÔÅÍÅ ÉÍÅÅÔÓÑ ÔÏÌØËÏ ÏÄÉÎ ËÌÀÞ - ÓÅËÒÅÔÎÙÊ,
ËÏÔÏÒÙÊ ÉÚ×ÅÓÔÅÎ É ÏÔÐÒÁ×ÉÔÅÌÀ, É ÐÏÌÕÞÁÔÅÌÀ
ÛÉÆÒÏ×ÁÎÎÏÇÏ ÓÏÏÂÝÅÎÉÑ. áÌÇÏÒÉÔÍÙ ÛÉÆÒÏ×ÁÎÉÑ É
ÄÅÛÉÆÒÏ×ÁÎÉÑ ÏÂÁ ÚÁ×ÉÓÑÔ ÏÔ ÜÔÏÇÏ ÓÅËÒÅÔÎÏÇÏ
ËÌÀÞÁ É ÔÁËÏ×Ù, ÞÔÏ ÄÌÑ ÌÀÂÏÇÏ ÏÔËÒÙÔÏÇÏ ÔÅËÓÔÁ .
ñÓÎÏ, ÞÔÏ ÅÓÌÉ ËÒÉÐÔÏÇÒÁÍÍÕ ÓÏÏÂÝÅÎÉÑ
×ÙÞÉÓÌÑÔØ ËÁË , ÔÏ ÐÒÏÔÉ×ÎÉË, ÐÅÒÅÈ×ÁÔÉ×ÛÉÊ
, ÍÏÖÅÔ ×ÙÞÉÓÌÉÔØ ÌÉÛØ Ó ÐÒÅÎÅÂÒÅÖÉÍÏ ÍÁÌÏÊ
×ÅÒÏÑÔÎÏÓÔØÀ. îÏ ×Ï-ÐÅÒ×ÙÈ, ÎÅÐÏÎÑÔÎÏ, ËÁËÉÍ ÏÂÒÁÚÏÍ
ÓÍÏÖÅÔ ×ÏÓÓÔÁÎÏ×ÉÔØ ÓÏÏÂÝÅÎÉÅ ÉÚ ËÒÉÐÔÏÇÒÁÍÍÙ ÚÁËÏÎÎÙÊ
ÐÏÌÕÞÁÔÅÌØ? ÷Ï-×ÔÏÒÙÈ, ÉÚ ÔÏÇÏ, ÞÔÏ ÆÕÎËÃÉÑ
ÏÄÎÏÓÔÏÒÏÎÎÑÑ ÓÌÅÄÕÅÔ ÌÉÛØ, ÞÔÏ ÐÒÏÔÉ×ÎÉË ÎÅ ÍÏÖÅÔ
×ÙÞÉÓÌÉÔØ ×ÓÅ ÓÏÏÂÝÅÎÉÅ ÃÅÌÉËÏÍ. á ÜÔÏ - ×ÅÓØÍÁ ÎÉÚËÉÊ
ÕÒÏ×ÅÎØ ÓÔÏÊËÏÓÔÉ. öÅÌÁÔÅÌØÎÏ, ÞÔÏÂÙ ÐÒÏÔÉ×ÎÉË, ÚÎÁÀÝÉÊ
ËÒÉÐÔÏÇÒÁÍÍÕ , ÎÅ ÍÏÇ ×ÙÞÉÓÌÉÔØ ÎÉ ÏÄÎÏÇÏ ÂÉÔÁ ÏÔËÒÙÔÏÇÏ
ÔÅËÓÔÁ.
îÁ
ÎÁÓÔÏÑÝÉÊ ÍÏÍÅÎÔ ÄÏËÁÚÁÎÏ, ÞÔÏ ÓÕÝÅÓÔ×Ï×ÁÎÉÅ
ÏÄÎÏÓÔÏÒÏÎÎÉÈ ÆÕÎËÃÉÊ Ñ×ÌÑÅÔÓÑ ÎÅÏÂÈÏÄÉÍÙÍ É ÄÏÓÔÁÔÏÞÎÙÍ
ÕÓÌÏ×ÉÅÍ ÄÌÑ ÓÕÝÅÓÔ×Ï×ÁÎÉÑ ÓÔÏÊËÉÈ ËÒÉÐÔÏÓÉÓÔÅÍ Ó ÓÅËÒÅÔÎÙÍ
ËÌÀÞÏÍ, Á ÔÁËÖÅ ÓÔÏÊËÉÈ ËÒÉÐÔÏÇÒÁÆÉÞÅÓËÉÈ ÐÒÏÔÏËÏÌÏ×
ÎÅÓËÏÌØËÉÈ ÔÉÐÏ×, ×ËÌÀÞÁÑ ÐÒÏÔÏËÏÌÙ ÜÌÅËÔÒÏÎÎÏÊ ÐÏÄÐÉÓÉ. ó
ÄÒÕÇÏÊ ÓÔÏÒÏÎÙ, ÉÍÅÅÔÓÑ ÒÅÚÕÌØÔÁÔ éÍÐÁÌØÑÃÃÏ É òÕÄÉÈÁ
[9], ËÏÔÏÒÙÊ Ñ×ÌÑÅÔÓÑ ÄÏÓÔÁÔÏÞÎÏ ÓÉÌØÎÙÍ ÁÒÇÕÍÅÎÔÏÍ ×
ÐÏÌØÚÕ ÔÏÇÏ, ÞÔÏ ÄÌÑ ÎÅËÏÔÏÒÙÈ ÔÉÐÏ× ËÒÉÐÔÏÇÒÁÆÉÞÅÓËÉÈ ÓÈÅÍ (×ËÌÀÞÁÑ
ÐÒÏÔÏËÏÌÙ ÒÁÓÐÒÅÄÅÌÅÎÉÑ ËÌÀÞÅÊ ÔÉÐÁ äÉÆÆÉ-èÅÌÌÍÁÎÁ) ÔÒÅÂÕÀÔÓÑ ÂÏÌÅÅ
ÓÉÌØÎÙÅ ÐÒÅÄÐÏÌÏÖÅÎÉÑ, ÞÅÍ ÐÒÅÄÐÏÌÏÖÅÎÉÅ Ï ÓÕÝÅÓÔ×Ï×ÁÎÉÉ ÏÄÎÏÓÔÏÒÏÎÎÉÈ
ÆÕÎËÃÉÊ. ë ÓÏÖÁÌÅÎÉÀ, ÜÔÏÔ ÒÅÚÕÌØÔÁÔ ÓÌÉÛËÏÍ ÓÌÏÖÎÙÊ, ÞÔÏÂÙ ÅÇÏ ÍÏÖÎÏ
ÂÙÌÏ ÒÁÚßÑÓÎÉÔØ × ÎÁÓÔÏÑÝÅÊ ÇÌÁ×Å.
Next: 2.4. ðÓÅ×ÄÏÓÌÕÞÁÊÎÙÅ ÇÅÎÅÒÁÔÏÒÙ
Up: 2. ëÒÉÐÔÏÇÒÁÆÉÑ É ÔÅÏÒÉÑ
Previous: 2.2. ëÒÉÐÔÏÇÒÁÆÉÑ É ÇÉÐÏÔÅÚÁ
Contents: óÏÄÅÒÖÁÎÉÅ
|