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

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

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

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

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

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

ماهیت:
کامپیوتر دارای دو جزء متفاوت سخت افزار و نرم افزار است.

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

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

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

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

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

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

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

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

به خصوص مهندسین نرم افزار فرصت های شغلی بیشتری داشته و برای کارکردن نیاز به امکانات و تجهیزات زیادی ندارند.

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

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

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

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

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

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

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

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

طراحی، شبیه سازی، فرآوری، پردازش، سنجش، آموزش، ویرایش و ...

لذا هدف از این رشته تربیت نیروی متخصص برای انجام امور فوق است.

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

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

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

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

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

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

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

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

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

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

ماهیت: کامپیوتر دارای دو جزء متفاوت سخت افزار و نرم افزار است.

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

نرم افزار جزء غیرقابل لمس کامپیوتر است.

یک مهندس نرم افزار یاد می گیرد که چگونه نرم افزارهای بزرگ و عظیم را طراحی و برنامه ریزی کند، تست و ارزیابی نهایی نماید و در نهایت مستند سازد.

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

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

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

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

نرم افزارهای کاربردی نیز برنامه هایی هستند که کاربر یا خود آن ها را می نویسد یا شرکت های نرم افزاری آنها را تهیه کرده و برای فروش عرضه می کنند.

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

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

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

از طرفی با توجه به استفاده روزافزون از شبکه اینترنت زمینه کار در این موضوع نیز بسیار مهیاست.

توانایی های جسمی، علمی، روانی و ...

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

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

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

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

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

وضعیت نیاز کشور به این رشته در حال حاضر: رشته کامپیوتر که باعث جهانی شدن اطلاعات و ارتباطات شده است ، رشته روز و رشته آینده است تا جایی که پیش بینی می شود تا 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 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 if (arr[ max ] max = j; ; ] temp = arr[ i arr[ i ] = arr[ max]; arr[ max ] = temp; } } ۳ - مرتب سازی (Shell Sort) نام این الگوریتم از نام مخترع آن گرفته شده‌است.

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