برنامه درسی

لیست برنامه های درسی

پیش نیاز درس

ریاضیات گسسته، برنامه‌سازی پیشرفته

منابع

  1. Horowitz, Ellis, Sartaj Sahni, and Susan Anderson-Freed. Fundamentals of Data Structures in C. (کتاب هوروتیز)

  2. Lipschutz, Seymour. Data Structures (از مجموعه Schaum's Outline). (کتاب لیپ‌شوتز)

  3. Tanenbaum, Aaron M., et al. Data Structures Using C. (کتاب تنباوم)

طرح درس
۱. مقدمات (۱ جلسه): سطوح انتزاع، مراحل حل مسئله، داده‌مدل‌ها، داده‌گونه‌ها، داده‌ساختارها، داده‌گونه‌ی انتزاعی، شیء
۲. تحلیل الگوریتم (۳ جلسه): تحلیل زمانی، مرتب‌سازی درجی، رشد توابع، تحلیل سرشکن
۳. تقسیم و حل (۲ جلسه): مرتب‌سازی ادغامی، تعداد نابجایی، زیردنباله‌ی متوالی، ضرب اعداد، قضیه اصلی
۴. تحلیل الگوریتم‌های تصادفی (۱ جلسه): میانه‌ی تقریبی، مسئله‌ی استخدام
۵. داده‌ساختارهای پایه (۱ جلسه): صف، پشته، لیست پیوندی
۶. داده‌ساختارهای درخت (۵ جلسه): پیاده‌سازی درخت‌ها، پیمایش، استقرای ساختاری، درخت عبارت، ترای، درخت دودویی جستجو، صف اولویت (هرم)
۷. مرتب‌سازی (۴ جلسه): درخت تصمیم، مرتب‌سازی هرمی، سریع، خطی (شمارشی، مبنایی، سطلی)، خارجی (اختیاری)
۸. مرتبه‌ی آماری (۲ جلسه): کمینه و بیشینه، انتخاب k-امین عنصر
۹. درهم‌سازی (۲ جلسه): زنجیره‌ای، سراسری، باز، کامل
۱۰. داده‌ساختارهای پیشرفته (۳ جلسه): مجموعه‌های مجزا، درخت قرمز-سیاه، درخت بازه
۱۱. گراف‌ها (۳ جلسه): پیاده‌سازی گراف، جست‌وجوی عمق اول و سطح اول، ترتیب توپولوژیکی، مؤلفه‌های قویاً همبند، کوتاه‌ترین مسیر (دایکسترا و بلمن-فورد)
هدف از طرح درس

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

پیش نیاز درس

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

منابع

  • Elmasri & Navathe, Fundamentals of Database Systems

  • Silberschatz, Korth & Sudarshan, Database System Concepts

  • Ramakrishnan & Gehrke, Database Management Systems

  • C. J. Date, An Introduction to Database Systems

طرح درس

۱. مشی پایگاهی و سیستم‌های پایگاهی (۳ جلسه): معرفی درس، تعریف پایگاه داده‌ها، مشی فایلینگ و مشی پایگاهی، عناصر محیط پایگاه داده، انواع معماری سیستم پایگاهی (متمرکز، مشتری-خدمتگزار، توزیع‌شده)، اجزای RDBMS و OLTP
۲. مدل‌سازی معنایی داده‌ها با روش ER و EER (۴ جلسه): موجودیت، صفت، ارتباط، نمودار ER و EER، انواع دام‌ها، تکنیک‌های تخصیص، تعمیم، تجزیه، ترکیب و تجمیع، ویژگی‌های روش مدل‌سازی معنایی
۳. اصول طراحی پایگاه داده‌ها (۲ جلسه): آشنایی با ساختار جدولی و پایگاه داده جدولی، روش طراحی بالا به پایین (تبدیل مدل‌سازی معنایی به طراحی منطقی)
۴. مقدمات پیاده‌سازی و SQL (۳ جلسه): زبان پایگاه داده‌ی جدولی (SQL)، آشنایی مقدماتی با دستورات DDL و DCL
۵. نرمال‌سازی (تا سطح BCNF): وابستگی‌های تابعی، اصول نرمال‌سازی، ۱NF، ۲NF، ۳NF و BCNF

هدف از طرح درس

آشنایی دانشجویان با مفاهیم اصلی سیستم‌های مدیریت پایگاه داده، مدل‌سازی معنایی داده‌ها و طراحی پایگاه داده‌ها. در انتهای ترم انتظار می‌رود دانشجویان با مفاهیم مطرح‌شده در سرفصل‌ها آشنایی کامل پیدا کرده باشند. تأکید بر طراحی منطقی از طریق تبدیل مدل ER/EER به ساختار جدولی و پیاده‌سازی مقدماتی با SQL است. در بخش نرمال‌سازی، تدریس تا سطح BCNF ارائه می‌شود.