سلام

با سلام و خیر مقدم به همه دانش پژوهان عزیز خصوصا علاقه مندان رشته زیبای ریاضی.

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

به امید روزی که همه دانش آموزان و دانشجویان عزیز به ریاضیات عاشقانه بنگرند.

+ نوشته شده در چهارشنبه هشتم مهر ۱۳۸۸ ساعت 3:21 توسط حسن نوری اصفهانی |

تانسور

تانسور عنصری هندسی است که در ریاضی و فیزیک به منظور گسترش مفاهیم اسکالرها، بردارهای هندسی و ماتریس‌ها به ابعاد بالاتر معرفی می‌شوند. تانسورها اولین بار توسطتولیو لوی چیویتا(Tullio Levi-Civita) و جورجیو ریچی-کورباسترو (Gregorio Ricci-Curbastro) ابداع شدند. در واقع کار آن‌ها ادامه کارهای برنارد ریمان(Bernhard Riemann)و الوین برونو کریستوفل (Elwin Bruno Christoffel)و دیگران در حساب دیفرانسیل مطلق بود.

تانسور آرایه‌ای است از اعداد که در یک جدول چیده شده‌اند. این جدول در حالت کلی می‌تواند به صورت $N \times M \times O \times P \times...$ باشد که حروف بزرگ هر کدام می‌توانند نمایندهٔ یک عدد طبیعی باشند و $\times$ نشان دهندهٔ عمل ضرب بین آنهاست. تانسور در ساده‌ترین حالت می‌تواند یک عضو داشته باشد که به آن تانسور، اسکالر گوییم. در حالت کمی پیشرفته تر تانسور می‌تواند به صورت بردار باشد. یعنی وقتی شما بردار $A$ را به صورت $(x, y, z)$ نشان می‌دهید در حقیقت یک تانسور دارید. در حالتی باز هم پیشرفته تر تانسور می‌تواند دو بعدی باشد (به صورت ماتریسی). یعنی مثلاً جدول ما $2 \times 2$ باشد یعنی دو سطر و دو ستون داشته باشد.

چنین تانسوری دارای ۴ عضو است. به طور کلی تانسورهای دو بعدی و بالاتر از دو بعد را با نام ماتریس هم می‌شناسند. ماتریس‌ها از آن جهت مورد استفاده قرار می‌گیرند که باعث ایجاد نظم بین داده‌های یک مسئله و دسته بندی اطلاعات آن می‌شوند.

تعریف فوق همراه با ساده‌سازی بسیار است. یک تعریف دقیق‌تر از این قرار است:

یک تانسور رتبه (۰,۱) و $N$ -بعدی حقیقی مانند $T$ نگاشتی است خطی از $\mathbb{R}^N$ به $\mathbb{R}$ یعنی:

$T(ax + by) = aT(x) + bT(y), \qquad \forall x,y \in \mathbb{R}^N \hbox{ and } a,b \in \mathbb{R}.$

اگر $\{e_n\}_{n=1}^{n=N}$ یک پایه برای $\mathbb{R}^N$ باشد، آنگاه به مجموعه $N$ عدد $T n$ که از

$T (e n) = T n$

به دست می‌آیند مؤلفه‌های $T$ در پایه $\{e_n\}_{n=1}^{n=N}$ می‌گویند. می‌توان دید که مؤلفه‌های این تانسور، تحت تغییر پایه، رفتاری شبیه مؤلفه‌های یک بردار پادهموردا دارند. با یک نگاه کلی‌تر می‌توانیم $\mathbb{R}^N$ را با یک فضای برداری $N$ -بعدی دلخواه چون $V$ عوض کنیم. در این صورت معمول است که مجموعهٔ همه چنین تانسورهایی را با $V *$ نشان دهیم.

به طور مشابه یک تانسور رتبه (۰,۲) به عنوان یک نکاشت دو-خطی از $V \times V$ به $\mathbb{R}$ تعریف می‌شود:

$T(ax + by, z) = aT(x, z) + bT(y, z), \qquad \forall x,y,z \in V \hbox{ and } a,b \in \mathbb{R},$ $T(z, ax + by) = aT(z, x) + bT(z, y), \qquad \forall x,y,z \in V \hbox{ and } a,b \in \mathbb{R}.$

این بار به مجموعه $N 2$ عدد $T m, n$ که با

$T (e m, e n) = T m, n$

تعریف می‌شوند مؤلفه‌های تانسور $T$ گفته می‌شود ( $\{e_n\}_{n=1}^{n=N}$ پایهٔ $V$ است). مجموعه تمام این تانسورها را با $V^* \otimes V^*$ نشان می‌دهیم و می‌نویسیم: $T \in V^* \otimes V^*$ .

یک تانسور (۱,۰) چون $T$ عضوی است از فضای برداری $V$ . مؤلفه‌های این تانسور با شاخص‌های بالا و بدین ترتیب تعریف می‌شوند:

$T = \sum_{n=1}^{n=N} T^n e_n$

یک تانسور (۲,۰) عضوی از فضای برداری $V \otimes V$ است که با پایه‌های $e_m \otimes e_n$ تولید می‌شود. بنابراین چنین تانسوری با

$T = \sum_{m,n=1}^{N} T^{mn} e_m \otimes e_n$

داده می‌شود و $T m n$ مؤلفه‌های آن نامیده می‌شوند.

+ نوشته شده در دوشنبه بیست و هشتم آذر ۱۳۹۰ ساعت 2:27 توسط حسن نوری اصفهانی |

فرض پیوستار

فرضیه پیوستار

فرض پیوستار در ریاضیات فرضی است درباره اندازه مجموعه‌های بینهایت. این فرض می‌گوید:

هیچ مجموعه‌ای وجود ندارد که اندازه‌اش بین اندازه مجموعه اعداد طبیعی و اندازه مجموعه اعداد حقیقی باشد.

یا به عبارتی هیچ عدد اصلی مانند $x$ در نامساوی $\aleph_0 < x < c=2^{\aleph_0}$ صدق نمی‌کند.

به همین ترتیب تعمیم فرض پیوستار می‌گوید:

به ازای هر عدد اصلی نامتناهی

a

، عدد اصلی چون

x

که در نا مساوی

a < x < 2 a

صدق کند وجود ندارد.

اولین مسئله هیلبرت

در سال ۱۹۰۰ در انجمن بین‌المللی ریاضی‌دانان در پاریس دیوید هیلبرت ۲۳ مسئله ریاضی ارئه کرد که اولین آنها قضیه تعمیم فرض پیوستار بود و تا سال ۱۹۳۸ هیچگونه پیشرفتی در حل این مسئله وجود نداشت که در این سال کورت گودل اثبات کرد که تعمیم فرض پیوستار در اصول جاری نظریه مجموعه‌ها قابل رد نیست. ولی در سال ۱۹۶۲ پل کوهن اثبات کرد که این مسئله با اصول نظریه مجموعه‌ها (ZFC) قابل اثبات نیست.

نتایج گودل و کوهن عموماً به عنوان یک تناقض برداشت نمی‌شود و مانند اصل توازی اقلیدسی در هندسه تایید یا تکذیب آن به ما یک تئوری سازگار در ریاضیات می‌دهد.

+ نوشته شده در دوشنبه بیست و هشتم آذر ۱۳۹۰ ساعت 1:54 توسط حسن نوری اصفهانی |

اثباتهایی از قضیه فیثاغورث

این اثبات بر اساس نسبت تناسب میان دو مثلث متشابه بیان شده‌است. به این معنی که اگر دو مثلث متشابه داشته باشیم، نسبت طول‌های هر دو ضلع متشابه میان دو مثلث ثابت است.

همان گونه که در شکل نشان داده شده‌است، فرض کنید ABC مثلثی راست‌گوشه‌است و C زاویه‌ای راست (۹۰ درجه) است. حال ارتفاع مثلث را از گوشهٔ C بر وتر AB رسم می‌کنیم و نقطهٔ برخورد را H می‌نامیم. نقطهٔ H وتر را به دو بخش d و e تقسیم می‌کند.

مثلث جدید ACH و مثلث ABC با یکدیگر متشابه‌اند. چون هر دو یک زاویهٔ ۹۰ درجه دارند (طبق تعریف ارتفاع مثلث) و زاویهٔ A در هر دو مشترک است؛ از این می‌توان نتیجه گرفت که زاویهٔ سوم θ در هر دو یکسان است (در شکل نشان داده شده‌است). به دلیل مشابه مثلث CBH نیز با مثلث ABC متشابه‌است. به دلیل تشابه مثلث‌ها، روابط زیر برقرار خواهد بود:

عبارت سمت چپ، برابر است با کسینوس زاویهٔ θ و سمت راست برابر است با سینوس زاویهٔ θ.

این نسبت‌ها را به صورت زیر نیز می‌توان نوشت: و

و اگر دو تساوی را با یکدیگر جمع کنیم، خواهیم داشت:

که همان تساوی قضیهٔ فیثاغورس خواهد بود.

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

اثبات خود جناب اقلیدوس :

اثبات نوشته شده در کتاب اصول هندسهٔ اقلیدوس :

خلاصهٔ اثباتی که در کتاب اصول هندسهٔ اقلیدوس نوشته شده چنین است: مربع بزرگ را به دو مستطیل سمت چپ و سمت راست تقسیم می‌کنیم. یک مثلث ساخته شده‌است که مساحتش نصف مساحت مستطیل سمت چپ است. سپس یک مثلث دیگر ساخته می‌شود که مساحتش نصف مساحت مربع سمت چپ است. می‌توان نشان داد که این دو مثلث با یکدیگر مساوی‌اند درنتیجه مساحت مربع با مساحت مستطیل سمت چپ برابر است. به دلیل مشابه، مطلب گفته شده برای مستطیل سمت راست و مربع دیگر نیز برقرار است. اگر دو مستطیل را کنار هم قرار دهیم تا یک مربع روی وتر مثلث تشکیل دهند، می‌بینیم که مساحت مربع بزگ (مربعی که روی وتر تشکیل شد) با مجموع مساحت‌های دو مربع دیگر برابر است. جزئیات این مطلب در ادامه گفته شده‌است.

فرض کنید A و B و C سه گوشهٔ یک مثلث راست‌گوشه‌اند که زاویهٔ A در آن ۹۰ درجه‌است. خطی را عمود از گوشهٔ A بر روی وتر BC رسم می‌کنیم و آن را امتداد می‌دهیم تا ضلع پایین مربع کشیده شده روی وتر را قطع کند. این خط مربع روی وتر را به دو مستطیل تقسیم می‌کند که هریک از این مستطیل‌ها مساحتی برابر با مساحت مربع‌های رسم شده بر روی دو ضلع زاویهٔ A دارند.

برای ادامهٔ اثبات نیاز به دانستن چند نکته‌است:

اگر دو ضلع از یک مثلث با دو ضلع از مثلث دیگر یک به یک برابر باشد و زاویهٔ میان آن دو ضلع نیز با هم برابر باشد، می‌توان نتیجه گرفت که دو مثلث با یکدیگر برابرند.

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

مساحت یک مستطیل برابر است با حاصل ضرب دو ضلع مجاورش.

مساحت یک مربع برابر است با حاصل ضرب دو ضلع از آن.

هر یک از دو مربع بالایی با یکی از آن دو مثلثِ هم نهشت مرتبط است و هر یک از این مثلث‌ها نیز به نوبهٔ خود با یکی از مستطیل‌های سازندهٔ مربع پایینی ارتباط دارد.

شکل جدید مسئله برای بهتر روشن شدن مطلب به همراه خط‌های جدید.

ادامهٔ اثبات:

فرض کنید مثلث ABC یک مثلث راست‌گوشه‌است که زاویهٔ CAB در آن ۹۰ درجه‌است.

بر روی هریک از اضلاع BC و AB و CA به ترتیب مربع‌های CBDE و BAGF و ACIH رسم شده‌است.

از گوشهٔ A خطی به موازات BD و CE رسم می‌کنیم؛ این خط به صورت عمودی با BC و DE بر خورد می‌کند، محل‌های برخورد را به ترتیب K و L می‌نامیم.

دو گوشهٔ C را به F و A را به D وصل می‌کنیم تا مثلث‌های BCF و BDA تشکیل شود.

زاویه‌های CAB و BAG هر دو زاویه‌های راست‌اند. بنابراین نقاط C و A و G بر روی یک امتداد قرار دارند (هم‌خط‌اند)؛ برای نقاط B و A و H نیز همین مطلب برقرار است.

در این شکل، دو مثلث مساوی که مساحتی برابر با نصف مساحت مستطیل BDLK و مربع BAGF دارند، نمایش داده شده‌است.

زاویه‌های CBD و FBA نیز هر دو زاویه‌های راست‌اند. درنتیجه دو زاویهٔ ABD و FBC با یکدیگر برابرند چون هردو برابرند با حاصل جمع یک زاویهٔ ۹۰ درجه با زاویهٔ ABC.

چون AB با FB و BD با BC برابر است؛ درنتیجه مثلث ABD ناگزیر با مثلث FBC برابر خواهد بود.

چون A-K-L یک خط مستقیم است و با BD نیز موازی است؛ پس BDLK یک چهارضلعی با اضلاع دو به دو موازی است و مساحتی دو برابر مساحت مثلث ABD دارد؛ چون قاعدهٔ BD در هر دو مشترک است و ارتفاع نیز در هر دو طولی برابر با BK دارد.

چون نقطهٔ C و دو نقطهٔ A و G هر سه بر یک راستا قرار دارند، پس مربع BAGF باید مساحتی دو برابر مساحت مثلث FBC داشته باشد.

می توان نتیجه گرفت که مساحت مستطیل BDLK، و مربع BAGF با هم برابر است و اندازهٔ آن برابر با AB2 است.

به طور مشابه می‌توان نشان داد که مستطیل CKLE مساحتی برابر با مساحت مربع ACIH و برابر با AC2 دارد.

با جمع این دو نتیجه با یکدیگر خواهیم داشت: AB² + AC² = BD × BK + KL × KC

چون BD = KL و BD* BK + KL × KC = BD(BK + KC) = BD × BC

چون CBDE یک مربع است پس می‌توان نتیجه گرفت که AB²+AC²=BC²

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

اثبات بوسیله بازچینی (جالب) :

در شکل متحرک بالا، مساحت کل و مساحت مثلث‌ها همگی ثابت است. بنابراین، مساحت کل ناحیهٔ سیاه رنگ، ثابت است. اما ناحیهٔ اصلی سیاه رنگ با ضلع c را می‌توان به دو مربع با ضلع‌های a و b تقسیم کرد و نشان داد که: a² + b² = c².

اثبات دوم با استفاده از شکل متحرک بالایی است. مربع بزرگ اول، مساحتی برابر با c2 دارد با کنار هم قرار دادن چهار مثلث راست‌گوشهٔ یکسان و به دلیل اختلاف طول ضلع مثلث‌ها، یک مربع کوچک میان آن‌ها و در مرکز مربع بزرگ باقی می‌ماند. اگر یک بار دیگر نگاه کنیم می‌بینیم که با جابجایی مثلث‌ها، دو مستطیل با ضلع‌های a و b تشکیل شده‌است. با ادغام مربع کوچک میانی با یکی از مستطیل‌ها، دو مستطیل به دو مربع تبدیل خواهد شد و مساحت هریک از آن‌ها برابر با a² و b² خواهد بود. بنابراین : b²+a² =c ²است.

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

اثبات با استفاده از بازچینی چهار مثلث راست‌گوشهٔ(قایم الزاویه) یکسان :

شکلهای مربوط به دو اثبات جبری:

قضیهٔ فیثاغورس را می‌توان با استفاده از چیدن چهار مثلث راست‌گوشهٔ یکسان با ضلع‌های a و b و c درون یک مربع با ضلع c به صورت جبری اثبات کرد. مثلث‌ها یکسانند و مساحتی برابر دارند. مربع کوچک ضلعی برابر با b − a و مساحتی برابر با ²(b − a) به این ترتیب مساحت مربع بزرگ برابر خواهد بود با:

و چون این مربع ضلعی برابر با c دارد پس مساحتی برابر با²c خواهد داشت، می‌توان نتیجه گرفت:

همان گونه که در پایین شکل می‌توان دید، اثبات مشابه دیگری وجود دارد که در آن با استفاده از بازچینی چهار مربع یکسان به دور مربعی به ضلع c به نتیجه می‌رسد. با این کار مربع بزرگتری به ضلع (a+b) و در نتیجه با مساحت ²(a+b) تشکیل می‌شود. چهار مثلث و مربع با ضلع c مساحتی برابر با مساحت مربع بزرگتر دارد.

با جابجایی عبارت پشت تساوی خواهیم داشت:

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

شکل مربوط به اثبات گارفیلد:

مربع داخلی نیز دو نیم شده‌است، ادامهٔ اثبات به همان روش مشابه‌است با این تفاوت که عامل را اضافه‌تر دارد. که با دو برابر کردن کل عبارت به آسانی حذف می‌شود.

اثبات به روش دیفرانسیلی (بسیار جالب):

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

همان‌گونه که در شکل نشان داده شده‌است، می‌توان از دو مثلث راست‌گوشهٔ ADP و AQP استفاده کرد تا حدهای بالایی و پایینی نسبت دیفرانسیل Δc/Δa را معلوم کرد. بنابراین حد را می‌توان از Δa, Δc → 0 نتیجه گرفت. از نتیجهٔ مشتق dc /da می‌توان برای اثبات قضیه فیثاغورس استفاده کرد.

از مثلث ABC:

حال مثلث ADP را رسم می‌کنیم، سپس:

شکلی که برای بدست آوردن حدهای بالایی و پایینی کشیده شده‌است :

همان گونه که در قسمت بالای شکل نشان داده شده‌است، آخرین نامساوی که می‌توان از AD > Δc نتیجه گرفت، با ترکیب cos θ در عبارت بدست می‌آید:

پس از آن مثلث راست‌گوشهٔ AQP را تشکیل می‌دهیم (قسمت پایین شکل) چون هر دو مثلث AQP و PBC یک زاویهٔ دارند، پس:

همان‌گونه که در شکل پایینی نمایش داده شده‌است، آخرین نامساوی که می‌توان از PQ < Δc نتیجه گرفت، با ترکیب دو نامساوی که از مثلث‌های ADP و AQP بدست آمد، ایجاد می‌شود:

حال حدهای بالایی و پایینی نسبت Δc /Δa را در اختیار داریم. وقتی که Δc و Δa به سمت صفر میل کنند، نسبت Δc /Δa به مشتق dc /da تبدیل می‌شود و حد بالایی و حد پایینی یکی می‌شود و خواهیم داشت:

یا

که انتگرالی برابر با مقدار زیر خواهد داشت:

^{مقدار ثابت}

آنگاه که a = 0 و c = b باشد، مقدار ثابت جواب انتگرال برابر با b² خواهد بود. بنابراین استدلال قضیهٔ فیثاغورس اثبات شد.

+ نوشته شده در دوشنبه بیست و یکم آذر ۱۳۹۰ ساعت 2:48 توسط حسن نوری اصفهانی |

سری هندسی

ویژگی‌ها

در سری هندسی اگر $r\; < 1$ باشد این سری همگرا خواهد بود. در غیر این صورت این سری واگرا است.

مجموع

مجموع یک سری هندسی همگرا ( $r < 1$ ) از رابطه زیر به دست می‌آید:

$S_{n} \;=\; \frac{a}{1-r}.$

اثبات:

موقعی که $|r| \;=\ 1$ سری تبدیل می‌شود به:

a + a + a + a + ....

مجموع این سری می‌شود:

S n = (n + 1) a

$\lim_{n\to \infty} S_{n} = \lim_{n\to \infty} (n+1)a = \pm \infty$

(علامت بستگی به منفی یا مثبت بودن $a$ دارد).

این واگرائی سری را نشان می‌دهد.

اکنون اگر $r \;=\ -1$ سری تبدیل می‌شود به:

a - a + a - a + ....

بنابراین دنباله مجموع آن به شکل زیر در می‌آید:

a,0, a,0, a,...

که واگرا می‌باشد.

حالا ملاحظه کنید موقعی که قدر نسبت سری $|r| \;\neq\ 1$ .

مجموع این سری می‌شود:

(١) $S n = a + a r + a r 2 + ... + a r n$

هر دو طرف معادله را با $r$ ضرب می کنیم:

(٢) $r S n = a r + a r 2 + ... + a r n + a r n + 1$

(٢) را از (١) کم می کنیم:

(٣) $S n - r S n = a - a r n + 1$

یا:

$(1-r)S_{n} \;=\; a-ar^{n+1}$

از آنجائی که در وضعیت مورد نظر $|r| \;\neq\ 1$ ، ما می‌توانیم آن را به شکل زیر بنویسیم:

$S_{n} \;=\; \frac{a-ar^{n+1}}{1-r}= \frac{a}{1-r}(1-r^{n+1})$

اگر $r < 1$ پس $lim_{n \to \infty} r^{n+1} =0$ و نتیجه می گیریم که سری همگرا است.

$\lim_{n\to \infty} S_{n} \;=\; \frac{a}{1-r}.$

مثال

یک سری با قدر نسبت $r = \frac{1}{2}$ را در نظر بگیرید:

$\frac{1}{2} \,+\, \frac{1}{4} \,+\, \frac{1}{8} \,+\, \frac{1}{16} \,+\, \cdots$

از آنجا که قدر نسبت کوچکتر از یک است این سری همگرا است. همگرایی این سری نیز به سمت 1 است.

+ نوشته شده در یکشنبه بیستم آذر ۱۳۹۰ ساعت 20:39 توسط حسن نوری اصفهانی |

احتمالات

نظریهٔ احتمال

برای ادامهٔ بحث، لازم است که ابتدا چند واژه را تعریف کنیم:

آزمایش تصادفی: یک آزمایش که نتیجهٔ آن به هیچ‌وجه قابل پیش‌بینی نباشد یا اصطلاحاً تصادفی باشد؛ مثل انداختن تاس یا سکه.
فضای نمونه: مجموعهٔ کل نتیجه‌هایی که ممکن است از یک آزمایش تصادفی حاصل شود؛ مثلاً در آزمایش انداختن تاس فضای نمونه به صورت ${1,2,3,4,5,6}$ است.
پیشامد: به هریک از زیرمجموعه‌های فضای نمونه یک پیشامد می‌گویند؛ مثلاً ${2,4,6}$ یک پیشامد در آزمایش انداختن تاس است.
فضای نمونهٔ هم‌شانس: در صورتی که همهٔ اعضای فضای نمونه شانس برابری برای ظاهر شدن داشته باشند یا به عبارت دیگر، شانس تمام اعضا یکسان باشد، این فضای نمونه را هم‌شانس می‌خوانیم. مثلاً آزمایش انداختن تاس سالمدر فضای هم‌شانس است.

احتمال در فضای متناهی

اگر فضای نمونهٔ ما هم‌شانس و دارای تعداد اعضای متناهی باشد، برای محاسبهٔ احتمال وقوع یک پیشامد، فرمول لاپلاس را به کار می‌گیریم.

$p={|E|\over |S|}$

یا به عبارت دیگر، احتمال وقوع یک پیشامد برابر است با نسبت اندازهٔ پیشامد به اندازهٔ فضای نمونه. برای مثال اگر آزمایش انداختن تاس سالم را در نظر بگیریم که دارای فضای نمونهٔ هم‌شانس با اندازهٔ متناهی است، با توجه به آن‌چه پیش‌تر گفته شد، احتمال آمدن عدد 6، برابر است با اندازه پیشامد (یعنی اندازهٔ ${6}$ که 1 است) بخش بر اندازهٔ فضای نمونه (یعنی اندازهٔ ${1,2,3,4,5,6}$ که 6 است). به این ترتیب احتمال آمدن عدد 6، برابر با $1\over 6$ محاسبه می‌شود.

احتمال پیشامدهای مرکب

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

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

$p(\bar{E})=1-p(E)$

با توجه به آن‌چه گفته شد اثبات این رابطه بسیار ساده است.

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

$p(E\cup F)=p(E)+p(F)-p(E\cap F)$

اثبات این رابطه با دانستن این‌که $|E\cup F|=|E|+|F|-|E\cap F|$ میسر است.

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

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

مقدار هر یک از این احتمال‌ها باید بین صفر و یک باشد؛ به عبارت دیگر برای هر $s\in S$ داشته باشیم:

$0\leq p(s)\leq 1$

مجموع مقدار احتمال‌های تخصیص‌داده‌شده، برابر 1 باشد؛ به عبارت دیگر داشته باشیم:

$\sum_{s\in S} p(s)=1$

به تابع احتمال p، تابع توزیع احتمال می‌گوییم.

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

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

احتمال شرطی و استقلال پیشامدها

فرض کنید خانواده‌ای دو فرزند دارد. می‌خواهیم بدانیم اگر فرزند اول پسر باشد، با چه احتمالی فرزند دوم دختر خواهد بود؟ برای حل چنین مسئله‌ای از رابطهٔ احتمال شرطیاستفاده می‌کنیم که به شکل زیر است:

$p(E|F)={p(E\cap F)\over p(F)}$

یا به عبارت دیگر احتمال وقوع E، اگر F اتفاق افتاده باشد، برابر است با نسبت احتمال اشتراک E و F به احتمال F.

حال اگر این دو پیشامد از هم مستقل باشند، روشن است که وقوع E ارتباطی با وقوع F نخواهد داشت یا به تعبیر دیگر $p (E | F)$ همان $p (E)$ خواهد بود.

به این ترتیب می‌توانیم دو پیشامد E و F را مستقل بدانیم، در صورتی که:

$p(E\cap F)=p(E)p(F)$

توزیع احتمال دوجمله‌ای

یک آزمایش تصادفی بسیار مشهور، موسوم به آزمایش برنولی ، به این شکل تعریف می‌شود:

آزمایشی تصادفی که در هر بار انجام آن تنها یا پیروزی اتفاق می‌افتد یا شکست.

با توجه به این آزمایش، در صورتی که n بار آزمایش برنولی انجام شود، و این آزمایش‌ها از هم مستقل باشند و احتمال پیروزی نیز p باشد، آن‌گاه تابع توزیع احتمال، مشهور به توزیع احتمال دوجمله‌ای خواهیم داشت که به صورت ${n\choose k}p^k(1-p)^{n-k}$ است (k تعداد پیروزی‌هاست).

علت این نام‌گذاری، شباهت فوق‌العادهٔ رابطهٔ به‌دست‌آمده با رابطهٔ بسط دوجمله‌ای نیوتن است.

توزیع احتمال هندسی

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

p (1 - p) k - 1

توجه کنید که تعریف این توزیع را می‌توانستیم به این ترتیب انجام دهیم که آن‌قدر آزمایش تکرار شود تا نتیجهٔ شکست به دست آید. اگر تعریف به این شکل باشد، کافی است جای p و 1-p را در رابطهٔ به‌دست‌آمده عوض کنیم.

متغیر تصادفی، امیدریاضی و واریانس

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

متغیر تصادفی

متغیر تصادفی ، تابعی است که از فضای نمونه بر اعداد حقیقی تعریف شده است؛ یعنی هر عضو از فضای نمونه را به یک عدد حقیقی مربوط می‌کند. متغیر تصادفی را معمولاً با X نشان می‌دهند. (اشتباه نکنید! متغیر تصادفی، نه متغیر است و نه تصادفی! این تنها یک نام‌گذاری است).

مثلاً فرض کنید که خانواده‌ای دو فرزند دارد. به این ترتیب فضای نمونهٔ حالت‌های ممکن برای این جنسیت دو فرزند به صورت {(پ، د)و(د، پ)و(د، د)و(پ، پ)} خواهد بود. حال فرض کنید متغیر تصادفی X قرار است تعداد فرزندان دختر را مشخص کند. به این ترتیب خواهیم داشت:

0=(پ، پ)X1=(پ، د)X1=(د، پ)X2=(د، د)X

همان‌طور که برای یک آزمایش تصادفی، توزیع احتمال تعریف کردیم، می‌توانیم برای متغیر تصادفی نیز تابع توزیع احتمال تعریف کنیم که با (p(X=r نموده می‌شود. مثلاً در مورد همان مثال بالا، تابع توزیع احتمال به این شکل درمی‌آید:

$p(X=0)={1\over4}$ $p(X=1)={1\over2}$ $p(X=2)={1\over4}$

حال می‌توانیم دومین تابع را معرفی کنیم.

امیدریاضی

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

$E(X)=\sum_{s\in S} p(s)X(s)$

برای نمونه، اگر همان مثال گفته شده در بخش قبل را در نظر بگیریم، امیدریاضی تعداد دختران یک خانواده با دو فرزند به صورت زیر خواهد بود:

$0\times{1\over4}+1\times{1\over2}+2\times{1\over4}=1$

یکی از مهم‌ترین ویژگی‌های تابع امیدریاضی، خطی بودن آن است؛ یعنی اگر n متغیر تصادفی به صورت $X_1,\cdots,X_n$ داشته باشیم، تساوی زیر برقرار خواهند بود:

$E(X_1+\cdots+X_n)=E(X_1)+\cdots+E(X_n)$

E (a X 1 + b) = a E (X 1) + b

برای ادامهٔ بحث، بد نیست تعریف زیر را انجام دهیم:

دو متغیر تصادفی X و Y را مستقل می‌خوانیم در صورتی که برای هر $a,b\in \mathbb{R}$ داشته باشیم احتمال X=a و Y=b برابر است با حاصل‌ضرب احتمال X=a در احتمال Y=b.

با توجه به این تعریف، می‌توان ثابت کرد که حکم مهم زیر برقرار است:

اگر X و Y دو متغیر تصادفی مستقل باشند، آن‌گاه خواهیم داشت (E(XY)=E(X)E(Y.

اگر به یاد داشته باشید در مبحث قبل، توزیع احتمال دوجمله‌ای و هندسی را تعریف کردیم. محاسبات نشان می‌دهند که امیدریاضی توزیع احتمال دوجمله‌ای برابر $n p$ و امیدریاضی توزیع احتمال هندسی برابر $1\over p$ خواهد بود.

حال به معرفی آخرین تابع می‌پردازیم که در محاسبات آماری جایگاه ویژه‌ای دارد.

واریانس

واریانس در محاسبات آماری، یک معیار برای سنجش میزان پراکندگی داده‌ها از میانگین است. ما در این مباحث، امیدریاضی را مشابه میانگین در نظر گرفتیم و به این ترتیب واریانس را چنین تعریف می‌کنیم:

اگر X متغیر تصادفی روی فضای نمونهٔ S باشد، واریانس X برابر خواهد بود با:

$V(X)=\sum_{s\in S} (X(s)-E(X))^2p(s)$

حکم بسیار مهمی که در محاسبات بسیار راه‌گشاست و از تعریف نتیجه می‌شود به قرار زیر است:

اگر متغیر تصادفی X روی فضای نمونهٔ S تعریف شده باشد، واریانس از رابطهٔ زیر نیز به دست می‌آید:

V (X) = E (X 2) - E (X) 2

در این‌جا مقصود از $X 2$ این است که مقدارهای متغیر تصادفی را به توان 2 برسانیم.

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

${1\over4}(0-1)^2+{1\over2}(1-1)^2+{1\over4}(2-1)^2={1\over2}$

واریانس مجموع چند متغیر تصادفی مستقل را می‌توان برحسب واریانس تک‌تک این متغیرها حساب کرد:

$V(X_1+\cdots+X_n)=Var(X_1)+\cdots+Var(X_n)$

تأکید می‌کنیم که این حکم فقط در صورتی قابل استفاده است که متغیرها مستقل باشند.

+ نوشته شده در چهارشنبه دوم آذر ۱۳۹۰ ساعت 3:18 توسط حسن نوری اصفهانی |

نظریه بازیها

درسال ۱۹۲۱ یک ریاضی‌دان فرانسوی به نام امیل برل (Emile Borel) برای نخستین بار به مطالعهٔ تعدادی از بازی‌های رایج در قمارخانه‌ها پرداخت و تعدادی مقاله در مورد آن‌ها نوشت. او در این مقاله‌ها بر قابل پیش‌بینی بودن نتایج این نوع بازی‌ها به طریق منطقی، تأکید کرده بود.

اگرچه برل نخستین کسی بود که به طور جدی به موضوع بازی‌ها پرداخت، به دلیل آن که تلاش پیگیری برای گسترش و توسعهٔ ایده‌های خود انجام نداد، بسیاری از مورخین ایجاد نظریهٔ بازی را نه به او، بلکه به جان ون نویمن (John Von Neumann) ریاضی‌دان مجارستانی نسبت داده‌اند.

آن چه نویمن را به توسعهٔ نظریهٔ بازی‌ها ترغیب کرد، توجه ویژهٔ او به یک بازی با ورق بود.او دریافته بود که نتیجهٔ این بازی صرفاً با تئوری احتمالات تعیین نمی‌شود. او شیوهٔ بلوف زدن در این بازی را فرمول‌بندی کرد. بلوف زدن در بازی به معنای راه‌کار فریب دادن سایر بازیکنان و پنهان کردن اطلاعات از آن‌هاست.

در سال ۱۹۲۸ او به همراه اسکار مورگنسترن(Oskar Mongenstern) که اقتصاددانی اتریشی بود، کتاب تئوری بازی‌ها و رفتار اقتصادی را به رشتهٔ تحریر در آوردند. اگر چه این کتاب صرفاً برای اقتصاددانان نوشته شده بود، کاربردهای آن در در روان‌شناسی، جامعه‌شناسی، سیاست، جنگ، بازی‌های تفریحی و بسیاری زمینه‌های دیگر به زودی آشکار شد.

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

از آن پس پیشرفت این دانش با سرعت بیشتری در زمینه‌های مختلف پی گرفته شد و از جمله در دههٔ ۱۹۷۰ به طور چشم‌گیری در زیست‌شناسی برای توضیح پدیده‌های زیستی به کار گرفته شد.

در سال ۱۹۹۴ جان نش(John Nash) به همراه دو نفر دیگر به خاطر مطالعات خلاقانه خود در زمینهٔ تئوری بازی‌ها برندهٔ جایزه نوبل اقتصاد شدند. در سال‌های بعد نیز برندگان جایزهٔ نوبل اقتصاد عموماً از میان نظریه‌پردازان بازی انتخاب شدند.

کاربردها

نظریه بازی‌ها در مطالعهٔ طیف گسترده‌ای از موضوعات کاربرد دارد.

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

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

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

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

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

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

هم چنین این نظریه نقش مهمی در مدل‌سازی الگوریتم‌های بر خط (Online Algorithms) دارد.

کاربردهای این نظریه تا آن جا پیش رفته است که در توصیف و تحلیل بسیاری از رفتارها در فلسفه و اخلاق ظاهر می‌شود.

انواع بازی

نظریه بازی‌ها علی الاصول می‌تواند روند و نتیجهٔ هر نوع بازی از دوز گرفته تا بازی در بازار بورس سهام را توصیف و پیش‌بینی کند.

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

متقارن - نامتقارن (Symmetric - Asymmetric)

بازی متقارن بازی‌ای است که نتیجه و سود حاصل از یک راه برد تنها به این وابسته‌ است که چه راه‌بردهای دیگری در بازی پیش گرفته شود؛ و از این که کدام بازیکن این راه‌برد را در پیش گرفته‌است مستقل است. به عبارت دیگر اگر مشخصات بازیکنان بدون تغییر در سود حاصل از به کارگیری راه‌بردها بتواند تغییر کند، این بازی متقارن است. بسیاری از بازی‌هایی که در یک جدول ۲*۲ قابل نمایش هستند، اصولاً متقارن‌اند.

بازی ترسوها و معمای زندانی (در ادامه توضیح داده خواهد شد.) نمونه‌هایی از بازی متقارن هستند.

بازی‌های نامتقارن اغلب بازی‌هایی هستند که مجموعهٔ راه‌بردهای یکسانی برای بازیکنان در بازی وجود ندارد. البته ممکن است راه‌بردهای یکسانی برای بازیکنان موجود باشد ولی آن بازی نامتقارن باشد.

مجموع صفر - مجموع غیر صفر(Zero Sum - Nonzero Sum)

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

اما در بازی‌های مجموع غیر صفر راهبردهایی موجود است که برای همهٔ بازیکنان سودمند است.

تصادفی - غیر تصادفی (Random - Nonrandom)

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

با آگاهی کامل – بدون آگاهی کامل (Perfect Knowledge – Non-Perfect Knowledge)

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

نمونه‌هایی از بازی‌ها

بازی ترسوها (Chicken Game)

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

بنابراین:

اگر یکی بترسد و منحرف شود دیگری می‌برد؛
اگر هر دو منحرف شوند هیچ‌کس نمی‌برد اما هر دو باقی می‌مانند؛
اگر هیچ‌کدام منحرف نشوند هر دو ماشین‌هایشان ( و یا حتی احتمالاً زندگیشان را!) می‌بازند؛

معمای زندانی(Prisoner’s delimma)

نوشتار اصلی: معمای زندانی‌ها

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

اگر دوستت را لو بدهی تو آزاد می‌شوی ولی او به پنج سال حبس محکوم خواهد شد.
اگر هر دو یکدیگر را لو بدهید، هر دو به سه سال حبس محکوم خواهید شد.
اگر هیچ‌کدام همدیگر را لو ندهید، هر دو یک‌سال در یک مرکز بازپروری خدمت خواهید کرد.
اگر شما یکی از این زندانی‌ها بودید چه می‌کردید؟

+ نوشته شده در چهارشنبه دوم آذر ۱۳۹۰ ساعت 3:13 توسط حسن نوری اصفهانی |

جوابیه اعتراض

در جواب دانشجوی نسبتا گرامی معترض همین قدر بگویم که نمرات با ارفاق زیاد بوده و بچه جان :

نابرده رنج گنج میسر نمیشود مزد آن گرفت جان برادر که کارکرد

+ نوشته شده در جمعه دهم دی ۱۳۸۹ ساعت 10:37 توسط حسن نوری اصفهانی |

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

روزی که شد به نیزه سر آن بزرگوار خورشید سر برهنه بر آمد ز کوهسار

موجی به جنبش آمد و بر خاست کوه کوه ابری ببارش آمد و بگریست زار زار

عرش آنزمان بلرزه در آمد که چرخ پیر افتاد در گمان که قیامت شد آشکار

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

وانگه ز کوفه خیل الم رو بشام کرد نوعیکه عقل گفت قیامت قیام کرد

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

این کشته فتاده به هامون حسین تست

وین صید دست و پا زده در خون حسین تست

یک بند از دوازده بند مشهور محتشم کاشانی

+ نوشته شده در جمعه چهارم دی ۱۳۸۸ ساعت 2:32 توسط حسن نوری اصفهانی |

مساله ژوزفوس

تاريخچه

اين مساله منتسب به فلاويوس ژوزفوس يك تاريخدان يهودي قرن اول ميلادي است. آنگونه كه داستان مي گويد، او و 40 سرباز همراه وي در يك غار زنداني شده اند كه توسط رومي ها محاصره شده است. آنها خودكشي را بر اسير شدن ترجيح مي دهند و تصميم مي گيرند كه يك دايره را تشكيل داده و سه تا سه تا خود را بكشند. چون ژوزفوس نمي خواهد كشته شود، و مي تواند مكان امن دور دايره را پيدا كند با يكي از همراهانش زنده مي ماند و به روميها كه آنها را دستگير مي كنند، مي پيوندد.(تنها جمله اي كه ژوزفوس بعدا گفت، اين بود كه با خوش شانسي يا به ياري لطف خدا او و فرد ديگري باقي ماندند و تسليم رومي ها شدند)

راه حل

ما مساله را درحالتي حل ميكنيم كه افراد دوتا دوتا كشته شوند:k=2.(براي حالت كلي تر يك راه حل نشان خواهيم داد). راه حل را به صورت روابط بازگشتي ارائه مي دهيم. فرض كنيد (f(n، مكان نجات يابنده باشد در صورتيكه n تعداد اوليه افراد باشد و (k=2). در اولين گردش دور دايره، تمام افراد با شماره زوج مي ميرند. در دومين چرخش، افراد جديد دوم كشته مي شوند و در دور بعدي افراد جديد چهارم و الي آخر .

اگر تعداد افراد اوليه زوج باشد، آنگاه فردي كه در دور دوم در مكان x‌ قرار گرفته است ابتدا در مكان 2x-1 بوده است. بنابراين فردي كه در مكان(f(n ‌قرار دارد، ابتدا در مكان 2f(n)-1 بوده است. اين ايده چنين رابطه بازگشتي را به ما ميدهد:

f(2n)=2f(n)-1

اگر تعداد افراد اوليه فرد باشد، آنگاه فرد شماره يك در اولين دور كشته خواهد شد. دوباره در دور دوم، افراد زوج جديد كشته خواهند شد. و در دور بعدي افراد چهارم جديد. اين ايده نيز به چينن رابطه اي بازگشتي اي منجر مي گردد: f(2n+1)=2f(n)+1

وقتي مقادير n و (f(n را جدول بندي كنيم چنين الگويي را مشاهده ميكنيم:

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

f(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

اين الگو نشان مي دهد كه (f(n يك دنباله فرد صعودي است كه از f(n)=1 شروع مي شود؛ وقتي كه انديس n تواني از 2 باشد. بنابراين اگر m و l را به گونه اي انتخاب كنيم كه $n = 2 m + l$ و $0\leq l<2^m$ باشد و آنگاه f(n)=2l+1. اين واضح است كه مقادير در جدول اين معادله را ارضا ميكنند. اما رياضيات نيازمند اثبات قطعي است. در زير ما اثباتي را از طريق استقرا ارائه ميكنيم.

قضيه: اگرn = 2m + l و $0\leq l<2^m$ ،آنگاه f(n)=2l+1

اثبات: ما از استقراي رياضي قوي روي n‌ استفاده مي كنيم. پايه n=1‌ است كه درست است.ما n هاي فرد و زوج را جداگانه بررسي مي نماييم. اگر n زوج باشد، آنگاه ما $l 1$ و $m 1$ را انتخاب ميكنيم به گونه اي كه $n/2 = 2^{m_1}+l_1$ و $0\leq l_1 < 2^{m_1}$ . توجه داشته باشيد كه $l_1=\frac{1}{2}$ .داريم

$f(n)=2f(\frac{n}{2})-1=2(2l_1+1)-1=2l+1$

كه تساوي دوم از فرض استقرا به دست مي آيد.

حال اگر n فرد باشد ما $m 1$ و $l 1$ را به گونه اي انتخاب مي كنيم كه $\frac{n-1}{2} = 2^{m_1}+l_1$ و $0\leq l_1 < 2^{m_1}$ . توجه داشته باشيد كه $l_1=\frac{l}{2}$ .داريم $f(n) = 2f(\frac {n-1}{2}) + 1 = 2((2l_1) + 1) + 1 = 2l + 1$ كه تساوي دوم از فرض استقرا به دست مي آيد. و اثبات كامل مي شود.

ظريف ترين شكل جواب نمايش دودويي n را دربرمي گيرد كه توسط آقای "آرمین شمس براق" دانشجوی دانشگاه مشهد به صورت زیر پیشنهاد شده و مورد توجه طراحانالگوریتم برجسته دنیا قرار گرفته است : اگر n را بصورت باینری بنویسیم و شماره فردی که زنده می ماند را برابر Jn بگیریم , و n را یک بیت شیفت دوران دهیم Jn به دست می‌آید.

+ نوشته شده در جمعه چهارم دی ۱۳۸۸ ساعت 1:10 توسط حسن نوری اصفهانی |

مطالب قدیمی‌تر

علاقه مندان به علوم پایه

مباحثی در ریاضیات و نجوم

سلام

تانسور

تانسور

فرض پیوستار

فرضیه پیوستار

اولین مسئله هیلبرت

اثباتهایی از قضیه فیثاغورث

سری هندسی

ویژگی‌ها

مجموع

مثال

احتمالات

نظریهٔ احتمال

احتمال در فضای متناهی

احتمال پیشامدهای مرکب

احتمال شرطی و استقلال پیشامدها

احتمال شرطی و استقلال پیشامدها

توزیع احتمال دوجمله‌ای

توزیع احتمال هندسی

متغیر تصادفی، امیدریاضی و واریانس

متغیر تصادفی

امیدریاضی

واریانس

نظریه بازیها

کاربردها

انواع بازی

متقارن - نامتقارن (Symmetric - Asymmetric)

مجموع صفر - مجموع غیر صفر(Zero Sum - Nonzero Sum)

تصادفی - غیر تصادفی (Random - Nonrandom)

با آگاهی کامل – بدون آگاهی کامل (Perfect Knowledge – Non-Perfect Knowledge)

نمونه‌هایی از بازی‌ها

بازی ترسوها (Chicken Game)

معمای زندانی(Prisoner’s delimma)

جوابیه اعتراض

مساله ژوزفوس

تاريخچه

راه حل

نوشته‌های پیشین