ساختمان داده‌ها - نیم‌سال اول 1400

هدف از این درس آشنایی با روش‌های تحلیل الگوریتم و نیز داده ساختارهای پایه‌ای و مهم است. همچنین برخی از مسائل مهم الگوریتمی از جمله مرتب سازی و نیز الگوریتم‌های پیمایش داده ساختارها در این درس مورد نظر خواهد بود.

1. مباحث مقدماتی
   • مراحل مختلف حل مساله و تفکر الگوریتمی، انتزاع و مدل‌سازی مساله، داده ساختارهای بدیهی شامل متغیر، کلاس و آرایه.
2. روش‌های تحلیل الگوریتم‌ها
   • شمارش مراحل اجرای یک الگوریتم در قالب مثال‌های ساده از جمله مرتب سازی درجی و حبابی، توابع رشد، تحلیل زمان اجرای الگوریتم‌های ترتیبی و بازگشتی، روش‌های حل روابط بازگشتی شامل حدس و استقرا، تکرار با جایگذاری، قضیه اصلی و روابط بازگشتی همگن.
3. داده ساختارهای ابتدایی
   • داده ساختارهای خطی شامل لیست، صف، پشته و لیست‌های دوطرفه و کلی.
4. داده ساختارهای درختی
   • روشهای پیاده‌سازی و پیمایش‌های میان ترتیب، پس ترتیب و پیش ترتیب درخت، الگوریتم و حل مساله بر روی درخت، درخت‌های دودویی، درخت عبارت و تبدیل نگارش‌های مختلف پسوندی، میانوندی و پیشوندی به هم، درخت جستجوی دودویی، صف اولویت و هرم بیشینه و کمینه، درخت‌های متوازن و یکی از پیاده‌سازی‌های درخت متوازن از جمله درخت قرمز⁃سیاه.
5. مرتب سازی و مرتبه‌های آماری
   • کران پایین الگوریتم‌های مرتب سازی و درخت تصمیم، الگوریتم‌های بهینه مرتب سازی شامل مرتب سازی ادغامی و هرمی، مرتب سازی سریع، مرتب سازی خطی شامل مرتب سازی شمارشی، مبنایی و سطلی، مرتب سازی خارجی، مرتبه آماری و الگوریتم خطی یافتن میانه و مرتب سازی با کمترین مقایسه.
6. روش‌های درهم سازی
   • داده ساختار جدول درهم سازی، درهم سازی زنجیره‌ای، توابع درهم سازی و درهم سازی سراسری، جداول پویا و تحلیل سرشکنی.
7. داده ساختار گراف و الگوریتم‌های مقدماتی
   • روش‌های پیاده سازی گراف، الگوریتم‌های جستجوی عمق-اول و سطح-اول، مرتب سازی توپولوژیکی، الگوریتم یافتن اجزای همبند و قویا همبند.

این درس بعد از آشنایی دانشجویان با زبان‌های برنامه‌نویسی و حل مساله در قالب یک برنامه کامپیوتر ارائه می‌شود. در نتیجه تسلط به یک زبان برنامه‌نویسی هنگام اخذ این درس الزامی است.

• M. Ghodsi. «Data Structures and Fundamentals of Algorithms(in persian)». 6th edition, Fatemi 1393.
• T. Cormen, C. Leiserson, R. Riverst, and C. Stein. «Introduction to Algorithms». 3rd edition, MIT Press, 2009.

درس بصورت مجازی برگزار خواهد شد.

• تمرین: 3 نمره
  • در این درس 3 سری تمرین خواهیم داشت.
• آزمونک: 8 نمره
  • در این درس 4 آزمون کوتاه (عمدتا چندگزینه‌ای) با اطلاع قبلی و سر جلسه کلاس گرفته می‌شود.
• تمرین برنامه نویسی: 3 نمره
  • در این درس 3 تمرین برنامه نویسی کوتاه خواهیم داشت.
• پایان‌ترم: 6 نمره