رفتن به مطلب
آخرین اخبار
  • به انجمن کتابساز خوش آمدین : لطفا بعد عضویت حتما با مقررات و قانون کتابساز آشنایی داشته باشید از این که مارو انتخاب کردین سپاس گذاریم
نحوه ی گذاشتن مطلب در انجمن
درخواست طراحی جلد برای رمان
قوانین و راهنمای ارسال کتاب در حال تایپ فراخوان جذب ویراستار + آزمون ویراستاری

...Ice...

نویسنده افتخاری
  • تعداد ارسال ها

    26
  • تاریخ عضویت

  • آخرین بازدید

  • روز های برد

    1

آخرین بار برد ...Ice... در 3 مرداد 1397

...Ice... یکی از رکورد داران بیشترین تعداد پسند مطالب است !

اعتبار در سایت

65

5 دنبال کننده

درباره ...Ice...

آخرین بازدید کنندگان نمایه

182 بازدید کننده نمایه
  1. ...Ice...

    خیلی نازه خدا حفظش کنه واستون.یه اسفند دود کنید براش چشم نخوره
  2. ...Ice...

    شرمنده من نمیدونستم.تازه اومدن .عذر خواهی
  3. ...Ice...

    نگاهی به ساعتش انداخت. منتظرش بود.اما این انتظار برای یک مرده کار سختی است.
  4. ...Ice...

    ادامه قسمت چهارم: ما نیاز به دو الگوریتم داریم .. یکی برای ادغام و دیگری برای مرتب سازی ادغامی که هردو رو به صورت شبه کد بیان می کنیم . تحلیل ادغام اگر بخوایم بدترین حالت الگوریتم ادغام رو تحلیل کنیم ، باید بگیم که در زمان خروج از حلقه ، اندیس i به h میرسه و j به m-1 خواهد رسید . لذا برای دو متغیر m و h داریم : T(h,m)=h+m-1 اما برای مرتب سازی ادغامی باید بگیم که تعداد کل مقایسه ها برابر هست با مجموع تعداد مقایسه ها در فراخوانی بازگشتی با U و تعداد مقایسه ها در فراخوانی بازگشتی با V به علاوه ی تعداد مقایسه های موجود در فراخوانی تابع merge . پس داریم : W(n)= W(h)+W(m)+h+m-1 با جایگذاری مناسب کل داده ها ی n داریم : W(n)=W(n/2)+W(n/2)+n+1 که با حل معادله ی بازگشتی فوق به n log n خواهید رسید . روش بعدی هم الگوریتم مرتب سازی سریع هست quick sort این روش نسبتا مشابه روش قبلی هست . توی این روش ما یک عنصر رو به عنوان عنصر محوری انتخاب می کنیم و عناصر کوچکتر از محور رو در یک زیر آرایه و عناصر بزرگتر رو به سمت زیر آرایه ی دیگه ای می بریم . عنصر محوری دلخواه هست ولی معمولا برای سهولت ، از عنصر اول به عنوان محور استفاد می کنن . زیر آرایه ها هم عنصر محوری میگیرن و همون روند تکرار میشه و به همین ترتیب ادامه پیدا میکنه تا کل آرایه با مرتب شدن زیر آرایه ها ، مرتب بشه . واضح هست که اینم نوعی روش تقسیم و حل هست . اول شبه کد افراز رو میگیم که در الگوریتم مرتب سازی سریع استفاده شده و سپس شبه کد خود الگوریتم رو بیان می کنیم . تحلیل: پیچیدگی زمانی الگوریتم افراز T(n)=n-1 هست چون تمام عناصر به جز اولی مقایسه میشن . اما برای مرتب سازی سریع بدترین حالت زمانی هست که آرایه به صورت غیر نزولی مرتب شده باشه از اول . ( به عنوان تمرین خودتون فکر کنید که چرا !!) در این صورت خواهیم داشت : T(n)=T(0) + T(n-1) + n-1 در فرمول بالا ، زمان اجرای مرتب سازی زیر آرایه ی چپ ، زیر آرایه ی راست و زمان لازم برای افراز با هم جمع شدند. با حل معادله ی بازگشتی فوق به رابطه ی زیر میرسید T(n) = (n*(n-1))/2 که مشخصا معلوم میکنه الگوریتم از مرتبه ی n به توان 2 هست لازم به ذکر هست که پیچیدگی این الگوریتم در حالت میانگین از مرتبه ی nlog n هست . اما برنامه ریزی پویا چیه ؟؟ این روش از لحاظ تقسیم کل مسئله به مسائل کوچک تر، مشابه روش تقسیم و حل هست ولی ما اول تقسیم می کنیم و نتایج رو ذخیره می کنیم و در ادامه هر زمان که به یکی از اونها احساس نیاز شد ، به جای محاسبه ی دوباره ، اون نتایج رو به اصطلاح بازیابی می کنیم . خب دوستان عزیز ، برای این جلسه کافیه .. ان شاءالله در جلسه ی بعد بحث برنامه ریزی پویا رو ادامه میدیم و با برخی الگوریتم ها و مباحث مرتبط با اون آشنا میشیم . کپی شده از سایت http://ilikephp.ir/
  5. ...Ice...

    قسمت چهارم: سلام عرض می کنم خدمت همه ی شما دوستان عزیز و ارجمند ضیادید هستم و با قسمت چهارم آموزش طراحی و تحلیل الگوریتم ها در خدمت شما خواهم بود . در این جلسه قصد داریم 3 الگوریتم بسیار مهم در روش تقسیم و حل رو بیان کنیم و پیچیدگی زمانی اونهارو هم مورد بررسی قرار بدیم . و ان شاءالله بعد از اون میریم سراغ یک تعریف مقدماتی از برنامه ریزی پویا اولین الگوریتمی که میخوایم بررسی کنیم ، الگوریتم جست و جوی دودویی به روش بازگشتی هست .همونطور که گفته شد ، در تقسیم و حل ما روش بالا به پایین رو اعمال می کنیم . هدف از جست و جوی دودویی ، پیدا کردن یک عنصر (عدد) در یک آرایه هست . مکانیزم این جست و جو هم به این شکل هست که فرض کنید عددی که ما به دنبال اون هستیم ، x باشه . یعنی میخوایم x رو در یک آرایه پیدا کنیم . بر اساس این الگوریتم ، عنصر x با عنصر میانی آرایه مقایسه میشه . 3 حالت به وجود میاد . اگر دو تا عدد مساوی باشن که مسئله حل میشه . اگه کوچکتر از عنصر میانی باشه ، به زیر آرایه ی سمت چپ میریم و اگر بزرگتر باشه هم به زیر آرایه ی سمت راست خواهیم رفت . تذکر مهم: از ساختار این الگوریتم هم مشخصه که فقط زمانی میتونیم از این الگوریتم استفاده کنیم که آرایه به صورت غیر نزولی (صعودی ) مرتب شده باشه . مثلا فرض کنیم عدد 19 رو بخوایم توی آرایه ی زیر پیدا کنیم : 10 11 14 18 19 29 40 41 48 50 51 در اولین گام ، آرایه به دو زیر آرایه تقسیم میشه . عنصر میانی عدد 29 هست که با 19 برابر نیست . چون 29>19 پس باید به زیر آرایه ی سمت چپ بریم یعنی این آرایه 10 11 14 18 19 حالا مرحله ی گذشته برای آرایه ی جدید ما اجرا خواهد شد و درنتیجه ی ادامه ی همین روند ، عدد مورد نظر پیدا میشه . خب حالا بریم سراغ شبه کد این الگوریتم اما پیچیدگی زمانی این الگوریتم به چه صورت هست ؟ ببینید دوستان ، اگه ما پیچیدگی این الگوریتم رو با T(n) نشون بدیم ، به این معناست که داریم پیچیدگی زمانی رو برای n متغیر ( آرایه ای با طول n ) بررسی می کنیم . اگه مرحله ی اول انجام بشه ، یعنی یک مقایسه بین عدد x و عنصر میانی آرایه صورت گرفته و نصف آرایه دور ریخته میشه و همون مکانیزم برای n/2 عضو باقیمانده ی آرایه تکرار خواهد شد . در واقع بین T(n) و T(n/2) فقط 1 واحد زمانی فاصله هست . پس ما میتونیم ادعا کنیم که رابطه ی زیر رو داریم : T(n) =T(n/2)+1 با استفاده از قضیه ی اساسی پیچیدگی الگوریتم (تئوری Master) واضح هست که پیچیدگی این الگوریتم از مرتبه ی log n خواهد بود . اما الگوریتم بعدی مرتب سازی ادغامی هست . دراینجا هدف ما مرتب سازی یک آرایه ی به هم ریخته به روش ادغام هست . (merge sort) یه اصطلاحی هست به نام" ادغام دوطرفه" و به معنی ترکیب دو آرایه ی مرتب شده در یک آرایه هست . وقتی شما به طور متوالی از فرایند ادغام استفاده کنید ، میتونید تمام اعضای یک آرایه رو مرتب کنید . مثلا اگه یک آرایه ی 8 عضوی داشته باشید ، با تقسیم اون به دو زیر آرایه ی 4 عضوی آنها رو مرتب و سپس ادغام کنید . یعنی با استفاده از این الگوریتم ، کل آرایه ابتدا تقسیم میشه و راه حل ما روی اونها اعمال میشه و سپس با ادغام زیر آرایه ها ، کل آرایه به دست میاد و شما میتونید متوجه بشید که در این الگوریتم هم از روش تقسیم و حل داره استفاده میشه . کپی از سایت http://ilikephp.ir/
  6. ...Ice...

    ادامه قسمت سوم: ما الان میخوایم یک قضیه ای رو بگیم به نام "قضیه ی اصلی" که بسیار در محاسبه ی پیچیدگی زمانی الگوریتم ها کاربرد داره . شکل خلاصه ی این قضیه به این صورت هست : البته دقت کنید که در حالت دوم (case 2) ، منظور log n بر مبنای b هست . فرض کنید مثلا شکل پیچیدگی زمانی یک الگوریتم به فرم بالا باشه طبق قضیه ی اصلی واضح هست که مرتبه ی زمانی چنین الگوریتمی θ(n^2 هست . اما معادلات بازگشتی رو هم باید به خوبی یاد گرفت . در تحلیل الگوریتم ها، روابط بازگشتی اهمیت زیادی دارن. مثلا اگه یک الگوریتم جوری طراحی بشه که یک مسأله رو به زیر مسأله های کوچکتر تبدیل کنه، زمان اجرای اون رو میشه با روابط بازگشتی توصیف کرد. ما توی این سری آموزشی نمیخوایم روابط بازگشتی رو باز کنیم چون یک مبحث مفصل هست و آموزش رو بیش از حد به سمت ریاضیات میبره . فقط در همین حد اشاره کنم که به دلیل اهمیت روابط بازگشتی ، باید حتما یک دانش ابتدایی از راه های پیدا کردن جواب های روابط بازگشتی و راه حل های اونها پیدا کنیم . پس حتما یک تحقیقاتی درباره ی روابط بازگشتی بکنید . اما اجازه بدید بریم سراغ روش تقسیم و حل : ببینید دوستان ، این روش شامل الگوریتم هایی هستن که نمونه ای از یک مسئله رو به دو یا چند نمونه ی کوچکتر تقسیم میکنن . حالا اگه بشه این نمونه های کوچک رو به راحتی حل کرد ، میشه با ترکیب اونها به جواب مسئله ی اصلی رسید و اگه نشه همون مسئله های کوچک رو براحتی حل کرد ، بازهم میان و مسئله رو به بخش های کوچتری تقسیم میکنن تا جایی که بشه اونها رو به شکل بسیار راحتی حل کرد . به این روش میگن روش تقسیم و حل یا divide & conquer . این روش اصطلاحا یک روش بالا به پایین یا top_down هست . یعنی حل یک نمونه ی سطح بالا از مسئله ، با رفتن به پایین و به دست آوردن حل نمونه های کوچکتر حاصل میشه . از جمله مهمترین الگوریتم هایی که در این روش قرار میگیرن عبارت هستن از : 1-جست و جوی دودویی 2-مرتب سازی ادغامی 3-مرتب سازی سریع 4-الگوریتم استراسن البته مشخص هست که چنین روشی (یعنی الگوریتم های موجود در این روش ) در همه جا کاربرد مطلوب نداره و ممکنه در بعضی از موقعیت ها اصلا مارو به جواب نرسونه و یا کارآمدی فوق العاده پایینی داشته باشه . اصولا برای همین هست که روش های گوناگون و الگوریتم های گوناگونی به وجود میان . پس بهتر هست با انواع مختلف روش ها آشنا بشیم و از هرکدوم در موقعیت های مخصوص به خودشون استفاده کنیم . مهمترین جاهایی که الگوریتم های موجود در روش تقسیم و حل در اونها جواب نمیده عبارت هستن از : 1- زمانی که نمونه ای با اندازه ی n به دو یا چند نمونه تقسیم بشه که اندازه ی اونها هم تقریبا n باشه . در این حالت معمولا پیچیدگی زمانی الگوریتم به صورت نمایی خواهد بود که اصلا جالب نیست !! 2- زمانی که نمونه ای با اندازه ی n تقریبا بهn نمونه ی با اندازه ی n/k تقسیم بشه که kیک عدد ثابت هست . در این جا هم پیچیدگی زمانی الگوریتم به صورت n^log n خواهد بود . خب دوستان عزیز ، برای این جلسه کافیه . در این جلسه به صورت کامل با نمادهای پیچیدگی زمانی الگوریتم ها آشنا شدیم ، یکی دو روش معمول در محاسبه ی پیچیدگی زمانی رو بیان کردیم و مقدمات روش تقسیم و حل رو گفتیم . در جلسه ی بعد هم انشاءالله دو یا سه الگوریتم بیان شده در روش تقسیم و حل رو با ذکر پیچیدگی زمانی اونها توضیح میدیم و مقدمات بحث " برنامه ریزی پویا " رو بیان خواهیم نمود . تا دیدار بعدی شما رو به خدای بزرگ می سپارم . موفق و پیروز و سالم و تندرست باشید . کپی شده از سایت http://ilikephp.ir
  7. ...Ice...

    قسمت سوم: من سعید ضیادید هستم و با جلسه ی سوم آموزش طراحی و تحلیل الگوریتم در خدمت شما خواهم بود در جلسه ی گذشته بیشتر درباره ی کارآمدی الگوریتم و پیچیدگی زمانی یک الگوریتم صحبت کردیم و تعدادی نماد رو هم معرفی کردیم . در این جلسه همون مباحث رو ادامه میدیم و چند نکته درباره ی پیچیدگی زمانی یک الگوریتم بیان میکنیم و انشاءالله در آخر مقدمات روش تقسیم و حل رو با شروع میکنیم .خب نماد θ رو تعریف میکنیم.. نماد θ دقیقا مرتبه ی یک الگوریتم رو تعیین میکنه .. درواقع θ بیانگر حد متوسط زمان اجرای یک الگوریتم هست یعنی زمان اجرای یک الگوریتم در حالت میانگین . پس ( θ(g(n) شامل توابعی هست که رشدشون تقریبا مساوی و یکسان با gn باشه . اما دوتا نماد دیگر هم داریم که ω و o هستند . ω شکل اکید Ω و o هم شکل اکیدO هست . این ها نماد هایی بودن که ما در پیچیدگی زمانی از اونها استفاده می کنیم . اما اجازه بدید الان ببینیم که چطور میشه سرعت رشد دو تابع رو باهم مقایسه کرد . یکی از راه های معمول برای این کار استفاده از حد هست . فرض کنید که ما دو تابع f و g داریم و میخوایم بدونیم رشد کدوم بیشتره و یا میخوایم بدونیم از چه نمادی باید استفاده کنیم برای این دو تابع . اگه بخوایم از حد استفاده کنیم کافیه عبارت زیر رو حساب کنیم : lim fx/gx که x به سمت بی نهایت میل خواهد کرد . (f و g توابعی بر حسب متغیر x هستند ) پس داریم حد در بی نهایت رو محاسبه میکنیم . اما برای جواب این حد ، 3 حالت پیش میاد : 1-جواب بی نهایت خواهد بود . 2-جواب 0 خواهد بود. 3-جواب یک عدد ثابت غیر از صفر خواهد بود . اگه جواب بی نهایت بشه ، یعنی سرعت رشد تابع f بسیار بیشتر از تابع g هست . اگه جواب صفر بشه ، یعنی سرعت رشد تابع fبسیار کمتر از تابع g هست چون اگر متغیر رو به سمت بی نهایت ببریم ، مقدار صورت کسر نسبت به مخرج کسر بسیار کوچک تر میشه .البته هردوی اونها دارن زیاد میشن ولی سرعت رشد صورت خیلی کمتر از مخرجه که در این صورت کسر به سمت صفر میل خواهد کرد . اگر هم جواب یک عدد ثابت مثل c بشه که c مخالف صفر باشه ، به این معنی خواهد بود که توابع f و g دارای سرعت رشد تقریبا یکسان هستند . بنابراین اگر خواستیم سرعت رشد یا میزان رشد دو تابع رو که معرف پیچیدگی زمانی دو الگوریتم هستن، با هم مقایسه کنیم ، میتونیم از این روش استفاده کنیم . اگر عبارتی که محاسبه کردیم ( حد نسبت تابع f به g ) مبهم شد ، میتونیم از راه هایی مثل قاعده ی هوپیتال استفاده کنیم تا جواب حد ، یکی از حالت های ذکر شده بیاد . کپی شده از سایت http://ilikephp.ir
  8. ...Ice...

    ادامه قسمت دوم: تعداد مراحل عمل انتساب <a>=> برابر با تعداد مراحل <b> هست . که a شامل یک متغیر و b شامل یک عبارت هست . البته اگه aتابعی از ویژگی های نمونه باشه ، اونوقت تعداد مراحل انتساب برابر با مجموع اندازه ی متغیر و تعداد مراحل عبارت هست . دستور شرطی if else هم 1 مرحله داره . حلقه ی for(a;b;c) هم دارای b+c مرحله هست . (منظور از b و c ، تعداد مراحل اونهاست . ) فراخوانی توابع و دستورات مدیریت حافظه دارای 1 مرحله هستن . شبه کد زیر رو در نظر بگیرید : float sum1(float *a , const int n) 1. { 2. float s=0 ; 3. for ( int i=0;i<n;i++) 4. s=s+a[i]; 5. return s; 6. } این شبه کد ، مجموع عناصر درون یک آرایه ی n عضوی رو برمیگردونه. خط اول این برنامه ، مرحله ای نداره خط دوم دارای 1 مرحله هست خط سوم که یک حلقه ی تکرار هست ، دارای n+1 مرحله هست . خط چهارم هم n مرحله داره . (اگرچه عمل انتساب هست ولی n بار داره تکرار میشه . ) خط پنجم دارای 1 مرحله هست . خط ششم هم مرحله ای نداره . پس میشه گفت تعداد کل مراحل شبه کد بالا برابر با 2n+3 هست . یک سوال : فرض کنیم که تعداد مراحل برنامه ی A برابر 2n+3 و تعداد مراحل برنامه ی B برابر 2n+2 باشد. آیا از این مطلب میشه نتیجه گرفت که برنامه ی A ازB کندتر انجام میشه؟ جواب منفیه !! نمیشه نتیجه ی مشخصی گرفت .. چون مراحل دارای واحد زمانی معینی نیستن . ممکنه 3 مرحله ی موجود برنامه ی A به طور مجموع سریع تر از 2 مرحله ی B باشن . پس میشه نتیجه گرفت اون اعداد ثابت ملاک خوبی نیستن پس در پیچیدگی زمانی اونها رو میتونیم درنظر نگیریم و به طور کلی بگیم پیچیدگی زمانی به n وابسته هست . به همین دلیل اصطلاحا میگیم هردو برنامه ی A و B از مرتبه ی n هستن . همونطور که میدونیم ، ممکنه الگوریتم های مختلفی برای حل یک مسئله وجود داشته باشن . مثلا برای مرتب سازی یک سری داده ، الگوریتم هایی نظیر : Bubble sort-Selection sort و .....وجود دارن . برای تشخیص دامنه ی کارآمدی الگوریتم ها ، به معیار هایی نظیر پیچیدگی زمانی و پیچیدگی فضای حافظه نیاز داریم. بنابراین منظور ما از تجزیه و تحلیل الگوریتم ها ، مشخص کردن زمان اجرای برنامه ها هست . هر پردازنده در هرلحظه بیش از یک دستور رو نمیتونه اجرا کنه و این مستقل از نوع پردازنده و سیستم هست. پس هر برنامه در کامپیوتر ها باید دستور به دستور انجام بشه و بنابراین تعداد دستورات برنامه ، مدت زمان اجرای برنامه را نشون میدن . هدف از تعیین تعداد مراحل این است که بتونیم پیچیدگی زمانی دو برنامه روکه عمل مشابهی انجام می دن مقایسه کنیم و بتونیم میزان افزایش زمان اجرا رو در زمان تغییر مشخصات نمونه ، پیشبینی کنیم . الان ، اصطلاحات و نمادهایی رو معرفی می کنیم که ما رو قادر می سازه عبارات با معنی در مورد زمان و فضای پیچیدگی یک برنامه ایجاد کنیم . معمولا زمان اجرای یک برنامه رو با Tnنشون میدن . اما یکی از نماد های مهم نماد اوی بزرگ هست . تعریف big O: حد بالای زمان اجرای برنامه هست . به معنای دیگر ، زمان اجرای یک برنامه در بدترین حالت . فرض کنیم fn زمان اجرای برنامه بر حسب n باشه. میگیم الگوریتم دارای زمان اجرای Ogn هست اگهc>0 وجود داشته باشه به طوریکه fn<=cgn وقتی میگیم On^2 یعنی تمام توابعی که رشدشون کمتر یا مساوی تابع n^2 هست . و وقتی پیچیدگی زمانی یک الگوریتم On^2باشه یعنی در بدترین حالت ممکن ، تابع پیچیدگی زمانیش از n^2 بیشتر نمیشه ..پس پیچیدگی رو برحسب یک تابع بیان میکنیم . O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(n!) پس مثلا الگوریتمی که مرتبه ی زمانیش در بدترین حالت ممکن برابر با log n باشه ، بسیار از لحاظ زمانی بهتر از الگوریتمی با زمان اجرای n^3 خواهد بود . تعریف Ω حد پایین زمان اجرای یک برنامه هست . یعنی زمان اجرای یک برنامه در بهترین حالت. میگیم الگوریتم دارای زمان اجرایΩgn هست اگه fn≥Ωgn پس Ωgn شامل توابعی هست که رشدشون بزرگتر یا مساوی gn باشه. الگوریتمی با چنین مرتبه ای هم در بهترین حالت دارای پیچیدگی زمانی gn میشه خب دوستان عزیزم برای این جلسه کافیه در جلسه ی بعد نماد Θ رو تعریف میکنیم . چند مثال برای محاسبه ی پیچیدگی زمانی همراه با نمایش نماد ها بیان میکنیم . کمی درباره ی روابط بازگشتی حرف میزنیم و مقدمات مبحث "تقسیم و حل" رو ارائه میکنیم .. کپی شده از سایت http://ilikephp.ir
  9. ...Ice...

    قسمت دوم: سلام عرض می کنم خدمت همه ی شما عزیزان .. من سعید ضیادید هستم و در خدمت شما هستم با جلسه ی دوم آموزش طراحی و تحلیل الگوریتم ها . اجازه بدید یک خلاصه از مباحث جلسه ی قبل رو خدمت شما عرض کنم . در جلسه ی گذشته با یکسری از تعاریف اولیه ی مرتبط با الگوریتم و فلوچارت آشنا شدیم و همچنین ویژگی های الگوریتم رو بیان کردیم . کمی هم درباره ی کارآمدی الگوریتم مطالبی ارائه کردیم . اما در این جلسه به طور کلی میخوایم درباره ی کارآمدی الگوریتم صحبت کنیم . همونطور که گفته شد ، ملاک و معیار کارایی یک الگوریتم ، پیچیدگی زمانی و پیچیدگی فضاست . ما دراین سری از آموزش ها بیشتر درباره ی پیچیدگی زمانی صحبت میکنیم . اما اجازه بدید کمی راجع به پیچیدگی فضا صحبت کنیم تا بعد مفصل بریم سراغ پیچیدگی زمانی شبه کد زیر رو در نظر بگیرید : float OP1(float a , float b , float c){ return a+b+c*a/a+c+2.0 ; } این برنامه یک عبارت خاصی رو محاسبه میکنه و نتیجه رو برمیگردونه. فضای مورد نیاز برای یک چنین برنامه ای شامل دو بخش ثابت و متغیر است . بخش ثابت ، مستقل از بعضی ویژگی های ورودی و خروجی هست و شامل فضای دستور العمل ، فضای لازم برای ذخیره ی کد برنامه ، فضای لازم برای متغیر های ساختاری با اندازه ی ثابت و ثابت ها و غیره هست . بخش متغیر هم شامل فضای لازم برای متغیر های ساختاری و تغییر پذیر برنامه هست که وابسته به نمونه ی موجود در مسئله هستن . همچنین این بخش شامل فضای لازم برای متغیر های مرجع و پشته ی بازگشتی هم هست . فضای لازم برای هر برنامه ای مثل P رو اگر S(P) فرض کنیم ، میشه به صورت S(P)=c+sp نوشت که توی اون c یک مقدار ثابت هست و sp مشخصات نمونه ی مسئله هست . برای برنامه ای که بالا گفتیم ، نمونه ی مسئله با حروفی نشون داده شدن (a,b,c). با این فرض که همه ی این مقادیر در یک کلمه از حافظه ذخیره بشن متوجه میشیم فضای مورد نیاز برای تابع درون مسئله ، مستقل از ویژگی های نمونه هست . پس sp برابر صفر هست . اما بریم سراغ پیچیدگی زمانی . پیچیدگی زمانی یعنی مقدار زمانی که یک کامپیوتر برای اجرای کامل یک برنامه لازم داره . هر برنامه یکسری مراحلی داره و از دستوراتی تشکیل شده . معمولا برای تشخیص زمان اجرای برنامه هم به مراحل اجرای برنامه توجه می کنند . اما یک مرحله از برنامه رو میشه به عنوان یک قسمت بامعنی از نظر دستوری تعریف کرد که زمان اجرای اون به ویژگی های نمونه بستگی نداره . تعداد مراحلی که به هر کدوم از دستورات برنامه باید نسبت داده بشه ، به ماهیت اون دستور بستگی داره . حالا برای آشنایی بیشتر میایم تعداد مراحل لازم برای اجرای برخی از دستورات موجود در یک زبان استاندارد ، مثلا ++C ، رو بررسی میکنیم . البته تعداد مراحل ذکر شده برای برخی دستورات به صورت تقریبی هستن و ممکنه توی برنامه های مختلف تغییر کنن ولی اغلب اوقات به همین شکل هستن . تمامی توضیحات در این زبان دارای صفر مرحله هست . یعنی برای توضیحات هیچ مرحله ای درنظر گرفته نمیشه . دستور های تعریفی و اعلان هم مرحله ای ندارن ( دارای صفر مرحله هستن .) منظور از دستور های تعریفی ، دستوراتی هستند که متغیر ها، ثابت ها ، توابع یا نوع دسترسی رو مشخص میکنن هر عبارت دارای 1 مرحله هست . ( به جز عبارات فراخوانی توابع ) کپی شده از سایت http://ilikephp.ir
  10. ...Ice...

    ادامه قسمت اول: خب حالا همین ابتدا سوالی پیش میاد : ❓چرا با وجود اینکه سرعت کامپیوتر ها در حال افزایش هست و حافظه هم در حال ارزانتر شدن ، بررسی کارایی یک الگوریتم ضرورت پیدا میکنه ؟ جواب رو بایک مثال متوجه خواهیم شد : در ریاضیات یکی از موضوعات کاربردی ، دنباله ی فیبوناچی هست . برای پیدا کردن یکی از جملات این دنباله 2 راه حل داریم . یکی الگوریتم بازگشتی هست و دیگری الگوریتم تکراری . int fibo (int n ) { if (n<=1) return n; else return fibo(n-1) + fibo (n-2) ; } الگوریتم بازگشتی محاسبه ی جمله ی n ام دنباله ی فیبوناچی int fibo (int n) { index i ; int f[0.n]; f [0] = 0 ; if (n>0) { f [1] = 1; for ( i=2; i<= n ; i++) f[ i ] = f [i-1] + f [i-2] ; } return f[n]; } الگوریتم تکراری محاسبه ی جمله ی n ام دنباله ی فیبوناچی فرض کنیم بخوایم جمله ی 100 ام این دنباله رو حساب کنیم . اگر با الگوریتم تکراری اینکارو کنیم ، 101 نانو ثانیه طول میکشه در حالی که با الگوریتم بازگشتی اینکار در 13 روز انجام خواهد پذیرفت . اگر جمله ی 120 ام رو بخوایم حساب کنیم ، با الگوریتم تکراری 121 نانو ثانیه وقت میخوایم ولی با روش بازگشتی 36 سال طول میکشه ..!!!!!! خب مشخصه که بحث کارایی بحث خیلی مهمیه .. این دقیقا بحث زمان اجراست و حالا باید دید چرا این زمان ها متفاوته و این اختلاف بسیار زیاده .. این همون پیچیدگی زمانی الگوریتم هست که در جلسه ی بعدی راجع به اون صحبت می کنیم خب برای جلسه ی اول کافیه .. ان شاءالله در جلسه ی بعدی به طور کلی به بحث تحلیل الگوریتم ها و نماد های موجود در محاسبه ی پیچیدگی زمانی الگوریتم ها می پردازیم . کپی شده از سایتhttp://ilikephp.ir
  11. قسمت اول: در جلسه ی اول قصد دارم درباره ی مقدمات الگوریتم و فلوچارت و همچنین مشخصات یک الگوریتم مطالبی رو عرض کنم . همچنین درباره ی کارآمدی الگوریتم هم کمی صحبت می کنیم . همه ی ما با مفهوم مسئله آشنا هستیم . یک مسئله پرسشی هست که به دنبال پاسخش می گردیم و برای رسیدن به جواب اون ، باید راه حلی رو بکار بگیریم . میشه گفت که مجموعه ی مراحل لازم برای رسیدن به پاسخ مطلوب یک مسئله ، روش حل یا الگوریتم هست . در برنامه نویسی کامپیوتر ، برای حل یک مسئله ، باید مرحله به مرحله و قدم به قدم ، به کامپیوتر بگیم که چگونه اون رو حل کنه . و این مراحل قدم به قدم همون الگوریتم نامیده میشه . مثلا برای محاسبه ی فاکتوریل عدد n یا پیدا کردن بزرگترین بین سه عدد ، باید مراحل انجام کار رو دقیقا و مرحله به مرحله به کامپیوتر یاد بدیم چون قطعا خودش همچین مکانیزمی برای تشخیص روش حل مسئله و پیدا کردن جواب مسئله نداره . پس همین الگوریتم ها در قالب یک برنامه به کامپیوتر میرسه و اون میتونه مسائلی رو مانند مسائل بالا حل کنه . مبحث الگوریتم معمولا مستقل از زبان برنامه نویسی هست و یکی از مهمترین مباحث موجود در علوم کامپیوتر به حساب میاد . یک الگوریتم باید ویژگی هایی داشته باشه از جمله : 1-دارای آغاز و پایان مشخص باشه . 2- هر مرحله دارای جزئیات دقیق باشه . 3- مراحل دارای یک ترتیب درست باشه . خب اما میشه دستور العمل هارو به انواع مختلفی تقسیم کرد برخی از انواع دستور العمل ها هم عبارت هستند از : 1-محاسباتی و انتسابی : میشه عملیات محاسباتی انجام داد یا مقداری رو به مقداری دیگر نسبت بدیم . 2-شرطی : با این دستورالعمل میشه انواع شروط رو بررسی کرد . 3-خروجی : در این دستور العمل هم مقادیری به چاپ میرسند . بیاید الگوریتم یک مسئله ی ساده رو بررسی کنیم : الگوریتمی که دو عدد رو دریافت کنه و تعیین کنه مجوعشون از 40 بزرگتر هست یا نه . 1-شروع 2-دو عدد aوb از ورودی دریافت کن 3- a+b رو محاسبه کن 4-آیا a+b > 40 هست ؟ اگر بله برو به مرحله ی 7 5-"خیر" را چاپ کن. 6-به مرحله ی 8 برو 7-" بله" را چاپ کن 8-پایان همون طور که مشاهده می کنید تمام ویژگی هایی که برای یک الگوریتم عرض شد ، در الگوریتم ساده ی بالا مشاهده میشن . یعنی آغاز و پایان مشخصی دارن . هر مرحله جزئیات کافی داره و ترتیب مراحل هم کاملا درست هستن . حالا فلوچارت چیه ؟؟ فلوچارت یک راه استاندارد برای نمایش الگوریتم هست که توی اون باید از یک سری شکل های استاندارد برای نمایش دستور العمل ها ی مختلف استفاده کرد . شکل های بالا همون شکل هایی هستند که به عنوان استاندارد در فلوچارت ها مورد استفاده قرار می گیرند.. شکل اول " شروع " یا " پایان " الگوریتم رو مشخص میکنه . شکل دوم که یک "فلش" هست ، جهت جریان منطقی در یک برنامه رو نشون میده شکل سوم یعنی متوازی الاضلاع ، دستور العمل های ورودی و خروجی رو مشخص میکنه شکل چهارم هم دستور العمل های انتساب و محاسبات رو نشون میده و در شکل آخر هم دستورات شرطی بررسی میشن حالا یه مثال هم از فلوچارت با هم میبینیم این فلوچارت مربوط به الگوریتمی هست که 3 عدد رو میگیره و تشخیص میده آیا میتونن تشکیل یک مثلث بدن یا خیر خب حالا که با مفاهیم پایه ای فلوچارت و الگوریتم آشنا شدیم کمی راجع به بحث کارایی الگوریتم صحبت می کنیم .. گاهی برای حل یک مسئله با چند راه حل رو به رو هستیم و در این زمان هست که باید الگوریتم با بیشترین کارآمدی رو انتخاب کنیم . ملاک و معیار کارایی یک الگوریتم هم 2 چیز هست : 1- زمان اجرای الگوریتم 2- میزان حافظه برای اجرا اصطلاحا به اولی پیچیدگی زمانی و به دومی پیچیدگی فضا هم میگن .. به دلایلی معمولا اولی رو بیشتر مورد بررسی قرار میدن و ماهم در ادامه ی آموزش هامون سعی میکنیم بیشتر با این موضوع آشنا بشیم . کپی شده از سایتhttp://ilikephp.ir
  12. ...Ice...

    دوستان طراحی و تحلیل الگوریتم در تاپیکی دیگه توضیح داده میشه
  13. ...Ice...

    1- پیش نیازها برای شروع برنامه نویسی : قبل از شروع به یادگیری کدنویسی ابتدا پیش نیازهای مربوط به برنامه نویسی را خوب یادبگیرید. یک برنامه نویس هنگامی موفق می شود که قدرت تجزیه و تحلیل یک سیستم را داشته باشد. بتواند مسائل را به خوبی حل کند. با مفاهیمی چون طراحی و تحلیل الگوریتم و فلوچارت غریبه نباشد. یک برنامه نویس خوب باید بتواند بهترین الگوریتم و ساختمان داده را برای کد خود طراحی کند. شاید شما بتوانید یک برنامه را با چندین روش بنویسید ولی بهترین روش الگوریتمی ست که فاکتورهایی مانند سرعت، دقت، امنیت و ... را داشته باشد. کپی شده از سایت http://ilikephp.ir/
  14. ...Ice...

    میخوام ده تا نکته بهتون بگم درباره برنامه نویسی.
  15. ...Ice...

    سلاااام. به به میبینم که آموزش برنامه نویسی نیست. آماااااااااا... میخوام براتون آموزش بذارم توپ تپل.نقلو نبات.قندو شیکر.شوکولاتو پشمک... میریم که داشته باشیم آموزش برنامه نویسی رو دنبال کنید این تاپیکو شک نکنید که عاشقش میشید.
×
×
  • جدید...