اصول طراحی الگوریتمها::کتابهای انتشارات ساحر::کتاب::گروه مهندسی

اصول طراحی الگوریتمها

نام کالا :

کد کالا :

160,000 ريال

قيمت کالا :

144,000 ريال

قيمت با تخفيف :

1 گرم

وزن :

‎۲۱ آذر ۱۳۸۸ ۱۳:۱۲

تاريخ ثبت :

1011

تعداد بازديد :

توضیحات کالا
مشخصات کالا
نظرات

فهرست‌ مطالب
فصل‌ 1	الگوریتمها ، کارائی ، آنالیز و مرتبه
	1-1 الگوریتمها	18
	2-1 اهمیت توسعة الگوریتمهای کارآمد	26
	1-2-1 جستجوی ترتیبی در مقابل جستجوی دودوئی	27
	2-2-1 سری فیبوناچی	30
	3-1 تحلیل الگوریتمها‌	36
	1-3-1 تحلیل پیچیدگی (Complexity Analysis)	36
	پیچیدگی زمانی تمامی – حالات برای الگوریتم 2-1 (مجموع اعضای آرایه)‌	39
	تحلیل پیچیدگی زمانی تمامی – حالات در الگوریتم 4-1 (ضرب ماتریس)‌	39
	تحلیل پیچیدگی زمانی بدترین حالت الگوریتم 1-1 (جستجوی ترتیبی)	40
	تحلیل پیچیدگی زمانی حالت میانگین الگوریتم 1-1 (جستجوی ترتیبی)	41
	اتحلیل پیچیدگی زمانی بهترین – حالت الگوریتم 1-1 (جستجوی ترتیبی)	43
	2-3-1 اعمال تئوری	44
	3-3-1 تحلیل صحت الگوریتم (Correctness)	46
	1-4-1 مقدمه‌ای کلی در مورد مرتبه (Order)	47
	2-4-1 مقدمه‌ای دقیق در مورد مرتبه	50
	3-4-1 بکارگیری یک حد برای تعیین مرتبه	62
	5-1 رئوس مطالب این کتاب	64
	تمرینات	65
فصل‌ 2	تقسیم - و - حل
	1-2 جستجوی دودویی (Binary Search)	72
	تحلیل پیچیدگی زمانی برترین حالت الگوریتم 1-2	76
	2-2 مرتب‌سازی ادغامی (MergeSort)	77
	تحلیل پیچیدگی زمانی برترین حالت الگوریتم 3-2 (ادغام)	81
	تحلیل پیچیدگی زمانی برترین حالت الگوریتم 2-2 (مرتب‌سازی ادغامی)	81
	3-2 روش تقسیم – و –حل	84
	4-2 مرتب‌سازی سریع یا QuickSort‌ (مرتب‌سازی معاوضه‌ای تفکیکی)	85
	تحلیل پیچیدگی زمان تمامی حالات الگوریتم 7-2 (Partition)	88
	تحلیل پیچیدگی زمانی برترین حالت الگوریتم 6-2 (QuickSort)	89
	تحلیل پیچیدگی زمان حالت میانگین الگوریتم 6-2 (QuickSort)	91
	5-2 الگوریتم ضرب ماتریس استراسن (Stressen)	93
	تحلیل پیچیدگی زمانی تمامی حالات الگوریتم 8-2 از نظر تحلیل تعداد ضربها (استراسن)	96
	تحلیل پیچیدگی زمانی تمامی حالات الگوریتم 8-2 از نظر تحلیل تعداد جمعها / تفریقها (استراسن)	97
	6-2 عملیات ریاضی بر روی اعداد بزرگ	99
	1-6-2 نمایش اعداد صحیح بزرگ: عملیات جمع و سایر عملیات با زمان خطی	99
	2-6-2 ضرب اعداد بزرگ	100
	تحلیل پیچیدگی زمانی برترین حالت الگوریتم 9-2 (ضرب عدد صحیح بزرگ)	102
	تحلیل پیچیدگی زمانی برترین حالت الگوریتم 10-2 (نگارش دوم ضرب اعداد بزرگ)	104
	7-2 تعیین آستانه‌ها (Thresholds)	106
	8-2 چه زمانی نباید از تکنیک تقسیم – و – حل استفاده کرد	111
	تمرینات	112
فصل‌ 3	برنامه سازی پویا(Dynamic Programming)
	مرور کلی	121
	1-3 ضریب دو جمله‌ای (Binomial Coefficient)	122
	2-3 الگوریتم فلوید برای یافتن کوچکترین مسیرها	127
	تحلیل پیچیدگی زمانی تمامی حالات الگوریتم 3-3 (الگوریتم فلوید برای کوتاهترین مسیرها)	134
	3-3 برنامه‌سازی پویا و مسائل بهینه سازی	137
	4-3 ضرب زنجیره‌ای ماتریس (Chained Matrix Multiplication)	139
	تحلیل پیچیدگی زمانی تمامی حالات الگوریتم 6-3 (حداقل ضربها)	146
	5-3 درختهای جستجوی دودویی بهینه	148
	تحلیل پیچیدگی زمانی تمامی حالات الگوریتم 9-3 (درخت جستجوی دودویی بهینه)	157
	6-3 مسئله فروشندة دوره‌گرد (Traveling Salesperson)	160
	تحلیل پیچیدگی فضایی و زمانی تمامی حالات الگوریتم 11-3 (الگوریتم برنامه‌سازی پویا برای مسئلة فروشنده دوره‌گرد)	166
	تمرینات	168
فصل‌ 4	روش حریصانه (Greedy approach)
	مرور کلی	173
	1-4 درختهای پوشای مینیمم (Minimum Spanning Trees)	177
	1-1-4 الگوریتم پرایم	181
	تحلیل پیچیدگی زمانی تمامی حالات الگوریتم 1-4 (الگوریتم پرایم)	185
	2-1-4 الگوریتم کراسکال	187
	تحلیل پیچیدگی زمانی بدترین حالت الگوریتم 2-4 (الگوریتم کراسکال)	190
	3-1-4 مقایسه الگوریتم پرایم با الگوریتم کراسکال	192
	4-1-4 بحث آخر	193
	2-4 الگوریتم دایجسترا (Dijkstra) برای کوتاهترین مسیرها از مبدأ واحد	193
	3-4 زمانبندی (Scheduling)	197
	1-3-4 به حداقل رساندن کل زمان داخل سیستم بودن	198
	2-3-4 زمانبندی براساس سررسیدها	201
	تحلیل پیچیدگی زمانی بدترین حالت الگوریتم 4-4 ( زمانبندی براساس سررسیدها)	206
	4-4 کُد هافمن (Huffman Code)	209
	1-4-4 کُدهای پیشوندی (Prefix Codes)	210
	2-4-4 الگوریتم هافمن	212
	5-4 روش حریصانه در برابر روش برنامه‌سازی پویا: مسئله کوله پشتی	216
	1-5-4 روش حریصانه برای مسئله کوله پشتی صفر – یک	217
	2-5-4 یک روش حریصانه برای مسئله کوله پشتی کسری	219
	3-5-4 یک روش برنامه‌سازی پویا برای مسئله کوله پشتی صفر – یک	220
	4-5-4 یک اصلاحیه بر روی الگوریتم برنامه‌سازی پویای مسئله کوله پشتی صفر – یک	221
	تمرینات	224
فصل‌ 5	Backtracking
	1-5 تکنیک Backtracking	232
	2-5 مسئله –n وزیر	241
	3-5 بکارگیری الگوریتم مونت کارلو برای تخمین کارایی یک الگوریتم backtracking	246
	4-5 مسئله مجموع زیرمجموعه‌ها (sum-of-subsets)	251
	5-5 رنگ‌آمیزی گراف (Graph Coloring)	257
	6-5 مسئله دورهای هامیلتونی (Hamiltonian circuits)	261
	7-5 مسئله کوله پشتی صفر – یک	266
	1-7-5 یک الگوریتم Backtracking برای مسئله کوله پشتی صفر – یک	266
	2-7-5 مقایسه الگوریتم برنامه‌سازی پویا و الگوریتم Backtracking برای مسئله کوله پشتی صفر – یک	277
	تمرینات	277
فصل‌ 6	انشعاب و کران (Branch-and-Bound)
	مرور کلی	283
	1-6 نمایش انشعاب و کران بر روی مسئله کوله پشتی صفر – یک	286
	1-1-6 جستجوی اول سطح با هرس انشعاب و کران	286
	2-1-6 جستجوی Best-first با هرس انشعاب و کران	292
	2-6 مسئله فروشنده دوره‌گرد	298
	استنتاج قیاسی [Abductive Inference] (تشخیصی)	309
	تمرینات	319
فصل‌ 7	‌مقدمه‌ای بر پیچیدگی – مسئله مرتب‌سازی
	1-7 پیچیدگی محاسباتی (Computational Complexity)	324
	2-7 مرتب‌سازی درجی و مرتب‌سازی انتخابی	326
	تحلیل پیچیدگی زمانی بدترین حالت الگوریتم 1-7 برحسب تعداد مقایسات کلیدها (مرتب‌سازی درجی)	328
	تحلیل پیچیدگی زمانی حالت میانگین الگوریتم 1-7 برای تحلیل تعداد مقایسات کلیدها (مرتب‌سازی درجی)	328
	تحلیل بکارگیری فضای اضافی در الگوریتم 1-7 (مرتب‌سازی درجی)	330
	3-7 کرانهای پائین الگوریتمهایی که حداکثر یک وارونگی در هر مقایسه را حذف می‌کنند	333
	4-7 بازنگری Mergesort (مرتب‌سازی ادغامی)	336
	تحلیل میزان مصرف فضای اضافی الگوریتم 2-7(Mergesort 2)	337
	بهبودی Mergesort	338
	تحلیل مصرف فضای اضافی الگوریتم 4-7 (Mergesort 4)	342
	5-7 بازنگری Quicksort	343
	بهبودها بر روی الگوریتم پایه‌ای Quicksort	344
	تحلیل میزان فضای خالی اضافی بکار رفته (Quicksort بهبود یافته)	344
	6-7 Heapsort (مرتب‌سازی هرمی)	345
	1-6-7 هرمها و روتین‌های پایه‌ای هرمها	345
	تحلیل پیچیدگی زمانی بدترین حالت تعداد مقایسات کلیدهای الگوریتم 5-7 (Heapsort)	353
	تحلیل makeheap	353
	تحلیل removekeyها	355
	ترکیب دو تحلیل	357
	تحلیل میزان فضای اضافی الگوریتم 5-7 (Heapsort)	358
	7-7 مقایسه Mergesort ، Quicksort و Heapsort	358
	8-7 کرانهای پائین مربوط به مرتب‌سازی فقط با مقایسه کلیدها	359
	1-8-7 درختهای تصمیم‌گیری مربوط به الگوریتمهای مرتب‌سازی	359
	2-8-7 کرانهای پائین مربوط به بدترین حالت	363
	کرانهای پائین برای رفتار حالت میانگین	366
	9-7 مرتب‌سازی بوسیلة توزیع (مرتب‌سازی مبنایی [radix sort])	371
	تحلیل پیچیدگی زمانی تمامی حالات الگوریتم 6-7 (مرتب‌سازی مبنایی)	375
	تحلیل مصرف فضای اضافی الگوریتم 6-7 (مرتب‌سازی مبنایی)	376
	تمرینات	376
فصل‌ 8	‌پیچیدگی محاسباتی بیشتر – مسئله جستجو
	مرور کلی	385
	1-8 کرانهای پائین مربوط به جستجوی فقط با مقایسات کلیدها	386
	1-1-8 کرانهای پائین مربوط به رفتار بدترین حالت	389
	2-1-8 کرانهای پائین مربوط به رفتار حالت میانگین	391
	تحلیل پیچیدگی زمانی حالت میانگین الگوریتم 1-2 (جستجوی دودویی، بازگشتی)	393
	2-8 جستجوی درون‌یابی (Interpolation Search)	398
	3-8 جستجو در درختها	402
	1-3-8 درختهای جستجوی دودویی	403
	2-3-8 B-Treeها	408
	4-8 درهم سازی (Hashing)	411
	5-8 مسئله انتخاب: مقدمه‌ای بر استدلالهای مغرضانه (adversary arguments)	416
	1-5-8 یافتن بزرگترین کلید	416
	2-5-8 یافتن هر دوی کوچکترین و بزرگترین کلیدها	418
	3-5-8 یافتن دومین بزرگترین کلید	427
	4-5-8 یافتن kامین کوچکترین کلید	431
	تحلیل پیچیدگی زمانی حالت میانگین الگوریتم 5-8 (انتخاب)	435
	تحلیل پیچیدگی زمانی بدترین حالت الگوریتم 6-8 (انتخاب با استفاده از میانه)	440
	5-5-8 یک الگوریتم احتمالی برای مسئله Selection	444
	تحلیل پیچیدگی زمانی مقدار مورد انتظار الگوریتم 7-8 (انتخاب احتمالی)	447
	تمرینات	449
فصل‌ 9	پیچیدگی و بغرنجی محاسبه-‌ مقدمه‌ای بر نظریه NP
	1-9 بغرنجی یا سختی (Intractablility)	456
	2-9 بازنگری اندازة‌ ورودی	458
	3-9 سه دسته‌بندی کلی مسائل	463
	1-3-9 مسائلی که برای آنها می‌توان الگوریتمهایی با زمان چند جمله‌ای پیدا کرد	463
	2-3-9 مسائلی که بغرنج بودن آنها اثبات شده است	463
	3-3-9 مسائلی که بعنوان بغرنج اثبات شده‌اند اما برای آنها الگوریتمهایی با زمان چند جمله‌ای هنوز پیدا نشده است	465
	-9 نظریه NP	465
	1-4-9 مجموعه‌های P و NP	468
	2-4-9 مسائل NP-complete	474
	وضعیت NP	483
	مسائل مکمل	485
	3-4-9 مسائل NP-Hard ، NP-Easy و NP-Equivalent	487
	مسئله تصمیم‌گیری بسط یافتة فروشندة دوره‌گرد	490
	5-9 مدیریت مسائل NP-Hard	492
	1-5-9 یک الگوریتم تقریبی برای مسئله فروشندة دوره‌گرد	493
	2-5-9 یک الگوریتم تقریبی برای مسئله Bin-Packing	498
	تمرینات	504
فصل‌ 10	الگوریتمهای نظریه اعداد (Number-theoretic)
	1-10 مرور نظریه اعداد	508
	1-1-10 اعداد مرکب و اول	508
	2-1-10 بزرگترین مقسوم‌علیه مشترک	509
	3-1-10 تبدیل به عوامل اول	513
	4-1-10 کوچکترین مضرب مشترک (Least Common Multiple (LCM))	515
	2-10 محاسبة بزرگترین مقسوم‌علیه مشترک	516
	1-2-10 الگوریتم اقلیدُسی	517
	تحلیل پیچیدگی زمانی بدترین حالت الگوریتم 1-10 (الگوریتم اقلیدُسی)	519
	2-2-10 مکملی بر الگوریتم اقلیدُسی	521
	3-10 مروری بر ریاضیات پیمانه‌ای (modular Arithmetic)	524
	1-3-10 تئوری گروهها (Group theory)	524
	2-3-10 هم‌ارز به پیمانة (Congruency Modulon)n	526
	3-3-10 زیر گروه‌ها (Subgroups)	533
	4-10 حل معادلات خطی پیمانه‌ای	539
	5-10 محاسبة توانهای پیمانه‌ای	546
	6-10 یافتن اعداد اول بزرگ	549
	1-6-10 جستجو بدنبال یک عدد اول بزرگ	549
	2-6-10 بررسی اینکه آیا یک عدد اول است یا خیر	550
	الگوریتم با زمان چند جمله‌ای	551
	صحت الگوریتم	558
	پیچیدگی زمانی الگوریتم	564
	تحلیل پیچیدگی زمانی بدترین حالت الگوریتم 5-10 (تعیین عدد اول بصورت چند جمله‌ای)	567
	نتایج حاصل از اثبات لِم 7-10	569
	7-10 سیستم رمزنگاری کلید عمومی RSA	571
	1-7-10 سیستمهای رمزگذاری کلید عمومی	571
	2-7-10 سیستم رمزنگاری RSA	573
	سیستم	573
	نتیجه نهایی	575
	تمرینات	576
فصل‌ 11	مقدمه‌ای بر الگوریتمهای موازی
	مرور کلی	581
	1-11 معماریهای موازی	585
	1-1-11 مکانیزم کنترلی	585
	2-1-11 سازمان فضای آدرس	586
	معماری فضای آدرس اشتراکی (Shared-Address-Space Arichitecture)	587
	معماری ارسال پیغام (Message-Passing Architecture)	588

	3-11 شبکه‌های اتصال داخلی (interconnection Networks)	589
	شبکه‌های اتصال داخلی پویا (Dynamic interconnection Networks)	591
	2-11 مدل PRAM	593
	1-2-11 طراحی الگوریتمهایی برای مدل CREW PRAm	59
	یافتن بزرگترین کلید در داخل یک آرایه	597
	کاربرد برنامه‌نویسی پویا	601
	تحلیل پیچیدگی زمانی بدترین حالت الگوریتم 3-11	605
	2-2-11 طراحی الگوریتمهایی برای مدل CRCW PRAM	606
	تمرینات	609
فصل‌ 12	مروری بر عملیات ریاضی
	1-A علائم	613
	2-A توابع	616
	3-A استقراء ریاضی (Mathematical Induction)	617
	4-A تئوریها و لِم‌ها	624
	5-A لگاریتمها (logarithms)	625
	1-5-A تعریف و خاصیتهای لگاریتمها	626
	برخی از ویژگیها (در تمامی موارد، a>1 ، b>1 ، x>0 و y>0 می‌باشد)	627
	2-5-A لگاریتم طبیعی (Natural logarithm)	628
	6-A مجموعه‌ها	630
	7-A جایگشتها و ترکیبها	632
	8-A احتمالات	635
	1-8-A تصادفی بودن (Randomness)	642
	2-8-A امید ریاضی (Expected Value)	647
	تمرینات	649
فصل‌ 13	حل معادلات بازگشتی و کاربرد آنها در تحلیل الگوریتمهای بازگشتی
	1-B حل بازگشتها با استفاده از استقراء	655
	2-B حل دنباله‌های بازگشتی با استفاده از معادلة مشخصه	660
	1-2-B دنباله‌های بازگشتی خطی همگن (Homogeneous Linear Recurrences)	660
	2-2-B دنباله‌های بازگشتی خطی ناهمگن	669
	3-2-B تغییر متغیرها (تبدیلات دامنه)	675
	3-B حل دنباله‌های بازگشتی بوسیلة جایگزینی	678
	4-B بسط نتایج برای n‌ ، بعنوان توانی از یک ثابت مثبت b ، تا n بطور کلی	680
	5-B اثبات تئوریها	688
	تمرینات	690
فصل‌ 14	ساختمان داده‌های مجموعه‌های گسسته(Disjoint Sets)
	ساختمان دادة مجموعة گسسته	702
	ساختمان دادة مجموعة گسستة II	705
	ساختمان دادة مجموعة گسستة III	707
پایان

مترجم :

مهرداد توانا - سعيد هراتيان

تعداد صفحات :

708

نوبت چاپ :

اول

سال چاپ :

1388

مولف :

Richard E.Nwapolitan

شابک :

978-964-2972-21-0

گروه مهندسی - پژوهشی ساحر