برنامه‌نویسی کامپیوتری به زبان‌های C#/C++/C
مارس 27, 2020
شبکه‌های کامپیوتری در مهندسی پزشکی
مارس 27, 2020

هدف
درس ساختمان داده‌ها، ادبیات برنامه‌نویسی و هنر ایجاد نرم‌افزار است.
هدف این درس ارایه ساختار کلاسیک ساختمان‌های مختلف داده‌ها، آشنایی با اصول استفاده از آنها به صورتی مستقل از زبانهای برنامه‌نویسی و در نهایت آشنایی مقدماتی با نحوه طراحی الگوریتم برای حل یک مسأله به ویژه نحوه انتخاب ساختمان داده مناسب برای آن مسأله است.
پیش نیاز
هر چند درس ساختمان داده‌ها به صورتی مستقل از زبانهای برنامه‌نویسی ارائه می‌شود، اما آشنایی مقدماتی با یک زبان برنامه‌نویسی شیءگرا (مانند C++ یا JAVA) برای دانشجویان الزامی است.
سرفصل مطالب درس
• مقدمه‌ای بر الگوریتمها: اصول ریاضی تحلیل الگوریتم، پیچیدگی‌های زمان-فضای الگوریتمها
• آرایه‌ها: عملیات اساسی آرایه‌ها، الگوریتمهای جستجو، چندجمله‌ای‌ها، رشته‌ها، آرایه‌های چندبعدی و ماتریسها، ماتریسهای خلوت، رکوردها، ADT آرایه.
• پشته‌ها و روابط بازگشتی: ساختار و عملیات اساسی پشته، ارزیابی عبارات محاسباتی و نمادگذاری لهستانی، نقش پشته‌ها در الگوریتمهای بازگشتی، بازسازی روابط بازگشتی با پشته‌ها، ADT پشته.
• صف: عملیات اساسی صفها، صفهای حلقوی، دوصفها، صفهای اولویتی، ADT صف.
• لیستهای پیوندی: عملیات اساسی لیستهای پیوندی، لیستهای پیوندی با سرگره، لیستهای دوطرفه، لیستهای حلقوی، لیستهای ناهمگون، الگوریتمهای بازگشتی تحلیل لیستها، مدیریت حافظه پویا، ADT لیستهای پیوندی، پیاده‌سازی پشته‌ها و صفها با لیستها پیوندی.
• درختها: معرفی ساختار درختها، نمایش درختها به کمک لیستهای پیوندی، درختهای دودویی، نمایش درختهای دودویی به کمک آرایه‌ها و لیستهای پیوندی، الگوریتمهای پیمایش درختهای دودویی، تحلیل درختهای دودویی، ADT درختهای دودویی، درختهای دودویی نخ‌کشی‌شده، کومه‌ها و الگوریتمهای مرتبط، درختهای جستجوی دودویی، عملیات اساسی درختهای جستجوی دودویی، درختهای عمومی، درختهای موزون عمقی، درختهای تصمیم‌گیری، درختهای کومه‌ای، درخت بیشینه-کمینه کومه‌ای، درختهای کومه‌ای دوجمله‌ای، درختهای کومه‌ای فیبوناتچی، جنگل.
• گرافها: نظریه گرافها، ماتریسهای مجاورت، عملیات اساسی گرافها، پیمایش گرافها، درختهای پوشا، مسأله کوتاهترین مسیر.
• ساختارهای جستجو: درختهای جستجوی بهینه، درختهای AVL، درختهای ۲-۳، درختهای ۲-۳-۴، درختهای قرمز-سیاه.
• مرتب‌سازی: مفاهیم مرتب‌سازی، بررسی الگوریتمهای مختلف مرتب‌سازی (حبابی، درجی، گزینشی، ادغام، مبنایی، کومه‌ای، پوسته‌ای) و مقایسه پیچیدگی آنها.
• درهم‌سازی: مفاهیم درهم‌سازی، الگوریتمهای درهم‌سازی، درهم‌سازی ایستا، درهم‌سازی پویا.
منابع
• Goodrich M., Tamassia R., “Data Structures and Algorithms in Java”, John Wiley & Sons, Inc., 4th Editio (pdf available).
• Goodrich M., Tamassia R., Mount D., “Data Structures and Algorithms in C++”, John Wiley & Sons Inc., ISBN: 0-471-20208-8
• Kruse Robert L. , Ryba Alexander J., “Data Structures and Program Design in C++”, Prentice Hall, 2000 (pdf available)
• Seymour Lipschutz,”Schaum’s Outline of Theory and Problems of Data Structure”, McGraw Hill, 1986.
• Horowitz E., Sahni S., Mehta D., “Fundamentals of Data Structures in C++”, W. H. Freeman & Co, 1999 (pdf available)
• Dale N., Joyce D., Weems C., “Object-oriented Data Structures Using Java”, Jones and Bartlett Publishers, 2006.
• Dale N., “C++ plus Data Structures”, Jones and Bartlett Publishers, 3d Edition.
• Cormen T., Leiserson C., Stein C., Rivest R.,”Introduction to Algorithms”, MIT Press, 2001 (pdf available).
• Wirth, N., “Algorithms + Data Structures = Programs”, Prentice- Hall.
ارزیابی
• ۶ نمره میان‌ترم
• ۶ نمره پروژه
• ۸ نمره پایان‌ترم
«تحویل کلیه پروژه‌ها و کسب حداقل نیمی از نمره کتبی جهت گذراندن درس الزامی است»