الگوریتم ها و پیچیدگی ها

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

یک مفهوم همراه ، طراحی یک ساختار داده خاص است که یک الگوریتم را قادر می سازد تا به طور کارآمد اجرا شود. اهمیت ساختار داده ها از این واقعیت ناشی می شود که حافظه اصلی یک رایانه (جایی که داده ها ذخیره می شوند) خطی است ، متشکل از دنباله ای از سلولهای حافظه که به صورت سریال 0 ، 1 ، 2 ،…بنابراین ، ساده ترین ساختار داده یک آرایه خطی است ، که در آن عناصر مجاور با "فهرست" عدد صحیح متوالی شماره گذاری می شوند و به یک شاخص منحصر به فرد آن به مقدار یک عنصر دسترسی پیدا می کند. به عنوان مثال می توان از آرایه ای استفاده کرد تا لیستی از نام ها را ذخیره کند و روشهای کارآمد برای جستجوی کارآمد و بازیابی نام خاص از آرایه مورد نیاز است. به عنوان مثال ، مرتب سازی لیست در سفارش الفبایی اجازه می دهد تا به اصطلاح تکنیک جستجوی باینری مورد استفاده قرار گیرد ، که در آن باقیمانده لیست در هر مرحله جستجو می شود به نصف. این تکنیک جستجو شبیه به جستجوی کتاب تلفنی برای یک نام خاص است. دانستن اینکه این کتاب به ترتیب حروف الفبا است ، به فرد اجازه می دهد تا به سرعت به صفحه نزدیک به صفحه حاوی نام مورد نظر تبدیل شود. بسیاری از الگوریتم ها برای مرتب سازی و جستجوی لیست داده ها به طور کارآمد تهیه شده اند.

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

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

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

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

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