Pollard's kangaroo algorithm
کمپیوٹیشنل نمبر تھیوری اور کمپیوٹیشنل الجبرا میں، پولارڈ کا کینگرو الگورتھم (پولارڈ کا لیمبڈا الگورتھم بھی، نیچے نام رکھنا دیکھیں) مجرد لوگرتھم کے مسئلے کو حل کرنے کے لیے ایک الگورتھم ہے۔ الگورتھم کو 1978 میں نمبر تھیوریسٹ جان ایم پولارڈ نے اسی مقالے میں متعارف کرایا تھا جس میں اسی مسئلے کو حل کرنے کے لیے ان کا مشہور پولارڈ کا rho الگورتھم تھا۔ اگرچہ پولارڈ نے یونٹس ماڈیولو اے پرائم پی کے ضرب گروپ میں مجرد لوگرتھم کے مسئلے پر اپنے الگورتھم کے اطلاق کو بیان کیا، لیکن حقیقت میں یہ ایک عام مجرد لوگرتھم الگورتھم ہے-یہ کسی بھی محدود چکور گروپ میں کام کرے گا۔ الگورتھم فرض کریں کہ ترتیب کا ایک محدود چکور گروہ ہے جو عنصر سے پیدا ہوتا ہے، اور ہم بیس پر عنصر کا مجرد لوگارتھم تلاش کرنے کی کوشش کرتے ہیں۔ دوسرے لفظوں میں، کوئی ایسا تلاش کرتا ہے۔ لیمبڈا الگورتھم کسی کو کچھ وقفے میں تلاش کرنے کی اجازت دیتا ہے۔ کوئی بھی ممکنہ لوگرتھم کی پوری رینج کو اور ترتیب دے کر تلاش کر سکتا ہے۔ 1. تقریبا اوسط کے مثبت عددوں کا ایک مجموعہ منتخب کریں اور سڈورینڈم نقشے کی وضاحت کریں۔ 2. ایک عدد کا انتخاب کریں اور گروپ عناصر کی ترتیب کا حساب لگائیں: 3۔ حساب لگائیں کہ: 4۔ گروپ عناصر کی دوسری ترتیب کا حساب لگانا شروع کریں: اور انٹیجرز کی متعلقہ ترتیب کے مطابق: مشاہدہ کریں کہ: 5. مندرجہ ذیل شرائط میں سے کسی ایک کو پورا کرنے کی شرائط کا حساب لگانا بند کریں: A) کچھ کے لیے۔ اگر ترتیبات اور "ٹکرانے" اس انداز میں، تو ہمارے پاس ہے: اور اس طرح ہم ہو گئے ہیں۔ ب)۔ اگر ایسا ہوتا ہے، تو الگورتھم تلاش کرنے میں ناکام رہا ہے۔ اس کے بعد کی کوششیں اور/یا کے انتخاب کو تبدیل کر کے کی جا سکتی ہیں۔ پیچیدگی پولارڈ الگورتھم کی وقت کی پیچیدگی کو اس مفروضے پر مبنی ممکنہ دلیل کا استعمال کرتے ہوئے پیش کرتا ہے جو فرضی طور پر کام کرتا ہے۔ چونکہ بٹس کا استعمال کرتے ہوئے نمائندگی کی جا سکتی ہے، اس لیے یہ مسئلہ کے سائز میں ایکسپونینشل ہے (حالانکہ اب بھی وقت لینے والے ٹریوئل بروٹ فورس الگورتھم کے مقابلے میں ایک اہم بہتری ہے)۔ سب ایکسپونینشیل ٹائم ڈسکریٹ لوگرتھم الگورتھم کی مثال کے لیے، انڈیکس کیلکولس الگورتھم دیکھیں۔ الگورتھم کو دو ناموں سے جانا جاتا ہے۔ پہلا "پولارڈ کا کینگرو الگورتھم" ہے۔ یہ نام الگورتھم پیش کرنے والے کاغذ میں استعمال ہونے والی مشابہت کا حوالہ ہے، جہاں الگورتھم کی وضاحت جنگلی کینگرو کو پھنسانے کے لیے ٹام کینگرو کے استعمال کے لحاظ سے کی گئی ہے۔ پولارڈ نے وضاحت کی ہے کہ یہ مشابہت سائنسی امریکی کے اسی شمارے میں شائع ہونے والے ایک "دلچسپ" مضمون سے متاثر تھی جو آر ایس اے پبلک کلیدی کرپٹو سسٹم کی نمائش کے طور پر شائع ہوئی تھی۔ مضمون میں ایک تجربہ بیان کیا گیا ہے جس میں کینگرو کی "حرکت کی توانائی بخش لاگت، جسے مختلف رفتاروں پر آکسیجن کی کھپت کے لحاظ سے ماپا جاتا ہے، کا تعین ٹریڈمل پر کینگروز رکھ کر کیا جاتا ہے۔" دوسرا "پولارڈ کا لیمبڈا الگورتھم" ہے۔ پولارڈ کے ایک اور مجرد لوگرتھم الگورتھم، پولارڈ کے rho الگورتھم کے نام کی طرح، یہ نام الگورتھم کے تصور اور یونانی حرف lambda () کے درمیان مماثلت کی طرف اشارہ کرتا ہے۔ لیمبڈا حرف کا چھوٹا اسٹروک ترتیب سے مطابقت رکھتا ہے، کیونکہ یہ پوزیشن b سے x کے دائیں طرف شروع ہوتا ہے۔ اس کے مطابق، لمبا اسٹروک اس ترتیب سے مطابقت رکھتا ہے، جو پہلی ترتیب سے "ٹکرا جاتا ہے" (بالکل لیمبڈا کے انٹرسیکٹ کے اسٹروک کی طرح) اور پھر بعد میں اس کے بعد آتا ہے۔ پولارڈ نے "کینگرو الگورتھم" نام کے لیے ترجیح کا اظہار کیا ہے، کیونکہ اس سے ان کے رو الگورتھم کے کچھ متوازی ورژن کے ساتھ الجھن سے بچا جا سکتا ہے، جنہیں "لیمبڈا الگورتھم" بھی کہا جاتا ہے۔ ڈائنکن کی کارڈ ٹرک کروسکل کاؤنٹ رینبو ٹیبل حوالہ جات مزید پڑھنا نمبر تھیوریٹک الگورتھم کمپیوٹر الجبرا لوگرتھمز