وبگاه دروس وبگاه دروس

« بازگشت

الگوریتم های پیشرفته

نام درس الگوریتم های پیشرفته
کد درس 8101748
تعداد واحد 3
دروس هم نیاز
دروس پیش نیاز
 

 

الگوریتم پیشرفته

شماره و نام درس

3 واحد

مهندسی کامپیوتر یا مهندسی فناوری اطلاعات

اجباری

نوع درس

کارشناسی ارشد

مقطع

ندارد

همنیازها

طراحی الگوریتم (کارشناسی)

پیش نیازها

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

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

مطالب پیش نیاز

-          Thomas H. Corman, Charles E. Leiserson and Ronald L. Rivest, “Introduction to Algorithms”, 2nd Edition, 2005.

-          S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani, Algorithms, 2006 .

-          J. Kleinberg, E. Trados, Algorithm Design, Pearson Education Inc., 2006

کتاب (کتب) مرجع

 هشام فیلی – عضو هیئت علمی دانشکده مهندسی برق و کامپیوتر

مدرس

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

اهداف درس

دانشجویانی که این درس را با موفقیت پشت سر بگذارند قادر خواهند بود

1-    مسائل مختلف را انالیز کرده و میزان سختی آن را مشخص کنند.

2-    در برخورد با مسائل ساده، راه حلهای دقیق با سرعت زیاد ارائه دهند.

3-    در برخورد با مسائل سخت راه حل های نادقیق که سرعت زیادی دارند را رائه دهند

نتایج درس

تحلیل سرشکنی (Amortized Analysis)

o       مفاهیم اولیه تحلیل سرشکنی

o       Accounting/ Aggregate/Potential

o       مثالهای مختلف

ساختمان داده های پیشرفته

·        B-Tree

o       مفاهیم اولیه

o       الگوریتم های Insert/delete/search

·        Binomial Heap

o       Binomial Tree

o       عملیات مختلف

o       تحلیل هزینه عملیات

·        Fibonacci Heap

o       مفاهیم اولیه

o       عملیات مختلف

o       تحلیل هزینه عملیات

·        Disjoint Set

o       مفاهیم مختلف

o       عملیات مختلف

o       تحلیل هزینه عملیات

روشهای پایه طراحی الگوریتم

-         عقب گرد

o       Knapsack

o       مسائل متفرقه

-         تقسیم و غلبه

o       Longest common subsequence

o       Fast Fourier Transform

o       نزدیک ترین دو نقطه در صفحه

o       مسائل متفرقه

-         حریصانه

o       مسائل متفرقه

o       Matroid

NP-Completenes

o       طبقه بندی مسائل P, NP, NP-hard, NP-complete

o       ارائه مسائل مهم در طبقه بندی مسائل

Network Flow

o       Maximum flow

o       Dual problem

o       Matching

Linear Programming

o       Definitions

o       canonical and standard forms

o       Duality

o       Simplex

Integer Linear Programming

o       Definition

o       Branch and Bound

o       Cutting plane

Approximation problem

Randomized Algorithm

 

مباحث

-          

استفاده از کامپیوتر

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

تکالیف

 

پروژه ها

 

میانترم: 7 نمره

پایانترم: 8 نمره

کوئیز: 2 نمره

تکالیف :3 نمره

 

 

نمره دهی

 

سایر مراجع

هشام فیلی

تنظیم کننده

 بهمن ماه  1392

تاریخ تنظیم