اسئلة من كتاب Introduction to alogrithms

وعليكم السلام ورحمة الله وبركاته،

لا توجد مشكلة.

طول الشجرة lg n

عدد الاوراق للشجره cn

الاجمالي cn * lg n

انظر الشكل المرفق

السلام عليكم ورحمة الله وبركاته

أولا : جزاك الله خيرا

ثانيا : فمهت الحمد لله ان بيضرب عدد ورق الشجره فى طولها لكى يحصل على الtotal cost ولكن حساب طول الشجره ثابت أقصد على طول Lg n ??

طول الشجرة يعتمد على عدد التقسيمات. وبما ان التقسيم ثنائي - كل مرة نقسم الى قسمين - فمعناه ان طولها lg n. لفهم الموضوع جرب بامثلة عملية غير في كل من قيمة الn وعدد التقسيمات مثلا ضع ال n = 32 وعدد التقسيمات 2، وهكذا .

بالتوفيق

السلام عليكم ورحمة الله وبركاته

جزاك الله خيرا على التوضيح وماذا عن باقى اسئلتى فى الجزء الاول ... :)

وبالنسبة لحساب lg n عندى مشكلة بسيطه ان شاء الله مع اللوغاريتمات .. فاهمه ان lg n = log_2⁡n

ولكن لكى اتأكد انى فهمتها صح .. حضرتك قولت n=32 وعدد التقسيمات 2 يبقى طول الشجرة log_32⁡n

اقتباس

وماذا عن باقى اسئلتى فى الجزء الاول

لم تكن موجودة سابقا. يبدو انه تم تعديل المشاركة :unsure:

اقتباس

mathemtical induction

طريقة من طرق البرهان على صحة جملة معينه. يمكن الرجوع الى دروس أ عادل Romanof في هذا الموضوع.

/index.php?showtopic=187576&st=0&p=942181&fromsearch=1entry942181

اقتباس

3- بالنسبة لالجوزرم ال Merge فى الكتاب حاطط sentials فى اواخر المصفوفات المتجزئة .. ؟ لماذا .. اقصد ما فائدتها ان وضعت ,, أم لا .. ؟

لم افهم سؤالك.

عموما (وللإقلال من الاسئلة ) يجب الاعتماد على اكثر من مرجع فما لايمكن فهمه في احد الكتب قد يمكن فهمه في كتاب اخر. يمكن ايضا الاستفادة من الموضوع المثبت :

/index.php?showtopic=147401

يوجد فيه شرح واضح مع الامثله بالاضافة الى رابط محاضرات الفيديو من معهد MIT لنفس الكتاب Introduction to Algorithms

بالتوفيق،

ibr_exn كتب:

لم افهم سؤالك.

عموما (وللإقلال من الاسئلة ) يجب الاعتماد على اكثر من مرجع فما لايمكن فهمه في احد الكتب قد يمكن فهمه في كتاب اخر. يمكن ايضا الاستفادة من الموضوع المثبت :

/index.php?showtopic=147401

يوجد فيه شرح واضح مع الامثله بالاضافة الى رابط محاضرات الفيديو من معهد MIT لنفس الكتاب Introduction to Algorithms

بالتوفيق،

السلام عليكم ورحمة الله وبركاته

جزاك الله خيرا على ردودك على أسئلتى ... وبالفعل كنت عدلت فى اسئلتى ..

بالنسبة للمقصود بال Mathematical induction مثال

use mathematical induction to show that when n is an exact power of 2 , the solution of the recurrence .

لم أفهمه ..؟

اعتذر على كثره اسئلتى .. :)

وبالنسبة لحساب lg n .. فاهمه ان lg n = log_2⁡n

ولكن لكى اتأكد انى فهمتها صح .. حضرتك قولت n=32 وعدد التقسيمات 2 يبقى طول الشجرة log_32⁡n ؟؟

اريد افهم شىء متى استخدم

θ

О

₀

جاما

ω

وكيف احدد ال best case to any algorithm or worst case ?

افهم ان best case t فى حالة ان الالجورزم كان ال o/p صحيح ..

اما ال worst case فى حالة ان الالجورزم كان o/p ليس المطلوب أو ان الالجورزم نتيجة مثلا وقف فى تنفيذ أحد ال i/p

وجزاكم الله خيرا مقدما على الردود

و عليكم السلام ورحمة الله وبركاته،

اقتباس

بالنسبة للمقصود بال Mathematical induction مثال

هل قراتي موضوع ا. عادل ؟؟؟ الرابط موجود في مشاركتي اعلاه.

اقتباس

حضرتك قولت n=32 وعدد التقسيمات 2 يبقى طول الشجرة log_32⁡n

اقتباس

اريد افهم شىء متى استخدم

θ

О

₀

جاما

ω

وكيف احدد ال best case to any algorithm or worst case ?

افهم ان best case t فى حالة ان الالجورزم كان ال o/p صحيح ..

اما ال worst case فى حالة ان الالجورزم كان o/p ليس المطلوب أو ان الالجورزم نتيجة مثلا وقف فى تنفيذ أحد ال i/p

وجزاكم الله خيرا مقدما على الردود

هل اطلعتي على محاضرات الفيديو في الرابط اعلاه ؟؟؟

باختصار :

O و اخواتها عبارة عن طريقة للتعبير عن الوقت والمساحة التي تحتاجها الخوارزمية وبالتالي يمكن عن طريقهم مقارنة (استطيع ان اقول ان خوارزمية طالب افضل من خوارزمية طالب اخر عن طريق هذه الرموز) وتصنيف الخوارزميات. يمكن استخدام اي منهم حسب الحاجة لوصف خوارزمية معينه، المهم معرفة معنى كل منهم.

O(n)

معناها ان الخوارزمية لن تأخذ وقت او حجم اكبر من n . يعني في أسوأ حال ستأخذ وقت او حجم n

o(n)

معناها ان الخوارزمية سـاخذ وقت او حجم اقل من n . (لن تصل الى n)

معناها ان الخوارزمية لن تأخذ وقت او حجم اقل من n .يعني في افضل الاحوال ستأخذ n.

معناها ان الخوارزمية ستأخذ وقت او حجم اكبر من n . لن تصل الى n.

معناها ان الخوارزمية ستأخذ وقت او حجم يساوي بالضبط n .

اقتباس

وكيف احدد ال best case to any algorithm or worst case ?

يعتمد على توزيع المدخلات. بمعنى اخر ندرس كل الاحتمالات ونحاول معرفة افضل توزيع واسوا توزيع للمدخلات. مثلا قد تكون خوارزمية معينة تعطي افضل وقت عندما تكون العناصر المدخلة مرتبة تصاعديا وتعطي اسوا وقت عندما تكون العناصر المدخلى مرتبة تنازليا. لذلك يجب دراسة الحالات المختلفة للمدخلات لاعطاء تقييم سليم للخوارزميه.

اكرر يجب حضور محاضرات الفيديو قبل الاسئلة ﻷن فيها توضيح ممتاز للكثير من المفاهيم الاساسية بالاضافة الى شرح وتحليل عدة امثلة من الخوارزميات.

بالتوفيق،

السلام عليكم ورحمة الله وبركاته

عندى استفسار بسيط عن معادلة لا اعلم كيف يتم حسابها

Ө(nlgn)+ Ө(n)

دائما نتجاهل الحدود الاصغر ونكتفي باكبر حد.

في السؤال السابق لدينا حدين :

Ө(nlgn)

و

 Ө(n)

اكبر حد هو

Ө(nlgn)

لذلك سيكون هو الحل..

يمكن معرفة اكبر حد عن طريق التعويض بقيمة n بعدد كبير ، مثلا :

2^20

وحساب قيمة كل حد للحصول على اكبر حد.

بالتوفيق،

السلام عليكم ورحمة الله وبركاته

جزاك الله خيرا

ولكن استفسار اّخر فى حالة

Ө(n)+Ө(n)=؟

يجب ان تكون قادرا على الاجابة من المشاركة السابقة، ضع اجابتك وساخبرك بصحتها. :happy:

السلام عليكم ورحمة الله وبركاته

معك حق ... اخمن ان تكون الاجابة = theta(n ,ولكن مع المسألة التى معى يجب ان تكون النتيجة theta(n^2))

صحيح الاجابة لل

Ө(n)+Ө(n)

هي :

Ө(n)

لاننا نقوم بتجاهل الثوابت ، يعني بالنسبة لنا 3n مثل 1000n ، وهكذا .

اقتباس

ولكن مع المسألة التى معى

لا ادري اي مسألة تقصد

السلام عليكم ورحمة الله وبركاته

المسألة التى أقصدها

use the substitution method to prove that the recurrence

T(n)=T(n-1)+Ө(n)

has the solution

T(n)=Ө(n^2)

فى هذه المسألة حدد انى استخدم ال substitution

بمعنى انى

1- أخمن الحل

2- اثبته

هنا قال ان الحل Ө(n^2)

بمعنى

T (n) = c (n^2-1) +Ө (n)

= c (n^2) – c + Ө (n) // ignore constants

Ө (n^2) +Ө (n )=

وحضرتك قولت قبل كده انى باخد الاكبر فيهم

يعنى = Ө (n^2)

هل كلامى صح أم خطأ .. ؟

لم اتتبع الحل من البداية. الجزئية الاخيرة صحيحه.

اقتباس

= c (n^2) – c + Ө (n) // ignore constants

Ө (n^2) +Ө (n )=

وحضرتك قولت قبل كده انى باخد الاكبر فيهم

يعنى = Ө (n^2)

ممتاز. :happy:

السلام عليكم ورحمة الله وبركاته

الحمد لله طلعت صح .. جزاك الله خيرا

اسمح لى باستفسار اّخر :)

كيف احدد ان الالجورزم stable ??

يعنى اعرف ان counting sort is stable ولكن لاأدرى لماذا ..؟ هل لانه لايعتمد على مقارنه العناصر ببعضها .. ؟ لا أعلم ان كان كلامى صح أم خطأ

ومثلا ماذا عن ال insertion sort , merge sort , heap sort , quick sort

السلام عليكم ورحمة الله وبركاته

معنى stability of any sorting algorithm

يعتمد على كون sorting algorithm يغير فى ترتيب العناصر المراد تخرينها وعلى اساسه بحدد انه stable فى حالة عدم التغيير ... اريد ان افهمها ؟؟

اعتقد انها طريقة من طرق تصنيف خوارزميات الترتيب. فممكن ان نصنف خوارزميات الترتيب حسب الوقت او حسب الذاكره او حسب الاستقرار(stability) ...الخ.

تكون الخوارزمية مستقرة عندما يكون المفتاح key (معلومات اضافيه) طوله ثابت (ليس كل خوارزميات الترتيب تحتاج مفتاح) .مثلا في الRadix sort algorithm اذا كان طول المفتاح ثابت فهي مستقره.

لفهم الموضوع اكثر يجب دراسة الخوارزميات التاليه :Radix sort, Bucket sort

بالتوفيق،

السلام عليكم ورحمة الله وبركاته

جزاك الله خيرا على ردودك على استفساراتى ..

كان عندى سؤال بسيط بالنسبة لرد حضرتك الاخير ... المقصود بال key >> Value or Index of Value ?

وبالنسبة لالجورزم ال Randomized select

قرأت فيه ولكن لم أفهم كيف يتم التنفيذ .. ؟ هل يسير بطريقه ال quicksort ?

فى حالة انى بستخدمه لكى أحصل على أصغر عنصر ..

مثال

كيف سيسير الالجورزم ...؟ ! كيف وجد i , k ... ?

وبالنسبة لطريقة ال quick sort العادية .. فى حاله non decreasing

انى بختار ال pivot وليكن العنصر الاخير ثم بدور من ناحيه يمين ال pivot على أصغر رقم منه .. ومن ناحية اليسار على أكبر رقم من ال pivot ان طلع اليسار أكبر من اليمين ببدل وهكذا بحيث تظهر المصفوفه مرتبه تصاعديا

اما طريقه ال Randomized بختار العنصر عشوائى ويكن ال pivot وببدله بالعنصر الاخير من المصفوفه ثم بطبق نفس الكلام فى السطر السابق ... هل كلام صح أم خطأ ..؟

السلام عليكم ورحمة الله وبركاته

أولا : اعرف انى اثقلت فى اسئلتى على حضرتك ... ولكن قبل ان ارسل استفسارى أكون قد حاولت البحث بنفسى على الحل ..

بالنسبة للينك اللى حضرتك بعته .. حملته .. ووجدث مثال كبير جدااااااا ولم أفهم شىء :) .. اريد فقط الفكره وسوف أطبقها

وجزاكم الله خيرا مقدما

السلام عليكم :

الكورس الكامل مشروح من صاحب الكتاب ، و هذه رابط أول محاضرة

والباقي موجود في نفس الصفحة .

وشكراً

السلام عليكم ورحمة الله وبركاته

الصلاة والسلام على سيدنا محمد "صلى الله عليه وسلم "

اريد منكم تأكدى فهمى ل randomized select for smallest element

مثال