next up previous contents
Next: æÕÎËÃÉÏÎÁÌØÎÁÑ ÄÅËÏÍÐÏÚÉÃÉÑ Up: òÁÓÐÒÅÄÅÌÅÎÉÅ ÒÁÂÏÞÅÊ ÎÁÇÒÕÚËÉ Previous: òÁÓÐÒÅÄÅÌÅÎÉÅ ÒÁÂÏÞÅÊ ÎÁÇÒÕÚËÉ   Contents

äÅËÏÍÐÏÚÉÃÉÑ ÄÁÎÎÙÈ

÷ ËÁÞÅÓÔ×Å ÐÒÏÓÔÏÇÏ ÐÒÉÍÅÒÁ ÄÅËÏÍÐÏÚÉÃÉÉ ÄÁÎÎÙÈ ÒÁÓÓÍÏÔÒÉÍ ÓÌÏÖÅÎÉÅ Ä×ÕÈ ×ÅËÔÏÒÏ× $A{[}1..N{]}$ É $B{[}1..N{]}$, × ÒÅÚÕÌØÔÁÔÅ ÞÅÇÏ ÐÏÌÕÞÉÔÓÑ ×ÅËÔÏÒ $C{[}1..N{]}$. åÓÌÉ ÐÒÅÄÐÏÌÏÖÉÔØ, ÞÔÏ ÎÁÄ ÜÔÏÊ ÚÁÄÁÞÅÊ ÒÁÂÏÔÁÅÔ $P$ ÐÒÏÃÅÓÓÏ×, ÒÁÚÂÉÅÎÉÅ ÄÁÎÎÙÈ ÐÒÉ×ÅÄÅÔ Ë ÒÁÓÐÒÅÄÅÌÅÎÉÀ $N/P$ ÜÌÅÍÅÎÔÏ× ËÁÖÄÏÇÏ ×ÅËÔÏÒÁ ÄÌÑ ËÁÖÄÏÇÏ ÐÒÏÃÅÓÓÁ, ËÏÔÏÒÙÊ ×ÙÞÉÓÌÑÅÔ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÅ $N/P$ ÜÌÅÍÅÎÔÏ× ÒÅÚÕÌØÔÉÒÕÀÝÅÇÏ ×ÅËÔÏÒÁ. ôÁËÏÅ ÒÁÓÐÒÅÄÅÌÅÎÉÅ ÄÁÎÎÙÈ ÍÏÖÅÔ ÂÙÔØ ÓÄÅÌÁÎÏ ÌÉÂÏ ``ÓÔÁÔÉÞÅÓËÉ'', ËÏÇÄÁ ËÁÖÄÙÊ ÐÒÏÃÅÓÓ ``ÁÐÒÉÏÒÉ'' ÚÎÁÅÔ (ÐÏ ËÒÁÊÎÅÊ ÍÅÒÅ, × ÔÅÒÍÉÎÁÈ ÐÅÒÅÍÅÎÎÙÈ $N$ É $P$) Ó×ÏÀ ÄÏÌÀ ÒÁÂÏÞÅÊ ÎÁÇÒÕÚËÉ, ÌÉÂÏ ``ÄÉÎÁÍÉÞÅÓËÉ'', ËÏÇÄÁ ËÏÎÔÒÏÌÉÒÕÀÝÉÊ ÐÒÏÃÅÓÓ (Ô.Å. ×ÅÄÕÝÉÊ) ÒÁÓÐÒÅÄÅÌÑÅÔ ÐÏÄÂÌÏËÉ ÒÁÂÏÞÅÊ ÎÁÇÒÕÚËÉ ÄÌÑ ÐÒÏÃÅÓÓÏ× - ËÁË É ËÏÇÄÁ ÏÎÉ ÏÓ×ÏÂÏÄÑÔÓÑ. ðÒÉÎÃÉÐÉÁÌØÎÁÑ ÒÁÚÎÉÃÁ ÍÅÖÄÕ ÜÔÉÍÉ Ä×ÕÍÑ ÐÏÄÈÏÄÁÍÉ - ÜÔÏ ``ÄÉÓÐÅÔÞÅÒÉÚÁÃÉÑ''. ðÒÉ ÓÔÁÔÉÞÅÓËÏÊ ÄÉÓÐÅÔÞÅÒÉÚÁÃÉÉ ÉÎÄÉ×ÉÄÕÁÌØÎÁÑ ÒÁÂÏÞÁÑ ÎÁÇÒÕÚËÁ ÐÒÏÃÅÓÓÁ ÆÉËÓÉÒÏ×ÁÎÁ; ÐÒÉ ÄÉÎÁÍÉÞÅÓËÏÊ, ÏÎÁ ×ÁÒØÉÒÕÅÔ × ÚÁ×ÉÓÉÍÏÓÔÉ ÏÔ ÓÏÓÔÏÑÎÉÑ ×ÙÞÉÓÌÉÔÅÌØÎÏÇÏ ÐÒÏÃÅÓÓÁ. ÷ ÂÏÌØÛÉÎÓÔ×Å ÍÕÌØÔÉÐÒÏÃÅÓÓÏÒÎÙÈ ÓÒÅÄ ÓÔÁÔÉÞÅÓËÁÑ ÄÉÓÐÅÔÞÅÒÉÚÁÃÉÑ ÜÆÆÅËÔÉ×ÎÁ ÄÌÑ ÔÁËÉÈ ÚÁÄÁÞ ËÁË ÐÒÉÍÅÒ ÓÌÏÖÅÎÉÑ ×ÅËÔÏÒÏ×; ÏÄÎÁËÏ × ÏÂÏÂÝÅÎÎÏÊ ÓÒÅÄÅ PVM ÓÔÁÔÉÞÅÓËÁÑ ÄÉÓÐÅÔÞÅÒÉÚÁÃÉÑ ÎÅ ÏÞÅÎØ ÎÅÏÂÈÏÄÉÍÁ. óÍÙÓÌ ÚÁËÌÀÞÁÅÔÓÑ × ÔÏÍ, ÞÔÏ ÓÒÅÄÙ PVM, ÂÁÚÉÒÕÀÝÉÅÓÑ ÎÁ ÓÅÔÅ×ÙÈ ËÌÁÓÔÅÒÁÈ, ×ÏÓÐÒÉÉÍÞÉ×Ù Ë ×ÎÅÛÎÉÍ ×ÏÚÄÅÊÓÔ×ÉÑÍ; ÐÏÜÔÏÍÕ ÓÔÁÔÉÞÅÓËÉ ÄÉÓÐÅÔÞÅÒÉÚÉÒÏ×ÁÎÎÙÅ ÚÁÄÁÞÉ Ó ÒÁÚÄÅÌÅÎÎÙÍÉ ÄÁÎÎÙÍÉ ÍÏÇÕÔ ËÏÎÆÌÉËÔÏ×ÁÔØ Ó ÏÄÎÉÍ ÉÌÉ ÂÏÌÅÅ ÐÒÏÃÅÓÓÁÍÉ, ËÏÔÏÒÙÅ ÒÅÁÌÉÚÕÀÔ Ó×ÏÀ ÐÏÒÃÉÀ ÒÁÂÏÞÅÊ ÎÁÇÒÕÚËÉ ÎÁÍÎÏÇÏ ÂÙÓÔÒÅÅ ÉÌÉ ÎÁÍÎÏÇÏ ÍÅÄÌÅÎÎÅÅ, ÞÅÍ ÄÒÕÇÉÅ. üÔÁ ÓÉÔÕÁÃÉÑ ÍÏÖÅÔ ÔÁËÖÅ ×ÏÚÎÉËÎÕÔØ, ËÏÇÄÁ ÍÁÛÉÎÙ × ÓÉÓÔÅÍÅ PVM ÇÅÔÅÒÏÇÅÎÎÙ, ÏÂÌÁÄÁÀÔ ÒÁÚÌÉÞÎÙÍÉ ÓËÏÒÏÓÔÑÍÉ ãðõ, ÒÁÚÌÉÞÎÏÊ ÐÁÍÑÔØÀ É ÐÒÏÞÉÍÉ ÓÉÓÔÅÍÎÙÍÉ ÁÔÒÉÂÕÔÁÍÉ.

ðÒÉ ÒÅÁÌØÎÏÍ ÉÓÐÏÌÎÅÎÉÉ ÄÁÖÅ ÕÐÏÍÑÎÕÔÏÊ ÔÒÉ×ÉÁÌØÎÏÊ ÚÁÄÁÞÉ ÓÌÏÖÅÎÉÑ ×ÅËÔÏÒÏ× ×ÙÑ×ÌÑÅÔÓÑ, ÞÔÏ ××ÏÄ É ×Ù×ÏÄ ÎÅ ÍÏÇÕÔ ÂÙÔØ ÐÒÏÉÇÎÏÒÉÒÏ×ÁÎÙ. ÷ÏÚÎÉËÁÅÔ ×ÏÐÒÏÓ: ËÁË ÚÁÓÔÁ×ÉÔØ ÏÐÉÓÁÎÎÙÅ ×ÙÛÅ ÐÒÏÃÅÓÓÙ ÐÒÉÎÑÔØ Ó×ÏÀ ÒÁÂÏÞÕÀ ÎÁÇÒÕÚËÕ É ÞÔÏ ÉÍ ÄÅÌÁÔØ Ó ÒÅÚÕÌØÔÉÒÕÀÝÉÍ ×ÅËÔÏÒÏÍ? ïÔ×ÅÔ ÎÁ ÜÔÏÔ ×ÏÐÒÏÓ ÚÁ×ÉÓÉÔ ÏÔ ÓÁÍÏÇÏ ÐÒÉÌÏÖÅÎÉÑ É ÏÂÓÔÏÑÔÅÌØÓÔ× ÅÇÏ ÞÁÓÔÉÞÎÏÇÏ ×ÙÐÏÌÎÅÎÉÑ, ËÏÇÄÁ:

  1. éÎÄÉ×ÉÄÕÁÌØÎÙÅ ÐÒÏÃÅÓÓÙ ÇÅÎÅÒÉÒÕÀÔ Ó×ÏÉ ÓÏÂÓÔ×ÅÎÎÙÅ ÄÁÎÎÙÅ ×ÎÕÔÒÅÎÎÅ, ÎÁÐÒÉÍÅÒ, ÉÓÐÏÌØÚÕÑ ÇÅÎÅÒÁÔÏÒÙ ÓÌÕÞÁÊÎÙÈ ÞÉÓÅÌ ÉÌÉ ÓÔÁÔÉÞÅÓËÉ ÚÁÄÁÎÎÙÅ ×ÅÌÉÞÉÎÙ. üÔÏ ×ÏÚÍÏÖÎÏ ÔÏÌØËÏ × ÏÞÅÎØ ÓÐÅÃÉÆÉÞÅÓËÉÈ ÓÉÔÕÁÃÉÑÈ ÉÌÉ ÐÒÉÍÅÎÑÅÔÓÑ × ÃÅÌÑÈ ÔÅÓÔÉÒÏ×ÁÎÉÑ.
  2. éÎÄÉ×ÉÄÕÁÌØÎÙÅ ÐÒÏÃÅÓÓÙ ÎÅÚÁ×ÉÓÉÍÏ ××ÏÄÑÔ ÐÏÄÍÎÏÖÅÓÔ×Á Ó×ÏÉÈ ÄÁÎÎÙÈ ÉÚ ×ÎÅÛÎÉÈ ÕÓÔÒÏÊÓÔ×. ôÁËÏÊ ÍÅÔÏÄ Ñ×ÌÑÅÔÓÑ ÚÎÁÞÁÝÉÍ ×Ï ÍÎÏÇÉÈ ÓÌÕÞÁÑÈ, ÎÏ ×ÏÚÍÏÖÅÎ ÔÏÌØËÏ ÐÒÉ ÐÏÄÄÅÒÖËÅ ÕÓÌÕÇ ÐÁÒÁÌÌÅÌØÎÏÇÏ ××ÏÄÁ/×Ù×ÏÄÁ.
  3. ëÏÎÔÒÏÌÉÒÕÀÝÉÊ ÐÒÏÃÅÓÓ ÐÏÓÙÌÁÅÔ ÉÎÄÉ×ÉÄÕÁÌØÎÙÅ ÐÏÄÍÎÏÖÅÓÔ×Á ÄÁÎÎÙÈ ËÁÖÄÏÍÕ ÐÒÏÃÅÓÓÕ. üÔÏ ÎÁÉÂÏÌÅÅ ÏÂÏÂÝÅÎÎÙÊ ÓÃÅÎÁÒÉÊ, ÏÓÏÂÅÎÎÏ ÐÏÌÅÚÎÙÊ ÐÒÉ ÏÔÓÕÔÓÔ×ÉÉ ÕÓÌÕÇ ÐÁÒÁÌÌÅÌØÎÏÇÏ ××ÏÄÁ/×Ù×ÏÄÁ. ëÒÏÍÅ ÔÏÇÏ, ÜÔÏÔ ÍÅÔÏÄ ÔÁËÖÅ ÐÒÉÍÅÎÉÍ ÐÒÉ ××ÏÄÅ ÐÏÄÍÎÏÖÅÓÔ× ÄÁÎÎÙÈ, ÐÏÌÕÞÅÎÎÙÈ ÐÒÉ ÐÒÅÄÙÄÕÝÉÈ ×ÙÞÉÓÌÅÎÉÑÈ, ÏÔÎÏÓÑÝÉÈÓÑ Ë ÄÁÎÎÏÍÕ ÐÒÉÌÏÖÅÎÉÀ.
ôÒÅÔÉÊ ÍÅÔÏÄ ÒÁÓÐÒÅÄÅÌÅÎÉÑ ÉÎÄÉ×ÉÄÕÁÌØÎÏÊ ÒÁÂÏÞÅÊ ÎÁÇÒÕÚËÉ ÔÁËÖÅ ÐÒÉÄÅÒÖÉ×ÁÅÔÓÑ ÄÉÎÁÍÉÞÅÓËÏÊ ÄÉÓÐÅÔÞÅÒÉÚÁÃÉÉ ÄÌÑ ÐÒÉÌÏÖÅÎÉÊ, × ËÏÔÏÒÙÈ ÍÅÖÐÒÏÃÅÓÓÎÙÅ ×ÚÁÉÍÏÄÅÊÓÔ×ÉÑ × ÈÏÄÅ ×ÙÞÉÓÌÅÎÉÊ ÒÅÄËÉ ÉÌÉ ÎÅ ÓÕÝÅÓÔ×ÕÀÔ ×ÏÏÂÝÅ. ïÄÎÁËÏ ÎÅÔÒÉ×ÉÁÌØÎÙÅ ÁÌÇÏÒÉÔÍÙ ÏÂÙÞÎÏ ÔÒÅÂÕÀÔ ÎÅÐÏÓÒÅÄÓÔ×ÅÎÎÙÈ ÏÂÍÅÎÏ× ÚÎÁÞÅÎÉÑÍÉ ÄÁÎÎÙÈ, É ÐÏÜÔÏÍÕ ÔÏÌØËÏ ÉÚÎÁÞÁÌØÎÏÅ ÎÁÚÎÁÞÅÎÉÅ ÐÏÒÃÉÊ ÄÁÎÎÙÈ ÕÄÏ×ÌÅÔ×ÏÒÑÅÔ ÔÁËÉÍ ÓÈÅÍÁÍ. îÁÐÒÉÍÅÒ, ÒÁÓÓÍÏÔÒÉÍ ÍÅÔÏÄ ÒÁÚÂÉÅÎÉÑ ÄÁÎÎÙÈ, ÉÚÏÂÒÁÖÅÎÎÙÊ ÎÁ ÒÉÓ. 85. þÔÏÂÙ ÕÍÎÏÖÉÔØ Ä×Å ÍÁÔÒÉÃÙ A É B, × ÐÅÒ×ÕÀ ÏÞÅÒÅÄØ ÐÏÒÏÖÄÁÅÔÓÑ ÇÒÕÐÐÁ ÐÒÏÃÅÓÓÏ× - ÓÏÇÌÁÓÎÏ ÐÁÒÁÄÉÇÍÅ ``×ÅÄÕÝÉÊ-×ÅÄÏÍÙÊ'' ÉÌÉ ``ÔÏÌØËÏ ÓÔÁÎÃÉÉ''. üÔÏÔ ÎÁÂÏÒ ÐÒÏÃÅÓÓÏ× ÐÒÅÄÎÁÚÎÁÞÅÎ ÄÌÑ ÆÏÒÍÉÒÏ×ÁÎÉÑ ÐÅÔÌÉ. ëÁÖÄÁÑ ÐÏÄÍÁÔÒÉÃÁ ÍÁÔÒÉà A É B ÐÏÍÅÝÁÅÔÓÑ × ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÊ ÐÒÏÃÅÓÓ Ó ÐÏÍÏÝØÀ ÏÄÎÏÊ ÄÅËÏÍÐÏÚÉÃÉÉ ÄÁÎÎÙÈ É ÏÄÎÏÊ ÉÚ ÐÅÒÅÞÉÓÌÅÎÎÙÈ ×ÙÛÅ ÓÔÒÁÔÅÇÉÊ ÒÁÓÐÒÅÄÅÌÅÎÉÑ ÒÁÂÏÞÅÊ ÎÁÇÒÕÚËÉ. ÷ ÐÒÏÃÅÓÓÅ ×ÙÞÉÓÌÅÎÉÑ ÐÏÄÍÁÔÒÉÃÙ ÔÒÅÂÕÀÔ ÐÅÒÅÄÁÞÉ ÉÌÉ ÏÂÍÅÎÁ ÍÅÖÄÕ ÐÒÏÃÅÓÓÁÍÉ, ÔÅÍ ÓÁÍÙÍ ÐÒÅÏÂÒÁÚÕÑ ÏÒÉÇÉÎÁÌØÎÕÀ ËÁÒÔÕ ÒÁÓÐÒÅÄÅÌÅÎÉÑ, ËÁË ÐÏËÁÚÁÎÏ ÎÁ ÒÉÓÕÎËÅ. ÷ ËÏÎÃÅ ×ÙÞÉÓÌÅÎÉÑ, ÏÄÎÁËÏ, ÐÏÄÍÁÔÒÉÃÙ ÒÅÚÕÌØÔÉÒÕÀÝÅÊ ÍÁÔÒÉÃÙ ``ÒÁÚÂÒÏÓÁÎÙ'' ÐÏ ÉÎÄÉ×ÉÄÕÁÌØÎÙÍ ÐÒÏÃÅÓÓÁÍ × ÓÏÏÔ×ÅÔÓÔ×ÉÉ Ó ÚÁÎÉÍÁÅÍÏÊ ÐÏÚÉÃÉÅÊ × ÓÅÔÉ ÐÒÏÃÅÓÓÏ× É ÎÁÐÏÌÎÅÎÙ ÄÁÎÎÙÍÉ ÓÏÇÌÁÓÎÏ ËÁÒÔÅ ÒÁÚÂÉÅÎÉÑ ÒÅÚÕÌØÔÉÒÕÀÝÅÊ ÍÁÔÒÉÃÙ C. ðÒÅÄÛÅÓÔ×ÕÀÝÁÑ ÄÉÓËÕÓÓÉÑ ×ÙÑ×ÉÌÁ ÏÓÎÏ×Ù ÄÅËÏÍÐÏÚÉÃÉÉ ÄÁÎÎÙÈ. ÷ ÓÌÅÄÕÀÝÅÍ ÒÁÚÄÅÌÅ ÂÕÄÕÔ ÐÒÅÄÓÔÁ×ÌÅÎÙ ÐÒÏÇÒÁÍÍÙ-ÏÂÒÁÚÃÙ, ×ÙÄ×ÉÇÁÀÝÉÅ ÎÁ ÐÅÒÅÄÎÉÊ ÐÌÁÎ ÐÏÄÒÏÂÎÏÓÔÉ ÜÔÏÇÏ ÐÏÄÈÏÄÁ.



2004-06-22