درس طراحی الگوریتم ها

صفحه 1:
درس طراحی الگوریتم ها (با شبه كد هاى 0 ++) تعداد واحد: © تهیه کننده : جعفر. پورامینی منبع : کتاب طراحی الگوریتمها مترجم : جعفر نژاد قمی 

صفحه 2:
فصل اول: كارايى » تحليل و مرتبه الكوريتم ها 

صفحه 3:
ین کاب در باره تکنیکگگهای مربوط به حل مسانل آکت. . تکنیک » روش مورد استفاده در حل مسائل است. * مسنله » پرسشی است که به دنبال پاسخ آن هستیم. 

صفحه 4:
" بكار بردن تکنیک منجر به روشی گام به گام (الگوریتم ) در حل یک مسئله می شود. * منظوراز سیم بودن یک الگوربنم» بعنی تحلبل آن از لحاظ زمان و حافظه. 

صفحه 5:
* نوشتن الگوریتم به زبان فارسی دو ايراد دارد: 0- نوشتن الگوریتم های پیچیده به این شیوه دشوار است. ©- مشخص نیست از توصیف فارسی الگوریتم چگونه می وان یک برنامه کامپپوثری اپجاد کرد. 

صفحه 6:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس الكوريتم 0-0): جسث و جوى ترتيبى ا م لبون [Jovwthevre © >< مها مسا قسل) } 1 = مسا while (loouiva <= 0 && G[ocuiog) | = x) +۲ ® (bouton > a) : ‏مسا‎ = O 

صفحه 7:
OO ‏الگوریتم 2.-1):محاسبه مجموع عناصر آرایه‎ ([ آه تایه اوه , ۰ ۵) مه ولمم } ۱ ‎rest‏ امسمز ‎res =O ‎Por (1 = 0; 1 <= oy r++) res = rest + ofl] ‏ای مه‎ ‎{ 

صفحه 8:
OO ‏الگوریتم 1-0):مرتب سازی تعویضی‎ مسئله: ب كليد را به ترتیب غیر نزولی مرتب سازی کنید. vod exchanesovt (tat ۰ , ‏مها‎ 6۵] [( } tendo ti Por (1 = 0; <= a -C; r++) Por (j= 1+; | <= 35 i++) ‏ع‎ ) ۵11 > ۵][( ‏اس‎ ۵] aed Oli] { 

صفحه 9:
‎oO "‏ الگوریتم <1-6):ضرب ماتریس ها ‏۰ ات لس ‏0 اس [] [], ‎} ‎jeder ti, ‎Por (4= 0; 1<5 05 H+) {Por ) - 0 <= 05 i++) Ch=o 

صفحه 10:
Por (k= 0; k <= aj K++) OC Mil =Cl + © ۱۱۳ * ۵ ۳۲ 

صفحه 11:
© 0اهمیت ساخت الگوریتم های کارآمد تعداد مقايسه هاى | تعداد مقايسه هاى ال شده ومط | ادجم قد توسق 8 جست و جوى دودويى معمولا جستجوى دودويى ‎١‏ | جستجوى ترتيبى | اندلزه آرليه بسيار سريع تر ازجسث و جوی ترتيبى است. 0 66 ©2606 | " تعداد مقايسه هاى انجام شده توسط جست و جوی دودوبی ‎aoe | aoe a‏ و ‎aoreo? | aro? eq‏ 8 9 69 اووعووم | ومهومم ‎ROOF 7008‏ 

صفحه 12:
OO ‏الگوریتم 4-): جست و جوی ترتیبی‎ ‎ta‏ ( داف ‏6 مها سس[ ] ‏> ههار ‏مسا قل) ‎} ‏20 مسا ‏(<-۲ [مسسان 86 ۰ -> سس طا ۲( ‎® (bound > «) ‏0 > مسا 

صفحه 13:
OO ‏الكوريتم 1-6): جست و جوی دودویی‎ یبا لبون © مجهوصا ددر[ ], >< ها (terdex 8 locations: } ‎wid‏ لیا رس تا ‎thw = (5 ick = a ‎jeden = O ‎} ahd (aw <= high && locaton = = 0( :[ ‏سط) > وه‎ + YO 

صفحه 14:
(س] ۵ :)۵ ‎wid‏ = مسا (7] ۵ > ) ۵ سا 7-0 2 يوار ‎ole‏ jaw 2 ٩ + { { 

صفحه 15:
OO ‏الگوریتم 20-0 جمله « ام فيبوناجى (بازكشتى)‎ ‏مسثله : جمله ج ام از دنباله فيبوناجى را تعيين كنيد.‎ tt Bib (tet) } ۸ ) > 0 ۱۳۵ نينا wetura Pb (a - 0( + ‏دع‎ )0- 8) { 

صفحه 16:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏الگوریتم ©7-):جمله دام فیبوناچی (تکراری) tat PEO (ct a) Por (= 8 31 <= a itt) PO SP + ۲ ‏زمه‎ ‎{ wetura Pfc] { 

صفحه 17:
4 تحلیل الگوریتم ها * برای تعیین میزان کاربایی یک الگوریتم را باید تحلیل كرد. 0-6-0 تحليل بيجيدكى زمانى " تحليل بيجبدكى زيمالى يك الكوريثم » تعيين تعداد دفعاتى است كه عمل اصلى به ازاى هر مقدار از ورودى انجام 8 می موی 

صفحه 18:
* (۲)0" را پیچیدگی زمانی-لگورینم در حاملمعمول می‌گویند. " (11/)2 را تحليلييجيدكوزمانىدر بدترينحالك مى نامند. " ()ث را بيجيدكوزمانودر حال لتميادكين مى كويند. 

صفحه 19:
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(جمع کردن عناصرآرایه) عمل اصلی: افزودن یک عنصر از آرایه به میرح اندازه ورودی: ‎cn‏ تعداد عناصر آرایه. TMa)=a 

صفحه 20:
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(مرتب سازی تحویضی) حمل اصلی: مقایسه [] 65 با []) . اندازه ورودی: تعداد عناصری که باید مرتب شوند. ٩ = ua 4( le 

صفحه 21:
تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم(جست و جوی ترئیبی) عمل اصلی: مقایسه یک عنصر آرایه با اندازه ورودی: , > تعداد عناصر موجود در آرایه. 0 )( 2۰ 

صفحه 22:
تحایل پیچیدگی زمانی در بهترین حالت برای الگوریتم(جست وجوی ترئیمی) عمل اصلی: مقایسه یک عنصر آرایه با > اندازه ورودى: , ه تعداد عناصر آرایه. ® (x) =4 

صفحه 23:
40-مرتبه الگرریتم * الگوریتم ها یی با پیچیدگی زمانی ازقبیل ۰ وه00 ‎ao) Ga So St‏ * مجموعه کامل توابع پیچیدگی را که با توابع درجه دوم محض قابل دسته بندی باشند» 6 ) (2» می گویند. 

صفحه 24:
* مجموعه ای ازتوابع پیچیدگی که با توابع درجه سوم محضص قابل دسته بندی بشند» 8 ) (3- نامیده می شوند. * برخی از گروه های پیچیدگی منداول در زیر داده شده است: 9 © 8 > (2) 6 > (2) 6 > (دجاء) 6 > «) 9 > 60۰ 

صفحه 25:
6-0 ‌آشنایی بیشتر با مرتبه الگوریتم ها * برای یک تابع پیچیدگی مفروض 0 )=( ‎(f‏ 0 ()ز بزرگ* مجموعه ای از توابع پیچیدگی () ٍ اسث که برای آن ها پک ثابت حقبفی مثبت ء و يك عدد صحيح غير منفى ۱ وجود دارد به قسمی که به ازای همه ی 0 >- ۱ داریم: ۱ )0( << ۰ * f (9) 

صفحه 26:
* برای یک تابع پیچیدگی مفروض (0)) (6) ۰ («) [مجموعه اى از توابع بيجيدكى (2) © است که برای آن ها یک عدد ثابت حقبفی مثبت ء و یک عدد صحبح غبر منفی [۱ وجود دارد به فسمی که به ازای همه ی 1 ع- ‎N‏ داريم: a(s) =< 0 * f (9) 

صفحه 27:
برای یک تابع پیچیدگی مفررض (0) داریم: ‎(F(=)) =O (F(@) N Q (Fe)‏ 8 یعنی ((0))0 مجموعه ای از توابع پیچیدگی (۳) [) است که پرای آن ها ثابت های حقیقی مثبت 6 و اه و عدد صحیح غیر منفی آ[ وچود دارد به قسمی که : 0% f(s) <=4* f(s) 

صفحه 28:
" براى يك تابع بيجيدكى ‎f(a)‏ مفروض.»( 2" (0) 7 کوچک" عبارت ازمجموعه کلیه توابع پیچیدگی(ه) ب است که این شرط را برآورده می سازند : به ازای هرثابت حقیقی مثبت ء »یک عدد صحيح غير منفى () وجود دارد به قسمى كه به ازای همه ى « >> © ‎wh‏ u(x) =< 0X Ff (3) 

صفحه 29:
ویژگی های مرتبه 4 (ه) 6 (م)۶) ۵ اگروفقط اگر.((۰)0) ۵ 6 )©( ‎f‏ ‎(f(s) ©‏ )( 4 6 9 اگررفقط اگر((م) م) 69 (م) ]. © اكر 0< ط و 0 < 4 در آن صورت: (5 هه 6 6 ۰ با اگر (0 <»< ط »در أن صوريث: ‎fv (bn)‏ 

صفحه 30:
OO : ‏به ازای همه ی مقادیر 0 < ۰ داریم‎ -5 w¥ Eo (al) 90 >= Ord >O g(a) Ev (f(a), 51-6 ‏درآن‌صورت‎ wal, h(a) € O(f(a)) ۷ wa) +d X k (a) 6 9 )۲)0( 

صفحه 31:
> ترنیب دسته های پیچیدگی زیر را در نظربگیرید: ‎(al)‏ 8 رم 6 رم 6 رم 6 ‎(x) Ofaka x) O(c?) O(c)‏ 6 دم و که در آن 6 <۲<۱و0 <۰ < ۲ است. اگر تابع پیچیدگی (9) © در مسته لوولقعدر طرفجيمستهى حايو(») لل ‎Wak‏ در آن صورت: ‎۱ )0( 6۰ ))0( ‎ 

صفحه 32:
فصل دوم: روش تقسيم و حل 

صفحه 33:
* روش تقسیم و حل یک روش بالا به پایین است. " حل يك نمونه سطح بالای مسئله با رفتن به جزء و بدست آوردن حل نمونه های کوچکتر حاصل می شود. 

صفحه 34:
* هنگام پی ریزی یک الگوریتم بازگشتی » باید: 0 راهی بربای به دست آوردن حل یک نمونه از روی حل ‎ean‏ ‎-~C‏ شرط(شرایط ) نهایی نزدیک شدن به نمونه(های) کوچک تر را تعیین کنیم. ‎da -9‏ را در حالث شرط (شرایط)نهایی نعیین کنیم. 

صفحه 35:
2ة## ‎OO‏ ‏الگوریتم0-0: جست و جوی دودوبی (بازگشتی) ( ۱ رهاط ) مها بط ‎(ow + (6‏ - لود [: (لسم] ۵ - ع م) ج ‎wwetura wid‏ 

صفحه 36:
(س] © > > ) م جام ‎toa ARO)‏ اه retwra. bouton (cord + (1, hick) { { 

صفحه 37:
تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم جست و جری دودویی بازگشتی عمل اصلی: مقایسه > با [لبب] نک اندازه ورودی: »۰ تعداد عناصر آرایه. (9/) 0 2 (و) ۵ برای ۰۰ 6< ۰ ثوالی از 8 است + (6/) 0 ۶ و) 4 2 () ۵ وب 6 6 0 + [ 1 ع (و) 0 

صفحه 38:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس مصرتب سازی ادغامی * ادغام یک فرآیند مرتبط با مرتب سازی است. * ادغام دوطرفه به معنای ترکیب دو آرایه مرتب شده در یک آرایه ی مرئب است. 

صفحه 39:
* مرتب سازی ادغامی شامل مراحل زیر می شود: 0- تقسیم آرايه به دو زير آرايه» هر یک با 10/2 عنصر. ©- حل هر زير آرايه با مرتب سازی آن. ©- تركيب حل هاى زير آرايه ها از طريق ادغام آن ها در يك آررايه مرتب. 

صفحه 40:
‎oO "‏ الگوریتم0-0: مرتب سازی ادخامی ‏([] 0 مهو , ۰ ۳۱ 5 عم , | ۲21۱۵ با سس ‎[C..0]‏ 10:0 0 بهیا: ‎( 6) <0( ‎op Of] ‏مس‎ GfK ۰ 0] iow © [k + W rourk GN © Ot] track Of] ‏سب‎ O) weryesori(w,O) ‎swore (kw, 00,6) ‎1 ‎1 

صفحه 41:
OO ‏الگوریتم-0: ادخام‎ ( مها اس رص له ,۰ ۱۵) مت ‎Tverd‏ ‎O‏ بات مت ۱9 (Levee © } ‎i,k‏ طهر ‏0 ط ۱2 2 ۱ ‎} whi (| <= k && | <= w) }PON<Of) ‎۵ [0 ][ ‎pitt 

صفحه 42:
{ }ebe :۵ 1 2 0 ]1 + { yt tk { ۶ )۱<۱( ‎rank G6 [kta]‏ [ ۵ ط [م] ۵ص [] 0) بجوم ‎ober‏ ‎copy © [i] rank © [ko G fk) rank G [kt] { 

صفحه 43:
OO ‏تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم 9-0(ادخام)‎ حمل اصلی: مقایسه(] 0 با . []ن اندازه ورودی::1 و : .تعداد عناصر موجود در هر یک از دو آرایه ورودی. 0۵ )۲, ( 2۷+ > - 0 

صفحه 44:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏با ۰ ۱۳ حمل اصلی: مقایسه ای که درادغام صورت می پذیرد. اندازه ورودی: ‎ «‏ تعداد عناصر آرایه 5. ‎O@) = OF) + O(w) + ۵-0‏ 1 1 1 زمان لازم برای ادغام.- زمان لازم برای مرتب سازی ‏ ۷ . زمان لازم برای مرتب سازی نآ براى 1< 2 كه 8 توانی از 2 است ‎W(n) =2W(n/2) +n-‏ 1 ۷۷ )1( 20 O(a) €8( aks) 

صفحه 45:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏الگوریتم-6: مرتب سازی ادخامی 2(9 ۳6۲9650۲۷ ) (۱ ۲ ,سا بط وچ لبمس 9 اعم سل } B (ew <kick) 3] sod = (law + hich) jwervesort © (low, wid) ‎(cord +0, hicks)‏ © مسي د: ‎were (lew, cord, bik) ‎1 ‎1 

صفحه 46:
‎oO "‏ الگوریتم 6 0:ادهام6 ‏مسئله: ادغام دو آرایه ی مرتب 3) که دربي سب ایجاد شده اند. ‎vord ware (tedex low, terdex wid, tordex highs) } ‏عا ىز ,ا طهر ‏.سحا ] () عجهووا ‎3 baw} | = ‏لمم‎ +0 = le ‎} while (1 <= wid && | <= hick) ‏(] ۵ > [] ۵) زر ‎0 0 < ۵ ][ ‎pete ‎{ 

صفحه 47:
عا ( 0 [- © ati { اجب { P(i> wid) wove © ff] track ۷ ۰0۵ 0 ۵ ‏اه‎ wove © [i] track © ‏۵ص 0 و و‎ 49 cove © [ow] toon © [kick] G [ow] eos G [kek] { 

صفحه 48:
موررش تیم ر حل راهبرد طراحی تقسیم و حل شامل مراحل زیر است: 0- تقسیم نمونه ای ازیک مسئله به یک یا چند نمونه کوچکتر. ©- حل هر نمونه کوچکتر. اگر نمونه های کوچک تر به قدر كوجك ثر به قدر کافی کوچک نبودند» برياى اين منظور از بازكشت استفاده كنيد. 9- در صورت نيازء حل نمونه هاى كوجك تر را تركيب ‎ans‏ نا حل نمونه اولپه به دست آید. 

صفحه 49:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏4۵ مرتب سازی سریع (101010602) * در مرتب سازی سریع» ترتیب آنها از چگونگی افراز آرایه ها داشی می شود. * همه عذاصر کوچک تر آز عنصر محوری در طرف چپ آن وهمه عناصربزرگ ترء» درطرف راست آن واقم هستند. 

صفحه 50:
* مرتب سازی سریع» به طور بازگشتی فراخوانی می شود تا هر یک از دوآرایه را مرتب کند» آن ها نیز افراز می شوند واين روال ادامه می یابد تا به آرایه ای با یک عنصریرسیم. چنبن آرایه ای ذاناً مرنب است. 

صفحه 51:
‎oO "‏ الگوریتم 0-0 :مرتب سازی سربع ‏مسئله: مرتب سازی » کلید با ترنیب غیر نزولی. ‎hich)‏ ۱ : تسا ی بای او } مس بط ‎}P (kek > bw)‏ ‎Pportiza (law , kik , puctpoicd)‏ (6 - سم , سها) تعاس اع , 0 + معصصم) مطاضور ‎x‏ ‏{ 

صفحه 52:
‎oO "‏ الگوریتم-0: افراز آرایه ‏مسئله: افراز آرایه 3) برای مرتب سازی سریع. ‎votd portiiza (terdene low, order ics)‏ ‎(ede & picipoicd‏ } ات مسج مها ‎ipwottecs = G [ow]‏ سا[ ‎Por (1 = bw 4051 <= hich 1 ++)‏ 

صفحه 53:
( سم > [] 6)۵ ( + ‎ot G [i]‏ ] 6۵ سس ‎{ ‏> لواصم ‎flaw] ond © [ puoipor]‏ © ماس { 

صفحه 54:
OO ‏تحلیل پیچیدگی زمانی در حالت معمول برای الگوریتم 9-۳( افراز)‎ . pivotitem ‏اصلی: مقایسه[1] 5 با‎ Jao ‏اندازه ورودی: 0+ ررمب! - ۱ < » نعداد عناصرموجود در زیر آرایه.‎ Ma) 2 ۰-0 

صفحه 55:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏تحلیل پیچیدگی زمانی در بدترین حالت برای الگوریتم ©-©(مرتب سازى سريع) عمل اصلی: مقایسه[1] 5 با مهس در روال ماج . اندازه ورودی: ب ‎٠»‏ تعداد عناصر موجود درآرايه ©. ‎Ma) = TM) + ۵-۵ + ۰-0‏ 1 1 1 زمان لازم برای افراز زمان لازم برای مرتب سازی زمان لازم برای مرتب سازی زیرآرایه طرف راست زیر آرایه طرف چپ 

صفحه 56:
< 00 T (a) 2٩ )6-0( + ۰-0 ‏به ازای‎ TO) 2 0۵ )( 2۰6-0۸6 60 )۶( 

صفحه 57:
OO ‏زمانی در حالت میانگین برای الگوریتم 0-0(مرتب سازی‎ ani ‏سریع)‎ عمل اصلی: مقایسه[[] 5 با مسسس در موم اندازه ورودی: »۰ تعداد عناصر موجود در ). 6 )( €8@ (ak) 

صفحه 58:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس 6الگرریتم ضرب ماتريس استراسن " بيجيدكى اين الكوريتم از لحاظ ضريبء جمع و تفریق بهتر از بيجيدكى درجه سوم اسث. " روش استراسن در موريد ضرب ماترپس های 2.0 اررش جندانى ندارد. 

صفحه 59:
OO ‏الگوریتم 29-6 استراسن‎ مسئله : تعيين حاصلضرب دو ماتریس ‎XN‏ كه در آن « توانی از 2 است. ‎vor starseed (tata‏ 1X a_ work O aX a_ work @ (a* a_ ware &O } B (a <= threshold) joowpule O = ۵ ۷ @ ustay the stradard akortha 

صفحه 60:
عد ( 6 ,009 ,00() هلت ‎tio Pour‏ © رز ‎(aa, (Bae , 60‏ اه و ۵ ون )مه بی 0 * ۵ 2 6۵ مه { { 

صفحه 61:
وا " " .۳ " " " ص" " " " ح" حح" "أ" " " "ح"""" ‎I‏ ‏ل ‎oo ae‏ عمل اصلى: يك ضرب ساده. اندازه ورودى:» » تعداد سطرها و ستون ها در ماتریس. به ازای ) < ۰ که » نوانی از 0است (۸ 2 () * (0) * 60 © 6 )-56.©0( 

صفحه 62:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏تحلیل پیچیدگی زمانی تعدادجمع هاو تفریقهای الگوریتم (استرسن)درحالت معمول عمل اصلى: يك جمع يا تفريق ساده. اندازه ورودى:» » تعداد سطرها و ستون ها در ماتریس. به ازاى 0 < ه كد ه توانی از 6س0) (2)/6 (و) )+ 2 0 (۶ ٩ )0( 6 6( a4 6.60) 

صفحه 63:
OO ‏الگوریتم(-0: ضرب اعداد صحیح بزرگ‎ مسئله: ضرب دو عدد صحیح بزرگ بو با إن ما إن تا ) مس ۱ _ ها } 2 سار تا متا : ۱۳۹ ‎oP digis itv)‏ ورن ‎digis to‏ و ام )موی < و (© || ۶0 عیم) ۸ ‏0 و 

صفحه 64:
‎(a <= terest)‏ ح یه ‎eta UX vobrived tthe wud way ‎}obe ‏۰:6 ك ‏د“ 00 عرد بر ز و5 000 ‎Shade‏ ‏0۰ مور - : 00۰ طجه ن 2 ‎w‏ ‎prod (« w) ۲ ۵ SOe + ( prod (x, 3) + prod‏ مج ‎(w, v )) ¥ AD 4 w+ prod (vy, 2)‏ ; ‎{ ‎{ 

صفحه 65:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏تحلیل پیچیدگی زمانی در بدترین حالت برای | لگوریتم 0-4( ضرب اعداد صحيح) عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در هنگام جمع کردن » تفریق کردن» با انجام اعمالب ۸ 40 ‎chide‏ ‎re WD Ao‏ 000 4 س. هر يك از اين اعمال را ب بار انجام می دهد. اندازه ورودی: 20 ۰ تعداد ارقام هر یک از دو عدد صحیح. ‏به ازاى ع < ۰ که ه توانی از 9است,می + (/۰) ۵ 6 - (۰) 0۵ ‎@(s)=0‏ ‎W(n) € 0(n?) ‎ 

صفحه 66:
الگوریتم 0-0: ضرب اعداد صحیح بزرگ 6 ‎v)‏ تا تا , با مها و مها } ‎jer _tirer x. .W 5257500‏ ص ‎jet,‏ ‎itv)‏ که مرن ال ‎Ja = waxtwure (cucvber oF‏ (0© ددس || © د دنم ص 0 مسب : ‎vee P («<= trestoll)‏ روت ام او ماه زد ند و 

صفحه 67:
( ‏اه‎ ‎۱ ‎۲ ‏عبط‎ 0۰۰ : yp Frew IO Ao ‏مور << : ی 000 علط ن 2 ببح‎ 0 r= prod (x ty, w tz) P= prodd (x,w) = prod? (v,z) preva p XID “Ga + (r—p—yq) * (0 “> ‏و+ د‎ { { 

صفحه 68:
I ‏تحلیل پیچیدگی زمانی در بدترین حالت برای الگوریتم0-00( ضرب اعداد‎ ‏صححه)‎ عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در هنگام جمع کردن » تفریق کردن» با انجام اعمالب ۸ 40 ‎chide‏ ‎re WD Ao‏ 000 4 س. هر يك از اين اعمال را ب بار انجام می دهد. اندازه ورودی: 10 ۰ تعداد ارقام هر یک از دو عدد صحیح. ‏به ازای ی < > که ب توانی از است ‎SOWE)+ oa <=O (x) <= 90 (cp /6 +1) toa‏ © - (و) ۵ ‎W (@) = 6 @ * 1.58)‏ ‎ 

صفحه 69:
فصل سوم: برنامه نويسى بويا 

صفحه 70:
* برنامه نویسی پوپا» از این لحاظ که نمونه به نمونه های کوچکتر تقسیم می شود » مشابه روش تقسیم و حل است ولى در اين روش » نخست نمونه های کوچک تر. را حل مى كنيم » نتايج را ذخيره مى كنيم و بعدا هر كاه به یکی از آن ها نیاز پیدا شد» به جای محاسبه دوباره کافی است آن را بازيابى كليم, 

صفحه 71:
* مراحل بسط یک الگوریتم برنامه نویسی پویا به شرح زیر است: 01- ارائه پک ویژگی بازگشتی بربای حل نمونه ای از مسئله . حل نمونه ای از مسئله به شیوه جزبه به کل با حل نمونه های کوچک نر. 

صفحه 72:
2ة## ‎OO‏ ‏الكوريتم ©-0): ضريب دو جمله ای با استفاده از تفسیم و حل tet bia (tata, tot k) } ®(k==0 || ‏عدم‎ ( }vetura we wetura bra (a — 0 , ‏0ك ) صط+ ( )عا‎ , 1 

صفحه 73:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس الگوریتم ©-9: ضريب دو جمله اى با استفاده از برنامه نويسى بويا ‎(ia, tak)‏ طم ‎} ‏زا ‏[..0]زه..ه] هم ‎١ ++(‏ :م 5: :© < ) مومع ‏(اعد | ۵ حد)م ‎:0 ][ ] 20 ‎ese ‎:0 ][ ][ 2 0 ]۱-۹[ ]۱-4 [+ ۵ ]۱-[ ][ re 

صفحه 74:
‎SSN‏ -9: الگوریتم فلوید برای یافتن کوتاه ترین مسیر ‎vord Roy (tot a ‎s00 vost ‏اه‎ ۵ ‎00 weber O ‎} ‎jtedex t, i,k ‎30 =O Por (REC; KSaj k++) Por (1= 51S a5 i++) Por (§= 05 1S 031 ++) ‎0 ][ 3 - ‏مسبت‎ )۵ [If OL + ORIN) 

صفحه 75:
تحلیل پیچیدگی زمانی در بدترین حالت برای | لگوریتم64 (الگوریتم ظوید برای پافتن کوتاهترین مسیر) حمل اصلی: دسئورهای موجود در حلفه ۳و . اندازه ورودی:» ۰ تعداد رنوس گراف. (2) 6 6 ثم ع ۰ 2۰:۷۰ )۰ 

صفحه 76:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏الگوریتم <-0:الگوریتم فلوید برای بافتن کوتاهترین مسیر 6 ‎(ta‏ ما لس ‎:[[ ‏ای بسه‎ (D ‏0 امه 0[ ‎(DD ‏معط‎ © ‎} ‎۱ ‎۳ )۱2 0: ۱5 ۰::۱۷+( ۳ )۱2 ۹:۱ 05 r+) 

صفحه 77:
P ][ - 0 :0 2 0 Por (k=; k<=ajk ++) ۰۱۱ ۱ :04 ۱<2) و۳ Por (i= 4; i<= 05 i++) ( ۸ )0 ][ [+ 0 ۲٩ 1 > ۵ ][ 1 ( Mak :0 ][ ]1 2 0 ][ 1 + 0 ۲ ][ { { 

صفحه 78:
I ‏الگوریتم 6-چاپ کوتاهترین مسیر‎ مسثله: چاپ رنوس واسطه روی کوتاه ترین مسیر از راسی به راس دیگر در یک گراف موزون. ‎votd pats ( tedex 4 , r)‏ } ‎CHO)‏ عر ‎aks (a, © [al ۳( ‎wou << ‘U" << @ fq] [4 ‎ivak (P [el Hr) ‎{ ‎{ 

صفحه 79:
I ‏برنامه نویسی پویا و مسائل بهینه سازی‎ 0 " حل بهينه » سومین مرحله از بسط یک الگوریتم برنامه نویسی پوپا برای مسائل بهپنه سازی اسث, مراحل بسط چنین الگوربتمی به شرح زیر است: 

صفحه 80:
‎-C‏ ارانه یک ویژگی بازگشتی که حل بهینه ی نمونه ای از مسئله را به دست می دهد. ‏0 محاسبه مقدار حل بهینه به شیوه ی جزء به گل. ‏©- بنا كريدن يك حل نمونه به شیوه ی جزه به کل. 

صفحه 81:
* هر مسئله بهپنه سازی را نمی ثوان با استفاده از برنامه نویسی پویا حل کرد چرا که باید اصل بهینگی در مسئله * اصل بهینگی در یک مسئله صدق می کند اگریک حل بهینه برای نمونه ای از مسئله » همواره حاوی حل بهینه بربای همه ی زیر تمونه ها باشد. 

صفحه 82:
۵ ضرب زنجیره ای ماتریس ها * هدف بسط الگوریتمی است که ترتیب بهینه ریا برای 10 * ثرئیب بهینه فقط به ابعاد مانریس ها بستگی دارید. * علاوه بر ۰۰ این ابعاد تنها ورودی های الگوریتم هستند. * ابن الگوربثم حداقل به صورت نماپی است. 

صفحه 83:
OO ‏الگوریتم 0-0: حداقل ضرب ها‎ tet totaal ) ‏هله‎ ‎vocwt tot d‏ ار ‏© »طم 01 ) ‎} ‏ام ,زرا از 0.0 [0.0] 0 مر ۰۱ 4:۱ ۱2) و۳ 0 2 [] [] 0: 

صفحه 84:
Por (daqoad = () davad = ۰ 4 : ‏مود‎ ++( } Por (4= 05 tS a — depo | 1 +4) ابا + 1د زر 0+ 0۲۰ + (0۲0۳) مس = ]0 + 1۱-۵ ): :0 ][[ < ‏و صامه‎ ۲ + gave he writen { vets Offs] { 

صفحه 85:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس تحلیل پیچیدگی زمانی حالت معمول برای | لگوریتم0- 9( حداقل ضرب ها) عمل اصنلی. می توا دتنتورات اجرا شده برای هر مقذاز :| را عمل اصلع در نظر بگیریم. مقایسه ای را که برای آزمون حداقل انجام می شود به عنوان عمل اصلی در نظر می گیریم. اندازه ورودی: - ۰ تعداد ماتریس ها که باید ضرب شوند. © (a4) 6۰+ 0/6 69 2 

صفحه 86:
الگوریتم 9-2: چاپ ثرئیب بهینه مسئله: چاپ ترتیب بهینه برای ضرب ب ماتریس, ( م۱ :مه( ) لس لاس } ۵ )۱ << ( >> ۲ >> له : } eee [] © حر انحن << “("ر (۱,۳) لسن (1 0+ ط) سر (CC >> vow { 

صفحه 87:
OO ‏و درخت های جست و جوی دودویی بهینه‎ * درخت جست و جوی دودویی یک دودویی از عناصر( که معمولا کلید نامیده می شوند)است که از یک مجموعه مرتب حاصل می شود به قسمی که: هر گره حاوی یک کلید است. 

صفحه 88:
2 کلید های موجود در زیردرخت چپ یک گره مفروض؛ کرچک نر با مساوی کلید آن گره هستند. (0. کلیدهای موجود درزبردرخت راست یک گره مفروض؛ بزررگ تر یا مساوی کلید آن گره هستند. 

صفحه 89:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس الگوریتم 9-0: درخت جست و جوی دودویی ‎tree‏ ان ‎void searck (ade‏ ها مها مغ ۷ _ ‎(woe‏ 

صفحه 90:
®(p-> key == kevin) 3 Poured = true be P ( heya < p - > hey ) ۱۳ ۶ -< ‏جوا‎ ober كوم < - م دمر { 

صفحه 91:
I ‏الگوریتم 0-6 : درخت جست و جری بهیله‎ مسظله: تعبین یک درخت جست وجوی بهینه برای مجموعه ای از کلید ها هر یک با احتمالی مشخص. امن پم , Leow! Pow p Plot & wicray (ODrrdex © } ام را زرط 

صفحه 92:
[..] [) + 0..0] ظ) فطل ۰۱:۱ ۱2:۱ ۳۲ ( 2 [0- ] [] 6 نام > [] [] 0: : ۸ ]0 0 2۱ : ][]۱-4[<- 0 { ;O[u+] [ey] =O ;®[ at] fe] =O 

صفحه 93:
Por (daqoad = Cdrwod > ۰-0: 0+ ( « )۱< ۱ > ۰ - dead | 1 ++) ۱2۱ ‏ام‎ مس ( مب هب[ )سسمی > [[زه۵ مه و هم ۰ ۲ جهن صلس » = ‎REL]‏ ‏{ ‎[fs]‏ © = مص ‎{ 

صفحه 94:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏تحلیل پیچیدگی زمانی حالت معمول برای | لگوریتم درخت جستجوی دودوبی بهیله عمل اصلی: دستورات اجرا شده به ازای هر مقدار از » .این دستورات شامل یک مقایسه برای آزمون حداقل است. اندازه ورودی: :۰ تعداد کلید. ۹ 2۰ )۰4( )(/6 60) ( 

صفحه 95:
OO ‏لگوریتم 600 -0: ساخت درخت جست و جوی دودوبی بهینه‎ كن — عاط" : م ۳ ۳0 : [] [] 6 حمر ®(k==0 ) yretura DOLL ( > 

صفحه 96:
: ۶ 16/۷ ۱ : 0 - < 167 = key [k] :0 - < left = tree (i, k- 1) ;p - > right = tree (k+1, j) return P { { 

صفحه 97:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس الگوریتم10-:الگوریتم برنامه نویسی بويا براى مسئله فروشنده دوره كرد vord tarvel (tat, a » [][ poet amber ۵ :][] (۳, ۶ كا لب 8 وولممیم) } jierdex i, 7,4 jp wrober ([0..a][subset oP O - {1 }] ‏مومع‎ ) ١ © ‏ر‎ ١ ‏ارم ك‎ ++( 

صفحه 98:
ee ; Of] [9] = © fi ]0[ Por (REQ; ‏م : © - م > طم‎ +*( 8 60 0 tterkes) ‏يجا عاصد ) سوط(‎ 1١ !- 0 ‏ها لد‎ 22 »©( :( ]0[ > ‏((ش) - ۵] [] ۵ + [] (] 0۵ ) میت‎ 3@ [i] [©] = vate oP j hat qave the wick 

صفحه 99:
+ 0 ]0[ ]0 - ‏سسسه - [ (م)‎ )۵ ]0( [1 3( ][ [O-{va-v1}] © ]0[ ]9 {v0 }] = ache oP | tet erase he : wim ‏ددم‎ = © [Q] [O - {14} ] { 

صفحه 100:
تحلیل پیچیدگی فضا و زمان در حالت معمول برای ۱ 9-0 ( الگرریتم برنامه نویسی پوبا برای مسئله فروشنده دوره گرد) عمل اصلى: زمان در هر دو حلقه ى اول و آخر » در مقايسه با زمان در حلقه ميانى جشمكير نيستء زيرا حلقه ميانى حاوى سطوح كوناكون تودر تويى اسث . دستورات اجرا شده برای هر مقدار , ,را می توان عمل اصلی در نظر گرفت. اندازه ورودی : ۰ » تعداد رنوس موجود در گراف. (5©-)68© مهمد 0 + 

صفحه 101:
فصل چهارم: روش حریصانه در طراحی الگوریتم 

صفحه 102:
* الگوریتم حریصانه ؛ به ترتیب عناصر را گرفته » هر بار آن عنصری را که طبق ملاکی معبن "بهترین" به نظر مى رسد بدون توجه به انتخاب هاپی که فبلا انجام داده پا در آینده انجام خواهد داد» بر می دارد. 

صفحه 103:
* الگوربتم حربصانه » همانند برنامه لویسی پوپا غالبا برای حل مسائل بهینه سازی به کار می روند» ولی روش حریصانه صراحت بیشتری دارد. * در روش حریصانه » تفسیم به نمونه های کوچک ثر صورت نمی پذیرد. 

صفحه 104:
* الگوریتم حریصانه با انجام یک سری انتخاب» كه هر یک در لحظه ای خاص بهترین به نظر می رسد عمل می کند؛ پعنی اننخاب در جای خود بهبنه است.امید این اسث که پک حل بهینه سرتاسری یافت شود ولی همواره چنین نیست. * برای یک الگوریتم مفروض باید تعیین کرد که آیا حل همواره بهینه اسث پا خبر. 

صفحه 105:
* الگوربنم حربصانه » کار را با بک مجموعه تهی آغاز کرده مجموعه حلی برای نمونه ای از پک مسئله را نشان دهد. هر دور ثکرار » شامل مولفه های زیر است: 

صفحه 106:
01)- روال انتخاب» عنصربعدی را که باید به مجموعه اضافه شوده‌انتخاب می کند.انتخاب طبق یک ملاک حریصانه اسث. ©- بررسى امكان سنجى » تعبين مى كند كه آيا مجموعه جديد برياى رسيدن به حل»عملى است يا خير. ©- بررسى راه حل » تعيين مى كند كه آيا مجموعه جديد » حل نمونه را ارائه مى كند يا خير. 

صفحه 107:
1:|7إظط-|-|-ُظ-ظ_طظطظطظ-طُطلل*““7/ “1 ‎I‏ ‏0-6 درخت های پو شای کمینه * فرض کنید طراح شهری می خواهد چند شهر معین را با جاده به هم وصل کند» به قسمی که مردم بتوانند از هر شهر به شهر ديكر بریوند. اگر محدودیت بودجه ای در کار باشد » ممکن است طراح بخواهد اين کار را با حداقل مقدار جاده کشی انجام دهد. * برای این مسئله دو الكوريثم حربصانه منفاوت : پربم و کروسکال برزسی می شود. 

صفحه 108:
* هر یک از اين الگوریتم ها از یک ویژگی بهینه محلی استفاده می کند, * تضمیلی وجود ندارد که یک الگوریثم حریصانه همواره حل بهینه بدهد» ثابت می شود که الگوریتم های کروسکال و پرپم همواره درخت ‎sla‏ پوشای کمینه را ایجاد می کنند. 

صفحه 109:
0-04 الگوریتم پریم * الگوریتم پریم با زیر مجموعه ای تهی از یال های <) و زبرمجموعه ای از رئوس "۷ آغاز می شود زیرمجموعه حاوی یک راس دلخواه است. به عنوان مقداراولیه ‎{U0}‏ ‏رابه ۷ می دهیم . نزدیک ترین را س به ۰۳ راسی در ۷ - ) است که توسط پالی با وزن کمینه به راسی در ۷۲ متنصل اسث. 

صفحه 110:


صفحه 111:
janwber dstrwe [C..«] : 260 ( ) ۱29 > ۰:۱ : ‏مه‎ ][ < ٩ [] (0] ۵ 2 [] سبط : { ‎win‏ > مر ‏(++ رم ع >( ر © ) عوم ‎( 6) Ss doar [] < wn ) 

صفحه 112:
} wha = ‏بط‎ [i] : ۰ Fi = eke ‏یط رو اوه‎ 1 wear ud ‏ور ] او‎ [ ۰۶ © } dstawe [vara ] < 40 ۳ ) ۱2 9:۱ ۰۱ 

صفحه 113:
( )0۵][ ] ‏مد > [ سس‎ ](( س‎ ][ > ۵ ][ ] ‏سس‎ [ : werest [i] = vaear { { { 

صفحه 114:
تحلیل پیچیدگی زمانی در حالت معمول برای | لگوریتم 6۳-0(الگوریتم پریم) عمل اصلی: در حلقه سپ دو حلقه وجود دارد که هر يك (0 -» ) بار تکرار می شود . اجرای دستورات داخل هر یک از آن ها را می توان به عنوان یک بار اجرای عمل اصل در نظر گرفت. اندازه ورودی: ۰ » تعداد رئوس. 2 )(-9 ۰-0 ۰-06۵ 

صفحه 115:
I ‏قضیه مج‎ ‏الگوریتم پریم همواره یک درخت پوشای کمینه تولید می کند.‎ * ‏البات : برای آن که نشان دهیم مجموعه 1 پس از هر بار‎ ‏تکرارحلقه ]۳0062 امید بخش است ازاستفرا استفاده مى‎ “as مبذای استفرا : واضح است که مجموعه 0 امید بخش است. 

صفحه 116:
الگوریتم -9: الگوریتم کروسکال > لذ ۰۱ ۱۵) ااصا سار ۳۳ _ oP _ odes © ( vet_ oP _eckew & F } زا ۱59۱ ۳۳7 ۳ joke & sort the w eckes in © by wenht ia 

صفحه 117:
اه همطل( :< 0 («) اس : jrelde( curober oP eckes ta @ ‏(0ه معدا عدا دز‎ ‏ولج > ع‎ wik least went wt vet } powsidered 3b, (= tadives oP verives ‏اج روا یی‎ +7 = Peed (i) () لمم دور 

صفحه 118:
} BC ead (7,9) i were (7.9) ورج لله ر 1 { { 

صفحه 119:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏تحلیل پیچیدگی زمانی در بدترین حالت برای | لگوریتم ‎AFIPS‏ کروسکال) عبل اصلی: یک دمخور مقایسه. اندازه ورودى : - ‎٠»‏ تعداد رنوس و7 تعداد يال ها. درباره ابن الكوريتم سه نكته را بايد در نظر داشت: 4 زمان لازم برای مرتب سازی یال ها . 

صفحه 120:
OO . ‏زمان در حلقه طانب‎ 0 ۵ ‏(م)‎ ۶ 6(wkw) ‏زمان لازم برا ی مقدار دهی اولیه به ب مجموعه متمایز,‎ 0 O(w,5)€ Owkw) ‏در نتیجه » بدترین حالت:‎ ( 2ت ) > 8 6( ,ه) ۰(0 8 ) 6 

صفحه 121:
OO ‏قضیه هم‎ * الگوریتم کروسکال همواره یک درخت پوشای کمینه توليد مى كند. بات : اثبات از طریق استقرا با شروع از مجموعه ای تهی از پال ها آغاز می شود, 

صفحه 122:
OO ‏الگرریتم دیکسترا برای کوتاهترین مسیر تک مبدا‎ 9< 5 براى كوتاهترين مسير از هر راس به همه رئوس دیگر در یک گراف موزون و بدون چهت یک الگوریتم(*0)13 از روش حریصانه داریم. که آن دیکسترا نام دارد. 

صفحه 123:
" الگوریتم را با این فرض ارائه می دهیم که از راس مورد نظر په هر یک از رئوس دیگر مسیری وچود دارد. " اپن الگوریتم مشاپه الگوریتم پریم برای مسئله درخت پوشای کمینه است. 

صفحه 124:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏الگوریتم-<4: الگوریتم دیکسترا 

صفحه 125:
: 2 0 ۱ ajitt) : ‏اس‎ ][ - 0 ‎fi] = © [۲‏ ابا ‎{ ‎} repent (0 — Ctcves ) ‏مج 2 هو ‏(+ج+دره > ؛: © ‎ -‏ ) مومع ‏( عم > [] هس ع> 0) ۵ ( ‎leak [i]‏ = ۳ : 

صفحه 126:
۱۰۵ Fi { = edge Prow vertix tedexed by touck [yaar] {to vertex ‏ی را لوط‎ ع ماج للم Por (i= 8 51S Gitt) JP (leas [yocar] + © [ucewr] [i] < eco) teorals [i] = eos [veer] + © [veer] [i] 

صفحه 127:
} touek [i] > ‏عدص‎ ~= سس ابا 

صفحه 128:
قضيه © تنها زمان بندى كه زمان كل درسيستم را كمينه سازى مى كند» زمان بندى است كه در آن كارها بر حسب افزايش زمان ارائه خدمات مرتب می شوند. 

صفحه 129:
‎oO "‏ الگوریتم 4-0 : زمان بندی با مهلت محین ‏مسئله : تعبین زمان بندی با سود کل بيشینه ؛ با این فرض که هر کاری دارای سود است و فقط وقتی قابل حصول است که آن کار در مهلت مقررش انجام شود. ‏هلم ) جامد لاوا , عالطا ب بو [ | , ‎(gequewe _ oP _ #۱ } ‎j index i 

صفحه 130:
: ‏ده وس‎ (C 1 > ]0[ ( ۲ )۱2 6:۱ ۰۱۱۱ (0 = walk i odded ‏وا پل یه‎ worderreusiay qudhues oP ‏مامحل‎ [i] P(( & Pew) ( 2 { { 

صفحه 131:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏تحلیل پیچیدگی زمانی در بدترین حالت برای | لگوریتم زمان بندی با مهلث معين حمل اصلی: باید برای مرتب سازی کارهاء مقایسه هایی انجام پذیرد و هنگامی که 1 با لل (پس از افزوده شدن کار ۱ ام ) مساوی قرار داده می شود.به مقایسه های بیشتری نیاز داریم و هنگامی که امکان پذیر بودن ) چک می شود به مقا پسه های بیشتری نباز است. عمل اصلی مقایسه است. اندازه ورودی : » » تعداد کارها, هو 6 00 

صفحه 132:
I OP dusk الگوریتم 6-6 ( زمان بندی با مهلت معین ) همواره یک مجموعه بهینه تولید می کند. اثبات: ازطریق اسنقرا روی تعداد کارهاء,»صورت می پذیرد. مینای استقرا: اگر یک کار داشته باشیم » قضيه بر قراراست. 

صفحه 133:
قضیه 4ج الگوریتم هافمن یک کد دودویی بهینه تولید می کند. اثبات : ازطریق استفرا صورث می گیرد. با ابن فرض که درخث هاى به دست آمده درمرحله :» انشعاب هایی در درخت دودویی متناظر با کد بهینه اند» نشان می دهیم که درخت های بدست آمده در مرحله (( 6 + ۱ نیز انشعاب هایی در درخت دودویی متناظر با یک کد بهینه اند. 

صفحه 134:
راهبرد عقبگرد 

صفحه 135:
مار تجنیک حبگرد بر ی #دل مسائلی سنداده هی و که در آن ها دنباله ای از اشپاء از پک مجموعه مشخص التخاب مى شود به طوری که اين دنباله » ملا کی را در بر می گیرد. * یک مذال کلاسپک از عفبگرد» مسئله « وزیر است. 

صفحه 136:
* هدف از مسنله م وزیر » چیدن « مهره وزیر در یک صفحه شطرنج است ‏ به طورى كه هيج دو وزيرى یکدیگر را گارد ندهند. يعنى هيج دو مهره اى نبايد در يك سطرء ستون يا قطر يكسان باشند. 

صفحه 137:
* عقبگرد حالت اصلاح شده ی جست و جوی عمقی یک درخث است, 5 الگورینم عقبگرد همانند جست و چوی عمقی است» با ابن تفاوت که فرزندان یک گره فقط هنكامى ملاقات مى شوند كه كره اميد بخش باشدو در أن كره حلى وجود نداشته باشد. 

صفحه 138:
OO Jy wien oly Se Ay Sl GS-0 a vold quecus ( tedex i) } ۳۱ ()عمسم ) ۵ ۵ )۱2< ۰ joo << ool ]0[ kro onl [a] vr ( ۳ )۱<2 ۹: > ۰: ( 

صفحه 139:
wot [140] =i wees (1 + (1) bool prowisicy ( tadex i) : ۲۲ سوه ام 2 ۱ : ‏مرو‎ = ine 

صفحه 140:
} kde (<1 && swack ) B (cal [] == ool] || cb>(ooll] - ‏وب > اس‎ jowitok = Pabse wk { Jretura switch { 

صفحه 141:
6.0 استفاده از الگرریتم مونت کارلو برای برآورد کردن کارایی یک الگوریتم عقبگرد * الگوریتم های مونت کارلو » احثمالی هستند.پعنی دستور اجرایی بعدی گاه به طور تصادفی تعیین می شوند. * در الگوریتم قطعی چنبن چیزی رخ نمی دهد. . همه ی الگوریتم هایی که تا کنون بحث شدند» قطعی هستند. 

صفحه 142:
* الگوریتم مونت کارلو مقدار مورد انتظار یک متغير تصادفی را که روی یک فضای ساده تعریف می ود » با استفاده از مقدار مپانگین آن روی نمونه تصادفی از فضای ساده بر آورد می کند. 

صفحه 143:
* تضمینی وجود ندارد که این برآورد به مقدار مورد انتظار رافعی نزدیک باشده ولی احتمال نزدیک شدن آن» با افزایش زیمان در دسترس برای الگوریتم افزبایش می یاید. 

صفحه 144:
2ة## ‎OO‏ ‏الگوریتم 0-6 : برآورد مونت کارلو ی ۵ () ١ ‏بط‎ حط وم , لسوت ريه أوار ‎ju = root site spwwe ree‏ 0 > سس wed jwpred = 

صفحه 145:
} while («|= O) } t= ‏ام‎ oP chided DP ov ‏و‎ - wered* w invades = cucvardes + wprod *t yw = cuvber oP prowistay ehidred ‏ن خاو‎ 6 ) ‏مب‎ !< 0( ۱ selevied prowisiay ‏یجان له‎ { جمدم دفو { 

صفحه 146:
الكوريتم ©-©: بر أورد مونت كارلو براى الكوريتم 6-4 (الكوريتم عقبگرد برای مستلهب وزیر) ‎querus (Int)‏ وه ان ۳ } ‎vol [(..<]‏ , ز , از ‎jw, wered , anvudes‏ ‎jeet_vP_tedex prow _chidred‏ 0 دنر ‎J wuvoades =1‏ wed 

صفحه 147:
0 ۲۳۳ : (۰ 66۱۱2 0 ۱۶:) طاسب ( ‎werd * wo‏ توت ‎nowdes = anvades + wrod * ‏م‎ ‏وب ‎۰-0 ‏29 مطاه_ مسر ۱ ‎seal] =i ‎} P ( prowasic(')) 

صفحه 148:
OO ‏ح" " " " "ص" "" ص" ص" آ أ" آ"‎ " " " " " " "." "" " ‏تب‎ ‎jprow_ochidred = prow _ chided © {i} { { ( 6) ۱< 0( _i = rendow seleviod Prow prow : ohideed ll 

صفحه 149:
I ‏الگوریتم 0-62: الگوریتم عبگرد برای مسئله حاصل جمع زیر‎ ‏مجموعه ها‎ هعومجم ‏مسئله : تعيين همه ى تركيبات اعداد صحيح موجود در يك‎ 0 ‏عدد صحيح ؛ به طورى كه حاصل جمع أن ها مساوى مقدار معين‎ ‏شود.‎ ‎ord suo _oP _ subsets ( terdex i (et weight , tot total } B (prowsicn(i)) ® (werkt == ) yout << tadkide [(] throudk ‏[ن] طغاض‎ } else 

صفحه 150:
عم - [+ ] ع۳ : ur_vP_subsets (1 +0, weigh + w fi +d] Word —w [i+] { { Ibook prowisiay ( iden i) } || veture (Weight + wot 2 O) &&( werd == O (werkt + w [i+] <O { 

صفحه 151:
I ‏ردك آميزى كراف‎ ©© * مسئله رنگ آمیزی «» عبارت از يافتن همه ى راه ها ى ممکن برای رنگ آمیزی یک گراف بدون جهت ‏ با اسثفاده از حداکثر , رینگ مثفاوت است» به طورى كه هيج دو راس مجاوری هم رنگ نباشند. 

صفحه 152:
الگوریتم6-: الگوریتم عقبگرد برای مسئله رنگ آمیزی 170 votd w_colorice; (trex i ) } 3 tet olor ® ( prowsrn )( Pisa ort << vovler[(l] teounk vevler [3] ube } Por (color = (; color Sw} color ++) 

صفحه 153:
حاص > [0 + ‎١‏ ] جا : (0 +) ومحامدر_ور { { bool prowasicny ) ۱۳۱ ( } : ۲۱ > boot switch ‎true‏ = سه: 

صفحه 154:
1*2 } whe (5 <1 && swick ) ® (© [i] [] && veo [i] == vew'er[i)) } switck = Pabe atti { : ‏بو‎ Swick { 

صفحه 155:
‎oO "‏ الگوریتم 6-0 الگوریتم حقبگرد برای مسئله مدارهای ها میلئونی ‎votd kaclizciaa ( terdex i) ‎7 ‎3 tarde i ‎2 ) ۰ )( ‎۸ )۱ << ۰۱0 ‎yoo << ‏سا [] بسن‎ viedex [ «(l] ‏اج‎ ‎( ۲ ‏ع)‎ 9 iS a5 i++) 

صفحه 156:
۱۵ 2۱ (۱۲۵) ماس { { ‎terdex i )‏ ( مومس اس ‎} ‎3 trex i ‎3 boot wick ۵۱-4 ‏ا88‎ ۵ [rend [ or I] [ verde [O]) ‎} suaick = Pose 

صفحه 157:
job } suck = true 1-0 ‎whe (5) <1 && swick )‏ } ((ن] عطمحب -- [خ] بت تس 2 مرو : ‎+ ‎{ ‎retura switch ‎{ 

صفحه 158:
.0 مسئله کوله پشتی صفر و یک ۰ ای 5 ای از قطعات داریم که هر یک ارای وزن و ارزش معین است ۱ است, * اوز ان و ارده 'وزان 39 ‎JJ!‏ تبد ش ها اعداد مثبتى هسئند. 

صفحه 159:
* دزدی درنظر دارد قطعاتی که می دزدد درون یک کوله پشنی فرار دهد و اگر وزن کل قطعات فرار داده شده در آن کوله پشتی از یک عدد صحبح مثبت() فراثر رود؛ کوله پشتی پاره می شود. 

صفحه 160:
I ‏الگوریتم 0-2:الگوریتم عقبگرد برای مسئله کوله پشتی صفر و‎ ‏يى‎ ات ) سس 0 هت با , ام ‎(et‏ } } BP (werkt S$ O && proPt > wagrol ) } wwanproba = probit jenobest =i jbestset = tachide (() سس ) 6 ( 

صفحه 161:
‎Veo‏ = ]0 +1[ طسب ‎+ ‏موی‎ (1+ 0, proPa + p ] ١+ )[ , wert iw [140] ‎Moke [140] = “oe ‎jkerapsuhk (1 +0, proPi, weidht ) ‎{ ‎{ ‎bool prowisicy ( terden i ) ‎} ‎3 tend j,k 

صفحه 162:
لته ۰ : ۳ P (wert 2 ©( }vetura Pobe } 0-00 امم > لصحط ر ورب ۶ زونه : ای [] ۵ + وس ع مها 

صفحه 163:
tbo = bourd + pli] بر / kei 8) ۰( bowed = bowed + (D — wavercht) * p [klk] 3 vetura bourdd > wax proba { { 

صفحه 164:
60-7 مقاپسه الگوریتم برنامه نویسی پوبا و الگوربتم عقبگرد برای مسئله کوله پشتی صفر و یک * تعداد عناصری که توسط الگورریتم برینامه نویسی پویا برای مسئله کوله پشتی صفر و پک محاسبه می شود دربدترین ‎ok ds O (minimum (2" , nW)) 4 ale‏ * در بدترین حالت » الگوریتم عقبگرد ( 2 ")0 گره را چک مى 5 

صفحه 165:
* الگوربتم عفبگرد معمولا کارابی بیشتری نسبت به الگوریتم برنامه نویسی پویا دارد. * هوروویتز و شانی » روش تقسیم و حل را با روش برنامه نویسی پوپا ترکیب کرده الگورربنمی برای مسئله کوله پشنی صفر و یک بسط داده اند که دربدترین حالت به ‎O(2*n/2)‏ تعلق دارد. 

صفحه 166:
فصل ششم: راهبرد شاخه و حد 

صفحه 167:
* راهبرد شاخه و حد ازآن لحاظ به عفبگرد شبا هت دارد که درآن» بریا حل مسئله از درخت فضای حالت استفاده می شود. " تفاوث ابن روش با عقبكرد؛ اولا ما را به بيمايش خاصى ازدرخت محدود نمى كندوثانيا فقط براى مسائل بهينه سازى به کار می رود. 

صفحه 168:
* الگوریتم شاخه و حد » در هر گره عددی را ( حدی ) رامحاسبه می کند نالعیین شود که آپا ابن گره امید بخش هست يا خیر. * اگر آن حد بهتر از مقدار بهترین حلی که تاکنون یافته شده » نباشد» گره غبر امید بخش است. در غبر ابن صورت ‏ اميد بخش است. 

صفحه 169:
* علاوه براستفاده از حد» می توان حدود گره های امید بخش را مقایسه کرد و فرزندان گرهی با بهترین حد را ملاقات نمود.بدین ترتیب می نوان سریع تر از آن که گره ها را در یک ترئیب از پیش تعبین شده ملاحظه کرد» به حل بهینه دست يافت. 

صفحه 170:
* این روش را بهترین جست و جو با هرس کردن شاخه و حد می گویند. * پیاده سازی این روش شکل اصلاح شده ی ساده ای از یک روش دیگر. موسوم به جست و جوی عرضی هرس كردن شاخه و حد اسث. 

صفحه 171:
10-4 جست و جوی عرضی با هرس کردن شاخه و حد برای مسئله کوله پشتی صفر و یک ه نه ) اس لس , تب ‎iL] poost tot 7 [] » Dowst tit‏ ‎O‏ 1 وج & ‎(tot‏ ‏} ‏0 طم _ نامر ‎ew‏ ‎UU‏ كت (۵) له 

صفحه 172:
( ‏اصجاري‎ < )( 5 v.proP = O : ‏ورین‎ 2 0 : ۳۷0۲ ۶ OD ( , 0) عمج ((0) بچست) طات ( dequeue (Q,u) {level = vlevel + 7 werkt =v. weight + w [ wlevel] ‎proPa = v.proh + p [ ulevel]‏ ند ‎®( uwerht <= O && uprohi > wagrehi) }oaxprohi = ‏مرن‎ ‎ 

صفحه 173:
® ( boucd (u) > waxprol ) : ‏عصم‎ )6, ۰( وت نع زوسن امون > وتوم ينج ‎boucd (u) > waxprofs )‏ ) صر ‎jeoneve (G , u)‏ ‎{ ‎{ ‎Bia bound ( cede u) { 

صفحه 174:
عا لا سنا ۱ 3) Pod resuh ® (uawertt >= O) ۳ عه ( jresut = uprobit ‎level + 0‏ > زر ‎weight‏ = كلووسامار ‎} whde( | <= 3 && waveicht tw [ij] <= ©) 

صفحه 175:
Jowett = tert + w [i] esl = result + p [i] ti { act P(k<ea) result = result +) ( - ‏م * ( تمصي‎ IK] / w [k] wetura rest { { 

صفحه 176:
I ‏الگوریتم 0-6 بهترین جست و جو با هرس کردن شاخه و حد‎ برای مسئله کوله پشتی صفر و یک ‎(toto‏ سم ۳ ‎cowttaty [] , oct tt‏ [ ], ‎O‏ 1 امو & ‎(ct‏ } Iprioviy _ quew_vP _wds PG jeodeu a } ieitalze (PQ) 

صفحه 177:
judevel = O 3 v.prohi ‏پوت : 0 ع‎ = O : ‏موم‎ 2 qu-boued = bowed (v) jesert (PQ , v) } while (! Cxor(PQ)) jrewove (PQ , v) ( P( v.boucd > wach) judevel = vlevel + 7 ewetuht = vwetet + w [ ulevet ] pwn prob = v.proki + p [ ulevel ] 

صفحه 178:
® (uawerdht <= O && uproPi > waxprohit ) ‏نع موی‎ (د) لا < لوا ® (uboudd > waxproht ) iesert (PQ , u) J wwetiht = vawetiht Jn proPa = v.proPt pwuboued = bowed (u) ( لامو < لمحن ) ضر ( نک 0۵) بصع il { { 

صفحه 179:
I ‏مه مسئله فروشنده دوره گرد‎ * هدف از اين مسئله يافتن کوتاهترین مسیر در یک گراف جهت دار با وم ازرپک ریاس ففزوض است ؛ مشروطّ بر آن که هر راس فقط یک با ر ملاقات شود. چنین مسیری را یک تور می گویند. 

صفحه 180:
الگوریتم 0-0: الگوریتم بهترین جستجو با هرس کردن شاخه و حد برای مسئله فروشنده دوره گرد دا ) وا لس حصي اومن [ ] [] , » ordeved-set & option ) ‏میم‎ & wideugh: } jprtoriy _ que _ oP _ wd PO jeodeu,v j atdize (PG ) 

صفحه 181:
judevel = O werk = [dq] juboued = baud (v) ای ع ها : i teert (PQ, v) } while (! Copy (PQ) jrewove( PQ, v ) } P (u.beurd > ‏موی‎ ) pwdlevel = vilevel + 

صفحه 182:
Por (ali suck tha 8 $i sa && tis ‏(كامدصن ها اص‎ } pak = v.pdk jpultattke ead oP ‏ای‎ } PB (ulevel ==u-©8 ) pul tedex oP pdb vertex jput icou.pak ot the ec oP pak put ottke ead oP ‏ات‎ ( و > () ما ) 6 } () ایا سس 

صفحه 183:


صفحه 184:
© هاستنباط فرضيه اى ( تشخيص بیماری ) * یک مسئله 35 ها ۵ مهم د رهوش مصنو سیستم حبر سح = عی و ای خبره؛ تعیین محثمل ثرین توضیح برای برخی پا فثه ها ۱ است, * پرا ‎ye‏ 5 دنم( ‎my‏ ىق » در پزشکی می خواهپم ثرین مجموعه از بیماری ها را که از یک سری علانم قابل نتپجه ‎nee‏ ۱ ال ۵ چ گیری 

صفحه 185:
ها را استنباط از طریق فرضیه می نا میم. * شبکه باور استانداردی برای نشان دادن روابط احتمالی » نظیر روابط میان بیماری و نشا نه ها به شمار, می رود. 

صفحه 186:
الگورینم 0-6 : الگوریتم بهترين جسث و جو با هرس كردن شاخه و حد براى استنباط فرضيه اى ( الككوريتم كوبر) د له یه وا ,60 9) وه وم _۲سیه_موبومو) ‎vet_ vP _sywpows‏ 7 ( set_vP _todoes & best , Rou & phest } 3 priorty_quew_vP_ade PG jwdeu,y judevel = O 

صفحه 187:
:7.0 2 0 : ‏بسا‎ =D ipbest= ‏م‎ )6 ۱6۵ ( ju-bouced = bared (v) ‏لما‎ (PQ ,v) ( ‏طب‎ ) ! Goo (PQ) ۲ (PQ ,v) ‏عام < مدان )م ل‎ ( ‏امطن < اصسططينم‎ + ۱,0 2 

صفحه 188:
‎level ic uO‏ تنج ‎} ®(e (vO |G ) > pest) jbest = uO ‏وعم‎ =p (uO |O) ‎{ ‎beard = bexracKa) ‎P (ubowsd > pbest ) jesert (PQ, u) ‎~O =v.0 ‎peboued = boucd (x) ‏حا < مجان )خم‎ ( 

صفحه 189:
iksert (PG , wv) { { tat bound ( we u ) } B (ulevel ==u) : ۳ 0 be (۵) ۱۰ 20 سم { 

صفحه 190:
فصل هفتم: محاسباتی: مقدمه ای بر پیچیدگی مسئله مرتب سازی 

صفحه 191:
© پیچیدگی محاسباتی * پیچیدگی محاسباتی عبارت از مطالعه تمام الگوهای امکن پذیر برای حل پک مسئله مفروض است. * در تحلیل پیچیدگی محاسباتی کوشش می کنیم تا حد پایینی کارایی همه ی الگوریتم ها را برای یک مسئله مفروض به دست آورپم. 

صفحه 192:
معرفی می گنپم. " اين انتخاب دو دلیل دارد: 0- چند الگوریتم ابداع شده اند که که مسنله را حل می کنند. ‎<Q‏ مسئله مرتب سازی یکی از معدود مسائلی است که در بسط الگوریتم هایی با پیچیدگی زمانی نزدیک به حد پایپنی ‏برای آن موفق بوده ایم. ‎ 

صفحه 193:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏9-2 مرتب سازی درجی و مرثب سازی التخابی * الگوریتم مرتب سازی درجی الگوریتمی اس که مرتب سازی را با درج رکوردها در یک آراپه مرتب شده ی موجود مرتب سازی می کند. 

صفحه 194:
‎oO "‏ الگوریتم 0-: مرتب سازی درجی ‏( [ ]۵ هه ,۰ ۱۵) مسج له } ‏,ام : ‎shee x ‎} Por (1= 8 51 <= asi tt) ‏[] 6 دعم ‎110 

صفحه 195:
( ‏طات‎ ):<0 88 0۵ [i] > x) :۵ ]۱+ [۶ 0 ][ soci { : 6 ]۱+ 12 1 1 

صفحه 196:
OO ‏تحلیل پیچیدگی زمانی تعداد مقایسه های کلید ها درا لگوریتم مرتب سازی درجی‎ ‏در بدترین حالت‎ عمل اصلی : مقایسه [ ] 63 با . اندازه ورودى ‎ :‏ » تعداد کلید هایی که باید مرتب شوند. 0 )0( 2۰۰-6 

صفحه 197:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏تحلیل پیچیدگی زمانی تعداد مقایسه های کلید ها درا لگوریتم مرتب سازی درجی در حالت میانگین x WG [gavin Gilde ‏اندازه ورودی : ۰7 نعداد کلیپد هاپی که باپد مرئب شوند.‎ ©/ت د رو © 

صفحه 198:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس تحليل استفاده از فضاى اضافى براى الكوريتم 7-0 ( مرتب سازى درجى) * تنها فضايى كه با 2 افزایش می يابدء اندازه ی آرایه ورودى 5 اسث. بس ‎ale‏ الكوريثم يك مريتب سازى درجا است و فضای اضافی به(0) 6 تعلق دارد. 

صفحه 199:
جدول 4 ۲۳ : خلاصه تحلیل مرتب سازی تحویضی » درجی و انتخابی استفاده ازفضای اضافی ‎aS tut]‏ | مقایسه كليد | الكوريتم 2 29 (و) ۱۵ 8۶ ع (0) 1 درجا 2/6 29 )6 ۱2 تعویضی ع ر(ه) ۷۷ غم > ‎W{)‏ ‏2 ۱2 درجا درجی A (a) = n?| A @) = n?/ 14 4 T@) =n?) T(@e=3n ‏درجا 2/ انتخار‎ 

صفحه 200:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏الگوریتم 0-0: مرتب سازی انتخابی ( [] ۵ مها , ۱۸۰ ) ‎vord seleviowsert‏ او , ز , ام ( Por (1 =, i <= oc ji t+ ) ((صاس:- ] ۵ > [] ۵ ) ۵ 2۱ اهب : : ‏اه‎ © [i] wad G [swolest ] { { 

صفحه 201:
I PO dpa * هر الگوریتمی که م کلید متمایز را فقط از طریق مقایسه ‎ls als‏ انجام دهد و پس از هر با مقايسه » حد اكثر يك وارونگی را حذف کنید باید در بدترین حالت حداقل 4/ (1 -2 )12 مقایسه روی کلید ها انجام دهد. 

صفحه 202:
ن<ظني5ْئظجعْقَج5حصَّّئقّْقأ ييا سس الگوریتم مرتب سازی تعویضی void exchaagesort (tata, keyype G [] ) } ز ۳۱ : ( 4:۱ ع> 0:۱ <۱) و (] 160 6) ع ۳ [i] ad 6 [i] { 

صفحه 203:
I ‏نگاهی دوباره به مرتب سازیی ادغامی‎ 6-2 * پیچیدگی زمانی تعداد مقایسه های کلید ها در مرتب سازی ادغامی در بدثرین حالت» وقنی که 0 نوانی ال 6 است» به طور کلی به ‎sok Gls O(n Ig n)‏ ‎=alkya—-(a-)‏ (م) 0 

صفحه 204:
* پیچیدگی زمانی تعداد مقایسه های رکورد ها در مرتب سازیی ادغامی در حالت معمول تفریبا به صورث زير است: «وام6 ع (و) ۰ 

صفحه 205:
بهبود بخشیدن به مرتب سازی ادخامی * می توانیم مرتب سازی ادغامی را به سه شیوه بهبود 00 0- نسخه ای ازمرئب سازی ادغامی به روش برنامه نوپسی بويا 2- نسخه پیوندی 0 الگوریتم ادغامی پیچیده تر 

صفحه 206:
I ‏الگوریتم 4: مرتب سازی ادخامی 9 ( نسخه برنامه نويسى بويا)‎ ( [] 2 هروا , ۰ ۱۸) موی لس ۲۷ pied ow , wid , high , size : ۰ 2] < بو : } vepedt (kro twee ) 3 Por (low = 0; law <= w -O * ste + } (ew = bw t+ 8 * sre 

صفحه 207:
: 9 = law + size -01 ‎(bw + 6 * size - 0 5 ((‏ محم > عيوار ( 6 , كلعط , له , سط) وجيجور ‎1 ‎joie 2 6 sie ‎{ ‎{ 

صفحه 208:
OO ‏الگوریتم > : مرتب سازی ادغامی 6 ( نسخه پیوندی)‎ ‎todex8cverqedist)‏ نها )۲ج و } ‎jiedex wid , bst 1, bet O ‎}8 (bw == kak) ‎} wervedist = lw ‎3 © ] ‏یی‎ [۱ = O ‎{ ‎}ebe 

صفحه 209:
©/ + س۲) 21 هو[ iwercesurtP (low , ‏له‎ ,۰۸( (6 ,0۱ + 6 ( ای ,9 با ,)۳ { { word were (larder ‏)سا‎ ero : } 3 todex hastsorted 

صفحه 210:
oO " ۱۵۵ ‏بدنلا س]‎ > © 9 © [ hey 

صفحه 211:
( © د! ها 66 ‎while (ist = O‏ بصا[ دز © > بصا ا دز هم ( 0 با < 4[ مسا ] ۵ : 0طا 2 لس stot 1 = ۵ ] ۷ 0 shes { } ube ‎bet ©‏ = ۱( سا ] ۵ : عدا < سم 

صفحه 212:
۷ 61 با ] ۵ د و سا { A (tet d ==0) 6ط د ۱[ سا ] ۵ : ‎che‏ 0 2 ۲ [ مسا ] ۵ : { 

صفحه 213:
ب د ‎ee‏ — ف " در هر حالت استفاده از فضاى اضافى به(12) © بيوند تعلق دارد. " منظور ال () 9 پیونداین است که نعداد پیوند ها به () 8 تعلق دارد. 

صفحه 214:
I ‏نگاهی دوباره به مرتب سازی سریع‎ 6-2 vord quisksort (terdex low , todo kits ) } امس ۳ : (6) > low ) ‎(lows , kil , pivoipoict )‏ مه ‎ssuicksort (low , kids , pivotpott — 1)‏ ‎iicksort (pvipoil + 1, kicks )‏ ‎“an 

صفحه 215:
I ‏روش های بهبود بخشیدن به الگوریتم مرتب سازی سریع‎ * استفاده از فضای اضافی در مرتب سازی سریع را می توان به پنچ شیره کاهش داد: )- در روال :1116150135]) » تعيين مى كنيم كدام زير آرايه كوجك تراست و همواره آن را در پشته قرار می دهیم و دیگری را نگه می داریم. 

صفحه 216:
* در اين نسخه اسثفاده از, فضای اضافی در بد ثرین حالث ‎(Ig n) 2‏ 0 اندیس تعلق دارد. 2- دسخه ای ار 08۳21101 وجود دارد که تعداد انتساب های رگورد ها را به طرزی چشمگیر کاهش می دهد. 

صفحه 217:
برای این نسخه. پیس اف زمانی تعناد نساب وا یام شده توسط مرتب سازی سریع در حالت میانگین عبارت است از 1 ( 1 + ) 0.69 > رد) دم 

صفحه 218:
9 مقدار زیادی از اعمال 000 و 711512 بی مورد است. می توانیم با نوشتن 01616890۳0 به شيوه تکرار و دستکاری پشته در روال» از عملهات بیهوده پرهیز کنپم؛ بعنی به جای استفاده از پشته و بازگشتی » پشته را خودمان می سازیيم. 

صفحه 219:
<- الگوریتم های بازگشتی مثل مرتب سازیی سریع را می وان با تعیین یک مقدار آستانه که در آن الگوریتم به جای تقسیم بیشتر نمونه » یک الگوریتم تکراری را فراخوانی می کند » بهبود بخشید. 

صفحه 220:
نتخاب ‎S [lo‏ میانه و + ۱10۲۷ ] 5 ۰ [ ۱۲۷ > انتخاب میا ‎es a‏ محوری است. ‎[high]‏ 5 پرای نقطه ی 

صفحه 221:
OO 160 ‏مرتب سازی‎ 6-2 * درخت دودویی کامل یک درخت دودویی است که واجد شرایط زیر باشد: * همه ی گره های داخلی دو فرزند داشنه باشند. * همه ی برگ ها دا رای عمق 0 باشند. 

صفحه 222:
* درخت دودویی اساسا کامل یک درخت دودویی است که: * تا عمق (1 - 0) یک درخت دودویی کامل باشد. * گره هایی با عمق 0 نا حد امکان در. طرف چپ ‎BL‏ شوند. 

صفحه 223:
* 620 یک درخت دودویی اساس کامل است به طوری که * مقادیر نگهداری شده در گره های آن از یک مجموعه مرتب باشند. * مقادیر نگهداری شده درهر گره بزرگ ثر پا مساوی مقادیر نگهداربی شده در فرزندان آن باشد. 

صفحه 224:
6-2 پیاده سازی مرتب سازی 620 ساختمان داده های 60 سا اد } ]4.0[ © مها } int ‏سوم‎ ‎:1 ‎keap& W , tedex i)‏ ( مره لس } 

صفحه 225:
index parent, largerchild; keytype ssiftkey ;bool spotfound ;siftkey = H.S[i] ;parent = i; spotfound = false while (2* parent <= H.hepsize &&! spotfound) if ( 2 * parent < H.heapsize && H.S [ 2*parent] jlargerchild = 2 * parent + 1 else ; largerchild = 2 * parent 

صفحه 226:
} if (siftkey < H.S[largerchild ]) 3H.S [parent] = H.S[largerchild ] ; parent = largerhild { else ;spotfound = true { ;H.S[parent] = siftkey { 

صفحه 227:
مها مها : jkevou < 1۶.۵ ]0[ من با > [9]0).ناكر ‎W.keupsize 0‏ > وس را ‎yoPrdowa (] , 7)‏ ‎jwetura ‏اوكا‎ ‎{ ‎wort rewoveleys (ita tow& WL ‏۵ سمصا]) 

صفحه 228:
} 3 tendon t (-4:۱ ع< رز =§( ‎Por‏ ‏(۷) ۲ > [] 0۵ { word wokeheup (toto ۵ WL } 3 tender i ‏مپسا‎ = a 

صفحه 229:
(-: :0 -<: : [ ع- 4 - ‎١‏ ) سوم (اربک) مه { 

صفحه 230:
الگوریتم -م: مرتب سازی سس ‎٩(‏ 6 , ۰ ۱۵ ) بویا لس } ‎pwokeheup (a, W ) jrewovekeys («, W ,W.G ) ‎{ 

صفحه 231:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏جح مقایسه مرئب سازی ادغامی» مرئب سازی سریم ومرتب سازی !ا * مرتب سازی سریع معمولا بر مرتب سازبی 160 ارجحيث دارد. * مرثب سازی سریع معمولا بر مرئب سازی ادغامی ترجیح داده می شود. 

صفحه 232:
I ‏درخت ها ی تصمیم گیری بربای الگوهای مرئب سازی‎ 064 " لم )0-4: متناظر با هر الگوریتم قطعی برای مرتب سازی > كليد متمايزء یک درخت تصمیم گیری دودویی » معتبر و هرس شده با دفیقا »! بررگ وجود دارد. 

صفحه 233:
" لم ©-20: تعداد مقایسه های انجام شده توسط یک درخت تصمیم گیری در بدترین حالت برابر با عمق درخت است. 

صفحه 234:
" لم 4: اگررم تعداد برگ ها در یک درخث دودوبی و ‎d‏ عمق آن باشد داریم: 7 12 paw 

صفحه 235:
I PO ya * هر الگوریتم قطعی که « کلید متمایزرا فقط با مقایسه ها مرتب سازی می کند؛ باید در بدترین حالت حد اقل * ۳ (اه) ۷ 7 مقایسه کلید ها راانجام دهد. 

صفحه 236:
" لم م به ازاى هر عدد مثب مثبت و صحیح ب» داریم: ه 0.66 هوه 2 (إم) وا 

صفحه 237:
OO PO ‏قضيه‎ * هر الگوریتم قطعی که > کلید متمایز را فقط با مقایسه ی کلید ها انجام می دهد باید در بدترین حالت حداقل ۳ 0 - ۰ با ۰ - مقایسه کلید ها را انجام دهد. 

صفحه 238:
OO ‏حدرد پایینی برای رفتار در حالت میانگین‎ 0-7 * لم ۵ متنا ظر با هر درخت تصمیم گیری دودوبی معتبر هرس شده برای مرثب سازی ب کلید منمایز» یک درخت -0 تصمیم گیری معتبر هرس شده وجود دارد که حد اقل به اندازه درخث اول كارابى دارد. 

صفحه 239:
" لم م4م*: هر الگررینم فطعی که ب کلید منمایز را فقط با مقایسه کلید ها مکی تنل عند حد اقل تعداد محاسبه کلید های که انجام می دهد به طور. میانگین برابر اسث با: 0(۰) ایا 

صفحه 240:
* لم مم؟: هر درخث دردوبی-0 که دارای مج برگ باشد و را۶6)آن برابر (س) ,)9ب باشد» باید همه ی برگ های آن در پایین ترین سطح باشند. 

صفحه 241:
"لم 6م هر درخث -0 که دارای مب برگ رام) آن برابر (م)ا0)بب باشد » باید 0 - ل بركدر سطح ل 0- و 4 ©- 92 برك درسطح ل داشته باد و برك ديكرى نداشته باشد» 4 عمق درخت است. 

صفحه 242:
* لم قح به ازای هر درخت -6 که ‎BOL 9 S407‏ آن برابربا() 000۷ باشد؛ عمق 4 عبارث است از: داع 1۷ 

صفحه 243:
" لم 2-000 به ازاى همه ى مقادير 1) < ج داریم : وا < (0)را0) مب |[ 

صفحه 244:
ل ررْهٌنيققظقِت:ً؟بظي ظرثر”اإًك”ض”ءضظبظً؟ظ»ظ»؛©ثز©”ز”-7 "آا ۳ ‎I‏ ‏قضیه ح» * هر الگوریتم قطعی که 0 کلید متمایزرا تنها با مقایسه کلیدها مرتب سازی کند» به طور مپانگین باید حداقل اين تعداد مقایسه ها را انجام دهد: 1 (066 -وباه 

صفحه 245:
OO ‏مرتب سازی از طریق توزیع (مرتب سازی مبنایی)‎ 9» الگوریتم -۳: مرتب سازی مبنایی ای روط ) معط لو له ب) } 3 tender wee_porier tsi [D..9] } Pow (4 = 05 1 <= cards | 1 ++) 

صفحه 246:
vord distrebute ) ۱۱ ( } : ۲ ۱ م جنر (+ج : 9 ع>: ۵ عر) ۳ 

صفحه 247:
ihet [i] = DOLL 32 = wosterist } while (7 != DOLL) ‎oP ik chat (Prow the richi)ta p => key‏ صلم > زر ‎oP bet [i]‏ لمح صا طم عكار ‎bok‏ حدم دمر ‎{ ‎Quod vodesve 

صفحه 248:
} از ‎DOLL‏ = اس ‎Por (i= © 5 1<=9 5 i*+) ‎thal the des tc bt [17 the cud oF coastertst { 

صفحه 249: