آموزش طراحی الگوریتم: تسلط بر حل مسائل محاسباتی - آخرین آپدیت

سرفصل ها و درس ها

مبانی طراحی الگوریتم Foundations of Algorithm Design

• مقدمه‌ای بر طراحی الگوریتم Introducing Algorithm Design

• آشنایی با مدرس: پروفسور فبین وهاب Meet your Instructor: Prof. Febin Vahab

• آشنایی با مدرس: پروفسور راکش پراسانا Meet your Instructor: Prof. Rakesh Prasanna

• مفهوم الگوریتم‌ها Notion of Algorithms

• متدولوژی‌های تحلیل الگوریتم Methodologies for Analyzing Algorithms

• مفهوم بهترین حالت، حالت متوسط و بدترین حالت Notion of Best Case, Average Case, and Worst Case

• روش عملیات پایه Basic Operation Method

• مرتبه رشد الگوریتم‌ها Order of Growth of Algorithms

• نمادهای مجانبی: بخش اول Asymptotic Notations: Part I

• نمادهای مجانبی: بخش دوم Asymptotic Notations: Part II

• تحلیل الگوریتم: مرتب‌سازی درجی Algorithm Analysis: Insertion Sort

• تحلیل الگوریتم‌های بازگشتی Analysis of Recursive Algorithms

• حل روابط بازگشتی: جایگزینی رو به عقب Solving Recurrences: Backward Substitution

• حل روابط بازگشتی: درخت بازگشتی - بخش اول Solving Recurrences: Recursion Tree—Part I

• حل روابط بازگشتی: درخت بازگشتی - بخش دوم Solving Recurrences: Recursion Tree—Part II

• حل روابط بازگشتی: روش مستر (Master Method) Solving Recurrences: Master Method

استراتژی‌های تقسیم و غلبه Divide and Conquer Strategies

• اصول و استراتژی‌های طراحی Design Principles and Strategy

• تحلیل الگوریتم‌های تقسیم و غلبه: مرتب‌سازی ادغامی Analysis of Divide and Conquer Algorithms: Mergesort

• الگوریتم تقسیم و غلبه: مرتب‌سازی سریع - بخش اول Divide and Conquer Algorithm: Quicksort—Part I

• الگوریتم تقسیم و غلبه: مرتب‌سازی سریع - بخش دوم Divide and Conquer Algorithm: Quicksort—Part II

• الگوریتم تقسیم و غلبه: جستجوی دودویی Divide and Conquer Algorithm: Binary Search

• مسئله ۱: مسئله ضرب اعداد صحیح Problem 1: Integer Multiplication Problem

• مسئله ۲: مسئله زیرآرایه‌ای بیشینه - بخش اول Problem 2: Maximum Subarray Problem—Part I

• مسئله ۲: مسئله زیرآرایه‌ای بیشینه - بخش دوم Problem 2: Maximum Subarray Problem—Part II

• مسئله زیرآرایه‌ای بیشینه: تحلیل Maximum Subarray Problem: Analysis

• مسئله ضرب ماتریسی استراسن Strassen’s Matrix Multiplication Problem

• ضرب ماتریس: یک الگوریتم ساده تقسیم و غلبه Matrix Multiplication: A Simple Divide and Conquer Algorithm

• الگوریتم استراسن Strassen’s Algorithm

• الگوریتم استراسن: تحلیل Strassen’s Algorithm: Analysis

متدولوژی الگوریتم‌های حریصانه Greedy Algorithm Methodology

• مسئله خرد کردن پول Change Making Problem

• استراتژی حریصانه: اصول طراحی و عناصر کلیدی Greedy Strategy: Design Principle and Key Elements

• مقدمه‌ای بر مسئله کوله‌پشتی Introduction to Knapsack Problem

• الگوریتم کوله‌پشتی کسری و تحلیل آن Fractional Knapsack Algorithm and Analysis

• کوله‌پشتی کسری: مثال عددی Fractional Knapsack: Numerical Example

• مسئله زمان‌بندی وظایف Task Scheduling Problem

• زمان‌بندی وظایف: الگوریتم و تحلیل Task Scheduling: Algorithm and Analysis

• توالی‌بندی کارها با ضرب‌الاجل: الگوریتم و تحلیل Job Sequencing with Deadlines: Algorithm and Analysis

• توالی‌بندی کارها با ضرب‌الاجل: مثال عددی Job Sequencing with Deadlines: Numerical Example

برنامه‌نویسی پویا Dynamic Programming 

• پارادایم برنامه‌نویسی پویا: تکنیک کلی Dynamic Programming Paradigm: The General Technique

• اعداد فیبوناتچی: رویکردهای بالا به پایین و پایین به بالا - بخش اول Fibonacci Numbers: Top-Down and Bottom-Up Approaches—Part I

• اعداد فیبوناتچی: رویکردهای بالا به پایین و پایین به بالا - بخش دوم Fibonacci Numbers: Top-Down and Bottom-Up Approaches—Part II

• ضرب زنجیره‌ای ماتریس‌ها (MCP) Matrix Chain Product (MCP)

• MCP: به‌کارگیری برنامه‌نویسی پویا MCP: Applying Dynamic Programming

• MCP: مثال عددی MCP: Numeric Example

• MCP: رویکرد پایین به بالا MCP: Bottom-Up Approach

• مسئله کوله‌پشتی ۰/۱ 0/1 Knapsack Problem

مبانی الگوریتم‌های گراف Graph Algorithms - Fundamentals

• مرور: ویژگی‌ها و انواع گراف Review: Graph Properties and Types

• مرور: نمایش‌های گراف Review: Graph Representations

• مسیر، دور، زیرگراف‌ها، اتصال، درخت‌ها و جنگل‌ها Path, Cycle, Subgraphs, Connectivity, Trees, and Forests

• قابلیت دسترسی و اتصال قوی Reachability and Strong Connectivity

• مرور: پیمایش گراف - جستجوی اول سطح (BFS) و تحلیل Review: Graph Traversal—Breadth First Search (BFS) and Analysis

• مرور: پیمایش گراف - جستجوی اول عمق (DFS) و تحلیل Review: Graph Traversal—Depth First Search (DFS) and Analysis

• مقایسه BFS و DFS BFS and DFS Comparison

• مرتب‌سازی توپولوژیک: الگوریتم و تحلیل Topological Sort: Algorithm and Analysis

الگوریتم‌های پیشرفته گراف Advanced Graph Algorithms

• درخت پوشای کمینه (MST) Minimum Spanning Tree

• استراتژی طراحی کروسکال Kruskal’s Design Strategy

• MST: استراتژی طراحی پرایم MST: Prim’s Design Strategy

• کوتاه‌ترین مسیرها و ویژگی‌های آن‌ها Shortest Paths and Properties

• الگوریتم بلمن-فورد The Bellman-Ford Algorithm

• الگوریتم دایکسترا Dijkstra’s Algorithm

• بستار متعدی: استراتژی طراحی Transitive Closure: Design Strategy

• کوتاه‌ترین مسیر بین همه جفت‌ها: استراتژی طراحی فلوید All Pair Shortest Path: Floyd’s Design Strategy

تکنیک‌های طراحی: بازگشت و شاخه و کران Design Technique: Backtracking and Branch & Bound

• تعریف حالت در فضای حالت Definition of a State in a State Space

• فضای حالت متناهی و نامتناهی Finite and Infinite State Space

• پیمایش در فضای حالت Traversing Through State Space

• درخت فضای حالت State Space Tree

• مقدمه‌ای بر بازگشت (Backtracking) Introduction to Backtracking

• DFS به عنوان مثالی از بازگشت با درخت فضای حالت DFS as an Example of Backtracking with State Space Tree

• تعریف حالت در مسئله N-ملکه Definition of the State in the N-Queen Problem

• پیمایش تمام فضاهای حالت با استفاده از بازگشتی Traversing Through All State Spaces Using Recursion

• توضیح استراتژی بازگشت Backtracking Strategy Explanation

• مقایسه راهکار بازگشتی در مقابل راهکار بدون بازگشت Backtracking Solution versus Solution Without Backtracking

• مقایسه پیچیدگی زمانی Time Complexity Comparison

• مسئله رنگ‌آمیزی گراف: تعاریف و کاربردها Graph Coloring Problem: Definitions and Applications

• رویکرد ساده برای رنگ‌آمیزی با تمام رنگ‌های ممکن Naive Approach to Color with All Possible Colors

• استراتژی بازگشت همراه با بصری‌سازی Backtracking Strategy with Visualization

• تعریف مسئله و حالت Problem and State Definition

• رویکرد ساده برای جستجو در تمام زیرمجموعه‌های ممکن Naïve Approach to Find Through all Possible Subsets

• کد بازگشتی و درخت فضای حالت Backtracking Code and State Space Tree

• تحلیل پیچیدگی زمانی Time Complexity Analysis

• مقدمه‌ای بر جستجوی کمترین هزینه (Least Cost Search) Introduction to Least Cost Search

• مثال‌های کاربردی جستجوی کمترین هزینه Application Examples of Least Cost Search

• پیاده‌سازی عملی جستجوی کمترین هزینه Practical Implementation of Least Cost Search

• ساختارهای داده FIFO، شاخه‌بندی و چارچوب کران‌بندی FIFO Data Structures, Branching, and Bounding Framework

• تحلیل و پیاده‌سازی رویکرد FIFO Analysis and Implementation of FIFO Approach

• مسئله کوله‌پشتی ۰/۱ با استفاده از شاخه و کران FIFO 0/1 Knapsack Problem Using FIFO Branch and Bounds

• مقایسه با سایر استراتژی‌های شاخه و کران: چالش‌ها و محدودیت‌ها Comparison with Other Branch and Bound Strategies: Challenges and Limitations

• تکنیک‌های بهینه‌سازی با مثال: مسیریابی شبکه در مخابرات و مسیریابی خودرو برای تحویل Optimization Techniques with Examples: Network Routing in Telecommunications and Vehicle Routing for Deliveries

• استراتژی‌های کران‌بندی و تکنیک شاخه‌بندی LC Bounding Strategies and LC Branching Technique

• مسئله کوله‌پشتی ۰/۱ با استفاده از شاخه و کران LC 0/1 Knapsack Problem Using LC Branch and Bounds

• مقایسه با سایر استراتژی‌های شاخه و کران، چالش‌ها و محدودیت‌ها Comparison with Other Branch and Bound Strategies, Challenges and Limitations

• تکنیک‌های بهینه‌سازی با مثال: زمان‌بندی پروژه و تخصیص منابع Optimization Techniques with Examples: Project Scheduling and Resource Allocation

• مقدمه‌ای بر توالی‌بندی کارها با محدودیت زمانی Introduction to Job Sequencing with Timebound

• پیاده‌سازی و تحلیل با استراتژی بهینه‌سازی Implementation and Analysis with Optimization Strategy

• توالی‌بندی کارها با ضرب‌الاجل Job Sequencing with Deadline

الگوریتم‌های تصادفی Randomized Algorithms

• الگوریتم تصادفی Randomized Algorithm

• مرتب‌سازی سریع کلاسیک Classical Quicksort

• انتخاب تصادفی محور (Pivot) Random Selection of Pivot

• الگوریتم مرتب‌سازی سریع تصادفی Randomized Quicksort Algorithm

• مقایسه پیچیدگی زمانی متوسط Average Time Complexity Comparison

• تعریف مسئله کمترین برش (Min Cut) Min-Cut Problem Definition

• منقبض کردن یال‌ها Contracting Edges

• الگوریتم کلاسیک Classical Algorithm

• الگوریتم کارگر برای یافتن کمترین برش Karger’s Algorithm for Finding the Min-Cut

• مقایسه پیچیدگی زمانی Time Complexity Comparison

مسائل P، NP، NP-Complete و NP-Hard P, NP, NP-Complete, and NP-Hard Problems

• مقدمه‌ای بر کلاس‌های پیچیدگی Introduction to Complexity Classes

• تعریف کلاس‌های P و NP و مثال‌ها Definition of P and NP Classes and Examples

• NP-Completeness: اهمیت NP-Completeness: Importance

• درک مفهوم NP-Completeness Understanding NP-Completeness

• کاهش (Reductions) در تئوری پیچیدگی Reductions in Complexity Theory

• NP-Hardness و تفاوت NP-Hard در مقابل NP-Complete NP-Hardness and NP-Hard versus NP-Complete

• مسئله ارضاپذیری (SAT) به عنوان یک مسئله NP-Complete Satisfiability Problem (SAT) as an NP-Complete Problem

• کاهش‌پذیری در زمان چندجمله‌ای: تعریف و مثال‌ها Polynomial Time Reducibility: Definition and Examples

• مسائل NP-Complete: مقدمه NP-Complete Problems: Introduction

• مسائل NP-Complete: مسائل کلیک (Clique)، پوشش مجموعه و مسئله دور هامیلتونی - بخش اول NP-Complete Problems: Clique and Set-Cover Problems and Hamiltonian Cycle Problem—Part I

• مسائل NP-Complete: مسائل کلیک، پوشش مجموعه و مسئله دور هامیلتونی - بخش دوم NP-Complete Problems: Clique and Set-Cover Problems and Hamiltonian Cycle Problem—Part II

• مسائل NP-Complete: مسائل کلیک، پوشش مجموعه و مسئله دور هامیلتونی - بخش سوم NP-Complete Problems: Clique and Set-Cover Problems and Hamiltonian Cycle Problem—Part III