چکیده
مسئله ی نزدیک ترین رمز واژه(NCP)، در نظریه ی کدهای تصحیح خطا، یک سوال الگوریتمی میباشد. در یک نقطه ی، و یک فضای خطی، با ابعادk، NCP به دنبال یک نقطه ی بوده، که این نقطه، فاصله ی تا v را کمینه میکند. مسئله ی نزدیک ترین رمزواژه، یک مسئله ی NP-hard میباشد. بنابراین، در این زمینه، الگوریتم های تقریب، مورد توجه میباشد. کارآمدترین الگوریتم های تقریب برای NCP، تا به امروز، مربوط به Bermn و Karpinski میباشد. اینها الگوریتم ها به ترتیب، یک الگوریتم قطعی بوده که به یک نسبت تقریبِ برای ثابت دلخواه c نائل شده و یک الگوریتم تصادفی میباشد که به نسبت تقریب نائل میشود.
در این مقاله، ما الگوریتم های قطعی را برای تقریب NCP ارائه میدهیم، که در مقایسه با کارهای قبلی، به طور قابل ملاحظه ای بهبود یافته است.
فهرست مطالب
1-مقدمه
2-الگوریتم تقریبO(n/ Loog n)
3-یک الگوریتم تقریب O(k log(s) n/ log n) بازگشتی
4-مسئله ی نقطه از راه دور
5-نتیجه گیری
6-مراجع
میتوانید از لینک ابتدای صفحه، مقاله انگلیسی را رایگان دانلود فرموده و چکیده انگلیسی و سایر بخش های مقاله را مشاهده فرمایید.