دسته بندي: تحقیق و پروژه رایگان,پروژه و تحقیق رایگان,دانش آموزی,تحقیق دانشجویی,

مهندسی کامپیوتر

هدف:
رشته مهندسي كامپيوتر كه به طراحي و ساخت اجزاي مختلف كامپيوتر مي پردازد، لذا اهميت بسيار زيادي در دنياي امروز برخوردار است. هدف از طي اين دوره تربيت كارشناساني است كه در زمينه تحليل، طراحي، ساخت و راه اندازي دستگاهها و مجموعه هاي سخت افزاري جديد، بررسي و شناخت مجموعه هاي سخت افزاري و نرم افزاري موجود، نگه داري، عيب يابي و تعمير و اصلاح و توسعه فعاليت كنند.
طراحي، شبيه سازي، فرآوري، پردازش، سنجش، آموزش، ويرايش و ... همه مفاهيمي هستند كه با بالاترين دقت و در كوتاهترين مدت زمان ممكن در برنامه هاي نرم افزاري كامپيوتر انجام مي شوند. لذا هدف از اين رشته تربيت نيروي متخصص براي انجام امور فوق است.
تواناييهاي فارغ التحصيلان
فارغ التحصيلان اين مقطع، قابليتها و تواناييهاي زيادي دارند و چنانچه در مسير مناسب هدايت شوند، قادر خواهد بود مشكلات زيادي را حل كنند. برخي از اين تواناييها به شرح زير است:
1) بررسي و شناخت نرم افزارها و سخت افزارهاي جديد و به كارگيري آنها.
2) بررسي كمبودها و نيازهاي نرم افزاري و سخت افزاري بخشهاي صنعت و خدمات و تدوين نيازهاي آنها، امكان سنجي و تعيين ابزار و نيروي انساني لازم براي رفع كمبودها.
3) تجزيه و تحليل سيستمهاي كوچك و متوسط نرم افزاري و سخت افزاري و ارائه راه حل مناسب براي اجراي آنها.
4) طراحي مجموعه هاي كوچك و متوسط نرم افزاري و سخت افزراي و توليد طرحهاي اجرايي براي انها.
5) اجراي طرحهاي كامپيوتري، نصب، آزمايش و آموزش آنها.
6) پشتيباني و نگه داري سيستمهاي نرم افزاري شامل شناسايي خطاها، رفع خطاها و افزودن امكانات جديد به سيستمها.
7) عيب يابي كامپيوترها و سيستمهاي كامپيوتري و رفع عيبها.
8) شناسايي فنون جديد طراحي و ساخت كامپيوتر و ارزيابي و به كارگيري آنها.
تواناييهاي ذكر شده مربوط به كارشناسان نرم افزار و سخت افزار مي باشد، اما روشن است كه كارشناسان نرم افزار در محدوده مسائل نرم افزاري توانايي بيشتري دارند و برعكس كارشناسان سخت افزار در محدوده مسائل سخت افزاري از توانايي بيشتري برخوردارند.

ماهيت:
كامپيوتر داراي دو جزء متفاوت سخت افزار و نرم افزار است. اجزاء فيزيكي و قابل لمس كامپيوتر مانند مدارها و بردهاي الكترونيكي سخت افزار ناميده مي شوند.
نرم افزار جزء غيرقابل لمس كامپيوتر است. نرم افزار برنامه ها و داده هايي است كه به كامپيوتر فرمان مي دهند كه چه عملي را انجام دهد. يك مهندس نرم افزار ياد مي گيرد كه چگونه نرم افزارهاي بزرگ و عظيم را طراحي و برنامه ريزي كند، تست و ارزيابي نهايي نمايد و در نهايت مستند سازد.
پس بدين گونه نسبت كه يك تعميركار كامپيوتري يك مهندس سخت افزار و يك اپراتور كامپيوتر يك مهندس نرم افزار تلقي گردد.
"نرم افزار در حقيقت روح و جان كامپيوتر است كه به سخت افزار هويت مي بخشد و اصولاً به برنامه اي گفته مي شود كه براي به كارگيري سخت افزار ساخته شده باشد.
نرم افزارها را مي توان به دوره كلي دسته بندي كرد كه عبارتند از : نرم افزارهاي سيستمي و نرم افزارهاي كاربردي.
نرم افزراهاي سيستمي برنامه هايي هستند كه كامپيوتر براي فعال شدن يا سرويس دادن به آن نياز دارد و اين دليل از سوي سازندگان سيستم كامپيوتري عرضه مي شوند و مهمترين آنها سيستم عامل، برنامه هاي سودمند و مترجم هاي زبان مي باشد.
نرم افزارهاي كاربردي نيز برنامه هايي هستند كه كاربر يا خود آن ها را مي نويسد يا شركت هاي نرم افزاري آنها را تهيه كرده و براي فروش عرضه مي كنند. اين گونه برنامه ها معمولاً عموميت برنامه هاي سيستم را نداشته و براي زمينه هاي مختلف مهندسي، علمي، تجاري، آموزشي، تفريحي و يا طراحي نوشته مي شوند."
"مهندسي سخت افزار در مقطع ليسانس به مطالعه و بررسي طراحي سخت افزاري، كنترل سخت افزاري و شبكه هاي كامپيوتري مي پردازد. براي مثال يك مهندس سخت افزار مي تواند طراحي سخت افزاري كند كه با IC ها كار كند، با كامپيوتر كار كند و يا از دروازه هاي كامپيوتر استفاده نمايد و در نهايت مي تواند به طراحي مدارهاي مجتمع ديجيتالي بپردازد. كه البته به اين بخش از سخت افزار بيشتر در مقطع كارشناسي ارشد و دكتري پرداخته مي شود."
گرايش هاي مقطع ليسانس:
رشته مهندسي كامپيوتر در مقطع كارشناسي داراي دو گرايش سخت افزار و نرم افزار است كه البته اين دو گرايش در مقطع كارشناسي تفاوت قابل توجهي با يكديگر ندارند.
"گرايش سخت افزار در برگيرنده فعاليت هاي آموزشي، پژوهشي و صنعتي در خصوص قطعات، بردها، تجهيزات و در نهايت سيستم هاي كامپيوتري در مقياس هاي مختلف است و يكي از شاخه هاي مهم آن به نام معماري كامپيوتر (طراحي و ساخت كامپيوتر) مي باشد."
"هدف از گرايش نرم افزار كامپيوتر، آموزش و پژوهش در زمينه زبانهاي مختلف برنامه نويسي، سيستم هاي عامل مختلف و طراحي انواع الگوريتم ها مي باشد."
آينده شغلي، بازار كار، درآمد:
با توجه به گسترش روزافزون دنياي كامپيوتر امروزه بيش از هر زمان ديگري نياز به متخصصان كامپيوتر احساس مي شود. امروزه يك مهندس كامپيوتر اگر علاقمند به كار باشد، هيچ وقت با مشكل بيكاري روبه رو نمي شود. به خصوص مهندسين نرم افزار فرصت هاي شغلي بيشتري داشته و براي كاركردن نياز به امكانات و تجهيزات زيادي ندارند. فرصت هاي شغلي اين رشته به حدي گسترده و متعدد است كه نه تنها فارغ التحصيلان اين رشته به راحتي جذب بازار كار مي شوند بلكه دانشجويان دو سال آخر اين رشته نيز مي توانند وارد بازار كار شده و فعاليت كنند. براي مهندسين سخت افزار هم امكان كار در شركتهاي توليد كننده قطعات و دستگاهها و مراكز صنعتي – توليدي بسيار فراهم است و از نظر سطح درآمدي هم با توجه به دانش و پشتكار شخصي در حد قابل قبول و ايده آلي قرار دارند. از طرفي با توجه به استفاده روزافزون از شبكه اينترنت زمينه كار در اين موضوع نيز بسيار مهياست.
توانايي هاي جسمي، علمي، رواني و ... مورد نياز و قابل توصيه
توانايي علمي: يك مهندس كامپيوتر بايد سخت كوش و با پشتكار باشد چون رشته كامپيوتر رشته پويايي است و هميشه بايد اطلاعاتش به روز بوده و به دنبال فراگرفتن مطالب جديد باشد. مهندس كامپيوتر بايد پايه رياضي قوي داشته و توانايي اش در زمينه فيزيك خوب باشد. همچنين لازم است فردي خلاق باشد تا بتواند مسايل را از راههاي ابتكاري حل كند.
علاقمنديها: مهندس كامپيوتر نرم افزار و سخت افزار بايد به يادگيري و مطالعه علاقمند باشد تا پيشرفت در خور توجه داشته باشد. همچنين بايد از جستجو و كاوش در مدارها و ريزساختارها استقبال كند و به كار با كامپيوتر علاقه داشته باشد.
توانايي مالي: با توجه به توضيحات گفته شده داشتن يك دستگاه كامپيوتر براي يك مهندس كامپيوتر امري ضروري به نظر مي رسد ولي اين گونه نيست كه بدون داشتن كامپيوتر دانشجويان از ادامه تحصيل و پيشرفت باز بمانند.
وضعيت نياز كشور به اين رشته در حال حاضر:
رشته كامپيوتر كه باعث جهاني شدن اطلاعات و ارتباطات شده است ، رشته روز و رشته آينده است تا جايي كه پيش بيني مي شود تا 10 سال ديگر در كشورهاي پيشرفته مردم همان قدر كه بر نيروي برق وابسته هستند به شبكه اينترنت وابسته خواهند شد. با توجه به توضيحات گفته شده روند رو به رشد استفاده از كامپيوتر در زندگي روزانه اشتغال و موقعيت كاري براي فارغ التحصيلان اين رشته فراهم است تا در قالب شركتهاي توليدكننده نرم افزار، شركتهاي توليدكننده قطعات، مراكز صنعتي – توليدي، شركتها و موسسات خدماتي، مراكز آموزشي و ... مشغول به كار شده و فعاليت كنند. با توجه به پيشرفت كند ايران نسبت به جامعه جهاني كامپيوتر در سالهاي اخير نياز به مهندسين خلاق و كوشا در اين زمينه كاملاً احساس مي شود.
روند رو به رشد استفاده از كامپيوتر در محافل عمومي و خصوصي، استفاده گسترده از شبكه اينترنت و زمينه هاي مرتبط با آن، فراهم آمدن شرايط آموزش و تجارت الكترونيك همه و همه دست به دست هم داده اند تا از اكنون چشم انداز روشني نسبت به آينده اين رشته وجود داشته باشد به نحوي كه فعالان در اين زمينه از آينده معلوم و مطمئني برخوردار خواهند بود. تنها نگراني به قسمت نرم افزار مربوط مي شود كه بايد مهندسان خلاق ايراني اقدام به تهيه نرم افزارهاي گوناگون و كارآمد كرده تا تنها مصرف كننده صرف نباشيم.

نكات تكميلي:
"بعضي از افراد تصور مي كنند كه مهندسي سخت افزار در حد يك تعميركار كامپيوتر است در حالي كه كار يك مهندس سخت افزار، تعمير يا نصب و راه اندازي كامپيوتر نيست. هر چند كه مي تواند چنين كاري را انجام دهد. در واقع كار يك مهندس سخت افزار، طراحي هاي سخت افزاري است و به همين دليل در دانشگاه دروسي مثل رياضيات و يا مدارهاي منطقي را مطالعه مي كند همچنين برخلاف تصور كساني كه يك اپراتور را در حد يك مهندس نرم افزار مي دانند، بايد گفت كه يك مهندس نرم افزار لازم است از دانش رياضي خوبي برخوردار باشد تا بتواند برنامه هاي كامپيوتري را طراحي كند و آنها را توسعه دهد. براي مثال بايد بتواند يك كار گرافيكي را از بنيان طراحي كند. كاري كه از عهده يك اپراتور بر نمي آيد. و به همين دليل ما معتقديم كه كلاسهاي آزاد آموزش كامپيوتر هيچ وقت نمي توانند يك مهندس كامپيوتر پرورش دهند.

ریاضیات

نظریه گراف

نمایش تصویری یک گراف

نظریه گراف شاخه ای از ریاضیات است که درباره اشیاء خاصی در ریاضی به نام گراف بحث می‌کند. به صورت شهودی گراف نمودار یا دیاگرامی است شامل تعدادی رأس که با یالهایی به هم وصل شده‌اند. تعریف دقیق‌تر گراف به این صورت است که گراف مجموعه‌ای از رأس‌ها است که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم مربوط شده‌اند.

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

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. اویلر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پل‌های کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم داده‌ورزی (انفورماتیک) بوده است.

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

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

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

نظریه محاسبات

نظریه محاسبه‌پذیری

نظریه محاسبه‌پذیری از مباحث پایه در علوم رایانه است که به بررسی محاسبه‌پذیر و محاسبه‌ناپذیر بودن عملیات با استفاده از ابزارهای کلاسیک نظیر ماشین ثبات، ماشین تورینگ و توابع بازگشتی میپردازد.

پیچیدگی محاسباتی

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

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

بعضی منابع دیگری که در این نظریه مورد بررسی قرار می‌گیرند، مثل عدم تعین صرفا جنبه‌ی صوری دارند ولی بررسی آن‌ها موجب درک عمیق‌تر منابع واقعی مثل زمان و فضا می‌شود.

معروف‌ترین کلاس‌های پیچیدگی، P و NP هستند که مساله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طور شهودی می‌توان گفت P کلاس مساله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما NP شامل آن دسته از مساله‌هاست که اگرچه ممکن است پیدا کردن جواب ‌برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیله‌ٔ یک الگوریتم سریع ممکن است. البته کلاس‌هاي پيچيدگي به مرتبه سخت‌تري از NP نيز وجود دارند.

· PSPACE: مسائلي که با اختصاص دادن مقدار کافي حافظه (که اين مقدار حافظه معمولا تابعي از اندازه مساله مي‌باشد) بدون در نظر گرفتن زمان مورد نياز به حل آن، مي‌توانند حل شوند.

· EXPTIME: مسائلي که زمان مورد نياز براي حل آنها به صورت تواني مي‌باشد. مسائل اين کلاس بسيار جذاب و سرگرم کننده مي‌باشند (حداقل براي ما!). و شامل همه مسائل سه کلاس بالايي نيز مي‌باشد. نکته جالب و قابل توجه اين مي‌باشد که حتي اين کلاس نيز جامع نمي‌باشد. يعني مسائلي وجود دارند که بهترين و کارامدترين الگوريتم‌ها نيز زمان بيش‌تري نسبت به زمان تواني مي‌گيرند.

· Un-decidable يا غيرقابل تصميم‌گيري: براي برخي از مسائل مي‌توانيم اثبات کنيم که الگوريتمي را نمي‌شود پيدا کردن که هميشه آن مساله را حل مي‌کند، بدون در نظر گرفتن فضا و زمان. در اين زمينه آقاي ريچارد ليپتون (از صاحب‌نظران اين زمينه) در مقاله‌اي نوشته‌اند: يک روش اثبات غيررسمي براي اين مساله مي‌تواند اين باشد: تعداد زيادي مساله، مثلا به زيادي اعداد حقيقي وجود دارند، ولي تعداد برنامه‌هايي که مسائل را حال مي‌کنند در حد اعداد صحيح مي‌باشند. اما ما هميشه مي‌توانيم مسائل به دردبخوري را پيدا کنيم که قابل حل نمي‌باشند.

آيا P=NP مي‌باشد؟

اين سوال که آيا مسائل کلاس P دقيقا همان مسائل کلاس NP مي باشند، يکي از مهم ترين سوال‌هاي بدون جواب علوم کامپيوتري مي‌باشد. به بياني ديگر اگر هميشه به اين سادگي باشد که بتوان صحت يک راه‌حل را بررسي کرد، آيا پيدا کردن راه‌حل نيز مي‌تواند به آن سادگي باشد؟ براي اين سوال يک جايزه 1 ميليون دلاري از طرف انسیتیتو ریاضی Clay در نظرگرفته شده‌است. ما هيچ دليلي براي قبول کردن آن نداريم ولي بين نظريه‌پردازان نيز اين باور وجود دارد که بايد جواب اين سوال منفي باشد. همچنين دليلي براي رد کردن آن نيز وجود ندارد.

پیچیدگی زمانی

پيچيدگي زماني يک مساله تعداد گام‌هاي مورد نياز براي حل يک نمونه از يک مساله به عنوان تابعي از اندازه‌ي ورودي (معمولا بوسيله تعداد بيت‌ها بيان مي‌شود) بوسيله کارآمدترين الگوريتم مي‌باشد. براي درک بهتر اين مساله، فرض کنيد که يک مساله با ورودي n بيت در n² گام حل شود. در اين مثال مي‌گوييم که مساله از درجه پيچيدگي n² مي‌باشد. البته تعداد دقيق گام‌ها بستگي به ماشين و زبان مورد استفاده دارد. اما براي صرف نظر کردن از اين مشکل، نشانه‌گذاری O بزرگ (Big O notation) معمولا بکار مي‌رود. اگر يک مساله پيچيدگي زماني از مرتبه (O(n² روي يک کامپيوتر نمونه داشته باشد، معمولا روي اکثر کامپيوتر‌هاي ديگر نيز پيچيدگي زماني از مرتبه (O(n² خواهد‌داشت. پس اين نشانه به ما کمک مي‌کند که صرف نظر از يک کامپيوتر خاص، يک حالت کلي براي پيچيدگي زماني يک الگوريتم ارائه دهيم.

معرفي NP-Complete

تا اين بخش از مقاله مسائلي معرفي شدند که اگر بتوان روشي براي حل آنها حدس زد، در زمان نزديک به زمان خطي و يا حداقل در زمان چند جمله‌اي برحسب ورودي مي‌توانستيم صحت راه‌حل را بررسي کنيم. ولي NP-Completeها مسائلي هستند که اثبات شده به سرعت قابل حل نيستند. در تئوري پيچيدگي NP-Completeها دشوارترين مسائل کلاس NP هستند و جزء مسائلي مي‌باشند که احتمال حضورشان در کلاس P خيلي کم است. علت اين امر اين مي‌باشد که اگر يک راه‌حل پيدا شود که بتوانديک مساله NP-Complete را حل کند، مي‌توان از آن الگوريتم براي حل کردن سريع همه مسائل NP-Complete‌ استفاده کرد. به خاطر اين مساله و نيز بخاطر اينکه تحقيقات زيادي براي پيدا کردن الگوريتم کارآمدي براي حل کردن اينگونه مسائل با شکست مواجه شده‌اند، وقتي که مساله‌اي به عنوان NP-Complete‌ معرفي شد، معمولا اينطور قلمداد مي‌شود که اين مساله در زمان Polynomial قابل حل شدن نمي‌باشد، يا به بياني ديگر هيچ الگوريتمي وجود ندارد که اين مساله را در زمان Polynomial حل نمايد. کلاس متشکل از مسائل NP-Compete با نام NP-C نيز خوانده مي‌شود.

بررسي ناکارآمد بودن زماني

مسائلي که در تئوري قابل حل شدن مي‌باشند ولي در عمل نمي‌توان آنها را حل کرد، محال يا ناشدني مي‌نامند. در حالت کلي فقط مسائلي که زمان آنها به صورت Polynomial مي‌باشد و اندازه ورودي آنها در حد کوچک يا متوسط مي‌باشد قابل حل شدن مي‌باشند. مسائلي که زمان آنها به صورت تواني (EXPTIME-complete) مي‌باشند به عنوان مسائل محال يا ناشدني شناخته شده‌اند. همچنين اگر مسائل رده NP جز مسائل رده P نباشند، مسائل NP-Complete نيز به عنوان محال يا نشدني خواهند بود. براي ملموس‌تر شدن اين مساله فرض کنيد که يک مساله 2n مرحله لازم دارد تا حل شود (n اندازه ورودي مي‌باشد). براي مقادير کوچک n=100 و با در نظر گرفتن کامپيوتري که $1010$ (10 giga) عمليات را در يک ثانيه انجام مي‌دهد، حل کردن اين مساله زماني حدود $1012 * 4$ سال طول خواهد کشيد، که اين زمان از عمر فعلي جهان بيشتر است!

چرا حل مسائل NP-Complete مشکل است؟

به خاطر اينکه مسائل بسيار مهمي در اين کلاس وجود دارد، تلاش‌هاي بسيار زيادي صورت گرفته است تا الگوريتم‌هايي براي حل مسائل NP که زمان آن به صورت Polynomial از اندازه ورودي باشد، پيدا شود. باوجود اين، مسائل خيلي بيشتري در اين رده وجود دارد که زمان لازم براي حل آن‌ها به صورت Super-Polynomial مي‌باشد. اين مساله که آيا اين مسائل در زمان Polynomial قابل حل شدن مي‌باشند، يکي از مهم‌ترين چالش‌هاي علوم کامپيوتري مي‌باشد.

روش‌هايي براي حل مسائل NP-Complete

به خاطر اينکه تعداد مسائل NP-Complete بسيار زياد مي‌باشد، شناختن اينگونه مسائل به ما کمک مي‌کند تا دست از پيدا کردن يک الگوريتم سريع و جامع برداريم و يکي از روش‌هاي زير را امتحان کنيم:

· به کار بردن يک روش حدسي: يک الگوريتم که تا حد قابل قبولي در بيشتر موارد درست کار مي‌کند، ولي تضميني وجود ندارد که در همه موارد با سرعت قابل قبول نتيجه درستي توليد کند.

· حل کردن تقريبي مساله به جاي حل کردن دقيق آن: اغلب موارد اين روش قابل قبول مي‌باشد که با يک الگوريتم نسبتا سريع يک مساله را به طور تقريبي حل کنيم که مي‌توان ثابت کرد جواب بدست آمده تقرييا نزديک به جواب کاملا صحيح مي‌باشد.

· الگوريتم‌هاي زمان تواني را به کار ببريم: اگر واقعا مجبور به حل کردن مساله به طور کامل هستيم، مي‌توان يک الگوريتم با زمان تواني نوشت و ديگر نگران پيدا کردن جواب بهتر نباشيم.

· از خلاصه کردن استفاده کنيم: خلاصه کردن به اين مفهوم مي‌باشد که از برخي اطلاعات غيرضروري مي‌توان صرف نظر کرد. اغلب اين اطلاعات براي پياده‌سازي مساله پيچيده در دنياي واقعي مورد نياز مي‌باشد، ولي در شرايطي که بخواهيم به نحوي مساله را حل کنيم (حداقل به صورت تئوري و نه در عمل) مي‌توان از برخي اطلاعات غيرضروري صرف نظر کرد.

نمونه مساله

يک مسير ساده در يک گراف به مسيري اطلاق مي‌شود که هيچ راس يا يال تکراري در آن وجود‌نداشته‌باشد. براي پياده سازي مساله ما به اين احتياج داريم که بتوانيم يک سوال بلي/خير طراحي کنيم. با داشتن گراف G، رئوس s و t و عدد k آيا يک مسير ساده از s به t با حداقل k يال وجوددارد؟ راه‌حل اين مساله جواب سوال خواهد بود. چرا اين مساله NP مي‌باشد؟ چون اگر مسيري به شما داده شود، به راحتي مي‌توان طول مسير را مشخص نمود و آن را با k مقايسه کرد. همه اين کار‌ها در زمان خطي و صد البته در زمان Polynomial قابل انجام مي‌باشد. اگر چه مي نمي‌دانيم که اين مساله آيا در کلاس P مي‌باشد يا نه، با اين حال روش خاصي براي پيدا کردن مسيري با ويژگي‌هاي ذکر شده نيز وجود بيان نشده است. و در حقيقت اين مساله جز NP-Completeها مي‌باشد، پس مي‌توان به اين نتيجه نيز رسيد که الگوريتمي کارآمد با چنان عمليات وجود ندارد. الگوريتم‌هايي وجود دارند که اين مساله را حل مي‌کنند، به عنوان مثال همه مسير‌هاي موجود و ممکن را بررسي نموده و نتايج مقايسه شوند که آيا اين مسير مساله را حل مي‌کند يا نه. اما تا آنجايي که مي‌دانيم، الگوريتمي با زمان Polynomial براي حل اين مساله وجود ندارد.

طراحی و تحلیل الگوریتم‌ها و ساختار داده‌ها

الگوریتم

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

نام

واژه الگوریتم از نام محمد ابن موسی خوارزمی گرفته شده است. کتاب معروف الجبر و المقابله خوارزمی که حاوی دستورالعمل‌های مختلف برای حل مسائل محاسباتی است از راه ترجمه اسپانیایی آن در اروپا شناخته شد و نام عربی او، الخوارزمی، (از طریق آوانگاری آن در زبان اسپانیایی و سپس ورود آن به دیگر زبان‌های اروپائی) مترادف شد با "دستورهای حل مسائل".

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

مفهوم الگوریتم

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

الگوریتم گاه دارای مراحلی است که تکرار می‌شود (در مثال آبگوشت مثلاً چند بار باید نمک زد یا آب اضافه کرد) و یا در مرحله‌ای نیازمند تصمیم‌گیری است (اگر نمک کافی است دیگر نمک نمی‌زنیم، اگر نیست می‌زنیم).

اگر الگوریتم برای عمل مورد نظر مناسب نباشد و با غلط باشد به نتیجه مورد نظر نمی‌رسیم. مثلاً اگر الگوریتم آبگوشت را با مواد اولیه کباب انجام دهیم یا اگر در الگوریتم ما ذکری از گوشت نباشد واضح است که به آبگوشت نمی‌رسیم.

تحلیل الگوریتم

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

تحلیل الگوریتم‌ها رشته‌ای است که به بررسی کارآئی الگوریتم‌ها میپردازد. موضوع تحلیل الگوریتم‌ها در مورد تعیین میزان منابعی است که برای اجرای هر الگوریتم لازم است. این منابع معمولاً زمان و حافظه در نظر گرفته می‌شوند. کارآئی یا پیچیدگی هر الگوریتم را با تابعی نشان می‌دهند که تعداد مراحل لازم برای اجرای الگوریتم را برحسب طول داده ورودی، یا میزان محل‌های لازم حافظه را بر حسب طول داده ورودی نشان می‌دهد.

جنبه حقوقی

در بعضی کشورها، مثل امریکا اگر تعبیه فیزیکی الگوریتمی ممکن باشد (برای مثال، یک الگوریتم ضرب که می‌شود آن را در واحد محاسبهٔ یک ریز پردازنده تعبیه کرد) می‌شود آن الگوریتم را به ثبت رساند.

الگوریتم مرتب‌سازی

الگوریتم مرتب‌سازی، در علوم کامپیوتر و ریاضی، الگوریتمی است که لیستی از داده‌ها را به ترتیبی مشخص می‌چیند.

پر استفاده‌ترین ترتیب‌ها، ترتیب‌های عددی و لغت‌نامه‌ای هستند. مرتب‌سازی کارا در بهینه سازی الگوریم‌هایی که به لیست‌های مرتب شده نیاز دارند (مثل جستجو و ترکیب) اهمیت زیادی دارد.

از ابتدای علم کامپیوتر مسائل مرتب‌سازی تحقیقات فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیده‌است. برای مثال مرتب‌سازی حبابی در سال ۱۹۵۶ به وجود آمد. در حالی که بسیاری این را یک مسئلهٔ حل شده می‌پندارند، الگوریتم کارآمد جدیدی همچنان ابداع می‌شوند (مثلاً مرتب‌سازی کتاب خانه‌ای در سال ۲۰۰۴ مطرح شد).

مبحث مرتب‌سازی در کلاس‌های معرفی علم کامپیوتر بسیار پر کاربرد است، مبحثی که در آن وجود الگوریتم‌های فراوان به آشنایی با ایده‌های کلی و مراحل طراحی الگوریتم‌های مختلف کمک می‌کند؛ مانند تحلیل الگوریتم، داده‌ساختارها، الگوریتم‌های تصادفی، تحلیل بدترین و بهترین حالت و حالت میانگین، هزینهٔ زمان و حافظه، و حد پایین.

طبقه‌بندی

در علم کامپیوتر معمولاً الگوریتم‌های مرتب‌سازی بر اساس این معیارها طبقه‌بندی می‌شوند:

· پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین): با توجه به اندازهٔ لیست (n). در مرتب‌سازی‌های معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n^۲ است. بهترین عملکرد برای مرتب‌سازی (O(n است. الگوریتم‌هایی که فقط از مقایسهٔ کلیدها استفاده می‌کنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.

· حافظه (و سایر منابع کامپیوتر) : بعضی از الگوریتم‌های مرتب‌سازی «در جا^[1]» هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظهٔ کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتم‌ها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.

· پایداری^[2] : الگوریتم‌های مرتب‌سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ می‌کنند. فرض کنید می‌خواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نام‌های الف و ب هم‌سن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.

· مقایسه‌ای بودن یا نبودن. در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب می‌شوند.

· روش کلی : درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و مرتب‌سازی سریع و گزینشی مانند مرتب‌سازی پشته‌ای.

الگوریتم‌های مرتب سازی

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

(به انگلیسی: Bubble Sort)

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

۰ - ۰)    ۵۶۴۲

۱ - ۱)    ۵۶۴۲

۱ - ۲)    ۵۴۶۲

۱ - ۳)    ۵۴۲۶

۲ - ۱)    ۴۵۲۶

۲ - ۲)    ۴۲۵۶

۳ - ۱)    ۲۴۵۶

مرحله اول سه مقایسه ، مرحله دوم دو مقایسه و مرحله سوم یک مقایسه داره ، که روی هم می‌شوند شش مقایسه. در کل این روش n (n - ۱) / ۲ مقایسه لازم داره. اما نه همیشه. به مثال زیر توجه کنید:

۰ - ۰)    ۰۷۱۳۵۴

۱ - ۱)    ۰۱۷۳۵۴

۱ - ۲)    ۰۱۷۳۵۴

۱ - ۳)    ۰۱۳۷۵۴

۱ - ۴)    ۰۱۳۵۷۴

۱ - ۵)    ۰۱۳۵۴۷

۲ - ۱)    ۰۱۳۵۴۷

۲ - ۲)    ۰۱۳۵۴۷

۲ - ۳)    ۰۱۳۵۴۷

۲ - ۴)    ۰۱۳۴۵۷

۳ - ۱)    ۰۱۳۴۵۷

۳ - ۲)    ۰۱۳۴۵۷

۳ - ۳)    ۰۱۳۴۵۷

۴ - ۱)    ۰۱۳۴۵۷

۴ - ۲)    ۰۱۳۴۵۷

۵ - ۱)    ۰۱۳۴۵۷

همونطور که می‌بینید انتهای مرحله ۲ داده‌ها مرتب هستن. تشخیص این مساله هم کار سختی نیست: اگه به مرحله‌ای رسیدیم که هیچ جابجایی در اون رخ نداد نتیجه می‌شه که داده‌ها مرتب هستن (مرحله سوم). پس بعد از مرحله ۳ مطمئن می‌شیم که داده هامون مرتب شدن و نیازی به مراحل ۴ و ۵ نیست. پیاده سازی (مرتب سازی حبابی) در c++

void bubble_sort (int arr [ ] , int n)

  register int i , j , t , c;

(--  for (i = n - ۲ ; i >= ۰ ; i

    c = ۰;

   (++ for (j = ۰ ; j <= i ; j

       if (arr [ j ] > arr [ j + ۱ ])

     ; ] t = arr [ j

          arr [ j ] = arr [ j + ۱ ];

       ; arr [ j + ۱ ] = t

        C++;

     (if (c == ۰

       ; break

مرتب سازی گزینشی

(به انگلیسی: Selection Sort)

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

روش انتخابی اولین روشیه که به ذهن می‌رسه: بزرگترین رکورد بین رکوردهای لیست رو پیدا می‌کنیم و به انتهای لیست انتقال می‌دیم. از بقیه رکوردها بزرگترین رو انتخاب می‌کنیم و انتهای لیست - کنار رکورد قبلی - قرار می‌دیم و ... مثلا:

۰:  ۹۱۶۴۷۳۵

۱:  ۵۱۶۴۷۳۹

۲:  ۵۱۶۴۳۷۹

۳:  ۵۱۳۴۶۷۹

۴:  ۴۱۳۵۶۷۹

۵:  ۳۱۴۵۶۷۹

۶:  ۱۳۴۵۶۷۹

پیاده سازی (مرتب سازی انتخابی) در c++

void selection_sort (int arr[] , int n)

  register int i , j;

  int max , temp;

  (--for (i = n - ۱ ; i > ۰ ; i

    max = ۰;

    for (j = ۱ ; j <= i ; j++)

      if (arr[ max ] < arr[ j])

            max = j;

          ; ] temp = arr[ i

            arr[ i ] = arr[ max];

            arr[ max ] = temp;

۳ - مرتب سازی (Shell Sort)

نام این الگوریتم از نام مخترع آن گرفته شده‌است. در این الگوریتم از روش درج استفاده می‌شود .

به عنوان مثال رشته f d a c b e را تحت این الگوریتم مرتب می‌کنیم.

           F     d   a    c    b    e             : شروع

           C     d   a    f    d    e            : مرحله اول

           A     b   c    d    e    f            : مرحله دوم

           A     b   c    d    e    f             : نتیجه

در مرحله اول : دادههای با فاصله ۳ از یکدیگر ، مقایسه و مرتب شده ، در مرحله دوم داده‌های با فاصله ۲ از یکدیگر ، مقایسه و مرتب می‌شوند  و در مرحله دوم داده‌ها با فاصله یک از یکدیگر مقایسه و مرتب می‌شوند .

منظور از فاصله سه این است که عنصر اول با عنصر چهارم(۳+۱) ، عنصر دوم با عنصر پنجم(۵=۳+۲) و عنصر سوم با عنصر ششم(۶=۳+۳) مقایسه شده در جای مناسب خود قرار می‌گیرد .

برای انتخاب فاصله در اولین مرحله ، تعداد عناصر لیست بر ۲ تقسیم می‌شود(n/۲) وفاصله بعدی نیز با تقسیم فاصله فعلی بر ۲ حاصل می‌گردد و الگریتم تا زمانی ادامه پیدا می‌کند که این فاصله به صفر برسد.

برای نمونه اگر تعداد عناصر برابر با ۱۰ باشد ، فاصله در مرحله اول برابر با ۵ ، در مرحله دوم برابر با ۲ ور در مرحله سوم برابر با ۱ و در نهایت برابر با صفر خواهد بود .

زمان مرتب سازی shell  از رابطه n       پیروی می‌کند که نسبت به    n^۲  بهبود خوبی پیدا کرده‌است لذا  سرعت عمل روش مرتب سازی shell   از روشهای  انتخابی ، در جی و حبابی   بیشتر است.

پیاده سازی مرتب سازی Shell sort)) در c++ :

#include<stdio.h>

#include<conio.h>

< include<string.h#

Void shell(int *,char*,int)

Int main()

            Char s[۸۰];

            Int gap[۸۰];

           (); Clrscr

           ;(«: Printf(» Enter a string

        ); Gets(s

        )); Shell(gap,s,strlen(s

        ); Printf(«\n the sorted string is : ٪s»,s

            Getch();

            Return ۰;

****************************//

Void shell(int gap [], char * item, int count)

                Register int I, j,step,k,p;

               ; Char x

                Gap[۰] =count /۲;

                While(gap[k] > ۱)

 ++; K

Gap[k]=gap[k-۱]/۲;

}//end of while

For (i= ۰;i<=k;i++)

Step=gap[i];

For(j=step;j<count; j++)

X=item[j];

P=j-step;

             While(p>=۰ &&  x<item[p])

Item[p+step]=item[p];

P=p-step;

Item[p+step]=x;

مرتب سازی سریع

(به انگلیسی: Quick Sort)

مرتب سازی سریع (Quick Sort) از جمله روشهای محبوب و با سرعت بالا برای مرتب کردن داده‌ها محسوب می‌شه. این روش هم مثل روش ادغام از تقسیم و حل (Divide andConqure) برای مرتب کردن داده‌ها استفاده می‌کنه. به این ترتیب که داده‌ها رو به دو قسمت مجزا تقسیم، و با مرتب کردن اونها کل داده‌ها رو مرتب می‌کنه. برای اینکار یکی از داده‌ها (مثلا داده اول) به عنوان محور انتخاب می‌شه. داده‌ها بر اساس محور طوری چینش می‌شن که همه داده‌های کوچکتر از محور سمت چپ و داده‌های بزرگتر یا مساوی اون سمت راستش قرار می‌گیرن. با مرتب کردن دو قسمت به دست اومده کل داده‌ها مرتب می‌شن. در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست. چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچکتر هستن و بالعکس. مثلا اعداد صحیح زیر رو در نظر بگیرید:

۵  ۶  ۱  ۹  -۲  ۴  ۵  ۱۵  ۳  ۱  ۴  ۱۰

عدد ۵ رو به عنوان محور در نظر می‌گیریم. داده‌ها به این صورت بازچینی می‌شن:

۱  -۲  ۴  ۳  ۱  ۴  ۵  ۶  ۹  ۵  ۱۵  ۱۰

همونطور که مشاهده می‌کنید اعداد سمت چپ عدد ۵ زیر خط دار همگی از ۵ کوچیکتر و اعداد سمت راست بزرگتر یا مساوی اون هستن.

پیاده سازی مرتب سازی Quick sort)) در c++

تابع partition با دریافت آرایه و حد بالا و پایین تکه‌ای که باید تقسیم بشه عملیات لازم رو انجام می‌ده، و اندیس محل تفکیک رو (محل عدد ۵ در مثال بالا) به عنوان نتیجه بر می‌گردونه.

int partition (int arr[ ] , int low , int high)

 int lb = low + ۱ , rb = high , temp , pivot = arr[ low ] , p;

 while (lb <= rb)

  while (arr[ lb ] <= pivot && lb <= rb)

   lb++;

  while (arr[ rb ] > pivot && lb <= rb)

   rb--;

  if (lb < rb)

   temp = arr[ lb];

   arr[ lb ] = arr[ rb];

   arr[ rb ] = temp;

 (if (rb == high

  p = high;

else if(rb == low)

  p = low;

 else

  p = lb – ۱;

 arr[ low ] = arr[ p];

 arr[ p ] = pivot;

 return p;

اگه این تابع رو برای مثال بالا استفاده کنیم مقدار ۶ (اندیس ۵ زیرخط دار) برگشت داده می‌شه. با تکرار کردن این عملیات برای دو قسمت به دست اومده (در مثال بالا از اندیس صفر تا ۵ و از اندیس ۷ تا ۱۱) داده‌ها به صورت کامل مرتب می‌شن.

بر اساس گفته‌های بالا تابع مرتب سازی به این صورت خواهد بود:

void quick_sort (int arr[ ] , int low , int high)

if (low < high)

  int p = partition(arr , low , high);

  quick_sort(arr , low , p – ۱);

  quick_sort(arr , p + ۱ , high);

همونطور که مشاهده می‌کنید این تابع بصورت بازگشتی نوشته شده. در صورتی که بخواید به صورت غیر بازگشتی بنویسید باید از پشته به صورت زیر استفاده کنید:

void quick_sort (int arr[ ] ,int n)

 stack st;

 st.push(۰);

 st.push(n – ۱);

 int low , p , high;

 while(! st.isempty())

  high = st.pop();

  low = st.pop();

  p = partition(arr , low , high);

  if (p > low)

   st.push(low);

   st.push(p – ۱);

  if (p < high)

   st.push(p + ۱);

   st.push(high);

۵ - مرتب سازی ادغامSort) Merge)

روش مرتب سازی ادغام از الگوریتم تقسیم و حل (divide-and-conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. در این الگوریتم مساله به چند جزء کوچکتر تقسیم می‌شه. هر کدوم از این قسمتها رو به طور مجزا حل کرده ، و با ترکیب اونها به مساله اصلی می‌رسیم. و اما طرح کلی مرتب سازی ادغام:

در این روش داده‌ها به دو قسمت مساوی تقسیم می‌شن. و هر کدوم از این قسمتها - به صورت بازگشتی - مرتب ، و با ادغامشون دادها بصورت کامل مرتب می‌شن.

پیاده سازی مرتب سازی Merge sort)) در c++

void merge_sort (int arr[ ] , int low , int high)

 if (low >= high)

  return;

 int mid = (low + high) / ۲;

 merge_sort (arr , low , mid);

 merge_sort (arr , mid + ۱ , high);

 merge_array (arr , low , mid , high);

procedure merge_sort (var arr : array of integer ; l : integer ; h : integer);

var

 m : integer;

begin

 if l >= h then

  exit;

 m := (l + h) div ۲;

 merge_sort (arr , l , m);

 merge_sort (arr , m + ۱ , h);

 merge_array (arr , l , m , h);

end;

این توابع اونقدر ساده هستن که نیاز به هیچ توضیحی ندارن. فقط می‌مونه تابع merge_array که دو زیر آرایه رو با هم ادغام می‌کنه.

void merge (int arr[ ] , int low , int mid , int high)

 register int i , j , k , t;

 j = low;

 for (i = mid + ۱ ; i <= high ; i++)

  while (arr[ j ] <= arr[ i ] && j < i)

   j++;

  if (j == i)

   break;

  t = arr[ i];

  for (k = i ; k > j ; k--)

   arr[ k ] = arr[ k – ۱];

  arr[ j ] = t;

procedure merge_array (var arr : array of integer ; l : integer ; m : integer ; h : integer);

var

 i , j , k , t : integer;

begin

 j := l;

 for i := m + ۱ to h do

 begin

  while (arr[ j ] <= arr[ i ]) and (j < i) do

   inc (j);

  if j = i then

   break;

  t := arr[ i];

  for k := i downto j + ۱ do

   arr[ k ] := arr[ k – ۱];

  arr[ j ] := t;

 end;

End;

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

۶ - مرتب سازی درجی (Insertion Sort)

مرتب سازی درجی (Insertion Sort) یکی از روشهای مرتب سازی رایج و البته نه چندان کارا محسوب می‌شه. این روش در مقایسه با مرتب سازی حبابی و انتخابی سرعت بهتری داره و برای مرتب کردن تعداد کمی از عناصر مناسبه. به همین خاطر مراخل انتهایی روش مرتب سازی سریع (Quick Sort) با کمک گرفتن از این روش انجام می‌گیره.

الگوریتم مرتب سازی درجی بر اساس مرتب سازیهایی که معمولا خود ما بصورت دستی انجام می‌دیم طراحی شده. فرض کنید دسته کارتی با شماره‌های ۱ تا ۱۰ بصورت نامرتب و کنار هم روی زمین چیده شدن:

۵ ۲ ۹ ۳ ۱ ۱۰ ۴ ۶ ۸ ۷

کارت دوم رو نسبت به کارت اول در جای مناسب خودش قرار می‌دیم:

۲ ۵ ۹ ۳ ۱ ۱۰ ۴ ۶ ۸ ۷

حالا نوبت به کارت سوم می‌رسه. این کارت رو نسبت به دو کارت قبلی در جای مناسب قرار می‌دیم. چون ۹ در مقایسه با ۲ و ۵ جای درستی داره بدون هیچ جابجایی به کارت چهارم می‌رسیم. جای این کارت رو نسبت به سه کارت قبلی مشخص می‌کنیم:

۲ ۳ ۵ ۹ ۱ ۱۰ ۴ ۶ ۸ ۷

و به همین ترتیب تا آخر ادامه می‌دیم.

اگه n تعداد عناصر رو مشخص کنه ، این روش n - ۱ مرحله رو برای مرتب کردن طی می‌کنه. بعد از اتمام مرحله i ام مطمئنا i + ۱ عنصر اول به صورت مرتب شده هستن (قسمتی که زیرشون خط کشیده شده). این مساله یکی از حسنهای مرتب سازی درجی محسوب می‌شه: در هر مرحله حتما قطعه‌ای از عناصر مرتب شذه هستن. مرتب سازی حبابی این ویژگی رو نداره.

پیاده سازی(مرتب سازی درجی) در c++

void insertion_sort (int arr[ ] , int n)

  register int i , j , t;

 (++ for (i = ۱ ; i < n ; i

  ]; t = arr[ i

   (-- for (j = i ; j > ۰ && arr[ j - ۱ ] >= t ; j

     ; arr[ j ] = arr[ j - ۱]

    arr[ i ] = t;

۷ - مرتب سازی Heep Sort))

یک الگوریتم مرتب سازی در حافظه (RAM) میباشد. Heap یک درخت دودویی کامل است با ارتفاع Height = ëlog nû هر گره (node) یک کلید بیشتر ندارد که بزرگتر یا برابر کلید گره پدر (parent) میباشد. بصورت یک آرایه (Array) ذخیره میشود. برای هر گره (i) فرزندان آن در گره‌های (۲i) و (۲i+۱) ذخیره شده‌اند. پدر هر گره (j) در گره (j/۲) میباشد.

الگوریتم Insert در Heap Sort چگونه است؟

۱) رکورد جدید در آخر Heap اضافه میشود.

۱) کلید آن با کلید گره پدر مقایسه می‌شود و اگر مقدار آن کوچکتر بود محل آن با محل گره پدر تعویض میشود.

۱) در صورت لزوم عمل (۲) تا ریشه درخت (Root) ادامه مییابد.

الگوریتم Remove در Heap Sort چگونه است؟ ۱) کوچکترین کلید که در گره Root میباشد خارج میشود. ۲) بزرگترین کلید (آخرین گره) به گره Root منتقل میگردد. ۳) کلید آن با کوچکترین کلید فرزند مقایسه می‌شود و اگر بیشتر بود جای آن دو تعویض میشود. ۴) در صورت لزوم عمل (۳) تا آخر Heap تکرار میگردد.

فهرست الگوریتم‌های مرتب‌سازی

در این جدول، n تعداد داده‌ها و k تعداد داده‌ها با کلیدهای متفاوت است. ستون‌های بهترین، میانگین و بدترین، پیچیدگی در هر حالت را نشان می‌دهد و حافظه بیانگر مقدار حافظهٔ کمکی (علاوه بر خود داده‌ها) است.

نام	بهترین	میانگین	بدترین	حافظه	پایدار	مقایسه‌ای‌	روش	توضیحات
مرتب سازی حبابی (Bubble sort)	(O(n	—	(O(n^۲	(O(۱	بله	بله	جابجایی	Times are for best variant
Cocktail sort	(O(n	—	(O(n^۲	(O(۱	بله	بله	جابجایی
Comb sort	(O(n log n	—	(O(n log n	(O(۱	خیر	بله	جابجایی
Gnome sort	(O(n	—	(O(n^۲	(O(۱	بله	بله	جابجایی
Selection sort	(O(n^۲	(O(n^۲	(O(n^۲	(O(۱	خیر	بله	گزینشی
Insertion sort	(O(n	—	(O(n^۲	(O(۱	بله	بله	درجی
Shell sort	(O(n log n	—	(O(n log^۲n	(O(۱	خیر	بله	درجی	Times are for best variant
Binary tree sort	(O(n log n	—	(O(n log n	(O(۱	بله	بله	درجی
Library sort	(O(n	(O(n log n	(O(n^۲	ε+۱)n)	بله	بله	درجی
Merge sort	(O(n log n	—	(O(n log n	(O(n	بله	بله	Merging
In-place merge sort	(O(n log n	—	(O(n log n	(O(۱	بله	بله	Merging	Times are for best variant
Heapsort	(O(n log n	—	(O(n log n	(O(۱	خیر	بله	گزینشی
Smoothsort	(O(n	—	(O(n log n	(O(۱	خیر	بله	گزینشی
Quicksort	(O(n log n	(O(n log n	(O(n^۲	(O(n	خیر	بله	Partitioning	Naive variants use (O(n space
Introsort	(O(n log n	(O(n log n	(O(n log n	(O(n	خیر	بله	Hybrid
Pigeonhole sort	(O(n+k	—	(O(n+k	(O(k	بله	خیر	Indexing
Bucket sort	(O(n	(O(n	(O(n^۲	(O(k	بله	خیر	Indexing
Counting sort	(O(n+k	—	(O(n+k	(O(n+k	بله	خیر	Indexing
Radix sort	(O(nk	—	(O(nk	(O(n	بله	خیر	Indexing
Patience sorting	(O(n	—	(O(n log n	(O(n	خیر	بله	درجی	تمام زیر دنباله‌های صعودی را با (O(n log (log(n پیدا می‌کند.

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

نام	بهترین	میانگین	بدترین	حافظه	پایدار	مقایسه‌ای	توضیحات
Bogosort	(O(n	O(n × n!)	بدون حد	(O(۱	خیر	بله
Stooge sort	(O(n^۲^٫^۷۱	—	(O(n^۲^٫^۷۱	(O(۱	خیر	بله
Bead sort	(O(n	—	(O(n	—	N/A	خیر	به سخت‌افزار مخصوص نیاز دارد.
Pancake sorting	(O(n	—	(O(n	—	خیر	بله	به سخت‌افزار مخصوص نیاز دارد.
Sorting networks	(O(log n	—	(O(log n	—	بله	بله	Requires a custom circuit of size (O(log n

زبان‌های برنامه‌نویسی و کامپایلرها

زبان‌های برنامه‌نویسی

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

تعداد زبانهای برنامه‌نویسی رایانه‌ای بسیار زیاد است، اما از میان معروفترین و اصلی‌ترین آنها می‌توان به این موارد اشاره کرد :

Visual Basic, C#, C++, Java, Python, Delphi, Turbo Pascal, Foxpro, Fortran, Cobol, PL1, Qbasic, Gwbasic,

همگردان

كامپایلر در اصل برنامه یا مجموعه ای از برنامه های كامپیوتری است كه متن تایپ شده در زبان برنامه نویسی را (زبان مبدا) به زبان ماشین دیگری تبدیل می كند(زبان مقصد). معمولا ورودی اصلی را كد مبدا و خروجی را كد شی گوییم. خروجی این برنامه ممكن است برای پردازش شدن توسط برنامه دیگری مثل Linker مناسب باشد یا فایل متنی باشد كه انسان نیز بتواند آنرا بخواند. مهمترین علت استفاده از ترجمه كد مبدا، ایجاد برنامه اجرایی می باشد. اصطلاح همگردان (compiler) اصولا برای برنامه هایی به كار میرود كه كد مبدا را از یك زبان سطح بالا به زبانی سطح پایین تری مثل اسمبلی یا زبان سطح ماشین ترجمه می كند. برعكس برنامه ای كه زبان سطح پایین را به بالاتر تبدیل می كند را decompiler گوییم.

به طور خلاصه می توان گفت:

· هر برنامه‌ای که با استفاده از قوانین دستوری و معنایی، مجموعه‌ای از نمادها را ترجمه می‌کند.

· برنامه‌ای که تمامی دستورات ترجمه نشدهٔ یک برنامهٔ نوشته شده با یک زبان سطح بالا را پیش از اجرا به زبان ماشین ترجمه می‌‌کند.

تاریخچه

كامپیوتر های اولیه از كامپایلر ها استفاده نمی كردند، چرا كه این كامپیوتر ها حافظه كوچكی داشتند و با برنامه های كوتاه سر و كار داشتیم. كاربران مجبور بودند كد باینری یا دسیمال برنامه ها را به طور مستقیم و با كمك نوار های مغناطیسی به سیستم وارد كنند. اما برنامه نویس ها زیاد این وضعیت را تحمل نكردند و به فكر تولید برنامه ای افتادند كه كاراكتر های الفبایی(واژه های اختصاری) را به تعدادی دستور كه قابل اجرا توسط ماشین باشد تبدیل كند. در این وضعیت بود كه زبان های اسمبلی و كامپایلر های اولیه با نام اسمبلر به وجود آمد. در اواخر دهه 90 بود كه ماشین های وابسطه به زبانهای زبانهای برنامه نویسی رونق گرفتند. متعاقبا كامپایلرهای آزمایشی ایجاد شدند. FORTRAN به سرپرستی John Backus در شركت IBM به عنوان اولین كامپایلر كامل را در سال 1957 تولید شد. كوبول اولین زبان كامپایلی با معماری چندگانه در سال 1960 تولید شد. در طی دهه 60 كامپایلر های زیادی تولید شد اما بر روی كیفیت كامپایلر ها كمتر فكر می شد. همزمان با تكامل زبان های برنامه سازی و افزایش قدرت كامپیوتر ها، كامپایلرها هرچه بیشتر پیچیده می شدند. یك كامپایلر خود برنامه ای است كه توسط زبان پیاده ساز تولید شده است. اولین كامپایلر خود محور كه می توانست كد خود را كامپایل كند برای زبان Lisp و توسط Hart و Levin در سال 1962 و در دانشگاه MIT ایجاد شد. در دهه 70 از زبانهای سطح بالایی مثل Pascal و C جهت نوشتن كامپایلر ها استفاده شد. ساخت كامپایلر های خود محور دارای مشكل راه اندازی است، چونكه هر كامپایلری باید توسط كامپایلر نوشته شده ای به زبان دیگر كامپایل شود یا برای این مشكل دست به دامن مفسری بشود. ساختار كامپایلر ها و كامپایلر بهینه ساز امروزه بخشی از برنامه درسی دانشجویان كامپیوتر است. برخی كامپایلر ها به منظور آموزشی برای زبان های برنامه نویسی تولید می گردد. مثلا كامپایلر PL/0 توسط Niklaus Wirth برای آموزش در دهه 1970 به كار رفت. به علت سادگی و دلایل زیر هنوز برای آموزش مورد استفاده قرار می گیرد:

· توسعه گام به گام برنامه

· به كار گیری پارسر های بازگشتی

· استفاده از EBNF جهت تعریف نحو زبان

· استفاده از P-Code در جریان تولید كد خروجی قابل حمل

· نمایش T-diagram جهت تعارف رسمی

کامپایلر تاریخچه کامپایلر

در تاریخچه کامپایلر سه دوره می‌توان در نظر گرفت:

از 1945تا1960:تولید کد

در این دوره ,زبانها به تدریج به وجود آمدند و ماشینها چندان متعارف نبودند . مسئله این بود که چگونه باید کدی را برای یک ماشین تولید کرد . با توجه به اینکه برنامه نویسی به زبان اسمبلی رواج داشت , این مسئله وخیمتر شد. استفاده از کامپایلر , برنامه نویسی خودکار نامیده شد . طرفداران زبانهای سطح بالا می‌ترسیدند که کد تولید شده نسبت به زبان اسمبلی کارایی چندان نداشته باشد. اولین کامپایلر فرترن(شریدان 1959) به خوبی بهینه سازی شد

از 1960تا1975 :تجزیه کردن

در دهه‌های 1960و1970 زبانهای برنامه‌سازی جدید به وجود آمدند و طراحان زبان معتقد بودند که طراحی سریع کامپایلر برای زبان جدید , مهمتر از وجود کامپایلری با کد کارآمد است .بدین ترتیب , در ساخت کامپایلر به پردازشگر جلویی تاکید شده است . در همین زمان , مطالعه زبانهای رسمی , تکنیکهای قدرتمندی را برای ساخت پردازشگر جلوی , بخصوص تولید تجزیه کننده به وجود آورد

از 1975 تاکنون :تولید کد و بهینه سازی کد

از 1975 تاکنون , تعداد زبانهای جدید و انواع ماشین مختلف کاهش یافت در نتیجه نیاز به کامپایلرهای سریع و ساده یا سریع و ناقص برای زبانها یا ماشینهای جدید , کاهش یافت . بزرگترین آشفتگی در طراحی زبان و ماشین خاتمه یافت و افراد خواستار کامپایلرهای قابل اعتماد , کارآمد و با واسط کاربر مناسب شدند . بدین ترتیب , توجه کیفی به کد بیشتر شد زیرا با تغیر اندکی که در ساختار ماشینها ایجاد می‌شود , طول عمر کدها افزایش می‌یابد.در همین دوره , مدلهایی در برنامه نویسی به وجود آمدند که برنامه نویسی تابعی , منطقی و توزیعی نمونه‌های از این مدلها هستند, خواسته‌های زمان اجرای این زبانها نسبت به زبانهای دستور, افزایش یافت .

انواع كامپایلر ها

راه های مختلفی جهت دسته بندی كامپایلر ها وجود دارد مثلا می توان آنها را با توجه به ورودی، خروجی، ساختار داخلی و یا رفتار زمان اجرای آن تقسیم بندی كرد.

كامپایلرهای Native و cross

اكثر كامپایلرها به دو دسته Native و Cross تقسیم می شوند. كامپایلرهایی كه به منظور اجرای برنامه ها كدهای باینری را تولید می كنند، كامپایلر هایی با كد محلی یا Native گوییم چرا كه تنها در كامپیوترهای یك نوع با سیستم عامل های یكسان قابل به كارگیری است. از طرف دیگر ممكن است كامپایلرها كدهای باینری را تولید كنند كه در سیستم های مختلف قابل اجرا باشد. به این دسته از كامپایلر ها كه وابستگی به سخت افزار ندارند، كامپایلر های عبوری یا Cross گوییم. برای این نوع كاپایلر ها تنها كافی است برای بار اول سخت افزار را به آن معرفی نمود. بنابراین می توان نتیجه گرفت كه كامپایلرهای عبوری مفیدتر هستند. این تقسیم بندی برای مفسرها به كار نمی رود جونكه آنها از نمایش دودویی برای اجرای كد خود استفاده نمی كنند. ماشین های مجازی در هیچ یك از این دسته بندی ها نمی گنجد. هر گاه در ماشین های مجازی یكسان قابل اجرا باشد می توان آنرا Native و هرگاه كامپایلر قادر به تولید خروجی برای پلت فورم های مختلف باشد آنرا Cross گوییم.

كامپایلرهای تك فاز و چند فاز

فاز بندی كامپایلر ها كه در پشت زمینه به محدودیت های منابع سخت افزاری وابسته است. در نتیجه كامپایلر ها به مجموعه برنامه های كوچكتر تقسیم می شوند هر یك بخشی از عمل ترجمه یا آنالیز را برعهده می گیرند. كامپایل تك فازی به نظر مفید می آید، چراكه سریعتر است. زبان پاسكال از این امكان استفاده می كند. اما مشكل اینجا است كه اگر اعلان جلوتر از دستور به كارگیری باشد، چه كار باید كرد؟ برای حل این مشكل میتوان در فاز اول اعلان ها را مشخص كرد و در فاز بعد عمل ترجمه را انجام داد. عیب دیگر كامپایلر تك فازی دشواری بهینه سازی كدهای زبان سطح بالا می باشد. همگردان یک‌گذره (One-PassCompiler) کامپایلری است که برای تولید کد ماشین، تنها یک مرتبه متن برنامه را می‌‌خواند. دستور برخی زبان‌ها به گونه‌ای است که تولید همگردان یک‌گذره برای آنها غیر ممکن است. مجموعه همگردان های گنو یا Gnu compliercolection یا به صورت مخفف GCC مجموعه ای از همگردان های آزاد برای زبان های برنامه نویسی است. تقسم بندی كامپایلر ها به برنامه های كوچكتر تكنیكی است كه همچنان مورد بحث محققان است. در این نوع دسته بندی كامپایلر ها، انواع دیگری نیز وجود دارد:

· كامپایلر مبدا به مبدا كه كدی با زبان سطح بالا را دریافت می كند و خروجی آن نیز زبان سطح بالا می باشد. مثلا موازی سازی خودكار كامپایلر در مواردی كه به طور تكراری در برنامه ورودی وجود دارد و سپس تغییر شكل دادن كد و نوشتن كد یا ساختار زبانی موازی(برابر)با آن.(همچون دستور DOALL در فورترن) .

· كامپایلر Stage كه به زبان اسمبلی برای ماشین نظری ترجمه می كند. مثلا در Prolog

o ماشین پرولوگ معمولا ماشین انتزائی (WAM) خوانده می شود. بایت كدهای جاوا و Python زیر مجموعه ای از این دسته اند.

· كامپایلر زمان اجرا، برای سیستم های Smalltalk ، Java و زبان های میانه(CIL) در محصولات NET. استفاده می شود.

زبانهای تفسیری و كامپایلی

بسیاری از افراد زبانهای سطح بالا را به دو دسته تفسیری و كامپایلی تقسیم می كنند. كامپایلر ها و مفسر ها روی زبان ها عمل می كنند نه زبانها روی آنها! مثلا این تصور وجود دارد كه الزاما BASIC تفسیر می شود و C كامپایل. اما ممكن است نمونه هایی از BASIC یا C ارائه شود كه به ترتیب كامپایلری و تفسیری باشد. البته استثنا هایی نیز وجود دارد، مثلا برخی زبانها در خصوصیات خود این تقسیم بندی را مشخص كرده اند(C كامپایلری است یا SNOBOL4 و اكثر زبانهای اسكریپتی كه كد منبع زمان اجرا دارند تفسیری می باشد).

طراحی كامپایلر ها

تقسیم بندی پروسه های كامپایل به مجموعه ای از فاز ها مورد حمایت پروژه كامپایلری (( تولید كامپایلرهای باكیفیت ))(PQCC) از دانشگاه Carnegie Mellon قرار گرفت. در این پروژه اصطلاحات جلو بندی، میان بندی(امروزه به ندرت به كار میرود) و عقب بندی معرفی شد. اكثر كامپایلرهای امروزی بیش از دو فاز دارند. جلوبندی معمولا با پردازش املایی و معنایی شرح داده می شود. عقب بندی شامل تبدیل نوع و بهینه سازی های مختلف می باشد. سپس كد برای آن كامپیوتر خاص تولید می شود. استفاده از جلوبندی و عقب بندی این را ممكن می كند كه جلوبندی های مختلفی برای زبانهای مختلف وجود داشته باشد و عقب بندی های مختلفی نیز برای CPU های مختلف.

جلو بندی

جلوبندی به منظور تولید كد میانی یا IR از كد مبدا استفاده می شود. جلوبندی معمولا جدول نماد ها را مدیریت نموده و یك نگاشتگر ساختمان داده ای، هر نماد را از درون كد مبدا به اطلاعات مربوط به آن مثل نوع و دامنه تعریف آن نگاشت می شود. این امر در چند فاز انجام میگردد:

1. خط نوسازی. زبانهایی كه اجازه تعیین فضای اختیاری برای شناسه ها را می دهند قبل از عمل تجزیه نیاز به فاز اضافی دارند كه كد ورودی را به صورت متعارفی برای تجزیه گر آماده كند. Algol، Coral66، Atlas Autocode وImp نمونه هایی از این زبانه هستند كه به خط نوسازی (Line Reconstruction) نیازمند است.

2. پیش پردازش. برخی زبانها همچون C احتیاج به فاز پیش پردازش برای جایگزینی شروط كامپایل و ماكرو ها دارند.در زبان C فاز پیش پردازش شامل مرحله تحلیل لغوی می شود.

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

4. تحلیل نحوی شامل تجزیه كردن نشانه های مرتب جهت شناخت ساختار نحوی زبان می باشد.

5. تحلیل معنایی فازی است كه معنای برنامه را جهت رعایت قوانین زبان بررسی می كند. یك مثال برای این فاز كنترل نوع است.

عقب بندی

گاهی مرحله عقب بندی با مرحله تولید كد اشتباه گرفته می شود. اما می توان گفت كه عقب بندی به مراحل چند گانه زیر تقسیم می شود:

1. تحلیل كامپایلر: این پروسه برای بدست آوردن اطلاعات بیشتر از نمایش میانی فایل های ورودی می باشد. تحلیلگر نوعی تعاریف مختلفی دارد همچون تحلیلگر حلقوی، تحلیلگر وابسطه، تحلیلگر مستعار، تحلیلگر اشاره ای یا غیره می باشد. تحلیل دقیق زیر بنای هر كامپایلرهای بهینه است. گراف فراخوانی و نمودار جریان كنترل معمولا در فاز تجزیه تولید می گردد.

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

3. تولید كننده كد: زبان میانی تغییر كرده به زبان خروجی مثل زبان ماشین ترجمه می شود. این شامل تخصیص منابع و تصمیمات ذخیره سازی است، مثلا اینكه كدام متغیر به رجستر ها یا حافظه اختصاص یابد و گزینش و زمانبندی دستورات مناسب ماشین .

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

همگردان های نمونه

مجموعه همگردان گنو

gcc از ابتدا مخفف Gnu C Compiler بود ولی از زمانی که توانست زبانهای دیگری غیر از C از قبیل C++,Ada,Java,Objective C و Fortran را کامپایل کند بهGnu CompilerColection تغییر نام داد. پدید آورنده اصلی GCC ریچارد استالمن است کسی که بنیانگذار پروژه Gnu محسوب می شود. نخستین نسخه GCC در سال 1987 انتشار یافت که یک پیشرفت مهم محسوب می شد زیرا محصول جدید اولین کامپایلر بهینه سازی شده قابل حمل ANSI C به عنوان یک نرم افزار آزاد محسوب می شد. در سال 1992 نسخه 2.0 کامپایلر GCC عرضه شد. نسخه جدید قابلیت کامپایل کدهای ++C را نیز داشت. در سال 1997 یک انشعاب آزمایشی در GCC به نام EGCC به منظور بهینه سازی کامپیایلر و پشتیبانی کامل تر از ++C ایجاد شد. در ادامه EGCC به عنوان نسل بعدی کامپایلر GCC پذیرفته شد و تکامل آن باعث انتشار نسخه سوم GCC در سال 2004 گردید. چهارمین نسخه از کامپایلر GCC در سال 2005 عرضه شد.