کاربرد علوم ریاضی در کامپیوتر قسمت دوم

در قسمت قبلی با موضوع: کاربرد علوم ریاضی در کامپیوتر قسمت اول بود به کاربرد عناوین زیر در علوم کامپیوتر پرداختیم

۱. جبر بولی و منطق دیجیتال

۲. نظریه مجموعه‌ها و ساختار داده‌ها

۳. جبر خطی و گرافیک کامپیوتری

۴. حساب دیفرانسیل و انتگرال در شبیه‌سازی و بهینه‌سازی

در این قسمت به عناوین زیر خواهیم پرداخت:

۵. نظریه اعداد و رمزنگاری

۶. نظریه گراف و شبکه‌ها

۷. احتمال و آمار در یادگیری ماشین

۸. نظریه محاسبه و پیچیدگی

———————

 

۵. نظریه اعداد و رمزنگاری

۵.۱. مقدمه

نظریه اعداد (Number Theory) شاخه‌ای از ریاضیات است که با خواص اعداد صحیح و روابط میان آن‌ها سر و کار دارد. در ظاهر، ممکن است نظری باشد، اما در دنیای مدرن، این علم ستون فقرات رمزنگاری (Cryptography) و امنیت اطلاعات است.
از قفل گوشی تا تراکنش بانکی، از امضای دیجیتال تا بلاک‌چین بیت‌کوین — همه متکی به مفاهیم نظریه اعداد هستند.

۵.۲. مفاهیم پایه در نظریه اعداد

الف) تقسیم‌پذیری و ب.م.م (GCD)

اگر عدد aبر bبخش‌پذیر باشد، می‌نویسیم b∣a.
بزرگ‌ترین مقسوم‌علیه مشترک (GCD) دو عدد با الگوریتم اقلیدس (Euclidean Algorithm) محاسبه می‌شود.
مثلاً:

GCD(252,105)=21

در رمزنگاری، از این مفهوم برای محاسبه‌ی وارون پیمانه‌ای (Modular Inverse) استفاده می‌شود.

 

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

مبنای اصلی رمزنگاری مدرن است.
در این حساب، فقط با باقیمانده‌ی تقسیم سر و کار داریم:
a≡b(modn)یعنی(a-b) بر  n بخش‌پذیر است.

مثلاً:
17≡۵(mod12)

 

چون ۱۷-۵=۱۲.

این مفهوم پایه‌ی کل الگوریتم‌های RSA و ECC است.

 

ج) وارون پیمانه‌ای (Modular Inverse)

برای عدد a، وارون پیمانه‌ای a^-۱عددی است که:

a⋅a^-۱≡۱(modn)

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

 

د) اعداد اول (Prime Numbers)

سنگ‌بنای امنیت دیجیتال هستند.
یک عدد اول فقط دو مقسوم‌علیه دارد: خودش و ۱
رمزنگاری‌هایی مانند RSA بر پایه‌ی سختی فاکتورگیری حاصل‌ضرب دو عدد اول بسیار بزرگ ساخته شده‌اند.

 

۵.۳. رمزنگاری چیست؟

رمزنگاری (Cryptography) علمی است برای تبدیل داده‌ها به شکلی که فقط افراد مجاز بتوانند آن را بخوانند.
دو نوع اصلی دارد:
1. رمزنگاری متقارن (Symmetric Encryption) — کلید رمزگذاری و رمزگشایی یکی است.
مثال: AES
2. رمزنگاری نامتقارن (Asymmetric Encryption) — دو کلید متفاوت:
. کلید عمومی (Public Key) برای رمزگذاری
. کلید خصوصی (Private Key) برای رمزگشایی
رمزنگاری نامتقارن بر پایه‌ی نظریه اعداد ساخته شده است.

 

۵.۴. الگوریتم RSA — ستون امنیت دیجیتال

ایده‌ی اصلی
امنیت RSA بر پایه‌ی سختی فاکتورگیری (Factorization Problem) است:
اگر عدد بسیار بزرگی حاصل‌ضرب دو عدد اول باشد، یافتن آن دو عدد تقریباً غیرممکن است.
مراحل ساخت کلید RSA
1️⃣ انتخاب دو عدد اول بزرگ:
pو q
2️⃣ محاسبه‌ی حاصل‌ضرب:

n=p×q

۳️⃣ محاسبه‌ی تابع اویلر:

φ(n)=(p-1)(q-1)

۴️⃣ انتخاب عددی eکه نسبت به φ(n)متباین باشد:

GCD(e,φ(n))=1

معمولاً e = 65537 انتخاب می‌شود.
5️⃣ محاسبه‌ی وارون پیمانه‌ای d:
d≡e^(-1) (modφ(n))

۶️⃣ کلید عمومی = (e, n)
کلید خصوصی = (d, n)

رمزگذاری و رمزگشایی
اگر m پیام (به صورت عددی) باشد:
رمزگذاری:

c=m^e mod”  ” n

رمزگشایی:

m=c^d mod”  ” n

مثال ساده:
فرض کنیم:

p=11,q=17⇒n=187
φ(n)=160
e=7

d=23چون ۷×۲۳≡۱(mod160)

اگر پیام m=88:

c=88^۷ mod 187=11
m=11^۲۳ mod187=88

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

 

۵.۵. امضای دیجیتال (Digital Signature)

در دنیای اینترنت، باید بتوانیم اثبات کنیم چه کسی پیامی را ارسال کرده است.
امضای دیجیتال با استفاده از RSA یا ECC انجام می‌شود.
فرستنده پیام را با کلید خصوصی خود امضا می‌کند:

s=H(m)^d mod n

گیرنده با کلید عمومی امضا را بررسی می‌کند:

H(m)=?s^e mod n

در اینجا H(m)تابع هش پیام است.
مثلاً وقتی وارد وب‌سایتی با HTTPS می‌شوید، مرورگر شما این امضاها را بررسی می‌کند.

 

۵.۶. رمزنگاری منحنی بیضوی (Elliptic Curve Cryptography – ECC)

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

y^۲=x^۳+ax+b

محاسبات روی این منحنی، در فضای پیمانه‌ای انجام می‌شوند.
در ECC، عملیات اصلی جمع نقاط روی منحنی است.
امنیت آن بر پایه‌ی مسئله لگاریتم گسسته بیضوی (Elliptic Curve Discrete Logarithm Problem) است که حل آن بسیار سخت‌تر از فاکتورگیری RSA است.

مزایا:
. امنیت بیشتر با اندازه کلید کمتر
. سرعت بالاتر
. مصرف انرژی پایین‌تر مهم برای موبایل و IoT
به همین دلیل امروزه بیشتر فناوری‌ها از ECC استفاده می‌کنند:
بیت‌کوین (کلیدهای ECDSA)
TLS/HTTPS
کیف‌پول‌های سخت‌افزاری

 

۵.۷. نظریه اعداد در بلاک‌چین و ارز دیجیتال

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

Public Key=k×G

که Gنقطه‌ی پایه‌ی منحنی است و kکلید خصوصی است.
محاسبه G×kآسان است،
اما برعکس آن (یعنی پیدا کردن kاز Gو PublicKey) عملاً غیرممکن است.

 

۵.۸. نقش نظریه اعداد در دنیای واقعی

کاربرد	مفهوم ریاضی	توضیح
HTTPS / SSL	حساب پیمانه‌ای و RSA	رمزگذاری ارتباطات اینترنتی
کارت‌های بانکی	امضای دیجیتال	تأیید هویت تراکنش‌ها
ارزهای دیجیتال	ECC و هش	امنیت کیف‌پول و تراکنش‌ها
امضای نرم‌افزارها	RSA / DSA	اطمینان از منبع معتبر
رمزنگاری کوانتومی	نظریه اعداد پیشرفته	محافظت در برابر کامپیوترهای کوانتومی

 

۵.۹. آینده نظریه اعداد در رمزنگاری

در آینده نزدیک، با ظهور رایانش کوانتومی (Quantum Computing)، بسیاری از الگوریتم‌های کنونی مانند RSA در خطر خواهند بود.
چون الگوریتم Shor می‌تواند فاکتورگیری را در زمان چندجمله‌ای انجام دهد.
بنابراین پژوهشگران در حال توسعه‌ی رمزنگاری‌های جدیدی هستند به نام Post-Quantum Cryptography، که بر پایه‌ی نظریه اعداد پیچیده‌تر (مثل شبکه‌ها، ایزومورفیسم گراف، و چندجمله‌ای‌ها) بنا شده‌اند.

۶. نظریه گراف و شبکه‌ها

۶.۱. مقدمه

نظریه گراف (Graph Theory) شاخه‌ای از ریاضیات است که به مطالعه‌ی ارتباط بین اشیاء (نودها) و رابطه‌های میان آن‌ها (یال‌ها) می‌پردازد.
در دنیای کامپیوتر، گراف‌ها به‌طور گسترده برای نمایش ارتباطات استفاده می‌شوند:
. شبکه‌های اجتماعی (ارتباط کاربران)
. اینترنت (ارتباط بین سرورها)
. نقشه‌ها و سیستم‌های مسیریابی (راه‌ها و مسیرها)
. هوش مصنوعی و شبکه‌های عصبی گرافی (GNN)
. بیوانفورماتیک (تحلیل ژن‌ها و پروتئین‌ها)

به بیان ساده:
گراف، مدل ریاضی دنیای ارتباطات است؛ هر جا که «چیزی به چیزی وصل است»، در واقع گرافی در پشت آن نهفته است.

 

۶.۲. ساختار گراف

یک گراف (Graph) از دو بخش اصلی تشکیل شده است:

G=(V,E)

که:
. V: مجموعه رأس‌ها (Vertices)
. E: مجموعه یال‌ها (Edges)
مثلاً در شبکه اجتماعی:
. هر کاربر = یک رأس
. هر دوستی = یک یال

 

گراف جهت‌دار (Directed Graph)
در آن یال‌ها جهت دارند.
مثلاً در توییتر، اگر A، B را دنبال کند، لزوماً B هم A را دنبال نمی‌کند.

گراف بدون جهت (Undirected Graph)
در آن ارتباط‌ها دوطرفه‌اند.
مثلاً در فیس‌بوک، دوستی دوطرفه است.

گراف وزن‌دار (Weighted Graph)
هر یال دارای عددی است که نشان‌دهنده هزینه، فاصله یا زمان است.
مثلاً در نقشه گوگل، وزن مسیر = زمان سفر یا فاصله است.

 

۶.۳. نمایش گراف در کامپیوتر

دو روش متداول برای نمایش گراف‌ها وجود دارد:

۱. لیست مجاورت (Adjacency List)

هر رأس، فهرستی از رأس‌های متصل به خودش دارد.
برای گراف‌های بزرگ و کم‌تراکم (Sparse) مناسب است.
مثال:
A → [B, C]
B → [A, D]
C → [A]
D → [B]

۲. ماتریس مجاورت (Adjacency Matrix)

یک ماتریس n×nکه در آن:

برای گراف‌های متراکم (Dense) مناسب است.

 

۶.۴. الگوریتم‌های پایه در نظریه گراف

 

۱. جستجوی عرضی (BFS – Breadth First Search)

برای پیمایش گراف از یک رأس و بررسی تمام همسایه‌ها در هر سطح.
کاربردها:
. پیدا کردن کوتاه‌ترین مسیر در گراف‌های بدون وزن
. پیشنهاد دوستان در شبکه‌های اجتماعی
مثال:
در فیس‌بوک، اگر A با B دوست است و B با C، الگوریتم BFS پیشنهاد می‌دهد که A با C دوست شود.

 

۲. جستجوی عمقی (DFS – Depth First Search)

پیمایش گراف با رفتن به عمق تا رسیدن به بن‌بست.
کاربردها:
. یافتن حلقه‌ها (Cycles)
. مرتب‌سازی توپولوژیک (در گراف‌های جهت‌دار)
. تشخیص مؤلفه‌های هم‌بند (Connected Components)

 

۳. الگوریتم Dijkstra — کوتاه‌ترین مسیر

در گراف‌های وزن‌دار، Dijkstra مسیر کم‌هزینه‌ترین بین دو رأس را پیدا می‌کند.
ایده:
هر بار نزدیک‌ترین رأس را از مبدأ انتخاب می‌کند و مسیرهای آن را به‌روزرسانی می‌کند تا به مقصد برسد.
کاربردها:
. مسیر در GPS و Google Maps
. مسیریابی در شبکه‌های کامپیوتری
. کنترل ترافیک شهری
مثلاً اگر بخواهی از تهران به مشهد با کمترین هزینه سفر کنی، Dijkstra تمام مسیرها و فواصل را بررسی می‌کند تا کوتاه‌ترین را بیابد.

۴. الگوریتم Bellman-Ford

مشابه Dijkstra، اما می‌تواند با وزن‌های منفی نیز کار کند (مثلاً در تحلیل اقتصادی یا شبکه‌های جریان).

۵. الگوریتم Floyd-Warshall

برای یافتن کوتاه‌ترین مسیر بین همه‌ی جفت رأس‌ها (All Pairs Shortest Path).
در شبکه‌های ارتباطی برای محاسبه سریع‌ترین مسیر بین تمام گره‌ها به کار می‌رود.

 

۶.۵. نظریه گراف در موتور جستجو PageRank گوگل

الگوریتم PageRank که گوگل را به شهرت رساند، یکی از زیباترین کاربردهای نظریه گراف است.
در وب، هر صفحه یک رأس و هر لینک یک یال است.
PageRank میزان اهمیت هر صفحه را بر اساس تعداد و کیفیت لینک‌ها محاسبه می‌کند.
فرمول ساده‌شده:

PR(A)=(1-d)+d∑_B∈M(A) (PR(B))/(L(B))

که:
. M(A): صفحاتی که به A لینک داده‌اند
. L(B): تعداد لینک‌های خروجی از صفحه B
. d: ضریب میرایی (معمولاً ۰.۸۵)

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

 

۶.۶. نظریه گراف در شبکه‌های اجتماعی

در شبکه‌های اجتماعی، نظریه گراف ابزار تحلیل ارتباطات انسانی است.

مفهوم شبکه اجتماعی	مفهوم ریاضی در گراف
کاربر	رأس (Node)
ارتباط (دوستی/فالو)	یال (Edge)
گروه‌ها	مؤلفه‌های هم‌بند
نفوذ کاربران	درجه‌ی رأس (Degree)
محبوبیت	Centrality

 

معیارهای تحلیل شبکه
Degree Centrality – تعداد ارتباطات مستقیم
Betweenness Centrality – میزان نقش در اتصال سایر گره‌ها
Closeness Centrality – فاصله میانگین از سایر گره‌ها
مثال:
در اینستاگرام، کاربری که بیشترین فالوور را دارد، مرکز گراف شبکه است (درجه بالا).
اما کاربری که بین چند گروه ارتباط برقرار می‌کند، از نظر Betweenness مهم‌تر است، چون در انتقال اطلاعات نقش کلیدی دارد.

 

۶.۷. نظریه گراف در هوش مصنوعی

در چند سال اخیر، نظریه گراف وارد قلب یادگیری ماشین شده است — با ظهور شبکه‌های عصبی گرافی (Graph Neural Networks – GNNs).
ایده‌ی اصلی GNN
هر گره داده‌ای دارد (مثلاً ویژگی‌های کاربر یا اتم در مولکول).
مدل یاد می‌گیرد اطلاعات را از همسایه‌ها جمع کند و ویژگی‌های گراف را بیاموزد.
کاربردها:
. تحلیل شبکه‌های اجتماعی
. پیش‌بینی ساختار مولکول‌ها در داروسازی
. تشخیص کلاهبرداری در تراکنش‌های مالی
. سیستم‌های پیشنهاد هوشمند (مثل نتفلیکس یا آمازون)

 

۶.۸. گراف در شبکه‌های کامپیوتری

شبکه‌های رایانه‌ای مانند اینترنت خود یک گراف عظیم هستند:
. روترها = رأس‌ها
. کابل‌ها و اتصالات = یال‌ها
پروتکل‌هایی مانند OSPF و BGP از الگوریتم‌های Dijkstra و Bellman-Ford برای مسیریابی بسته‌ها استفاده می‌کنند.
هر بسته داده، مسیرش را از میان هزاران نود اینترنت بر اساس کوتاه‌ترین یا سریع‌ترین مسیر انتخاب می‌کند.

 

۶.۹. گراف در علوم زیستی و تحلیل داده

در بیوانفورماتیک، گراف‌ها برای مدل‌سازی روابط ژنتیکی و پروتئینی استفاده می‌شوند:
. شبکه تعامل پروتئین‌ها (Protein Interaction Networks)
. گراف مسیرهای متابولیکی
. گراف‌های DNA برای مقایسه ژن‌ها
همچنین در تحلیل داده‌های بزرگ (Big Data)، داده‌ها اغلب به شکل گراف ذخیره می‌شوند تا جستجو و تحلیل ارتباطات مؤثرتر شود.

 

۶.۱۰. کاربردهای واقعی

حوزه	کاربرد نظریه گراف	مثال واقعی
موتورهای جستجو	رتبه‌بندی صفحات	PageRank گوگل
شبکه‌های اجتماعی	تحلیل ارتباطات	Facebook Graph API
مسیریابی	یافتن کوتاه‌ترین مسیر	GPS و گوگل‌مپ
شبکه‌های کامپیوتری	الگوریتم‌های مسیر	پروتکل OSPF
هوش مصنوعی	شبکه‌های عصبی گرافی	پیش‌بینی ارتباطات
بیوانفورماتیک	تحلیل ژن و پروتئین	شبکه‌های زیستی

 

۷. احتمال و آمار در یادگیری ماشین

۷.۱. مقدمه

هوش مصنوعی (AI) و یادگیری ماشین (ML) بر این ایده استوارند که:
ماشین‌ها می‌توانند از داده‌ها «الگو» یاد بگیرند و بر اساس احتمال تصمیم بگیرند.
ریاضیات پشت این یادگیری، احتمال (Probability) و آمار (Statistics) است.
در واقع:
. احتمال به ما می‌گوید چه چیزی ممکن است اتفاق بیفتد.
. آمار به ما می‌گوید با مشاهده داده‌ها، احتمال وقوع هر چیز چقدر است.

 

۷.۲. مفاهیم پایه

۱. متغیر تصادفی (Random Variable)

یک تابع است که به هر نتیجه ممکن، عددی نسبت می‌دهد.
مثلاً:
. پرتاب سکه: X=1 برای شیر، X=0 برای خط.
. دمای هوا، نتیجه امتحان، یا احتمال خرید محصول.

 

۲. تابع چگالی احتمال (Probability Density Function – PDF)

در متغیرهای پیوسته، چگالی احتمال توزیع داده‌ها را نشان می‌دهد.
مثلاً در یک مدل نرمال (Normal Distribution):

f(x)=1/√(۲πσ^۲ ) e-^{((x-μ)۲)/(۲σ۲ )}

بیشتر داده‌های دنیای واقعی — از قد انسان گرفته تا خطای مدل — به‌طور تقریبی نرمال هستند.

 

۳. قانون بیز (Bayes’ Theorem)

یکی از بنیادی‌ترین مفاهیم در یادگیری ماشین و فیلتر اسپم:

P(A∣B)=(P(B∣A)×P(A))/(P(B))

یعنی:
احتمال رخداد A با دانستن B، برابر است با احتمال B در صورت وقوع A، ضرب‌در احتمال کلی A، تقسیم بر احتمال کلی B.

 

۷.۳. کاربرد قانون بیز — فیلتر اسپم Gmail

در فیلتر اسپم، گوگل بررسی می‌کند که یک ایمیل چقدر احتمال دارد هرزنامه باشد.
فرض کنید:
. A = «ایمیل اسپم است»
. B = «در ایمیل کلمه Free آمده است»
با استفاده از قانون بیز:

P(Spam∣Free)=(P(Free ∣Spam )×P(Spam ))/(P(Free))

اگر احتمال ظاهر شدن کلمه «Free» در اسپم‌ها زیاد باشد، و در ایمیل‌های عادی کم، آنگاه احتمال اسپم بودن ایمیل بالا می‌رود.
این دقیقاً اساس فیلتر بیزی ناایو (Naive Bayes Classifier) است — یکی از ساده‌ترین و مؤثرترین الگوریتم‌های یادگیری ماشین.

 

۷.۴. نقش آمار در یادگیری از داده‌ها

آمار به مدل‌ها کمک می‌کند از داده‌ها یاد بگیرند و قضاوت کنند.
نمونه‌گیری (Sampling)
به جای مشاهده کل جمعیت، داده‌ها را از نمونه‌ها به‌دست می‌آوریم.
مثلاً برای پیش‌بینی انتخابات، فقط از چند هزار نفر نظرسنجی می‌شود.
برآورد (Estimation)
تخمین پارامترهای توزیع داده‌ها، مثل میانگین (μ) و واریانس (σ^۲).
آزمون فرضیه (Hypothesis Testing)
برای تصمیم‌گیری بر اساس داده‌ها.
مثلاً در طراحی وب‌سایت، تست می‌کنیم آیا نسخه جدید دکمه “خرید” واقعاً نرخ کلیک را بالا می‌برد یا نه؟

 

۷.۵. A/B Testing — آمار در تصمیم‌گیری

آزمایش A/B یکی از کاربردهای عملی آمار در کسب‌وکار دیجیتال است.
مثلاً:
. نسخه A از وب‌سایت دکمه آبی دارد
. نسخه B دکمه سبز
با اجرای تست روی هزاران کاربر، با تحلیل آماری بررسی می‌کنیم:
آیا تفاوت نرخ کلیک (CTR) بین دو نسخه معنادار (Statistically Significant) است؟
فرمول آزمون z:

z=(X ˉ_۱-X ˉ_۲)/√((σ_1^۲)/n_۱ +(σ_2^۲)/n_۲ )

اگر مقدار z از حد بحرانی بیشتر باشد ⇒ نسخه برنده انتخاب می‌شود.
گوگل، نتفلیکس، آمازون و تیک‌تاک هر روز صدها A/B تست برای بهینه‌سازی رابط کاربری اجرا می‌کنند.

 

۷.۶. احتمال در مدل‌های یادگیری ماشین

در یادگیری ماشین، مدل‌ها خروجی‌های خود را به صورت احتمال بیان می‌کنند.
تابع Softmax در شبکه‌های عصبی
در مسأله‌های چندکلاسه، خروجی شبکه با تابع Softmax به احتمال هر کلاس تبدیل می‌شود:

P(y_i)=e^{(zi )}/∑_j e(z_j ) 

مثلاً در تشخیص تصویر:
– P(Cat)=0.9
– P(Dog)=0.07
– P(Car)=0.03
مدل می‌گوید: «با احتمال ۹۰٪ این تصویر گربه است»

 

۷.۷. تابع زیان (Loss Function) و آمار

برای آموزش مدل، باید میزان خطا را اندازه بگیریم.
در یادگیری ماشین، تابع زیان (Loss Function) معیار اختلاف بین پیش‌بینی و واقعیت است.
مثلاً در طبقه‌بندی:

L=-∑y_i log⁡(y ̂_i)

که همان Cross-Entropy Loss است — ارتباط مستقیم با مفهوم انتروپی در نظریه اطلاعات و آمار دارد.

 

۷.۸. آمار و واریانس در مدل‌ها

مدل‌های یادگیری ممکن است:
– Bias بالا (سوگیری زیاد) داشته باشند ⇒ مدل ساده است و الگو را درست یاد نمی‌گیرد.
– Variance بالا (تغییرپذیری زیاد) ⇒ مدل بیش از حد از داده‌ها یاد گرفته (Overfitting).
هدف یادگیری آماری:
یافتن تعادل میان Bias و Variance، برای تعمیم بهتر روی داده‌های جدید.

 

۷.۹. احتمالات در مدل‌های مولد (Generative Models)

در مدل‌های پیشرفته مانند ChatGPT، DALL·E یا Stable Diffusion ، همه‌چیز بر پایه احتمال است:
– مدل احتمال توزیع داده‌ها را یاد می‌گیرد
– سپس از آن توزیع، نمونه‌گیری (Sampling) می‌کند تا داده جدید بسازد
در واقع، مدل‌های مولد یاد می‌گیرند احتمال وجود یک داده را پیش‌بینی کنند.

 

۷.۱۰. کاربردهای واقعی احتمال و آمار در کامپیوتر

حوزه	کاربرد	مثال واقعی
فیلتر اسپم	مدل بیزی	Gmail
پیشنهاد محتوا	مدل احتمالی کاربر	YouTube / Netflix
یادگیری عمیق	Softmax و Cross-Entropy	بینایی ماشین
تصمیم‌گیری تجاری	A/B Testing	Amazon UX
تحلیل داده	رگرسیون، توزیع نرمال	Excel, Pandas
شبیه‌سازی	مونت‌کارلو (Monte Carlo Simulation)	پیش‌بینی ریسک مالی

 

۸. نظریه محاسبه و پیچیدگی (پایه‌گذار منطق محاسبات مدرن)

۸.۱. مقدمه

آیا هر مسئله‌ای را می‌توان با کامپیوتر حل کرد؟
و اگر بله، «چقدر سریع می‌توان آن را حل کرد؟»
این دو پرسش فلسفی اساس نظریه محاسبه (Computability) و پیچیدگی (Complexity Theory) را تشکیل می‌دهند.
به زبان ساده:
– نظریه محاسبه: چه چیزهایی را می‌توان محاسبه کرد.
– نظریه پیچیدگی: آن محاسبه چقدر زمان و حافظه نیاز دارد.

 

۸.۲. ماشین تورینگ — مدل انتزاعی کامپیوتر

در دهه ۱۹۳۰، آلن تورینگ (Alan Turing) مفهوم «ماشین تورینگ» را معرفی کرد تا مفهوم محاسبه را به‌شکل ریاضی تعریف کند.
ماشین تورینگ شامل:
– نواری بی‌نهایت از سلول‌ها (حافظه)
– هد خواندن/نوشتن (مثل CPU)
– مجموعه‌ای از وضعیت‌ها (States)
– جدولی از قوانین انتقال (Transition Table)
این ماشین می‌تواند هر محاسبه منطقی ممکن را انجام دهد — اگر زمان و حافظه بی‌نهایت داشته باشد.
امروزه، هر زبان برنامه‌نویسی Python، C++، Java عملاً معادل با یک ماشین تورینگ است.

 

۸.۳. محاسبه‌پذیر و غیرمحاسبه‌پذیر

مسائل را می‌توان به دو دسته تقسیم کرد:

نوع مسئله	توضیح	مثال
محاسبه‌پذیر (Computable)	می‌توان با الگوریتم آن را حل کرد.	جمع دو عدد، جستجو در فهرست
غیرمحاسبه‌پذیر (Uncomputable)	هیچ الگوریتمی وجود ندارد که همیشه جواب بدهد.	مسئله توقف (Halting Problem)

مسئله توقف (Halting Problem):
آیا می‌توان برنامه‌ای نوشت که تشخیص دهد هر برنامه‌ی دیگری متوقف می‌شود یا تا ابد اجرا می‌شود؟
تورینگ ثابت کرد پاسخ خیر است — یعنی محدودیت ذاتی در توان کامپیوتر وجود دارد.

 

۸.۴. نظریه پیچیدگی محاسباتی

حال فرض کنیم مسئله‌ای قابل حل است؛ پرسش بعدی این است:
حل آن مسئله چقدر طول می‌کشد؟
اینجاست که مفهوم زمان محاسباتی (Time Complexity) و فضا (Space Complexity) وارد می‌شود.

 

۸.۵. نماد Big-O — اندازه‌گیری رشد زمان

برای تحلیل الگوریتم‌ها از نماد Big-O استفاده می‌شود تا نشان دهد زمان اجرا چگونه با افزایش اندازه داده رشد می‌کند.

مرتبه پیچیدگی	مثال	توضیح
O(1)	دسترسی به عنصر آرایه	زمان ثابت
O(log⁡n)	جستجوی دودویی	رشد آرام
O(n)	پیمایش لیست	خطی
O(nlog⁡n)	QuickSort، MergeSort	بهینه برای مرتب‌سازی
O(n۲)	الگوریتم‌های ساده ماتریسی	کند برای داده‌های بزرگ
O(2n)	حل مسئله n-Queen با brute-force	بسیار سخت
O(n!)	مسئله فروشنده دوره‌گرد	تقریباً غیرممکن در مقیاس بزرگ

 

۸.۶. طبقه‌بندی مسائل — P و NP

در نظریه پیچیدگی، مسائل بر اساس سختی حل‌شان به چند دسته تقسیم می‌شوند.
P (Polynomial Time)
مسائلی که در زمان چندجمله‌ای قابل حل‌اند.
مثلاً مرتب‌سازی، جستجوی باینری.
NP (Nondeterministic Polynomial)
مسائلی که جواب‌شان به‌سرعت قابل بررسی است، اما شاید حل‌شان سخت باشد.
مثلاً:
– مسئله فروشنده دوره‌گرد (TSP)
– رنگ‌آمیزی گراف
– تقسیم‌بندی مجموعه‌ها
اگر بتوانیم راه‌حل را حدس بزنیم، می‌توانیم صحت آن را سریع بررسی کنیم.

 

۸.۷. معمای بزرگ دنیای ریاضی: P vs NP

پرسش اصلی:
آیا هر مسئله‌ای که جواب آن را می‌توان به‌سرعت بررسی کرد (NP)، را می‌توان به‌سرعت حل کرد (P)؟
یعنی آیا P=NPاست یا خیر؟
هیچ‌کس هنوز جواب قطعی ندارد!
حل این مسئله یکی از ۷ مسئله هزاره ریاضی است که ۱ میلیون دلار جایزه دارد.
اگر ثابت شود P=NP، دنیای کامپیوتر دگرگون می‌شود:
رمزنگاری فعلی از بین می‌رود RSA شکسته می‌شود
بسیاری از مسائل سخت (مثل فشرده‌سازی بهینه، طراحی دارو، برنامه‌ریزی) قابل حل سریع می‌شوند.

 

۸.۸. NP-Complete — سخت‌ترین مسائل قابل بررسی

دسته‌ی خاصی از مسائل NP وجود دارد به نام NP-Complete:
اگر بتوانیم یکی از آن‌ها را سریع حل کنیم، بقیه هم قابل حل خواهند بود.
مثال‌ها:
– مسئله کوله‌پشتی (Knapsack Problem)
– مسئله مسیر همیلتونی
– مسئله رنگ‌آمیزی گراف
Sudoku
این مسائل پایه بسیاری از چالش‌های مهندسی، بهینه‌سازی، و حتی بازی‌های کامپیوتری‌اند.

 

۸.۹. کاربردهای نظریه پیچیدگی

حوزه	کاربرد	توضیح
رمزنگاری	امنیت RSA و AES	سختی فاکتورگیری عدد بزرگ
بهینه‌سازی	الگوریتم‌های ژنتیک، شبیه‌سازی تبرید	تقریب برای مسائل NP-Complete
یادگیری ماشین	تحلیل هزینه آموزش مدل	پیچیدگی محاسبه گرادیان‌ها
هوش مصنوعی	جستجو در فضاهای حالت بزرگ	الگوریتم‌های Heuristic مثل A*
رایانش ابری	تخصیص منابع	NP-hard Scheduling

 

۸.۱۰. الگوریتم‌های تقریبی و تصادفی

چون بسیاری از مسائل NP-Complete را نمی‌توان دقیق حل کرد، از الگوریتم‌های تقریبی (Approximation Algorithms) یا احتمالی (Randomized Algorithms) استفاده می‌شود.
مثال‌ها:
– Monte Carlo Simulation: برآورد جواب با نمونه‌گیری تصادفی
– Simulated Annealing: جستجوی تدریجی در فضای پاسخ
– Genetic Algorithms: شبیه‌سازی تکامل طبیعی برای یافتن پاسخ‌های خوب
این الگوریتم‌ها در هوش مصنوعی و طراحی صنعتی کاربرد گسترده دارند.

 

۸.۱۱. نظریه محاسبه در رایانش کوانتومی

در کامپیوترهای کوانتومی، مدل محاسبه از کلاسیک به احتمالی کوانتومی تغییر می‌کند.
الگوریتم‌هایی مانند:
– Shor’s Algorithm: تجزیه عددهای بزرگ در زمان چندجمله‌ای ⇒ تهدیدی برای RSA
– Grover’s Algorithm: جستجوی سریع‌تر در پایگاه داده‌ها در O(√n)
بنابراین نظریه پیچیدگی کوانتومی، مرز جدیدی برای تعریف کلاس‌های جدید مثل BQP (Bounded Quantum Polynomial) ایجاد کرده است.

 

۸.۱۲. ارتباط با ریاضیات دیگر

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