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

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

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

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

شمایی از یک کامپایلر

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

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

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

در اواسط دهه ۱۹۵۰ کامپایلرها به عنوان برنامه‌هایی دشوار شناخته شده بودند. اولین کامپایلر فرترن، به عنوان مثال ۱۸ سال زمان برای طراحی صرف نمود. از آن زمان روش‌های سیستماتیک برای استفاده از بسیاری اعمال مهم حین عمل کمپایل ابداع شده‌است. همچنین زبان‌های پیاده‌سازی خوب، محیط‌های برنامه نویسی و ابزارهای نرم‌افزاری مناسب ایجاد شده‌اند. با کمک این پیشرفت‌ها یک کامپایلر را می‌توان حتی به عنوان پروژه درسی در یک ترم تحصیلی دانشجویی طراحی نمود.

تاریخچه

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

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

یک کامپایلر خود برنامه‌ای است که توسط زبان پیاده ساز تولید شده‌است. اولین کامپایلر خود محور که می‌توانست کد خود را کامپایل کند برای زبان Lisp و توسط Hart و Levin در سال ۱۹۶۲ و در دانشگاه MIT ایجاد شد. در دهه ۷۰ از زبانهای سطح بالایی مثل پاسکال و سی جهت نوشتن کامپایلرها استفاده شد. ساخت کامپایلرهای خود محور دارای مشکل راه اندازی است، چونکه هر کامپایلری باید توسط کامپایلر نوشته شده‌ای به زبان دیگر کامپایل شود یا برای این مشکل دست به دامن مفسری بشود.

ساختار کامپایلرها و کامپایلر بهینه ساز امروزه بخشی از برنامه درسی دانشجویان کامپیوتر است. برخی کامپایلرها به منظور آموزشی برای زبان‌های برنامه نویسی تولید می‌گردد. مثلاً کامپایلر PL/۰ توسط 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 کامپایلری است یا SNOBOL۴ و اکثر زبانهای اسکریپتی که کد منبع زمان اجرا دارند تفسیری می‌باشد).

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

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

جلو بندی

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

1. خط نوسازی. زبانهایی که اجازه تعیین فضای اختیاری برای شناسه‌ها را می‌دهند قبل از عمل تجزیه نیاز به فاز اضافی دارند که کد ورودی را به صورت متعارفی برای تجزیه گر آماده کند. Algol، Coral۶۶، 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 Collection تغییر نام داد. پدید آورنده اصلی GCC ریچارد استالمن است کسی که بنیانگذار پروژه Gnu محسوب می‌شود. نخستین نسخه GCC در سال ۱۹۸۷ انتشار یافت که یک پیشرفت مهم محسوب می‌شد زیرا محصول جدید اولین کامپایلر بهینه سازی شده قابل حمل ANSI C به عنوان یک نرم‌افزار آزاد محسوب می‌شد. در سال ۱۹۹۲ نسخه ۲٫۰ کامپایلر GCC عرضه شد. نسخه جدید قابلیت کامپایل کدهای ++C را نیز داشت. در سال ۱۹۹۷ یک انشعاب آزمایشی در GCC به نام EGCC به منظور بهینه سازی کامپیایلر و پشتیبانی کامل تر از ++C ایجاد شد. در ادامه EGCC به عنوان نسل بعدی کامپایلر GCC پذیرفته شد و تکامل آن باعث انتشار نسخه سوم GCC در سال ۲۰۰۴ گردید. چهارمین نسخه از کامپایلر GCC در سال ۲۰۰۵ عرضه شد.

مهندسی نرم‌افزار پیشه‌ای است که به یاری دانش رایانه و دیگر فناوری‌ها و روش‌ها به آفریدن و نگاهداری نرم‌افزار رایانه‌ای می‌پردازد.

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

• الزام های تعیین شده
• در زمان تعیین شده
• در محدودهٔ بودجه پیش‌بینی شده

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

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

فناوری‌ها و خدمات مهندسی نرم‌افزار به کاربران برای بهبود بهره‌وری و کیفیت یاری میرساند. نمونه‌هایی از زمینه‌های بهبود: پایگاه داده‌ها، زبان‌ها، کتابخانه‌ها، الگوها، فرآیندها و ابزار.

پیشینه مهندسی نرم‌افزار

اصطلاح مهندسی نرم‌افزار بعد از سال ۱۹۶۸ شناخته شد. این اصطلاح طی کنفرانس «مهندسی نرم‌افزار ناتو ۱۹۶۸» (که در گارمیش آلمان برگزار شد) توسط ریاست کنفرانس F.L. Bauer معرفی شد و از آن پس بطور گسترده مورد استفاده قرار گرفت.

اصطلاح مهندسی‌نرم‌افزار عموماً به معانی مختلفی به کار می‌رود:

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

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

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

• مهندسی نرم‌افزار عبارتست از : الف) کاربرد یک رویکرد سیستماتیک، انتظام یافته، قابل سنجش نسبت به توسعه، عملکرد و نگهداری نرم‌افزار، که کاربرد مهندسی در نرم‌افزار است و ب) مطالعه روشهای موجود در استاندارد IEEE

محدوده مهندسی نرم‌افزار و تمرکز آن

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

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

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

نیاز به مهندسی نرم‌افزار

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

تکنولوژی‌ها و روشهای عملی

مهندسین نرم‌افزار طرفدار تکنولوژی‌ها و روشهای عملی بسیار متفاوت و مختلفی هستند، که با هم ناسازگارند. این بحث در سالهای دهه ۶۰ میلادی شروع شد و ممکن است برای همیشه ادامه پیدا کند. مهندسین نرم‌افزار از تکنولوژی‌ها و روشهای عملی بسیار متنوعی استفاده می‌کنند. کسانی که کار عملی می‌کنند از تکنولوژی‌های متنوعی استفاده می‌کنند : کامپایلرها، منابع کد، پردازشگرهای متن. کسانی که کار عملی می‌کنند از روشهای عملی بسیار متنوعی استفاده می‌کنند تا تلاشهایشان را اجرا و هماهنگ کنند : برنامه نویسی در دسته‌های دونفری، بازبینی کد، و جلسات روزانه. هدف هر مهندس نرم‌افزار بایستی رسیدن به ایده‌های جدید خارج از مدلهای طراحی شده قبلی باشد، که باید شفاف بوده و بخوبی مستند شده باشد.

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

ماهیت مهندسی نرم‌افزار

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

دیوان فعالیتهای آماری آمریکا مهندسان نرم‌افزار را به عنوان زیرگروهی از «متخصصین کامپیوتر»، با فرصت‌های شغلی‌ای مانند «دانشمند کامپیوتر»، «برنامه نویس» و «مدیر شبکه» دسته بندی کرده‌است. BLS تمام مهندسین دیگر این شاخه علمی، که شامل مهندسین سخت‌افزار کامپیوتر نیز هست، را به‌عنوان «مهندسین» دسته بندی می‌کند.

توضیحات پایه

یک ماشین، یک مدل ریاضی از ماشین با حالات متناهی (FSM) است. یک ماشین شامل مجموعه‌ای متناهی از حالات است که بر اساس ورودی و تابع گذار خود (که می‌تواند به صورت جدول باشد)، از یک حالت به حالت دیگر، تغییر وضعیت می‌دهد. این تابع انتقال به ماشین خودکار می‌گوید که به کدام حالت بعدی با توجه به حالت فعلی و نماد داده شده، برود.

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

در ادامه تعریفی مقدماتی از یک نوع اتوماتا می‌باشد که به فهم مفاهیم ضروری مورد بحث در نظریهٔ ماشین‌ها کمک می‌کند.

 تعاریف پایه نظریه ماشین‌ها

 شرح غیر قراردادی

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

 شرح قراردادی

 واژگان

• نماد: کوچک‌ترین و بنیادی‌ترین موجودیتی که دارای معنی یا تأثیری بر ماشین است. برخی مواقع به نمادها حرف هم گفته می‌شود.

• الفبا: یک مجموعه متناهی از نمادها که در یک زبان تعریف شده‌اند. الفبای زبان توسط Σ نشان داده می‌شود.

• کلمه: دنباله‌ای متناهی از نمادهای یک الفباست که با عمل الحاق به هم پیوسته‌اند.

• زبان: مجموعه‌ای از رشته‌ها است. این مجموعه می‌تواند متناهی یا نامتناهی باشد.

 ماشین

۵ تایی نمایندهٔ یک ماشین خودکار است که در آن:

• Q مجموعه‌ای از حالات است.
• ∑ یک مجموعهٔ کراندار از نمادهاست که ما آن را الفبای زبانی که ماشین خودکار می‌پذیرد، می‌نامیم.
• δ تابع گذار است که

(برای ماشین خودکار غیر قطعی، یک رشتهٔ خالی نیز یک ورودی قابل قبول است)

• q₀ حالت شروع است، یعنی حالتی از ماشین خودکار که در آن، هیچ یک از ورودی‌ها هنوز پردازش نشده‌است (بدیهی است که )
• F مجموعه‌ای از حالات Q است (برای مثال F⊆Q) که وضعیت‌های قبول نامیده می‌شوند.

با داشتن حرف ورودی a که می‌توان تابع گذار را به صورت نوشت. که این کار با استفاده از ترفند سادهٔ مالش صورت می‌گیرد (ترفند مالش عبارت است از نوشتن δ(q,a) = δ_aq به ازای همهٔ ). با این روش، تابع گذار به فرم ساده تری تبدیل می‌شود. ترکیب تابع تکرار شده یک مونوئید را تشکیل می‌دهد. برای توابع گذار، این مونوئید تحت نام مونوئید گذار یا در بعضی مواقع نیم گروه دگرسازیشناخته می‌شود.

 کلمهٔ ورودی

ماشین یک رشتهٔ متناهی از نمادهای a₁,a₂,....,a_n را که می‌خواند که کلمهٔ ورودی گفته می‌شود. مجموعهٔ تمام کلمات با *Σ مشخص می‌شود. گاهی اوقات یک کاراکتر خاص برای مشخص کردن انتهای یک رشته به کار می‌رود (بعضی اوقات با λ نمایش داده می‌شود) که همچنین در الفبا نیز موجود است.

 اجرا

یک اجرا ماشین بر روی یک کلمهٔ ورودی، یک دنباله از حالت هایq₀,q₁,q₂,....,q_n است که ، به طوری که q₀ حالت شروع است و برای داریم q_i = δq_{i − 1},a_i . به عبارت دیگر در ابتدا ماشین در حالت شروع q₀ است و بعد ماشین دنباله وار نمادهای کلمهٔ ورودی را می خواند. وقتی ماشین نماد a_i را می خواند به حالت q_i = δq_{i − 1},a_i جهش می کند. q_n حالت نهایی اجرا گفته می شود.

 کلمهٔ مورد قبول

یک کلمه توسط ماشین مورد قبول است اگر .

 زبان شناخته شده

یک ماشین می تواند یک زبان رسمی(formal language) را تشخیص دهد. یک زبان شناخته شده توسط یک ماشین مجموعه ای از کلمات است که برای ماشین پذیرفته باشد.

 زبان‌های قابل تشخیص

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

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

این ساختار می‌تواند معکوس هم بشود، با داشتن ، می‌توان دوباره δ را ساخت و بنابراین، این دو توصیف هم ارزند.

سه تایی تحت نام ماشین نیمه خودکار شناخته می‌شود. ماشین نیمه خودکار همان ماشین خودکار است با این تفاوت که وضعیت شروع و مجموعهٔ وضعیت‌های قبول آن نادیده گرفته شده اند. مفهوم‌های افزودهٔ وضعیت اولیه و وضعیت قبول باعث می‌شوند تا توانائی ماشین خودکار بیش از توانائی ماشین نیمه خودکار باشد، بدین شرح که ماشین نیمه خودکار نمی‌تواند یک زبان‌های فرمال را شناسائی کند. زبان L که توسط ماشین خودکار قطعی کراندارپذیرفته شده است، این گونه تعریف می‌شود:

توضیح اینکه، زبان پذیرفته شدهٔ ماشین خودکار(یعنی L) مجموعه‌ای از کلمات w است که با الفبای Σ ساخته شده اند و وقتی به عنوان ورودی به ماشین خودکار داده می‌شوند، نهایتا یکی از وضعیت‌های F را نتیجه می‌دهند. زبانهایی را که توسط ماشین خودکار پذیرفته شده اند، زبان‌های قابل تشخیص می نامند.

وقتی مجموعهٔ وضعیت‌های Q کراندار است، ماشین خودکار به عنوان ماشین خودکار وضعیت محدود شناخته می‌شود و مجموعهٔ همهٔ زبان‌های قابل تشخیص آن را، زبان‌های باقاعده می نامیم. در واقع یک هم ارزی قوی وجود دارد: به ازای هر زبان باقاعده یک ماشین خودکار وضعیت محدود وجود دارد.

 انواع ماشین‌های خودکار کراندار

در زیر، سه نوع از ماشین‌های خودکار کراندار ذکر شده است

ماشین‌های خودکار کراندار قطعی

هر وضعیت از یک ماشین خودکار از این نوع، یک گذار برای هر نشانه دارد.

ماشین‌های خودکار کراندار غیر قطعی

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

ماشین‌های خودکار کراندار غیر قطعی با ε-گذار

علاوه بر اینکه می‌توانند با هر نشانه‌ای به وضعیت‌های بیشتری( یا هیچ وضعیتی) پرش کنند، این ماشین‌ها می‌توانند که به روی هیچ نشانه‌ای پرش نکنند. به این معنا که، اگر یک وضعیت گذارهای نامگذاری شده با ε را دارد، این ماشین می‌تواند در هر وضعیتی که به وسیلهٔ ε-گذار بدست آمده قرار گیرد که این کار می‌تواند با واسطه یا بدون واسطهٔ وضعیت‌های دیگر صورت گیرد. مجموعهٔ وضعیت هایی که می‌توان به وسیلهٔ این شیوه از وضعیت q بدست آورد، ε-بستار برای qنامیده می‌شود.

با این وجود می‌توان نشان داد که تمام این ماشین ها، می‌توانند زبان‌های مشابهی را بپذیرند.

 گسترهٔ ماشین‌های متناهی

خانوادهٔ زبان هایی که با ماشین‌های توصیف شده در بالا پذیرفته می‌شوند، خانوادهٔ زبان‌های باقاعده نامیده می‌شوند. هر چه یک ماشین قوی تر باشد، می‌تواند زبان‌های پیچیده تری را بپذیرد. ماشین‌های خودکار این چنینی عبارتند از:

ماشین‌های خودکار پائین فشردنی

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

ماشین‌های خودکار کراندار خطی

یک ماشین خودکار کراندار خطی، یک ماشین تورینگمحدود شده است که در آن، به جای یک نوار نامتناهی، فضایی متناسب با اندازهٔ رشتهٔ وارد شده، بر روی نوار وجود دارد. این ماشین‌ها زبان‌های حساس به متن را می پذیرند.

ماشین‌های تورینگ

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

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

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

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

شاخه بندی

متدهای حل معادلات دیفرانسیل بسیار مرتبط با نوع معادله هستند. معادلات دیفرانسیل را به طور کلی به دو دسته می توان تقسیم کرد.

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

معادلات دیفرانسیل جزیی: در این نوع معادلات تابع جواب دارای چندین متغیر مستقل می باشد.

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

معادلات دیفرانسیل مشهور

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

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

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

بازیابی اطلاعات (به انگلیسی: Information Retrieval) به فن‌آوری و دانش پیچیدهٔ جستجو و استخراج اطلاعات، داده‌ها، فراداده‌ها در انواع گوناگون منابع اطلاعاتی مثل بانک اسناد، مجموعه‌ای از تصاویر، و وب گفته می‌شود.

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

جستجوگرهای گوگل، یاهو و بینگ سه نمونه از پراستفاده‌ترین سیستم‌های بازیابی اطلاعات هستند که به کاربران برای بازیابی اطلاعات متنی، تصویری، ویدئویی و غیره کمک می‌کنند.

«بازیابی اطلاعات» در برخی منابع فارسی به اشتباه به جای ذخیره و بازیابی داده‌ها که به معنای دانش شناخت رسانه‌های ذخیره‌سازی فیزیکی است، به کار رفته است.

مدل‌سازی اطلاعات

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

• مدل دودویی (یا دوگانی): در مدل دودویی (یا دوگانی) هر سند (document) به صورت کیفی پر از کلمات (bag of words) در نظر گرفته می‌شود.
• مدل بُرداری: در مدل بُرداری، هر سند به صورت برداری از کلمات در یک فضای برداری چند بُعدی در نظر گرفته می‌شود که ابعاد آنرا کلمات تشکیل می‌دهند. مولفه‌های این بردار سند، در واقع وزن هایی هستند که نشان می‌دهند هر یک از کلمات چقدر در متمایز کردن آن سند دخیل هستند.
• مدل احتمالاتی: در مدل احتمالاتی، به هر سند احتمالی اختصاص داده می‌شود که مربوط بودن آن مستند را به نیاز کاربر به صورت احتمال بین صفر و یک بیان می‌کند.

تعیین میزان ربط هر سند به نیاز اطلاعاتی کاربر

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

مدل دودویی

در مدل دودویی، نیاز اطلاعاتی کاربر به صورت عبارتی منطقی با عملگرهای AND و OR و NOT بیان می‌شود و هر سندی که این عبارت در مورد آن صحیح باشد بازیابی می‌شود. مثلاً اگر نیاز اطلاعاتی به صورت Iran AND Oil بیان شود، تمامی اسنادی که هردو کلمهٔ Iran و Oil را دربردارند به کاربر نمایش داده می‌شوند. در مدل دودویی سند یا باربط است یا نیست، و هیچ معیاری برای سنجش میزان (درجهٔ) ربط وجود ندارد. مثلاً دو سند را در نظر بگیرید که یکی تماما دربارهٔ ایران و نفت بحث می‌کند، و دیگری در مورد اقتصاد جهانی صحبت می‌کند و فقط از نام ایران و نفت به عنوان مثالی در یک جمله استفاده کرده است. سیستمی که از مدل دودویی استفاده کرده تفاوتی بین این دو سند قائل نخواهد شد. در صورتیکه در واقع سند اول بیشتر به نیاز کاربر مربوط است.

مدل بُرداری

در مدل برداری، برای سنجش میزان ربط اسناد و نیاز اطلاعاتی کاربر، سیستم اسناد موجود و پُرسهٔ کاربر را در فضای چند بعدی مدل‌سازی می‌کند. در نتیجه برای سنجش میزان شباهت میان بُردار پُرسه و بردار هر سند می‌توان از زاویه‌ای که این دو بردارها با هم می‌سازند استفاده کرد. اسنادی که بردارشان با بردار پرسهٔ کاربر زاویه کوچکتری می‌سازد بیشتر با نیاز اطلاعاتی کاربر هم جهت هستند و در نتیجه مرتبط‌تر خواهند بود. برتری این مدل این است که به سیستم امکان درجه‌بندی میزان ارتباط اسناد با پرسه را می‌دهد.

مدل احتمالاتی

در مدل احتمالاتی هم به ازای هر نیاز اطلاعاتی، تمامی اسناد بر اساس احتمال این که با نیاز اطلاعاتی مرتبط باشد مرتب می‌شوند و لیست اسناد در نهایت به صورت درجه‌بندی شده (مانند مدل برداری) به کاربر نمایش داده می‌شود، به نحوی که اولین سندی که کاربر می بیند از همه بیشتر احتمال دارد که به نیاز او ربط داشته باشد.

تفاوت بازیابی داده و بازیابی اطلاعات

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

معیارهای ارزیابی

• معیار دقت: به حاصل تقسیم «تعداد مستندات بازیابی شدهٔ واقعاً باربط» بر «تعداد کل مستندات بازیابی شده» گفته می‌شود.
• معیار بازخوانی: به حاصل تقسیم «تعداد مستندات بازیابی شدهٔ باربط» بر «تعداد کل مستندات باربطی که در مجموعهٔ اطلاعاتی موجود بوده است» گفته می‌شود.

اگر عناصر تشکیل دهندهٔ مدار الکتریکی باشند، مدار الکتریکی نامیده می‌شود، و اگر عناصر الکتریکی و الکترونیکی باشند، مدار الکترونیکی است .

هر مدارالکتریکی از اجزای اصلی زیر تشکیل شده است:

1. یک منبع تغذیه‌الکتریکی مانند باتری یا ژنراتور
2. سیم‌های رابط: سیم‌ها یا نوارهای ارتباط دهنده مدار، از یک ماده رسانای الکتریسیته خوب مانند مس تشکیل می‌شوند.
3. مصرف کننده یا بار: وقتی می‌گوییم یک مدار الکتریکی تشکیل شده است، که اتصال دهنده‌ها و سایر قطعات، یک حلقه بسته را بوجود آورده باشند. تنها در این صورت است که جریان برق برقرار می‌شود.
4. المانهای مداری: همچون خازن، مقاومت، سلف، ترانسفورماتور، دیود

مدارهای الکترونیکی (به انگلیسی: Electronic circuit) به همراه مدارهای الکتریکی دو دستهٔ کلی از مدارات به‌شمار می‌روند. در مدارهای الکتریکی محیط حرکت الکترون و به طور کلی جنس تشکیل دهنده اجزا مدار به هیچ عنوان اهمیت ندارند، بلکه، رابطه ریاضی بین ولتاژ و جریان این اجزای الکترونیکی مهم هستند. در حقیقت، در تحلیل این مدارها کمتر به ساختمان این قطعات توجه می‌شود.

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

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

ساختمان داده‌ها (به انگلیسی: Data Structure) از جملهٔ بنیادی‌ترین مباحث مورد نیاز جهت یادگیری و درک بسیاری از مفاهیم عمده در علوم رایانه است.

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

موارد زیر از جمله مهمترین ساختمان داده‌ها هستند:

• آرایه (Array)
• صف (Queue)
• پشته (Stack)
• لیست پیوندی (Linked list)
• گراف (Graph)
• درخت (Tree)

اصول اساسی

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

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

مجموعه‌ها با ترتییب جزئی (poset):

یک رابطه R در A ترتیب جزئی خواهیم گفت هرگاه بازتابی، نامتقارن ومستعدی باشد مجموعه A را بهمراه ترتیب جزیی R، مجموعه با ترتیب جزیی گفته و آنرا (R,A) نمایش خواهیم داد. معروفترین ترتیب جزیی، روابط≥,≤ در R می باشند. بدین دلیل، وقتی که در حالت عمومی جهت از ترتیب جزیی R می‌شود، ما اغلب سمبولهای ≥,≤ رابکار خواهیم بود. این مطلب، بخاطر سپردن ویژگیهای R را ساده تر و آشنا تر می کندئ . سمبول ≤ می تواند برای ترتیب‌های جزیی متفاوت در مجموعه‌های متفاوت بکار برده شود. بنابراین، نباید این سمبولها را با رابطه متفاوت ≤ و یا ≥ در و یا در R اشتباه کرد. اگر الزامی به تمیز دادن ترتیب‌های جزیی از یکدیگر باشد، و این ترتیب‌های جزیی را با (≥ , ≥_1 ) ́ , ≤ ́ , ≤_1 و غیره نمایش خواهیم داد.

اگر (A ,≤) یک مجموعه با ترتیب جزیی باشد، در این صورت ماهواره سمبول ≥ را برای دادن ترتیب جزیی بکار خواهیم بود، در نتیجه (A ,≥) دو گان (A ,≤) خواهد بود. بهمین طریق دو گان (A ,≤) با (A ,≤)، دو گان (B ,≤) با (B ,≤) نمایش داده خواهند شد.

اگر (A ,≤) یک مجموعه با ترتیب جزیی باشد، عناصر a و b را قابل مقایسه خواهیم داشت . (b ,≤a) یا (a ,≤b)

دقت کنید که در یک poset لزومی ندارد که هر زوج از عناصر قابل مقایسه باشند.

اگر (A ,≤) و (B ,≤) ودو poset باشند در این صورت (A ,≤) فیزیک poset است که در آن ترتیب جزیی بصورت زیر تعریف شده است :

(a,b) ≤ (a ́,b ́) اگر B b≤b ,A a≤a

دقت کنید که سمبول ≤ بعنوان سه ترتیب جزیی متفاوت بکار رفته است خواننده براحتی می تواند در هر لحظه تعیین کنید که کدامیک از آنها مورد نظر است .

اگر (A ,≤) یک poset باشد، گوییم که a

بدین تریب را ترتیب قاموسی و یا ترتیب دیکسیونری می خوانند . وقتی که A و B مجموعه‌های کاملا مرتب باشند، در این صورت ترتیب قاموسی در A*B فیزیک ترتیب کامل است .

اگر A یک مجموعه با ترتیب جزیی ≤ باشد، بعضی مواقع لازم است تا ترتیب کاملی مثل ≺ برای مجموعه A پیدا کنیم .
بطوریکه صرفا گسترشی از ترتیب جزیی داده شده باشد، به عبارت دیگر اگر a≤b . فرآیند تشکیل یک ترتیب کامل مثل ≺ را ترتیب توپولوژیکی گویند.
ما با این مسیله وقتی که مواجه خواهیم شد که بخواهیم مجموعه متناهی با ترتیب جزیی A را وارد کاممپیوتر بکنیم .