صفحه 1 از 1

کتاب جامع درباره پیچیدگی زمانی

ارسال شده: سه‌شنبه ۱۳۹۴/۶/۳ - ۰۶:۲۲
توسط werner_heisenberg
سلام دوستان عزیز
دنبال یک کتاب جامع درباره پیچیدگی زمانی الگوریتم میگشتم smile015
ممنون میشم جواب بدین smile015
با تشکر فراوان smile072

Re: پیچیدگی زمانی

ارسال شده: سه‌شنبه ۱۳۹۴/۶/۳ - ۰۷:۴۲
توسط aalireza
چیزی که می‌خوایی مثلِ اینه که یه‌نفر دنبالِ کتابی راجع به حد بگرده... یعنی تقریباً هیچ‌جا کتابی پیدا نمی‌کنی که فقط در این زمینه نوشته شده باشه و این موضوع تحتِ یه موضوعِ گسترده‌تر بحث می‌شه.

سطوحِ اوّلیه:
فوکوسِ سطوحِ اوّلیه بیشتر رویِ معرفیِ الگوریتم‌هایِ مختلف هست تا آنالیزشون.

در این سطح، کتابی مثلِ Introduction to Algorithms از Cormen می‌تونه خیلی موثر باشه. نکته‌یِ مهمش هم اینه که بیشتر رویِ خودِ‌ الگوریتم‌ها و آنالیزشون فوکوس داره و مثلاً عوضِ این‌که رویِ پایه‌گذاریِ چنین الگوریتم‌هایی تویِ یه‌زبانِ برنامه نویسیِ خاص مثلِ جاوا وقت تلف کنه، رویِ چیزایی مثلِ اثباتشون و استقراء و این مدل چیزا وقت می‌گذاره. تویِ همون فصولِ اوّلیه هم راجع به پیچیدگی و اینا صحبت می‌کنه.

+ اگه می‌خوایی کتابِ بالا رو بخونی، این درس از استنفورد (https://www.coursera.org/course/algo) مطابق با همین کتاب می‌ره جلو منتهی بعضی از چیزا رو جا می‌ندازه. مثلاً کنوث-موریس-پرت رو واسه جست‌و‌جویِ استرینگ‌ها اصلاً بررسی نمی‌کنه (چیزی که تقریباً‌ همه بررسی‌ش می‌کنن).

یخده آسون‌تر از کتابِ بالا، قسمتِ اوّلِ درسیه مثلِ این (https://www.udacity.com/course/intro-to ... hms--cs215) و بعداً این (https://www.udacity.com/course/intro-to ... nce--cs313). اگه این دوتا رو بخونی، بیشترِ سوادت می‌ره واسه الگوریتم‌هایِ گراف ولی یه دیدِ کلی نهایتا به‌دست میاری از نظریه‌یِ پیچیدگی.


سطوحِ متوسطه:
می‌تونی همین پیچیدگی رو رویِ چیزایی مثلِ اتوماتا و امثالهم رو هم بررسی کنی. با وجودی که دیدِ بهتری بهت می‌ده نسبت بالا و تویِ کلاسِ های مختلف می‌ری (عوضِ این‌که فقط رویِ چندجمله‌ای‌ها و لگاریتمی‌ها و لگاریتم‌خطی‌ها و تصاعدی‌ها و ثابت‌ها فوکوس کنی)، ولی تقریباً هیچ‌جا جز علومِ کامپیوترِ نظری و بعضی شاخه‌هایِ کاربردیِ سطحِ بالا (مثلِ کامپایلرها، یادگیریِ ماشین و هوشِ مصنوعی و الخ) کاربرد نداره (اگه از چیزاییِ مثلِ رگولار اکسپرشن‌ها فاکتور بگیری البته! چون اونا عملاً‌ همه جا هستند)
بهترین کتاب در این زمینه هم می‌شه Introduction to Automata Theory, Languages, and Computation از اولمان. همراه با این (https://www.coursera.org/course/automata) می‌تونی بخونیش. من خودم این رو تازه شروع کردم.


سطوحِ عالی:
همون چیزایِ قبل رو به‌صورتِ فرمال بررسی می‌کنی. توش پر از منطق و نظریه‌یِ مجموعه‌ها و این مدل چیزاست. کتابی هم که ملّت معمولاً شروع می‌کنن Introduction to the Theory of Computation از سیپسر هست.



نه‌کاملاً بی‌ربط به موضوعاتِ بالا:
۱- معمولاً باید تکنیک‌هایِ اثبات‌کردنِ پایه‌ای رو تویِ ریاضی‌گسسته بلد باشی تا بتونی بری تو الگوریتم‌ها. Concrete Mathematics از حضرتِ کنوث کتابی‌ست بس خفن.
۲- این‌مدل تکنیک‌ها رو می‌شه فارغ از الگوریتم‌ها تویِ شاخه‌هایِ دیگه‌یِ ریاضی هم استفاده کرد. کتاب Asymptotic Methods in Analysis کتابِ جالبیه.

Re: پیچیدگی زمانی

ارسال شده: سه‌شنبه ۱۳۹۴/۶/۳ - ۱۳:۴۱
توسط werner_heisenberg
aalireza نوشته شده:چیزی که می‌خوایی مثلِ اینه که یه‌نفر دنبالِ کتابی راجع به حد بگرده... یعنی تقریباً هیچ‌جا کتابی پیدا نمی‌کنی که فقط در این زمینه نوشته شده باشه و این موضوع تحتِ یه موضوعِ گسترده‌تر بحث می‌شه.

سطوحِ اوّلیه:
فوکوسِ سطوحِ اوّلیه بیشتر رویِ معرفیِ الگوریتم‌هایِ مختلف هست تا آنالیزشون.

در این سطح، کتابی مثلِ Introduction to Algorithms از Cormen می‌تونه خیلی موثر باشه. نکته‌یِ مهمش هم اینه که بیشتر رویِ خودِ‌ الگوریتم‌ها و آنالیزشون فوکوس داره و مثلاً عوضِ این‌که رویِ پایه‌گذاریِ چنین الگوریتم‌هایی تویِ یه‌زبانِ برنامه نویسیِ خاص مثلِ جاوا وقت تلف کنه، رویِ چیزایی مثلِ اثباتشون و استقراء و این مدل چیزا وقت می‌گذاره. تویِ همون فصولِ اوّلیه هم راجع به پیچیدگی و اینا صحبت می‌کنه.

+ اگه می‌خوایی کتابِ بالا رو بخونی، این درس از استنفورد (https://www.coursera.org/course/algo) مطابق با همین کتاب می‌ره جلو منتهی بعضی از چیزا رو جا می‌ندازه. مثلاً کنوث-موریس-پرت رو واسه جست‌و‌جویِ استرینگ‌ها اصلاً بررسی نمی‌کنه (چیزی که تقریباً‌ همه بررسی‌ش می‌کنن).

یخده آسون‌تر از کتابِ بالا، قسمتِ اوّلِ درسیه مثلِ این (https://www.udacity.com/course/intro-to ... hms--cs215) و بعداً این (https://www.udacity.com/course/intro-to ... nce--cs313). اگه این دوتا رو بخونی، بیشترِ سوادت می‌ره واسه الگوریتم‌هایِ گراف ولی یه دیدِ کلی نهایتا به‌دست میاری از نظریه‌یِ پیچیدگی.


سطوحِ متوسطه:
می‌تونی همین پیچیدگی رو رویِ چیزایی مثلِ اتوماتا و امثالهم رو هم بررسی کنی. با وجودی که دیدِ بهتری بهت می‌ده نسبت بالا و تویِ کلاسِ های مختلف می‌ری (عوضِ این‌که فقط رویِ چندجمله‌ای‌ها و لگاریتمی‌ها و لگاریتم‌خطی‌ها و تصاعدی‌ها و ثابت‌ها فوکوس کنی)، ولی تقریباً هیچ‌جا جز علومِ کامپیوترِ نظری و بعضی شاخه‌هایِ کاربردیِ سطحِ بالا (مثلِ کامپایلرها، یادگیریِ ماشین و هوشِ مصنوعی و الخ) کاربرد نداره (اگه از چیزاییِ مثلِ رگولار اکسپرشن‌ها فاکتور بگیری البته! چون اونا عملاً‌ همه جا هستند)
بهترین کتاب در این زمینه هم می‌شه Introduction to Automata Theory, Languages, and Computation از اولمان. همراه با این (https://www.coursera.org/course/automata) می‌تونی بخونیش. من خودم این رو تازه شروع کردم.


سطوحِ عالی:
همون چیزایِ قبل رو به‌صورتِ فرمال بررسی می‌کنی. توش پر از منطق و نظریه‌یِ مجموعه‌ها و این مدل چیزاست. کتابی هم که ملّت معمولاً شروع می‌کنن Introduction to the Theory of Computation از سیپسر هست.



نه‌کاملاً بی‌ربط به موضوعاتِ بالا:
۱- معمولاً باید تکنیک‌هایِ اثبات‌کردنِ پایه‌ای رو تویِ ریاضی‌گسسته بلد باشی تا بتونی بری تو الگوریتم‌ها. Concrete Mathematics از حضرتِ کنوث کتابی‌ست بس خفن.
۲- این‌مدل تکنیک‌ها رو می‌شه فارغ از الگوریتم‌ها تویِ شاخه‌هایِ دیگه‌یِ ریاضی هم استفاده کرد. کتاب Asymptotic Methods in Analysis کتابِ جالبیه.

smile072 smile072 smile072