آموزش ساختمان داده و طراحی الگوریتم

آموزش ساختمان داده و طراحی الگوریتم

کتب مرجع درس ساختمان داده و طراحی الگوریتم:

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

سرفصل‌های  درس ساختمان داده و طراحی الگوریتم:

فصل اول: رشد توابع و نمادهای مجانبی (O ,o,…)

فصل دوم: روابط بازگشتی، پیچیدگی زمانی، تحلیل مرتبه حلقه‌ها

فصل سوم: معرفی روش تقسیم و غلبه

فصل چهارم: مرتب‌سازی‌ها (مقایسه‌ای و غیر مقایسه‌ای)

این فصل شامل تعداد زیادی از متدهای sort است. مانند مرتب‌سازی سریع، ادغامی و …

فصل پنجم: آماره‌های ترتیبی و میانه

فصل ششم: درخت‌های ویژه

انواع heap،  درخت جستجوی دودویی BST، درخت AVL، درخت Red_Black و درخت ترای و …

فصل هفتم: جدول درهم‌ساز (hash) و تابع

درهم‌ساز. تکنیک‌های رفع تصادم مانند وارسی خطی و غیر‌خطی.

فصل هشتم: الگوریتم های حریصانه برای مثال کد هافمن.

فصل نهم: الگوریتم‌های پویا برای مثال یافتن بزرگترین زیر رشته مشترک (LCS)

فصل دهم: آنالیز استهلاکی

فصل یازدهم: الگوریتم‌های گرافی

درخت پوشای کمینه MST
Prim ،Kruskal ،Solin….
کوتاهترین مسیر تک منبع:
Dijkstra ،Bellman_Ford,…
کوتاهترین مسیر بین هر جفت گره:
FLoyd، Johnson، …

فصل دوازدهم: یافتن حداکثر جریان
Maximum Flow
در این زمینه هم چند روش مختلف بحث می‌شود.

فصل سیزدهم: نظریه NP

سرفصل‌های  درس ساختمان داده و طراحی الگوریتم کتاب CLRS

introduction to ALGORITHMS

فصل اول: مقدمات پایه

تعریف الگوریتم، درستی الگوریتم، نرخ رشد توابع، معرفی مفاهیم: پایایی حلقه، تقسیم و غلبه، آنالیز احتمالات و محاسبه متوسط زمان مورد نیاز.

واژه های کلیدی:

Algorithms, loop invariant, Divided_and_Conquer
Growth of Functions

فصل دوم: مرتب‌سازی و آماره ترتیبی

فرض کنید لیستی از n داده عددی داشته باشیم:
x₁ x₂ . . . xₙ

اگر این لیست را به شکل صعودی مرتب کنیم لیست مرتب شده را به این صورت نامگذاری می‌کنیم:
x₍₁₎ x₍₂₎ . . . x₍ₙ₎

مثلا x₍₁₎ کوچکترین داده است و x₍₂₎ دومین کوچکترین داده است و … x₍ₙ₎ بزرگترین داده است. این‌ها را آماره‌های ترتیبی می‌نامند.

در این فصل، روش‌های مرسوم مرتب‌سازی معرفی شده‌اند. هر کدام از این روش‌ها مرتبه زمانی خود را دارند. البته هر کدام مزیت‌ها و محدودیت‌هایی دارند. مثلا برخی از آنها فقط برای اعداد صحیح کارایی دارند و برخی برای اعداد حقیقی ( اعشاری).
واژه‌های کلیدی این فصل:

Heap sort، Quick sort، Radix sort،
Worst case.

فصل سوم: ساختمان داده‌ها

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

می‌دانید که ساختمان‌های متنوعی برای داده‌ها وجود دارد. هر کدام از آنها مزیت‌ها و محدودیت‌هایی دارند. به ویژه نحوه درج یک داده جدید یا حذف یک داده در هر کدام از این ساختارها برای ما اهمیت دارد. این ساختارها عبارتند از: پشته، صف، آرایه‌های یک بعدی و چند بعدی، لیست پیوندی….

واژه‌های کلیدی این فصل:

Stacks،  Queues، Linked lists،
Rooted Trees، Hash table،
Binary search trees،
Insertion and Deletion،

فصل چهارم: طراحی الگوریتم پیشرفته

در بسیاری از مسائل کاربردی حوزه اقتصاد، صنعت و مدیریت، با مفهوم  بهینه‌سازی روبرو هستیم.
یافتن بیشترین سود ممکن، یافتن کمترین هزینه ممکن، یافتن کوتاهترین مسیر، و … همه این‌ها نمونه‌هایی از بهینه‌سازی هستند.

برای حل مسئله بهینه‌سازی در قالب یک الگوریتم، دو راه اصلی وجود دارد:

روش  پویا (dynamic) و روش  حریصانه (greedy). تعریف دقیق این روش‌ها مشکل است اما به طور کلی می‌توان گفت:
اگر بتوانیم ابتدا یک معیار برای انتخاب بهینه پیدا کنیم و اشیاء را طبق آن اولویت‌بندی کنیم و بعد با رعایت آن اولویت کار را انجام دهیم، روش حریصانه را انجام داده‍ایم.

اما اگر نتوانیم آن اولویت را ایجاد کنیم و بخواهیم در ضمن انجام کار و گام به گام مراقب انتخاب بهینه باشیم، روش پویا را در پیش گرفته‌ایم. در روش پویا معمولا یک فرمول بازگشتی هم داریم که به بهینه کردن کار در هر مرحله کمک می‌کند.

مثلا سارقی را تصور کنید که با یک کوله پشتی به مغازه حبوبات رفته است. او ابتدا قیمت هر کیلو از حبوبات مختلف را در نظر می‌گیرد، سپس با گران قیمت‌ترین کالا شروع می‌کند و آنقدر ادامه می‌دهد تا کوله‌اش پر شود. این یک روش حریصانه است. او از همان ابتدا می‌داند که اولویتش چیست.

حالا همان سارق را تصور کنید که به مغازه ساعت فروشی رفته است. دیگر نم‌یتواند با خیال راحت از گران قیمت‌ترین ساعت شروع کند زیرا ممکن است گران قیمت‌ترین ساعت به دلیل شکل هندسی‌اش دیگر اجازه ورود ساعت‌های دیگر به کوله را ندهد.

ممکن است انتخاب ۵ ساعت ارزان‌تر و کوچک‌تر بهتر از انتخاب یک ساعت بزرگ و گران قیمت باشد. حالا او معیار انتخابش را از دست داده و باید در بین همه حالات ممکن، بهترین انتخاب‌ها را پیدا کند. او نیاز به یک روش پویا دارد.
در فصل چهارم، نمونه هایی از حل مسایل با دو روش بالا را خواهید دید:

ضرب ماتریس‌ها، کوله پشتی، کد هافمن، طولانی‌ترین زیر رشته مشترک، ….

واژه های کلیدی:
Dynamic programming
Greedy Algorithms
Huffman codes
Longest common subsequence
Optimal binary search

فصل پنجم: ساختمان داده‌های پیشرفته

برای پیش رفتن در طراحی الگوریتم باید با ساختارهای دیگری از داده ها آشنا شویم.
فصل پنجم مقدمه ای برای فصل ششم است.
واژه‌های کلیدی:
B.trees
Fibonacci heaps
Disjoint sets

فصل ششم: الگوریتم‌های مرتبط با گراف.

تعداد زیادی از کاربردهای ریاضی در اقتصاد و مدیریت، در قالب گراف مدل‌سازی می‌شوند.
در این فصل، ابتدا کمی از مباحث نظریه گراف‌ها را مرور می‌کنیم مانند: نمایش‌های مختلف گراف به صورت ماتریس مجاورت و ماتریس تقاطع و … جستجوی سطح نخست، جستجوی عمق نخست، درخت فراگیر، ترتیب توپولوژیک، همبندی و انواع آن، گراف ساده و وزن‌دار….

سپس بحث اصلی آغاز می‌شود:

۱. یافتن درخت فراگیر مینیمال:
پریم و کراسکال
۲. یافتن کوتاهترین مسیر با مبدا مشخص
بلمن فورد و دیجسترا
۳. یافتن کوتاهترین مسیر با مبدا و مقصد دلخواه
فلوید وارشال، جانسون،
همچنین تکرار دیجسترا یا بلمن فورد در یک حلقه نیز می‌تواند مساله را حل کند.
۴. یافتن حداکثر شار
واژه‌های کلیدی:
Depth_first search
Breadth_first search
Topological sort
Minimum spanning tree
Shortest paths
Maximum flow

فصل هفتم: عناوین انتخابی

در این فصل از آموزش ساختمان داده و طراحی الگوریتم، تعدادی از الگوریتم های پرکاربرد در مباحث متنوع انتخاب و معرفی شده اند.

الگوریتم های چند شاخه ای، عملگرهای ماتریسی، الگوریتم های مرتبط با چند جمله ایها، روش هورنر ،برنامه‌ریزی خطی، الگوریتم های مرتبط با نظریه اعداد و ….همچنین بخشی در مورد رده P و NP آمده است.

واژه های کلیدی:

Multithreaded Algorithms
Matrix operations
Linear programming
Polynomials
Number theory
Np completeness
فصل هشتم: زمینه‌های ریاضی
این فصل از آموزش ساختمان داده و طراحی الگوریتم، در واقع یک ضمیمه است که در آن پیش‌نیازهای ریاضی بحث، مطرح شده‌اند.
مجموع‌های متناهی، دنباله‌ها، نظریه مجموعه‌ها و توابع، شمارش و احتمال، ماتریس‌ها.

کتب کنکوری دروس ساختمان داده و طراحی الگوریتم:

بهترین کتاب نتیجه‌گرا و امن این درس کتاب ساختمان داده انتشارات راهیان ارشد تالیف استاد ابوالفضل گیلک است.

بهترین کتاب نتیجه‌گرا و امن این درس کتاب طراحی الگوریتم انتشارات راهیان ارشد تالیف استاد ابوالفضل گیلک است.

بهترین کتاب نتیجه‌گرا و امن این درس کتاب ۶۰۰ مسئله‌ی چند گزینه‌ای از داده ساختارها و الگوریتم‌ها انتشارات فاطمی تالیف استاد محمد قدسی است.

کلاس آنلاین دروس ساختمان داده و طراحی الگوریتم:

بهترین کلاس آنلاین نتیجه‌گرا و امن این درس کلاس ساختمان داده و طراحی الگوریتم گروه بابان استاد ابوالفضل گیلک است.