الگوریتم و داده ساختار
اهمیت طراحی الگوریتمهای کارا، قرنها پیش از ظهور کامپیوترهای الکترونیکی درکشدهبود. قدیمیترین الگوریتم شناختهشده، الگوریتمی است که اقلیدس حدود ۲۴۰۰ سال پیش، برای محاسبهی ب.م.م. دو عدد طبیعی طرح کرد. رایجترین تصویری که از الگوریتم در اذهان وجود دارد، «دستورالعمل و روالی برای حل یک مساله، بهویژه مسایل ریاضی» است. الگوریتم بهگونهای گامبهگام و دقیق، روشی برای حل یک مساله ارایه میدهد. در قرون وسطی الگوریتم به روشهای محاسباتی اطلاق میشد که در آنها اعمال حسابی در دستگاه اعداد هندی-عربی انجام میشد، غیر از این شیوه، تنها شیوهای که در آن زمان برای انجام اعمال حسابی بهکار بستهمیشد استفاده از چرتکه بود. در آن زمان الگوریتمهایی برای حل معادله، جمع، ضرب، تفریق و تقسیم اعداد در دستگاه عددنویسی هندی-عربی وجود داشت. زبانشناسان دورهی رنسانس براین باور بودهاند که الگوریتم از ترکیب دو واژهی لاتین آلگوریس(Algoris) بهمعنی دردناک و آریتموس (Arithmos) بهمعنی عدد ساختهشده است. اما در واقع این واژه برگرفته از نام دانشمند بزرگ ایرانی، ابوجعفر محمدبن موسی خوارزمی است. نوشتههای او از جمله کتاب الجبر و المقابله ابتدا به زبان اسپانیایی و سپس به دیگر زبانهای اروپایی ترجمه شد. در حال حاضر واژهی گواریزمو (Guarismo) در زبان اسپانیایی و آلگاریسمو (Algarismo )در زبان پرتغالی، هر دو به معنی رقم، برگرفته از نام خوارزمی است. با فرایندهای مشابه زبانی، روشهایی که او برای حل مسایل، به ویژه معادلات درجه ۲ بهکار برده بود به نام او خوانده شد. این واژهها از الخوارزمی به الخوریزم، الخوریسم، و الگوریسم (Algorism) تبدیل شد. در دوران رنساس به سبب تصوری که از خویشی این واژه با واژهی آریتموس داشتند، شیوهی نوشتن آن به صورت فعلی، یعنی Algorithm درآمد. این واژه تا اواسط قرن بیستم میلادی جایی در واژهنامههای رسمی زبان انگلیسی نداشت، و در مجامع گوناگون نیز اغلب تنها روش اقلیدس برای محاسبهی ب.م.م را با عنوان الگوریتم میشناختند. با اینهمه به جرات میتوان ادعا نمود که طراحی الگوریتمها، یکی از قدیمیترین مشغولیتهای بشر بودهاست. انسانها همواره در پی یافتن روشهایی بهتر برای دستیابی به اهداف خود بودهاند، خواه این هدف روشن کردن آتش یا جمعآوری یک محصول کشاورزی یا ساخت یک عمارت بزرگ باشد، خواه حل یک مسالهی انتزاعی ریاضی. اما آنچه امروزه به عنوان شاخهای از علوم کامپیوتر شناخته میشود، شکل نوینی از مطالعهی الگوریتمها است. در این حوزه، به دنبال طراحی الگوریتمها و روشهایی برای حل مسایل هستیم که توسط یک کامپیوتر «قابل اجرا» باشند. در واقع هر الگوریتم بایستی خواص زیر را دارا باشد:
- پایانپذیری(Finitness): بایستی ضمانتی وجود داشتهباشد که الگوریتم پس از طی مراحل متناهی به پایان خواهد رسید، و البته یادآوری این نکته خالی از لطف نیست که پایان الگوریتم معادل یافتن پاسخ مساله است.
- خوشتعریفی(Definitness): هر گام از یک الگوریتم بایستی دقیقاً و بدون هیچ ابهامی تعریف شدهباشد.
- داشتن ورودی: هر الگوریتم صفر یا بیشتر ورودی دارد. این ورودیها مشخصات نمونهای از مساله که الگوریتم باید برای آن اجرا شود را در خود دارند.
- داشتن خروجی: هر الگوریتم حداقل یک خروجی دارد.
- کارایی(Effectiveness): مقصود از کارا بودن الگوریتم این است که هرگام آن را بتوان در زمان محدود، و تنها به کمک مداد و کاغذ اجرا نمود.
این پنج مشخصه را میتوان اینگونه خلاصه نمود: الگوریتم مجموعهای پایانپذیر و خوشتعریف از گامهاست که با دنبال نمودن آنها برای هر ورودی مجاز، بتوان خروجی متناسب با آن ورودی را در زمان مناسب بهدستآورد. وظیفهی پژوهشگران این شاخه از علوم کامپیوتر در تعریف فوق و بهویژه در بخش انتهایی آن خلاصهشدهاست. پژوهشگرانِ طراحی الگوریتم همواره بهدنبال طرح الگوریتمهایی کارا برای حل مسایل گوناگون هستند و آنچه در این شاخه از دانش، باعث ارزشمند بودن یک الگوریتم میگردد، کارایی بالا و پیچیدگی اندک آن است. پیچیدگی یک الگوریتم، بههیچوجه پیچیدگی جنبهی انسانی ندارد. منظور از پیچیدگی یک الگوریتم، میزان زمان و حافظهای است که برای حل یک مساله مصرف مینماید. به عنوان نمونه، الگوریتمی را در نظر بگیرید که بهعنوان ورودی لیست نمرات دانشآموزان یک کلاس $n$-نفری را دریافت کرده و آنها را بهترتیب از بالاترین نمره تا پایینترین نمره مرتب مینماید. ورودی این الگوریتم $n$ عدد است که به شکل نامرتب به آن دادهمیشوند، و در خروجی همان اعداد به صورت مرتبشده ظاهر میگردند. اندازهی ورودی این مساله $n$ است. اکنون اگر الگوریتم ما، احتیاج به $n^2$ گام برای حل مساله داشته باشد، پیچیدگی زمانی آن از مرتبهی $n^2$ است و اگر احتیاج به $n$ گام برای حل مساله داشته باشد، پیچیدگی زمانی آن از مرتبهی $n$ است. بدیهی است که در حالت دوم الگوریتم سریعتر به جواب میرسد. متخصصان طراحی الگوریتم در پی آن هستند که الگوریتمهایی طرح نمایند که پیچیدگی زمانی کمتری داشته و سریعتر به پاسخ برسند. در این راستا استراتژیها و روشهای گوناگونی برای طراحی الگوریتم ابداع شدهاند که برخی از آنها خیلی پیش از اینکه کامپیوترها وارد زندگی بشر شوند، وجود داشتهاند و برخی دیگر با پیدایش کامپیوترها و امکانات نوینی که با خود داشتند، شکلگرفتهاند. از آنجایی که الگوریتمها با دادههایی سروکار دارند که در حافظهی کامپیوتر ذخیرهشدهاند، برای این که بتوانند کار خود را به سرعت انجام دهند، نیاز دارند که این دادهها به شیوهای در حافظه چیدهشدهباشند و آرایش یافتهباشند که در کوتاهترین زمان ممکن بتوان آنها را خواند، تغییر داد، حذف کرد یا اضافه نمود. شاخهای از طراحی الگوریتمها که به این موضوع میپردازد، طراحی دادهساختارها نام دارد. حوزهی طراحی الگوریتمها، به عنوان یک شاخهی مهم و بزرگ از علوم کامپیوتر زیرشاخههای متعددی دارد که از جملهی آنها میتوان به تحلیل الگوریتمها، الگوریتمهای گراف و شبکه یا نظریه الگوریتمی گراف، الگوریتمهای تقریبی، الگوریتمهای تصادفی، الگوریتمهای موازی و توزیعشده، الگوریتمهای عددی، محاسبات ماتریسی، نظریهی الگوریتمی بازیها و هندسهی محاسباتی اشاره نمود.