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

مروری بر مطالب مهم در درس ساختمان داده و تکمیل نکات ارائه شده در خصوص: استقرا ریاضی و روشهای بازگشتی، پیچیدگی الگوریتمها و آنالیز آنها، نمادهای O ، تتا، امگا، o و روشهای حل مسئله: در هر روشی تعدادی مسئله مهم انتخاب و الگوریتمهای هر یک گفته شده و اثبات و آنالیز گردد. روش مستقیم و حل ( مسائل: ماکزیمم و مینیمم یک آرایه، ضرب دو عدد nبیتی، روش strassen در ضرب ماتریسها، تورنمت بازیها، مرتب کردن براساس  QuickSort)، روش برنامه سازی پویا ( مسائل: ضرب ماتریسها، کوله پشتی، مثلث بندی بهینه یک چندضلعی، طولانی ترین زیرترتیب مشترک، حروف چینی یک پاراگراف )، روش حریصانه ( مسائل:‌ مسائل زمانبندی، خرد کردن پول، کدهافمن )، روشهای مبتنی بر جستجوی کامل و تکنیکهای محدود کردن فضای جستجو، استفاده از درخت بازی و Pruning، بازیهای Puzzle، tic-tac-tac روشهای مکاشفه ای برای حل مسائل مشکل ( مسئله فروشنده دوره گرد ) الگوریتمهای گراف شامل: روشهای جستجوی گراف ( عمقی، سطحی ) گرافهای بدون جهت ( الگوریتمهای Dijkstra درخت پوشای مینیمال، اجزا همبند، کاملا همبند و مسائل دیگر ) گرافهای جهت دار ( الگوریتمهای Floyd، مرتب کردن Topological، اجزا دو همبند و ...) شبکه های ماکزیمم جریان و مسائل مربوطه.

مراجع:

1- Neapolitan, Foundations of Algorithms.

2- CLRS) Cormen, leisersen, Rivert, Introduction to Algorithms)

3- Horowitz, Sahni, Fundamental of Computer Algorithms.

4- Aho, Hopctoft, Data Structure & Algorithms.

5- Udi Manber, Introduction to Algorithms.

6- Brassard, Fundamentals of Algorithms

اصول طراحی پایگاه داده

مقدمه، معرفی ومرور مباحث ذخیره و بازیابی اطلاعات، مفاهیم و تعاریف مدیریت پایگاه داده (تعریف داده و اطلاعات، تعریف پایگاه داده، ضرورت پایگاه داده، استقلال داده ای، مدل های مختلف سیستم های پایگاه داده)، معماری یک سیستم پایگاه داده (معماری سه سطحی، سطح خارجی، سطح مفهومی، سطح داخلی، مدیر پایگاه داده و مدیر داده، مدیر ارتباطات داده ای)، مدل های مختلف سیستم های پایگاه داده (مدل سلسله مراتبی، مدل رابطه ای، مدل شبکه ای)، مدل رابطه ای پایگاه داده ها(رابطه یا جدول، جداول مبنا و غیرمبنا، زبان پرس و جو)، عناصر مدل رابطه ای (دامنه، رابطه و انواع آن)، جامعیت مدل رابطه ای(کلید کاندید، کلید اولیه، کلید رقیب، کلید خارجی و قواعد آن، تهی بودن کلید خارجی و کلید اولیه) ، جبر رابطه ای، حساب رابطه ای، زبان SQL، وابستگی تابعی (تعریف، وابستگی های جزئی، بستار مجموعه ای از وابستگی ها، مجموعه کاهش ناپذیر از وابستگی ها)، نرمال سازی(1NF, 2NF, 3NF, BCNF وابستگی چند مقداری(MVD) و 4NF، وابستگی الحاقی (JD) و 5NF) ،مرور مطالب پیشرفته تر (حفاظت، ترمیم، همزمانی، پایگاههای داده شی گرا، پایگاه های داده استنتاجی).

مراجع:

1- Date, Introduction to Database Design

2- Elmasri, Fundamental of Database systems

3- Abitebout, Foundations of Database

4- Korth and Silberchatz, Database System Concepts

ساختمان داده ها

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

مراجع:

1- Horowitz and Sahni, Fundamental of Data Structure and Computer Algorithms

2- Tenenbawn, Data Structure Using Pascal

3- Wirth, Algorithms + Data Structure = Programs

اصول طراحی کامپایلر

مقدمات ( انواع مترجم ها شامل کامپایلرها و مفسرها ) ساختار و اجزای کامپایلر( تحلیل گر لغوی،‌ نحوی، معنایی، مدیریت جدول نمادها، تولید کد میانی و نهایی،‌ بهینه سازی، مدیریت خطاها ) ، بررسی انواع گرامرها و خواص عمومی زبانها( طبقه بندی Chomsky )، گرامرهای گنگ، گرامر خالص( مختصر و مفید )، تحلیل لغوی، عباریات منظم برای نمایش الگوی توکن ها، اصلاح خطاهای لغوی، گرامرهای تفسیر حالت قطعی و غیرقطعی، روشهای تحلیل نحوی (بالا به پایین، (LL(1 ، پیاده سازی RecursiveDescent و جدول تجزیه پایین به بالا(OP-SP)، روشهای (LL(1 شامل (SLR(1 و (LALR(1 و (CLR(1 و اصلاح جدول (LR(1 در مورد گرامرهای گنگ )، روشهای اصلاح خطاهای نحوی، تحلیل معنایی ( تستهای ایستا و پویا ) ، مدیریت جدول نمادها و ساختار آنها، روشهای تحصیص حافظه ( ایستا و پویا )، تولید کد میانی و نهایی و روشهای تولید کد مانند Syntax Directed یا Tree Walking با استفاده از کنش های مفهومی و علایم کنش، ترجمه تعدادی از ساختارهای زبانهای امری مانند عبارتها ، ساختارهای کنترلی، فراخوانی روال ها، مختصری در مورد بهینه سازی کد میانی

مراجع:

1- Aho, Sethi, Compilers: Principles, Techniques and Tools

2- Trembly, The Theory and Practice of Compiler Writing

3- Pittman and Petersm The Art of Compiler Design

4- Mack, Writing Compilers and Interpreters

ریاضی گسسته

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

مراجع:

1- Johnson Baugh,Discerte Mathematics

2- Grassman And Tremblay, Logic and Discrete Mathematics

3- Termblay, Discrete Mathematical Structures with Applications to computer science

4- Keneth, Rossen and Charles R.B,Wright, Discrete Mathematics

5- Grimaldi, Discrete and Combinatorial Mathematics

6- Michael Alberison, Discrete Mathematics with Algorithms

زبان تخصصی نرم افزار

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

منبع: سایت کارشناسی

 نوشته شده توسط محمد قاری در چهارشنبه 90/8/4 و ساعت 6:45 عصر | نظرات دیگران()