25755: ساختار داده و الگوریتم  
نام درس: ساختار داده و الگوریتم (Data Structure and Algorithm)
شماره درس: 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