سلام دوستان عزیز
دنبال یک کتاب جامع درباره پیچیدگی زمانی الگوریتم میگشتم
ممنون میشم جواب بدین
با تشکر فراوان
کتاب جامع درباره پیچیدگی زمانی
- werner_heisenberg
نام: hahah
عضویت : شنبه ۱۳۹۴/۵/۱۷ - ۲۲:۴۳
پست: 16-
- جنسیت:
کتاب جامع درباره پیچیدگی زمانی
دنیا عجیب تر از اونی هست که فکر میکنیم و عجیب تر از اونی که می تونیم فکر کنیم (ورنر هایزنبرگ )
Re: پیچیدگی زمانی
چیزی که میخوایی مثلِ اینه که یهنفر دنبالِ کتابی راجع به حد بگرده... یعنی تقریباً هیچجا کتابی پیدا نمیکنی که فقط در این زمینه نوشته شده باشه و این موضوع تحتِ یه موضوعِ گستردهتر بحث میشه.
سطوحِ اوّلیه:
فوکوسِ سطوحِ اوّلیه بیشتر رویِ معرفیِ الگوریتمهایِ مختلف هست تا آنالیزشون.
در این سطح، کتابی مثلِ 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 کتابِ جالبیه.
سطوحِ اوّلیه:
فوکوسِ سطوحِ اوّلیه بیشتر رویِ معرفیِ الگوریتمهایِ مختلف هست تا آنالیزشون.
در این سطح، کتابی مثلِ 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 کتابِ جالبیه.
- werner_heisenberg
نام: hahah
عضویت : شنبه ۱۳۹۴/۵/۱۷ - ۲۲:۴۳
پست: 16-
- جنسیت:
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 کتابِ جالبیه.
دنیا عجیب تر از اونی هست که فکر میکنیم و عجیب تر از اونی که می تونیم فکر کنیم (ورنر هایزنبرگ )