الفصل الخامس

Probabilistic Analysis and Randomized Algorithms

مقدمة

في الفصل الرابع اتعرضنا لما يسمى الrecurrence وقلنا انه عبارة عن معادلة بتوصف function بدلالة قيمتها مع دخل أصغر أو بمعنى تاني بتوصف recursive function يعني دالة بتنادي نفسها مع دخل أصغر لغاية متوصل لدخل صغير جدا تقدر تحل المشكلة عنده , واتعرضنا ل3 طرق لحل الrecurrences وهما الsubstitution method والrecursion-tree method والmaster method . في الفصل ده هنتعرض لنوع جديد من الanalysis وهو الprobabilistic analysis ودي طريقة تحليل بتستخدم لتحليل مشاكل و algorithms كتير جدا , وكمان هنتعرض لproperty(خاصية) ممكن نضيفها لبعض الalgorithms علشان تحل مشاكل معينة والخاصية دي هي الrandomization والalgorithm اللي فيه الخاصية دي اسمه randomized algorithm. علشان نفهم الprobabilistic analysis والrandomized algorithms هناخد مثال لمشكلة نقدر نوظف فيها المفهومين دول.

The Hiring Problem

كلمة hiring جاية من الفعل hire بمعنى يوظف , وبالتالي الhiring problem هي مشكلة توظيف , يعني فيه شركة عندها موظف معين عايزه ترفده(fire) وتوظف واحد مكانه(hire) , بعد محاولات من الشركة للتوظيف فشلت في انها تلاقي موظف , فقررت تعتمد على employment agency(وكالة توظيف) تجبلها موظفين , وكمان الشركة لو وظفت واحد وجه واحد بعديه من خلال الemployment agency أفضل منه هترفد الحالي وتوظف اللي أفضل منه لإنها عايزة دايما يكون عندها أفضل موظف , كل مرة الemployment agency تبعت موظف للشركة الشركة هتعمله interview(مقابلة شخصية) , ولو هو أفضل من الموظف الحالي هترفد الحالي وتوظف(hire) الجديد , إلا في حالة أول موظف تبعته الemployment agency فده بعد الinterview هيتوظف على طول لإنهم عايزين يرفده الموظف الحالي , الemployment agency بتاخد fee(عمولة) على كل موظف تبعته يعمل interview وعمولة تاني أكبر لو الموظف حصله hire . الprocedure ده بنسميه HIRE_ASSISTANT وهنشوف دلوقتي pseudocode ليه.

كلمة assistant يعني مساعد أو موظف يعني

كلمة candidate يعني مرشح للوظيفة

في السطر 1 بيعرف variable وسماه best وده هيخزن فيه الindex بتاع أفضل candidate اتعمله interview حتى الان واداله قيمة 0 علشان لسة معملش interview لأي candidate

في السطر 2 بيدخل for loop هيعدي فيها عالمترشحين كلهم من 1 ل n

في السطر 3 بيعمل interview للcandidate i

في السطر 4 بيشوف candidate i افضل من الbest candidate ولا ﻷ

في السطر 5 لو أفضل هيخزن الindex بتاعه في المتغير best

في السطر 6 هيوظف الcandidate ده بما انه الأفضل حتى الان

الcost بتاع الalgorithm ده مش وقت(time) ولكن فلوس(money) هتتدفع للemployment agency , الcost هنا عبارة عن مجموع تكلفة الinterview بتاع كل candidate وتكلفة الhiring بتاع candidates اللي حصلهم hire , وبالتالي لو عبرنا عن تكلفة الinterview ب C_i وتكلفة الhire ب C_h حيث C_h > C_i وعدد candidate كلهم ب n وعدد candidate اللي حصلهم hire ب m نقدر نعبر عن الcost بتاع الalgorithm بالعلاقة دي

O(nC_i + mC_h)

طبعا ال nC_i دي ثابتة في كل مرة بنشغل فيها الalgorithm لان احنا لازم نعمل interview لكل candidate ولكن اللي بيختلف واللي احنا هنعمله analysis هو ال mC_h لانه بيختلف مع كل مرة بتشغل فيها الalgorithm ممكن مرة توظف candidate واحد وممكن مرة توظفهم كلهم وكل مرة بتوظف عدد مختلف.

الworst case للalgorithm هي ان احنا وظفنا كل ال candidates يعني كل ما ييجي candidate يكون أفضل من اللي قبله فنوظفه وده بيحصل لو المرشحين in increasing order يعني كل واحد افضل من اللي قبله وأفضل واحد هو اخر واحد وبالتالي نقدر نعبر عن الworst case بالعلاقة دي

O(nC_h)

الbest case للalgorithm هي ان احنا وظفنا candidate واحد بس يعني أفضل candidate هو أول candidate اتعمله interview وبالتالي بعد توظيفه مفيش حد اتوظف تاني وبالتالي نقدر عن الbest case بالعلاقة دي

Ω(C_h)

في الحالة دي بنستخدم الprobabilistic analysis في تحديد الaverage case.

Probabilistic analysis

كلمة probabilistic تعني "احتمالي" وجاية من كلمة probability(الاحتمالية) وده موضوع كبير في الmaths , الprobabilistic analysis بقى هي استخدام الprobability في تحليل الproblems , والحقيقة احنا مش هنقدر نفهم الprobabilistic analysis من غير ما نفهم أساسيات الprobability وعلشان الكاتب أورد شرح بسيط للprobability في الكتاب فهنحاول مع بعض نفهم الحاجات اللي احنا محتاجينها في الprobability علشان نفهم الprobabilistic analysis.

Probability Basics

أولا يعني ايه probability؟ وهل هي حاجة معقدة في الmaths بس ولا حاجة بنوظفها يوميا في حياتنا؟ الحقيقة هي انها فعلا حاجة بنستخدمها يوميا في حياتنا من غير منعرف , كمثال لو انت متاكد جدا ان النهاردة إما يوم الخميس أو يوم الجمعة مش أي يوم تاني وواحد صاحبك سألك هو النهاردة الجمعة؟ بترد تقوله بنسبة 50% النهاردة الجمعة , ولو سالتك اشمعنة 50% واحنا مش بنتكلم بالرياضة هتقولي ببساطة انا متاكد ان النهاردة اما الخميس او الجمعة فنسبة الجمعة 50% , فانت في الحالة دي وظفت مفاهيم الprobability من غير متعرف ولما نعرف المفاهيم دي حالا هتعرف تثبت النسبة اللي انت حسبتها قبل كدة بديهيا دلوقتي بالرياضة.

1) أول حاجة نعرفها هي الevent وهو الحدث أو ببساطة ناتج تجربة معينة , كمثال لو التجربة دي ان احنا بنرمي coin(عملة) هيبقى عندك 2 events الاول ان الcoin تظهر ملك والتاني ان الcoin تظهر كتابة , كمثال تاني لو التجربة هو ان احنا بنختار يوم من أيام الأسبوع نعمل فيه حفلة معينة فيبقى عندنا 7 events هما أيام الأسبوع , المثالين اللي فاتو دول كان الevent عبارة عن ناتج واحد بس للتجربة يعني ملك كتابة أو سبت أحد إتنين وهكذا وده بنسميه elementary event يعني ناتج أولي , إيه ده يعني ممكن يكون الevent فيه أكتر من ناتج؟ اه ممكن , في مثال ايام الاسبوع الevent ممكن يكون اكتر من يوم (سبت واتنين وخميس) كمثال لevent وده زي مثلا لو حد سألك أيه نسبة ان النهاردة يكون سبت أو إتنين أو خميس فالevent اللي انت بتحاول تجبله الprobability هنا مكون من 3 elementary events.

2) تاني حاجة الsample space وهي مجموعة من الelementary events بتحدد الpossible outcomes(النتائج الممكنة) لتجربة معينة , زي مثلا أيام الأسبوع دي sample space فيها 7 عناصر {سبت, أحد, إثنين, ثلاثاء, أربعاء, خميس, جمعة} وال sample space لو اخدت جزء منها أو كلها تمثل event وكل event بيكون ليه قيمة probability معينة.

3) تالت حاجة هي الprobability distribution وهي دالة بتحول من الevents لreal numbers والreal numbers دي بتحدد امكانية وقوع الحدث وبنرمز لها Pr{event} , كمثال(الcoin) لو عند sample space S حيث S = {Head, Tail} حيث Head, Tail الelementary events لما تقول Pr{Head} = 0.5 كأنك بتقول إمكانية وقوع الحدث Head بتساوي 50% , في 3 قوانين خاصة بالprobability distribution :

A. 0 <= Pr{A} <= 1 for any event A

يعني أي event الprobability distribution بتاعته بتتراوح ما بين ال0 وال1

B. Pr{S} = 1

يعني لما يكون الevent هو الsample space كلها الprobability distribution بتاعه بيساوي 1 لإن ببساطة هو جامع لكل الelementary events فلازم واحد منهم يحصل وبالتالي الprobability distribution بتساوي 1

C. Pr{A ⋃ B} = Pr{A} + Pr{B}

يعني لو عندك 2 events هما A , B فامكانية ان يحصل واحد منهم(A أو B وده معنى الاتحاد U) هو مجموع امكانية ان يحصل A لوحده و B لوحده

D) رابع حاجة الuniform probability distrbution وكلمة uniform تعني منتظم فالمفهوم ده معناه ان الprobability متوزعة بانتظام على الelementary events اللي في الsample space يعني لكل event A في الsample space

Pr{A} = 1 / |S|

حيث |S| عدد الelementary events في S ويسمى الcardinality

كمثال أيام الأسبوع

S = {Sat, Sun, Mon, Tue, Wed, Thu, Fri}

Pr{Sat} = Pr{Sun} = Pr{Mon} = Pr{Tue} = Pr{Wed} = Pr{Thu} = Pr{Fri} = 1 / |S| = 1 / 7

كدة ده يعتبر uniform probability distribution on S

E) خامس حاجة الrandom variable وهو عبارة عن function بتحول من events في الsample space لreal numbers , وده طبعا نفس تعريف الprobability distribution , ايه الفرق بقى؟ الفرق ان الprobability distribution دالة ليها معنى محدد , أما الrandom variable انا اللي بديله المعنى اللي انا عايزه حسب الproblem , كمثال لو انا برمي 2 coins فال sample space هتكون

S = {HH, HT, TH, TT}

اقدر اعرف random variable واسميه X واعرفه على انه عدد ظهور ال Heads في الevent وبكدة

X(HH) = 2 , X(HT) = 1 , X(TH) = 1 , X(TT) = 0

F) سادس حاجة هي الindicator random variable وهو نوع من أنواع الrandom variable وبيتعرف رياضيا بالشكل ده

X_A = 1 if A occurs

= 0 if A does not occur

يعني كمثال انا ممكن اعرف indicator random variable واسميه Y واعرفه على انه ظهور H في الcoin الاول وبالتالي ال variable بياخد قيمتين , 1 لو الcoin الاول أظهر H و 0 لو مظهرش H .

G) سابع واخر حاجة ان شاء الله هي الexpectation ودي function بطبقها على الrandom variable علشان تحسبلي ال expected value(القيمة المتوقعة) لل variable ده , وتعرف رياضيا كالتالي

E[X] = Summation(x * Pr{X = x})

يعني مجموع حاصل ضرب كل قيمة ممكنة للvariable ده في احتمالية الevents اللي بتنتج القيمة دي للvariable , نشوف مثال علشان نفهم , تطبيقا على مثال الcoins اللي في النقطة 5 , احنا عندنا كام قيمة لX? الاجابة 3 قيم هما 2 و 1 و 0 , نحسب الprobability distribution بتاع كل قيمة للvariable

Pr{X = 2} = 1 / 4 (only one event_HH_ with Pr=1/4 can produce this value for X)

Pr{X = 1} = 1 / 2 (two events_HT, TH_ each of which with Pr=1/4 can produce this value for X)

Pr{X = 0} = 1 / 4 (only one event_TT_ with Pr=1/4 can produce this value for X)

وبالتالي اقدر احسب الexpectation(expected value) للvariable X كالتالي

E[X] = 2 * 1/4 + 1 * 1/2 + 0 * 1/4 = 1

بناءا على التعريف الرياضي السابق للexpectation ممكن نوجد علاقة لحساب الexpectation للindicator random variable كالتالي

E[X] = 1 * Pr{X = 1} + 0 * Pr{X = 0} = Pr{X = 1}

ودي علاقة بتحول مباشرة بين الexpectation وال probability لل indicator random variable وده السبب اللي بيجعل الanalysis باستخدام الindicator random variable في حالات كتير أسهل من استخدام الrandom variable.

دي كانت الرياضة اللي محتاجينها في الprobability علشان نستخدمها في فهم الprobability analysis , ودلوقتي نقدر نعمل analysis لمشكلة الHiring.

Analysis of the Hiring problem

لاستخدام الprobabilistic analysis لازم يكون عندنا معرفة عن الinput distribution(توزيع الدخل) ولو معندناش معرفة بنعمل assumption(فرض) هنا بنفرض ان الcandidates بييجوا بشكل عشوائي in random order(من حيث الكفاءة يعني ميجوش مترتبين من الاصغر كفاءة للأعلى أو العكس) ولما نتعرض للrandomized algorithms هنقدر نشيل الفرض ده.

احنا قلنا ان الanalysis في الhiring problem بيتوقف على عدد candidates اللي هيتم توظيفهم لإن عدد الinterviews ثابت , اللي بيتغير عدد مرات التوظيف , كدة الهدف بتاعنا اننا نحسب الExpected value لعدد ال candidates اللي هيتم توظيفهم , علشان نحسب الExpectation ده هنفرض random variable ونسميه X ونعرفه على انه عدد ال candidates اللي تم توظيفهم , كدة احنا المفروض نحسب الExpected value للX كالتالي

E[X] = Summation(x * Pr{X = x})

صعب جدا نحل المعادلة دي لان من الصعب حساب Pr{X=x} لكل قيم x اللي هي 1 .. n (لان عدد ال candidates اللي ممكن يتوظفو بيتراوح من 1 ودي الbest-case ل n ودي الworst-case) , علشان كدة بنستخدم الindicator random variable , بنعرف عدد n من الindicator random variable , كل variable خاص بcandidate وقيمة الvariable بتساوي 1 لو الcandidate ده اتوظف أو 0 لو متوظفش وبنعبر عن الكلام ده بالشكل ده

X_i = I{candidate i is hired} = 1 if candidate i is hired

= 0 if candidate i is not hired

وبكدة مجموع الindicator random variables دول بيساوي الrandom variable X

X = X1 + X2 + X3 + .... + Xn

نحسب الexpectation ل X بدلالة الindicator random variables

E[X] = E[Summation(Xi)] i = 1 : n

وفيه خاصية في الexpectation اسمها linearity ودي بتثبت ان الـ

expectation of sum = sum of expectation

وبكدة نقدر نقول

E[X] = Summation(E[Xi]) i = 1 : n

كدة فاضل اننا نحسب الexpectation للindicator random variable Xi واحنا عندنا علاقة بتحول الexpectation ل probability

E[X_i] = Pr{X_i = 1}

الcandidate بيتم توظيفه لو هو أحسن من كل الcandidates اللي قبليه , وبما اننا فارضين ان الcandidates بييجوا in random order فنقدر نقول ان احتمالية ان الcandidate i يكون أفضل candidate وسط i number of candidates بتساوي 1 / i لإن ده يعتبر uniform probability distribution وده بسبب الفرض اللي فارضينه.

E[X_i] = Pr{X_i = 1} =

Thus

E[X] = ln n + O(1) (Harmonic series)

وبكدة تم استخدام الprobabilistic analysis في تحديد الaverage case للhiring problem وهو الexpected number of candidates hired.

Randomized Algorithms

مقدرناش نعمل analysis للhiring problem الا بassumption ان الcandidates بييجوا in random order لكن احنا ممكن نشيل الassumption ده باستخدام concept اسمه randomization وهو ببساطة بدل ما تفرض(assume) الrandomness(العشوائية) احنا ممكن نجبر(enforce) الrandomness , وده في المشكلة بتاعتنا ممكن يحصل باننا لما تجيلنا قائمة الcandidates نعيد ترتيبهم بشكل عشوائي , وبكدة نكون اجبرنا الrandomness of input , في الحالة دي الalgorithm بيتحول randomized algorithm وهو algorithm الbehaviour بتاعه مش بيتوقف بس على الinput ولكن بيتوقف أيضا على values produced by random number generator وهي الrandomness اللي احنا ادخلناها في الalgorithm , وبكدة الrandomized algorithm يزيد خطوة واحدة عن الalgorithm العادي وهي خطوة اعادة الترتيب عشوائيا.

Randomly permuting arrays

الخطوة الأولى في الrandomized algorithm بتاعنا هي انك تعيد ترتيب(permute) الarray بشكل عشوائي ,في اكتر من طريقة لتنفيذ الpermutation , هنشوف 2 algorithms في الفصل ده.

أول algorithm معانا اسمه Permute_By_Sorting ومن اسمه في عملية sorting وهي ضد عملية الpermutation ازاي ده؟ ببساطة في الalgorithm ده بيعدي على كل عنصر في الarray ويديله قيمة priority(أولوية) عشوائية بعد كدة يرتب الarray بناءا على قيم الpriorities دي وبكدة أعاد ترتيبهم بشكل عشوائي لإن القيم اللي بيرتب بناءا عليها (priorities) جبناها بشكل عشوائي (by random number generator).

في السطر 3 بيجيب قيمة priority عشوائية ما بين ال1 والn^3 علشان يضمن إلى حد كبير ان قيم الpriorities تكون unique(مش متكررة).

في السطر الرابع مش خطوة عادية دي محتاجة algorithm يعمل sorting واحنا هنا ممكن نستخدم الmerge sort على سبيل المثال.

تاني algorithm معانا اسمه Randomize_In_Place ومن اسمه بيرتب في نفس الarray مش محتاج يخزن قيم برة الarray زي الPermute_By_Sorting , والحقيقة الalgorithm ده أسهل بكتير , ببساطة بيعدي على كل عناصر الarray وكل مرة يعمل swap(تبديل) للعنصر مع عنصر عشوائي من الarray.