ترجمه مقاله الگوریتم های تخمین قطعی، برای مسئله ی نزدیک ترین رمزواژه

عنوان مقاله انگلیسی

Deterministic Approximation Algorithms for the Nearest Codeword Problem

عنوان ترجمه فارسی

ترجمه مقاله الگوریتم های تخمین قطعی، برای مسئله ی نزدیک ترین رمزواژه

دسته : فناوری اطلاعات

ترجمه مقاله الگوریتم های تخمین قطعی، برای مسئله ی نزدیک ترین رمزواژه


چکیده

مسئله ی نزدیک ترین رمز واژه(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-مراجع

 

Abstract

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point and a linear space dimension k NCP asks to find a point that minimizes the (Hamming) distance from v: It is well-known that the nearest codeword problem is NP-hard. Therefore approximation algorithms are of interest. The best e_cient approximation algorithms for the NCP to date are due to Berman and Karpinski. They are a deterministic algorithm that achieves an approximation ratio of for an arbitrary constant ; and a randomized algorithm that achieves an approximation ratio of . In this paper we present new deterministic algorithms for approximating the NCP that improve substantially upon the earlier work

Contents

  1. Introduction
  2. An O(n/ log n)-approximation algorithm
  3. A recursive O(k log(s) n/ log n)-approximation algorithm
  4. The remote point problem
  5. Conclusion

6.References


نویسنده/ناشر/نام مجله :
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

سال انتشار

2009

کد محصول

1000048


 

تعداد صفحات انگليسي

13


 

تعداد صفحات فارسي

15


 

نوع فایل های ضمیمه

Pdf+Word


 

حجم فایل

610 کیلو بایت


 


Random Posts

One thought on “ترجمه مقاله الگوریتم های تخمین قطعی، برای مسئله ی نزدیک ترین رمزواژه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

*
*

5 × 5 =