تبلیغات
آموزش رایانه - الگوریتم چیست؟
آموزش رایانه
تفاهم : شامل 3ت (توانایی -تحمل- تفاوتها)
سه شنبه 18 اسفند 1388

الگوریتم چیست؟

سه شنبه 18 اسفند 1388

نوع مطلب :

الگوریتم چیست؟
آموزش الگوریتم نویسی - آموزش مقدماتی

کلمه الگوریتم از نام ریاضیدان برجسته ایرانی, ابو جعفر محمد بن موسی الخوارزمی و به پاس خدمات ارزنده او به توسعه دانش بشری گرفته شده‌است. او اولین کسی است که علم جبر را کشف کرد.
لازم به ذکر است که کلمه الجبرا در انگلیسی نیز برگرفته از روی کتاب مشهور او, الجبر و المقابله‌است. به همین دلیل دانشمندان علم کامپیوتر او را پدر برنامه نویسی نامیده‌اند .

در اینجا دو تعریف را برای الگوریتم بیان می‌كنیم:

 

1- مجموعه‌ای خاص از روال منطقی و یا ریاضی ساده و خوب تبیین شده می‌باشد که می‌تواند در حل یک مسئله مشخص کمک کند. الگوریتم دستورالعملی برای یافتن پاسخ درست یک مساله سخت به وسیله شکستن آن مساله به مراحل ساده و آسان می‌باشد .
۲- هر روال محاسباتی خوش تعریفی است که مقداری, یا مجموعه‌ای از مقادیر را بعنوان ورودی می‌گیرد و مقداری, یا مجموعه‌ای از مقادیر را بعنوان خروجی تولید می‌کند. بنابراین یک الگوریتم یک توالی از گام‌های محاسباتی است که ورودی را به خروجی تبدیل می‌کند.
یک الگوریتم یابد سه شرط اساسی زیر را تأمین کند :
  • لیست دستورالعمل‌ها باید محدود بوده و به اندازه‌ای کوتاه باشد تا قابل اجرا گردد.
  • هر دستورالعمل باید دارای قابلیت اجرا باشد، شما هم باید بتوانید اجرا کارهای یاد شده را به اجرا برسانید.
  • الگوریتم باید روند اجرا را قادر سازد تا در یک نقطه به پایان برسد.

مثلا این جوك معروف را در نظر بگیرید:

می دونی یک فیل را چطوری با سه حرکت می گذارند توی یخچال؟ اول در یخچال را باز می کنند، بعد فیل را می گذارند توش، بعد هم در یخچال را می بندند.

شاید جواب این جك ظاهرا یك الگوریتم باشد، اما اینطور نیست چون ویژگی دوم یعنی قابل اجرا بودن را ندارد.

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

الف) مرتب‌سازی انتخابی

در این الگوریتم در هر مرحله عنصر بزرگتر پیدا می‌شود (اگر مرتب سازی نزولی باشد کوچکترین عنصر) و با یک جابه‌جایی در جای خود قرار می‌گیرد، عمل مقایسه در مرحله اول به اندازه N-1 انجام می‌شود (N تعداد داده‌های موجود است)، و در مرحله دوم به اندازه N-2. به‌همین ترتیب در مرحله iام N-i مقایسه باید انجام شود، در کل n*(n-1)/2 مقایسه باید انجام شود، و در هر مرحله حداکثر 1 جابه‌جایی انجام می‌شود. در بهترین شرایط‌داده‌ها از اول بصورت مرتب شده هستند که در این حالت هیچ جابه‌جایی صورت نمی‌گیرد؛ در بدترین حالت در هر مرحله یک جابه‌جایی داریم و حداکثر n-1 جا‌به‌جایی صورت می‌گیرد. بدین ترتیب مرتبه اجرایی این الگوریتم در بهترین و بدترین شرایط به ترتیب به صورت زیر است:

O(N^2) مقایسه، O(1) جابه‌جایی

O(N^2) مقایسه، O(N) جابه‌جایی

می‌توان اثبات کرد که در مرتب سازی صعودی اگر داده‌ها به‌صورت نزولی مرتب شده باشند، میزان جابه‌جایی همان n*(n-1)/2 است ولی تعداد تعویض‌ها برابر n/2 است.


ب) مرتب‌سازی حبابی

در این الگوریتم چندین بار داده‌های مورد نظر را بررسی می‌کنیم، در هر مرحله هر عنصر با عنصر بعدی مقایسه می‌شود اگر بزرگتر بود، با عنصر بعدی جابه جا می‌شود، در پایان مرحله اول بزرگترین عنصر در آخرین خانه قرار می‌گیرد. در مرحله بعد از خانه صفر تا خانه n-1 بررسی می‌شود و به‌همین ترتیب تا اینکه به اولین عنصر که کوچکترین عنصر است برسیم. در این الگوریتم مانند الگوریتم انتخابی میزان مقایسه‌ها برابر n(n-1)/2 است و تعداد جابه‌جایی‌ها در بهترین حالت زمانی است که داده‌ها مرتب شده باشند و میزان جابه‌جایی برابر صفر می‌گردد، در بدترین شرایط زمانی است که داده‌ها به‌صورت معکوس مرتب شده‌باشند، که برابر n(n-1)/2 است، مرتبه اجرایی این الگوریتم در بهترین و بدترین شرایط به ترتیب به صورت زیر است:

O(N) مقایسه، O(1) جابه‌جایی

O(N^2) مقایسه، O(N^2) جابه‌جایی

ج) مرتب‌سازی خارجی

در این الگوریتم به ترتیب عناصر 0 تا n خوانده شده و عنصر nام در جای درست خود در زیر آرایه از قبل مرتب شده x[0]، x[1]، ... x[n-1] قرار می‌گیرد.

در مرحله اول، عنصر 0ام را در نظر می‌گیریم که بطور بدیهی مرتب است.

در مرحله دوم، عنصر 1ام را با عنصر 0ام مقایسه می‌کنیم و در جای مناسب خود قرار می‌دهیم به‌طوری که عناصر 0ام و 1ام مرتب شده باشند.

در مرحله سوم، عنصر 2ام را با دو عنصر قبلی مقایسه کرده و در جای خود قرار می‌دهیم، به‌طوری که آرایه حاصله مرتب شده باشد. و در مرحله iام، عنصر iام را با کل آرایه. حال از مرحله i-1 مقایسه کرده و در جای خود قرار می‌دهیم به‌طوری که آرایه حاصل مرتب شده باشد.

در این الگوریتم نیز میزان مقایسه مانند دو الگوریتم ذکر شده برابر n*(n-1)/2 است، در بهترین شرایط داده‌ها مرتب شده هستند، که در این حالت تعداد مقایسه‌ها برابر n-1 است و هیچ جابه‌جایی نیز صورت نمی‌پذیرد، مرتبه اجرایی این الگوریتم در بهترین و بدترین شرایط به ترتیب به صورت زیر است:

O(N) مقایسه، O(1) جا به جایی

O(N^2) مقایسه ، O(N^2) جا به جایی

د) مرتب‌سازی ادغامی

اساس این الگوریتم از روش تقسیم و حل برای مرتب سازی استفاده می‌کند، در این روش مساله به چند مساله کوچکتر تقسیم می‌شود، و با حل هر کدام از این مساله‌های کوچک و ترکیب آنها با هم مساله اصلی حل می‌شود. پس می‌توان پی‌برد که بخشی از این الگوریتم بصورت بازگشتی پیاده‌سازی می‌شود، نکته‌ای که قبل از توضیح روش کار باید در نظر گرفت بحث ترکیب است، در این الگوریتم حاصل هر مرحله با حاصل‌های دیگر باید ترکیب شده تا نتیجه درست حاصل شود. در این بحث از توضیح این الگوریتم صرف نظر می‌کنیم ولی این الگوریتم برای دو آرایه x[s,m] و y[m+1,n] از مرتبه O(n-s+1) است که n-s+1 تعداد عناصری هستند که با هم ترکیب شده‌اند.

شرح الگوریتم

در مرحله اول داده‌ها به N آرایه 1 عضوی تقسیم می‌شوند و سپس عناصر دو به دو با هم ادغام می‌شوند تا n/2 آرایه دو عضوی حاصل شود (اگر n عددی فرد باشد یک آرایه تک عضوی پدید می‌آید)، سپس این n/2 آرایه را دو به دو با هم ترکیب کرده تا به یک لیست n عضوی مرتب برسیم، از این رو به حداکثر Log n مرحله جهت مرتب‌کردن آرایه نیاز دارد، مرتبه اجرایی این الگوریتم همواره O(n*Log n) است، معمولا از این الگوریتم برای فایل‌ها استفاده می‌کنند.

A-Sorting-1

ح) مرتب‌سازی درختی

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

درج هر داده در درخت BST به مدت O(Log N) انجام می‌پذیرد و درج n داده O(n*Log n) انجام می‌گیرد پیمایش inorder درخت جستجوی دودویی باعث نمایش لیست مرتب شده بصورت صعودی می‌شود.

بدترین وضیعت در درخت جستجوی دودویی زمانی است که داده‌های ورودی به‌صورت مرتب شده باشند (چه صعودی چه نزولی)، که درخت حاصل بصورت اریب ظاهر می‌شود در این حال اگر داده‌های تکراری نباشند برای درج n(n-1)/2 مقایسه باید انجام شود و مرتبه زمانی درج داده ها بصورت O(N2) است.

بهترین حالت برای این الگوریتم زمانی است که داده ها نا مرتب بوده، که عمق درخت در حال متوازن (Log(n,2 قرار گیرد، در نتیجه زمان درج n داده همانطور که گفته شد برابر O(nLog n) است و زمان مرتب سازی برابر O(n*Log(n,2)) است.




فرزاد
چهارشنبه 26 مهر 1391 12:59 ق.ظ
منابعی كه بتوان دررابطه با الگوریتم بیشتر آشنا شد را معرفی نمایید 0باتشكر
عکاسباشی
یکشنبه 25 دی 1390 10:03 ق.ظ
سلام
من فقط از تعریف الگوریتم استفاده کردم از بقیش سر در نیاوردم
رشته خیلی سختی دارید
فرهاد
دوشنبه 27 دی 1389 09:18 ب.ظ
salam
khaste nabashin
didam kasi nazar nadade goftam ye nazar bedam !
jedan kare khobi kardin babate amozesh ama bishtar bayad talash konin
ama tarhe khobie
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر