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


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

نوشتهاز سوی werner_heisenberg در سه شنبه 3 شهريور 1394 - 05:22

سلام دوستان عزیز
دنبال یک کتاب جامع درباره پیچیدگی زمانی الگوریتم میگشتم smile015
ممنون میشم جواب بدین smile015
با تشکر فراوان smile072
دنیا عجیب تر از اونی هست که فکر میکنیم و عجیب تر از اونی که می تونیم فکر کنیم (ورنر هایزنبرگ )
نماد کاربر
 
سپـاس : 0

ارسـال : 16


نام: hahah
نام نویسی: 94/5/17

زن

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

نوشتهاز سوی aalireza در سه شنبه 3 شهريور 1394 - 06:42

چیزی که می‌خوایی مثلِ اینه که یه‌نفر دنبالِ کتابی راجع به حد بگرده... یعنی تقریباً هیچ‌جا کتابی پیدا نمی‌کنی که فقط در این زمینه نوشته شده باشه و این موضوع تحتِ یه موضوعِ گسترده‌تر بحث می‌شه.

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

در این سطح، کتابی مثلِ 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 کتابِ جالبیه.
نماد کاربر
 
سپـاس : 502

ارسـال : 781


نام نویسی: 88/5/8

مرد

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

نوشتهاز سوی werner_heisenberg در سه شنبه 3 شهريور 1394 - 12:41

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
دنیا عجیب تر از اونی هست که فکر میکنیم و عجیب تر از اونی که می تونیم فکر کنیم (ورنر هایزنبرگ )
نماد کاربر
 
سپـاس : 0

ارسـال : 16


نام: hahah
نام نویسی: 94/5/17

زن


بازگشت به معرفی کتاب های علمی

چه کسی هم اکنون اینجاست ؟

کاربرانی که در این تالار هستند: بدون کاربران عضو شده و 5 مهمان


cron