سلام، کسی میتونه این سوال رو تشریح کنه؟
![[تصویر: 241989_problem_algorithm_92.gif]](https://img.manesht.ir/241989_problem_algorithm_92.gif)
این سوال مشکل منم هست
پارسه گفته گزینه ۳
سازمان سنجش گفته گزینه ۴
برای هر آرایه n فاکتوریل حالت وجود داره جمع تمام این حالت ها تقسیم بر n فاکتروریل میشه متوسط حالات ما
وقتی متوسط ما n به توان ۲ هست یعنی ممکنه جایگشتی وجود داشته باشه که با زمان ثابت و خطی حل بشه ولی درمورد n به توان ۳n اگر این جمله در صورت قرار بگیره و تقسیم بر n فاکترویل بشه از n به توان ۲ حتما بیشتر خواهد شد پس وجود چنین جمله ای امکان پذیر نیست پس گزینه ی ۳
منظور از (یک الگوریتم تصادفی) چیست؟
یعنی مرتب سازی ؟ جستجو ؟ قضیه چیه ؟!
(۱۱ بهمن ۱۳۹۲ ۰۹:۴۵ ب.ظ)tayebe68 نوشته شده توسط: منظور از (یک الگوریتم تصادفی) چیست؟
یعنی مرتب سازی ؟ جستجو ؟ قضیه چیه ؟!
الگوریتم تصادفی یعنی worst case behavior رو شما نمیتونی به هیچ وجه بهش اعملا کنی، یعنی نمیتونی یه ورودی رو بهش بدی که زمانش بدترین حالت بشه، مثال مرتب سازی سریع مدل تصادفیش همیشه زمانش nlgn هست و شما نمیتونی هیچ ورودی بهش بدی که n2 بشه، واسه این سوال هم به نظر من میشه ۰ .
(۱۰ بهمن ۱۳۹۲ ۰۷:۱۳ ب.ظ)izadan11 نوشته شده توسط: برای هر آرایه n فاکتوریل حالت وجود داره جمع تمام این حالت ها تقسیم بر n فاکتروریل میشه متوسط حالات ما
وقتی متوسط ما n به توان ۲ هست یعنی ممکنه جایگشتی وجود داشته باشه که با زمان ثابت و خطی حل بشه ولی درمورد n به توان ۳n اگر این جمله در صورت قرار بگیره و تقسیم بر n فاکترویل بشه از n به توان ۲ حتما بیشتر خواهد شد پس وجود چنین جمله ای امکان پذیر نیست پس گزینه ی ۳
دوست من متاسفانه منابع موجود به این سوال اشتباه جواب دادند
پاسخ همان کلید سنجش است گزینه ۴ و هر سه گزاره درست است
گزاره یک درست است زیرا :
جواب غلط:
حداقل یکی از اعمال در زمان ان به توان ۳ان و حتی اگر باقی اعمال را در زمان ۰ فرض کنیم مجموع هزینه ها تقسیم بر تعدادشان یعنی
ان به توان ۳ان تقسیم بر ان میشود جمله ای از درجه ان به توان ۳ان که خیلی خیلی بیشتر از ان به توان دو است طبق این ایده باید گفت گزینه ۳ غلط است !
اما ما برای پیچیدگی یک الگوریتم در حالت میانگین استهلاکی فکر نمیکنیم بلکه مجموع هزینه های هر بار اجرا ی کامل را تقسیم بر کل تعداد دفعات اجرای کامل میکنیم(به محاسبه حالت میانگین برای کویک سورت رجوع کنید )
با این اوصاف اگر شما این الگوریتم را ان به توان ۳ان بار تکرار کنی میتوانی حتی اگر در یک حالت با ان به ۳ان بار زمان اجرا داشتی در حالت میانگین پیچیدگی ان به توان ۲ داشته باشی
بنابر این هر سه گزاره صحیح است
(۱۲ بهمن ۱۳۹۲ ۰۹:۲۹ ب.ظ)atharrashno نوشته شده توسط:در مرحله ی اول گفته یک آرایه ی تصادفی یعنی شانس همه ی ترکیب ها برابر است(یک تقسیم بر ان فاکتوریل)(10 بهمن ۱۳۹۲ ۰۷:۱۳ ب.ظ)izadan11 نوشته شده توسط: برای هر آرایه n فاکتوریل حالت وجود داره جمع تمام این حالت ها تقسیم بر n فاکتروریل میشه متوسط حالات ما
وقتی متوسط ما n به توان ۲ هست یعنی ممکنه جایگشتی وجود داشته باشه که با زمان ثابت و خطی حل بشه ولی درمورد n به توان ۳n اگر این جمله در صورت قرار بگیره و تقسیم بر n فاکترویل بشه از n به توان ۲ حتما بیشتر خواهد شد پس وجود چنین جمله ای امکان پذیر نیست پس گزینه ی ۳
دوست من متاسفانه منابع موجود به این سوال اشتباه جواب دادند
پاسخ همان کلید سنجش است گزینه ۴ و هر سه گزاره درست است
گزاره یک درست است زیرا :
جواب غلط:
حداقل یکی از اعمال در زمان ان به توان ۳ان و حتی اگر باقی اعمال را در زمان ۰ فرض کنیم مجموع هزینه ها تقسیم بر تعدادشان یعنی
ان به توان ۳ان تقسیم بر ان میشود جمله ای از درجه ان به توان ۳ان که خیلی خیلی بیشتر از ان به توان دو است طبق این ایده باید گفت گزینه ۳ غلط است !
اما ما برای پیچیدگی یک الگوریتم در حالت میانگین استهلاکی فکر نمیکنیم بلکه مجموع هزینه های هر بار اجرا ی کامل را تقسیم بر کل تعداد دفعات اجرای کامل میکنیم(به محاسبه حالت میانگین برای کویک سورت رجوع کنید )
با این اوصاف اگر شما این الگوریتم را ان به توان ۳ان بار تکرار کنی میتوانی حتی اگر در یک حالت با ان به ۳ان بار زمان اجرا داشتی در حالت میانگین پیچیدگی ان به توان ۲ داشته باشی
بنابر این هر سه گزاره صحیح است
ما باید یک زیگما بر روی پیچیدگی یک حالت ضرب در احتمال رخ دادن بزنیم
ما کلا ان فاکتوریل حالت داریم چطور ان به توان ۳ ان حالت را انتخاب کنیم؟
فصل ۵ clrs(تحلیل احتمالی و الگوریتم های تصادفی) تمام حالت های متوسط رو به این شیوه بدست آورده
با تحلیل شما می شه خیلی از الگوریتم ها رو در حالت متوسط پیچیدگی ثابت دونست
وقتی میانگین از درجه تتا ان توان دو هست
اول :
یعنی بدترین حالت از درجه کف (اومگا ) ان به توان دو هست پس وقتی بدترین حالت یه بابایی ان به توان ۳ان باشه با این کف ان به توان ۲ منافاتی نداره(یعنی ممکنه بدترین هایی وجود داشته باشند از درجه بیشتر از ان به توان ۲)
دوم
یکی از مزایای الگوریم های تصادفی این هست که احتمال وقوع بدترین حالت در اون بسیار کمه خب من میتونم این احتمال را یه مقدار بسیار ناچیز ۱ به روی ان به توان۳ ان بگیرم ما که در مورد الگوریتم اطلاعات خاصی نداریم در ضمن نمیدونم احتمال وقوع هر حادثه با دیگری برابر هست یا خیر
متاسفانه الان سی ال ار اس دم دست ندارم اما پاسخ گفته شده حل مهندس یوسفی است از این مساله
(۱۲ بهمن ۱۳۹۲ ۱۱:۵۳ ب.ظ)atharrashno نوشته شده توسط: وقتی میانگین از درجه تتا ان توان دو هست
اول :
یعنی بدترین حالت از درجه کف (اومگا ) ان به توان دو هست پس وقتی بدترین حالت یه بابایی ان به توان ۳ان باشه با این کف ان به توان ۲ منافاتی نداره(یعنی ممکنه بدترین هایی وجود داشته باشند از درجه بیشتر از ان به توان ۲)
دوم
یکی از مزایای الگوریم های تصادفی این هست که احتمال وقوع بدترین حالت در اون بسیار کمه خب من میتونم این احتمال را یه مقدار بسیار ناچیز ۱ به روی ان به توان۳ ان بگیرم ما که در مورد الگوریتم اطلاعات خاصی نداریم در ضمن نمیدونم احتمال وقوع هر حادثه با دیگری برابر هست یا خیر
متاسفانه الان سی ال ار اس دم دست ندارم اما پاسخ گفته شده حل مهندس یوسفی است از این مساله
تعریف شما از میانگین غلطه
وقتی میانگین از درجه تتا ان به توان دو هست یعنی جمع پیچیدگی تمام حالات تقسیم بر تعداد حالات برابر است با ان به توان ۲
وقتی می گن الگوریتم تصادفی است یعنی تمام حالت ها احتمال یکسان دارند
بازم تکرار می کنم: آرایه ای به طول n رو ما به n فاکتوریل حالت مختلف می توانیم مرتب کنیم که احتمال هر حال یکسان است از اونجایی دقیقا n فاکتوریل حالت مختلف داریم پس احتمال هر حالت یک تقسیم بر n فاکتوریل هست حال یک زیگما از ۱ تا حالت n فاکتوریل میزنیم و جمع تمام حالات رو محاسبه می کنیم و تقسیم بر تعداد حالات (n فاکتوریل ) می کنیم
الان بالاترین درجه ی قابل قبول ان فاکتوریل به توان دو است و پایین ترین ثابت
آقای یوسفی اشتباه کردن
پی دی اف انگلیسیش(اگه قابل پیدا کردن هست) رو یه مرور کن همه ی سوال های این فصل رو با زیگما زدن بر امید ریاضی حالات بدست آورده
(۱۳ بهمن ۱۳۹۲ ۱۲:۵۷ ق.ظ)izadan11 نوشته شده توسط:اگر احتمال همه حالات برابر می بود گفته شما صحت داشت حالات میانگین الگوریتم هایی که اطلاعاتی در مورد اون و یا وقع حالاتشون داریم مثل کویک صورت که به ترتیب عناصر وابسته است با احتمال وقوع هر حالت یک بر روی ان فاکتوریل خواهد بود اما در منابع که گشتم نگفتن همیشه در الگوریتم های تصادفی احتمال هر حالت با دیگری برابر است بلکه تاکیید کردند الگوریتم های تصادفی الگوریتم هایی است که احتمال وقوع بدترین حالت در ان پایین است و نگفتن این احتمال همیشه ان فاکتوریل است !(12 بهمن ۱۳۹۲ ۱۱:۵۳ ب.ظ)atharrashno نوشته شده توسط: وقتی میانگین از درجه تتا ان توان دو هست
اول :
یعنی بدترین حالت از درجه کف (اومگا ) ان به توان دو هست پس وقتی بدترین حالت یه بابایی ان به توان ۳ان باشه با این کف ان به توان ۲ منافاتی نداره(یعنی ممکنه بدترین هایی وجود داشته باشند از درجه بیشتر از ان به توان ۲)
دوم
یکی از مزایای الگوریم های تصادفی این هست که احتمال وقوع بدترین حالت در اون بسیار کمه خب من میتونم این احتمال را یه مقدار بسیار ناچیز ۱ به روی ان به توان۳ ان بگیرم ما که در مورد الگوریتم اطلاعات خاصی نداریم در ضمن نمیدونم احتمال وقوع هر حادثه با دیگری برابر هست یا خیر
متاسفانه الان سی ال ار اس دم دست ندارم اما پاسخ گفته شده حل مهندس یوسفی است از این مساله
تعریف شما از میانگین غلطه
وقتی میانگین از درجه تتا ان به توان دو هست یعنی جمع پیچیدگی تمام حالات تقسیم بر تعداد حالات برابر است با ان به توان ۲
وقتی می گن الگوریتم تصادفی است یعنی تمام حالت ها احتمال یکسان دارند
بازم تکرار می کنم: آرایه ای به طول n رو ما به n فاکتوریل حالت مختلف می توانیم مرتب کنیم که احتمال هر حال یکسان است از اونجایی دقیقا n فاکتوریل حالت مختلف داریم پس احتمال هر حالت یک تقسیم بر n فاکتوریل هست حال یک زیگما از ۱ تا حالت n فاکتوریل میزنیم و جمع تمام حالات رو محاسبه می کنیم و تقسیم بر تعداد حالات (n فاکتوریل ) می کنیم
الان بالاترین درجه ی قابل قبول ان فاکتوریل به توان دو است و پایین ترین ثابت
آقای یوسفی اشتباه کردن
پی دی اف انگلیسیش(اگه قابل پیدا کردن هست) رو یه مرور کن همه ی سوال های این فصل رو با زیگما زدن بر امید ریاضی حالات بدست آورده
در ضمن سوال از ما نپرسیده دقیقا چه اتفاقی میافته گفته ممکنه چه اتفاقی بیوفته این اتفاق اگر احتمال وقوقع بدترین حالت ضریبی از ان به توان ان۳ باشه ممکنه بیوفته این رابطه را مرور کنید شاید از زاویه به جواب کمک کنه
پیچیدگی در بهترین حالت [tex]\Theta \left ( n^{2} \right )\Rightarrow \O\left (n ^{2} \right )[/tex]
پیچیدگی دربدترین حالت =[tex]\Theta \left ( n^{2} \right )\Rightarrow \Omega \left (n ^{2} \right )[/tex]
(۱۳ بهمن ۱۳۹۲ ۱۰:۲۹ ق.ظ)atharrashno نوشته شده توسط: اگر احتمال همه حالات برابر می بود گفته شما صحت داشت حالات میانگین الگوریتم هایی که اطلاعاتی در مورد اون و یا وقع حالاتشون داریم مثل کویک صورت که به ترتیب عناصر وابسته است با احتمال وقوع هر حالت یک بر روی ان فاکتوریل خواهد بود اما در منابع که گشتم نگفتن همیشه در الگوریتم های تصادفی احتمال هر حالت با دیگری برابر است بلکه تاکیید کردند الگوریتم های تصادفی الگوریتم هایی است که احتمال وقوع بدترین حالت در ان پایین است و نگفتن این احتمال همیشه ان فاکتوریل است !
در ضمن سوال از ما نپرسیده دقیقا چه اتفاقی میافته گفته ممکنه چه اتفاقی بیوفته این اتفاق اگر احتمال وقوقع بدترین حالت ضریبی از ان به توان ان۳ باشه ممکنه بیوفته این رابطه را مرور کنید شاید از زاویه به جواب کمک کنه
پیچیدگی در بهترین حالت [tex]\Theta \left ( n^{2} \right )\Rightarrow \O\left (n ^{2} \right )[/tex]
پیچیدگی دربدترین حالت =[tex]\Theta \left ( n^{2} \right )\Rightarrow \Omega \left (n ^{2} \right )[/tex]
این که گفته بشه " احتمالش بسیار ناچیزه" صحیحه ولی این در مواردی هست که کتاب نمی خواد اثبات دقیق ارائه بده (اثبات سرپای بهش می گن) بهتون پیشنهاد می کنم چند تااز این اثبات های دقیق رو بخونید
تصادفی در همه جا و همیشه یعنی الگوریتمی که احتمال وقوع هر حالت برابر باشد این یه مفهومه و بارها در درس های مختلف از استاد ها شنیدم
(۱۳ بهمن ۱۳۹۲ ۱۰:۴۵ ق.ظ)izadan11 نوشته شده توسط:ممکنه در درس های مختلف معانی مختلفی بده اساسا شما درسیستمی که به صورت تصادفی که یکدونه ۲، ۶۰۰ تا ۱ و ۲۰۰۰ تا صفر را تولید کرده و بخوای دنبال بزرگترین عنصر ۲ باشید نمیتونید بگید احتمال پیدا کردن ۲ با احتمال پیدا کردن ۱ برابره !(13 بهمن ۱۳۹۲ ۱۰:۲۹ ق.ظ)atharrashno نوشته شده توسط: اگر احتمال همه حالات برابر می بود گفته شما صحت داشت حالات میانگین الگوریتم هایی که اطلاعاتی در مورد اون و یا وقع حالاتشون داریم مثل کویک صورت که به ترتیب عناصر وابسته است با احتمال وقوع هر حالت یک بر روی ان فاکتوریل خواهد بود اما در منابع که گشتم نگفتن همیشه در الگوریتم های تصادفی احتمال هر حالت با دیگری برابر است بلکه تاکیید کردند الگوریتم های تصادفی الگوریتم هایی است که احتمال وقوع بدترین حالت در ان پایین است و نگفتن این احتمال همیشه ان فاکتوریل است !
در ضمن سوال از ما نپرسیده دقیقا چه اتفاقی میافته گفته ممکنه چه اتفاقی بیوفته این اتفاق اگر احتمال وقوقع بدترین حالت ضریبی از ان به توان ان۳ باشه ممکنه بیوفته این رابطه را مرور کنید شاید از زاویه به جواب کمک کنه
پیچیدگی در بهترین حالت [tex]\Theta \left ( n^{2} \right )\Rightarrow \O\left (n ^{2} \right )[/tex]
پیچیدگی دربدترین حالت =[tex]\Theta \left ( n^{2} \right )\Rightarrow \Omega \left (n ^{2} \right )[/tex]
این که گفته بشه " احتمالش بسیار ناچیزه" صحیحه ولی این در مواردی هست که کتاب نمی خواد اثبات دقیق ارائه بده (اثبات سرپای بهش می گن) بهتون پیشنهاد می کنم چند تااز این اثبات های دقیق رو بخونید
تصادفی در همه جا و همیشه یعنی الگوریتمی که احتمال وقوع هر حالت برابر باشد این یه مفهومه و بارها در درس های مختلف از استاد ها شنیدم
ایجا هم ما هیچ پیش فرضی از عناصر نداریم نمیدونیم یکتا هستند میخواد ارایه چکار کنه بدترین حالتش به چی وابسته است و....
هرچند حرف شما متین و حرفه ای است