آموزش ساختمان داده (داده ساختار ها و مبانی الگوریتم ها)

  • نویسنده موضوع Ali
  • تاریخ شروع

Ali

مدیریت کل
پرسنل مدیریت
"مدیر کل"
با درود
این نوشتار کاملا اختصاصی هست، نویسنده و مترجم اینجانب (Ali) هستم...
کپی برداری حتی با ذکر منبع غیر مجاز است.

آموزش از ترجمه کتاب و مرجع اصلی قدرتمند INTRODUCTION TO ALGORITHMS (معرفی ، آشنایی با الگوریتم ها) ورژن (نسخه) 3.
نویسندگان:
Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein

الگوریتم مجموعه ای از ارزش ها و راهکار های با ارزش محاسباتی برای خروجی است. الگوریتم در نتیجه دنباله از گام های محاسباتی از طریق ورودی است.


ما الگوریتم را مانند یک ابزار برای حل کردن مشکل محاسباتی تعریف میکنیم. الگوریتم، راجع به رویه خروجی و ورودی و ارتباط خاص آن ها توضیح میدهد.


برای مثال، ما باید یک نمونه دنباله ی عددی نامرتب را مرتب نماییم.

این مشکل غالبا در تمرین و تهیه ی عملی مطرح می شود و زمینه ای مناسب را برای معرفی طرح های استاندارد، ارائه می کند.

اینجا چگونگی تعیین مشکل "مرتب سازی" را تببین میکنیم.



ورودی: دنباله ای از n عدد (a1,a2,...,an)
خروجی: (مرتب سازی مجدد با جایگشت) (a'1,a'2,...,a'n)
از ورودی نمونه ها
مثل
a'1<a'2<...<a'n


سعی کردم ترجمه رو راحت بیان کنم برای همین شاید تکرار زیاد داشته باشه اگر غلط داشت حتما بگید ...
ادامه داره.
 

Ali

مدیریت کل
پرسنل مدیریت
"مدیر کل"
برای مثال، یک سری ورودی عددی 31,41,59,26,41,58 داریم، الگوریتم مرتب سازی در خروجی اعداد را بصورت 26,31,41,41,58,59 بر میگرداند.
چننی ورودی دنباله ای یک مثال از سوال و طرح مرتب سازی است

ولی در عموم، یک نمونه از مسأله شامل ورودی است که نیازمند محاسبه حل مشکل است.

زیرا بسیاری از برنامه ها آن را بصورت یک مرحله ی مداخله جو استفاده میکنند، مرتب سازی یک مرحله بنیادی در علوم کامپیوتریست.

بعنوان یک نتیجه، ما یک عدد بزرگ از الگوریتمی خب در اختیارمان داریم. که الگوریتم ها به برنامه ای که داریم و تعداد عدد هایی که باید ذخیره نماییم بستگی دارند.

وسعت و اندازه ی اینکه موارد ذخیره شده چقدر هستند، به ارزش آنها می باشد.( یعنی شیوه ی ذخیره سازی یا ابزار ما) یعنی سبک معماری کامپیوتر (ساختمان داده) و انواعی از ذخیره سازی ابزار ها مثل حافظه های اصلی ، دیسک ها، نوار ها و .. .

یک الگوریتم را در صورت صحیح گوییم که برای هر ورودی و توقف آن برای خروج مناسب دهد. در این صورت آن را یک الگوریتم حل شده ی محاسباتی گوییم. (یعنی با عملیات ریاضی آن را اثبات کنیم!)

ادامه دارد ...
 

Ali

مدیریت کل
پرسنل مدیریت
"مدیر کل"
یک الگوریتم غلط شاید با ورودی های متفاوت همیشه جواب ندهد یا اینکه جواب های نادرست بدهد.

بر خلاف چیزی که شما انتظار دارید، الگوریتم های اشتباه می توانند مفید و کاربردی باشند، اگر بتوانیم خطاهای آن ها را ارزیابی کنیم.

ما بایستی یک مثال از یک الگوریتم با یک کنترل کننده ی ارزیابی خطاها (که در آینده الگوریتم هایی برای اعداد بزرگ اول خواهید دید) را ببینیم.

در حالت عادی، در هر حال بایستی فقط درگیر الگوریتم های درست و صحیح باشیم.

یک الگوریتم می تواند در انگلیسی مشخص شده باشد، مثل یک برنامه کامپیوتری یا حتی طراحی یک سخت افزار یا ابزار ، این فقط نیاز به تهیه خصوصیات و مشخصات و شرح دقیق و مفید از رویه محاسباتی به دنبال دارد.

- انواع مسائلی که با الگوریتم حل می شوند، کدامند؟
مرتب سازی فقط با یک مسأله ی محاسباتی صرفا ریاضی توسعه نیافته است. (شاید شما به همان اندازه مشکوکید که به اندازه یک کتاب دیده باشید!!)
برنامه های کاربردی از الگوریتم ها در همه جا شامل این مثال های بزرگ می شود:


  • پروژه های ژنتیکی انسان با اهداف شناخت 100,000 ژن در dna انسان پیشرفت های خوب و رو به جلویی داشته است. تعیین و تعریف دنباله ی عددی 3 بیلیون جفت پایه شیمیایی (یک اصطلاح در علوم ژنتیکی) که dna انسان می تواند تشکیل دهد، می باشد. طبقه بندی و مرتب سازی این اطلاعات در پایگاه های داده و توسعه دادن برای آنالیز آن ها هر کدام یک الگوریتم مشکل و پیچیده ای را نیاز دارند.



  • اینترنت ، کار مردم جهان را برای دسترسی سریع و بازیابی مقدار بسیار زیادی از اطلاعات ساده کرده و این توانایی را دارد . با کمک یک الگوریتم بسیار هوشمندانه سایت ها روی اینترنت قادر هستند با یک مهارت خاص این حجم عظیم اطلاعات را مدیریت کنند. نمونه هایی از مسائل وجود دارد که برای استفاده از الگوریتم که شامل جستجوی راه های مناسب برای گردش اطلاعات ساخته شده است. یا به کار گیری موتورهای جستجو که برای یافتن صفحات دارای اطلاعات ویژه و خاص و معین استفاده شود.



  • تجارت الکترونیکی کالا ها و خدمات را قادر کرد که بصورت الکترونیکی رد و بدل شده و مذاکره کنند. این بستگی به اطلاعات خصوصی و شخصی فرد مثل کارت های اعتباری ، رمز ها و اظهارنامه های بانکی دارد. هسته ی تکنولوژی ها در تجارت الکترونیکی شامل کلید های عمومی رمزنگاری شده و امضاهای دیجیتالی می باشد. که روی یک الگوریتم شمارشی و نظریه ی عددی مستقر است.

ادامه دارد ...
 

Ali

مدیریت کل
پرسنل مدیریت
"مدیر کل"
  • ساخت و سرمایه گذاری تجاری اغلب به یک منبع سهمیه ی نادر در بهترین راه را دارد، یک کمپانی مواد نفتی باید بداند که بهترین مکان برا قرار گیری چاه هایش با حداکثر سودی که مورد انتظارش است کجاست. یک نامزد انتخاباتی (سیاسی) می خواهد باید بداند که پول خود را برای صرف کردن امور تبلیغات انتخاباتی در کجا بالاترین شانس برنده شدن را در رأی گیری دارد. یک شرکت هواپیمایی باید بداند که خدمه ی پروازی اش در کجا حداقل هزینه را دارند و هم چنین در هر پروازش به دولت و برنامه هایی که ریخته مربوط است مطمئن باشد. یک سرویس دهنده ی اینترنت (ISP) باید بداند و تخمین بزند که چه جایی وسیله و ابزار اضافی برای استفاده ی مشتری هایش مؤثر تر است و ...

تمام این موارد می تواند در برنامه نویسی خطی استفاده و حل شود. گرچه بسیاری از جزئیات این مثال ها در حد این کتاب نمی باشد. ما شیوه های اساسی بکار بردن این مسائل را شرح می دهیم. هم چنین نشان می دهیم که چگونه بسیاری از مسائل مخصوص، حل می شوند، که شامل موارد زیر است:


  • ما یک نقشه راه معین داریم که فاصله بین هر جفت چهار راه مجاور مشخص شده است، می خواهیم کوتاه ترین مسیر از یک چهار راه (تقاطع) به دیگر چهار راه ها را تعیین کنیم. تعداد مسیرهای احتمالی قطعا عدد بسیار بزرگی خواهد بود. حتی اگر ما برای آن گردش های ممنوعه (محدودیت های ترافیکی) را قائل نشویم. چگونه می توانیم از همه راه های ممکن کوتاه ترین را انتخاب کنیم؟ این مسئله با گراف قابل حل خواهد بود.



  • ما 2 دسته سری عدد مرتب شده شامل و را داریم. حال می خواهیم طولانی ترین دنباله ی مشترک (اشتراک بین دو مجموعه) از X و Y را پیدا کنیم. یک دنباله از X تنها X با تعدادی (شاید همه یا هیچ کدام!) از اعضایی که حذف شده است. برای مثال، یک دنباله از {A,B,C,D,E,F,G} می تواند {B,C,E,G} باشد.

این مسئله ادامه دارد ...
 

Ali

مدیریت کل
پرسنل مدیریت
"مدیر کل"
  • طول بلندترین دنباله مشترک از X و Y یک میزان می دهد که چقدر این دو دنباله به هم مشابهت دارند. برای مثال اگر 2 دنباله (سری) جفت رشته اصلی DNA باشند، پس اگر آن ها یک اشتراک دنباله ای طولانی دارند، ما باید شباهت های آنها را ملاحظه کنیم. اگر X دارای m رقم، Y دارای n رقم باشند، پس X , Y به ترتیب دو به توان m و دو به توان n دنباله ممکن است داشته باشند. انتخاب کردن همه دنباله های X , Y و تطابق دادن آن ها می تواند یک عامل بازدارنده، برای m و n که کوچک هم هستند باشند، چون زمان بسیار زیاد و بی استفاده ای می برد.


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

ادامه دارد.
 

Ali

مدیریت کل
پرسنل مدیریت
"مدیر کل"
ساختار داده ها (ساختمان داده)

این کتاب شامل چندین داده ساختار است. ساختمان داده یک راه حل برای ذخیره و ساماندهی اطلاعات و هم چنین آسانتر کردن دسترسی و تغییر داده است.

شیوه

اگرچه شما این کتاب را مثل یک کتاب آشپزی برای الگوریتم هایتان استفاده کنید. ولی شما یک روزی با یک مسأله (مشکل) مواجه شوید که نمیتوانید سریعاً برایش یک الگوریتم پیدا کنید.

این کتاب به شما شیوه های طراحی و آنالیز الگوریتم ها را که می توانید الگوریتم هایی برای خودتان گسترش دهید، آموزش میدهد. می توان نشان داد که آنها جواب صحیح می دهند و بازده ی آن ها را نیز بفهمید.

مسأله های np (غیر قابل حل):

بیشتر این کتاب در مورد الگوریتم های کار آمد است.

معمولا ما با اندازه گیری سرعت، کارآمدی را انجام میدهیم، یعنی چقدر زمان صرف شود که یک الگوریتم بتواند نتیجه را تولید کند. مشکلات متعددی موجود است و. گرچه برای هرکدام نیز راهل حل شناخته شده ای نیست!

یک زیر مجموعه جالب از این مسائل و مشکلات، مسائل np هستند.

چرا مسائل np جالبند؟


اولا هرچند هیچ الگوریتم کار آمدی برای مسائل np پیدا نشده است هیچ کس هم هنوز نتوانسته اثبات کند که آن الگوریتم یک راه حل کار آمد دارد و آن نیز وجود دارد!
بعبارت دیگر، هیچ کس یک جواب کارآمدی برای حل مشکلات مسائل np نمیشناسد!

ثانیا در ادامه ...
 

Ali

مدیریت کل
پرسنل مدیریت
"مدیر کل"
ثانیاً: دسته ای از مسائل np دارای خاصیت قابل توجهی هستند که اگر برای آن ها یک الگوریتم کار آمد وجود داشته باشد، پس برای همه آن الگوریتم ها هم وجود دارد.

این ارتباط بین مسائل np باعث می شود که به حل مسائل بیشتر امیدوار بود.

ثالثا: بسیاری از مسائل np شبیه به هم هستند، اما با مسائلی که الگوریتم کار آمد آن ها را می دانیم دقیقا مساوی نیستند! (تکراری نیستند)

دانشمندان کامپیوتر با فریفتن (دسیسه!) ، درصدد این که چگونه با یک تغییر کوچک در توضیح یک سوال (اضافه کردن فرضیات مسأله) بتوانند باعث یک تغییر بزرگ برای بازده زیاد در بهترین الگوریتم شناخته شده باشند، هستند.

شما باید مسائل np را تا حدودی بشناسید، زیرا تعجب شما ناشی از استفاده های واقعی آن ها در بعضی مواقع و موارد بوده است. اگر شما به محض ساخت یک الگوریتم، به مسأله ی np رسیدید (فرخوانده شدید!)، احتمالا باید مقدار بسیار زیادی از زمان خود را برای جستجو، بی ثمر بگذرانید.

اگر شما توانستید نشان دهید که یک مسأله از نوع np (غیر قابل حل!) است، می توانید در عوض زمان خود را به توسعه دادن الگوریتم کار آمد به خوبی بگذرانید (بدهید!) ، اما این، بهترین احتمال، و امکان شدنی نیست.

الگوریتم مثل یک تکنولوژی (فناوری)

ادامه دارد ...
 

Ali

مدیریت کل
پرسنل مدیریت
"مدیر کل"
الگوریتم و تکنولوژی

فرض کنید کامپیوتر ها از لحاظ سرعت نامحدود بودند و حافظه آن ها نیز خالی بود. آیا دلیلی دارید که الگوریتم ها را مطالعه کنید ؟

جواب بله است، زیرا اگر این هم نبود، (این دلیل!) شما باید متد و روش خودتان را با اثبات نشان میدادید!

اگر کامپیوتر ها بی نهایت سریع و آزاد بودند، هر پاسخ و روشی را برای مسأله که میخواستید انجام می دادید. احتمالا شاید در نرم افزار های تمرین های مهندسی این محدودیت ها را دیده اید.

البته، کامپیوتر سریع هست (باید خیلی سریع باشد!) ولی بی نهایت سریع نیست.

و مموری (حافظه) بصرفه و ارزان هست ولی آزاد نیست.

محاسبه زمان، به منظور یک وسیله با حد و مرز است. بنابراین با حافظه دخیل هستند.

شما این وسیله را عاقلانه بکار ببرید، و این الگوریتم ها به شما زمان کافی و حافظه کافی را کمک خواهند کرد.

بازده

یک مثال، ما 2 الگوریتم برای مرتب سازی دیده ایم.

1) مرتب سازی درجی: که این الگوریتم زمانی معادل را برای مرتب سازی n مورد می برد. در اینجا، C[SUB]1 [/SUB]یک عدد ثابت است و به n بستگی ندارد. پس این زمانی معادل n[SUP]2 [/SUP]را می گیرد.
2) مرتب سازی ترکیبی (ادغامی): که زمانی حدود میگیرد. جایی که lg n است، منظور log[SUB]2[/SUB] n می باشد. و هم چنین C[SUB]2[/SUB] نیز ثابت است و به n بستگی ندارد.

Sort درجی صریحاً عامل کوچکتری از Sort ادغامی دارد. پس C[SUB]1[/SUB]<C[SUB]2[/SUB] . ما باید ببینیم که عوامل مستقیم می توانند بسیار کمتر تأثیر مداوم روی زمان بگذراند. البته این به مقدار ورودی و سایز آن نیز بستگی دارد.

ادامه دارد...
 

Ali

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

هم چنین زبان بحث شده در این مبحث بنده، ++C هست ولی ممکن است از شبه کد ها استفاده کنیم که
برای زبان های مختلفی از جمله C, C++, Java, Python, Pascal نیز کاربرد دارد. (یعنی اگر با این زبان ها آشنا باشید، می توانید مراحل برنامه نویسی را داشته باشید)​
 

Ali

مدیریت کل
پرسنل مدیریت
"مدیر کل"
اجازه دهید، زمان اجرای sort درجی ، ادغامی را بنویسیم.
اجرای برنامه insertion sort را اگر بصورت C[SUB]1[/SUB]n.n و merge sort بصورت C[SUB]2[/SUB]n.lg n باشد، می بینید که روش ادغامی خیلی کوچکتر از روش درجی است.
(مثلا برای n=1000، روش ادغامی lg 1000 = 10 است و یا برای یک میلیون lg 1,000,000 = 20 می باشد.
گر چه معمولاً روش درجی برای مقادیر کوچکتر، زودتر از مرتب سازی ادغامی اجرا می شود. تا وقتی که سایز عدد n به حد کافی بزرگ شود، روش ادغامی (در شرایط یکسان) نسبت به درجی، برتر خوهد بود.
این که C[SUB]1[/SUB] < C[SUB]2 [/SUB]اهمیتی ندارد.
برای مثال، اجازه بدید یک کامپیوتر بسیار سریع به نام A، مرتب سازی insertion اجرا شود , بر خلاف آن در کامپیوتر B آرامتر باشد و مرتب سازی ادغامی صورت گیرد. این دو باید یک آرایه ی 10 میلیون عددی را مرتب کنند.

(اگر چه 10 میلیون عدد به نظر بسیار زیاد می رسد اگر عدد ها 8 باید از نوع صحیح (int) باشند ، 80 مگابایت را اشغال می کنند)
فرض کنیم کامپیوتر A، ده بیلیون دستور بر ثانیه را اجرا می کند و کامپیوتر B ، ده میلیون دستور بر ثانیه را اجرا می کند. پس در هر سطر کامپیوتر A، هزار برابر 10 میلیون سریع تر و قدرتمند تر از کامپیوتر B است.
ادامه دارد.
 
بالا