ساختمان داده ها و الگوریتم

نام درس ساختمان داده ها و الگوریتم
کد درس 8101437
تعداد واحد 3
نوع درس اجباری - مهندسی کامپیوتر، مهندسی فناوری اطلاعات
مقطع درس کارشناسی
دروس هم نیاز برنامه سازی پیشرفته
دروس پیش نیاز رياضيات گسسته
مطالب پیش نیاز

آشنایی با مبانی کامپيوتر و اصول برنامه نویسي

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

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

مدرس دکتر هشام فيلي
اهداف درس

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

نتایج درس

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

 

  1. ساختمان داده های مختلف را طراحی کنند.
  2. الگوریتمهای مختلف را طراحی و پیاده سازی کنند.
  3. الگوریتمها را آنالیز کنند.
مباحث

1-روشهاي تحليل الگوريتمها – شامل

  • محاسبه زمان اجراي الگوريتم
  • تعريف بدترين حالت الگوريتم، بهترين حالت و حالت متوسط اجراي الگوريتم
  • تعريف O، o، q، W، w
  • تعريف توابع رشد
  • الگوريتم  مرتب سازی MergeSort و تحليل زمان اجراي آن
  • چند نمونه ساده ...

 

2-الگوريتمهاي بازگشتي

  • الگوريتم بازگشتي برجهاي هانوي
  • روشهاي حل روابط بازگشتي
    • بازکردن فرمول
    • حدس جواب و اثبات به شيوه استقراء
    • استفاده از قضيه اصلي
  • مثالهاي حل روابط بازگشتي رياضي

3-ساختمانهاي داده اي پايه

  • ليست پيوندي
    • توابع insert, delete, merge, copy, getcount, reverse, purge
    • ليست کلي
  • مفهوم پشته
    • پياده سازی پشته با استفاده از ليست پيوندي و آرايه
    • کاربرد پشته در عبارتهاي محاسباتی – Infix/prefix/postfix
  • صف
    • پياده سازي صف
    • صف دوار

4-درختها

  • تعاريف مربوطه
  • روشهاي پياده سازی درخت
  • توابع Preorder, Postorder, Inorder, Height, GetCount, Parent, ...
  • درخت انبوه (Heap)
    • الگوريتم جستجو انبوه (HeapSort)
  • درخت دودويي جستجو (Binary Search Tree)
  • درخت هافمن (Huffman Tree)
    • کد هافمن (Huffman Coding)
  • درخت عبارت (Expression Tree)
    • Prefix, Postfix, Infix
    • روش محاسبه عبارتهاي محاسباتي

5-Hashing

  • مفاهيم اوليه
  • Direct address
  • Open addressing
  • Linear Probing
  • Quadratic Probing
  • Double Probing

6-الگوريتمهاي مرتب سازي

  • مفاهيم اوليه
  • مرتب سازي غيرمبتني بر مقايسه
    • CountSort, RadixSort, Bucket Sort
  • مرتب سازی مبتني بر مقايسه
    • Insertion Sort
    • Selection Sort
    • Bubble Sort
    • Merge Sort
    • Heap Sort
    • Quick Sort
      • Randomize Quick Sort
  • مرتب سازي خارجي
    • External Merge Sort

 

7-تبديل الگوريتمهاي بازگشتي به غيربازگشتي

  • روش تبديل الگوريتم هاي بازگشتي به غيربازگشتي
  • مثال های مختلف

8-گرافها

  • تعاريف مربوطه
  • روشهاي پياده سازی گراف
  • گراف خلوت
    • پياده سازي
  • الگوريتمهاي پيمايش گراف – DFS - BFS
  • گراف جهت دار بدون حلقه
    • Topological Sort
  • اجزاي قويا همبند (Strongly connected component)
  • درخت پوشاي کمينه – Prim - Kruskal
  • Shortest Path
    • Single Source Shortest Path
    • All Pairs Shortest Path

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

  • مفاهیم اوليه تحليل سرشکنی
  • Accounting/ Aggregate/Potential
  • مثالهاي مختلف

10-ساختمان داده هاي پيشرفته

  • B-Tree
    • مفاهيم اوليه
    • الگوريتم هاي Insert/delete/search
  • Binomial Heap
    • Binomial Tree
    • عمليات مختلف
    • تحليل هزينه عمليات
  • Fibonacci Heap
    • مفاهیم اوليه
    • عمليات مختلف
    • تحليل هزينه عمليات
  • Disjoint Set
    • مفاهيم مختلف
    • عمليات مختلف
    • تحليل هزينه عمليات 
استفاده از کامپیوتر

استفاده از کامپيوتر در این درس از طريق تعریف پروژه های کامپيوتری صورت میگیرد.

تکالیف

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

پروژه ها

پروژه هاي کامپيوتري در زمینه هاي زیر وجود دارد که البته به دو بخش Short Assignment/ Computer Assignment تقسيم مي­گردد.

  1. ساختمان داده ای پايه
  2. درختها
  3. الگوريتمهای مرتب سازی
  4. گراف
  5. Hashing
نمره دهی
  • میانترم: 6 نمره
  • پايانترم: 7 نمره
  • کوئيز: 2 نمره
  • تکالیف : 2 نمره
  • پروژه ها: 3 نمره 
سایر مراجع

1- محمد قدسی، داده ساختارها و مبانی الگوریتمها، انتشارات فاطمي، نسخه 1، 1388

2- A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data Structures and Algorithms, 1983

3- U. Manber, Introduction to Algorithms: A Creative Approach, Addison Wesley,m 1989

 

 

تنظیم کننده دکتر هشام فيلي
تاریخ تنظیم بهمن 1392