آموزش ریاضیات گسسته برای علوم کامپیوتر - شمارش و احتمال - آخرین آپدیت

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

مقدمه‌ای بر ریاضیات گسسته برای علوم کامپیوتر (شمارش و احتمال) Introduction to Discrete Math for Computer Science (Counting & Probability)

مبانی شمارش Basics of Counting

• مروری بر مبانی شمارش Basics of Counting Overview

• مبانی شمارش_مقدمه Basics of Counting_intro

• قانون ضرب_مقدمه، مثال ۱ و ۲ Product Rule_Intro, Example1 & 2

• (اختیاری) قانون ضرب_مثال ۳ و ۴ (Optional) Product Rule_Example3 & 4

• (اختیاری) قانون ضرب_مثال ۵ و ۶ (Optional) Product Rule_Example5 & 6

• قانون جمع_مثال Sum Rule_Example

• (اختیاری) استفاده همزمان از قوانین ضرب و جمع_مثال ۱ (Optional) Using Both Product and Sum Rules_Example1

• (اختیاری) استفاده همزمان از قوانین ضرب و جمع_مثال ۲ (Optional) Using Both Product and Sum Rules_Example2

• (اختیاری) تمرینات کلاسی (Optional) InclassEx

• نمودارهای درختی_مقدمه، مثال ۱ و ۲ Tree Diagrams_Intro, Example1 & 2

• اصل لانه کبوتر_مقدمه و مثال ۱ The Pigeonhole Principle_Intro & Example1

• (اختیاری) اصل لانه کبوتر_مثال ۲ (Optional) The Pigeonhole Principle_Example2

• (اختیاری) اصل لانه کبوتر_مثال ۳ (Optional) The Pigeonhole Principle_Example3

• اصل لانه کبوتر_اصل لانه کبوتر تعمیم‌یافته_مقدمه و مثال ۱ The Pigeonhole Principle_Generalized Pigeonhole Principle_Intro & Example1

• (اختیاری) اصل لانه کبوتر_اصل لانه کبوتر تعمیم‌یافته_مثال ۲ و ۳ (Optional) The Pigeonhole Principle_Generalized Pigeonhole Principle_Example2 & 3

جایگشت‌ها و ترکیب‌ها Permutations and Combinations

• مروری بر جایگشت‌ها و ترکیب‌ها Permutations and Combinations Overview

• جایگشت‌ها و ترکیب‌ها_مقدمه Permutations and Combinations_intro

• (اختیاری) جایگشت‌ها_مثال ۱ (Optional) Permutations_Example1

• جایگشت‌ها_تعداد جایگشت‌های k Permutations_Number of k-Permutations

• (اختیاری) جایگشت‌ها_مثال ۲ و ۳ (Optional) Permutations_Example2 & 3

• جایگشت‌ها_تعریف جایگشت و جایگشت k Permutations_Permutation & k-Permutation Definition

• (اختیاری) جایگشت‌ها_مثال ۴، ۵ و ۶ (Optional) Permutations_Example4 & 5 & 6

• (اختیاری) جایگشت‌ها_مثال ۷ (Optional) Permutations_Example7

• ترکیب‌ها_مقدمه و ترکیب‌های k، اثبات Combinations_Intro & k-Combinations, Proof

• (اختیاری) ترکیب‌ها_مثال ۱ و ۲ (Optional) Combinations_Example1 & 2

• ترکیب‌ها_اثبات ترکیبیاتی و اصل یک‌به-یک_مقدمه و مثال‌ها Combinations_Combinatorial Proof and Bijection Principle_Intro & Examples

• جایگشت‌ها و ترکیب‌های تعمیم‌یافته_جایگشت‌های اشیاء غیر متمایز_مقدمه و مثال Generalized Permutations and Combinations_Permutations with Indistinguishable Objects_Intro & Example

• جایگشت‌ها و ترکیب‌های تعمیم‌یافته_توزیع اشیاء در جعبه‌ها_مقدمه و مثال Generalized Permutations and Combinations_Distributing Objects into Boxes_Intro & Example

• جایگشت‌ها و ترکیب‌های تعمیم‌یافته_اشیاء غیر متمایز در جعبه‌های متمایز_قضیه و مثال Generalized Permutations and Combinations_Indistinguishable objects Distinguishable boxes_Theorem & Example

• جایگشت‌ها و ترکیب‌های تعمیم‌یافته_ترکیب‌های تکرارپذیر_مقدمه و مثال‌ها Generalized Permutations and Combinations_Combinations with Repetition_Intro & Examples

• (اختیاری) تمرینات کلاسی (Optional) InclassEx

ضرایب دوجمله‌ای Binomial Coefficients

• مروری بر ضرایب دوجمله‌ای Binomial Coefficients Overview

• ضرایب دوجمله‌ای_مقدمه Binomial Coefficients_Intro

• قضیه دوجمله‌ای_مثال ۱، تعریف و اثبات Binomial Theorem_Example1, Definition & Proof

• (اختیاری) قضیه دوجمله‌ای_مثال ۲ و ۳ (Optional) Binomial Theorem_Example2 & 3

• قضیه دوجمله‌ای_نتیجه ۱ و اثبات ترکیبیاتی Binomial Theorem_Corollary1 & Combinatorial Proof

• قضیه دوجمله‌ای_نتیجه ۲ و مثلث پاسکال Binomial Theorem_Corollary2 & Pascal’s Triangle

• قضیه دوجمله‌ای_نتیجه ۳ Binomial Theorem_Corollary3

• همانی و مثلث پاسکال_همانی پاسکال و اثبات ترکیبیاتی آن Pascal’s Identity and Triangle_Pascal's Identity & Combinatorial proof of Pascal’s identity

• همانی و مثلث پاسکال_مثلث پاسکال Pascal’s Identity and Triangle_Pascal’s Triangle

• سایر همانی‌ها_همانی واندرموند Some Other Identities_Vandermonde's Identity

• سایر همانی‌ها_همانی واندرموند_نتیجه Some Other Identities_Vandermonde's Identity_Corollary

• سایر همانی‌ها_شمارش رشته‌های بیتی و اثبات Some Other Identities_Counting bit strings & Proof

• (اختیاری) تمرینات کلاسی (Optional) InclassEx

اصل شمول و عدم شمول The Inclusion-Exclusion Principle

• مروری بر اصل شمول و عدم شمول The Inclusion-Exclusion Principle Overview

• اصل شمول و عدم شمول_مقدمه The Inclusion-Exclusion Principle_Intro

• دو مجموعه متناهی_مقدمه و مثال‌ها Two Finite Sets_Intro & Examples

• سه مجموعه متناهی_مقدمه Three Finite Sets_Intro

• (اختیاری) سه مجموعه متناهی_مثال (Optional) Three Finite Sets_Example

• اصل شمول و عدم شمول_قضیه Inclusion-Exclusion Principle_Theorem

• اصل شمول و عدم شمول_اثبات Inclusion-Exclusion Principle_Proof

• تعداد توابع پوشا_مقدمه و مثال ۱ Number of Onto Functions_Intro & Example1

• (اختیاری) تعداد توابع پوشا_مثال ۲ (Optional) Number of Onto Functions_Example2

• جایگشت‌های بدون نقطه ثابت (Derangement)_مثال ۱ و اثبات Derangement_Example1 & Proof

• (اختیاری) جایگشت‌های بدون نقطه ثابت_مثال ۲ (Optional) Derangement_Example2

• احتمال جایگشت بدون نقطه ثابت Probability of a derangement

• (اختیاری) تمرینات کلاسی (Optional) InclassEx

مقدمه‌ای بر احتمال Introduction to Probability

• مروری بر مقدمات احتمال Introduction to Probability Overview

• بررسی مجدد مسئله کلاه‌گیر (Hatcheck) The Hatcheck Problem Revisited

• احتمال_تعاریف Probability_Definitions

• (اختیاری) احتمال_مثال (Optional) Probability_Example

• پوکر_مقدمه Poker_Intro

• (اختیاری) پوکر_مثال ۱ (Optional) Poker_Ex1

• (اختیاری) پوکر_مثال ۲ (Optional) Poker_Ex2

• (اختیاری) پوکر_مثال ۳ (Optional) Poker_Ex3

• (اختیاری) پوکر_مثال ۴ (Optional) Poker_Ex4

• بازی مارک سیکس (Mark Six) Mark Six

• نمونه‌گیری با جایگزینی و بدون جایگزینی Sampling with/without replacement

• متمم پیشامد_قضیه Complement of Event_Theorem

• (اختیاری) متمم پیشامد_مثال (Optional) Complement of Event_Example

• اتحاد پیشامدها و اصل شمول و عدم شمول برای احتمال، متمم و اتحاد پیشامدها Union of Events & Inclusion-Exclusion Principle for Probability, Complement and Union Events

• توزیع احتمالی Probability Distribution

• توزیع یکنواخت و توزیع غیر یکنواخت Uniform Distribution & Non-Uniform Distribution

• احتمال یک پیشامد Probability of an Event

• استقلال_تعریف Independence_Definition

• (اختیاری) استقلال_مثال‌ها (Optional) Independence_Examples

• استقلال دو به دو و استقلال متقابل Pairwise and Mutual Independence

• (اختیاری) تمرینات کلاسی (Optional) InclassEx

احتمال شرطی و قضیه بیز Conditional Probability and Bayes' Theorem

• مروری بر احتمال شرطی و قضیه بیز Conditional Probability and Bayes' Theorem Overview

• احتمال شرطی و قضیه بیز_مقدمه Conditional Probability and Bayes' Theorem_Intro

• احتمال شرطی Conditional Probability

• (اختیاری) احتمال شرطی_مثال ۱ (Optional) Conditional Probability_Example1

• (اختیاری) احتمال شرطی_مثال ۲ (Optional) Conditional Probability_Example2

• احتمال شرطی_مسئله تولد Conditional Probability_The Birthday Problem

• بررسی مجدد استقلال Independence Revisited

• بررسی مجدد مثال استقلال Independence Example Revisited

• قضیه بیز_قضیه و مثال ۱، توضیح Bayes’ Theorem_Theorem & Example1, Explanation

• (اختیاری) قضیه بیز_مثال ۲ (Optional) Bayes’ Theorem_Example2

• (اختیاری) قضیه بیز_مثال ۳ (Optional) Bayes’ Theorem_Example3

• فیلتر اسپم بیزی_مقدمه و مثال Bayesian Spam Filter_Intro & Example

• قضیه بیز تعمیم‌یافته_قضیه و مثال Generalized Bayes’ Theorem_Theorem & Example

• مسئله مونتی هال Monty Hall Problem

• (اختیاری) تمرینات کلاسی (Optional) InclassEx

متغیرهای تصادفی Random Variables

• مروری بر متغیرهای تصادفی Random Variables Overview

• متغیرهای تصادفی Random Variables

• توزیع یک متغیر تصادفی Distribution of a Random Variable

• آزمون‌های برنولی Bernoulli Trials

• توزیع دوجمله‌ای_قضیه و مثال Binomial Distribution_Theorem & Example

• توزیع احتمالی پیوسته Continuous Probability Distribution

• فضای نمونه نامتناهی Infinite Sample Space

• توزیع هندسی Geometric Distribution

• امید ریاضی_تعریف، قضیه و مثال Expected Value_Definition, Theorem & Example

• امید ریاضی_مثال توزیع دوجمله‌ای Expected Value_Example_Binomial Distribution

• خطی بودن امید ریاضی_قضیه و اثبات Linearity of Expectations_Theorem & Proof

• متغیرهای تصادفی نشانگر_مقدمه Indicator Random Variables_Intro

• (اختیاری) متغیرهای تصادفی نشانگر_مثال مسئله کلاه‌گیر (Optional) Indicator Random Variables_Example_the Hatcheck Problem

• (اختیاری) متغیرهای تصادفی نشانگر_مثال مسئله استخدام (Optional) Indicator Random Variables_Example_Hiring Problem

• (اختیاری) متغیرهای تصادفی نشانگر_مثال توپ‌ها و جعبه‌ها (Optional) Indicator Random Variables_Example_Balls and Bins

• تحلیل حالت متوسط الگوریتم‌ها_تعریف و مثال جستجوی خطی Average-case Analysis of Algorithms_Definition & Example_Linear Search

• (اختیاری) تحلیل حالت متوسط الگوریتم‌ها_مثال مرتب‌سازی درجی (Optional) Average-case Analysis of Algorithms_Example_Insertion Sort

• توزیع هندسی_تعریف و قضیه Geometric Distribution_Definition & Theorem

• (اختیاری) توزیع هندسی_مثال جمع‌کننده کوپن (Optional) Geometric Distribution_Example_Coupon Collector

• متغیرهای تصادفی مستقل_تعریف، قضیه و اثبات Independent Random Variables_Definition, Theorem & Proof

• (اختیاری) متغیرهای تصادفی مستقل_مثال (Optional) Independent Random Variables_Example

• واریانس و انحراف معیار_تعریف Variance and Standard Deviation_Definition

• واریانس_قضیه Variance_Theorem

• (اختیاری) واریانس_مثال (Optional) Variance_Example

• فرمول بینایمے_قضیه و اثبات Bienaymé’s Formula_Theorem & Proof

• (اختیاری) فرمول بینایمے_مثال ۱ (Optional) Bienaymé’s Formula_Example1

• (اختیاری) فرمول بینایمے_مثال ۲ (Optional) Bienaymé’s Formula_Example2

• (اختیاری) تمرینات کلاسی (Optional) InclassEx