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

هدف:

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

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

تواناییهای فارغ التحصیلان

فارغ التحصیلان این مقطع، قابلیتها و تواناییهای زیادی دارند و چنانچه در مسیر مناسب هدایت شوند، قادر خواهد بود مشکلات زیادی را حل کنند. برخی از این تواناییها به شرح زیر است:

۱) بررسی و شناخت نرم افزارها و سخت افزارهای جدید و به کارگیری آنها.

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

۳) تجزیه و تحلیل سیستمهای کوچک و متوسط نرم افزاری و سخت افزاری و ارائه راه حل مناسب برای اجرای آنها.

۴) طراحی مجموعه های کوچک و متوسط نرم افزاری و سخت افزرای و تولید طرحهای اجرایی برای انها.

۵) اجرای طرحهای کامپیوتری، نصب، آزمایش و آموزش آنها.

۶) پشتیبانی و نگه داری سیستمهای نرم افزاری شامل شناسایی خطاها، رفع خطاها و افزودن امکانات جدید به سیستمها.

۷) عیب یابی کامپیوترها و سیستمهای کامپیوتری و رفع عیبها.

۸) شناسایی فنون جدید طراحی و ساخت کامپیوتر و ارزیابی و به کارگیری آنها.

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

ماهیت:

کامپیوتر دارای دو جزء متفاوت سخت افزار و نرم افزار است. اجزاء فیزیکی و قابل لمس کامپیوتر مانند مدارها و بردهای الکترونیکی سخت افزار نامیده می شوند.

نرم افزار جزء غیرقابل لمس کامپیوتر است. نرم افزار برنامه ها و داده هایی است که به کامپیوتر فرمان می دهند که چه عملی را انجام دهد. یک مهندس نرم افزار یاد می گیرد که چگونه نرم افزارهای بزرگ و عظیم را طراحی و برنامه ریزی کند، تست و ارزیابی نهایی نماید و در نهایت مستند سازد.

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

“نرم افزار در حقیقت روح و جان کامپیوتر است که به سخت افزار هویت می بخشد و اصولاً به برنامه ای گفته می شود که برای به کارگیری سخت افزار ساخته شده باشد.

نرم افزارها را می توان به دوره کلی دسته بندی کرد که عبارتند از : نرم افزارهای سیستمی و نرم افزارهای کاربردی.

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

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

“مهندسی سخت افزار در مقطع لیسانس به مطالعه و بررسی طراحی سخت افزاری، کنترل سخت افزاری و شبکه های کامپیوتری می پردازد. برای مثال یک مهندس سخت افزار می تواند طراحی سخت افزاری کند که با IC ها کار کند، با کامپیوتر کار کند و یا از دروازه های کامپیوتر استفاده نماید و در نهایت می تواند به طراحی مدارهای مجتمع دیجیتالی بپردازد. که البته به این بخش از سخت افزار بیشتر در مقطع کارشناسی ارشد و دکتری پرداخته می شود.”

گرایش های مقطع لیسانس:

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

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

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

آینده شغلی، بازار کار، درآمد:

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

توانایی های جسمی، علمی، روانی و … مورد نیاز و قابل توصیه

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

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

توانایی مالی: با توجه به توضیحات گفته شده داشتن یک دستگاه کامپیوتر برای یک مهندس کامپیوتر امری ضروری به نظر می رسد ولی این گونه نیست که بدون داشتن کامپیوتر دانشجویان از ادامه تحصیل و پیشرفت باز بمانند.

وضعیت نیاز کشور به این رشته در حال حاضر:

رشته کامپیوتر که باعث جهانی شدن اطلاعات و ارتباطات شده است ، رشته روز و رشته آینده است تا جایی که پیش بینی می شود تا ۱۰ سال دیگر در کشورهای پیشرفته مردم همان قدر که بر نیروی برق وابسته هستند به شبکه اینترنت وابسته خواهند شد. با توجه به توضیحات گفته شده روند رو به رشد استفاده از کامپیوتر در زندگی روزانه اشتغال و موقعیت کاری برای فارغ التحصیلان این رشته فراهم است تا در قالب شرکتهای تولیدکننده نرم افزار، شرکتهای تولیدکننده قطعات، مراکز صنعتی – تولیدی، شرکتها و موسسات خدماتی، مراکز آموزشی و … مشغول به کار شده و فعالیت کنند. با توجه به پیشرفت کند ایران نسبت به جامعه جهانی کامپیوتر در سالهای اخیر نیاز به مهندسین خلاق و کوشا در این زمینه کاملاً احساس می شود.

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

 

نکات تکمیلی:

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

ریاضیات

نظریه گراف

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

این سوال که آیا مسائل کلاس P دقیقا همان مسائل کلاس NP می باشند، یکی از مهم ترین سوال‌های بدون جواب علوم کامپیوتری می‌باشد. به بیانی دیگر اگر همیشه به این سادگی باشد که بتوان صحت یک راه‌حل را بررسی کرد، آیا پیدا کردن راه‌حل نیز می‌تواند به آن سادگی باشد؟ برای این سوال یک جایزه ۱ میلیون دلاری از طرف انسیتیتو ریاضی 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 نیز به عنوان محال یا نشدنی خواهند بود. برای ملموس‌تر شدن این مساله فرض کنید که یک مساله ۲n مرحله لازم دارد تا حل شود (n اندازه ورودی می‌باشد). برای مقادیر کوچک n=100 و با در نظر گرفتن کامپیوتری که ۱۰۱۰ (۱۰ giga) عملیات را در یک ثانیه انجام می‌دهد، حل کردن این مساله زمانی حدود ۱۰۱۲ * ۴ سال طول خواهد کشید، که این زمان از عمر فعلی جهان بیشتر است!

 چرا حل مسائل 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 مقایسه نیاز دارند.
  • حافظه (و سایر منابع کامپیوتر): بعضی از الگوریتم‌های مرتب‌سازی «در جا[۱]» هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظهٔ کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتم‌ها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.
  • پایداری[۲]: الگوریتم‌های مرتب‌سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ می‌کنند. فرض کنید می‌خواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نام‌های الف و ب هم‌سن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.
  • مقایسه‌ای بودن یا نبودن. در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب می‌شوند.
  • روش کلی: درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و مرتب‌سازی سریع و گزینشی مانند مرتب‌سازی پشته‌ای.

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

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

(به انگلیسی: 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;        } }                                                }

 

پیشنهاد می کنیم :  دانلود رایگان مقاله دلیل مهم برای نصب Xp Service pack ۲

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

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

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

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

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

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

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

پیاده سازی مرتب سازی 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 گوییم.

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

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

تاریخچه

کامپیوتر های اولیه از کامپایلر ها استفاده نمی کردند، چرا که این کامپیوتر ها حافظه کوچکی داشتند و با برنامه های کوتاه سر و کار داشتیم. کاربران مجبور بودند کد باینری یا دسیمال برنامه ها را به طور مستقیم و با کمک نوار های مغناطیسی به سیستم وارد کنند. اما برنامه نویس ها زیاد این وضعیت را تحمل نکردند و به فکر تولید برنامه ای افتادند که کاراکتر های الفبایی(واژه های اختصاری) را به تعدادی دستور که قابل اجرا توسط ماشین باشد تبدیل کند. در این وضعیت بود که زبان های اسمبلی و کامپایلر های اولیه با نام اسمبلر به وجود آمد. در اواخر دهه ۹۰ بود که ماشین های وابسطه به زبانهای زبانهای برنامه نویسی رونق گرفتند. متعاقبا کامپایلرهای آزمایشی ایجاد شدند. FORTRAN به سرپرستی John Backus در شرکت IBM به عنوان اولین کامپایلر کامل را در سال ۱۹۵۷ تولید شد. کوبول اولین زبان کامپایلی با معماری چندگانه در سال ۱۹۶۰ تولید شد. در طی دهه ۶۰ کامپایلر های زیادی تولید شد اما بر روی کیفیت کامپایلر ها کمتر فکر می شد. همزمان با تکامل زبان های برنامه سازی و افزایش قدرت کامپیوتر ها، کامپایلرها هرچه بیشتر پیچیده می شدند. یک کامپایلر خود برنامه ای است که توسط زبان پیاده ساز تولید شده است. اولین کامپایلر خود محور که می توانست کد خود را کامپایل کند برای زبان Lisp و توسط Hart و Levin در سال ۱۹۶۲ و در دانشگاه MIT ایجاد شد. در دهه ۷۰ از زبانهای سطح بالایی مثل Pascal و C جهت نوشتن کامپایلر ها استفاده شد. ساخت کامپایلر های خود محور دارای مشکل راه اندازی است، چونکه هر کامپایلری باید توسط کامپایلر نوشته شده ای به زبان دیگر کامپایل شود یا برای این مشکل دست به دامن مفسری بشود. ساختار کامپایلر ها و کامپایلر بهینه ساز امروزه بخشی از برنامه درسی دانشجویان کامپیوتر است. برخی کامپایلر ها به منظور آموزشی برای زبان های برنامه نویسی تولید می گردد. مثلا کامپایلر PL/0 توسط Niklaus Wirth برای آموزش در دهه ۱۹۷۰ به کار رفت. به علت سادگی و دلایل زیر هنوز برای آموزش مورد استفاده قرار می گیرد:

  • توسعه گام به گام برنامه
  • به کار گیری پارسر های بازگشتی
  • استفاده از EBNF جهت تعریف نحو زبان
  • استفاده از P-Code در جریان تولید کد خروجی قابل حمل
  • نمایش T-diagram جهت تعارف رسمی

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

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

از ۱۹۴۵تا۱۹۶۰:تولید کد

 

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

از ۱۹۶۰تا۱۹۷۵ :تجزیه کردن

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

از ۱۹۷۵ تاکنون :تولید کد و بهینه سازی کد

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

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

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

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

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

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

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

  • کامپایلر مبدا به مبدا که کدی با زبان سطح بالا را دریافت می کند و خروجی آن نیز زبان سطح بالا می باشد. مثلا موازی سازی خودکار کامپایلر در مواردی که به طور تکراری در برنامه ورودی وجود دارد و سپس تغییر شکل دادن کد و نوشتن کد یا ساختار زبانی موازی(برابر)با آن.(همچون دستور DOALL در فورترن) .
  • کامپایلر Stage که به زبان اسمبلی برای ماشین نظری ترجمه می کند. مثلا در Prolog
    • ماشین پرولوگ معمولا ماشین انتزائی (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 Compiler Colection تغییر نام داد. پدید آورنده اصلی GCC ریچارد استالمن است کسی که بنیانگذار پروژه Gnu محسوب می شود. نخستین نسخه GCC در سال ۱۹۸۷ انتشار یافت که یک پیشرفت مهم محسوب می شد زیرا محصول جدید اولین کامپایلر بهینه سازی شده قابل حمل ANSI C به عنوان یک نرم افزار آزاد محسوب می شد. در سال ۱۹۹۲ نسخه ۲٫۰ کامپایلر GCC عرضه شد. نسخه جدید قابلیت کامپایل کدهای ++C را نیز داشت. در سال ۱۹۹۷ یک انشعاب آزمایشی در GCC به نام EGCC به منظور بهینه سازی کامپیایلر و پشتیبانی کامل تر از ++C ایجاد شد. در ادامه EGCC به عنوان نسل بعدی کامپایلر GCC پذیرفته شد و تکامل آن باعث انتشار نسخه سوم GCC در سال ۲۰۰۴ گردید. چهارمین نسخه از کامپایلر GCC در سال ۲۰۰۵ عرضه شد.

هوش مصنوعی