مقدمه

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

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

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

من در اين تحقيق كاربرد گراف را در هوش مصنوعي كه علم روز مي باشد برگزيدم.

نظریهٔ مجموعه‌ها

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

تاریخچه

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

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

نظریه طبیعی مجموعه‌ها

مطالعه مجموعه‌ها به صورتی طبیعی به عنوان نظریه طبیعی مجموعه‌ها یا Naive set theory است و این همان نظریه‌ای است که در آغاز پیدایش نظریه مجموعه‌ها توسط جرج کانتور مطرح گردید. اما در ادامه این نظریه درگیر اشکالات و پارادکس‌هایی همچون پارادکس راسل شد، و به این ترتیب نیاز به یک تغییر در نظریه مجموعه ها احساس شد و به این ترتیب ریاضیدانانی چون ارنست زرملو سعی کردند نظریه مجموعه‌ها را در قالب یک دستگاه اصل موضوعی ارایه کنند که منجر به ایجاد نظریه اصل موضوعی مجموعه‌ها انجامید.

نظریهٔ اصل موضوعی مجموعه‌ها

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

زمينه هاي كاري و تحقيقاتي رشته مهندسي كامپيوتر

1. سخت افزار و معماري کامپيوتر (Hardware & Computer Architecture)

طراحيوساختمدارهايمنطقيوديجيتال(Design & Implementation of Digital Logic Circuits)به عنوان مثالهايي از سيستم هايي که شامل مدارهاي منطقي مي باشند، مي توان از سيستم هاي ديجيتال مانند ساعت هاي ديجيتال، برد هاي تبليغاتي، سيستم هاي کنترل ديجيتال در اکثر وسايل امروزي، موبايل ها و ... نام برد. مسلما بارزترين نوع اين سيستم ها کامپيوتر ها هستند.

معماري کامپيوتر (Computer Architecture)

نحوه طراحي و ساخت کامپيوترها و مدارهاي کامپيوتري بوسيله اجزاي ساده منطقي.

طراحي و ساخت مدارهاي واسط (Design & Implementation of Interface Circuits)نحوه ساخت مدارهايي که بتوانند به کامپيوترها، ميکروپروسسورهاو ميکروکنترلر ها متصل گردند و وظيفه اي خاص را انجام دهند. (براي مثال کارت صوتي يا کارت مودم)

طراحي و ساخت سيستم هاي بلادرنگ (Design & Implementation of Real-time Systems)سيستم هاي کامپيوتري که در حين انجام چند عمل مختلف، ضمانت مي کنند اعمال خاصي در زمانهاي مشخص يا به تعداد مشخصي انجام خواهند شد.

کنترل (Control)

تعيين ورودي هاي يک سيستم به نحوي که به ما خروجي هاي مطلوب بدهد. (براي مثال سيستم هايي که دما را کنترل مي کنند. در اين سيستم ورودي ها مي توانند شدت کار دستگاههاي خنک کننده و يا گرم کننده و خروجي هم مي تواند دماي محيط باشد.)

ميکروکنترل ها و سيستم هاي تعبيه شده (Microcontrollers & Embedded Systems)سيستم هاي تعبيه شده: سيستم هايي که در آنها يک يا چند پردازشگر کامپيوتري يا ميکرو کنترلر تعبيه شده تا اعمال سيستم و قسمت هاي مختلف آن را کنترل کنند.

طراحي و ساخت مدارهاي مجتمع در مقياس بزرگ (VLSI)

Very Large Scale Integration: تکنولوژي گردآوري و ساخت تعداد بسيار زيادي مدار ترانزيستوري در يک تراشه (چيپ) نيمه رسانا.

انتقال داده ها (Data Communication)

روشهاي انتقال داده ها و اطلاعات بين سيستم هاي کامپيوتري و ديجيتال.

2. نرم افزار و برنامه نويسي (Software & Programming)طراحي و پياده سازي پايگاه داده ها (Database)پايگاه داده ها: سيستمي که مسئول وظيفه نگهداري و مديريت اطلاعات را در سيستم هاي نرم افزاري به عهده دارد.

مهندسي نرم افزار (Software Engineering)

روشهاي مديريت، طراحي، پياده سازي و نگه داري برنامه ها و پروژه هاي نرم افزاري (مخصوصا پروژه هاي بزرگ)

سيستم هاي عامل (Operating Systems)

سيستم عامل برنامه ايست که بر روي يک سيستم سخت افزاري (مثل کامپيوتر) قرار مي گيرد و وظيفه آن عبارت است از ايجاد ارتباط بين نرم افزار ها و قسمت هاي مختلف سخت افزاري و همچنين مديريت و کنترل قسمت هاي مختلف سيستم.

اتوماسيون اداري (Office Automation)

اتوماتيک کردن روند فعاليت هاي يک اداره، موسسه يا سازمان بوسيله کامپيوتر.

برنامه نويسي همروند (Concurrent Programming)

به وجود آوردن امکان اجراي همزمان چند برنامه در کامپيوتر و مديرت آنها.

الگوريتم هاي موازي (Parallel Algorithms)

شکستن يک الگوريتم به قسمت هايي که مي توانند به صورت همزمان توسط چند پردازنده (چند کامپيوتر) انجام شوند، به منظور افزايش سرعت اجراي الگوريتم.

طراحي و ساخت کامپايلرها (Design & Implementation of Compilers)

کامپايلرها (در حالت خاص) برنامه هايي هستند که زبانهاي برنامه نويسي را به زبان کامپيوتر تبديل مي کنند.

شبيه سازي کامپيوتري (Computer Simulation)

شبيه سازي يک پديده خارجي در کامپيوتر با استفاده از قوانين (رياضي) حاکم بر آن پديده.گرافيک کامپيوتري (Computer Graphics)

تعداد صفحات پروژه 30 صفحه می باشد.