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

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

حساب پیمانه‌ای Modular Arithmetic

• مرور کلی حساب پیمانه‌ای Modular Arithmetic Overview

• نظریه اعداد و مقدمه Number Theory & Intro

• تعریف بخش‌پذیری Divisibility_Definition

• ویژگی‌های بخش‌پذیری Divisibility_Properties of Divisibility

• (اختیاری) مثال بخش‌پذیری (Optional) Divisibility_Example

• قضیه تقسیم اقلیدس - اثبات وجود Divisibility_Euclid’s Division Theorem_Proof of Existence

• قضیه تقسیم اقلیدس - اثبات یکتایی Divisibility_Euclid’s Division Theorem_Proof of Uniqueness

• لم حساب پیمانه‌ای Modular Arithmetic_Lemma

• (اختیاری) مثال حساب پیمانه‌ای (Optional) Modular Arithmetic_Example

• قضیه ۱ و ۲ حساب پیمانه‌ای Modular Arithmetic_Theorem1 & 2

• حساب پیمانه‌ای در Zm Modular Arithmetic_Modular Arithmetic on Zm

• ویژگی‌های حساب پیمانه‌ای modulo m و اثبات شرکت‌پذیری Modular Arithmetic_Properties of Arithmetic Modulo m & Proof of Associativity

• معکوس‌های جمعی و ضربی Modular Arithmetic_Additive inverses and multiplicative inverses

• تعریف هم‌نهشتی و رابطه حساب پیمانه‌ای و هم‌نهشتی Congruences_Definition & Modular Arithmetic and Congruences

• قضیه و نتیجه هم‌نهشتی Congruences_Theorem & Corollary

• کاربردهای حساب پیمانه‌ای - بیت‌های توازن (Parity Bits) Applications of Modular Arithmetic_Parity Bits

• کاربردهای حساب پیمانه‌ای - اعداد تصادفی و شبه‌تصادفی Applications of Modular Arithmetic_Random Numbers & Pseudorandom Numbers

بزرگ‌ترین مقسوم‌علیه مشترک (GCD) Greatest Common Divisor

• مرور کلی GCD GCD Overview

• مقدمه GCD GCD_intro

• مرور پیش‌نیازهای ابتدایی Review of Primary School Knowledge

• تعریف بزرگ‌ترین مقسوم‌علیه مشترک Greatest Common Divisor_Definition

• الگوریتم اقلیدسی - لم Greatest Common Divisor_Euclidean Algorithm_Lemma

• (اختیاری) مثال الگوریتم اقلیدسی (Optional) Greatest Common Divisor_Euclidean Algorithm_Example

• GCD به عنوان ترکیبات خطی Greatest Common Divisor_gcds as Linear Combinations

• الگوریتم اقلیدسی توسعه‌یافته و معمای اندازه‌گیری آب Greatest Common Divisor_The Extended Euclidean Algorithm & Puzzle_Water Measuring

• معکوس ضربی - تعریف و قضیه Multiplicative Inverses_Definition & Theorem

• معکوس ضربی - اثبات یکتایی Multiplicative Inverses_Proof of uniqueness

• معکوس ضربی - مثال‌های یافتن معکوس Multiplicative Inverses_Finding Inverses_Examples

• حل هم‌نهشتی‌های خطی - نتیجه، اثبات و مثال Solving Linear Congruences_Corollary & Proof, Example

• حل هم‌نهشتی‌های خطی - بازبینی تابع هش رشته Solving Linear Congruences_Revisiting the String Hash Function

• حل هم‌نهشتی‌های خطی - مجموع چک HKID Solving Linear Congruences_HKID Checksum_Single & Transposition Error

• قضیه باقی‌مانده چینی - مسئله سون تسو و قضیه The Chinese Remainder Theorem_Sun-Tsu’s Problem & Theorem

• قضیه باقی‌مانده چینی - اثبات The Chinese Remainder Theorem_Proof

• (اختیاری) مثال قضیه باقی‌مانده چینی (Optional) The Chinese Remainder Theorem_Example

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

رمزنگاری Cryptography

• مرور کلی رمزنگاری Cryptography Overview

• رمزنگاری کلید متقارن (Secret Key) - مقدمه Secret Key Cryptography_Intro

• رمزنگاری کلید متقارن - رمز سزار (جابجایی) و مثال Secret Key Cryptography_Caesar Cipher (Shift Cipher) & Example

• رمزنگاری کلید متقارن - رمزهای آفین (Affine) Secret Key Cryptography_Affine Ciphers

• رمزنگاری کلید متقارن - رمزهای بلوکی Secret Key Cryptography_Block Ciphers

• رمزنگاری کلید متقارن - AES Secret Key Cryptography_AES

• تبادل کلید - مشکلات رمزنگاری کلید متقارن و معمای تبادل کلید Key Exchange_Problems with secret-key cryptography & The Key Exchange Puzzle

• تبادل کلید - توان‌رسانی پیمانه‌ای و تابع یک‌طرفه Key Exchange_Modular exponentiation & A One-Way Function_Modular Exponentiation and Logarithm

• تبادل کلید - لگاریتم گسسته و تبادل کلید دیفی-هلمن Key Exchange_Discrete Logarithm & Diffie-Hellman Key Exchange

• تبادل کلید - حمله مرد میانی (MITM) Key Exchange_Man-in-the-middle Attack

• رمزنگاری کلید عمومی و RSA - مقدمه Public Key Cryptography and RSA_Intro & Public Key Cryptography

• رمزنگاری کلید عمومی و RSA - سیستم رمزنگاری RSA Public Key Cryptography and RSA_The RSA Cryptosystem

• رمزنگاری کلید عمومی و RSA - تابع یک‌طرفه دیگر: ضرب و تجزیه Public Key Cryptography and RSA_Another one-way function_Multiplication and factoring

• رمزنگاری کلید عمومی و RSA - تولید کلید، رمزگذاری و رمزگشایی RSA Public Key Cryptography and RSA_Key Generator, RSA Encryption & Decryption, RSA in Use & Correctness

• رمزنگاری کلید عمومی و RSA - قضیه کوچک فرما - لم Public Key Cryptography and RSA_Fermat Little Theorem_Lemma

• رمزنگاری کلید عمومی و RSA - قضیه کوچک فرما، نتیجه و اثبات Public Key Cryptography and RSA_Fermat Little Theorem_Theorem, Corollary & Proof

• رمزنگاری کلید عمومی و RSA - اثبات درستی RSA Public Key Cryptography and RSA_RSA Correctness_Proof

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

الگوریتم‌ها Algorithms

• مرور کلی الگوریتم‌ها Algorithms Overview

• بازبینی الگوریتم مرتب‌سازی انتخابی و نحوه اندازه‌گیری زمان اجرا Revisiting the Selection Sort Algorithm & How to Measure the Running Time

• بازبینی الگوریتم مرتب‌سازی انتخابی - راه حل Revisiting the Selection Sort Algorithm_Solution

• رشد توابع The Growth of Functions

• بگ تتا (Big Theta) - تعریف Big-Theta_Definition

• بگ تتا - استفاده از تعریف برای استخراج تتا Big-Theta_Using Definition to Derive Big-Theta

• بگ تتا - مقایسه الگوریتم‌ها Big-Theta_Comparison of Algorithms

• بگ تتا - مثال‌های ۱ و حل سری‌های هندسی Big-Theta_Examples1 & Solving Geometric Series

• (اختیاری) بگ تتا - مثال‌های ۲ (Optional) Big-Theta_Examples2

• (اختیاری) بگ تتا - مثال‌های ۳ (Optional) Big-Theta_Examples3

• بگ تتا - محدودیت‌های بگ تتا Big-Theta_Limitation of Big-Theta

• مرور بگ او (Big Oh) و بگ امگا (Big Omega) Big-Oh & Big-Omega, Review

• مثال‌های بگ تتا، بگ او و بگ امگا Big-Theta, Big-Oh & Big-Omega_Examples

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

• تحلیل الگوریتم‌ها - تحلیل بدترین حالت Analysis of Algorithms_Worst-case Analysis

• (اختیاری) تحلیل الگوریتم‌ها - مثال جستجوی خطی (Optional) Analysis of Algorithms_Example_Linear Search

• (اختیاری) تحلیل الگوریتم‌ها - مثال جستجوی دودویی (Optional) Analysis of Algorithms_Example_Binary Search

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

استقراء Induction

• مرور کلی استقراء Induction Overview

• بالا رفتن از نردبان بی‌نهایت و اعتبار استقرای ریاضی Climbing an Infinite Ladder & Validity of Mathematical Induction

• اثبات مجموع‌ها - مثال ۱ و مزایا و معایب استقراء Proving Summations_Example1 & The Good and Bad of Induction

• (اختیاری) اثبات مجموع‌ها - مثال ۲ (Optional) Proving Summations_Example2

• (اختیاری) اثبات نامساوی‌ها - مثال ۱ و ۲ (Optional) Proving Inequalities_Example1 & 2

• اثبات نتایج بخش‌پذیری Proving Divisibility Results

• تعداد زیرمجموعه‌های یک مجموعه متناهی Number of Subsets of a Finite Set

• مسئله جنگ پای‌های فرد - اثبات Odd Pie Fight Problem_Proof

• کاشی‌کاری تخته شطرنج Tiling Checkerboards

• قضیه تقسیم اقلیدس Euclid’s Division Theorem

• انواع استقراء Variants of Induction

• استقرای قوی Strong Induction

• قضیه بنیادی حساب Fundamental Theorem of Arithmetic

• مسئله دو دسته کبریت Two Piles of Matches Problem

• اشتباهات در اثبات‌های استقرایی ۱ Mistakes in Proofs by Induction1

• اشتباهات در اثبات‌های استقرایی ۲ Mistakes in Proofs by Induction2

بازگشت Recursion

• مرور کلی بازگشت Recursion Overview

• توابع تعریف شده به صورت بازگشتی - از استقراء به بازگشت Recursively Defined Functions_From Induction to Recursion

• (اختیاری) توابع بازگشتی - مثال ۱ (Optional) Recursively Defined Functions_Example1

• (اختیاری) توابع بازگشتی - مثال ۲ (Optional) Recursively Defined Functions_Example2

• توابع بازگشتی - روابط بازگشتی و حل بازگشتی خطی مرتبه اول Recursively Defined Functions_Recurrences & Solving First-Order Linear Recurrence

• توابع بازگشتی - محاسبه وام مسکن Recursively Defined Functions_Mortgage Calculation

• توابع بازگشتی - شمارش خرگوش‌ها Recursively Defined Functions_Counting Rabbits

• توابع بازگشتی - اعداد فیبوناچی - مقدمه Recursively Defined Functions_Fibonacci Numbers_Intro

• (اختیاری) توابع بازگشتی - اعداد فیبوناچی - مثال ۱ (Optional) Recursively Defined Functions_Fibonacci Numbers_Example1

• (اختیاری) توابع بازگشتی - اعداد فیبوناچی - مثال ۲ (شمارش رشته‌های بیتی) (Optional) Recursively Defined Functions_Fibonacci Numbers_Example2_Counting Bit Strings

• توابع بازگشتی - بازبینی الگوریتم GCD اقلیدسی - لم Recursively Defined Functions_Revisiting Euclid’s GCD Algorithm_Lemma

• توابع بازگشتی - بازبینی الگوریتم GCD اقلیدسی - اثبات لم Recursively Defined Functions_Revisiting Euclid’s GCD Algorithm_Proof of Lemma

• سایر تعاریف بازگشتی - مجموعه‌های تعریف شده بازگشتی Other Recursively Definitions_Recursively Defined Sets

• سایر تعاریف بازگشتی - درخت‌های دودویی کامل Other Recursively Definitions_Full Binary Trees

• استقرای ساختاری - مثال ۱ و اثبات، چارچوب استقرای ساختاری Structural Induction_Example1 & Proof, Structural Induction Framework

• استقرای ساختاری - مثال ۲ (درخت‌های دودویی کامل) Structural Induction_Example2_Full Binary Trees

• استقرای ساختاری - مثال‌های بیشتر از تعریف بازگشتی و استقرای ساختاری Structural Induction_More examples on recursive definition and structural induction & Example3

• استقرای ساختاری - رشته‌ها Structural Induction_Strings

• استقرای ساختاری - پرانتزهای متوازن Structural Induction_Balanced Parentheses

• استقرای ساختاری - الحاق رشته‌ها Structural Induction_String Concatenation

• استقرای ساختاری - طول رشته Structural Induction_Length of a String

• (اختیاری) استقرای ساختاری - مثال ۴ (Optional) Structural Induction_Example4

• الگوریتم‌های بازگشتی - الگوریتم GCD اقلیدسی و اعداد فیبوناچی Recursive Algorithms_Recursive Algorithms, Euclid’s GCD Algorithm & Fibonacci Numbers

• الگوریتم‌های بازگشتی - برج هانوی Recursive Algorithms_The Tower of Hanoi

• الگوریتم‌های بازگشتی - جمع‌بندی Recursive Algorithms_Summary

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