اتاق ریاضیات(طرح سؤالات)

[k1kz]

سلام به همگی من یه سوال دارم اگه کسی می تونه لطفا راهنمایی کنه:
چطوری میشه یه الگوریتمی طراحی کنیم که توابع دلخواه ما را برای مقادیر بزرگ تقریب کنه و الگوریتم در مرتبه زمانی لگاریتمی باشه؟ Logspace
یعنی فرض کنید میخواهیم تابع ((f(n)=Log(Bessel I0(n را برای مقادیر ...,n= 2^2 ,2^4 ,2^8 ,2^16
برآورد کنیم و زمان حل مساله را هم اندازه میگیریم این زمان برای nهای داده شده باید تناسب هندسی داشته باشه یعنی زمان حل مساله در هر n نسبت به n قبلی در یک عدد ثابت ضرب شده باشه.من اینکار رو برای هر تابعی که خواستم با برنامه Mathematica انجام دادم ولی نمیدونم چطوری برنامه اینکارو میکنه؟ جالب اینجاست که روشهای مرسوم تقریب توابع مثل سریهای تیلور و فوریه و چبیشف و کسرهای پده (pade) و کسرهای متوالی هیچکدوم در زمان لگاریتمی نمیتونن تقریب کنن من امتحان کردم.
اگه کسی چنین الگوریتمی سراغ داره لطفا بگه یا لینک کنه
ممنون
کیوان

[k1kz]

سلام کسی کتاب یا مقاله خوب برای حل معادلات بازگشتی غیر خطی سراغ داره؟
مثلا اینو چطوری دقیق حل کنیم؟ a(n+1)=(a(n)^2+1),a0=0

[saber57]

چطوری میشه یه الگوریتمی طراحی کنیم که توابع دلخواه ما را برای مقادیر بزرگ تقریب کنه و الگوریتم در مرتبه زمانی لگاریتمی باشه؟ logspace
کیوان

اگه ممکنه بیشتر توضیح بدید

[k1kz]

اگه ممکنه بیشتر توضیح بدید

یک مقاله خیلی کلی و ساده در این رابطه اینجاست ببینید:
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

[k1kz]

با سلام

دوستان به لینک زیر سری بزنید و نرم افزار geometer's sketchpad را که مخصوص تولید تصاویر متحرک ریاضی است، دانلود کنید. از این نرم افزار می توان برای آموزش مفاهیم ریاضی در سطوح مختلف استفاده کرد.

[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

دانلود نرم افزار با حجم2.17 مگابایت:

[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

ممنون هستم جالب بود.

[k1kz]

اگه ممکنه بیشتر توضیح بدید

نظریه‌ی پیچیدگی محاسباتی شاخه‌ای از علوم کامپیوتر و ریاضی است که به بررسی دشواری حل مسائل به وسیله‌ی رایانه (به عبارت دقیق‌تر به‌ صورت الگوریتمی) می‌پردازد. این نظری بخشی از نظریه‌ی محاسباتی است که با منابع مورد نیاز برای حل یک مساله سروکار دارد. عمومی‌ترین منابع زمان (چقدر زمان برای حل کردن مساله لازم است) و فضا (چقدر حافظه مورد نیاز است) می‌باشند. سایر منابع می‌تواند تعداد پروسسور‌های موازی (در حالت پردازش موازی) و … باشند. اما در این مقاله ما در مورد عواملی مثل عوامل بالا بحثی نکرده‌ایم. باید به این نکته توجه داشت که نظریه پیچیدگی با نظریه قابل حل بودن متفاوت می‌باشد. این نظریه در مورد قابل حل بودن یک مساله بدون توجه به منابع مورد نیاز آن، بحث می‌کند. بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل می‌باشند و کدام مسائل غیرقابل حل، این سوال به نظر طبیعی می‌رسد که درجه سختی مساله چقدر است. نظریه پیچیدگی محاسبات در این زمینه می‌باشد.
برای یک توضیح مختصر در این باره میتونید به سایت آکادمیست مراجعه کنید.

به نقل از سایت آکادمیست دات آی آر

[saber57]

نظریه‌ی پیچیدگی محاسباتی شاخه‌ای از علوم کامپیوتر و ریاضی است که به بررسی دشواری حل مسائل به وسیله‌ی رایانه (به عبارت دقیق‌تر به‌ صورت الگوریتمی) می‌پردازد. این نظری بخشی از نظریه‌ی محاسباتی است که با منابع مورد نیاز برای حل یک مساله سروکار دارد. عمومی‌ترین منابع زمان (چقدر زمان برای حل کردن مساله لازم است) و فضا (چقدر حافظه مورد نیاز است) می‌باشند. سایر منابع می‌تواند تعداد پروسسور‌های موازی (در حالت پردازش موازی) و … باشند. اما در این مقاله ما در مورد عواملی مثل عوامل بالا بحثی نکرده‌ایم. باید به این نکته توجه داشت که نظریه پیچیدگی با نظریه قابل حل بودن متفاوت می‌باشد. این نظریه در مورد قابل حل بودن یک مساله بدون توجه به منابع مورد نیاز آن، بحث می‌کند. بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل می‌باشند و کدام مسائل غیرقابل حل، این سوال به نظر طبیعی می‌رسد که درجه سختی مساله چقدر است. نظریه پیچیدگی محاسبات در این زمینه می‌باشد.
برای یک توضیح مختصر در این باره میتونید به سایت آکادمیست مراجعه کنید.

به نقل از سایت آکادمیست دات آی آر

مساله شما در زمینه مهندسی کامپیوتر نرم افزار هست . فکر کنم دتبال پیدا کردن الگوریتمی برای حل مساله پیچیدگی میگردید. شاید این کتاب مفید باشه :

C++طراحي الگوريتم ها با شبه كدهاي

ريچارد نيپوليتان , كيومرث نعيمي پور
نویسندگان
عين الله جعفرنژاد قمي
مترجمین

لینک :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[k1kz]

مساله شما در زمینه مهندسی کامپیوتر نرم افزار هست . فکر کنم دتبال پیدا کردن الگوریتمی برای حل مساله پیچیدگی میگردید. شاید این کتاب مفید باشه :

C++طراحي الگوريتم ها با شبه كدهاي

ريچارد نيپوليتان , كيومرث نعيمي پور

نویسندگان

عين الله جعفرنژاد قمي
مترجمین

لینک :

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

نظریه پیچیدگی قصد دارد اثبات کند که کلا کلاس P=NP است یعنی هر الگوریتم غیر قطعی در زمان چند جمله ای را میتوان به صورت الگوریتم قطعی در زمان چند جمله ای نوشت .مثلا در سال 2002 الگوریتم AKS برای اولین بار نشان داد که پیدا کردن برای اعداد اول این مطلب درست است و اعداد اول در کلاس پیچیدگی P قرار دارند. اما سوال من در باره تقریب توابع بدیهی است که در کلاس P است یعنی در زمان چند جمله ای و قطعی از روش سریهای تیلور حل میشود.ولی من دنبال الگوریتمی در کلاس Log Space هستم نه P اینکه P=NP باشد یا نباشد این مشکل را حل نمیکند در واقع :
LogSpace زیرمجموعه یا مساوی P است.
و P زیرمجموعه یا مساوی NP است.

[k1kz]

یک توضیح ساده برای اینکه دقیقا بگم می خواهم چه کار کنم اینه:
فرض کن ما یک عدد بزرگ داریم n میخواهیم مقدار تابع دلخواه مثلا BesselJ را محاسبه کنیم اگر از سری های تیلور استفاده کنیم بعلت همگرایی کند این سری ها باید بیشتر از n جمله از سری های تیلور را محاسبه کنیم یعنی در برنامه نویسی آن باید یک حلقه n تایی داشته باشیم تا اینکه به دقت مورد نظر برسیم ولی این اصلا مطلوب نیست و خیلی طول میکشه ولی مثلا اگه با برنامه Mathematica بخواهیم اینکارو زمان حل این مساله برابر یک عدد ثابت در لگاریتم n میشه یعنی برنامه یک حلقه ای به طول Log n رو اجرا میکنه.البته باید بگم سریهای تیلور برای n های کوچک یعنی بین صفر و یک خیلی سریع همگرا میشه ولی برای اعداد بزرگ نه.

[k1kz]

آقا صابر از توجه تون ممنون هستم ولی فکر کنم متوجه سوالم نشدید
یه توضیح ساده برای اینکه دقیقا بگم چیکار میخواهم کنم اینه:
فرض میخواهیم تابع BesselI0 رو برای یک n بزرگ حساب کنیم اگه از سریهای تیلور استفاده کنیم مجبوریم بیشتر از n
جمله از سریها را حساب کنیم. بعلت همگرایی کند این سریها برای اعداد بزرگ اگه بخواهیم برای محاسبه این تابع برنامه بنویسیم باید یک حلقه به طول بیشتر از n داشته باشیم ولی اگه بخواهیم اینکارو با برنامه Mathematica انجام بدهیم میبینیم که زمان حل مساله توسط برنامه برابر یک عدد ثابت در Log n میشه یعنی برنامه از یک روش پیچیده استفاده میکنه که اینقدر سریع جواب میده .البته بدیهیست که سریهای تیلور برای اعداد کوچک بین صفر و یک خیلی سریع همگرا میشه و تا هر
دقتی میشه سریع محاسبه کرد ولی برای اعداد بزرگ نه . این یک مساله در آنالیز عددی پیشرفته است اگه کتاب یا مقاله در باره آنالیز عددی پیشرفته که این مطلب رو توضیح داده باشه سراغ دارین لطفا بگین