كتب M-Ray-Y: سمعنا أنو عندك أسئلة الاتصالات يا ريت تشحدنا ياهم زكاتك أولاً : شو جاب سيرة أسئلة الاتصالات على لسانك هلأ ؟؟؟؟ ثانياً : ياريــــــــــــــــــــــــــت يكون عندي ياهم .... ثالثاً : معقول أنت .. معقــــــــــــــول .. معقولة روح خبيهم وخليك تشحدهم مني شحادة .. !؟؟! الله يسامحك يا رب هيك ما حبيتها منك منوب هي .. ما أنا ضد فكرة الأنانية والاحتكار .. وتجي تبليني بهالتهمة الباطلة يا ظالمني .؟؟؟!!!
بإذن الله تعالى إذا وقعوا بين إيديي لنزلهم على الموقع .. ولو يا زلمة شبنا أنا Dr.Siko مو حدا تاني  منرجع لصلب همنا .. مسألة في البيان .. فحلها إن شئت فيما بعد أو الآن ... نقول عن بيان موجه أنه متشابك lattice إذا احتوى على : 1- عقدة نصل منها إلى جميع العقد الأخرى
2- وعقدة يمكن أن نصل إليها من جميع العقد اكتب خوارزمية لتحديد فيما إذا كان البيان الموجه G من النوع المتشابك Lattice ؟؟ الحــــــــل : حسناً .. هنا لدينا شرطان لكون البيان G متشابكاً .. وعلينا حل كل منها على حدا : المبدأ : سأستخدم هنا جدول التجاور حيث يستفاد منه في معرفة الأسهم الصادرة والواردة من وإلى العنصر الواحد .. وهو يعرف بالشكل : Type AdjArray = Array [1..n,1..n] of Boolean AdjArray يعني adjacency Array ( جدول التجاور ) وبفرض أنه جاهز للعمل عليه .... الشرط الأول : عقدة نصل منها إلى جميع العقد الأخرى :
أي أن هذه العقدة لديها أسهم ( صادرة ) تصل إلى جميع عناصر البيان .. ونحن نعلم أن في جدول التجاور يكون كل سطر (i) يعبر عن الأسهم الصادرة للعنصر رقم (i) وبالتالي إن فحصنا سطر عنصر معين ووجدنا أن كل خانات هذا السطر تحوي القيمة البوليانية ( True ) مــــا عـــــدا خانة العنصـــــر نفسه أي [i,i] لأن العنصر لا يشير إلى نفسه .. فالعنصر صاحب هذا السطر يحقق الشرط المطلوب ! كتابة الخوارزمية : ليكن لدينا التابع One_to_All والذي يتحقق من الشرط الأول من المسألة .. علينا فحص كل سطر من أسطر الجدول AdjArray بغية البحث عن العنصر الذي يحقق الشرط .. سنقوم بالبحث في الأسطر الواحد تلو الآخر حتى نجد عنصرا يحقق المطلوب فنتوقف عن البحث لأنه لا داعي لإكمال البحث إن وجد عنصر واحد على الأقل يحقق الشرط .. ودائماً نقوم بفرض أن العنصر يحقق الشرط حتى يثبت العكس ( أي أن نجد قيمة واحدة على الأقل False ) وبالتالي يدوم البحث حتى تحقق الشرط أو انتهاء البحث في جميع العناصر ولنكتب الخوازمية : Function One_to_All (G:AdjArray;n:integer):Boolean Var Proper:Boolean
I,J:Integer Begin
I:=1
Repeat
Proper:=True
For J:=1 to n do
If (I<>J) Then
If (G[I,J]<>True) Then
Proper:=False
I:=I+1
Until (I>N) Or (Proper)
One_to_All:=Proper
End الشرط الثاني : عقدة يمكن أن نصل إليها من جميع العقد : في هذا العنصر نلاحظ أن جميع العناصر تصل إليه .. أي أن جميع العناصر لديها أسهم صادرة إليه
وبالتالي فإنه ( يرد ) إليه أسهم من جميع العناصر الموجودة في البيان G
ونعلم أن في جدول التجاور تمثل الأعمدة الأسهم الواردة إلى كل عنصر من العناصر... فلو أثبتنا أن لعمود ما يحوي جميع خاناته على القيمة True مـــا عــــدا العنصر نفسه [i,i] بالتالي نحقق الشرط الثاني .. الخوارزمية :
بنفس الخوارزمية السابقة لكن الآن نريد المقارنة من أجل الأعمدة لا الأسطر .. وسأسمي التابع هذه المرة All_to_One : Function All_to_One (G:AdjArray;n:integer):Boolean
Var Proper:Boolean
I,J:Integer Begin
I:=1
Repeat
Proper:=True
For J:=1 to n do
If (I<>J) Then
If (G[J,I]<>True) Then
Proper:=False
I:=I+1
Until (I>N) Or (Proper)
One_to_All:=Proper
End الآن نريد تابعاً ثالثا وبسيطا نسمية IsLattice يختبر فيما إذا تحقق شرطا التشابك في البيان .. ففي حال تحقق شرط One_to_All و All_to_One بأن يعيدا القيمة True معاً .. فالبيان متشابك حقاً .. Function IsLattice (G:AdjArray;N:Integer):Boolean Begin
If (One_to_All) and (All_to_One) Then
IsLattice:=True
Else
IsLattice:=False
End سؤال صغير : احسب كلفة هذه الخوارزمية ؟؟ الحــــل : هنا وقعت في طامة كبيرة !! المشكلة في الكلفة الكبيرة التي تسببها خوارزميتي .. ففي كلا التابعين One_to_All و All_to_One نجد أن كلفة كل منها هي N*N=N^2 حيث يتم الفحص جميع الأسطر والأعمدة وبما أنه يتم البحث مرتين في جدول التجاور فإنه يجب تحقق الشرطين .. وبالتالي يكون كلفة البحث هي N^2*N^2=N^4 !! كلفة كبيرة ... وهذه مشكلة .. لكن لا تقلقوا ... لقد أصلحت الوضع نوعاً ما !! يمكننا دمج الشرطين في تابع واحد ولا داعي لأن أغوص في البحث مرتين عن العناصر التي تحقق الشروط .. فنقوم في كل مرة بفحص السطر والعمود .. وليس كل منهما على حدا .. فإن تحقق الشرط الأول نضع قيمة True لمتحول بولياني Horizonal وإذا تحقق الثاني نضع قيمة True للمتحول البولياني Vertical .. مع ملاحظة أنه عندما يتحقق أحد الشروط ( لا ) نقوم بإعادة البحث في الأسطر الأخرى ... وعند تحقق الشرطين معاً نقوم بإنهاء البحث .. Function IsLattice (G:AdjArray;N:Integer):Boolean Var I,J:Integer
Horizonal,Vertical,Cond1,Cond2:Boolean Begin I:=1
Cond1:=False
Cond2:=False
Repeat Horizonal:=True
Vertical:=True
For J:=1 to N Do
If (I<>J) Then
If ( Not Cond1 ) and (G[I,J]<>True) Then
Horizonal:=False
If ( Not Cond2 ) and (G[J,I]<>True) Then
Vertical:=False
If Horizonal Then Cond1:=True
If Vertical Then Cond2:=True Until (I>N) Or (Cond1 and Cond2)) If (Cond1 and Cond2) then
IsLattice:=True
Else
IsLattice:=False
End 3 في واحد !!! دمجنا ثلاثة توابع في تابع واحد جيد نوعا ما ... وبالتالي انخفضت كلفة البحث إلى النصف N^2 قد تستغربون من Cond1 و Cond2 .. أقصد بهما 1st condition و 2nd Condition ففي حال تحقق الشرط الأول نحتفظ به في متحول خاص لكي لا نعيد البحث في الأسطر الباقية فلا حاجة لنا بذلك طالما وجدنا عنصرا على الأقل يحقق ذلك . وكذلك الأمر بالنسبة للشرط الثاني .. سؤال شخصي : ما الفرق بين الشرط الثاني من المسألة والبؤرة في البيان ؟؟ الجواب :
البورة هي كما تعلمنا وجاءنا في امتحان العملي هي التي يرد إليها أسهم من جميع العناصر ( و ) لا يصدر منها أية أسهم .. بينما في الشرط الثاني ليس من الشرط أن لا يصدر منها أي سهم .. قد يصدر منها سهم أو سهمان إلى العناصر لكن هذا لا يهم .. المهم أن يرد إليها أسهم من جميع العناصر الموجودة في البيان فحسب .. فتصور يرعاك الله .. ماشي بكرة ممكن ننزل مسألة عن تنظيم الملفات .. ادعولنا وشدوا حيلكم ...
|
أرسل من قبل 
