معرفی روش انقباض

هدف این مقاله، معرفی روش انقباض برای تحلیل الگوریتم ها است. بر اساس این روش، چندین رده از روابط بازگشتی می توانند به عنوان حالت های خاص چارچوب کلّی بیان شده تحلیل شوند. گام های اصلی این فن بر اساس ویژگی های انقباض الگوریتم نسبت به متر های احتمالیِ مناسب پایه ریزی می شوند. نوعاً توزیع حدی به عنوان نقطه ثابت یک عملگر حدی روی ردۀ توزیع های احتمال مشخص سازی می شود.

Introducing the Contraction Method

The goal of this paper is to introduce the contraction method for analysing the algorithms . By means of this method several interesting classes of recursions can be analyzed as paricular cases of the general framework . The main steps of this technique is based on contraction properties of algorithm with respect to suitable probability metrics . Typlically the limiting distribution is characterized as a fixed poin of a limiting operator on the class of probability distributions .