![](/documents/1230688/0/1200px-Sharifee1.jpg/8c58b63b-753a-7245-0424-0999b3927f66?t=1629537943623&download=true)
25755: ساختار داده و الگوریتم
نام درس: ساختار داده و الگوریتم (Data Structure and Algorithm)
شماره درس: 25755
پیشنیاز(ها): 25767 (برنامهسازی شیءگرا)
همنیاز(ها): -
تعداد واحد: 3
مقطع: کارشناسی
آخرین ویرایش: اسفند 1397
توضیحات:
سرفصلها:
مراجع:
شماره درس: 25755
پیشنیاز(ها): 25767 (برنامهسازی شیءگرا)
همنیاز(ها): -
تعداد واحد: 3
مقطع: کارشناسی
آخرین ویرایش: اسفند 1397
توضیحات:
در این درس، دانشجویان با روشهای مختلف طراحی الگوریتمهای کارا آشنا شده و از ساختارهای داده مناسب برای بهبود عملکرد الگوریتم استفاده خواهند کرد. همچنین در طراحی الگوریتمها، بر اثبات درستی و تحلیل عملکرد آن تاکید خواهد شد.
سرفصلها:
- مقدمه
- استقرا
- تحلیل الگوریتمها:
- رشد توابع
- روابط بازگشتی
- طراحی الگوریتم:
- الگوریتم های حریصانه
- برنامه ریزی پویا
- ساختار داده:
- پشته و صف، لیست، درخت
- درخت جستجوی باینری، Heap، درخت AVL، درخت قرمز-مشکی
- جدول درهمساز
- گراف
- الگوریتمهای کار با دنبالهها و مجموعهها:
- جستجوی باینری و مشتقات آن
- مرتبسازی
- الگوریتم های گرافی:
- جستجوی عمق اول، مرتبسازی توپولوژیک، مولفههای همبند قوی
- کوتاهترین مسیر
- جریان شبکه: قضیه max-flow-min-cut، تطابق دوبخشی
- الگوریتمهای تصادفی
- Contention resolution ،Quicksort
- توازن بار، Global mincut ،Max 3-SAT
- محاسبه پذیری و پیچیدگی
- P vs NP ،NP-hardness، قضیه Cook-Levin
- 3SAT ،Inedpendent set ،Clique ،Vertex Cover
مراجع:
- Jon Kleinberg, and Eva Tardos, Algorithm Design, Pearson, 2006
- Thomas H. Cormen, Charles E, Leiserson, Ronald L, Rivest, Clifford Stein, Introduction to Algorithms, 3rd Edition, MIT Press
- Udi Manber, Introduction to Algorithms: A Creative Approach, MA: Addison-Wesley
آخرین بهروزرسانی: 3 / 3 / 1403