title: آبشاره‌سازی جزءبه‌جزء

text: می‌خواهیم به پرسش‌هایی از این دست، در گرافی پاسخ دهیم. در این گراف به ازای مقدار ثابت d حداکثر تعداد یال‌های ورودی از هر رأس d و حد اقل تعداد یال‌های ورودی به هر رأس نیز d است. لیست‌های مربوط به هر رأس را، بر اساس همسایه‌های منتهی به یال‌های خروجی رأس، گسترش می‌دهیم. این کسر باید طوری انتخاب شود که کوچکتر از ۱/d باشد. به طوری که مقدار مجموع لیست‌های گسترش یافته نسبت به سایز ورودی خطی باشد. هر مورد، در هر لیست گسترش یافته، محل قرار گرفتن آن مورد را در لیست‌های گسترش نایافته‌ای که در همان رأس و در رأس‌های همسایهٔ منتهی به یال‌های خروجی، ذخیره شده‌اند، ذخیره می‌کند. به عنوان یک مثال ساده از این توضیحات، d=۱، و ما هر لیست را با ½ از همسایه‌هایش گسترش داده‌ایم:


title: آبشاره‌سازی جزءبه‌جزء

text: یک پرسش در این داده ساختار، شامل یک جستجوی دودویی عادی در لیست گسترش یافتهٔ مربوط به رأس اول از مسیر مورد پرس و جو، و علاوه بر آن، تعدادی جستجوی ساده‌تر، در هر یک از رئوس بعدی مسیر است. اگرکسر ۱/r از همسایه‌های یک رأس در گسترش دادن لیست آن استفاده شود، در آن صورت نتیجهٔ هر پرسش بعدی حداکثر در r مرحله، از روی مکان‌هایی که در پرسش‌های قبلی، در رئوس قبلی مسیر ذخیره شده‌است، بدست خواهد آمد و حتی ممکن است در زمانی ثابت و کوتاه، بدون انجام یک جستجوی دودویی کامل یافته شود.


title: آبشاره‌سازی جزءبه‌جزء

text: در آبشاره‌سازی جزءبه‌جزء به صورت پویا، لیستی که در هر گره از گراف کاتالوگ ذخیره شده‌است، می‌تواند به صورت پویا تغییر کند. به عبارتی اجزای این لیست می‌توانند به روز شوند و یک عضو در آن درج شود یا از آن حذف گردد. ایجاد این تغییرات باعث به وجود آمدن مشکلاتی در ساختاربندی داده‌ها می‌شود.


title: آبشاره‌سازی جزءبه‌جزء

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


title: آبشاره‌سازی جزءبه‌جزء

text: همان‌طور که پیش‌تر گفته شد، هر گره از گراف کاتالوگ، تعدادی از اعضای لیست همسایهٔ خود را نیز نگه‌داری می‌کند. به عبارتی در لیست یک گره، اعضایی که در مکان d از لیست همسایه قرار دارند نیز وجود دارد. در برخی شرایط با توجه به مقدار d و همچنین اعضای یک لیست، این امکان وجود دارد که با هر به روز رسانی و تغییر در یک لیست، لیست‌های همسایه نیز تغییر کنند. برای حل این مشکل از روشی شبیه به روش ساخت داده ساختار B tree استفاده می‌شود. با استفاده از این روش، می‌توان اطمینان حاصل کرد که تعداد داده‌هایی که انتخاب می‌شوند، کمتر از کل داده‌های لیست تقسیم بر d است و همچنین این اعداد در مکان‌های ثابتی از لیست قرار دارند. این موضوع باعث می‌شود که انتقال تغییرات هنگام درج یا حذف برای یک لیست از یک گره، تعداد عملیاتی کمتر از یک تقسیم بر d نیاز داشته باشد. یعنی یک تغییر در یک گره، به طور میانگین حداکثر یک تقسیم بر d تغییر برای به روز رسانی سایر گره‌ها نیاز دارد. با این روش، توزیع داده‌ها در میان گره‌ها به گونه‌ای خواهد بود که میانگین تعداد عملیاتی که برای به روز رسانی درخت‌های جستجوی دودویی صورت می‌گیرد، عددی ثابت است.


title: آبشاره‌سازی جزءبه‌جزء

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


title: آبشاره‌سازی جزءبه‌جزء

text: این داده ساختارها باعث می‌شوند که آبشاره‌سازی پویا در مرتبهٔ زمانی (O(log n برای هر درج و حذف عمل کند. همچنین یک زنجیره از k عمل جستجوی دودویی که در یک مسیر به طول k در گراف کاتالوگ صورت می‌گیرد، در مرتبهٔ زمانی (O(log n + k log log n انجام پذیرد.


title: آبشاره‌سازی جزءبه‌جزء

text: یکی از کاربردهایی که آبشاره‌سازی جزءبه‌جزء دارد، در داده ساختارهای جستجوی محدوده که در هندسهٔ محاسباتی مورد استفاده قرار می‌گیرد، می‌باشد. به طور مثال، در مسئلهٔ half-plane range reporting باید تعداد n نقطهٔ ثابت را تقسیم‌بندی کرد. یکی از ساختارهایی که در این زمینه مورد استفاده قرار می‌گیرد، لایه‌های محدب می‌باشد. آبشاره‌سازی جزءبه‌جزء به این مسئله کمک می‌کند تا عملیات جستجو برای شیب‌های مربوط به هر لایه در حافظهٔ مرتبهٔ (O(n و زمان (O(log n + h صورت گیرد که در آن h اندازهٔ زیرمجموعه‌هایی از نقاط است که مورد سؤال قرار می‌گیرد. با استفاده از الگوریتم Chazelle داده ساختاری که از مرتبهٔ زمانی (O(n log n ساخته می‌شود، این مسئله حل می‌شود. با توجه به این مثال، کاربرد آبشاره‌سازی جزءبه‌جزء شامل تعدادی جستجوی دودویی در یک سری خطی از لیست‌ها (سری‌های تودرتو از لایه‌های محدب) می‌باشد؛ بنابراین گراف کاتالوگ در این حالت، فقط یک مسیر ساده خواهد بود.


title: آبشاره‌سازی جزءبه‌جزء

text: یکی دیگر از کاربردهای آبشاره‌سازی جزءبه‌جزء در داده ساختارهای هندسی در رابطه با مکان‌یابی نقاط در نواحی یکنواخت می‌باشد. ناحیهٔ یکنواخت، بخشی از صفحه شامل تعدادی چندضلعی است که هر خط هرکدام از چندضلعی‌ها را در حداکثر دو نقطه قطع کند. Edelsbrunne, Guibas و Stolfi در سال ۱۹۸۶ نشان دادند که برای حل این مسئله، کافیست دسته‌ای از مسیرهای به شکل چندضلعی را یافت که از چپ تا راست ناحیهٔ مورد نظر کشیده شده‌اند. سپس یک جستجوی دودویی بر روی این مسیرها باید زد تا مسیری را که در پایین‌ترین سطح قرار دارد و همچنین بالاتر از نقطهٔ مورد جستجو واقع شده‌است پیدا کرد. این موضوع که یک نقطه بالای یک مسیر قرار دارد یا پایین آن، با جستجوی دودویی قابل بررسی است. به عبارتی باید جستجویی بر روی مختصهٔ اول از هرکدام از نقاط مسیر داشت تا مقایسه کرد که نقطهٔ مورد بررسی زیر مسیر قرار دارد یا بالای آن؛ بنابراین برای جستجوهای دودویی که صورت می‌گیرد، می‌توان از آبشاره‌سازی جزءبه‌جزء استفاده کرد و سرعت را افزایش داد. با استفاده از این روش، مرتبهٔ زمانی انجام جستجو (O(log n خواهد بود و فضای (O(n از حافظه درگیر خواهد شد. در این حالت، گراف کاتالوگ یک گراف درخت خواهد بود که ترتیب‌های ممکن را برای جستجوی دودویی خارجی را می‌نمایاند.


title: آبشاره‌سازی جزءبه‌جزء

text: کاربرد آبشاره‌سازی جزءبه‌جزء تنها در محدودهٔ هندسهٔ محاسباتی نیست. Lakshamn و Stiliadis و همچنین Buddhikot, Suri و Waldvogel از این مدل برای طراحی داده ساختارهایی در حوزهٔ فیلتر کردن بسته‌های ارتباطی در مسیریاب‌های اینترنتی استفاده کرده‌اند. Gao et al نیز از آن به عنوان مدلی برای توزیع و بازیابی داده در حسگرهای شبکه‌ای استفاده کرده‌است.


آبشاره‌سازی جزءبه‌جزء


title: مسئله پوشش بیشینه

text: مسئله پوشش بیشینه (به انگلیسی: maximum coverage problem)، یک سؤال کلاسیک در علوم رایانه و نظریه پیچیدگی محاسباتی است. این مسئله به طور گسترده در الگوریتم‌های تقریبی آموزش داده می‌شود. برای ورودی تعدادی مجموعه و یک عدد formula_1 داده می‌شود. مجموعه‌ها می‌توانند عضو مشترک داشته باشند. شما باید به تعداد حداکثر formula_1 تا از این مجموعه‌ها را انتخاب کنید به طوری که حداکثر تعداد اعضا پوشش داده شود؛ برای مثال اجتماع مجموعه‌های انتخاب شده، بیشینه تعداد اعضا را دارد. به عبارت دیگر، پوشش بیشینه (بدون وزن) نمونه: عدد formula_1 و مجموعه‌ای از مجموعه‌ها formula_4. هدف: یافتن یک زیرمجموعهٔ formula_5 ، به طوری که formula_6 و تعداد اعضای پوشانده شده formula_7 حداکثر باشد. مسئله پوشش بیشینه یک ان‌پی سخت (به انگلیسی: NP-hard) و نمی‌تواند تحت مفروضات استاندارد با formula_8 تقریب زده شود. این نتیجه در اصل با نسبت تقریبی الگوریتم حریصانه عمومی که برای بیشینه‌سازی توابع زیرپیمان‌های با محدودیت کاردینالیتی (به انگلیسی: maximization of submodular functions with a cardinality constraint) به کار می‌رود، مطابقت دارد.


title: مسئله پوشش بیشینه

text: مسئله پوشش بیشینه می‌تواند به شکل زیر در قالب برنامه‌ریزی خطی عدد صحیح (به انگلیسی: Integer Linear Program) فرمول‌بندی شود.


title: مسئله پوشش بیشینه

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


title: مسئله پوشش بیشینه

text: نتایج غیرتقریبی به همهٔ تعمیم‌های مسئله پوشش بیشینه اعمال می‌شود زیرا آنها مسئله پوشش بیشینه را به عنوان یک حالت خاص دارند.


title: مسئله پوشش بیشینه

text: در مدل وزن دار هر عضو formula_21 وزنی برابر formula_22 دارد. هدف یافتن یک پوشش بیشینه است به طوری که بیشترین وزن را داشته باشد. حالت پایه، حالت خاصی است که همه وزن‌ها برابر formula_23 است. الگوریتم حریصانه برای پوشش بیشینه وزندار در هر مرحله مجموعه‌ای را انتخاب می‌کند که دارای بیشترین وزن اعضای پوشش داده نشده باشد. این الگوریتم به نسبت تقریب formula_20 می‌رسد.


title: مسئله پوشش بیشینه

text: در حالت پوشش بیشینه بودجه‌ای (به انگلیسی: Budgeted maximum coverage)، نه تنها هر عضو formula_21 وزنی برابر formula_22 دارد، بلکه هر مجموعه formula_19 قیمتی برابر formula_40 دارد. به جای formula_1 که تعداد مجموعه‌ها در پوشش را محدود می‌کند، بودجهٔ formula_42 داده می‌شود. بودجهی formula_42 وزن پوششی که می‌تواند انتخاب شود را محدود می‌کند. الگوریتم حریصانه دیگر راه حل‌هایی با تضمین کارایی ارائه نخواهد کرد. یعنی ممکن است رفتار این الگوریتم در بدترین حالت با راه حل بهینه بسیار متفاوت باشد. الگوریتم تقریب به روش زیر بدست می‌آید. ابتدا، پس از یافتن راه حلی که از الگوریتم حریصانه استفاده می‌کند، راه حل بهتر الگوریتم حریصانه و مجموعه با بیشترین وزن را بازمی‌گردانیم. این روش را، الگوریتم حریصانه اصلاح شده می‌نامیم. در مرحله دوم، با شروع از همهٔ خانواده‌های ممکن مجموعه‌های اندازه‌ها از یک تا (حداقل) سه، این راه حل‌ها را با الگوریتم حریصانه اصلاح شده تقویت می‌کنیم. در مرحله سوم، بهترین راه حل تقویت شده را بازمی‌گردانیم. این الگوریتم به نسبت تقریب formula_55 می‌رسد. این بهترین نسبت تقریب ممکن است مگر formula_56.


title: مسئله پوشش بیشینه

text: در تعمیم یافتهٔ پوشش بیشینه هر مجموعهٔ formula_19 قیمت formula_40 دارد، عضو formula_21 دارای وزنی متفاوت و هزینه‌ای بسته به مجموعه‌ای که آن را پوشش می‌دهد، دارد. یعنی اگر formula_21 توسط مجموعهٔ formula_19 پوشش داده شده باشد، وزن formula_21 برابر formula_63 و هزینهٔ آن برابر formula_64 خواهد بود. بودجه formula_65 برای هزینهٔ کل راه حل داده شده است.


title: مسئله پوشش بیشینه

text: این الگوریتم از مفهوم باقیماندهٔ وزن/هزینه استفاده می‌کند. باقیماندهٔ وزن/هزینه در مقابل یک راه حل آزمایشی اندازه‌گیری می‌شود و این تفاوت بین وزن/هزینه و وزن/هزینه بدست آمده با یک راه حل آزمایشی است. این الگوریتم چندین مرحله دارد. اول، یافتن راه حلی که از الگوریتم حریصانه استفاده می‌کند. در هر تکرار الگوریتم حریصانه، راه حل آزمایشی مجموعه‌ای را که شامل بیشترین مقدار وزن اعضای باقیمانده تقسیم بر هزینهٔ این اعضا همراه با هزینه اعضای باقیمانده دارد، اضافه می‌کند. دوم، مقایسهٔ راه حل بدست آمده در قدم اول با راه حل بهینه که از تعداد کمی از مجموعه‌ها استفاده می‌کند. سوم، بازگرداندن بهترین راه حل از بین راه حل‌های بررسی شده. این الگوریتم به نسبت تقریب formula_81 می‌رسد.


title: الگوریتم فورچون

text: الگوریتم فورچون یک الگوریتم خط جارویی برای ساختن نمودار ورونی از یک دسته نقطه در صفحه با استفاده از زمان formula_1 و حافظۀ formula_2 است. این الگوریتم اولین بار توسط استیون فورچون در سال ۱۹۸۶ در مقالۀ "یک الگوریتم خط جارویی برای نمودارهای ورونی" چاپ شد.


title: الگوریتم فورچون

text: این الگوریتم هم از خط جارویی و هم از "خط ساحلی" استفاده می‌کند که هردوی این خطوط در حین پیشرفت الگوریتم روی صفحه حرکت می‌کنند. خط جارویی خط مستقیمی است که ما به صورت توافقی می‌توانیم فرض کنیم که یک خط عمودی است و از چپ به راست صفحه حرکت می‌کند. در هر لحظه در طی الگوریتم نقاط ورودی سمت چپ خط جارویی با نمودار ورونی یکپارچه خواهند شد درحالی که نقاط سمت راست خط هنوز در نظر گرفته نشده‌اند. خط ساحلی یک خط نیست، بلکه یک منحنی مرکب در سمت چپ خط جارویی است که از تکه‌های سهمیها تشکیل شده است؛ این خط صفحه را به گونه‌ای تقسیم می‌کند که در آن نمودار ورونی، بدون توجه به وجود نقاط ممکن در سمت راست خط جارویی، از بقیۀ صفحه قابل تشخیص است. برای هر نقطه در سمت چپ خط جارویی، میتوان یک سهمی از نقاط هم‌فاصله از آن نقطه و خط جارویی تعریف کرد. خط ساحلی مرز مجموعۀ این سهمی‌ها است. هر چه خط جارویی پیشروی می‌کند رئوس خط ساحلی، که محل تلاقی دو سهمی است، یال‌های نمودار ورونی را رسم می‌کنند. خط ساحلی طوری پیشرفت می‌کند که رأس هر سهمی دقیقأ در وسط نقاط اولیۀ خط جارویی و جایگاه جدید خط جارویی قرار بگیرد.


title: الگوریتم فورچون

text: این الگوریتم از داده ساختارها استفاده می‌کند: یک درخت جستجوی دودویی که ساختار ترکیبی خط ساحلی را توصیف می‌کند و یک صف اولویت‌دار که رخدادهای بالقوۀ بعدی را که می‌توانند ساختار خط ساحلی را تغییر دهند لیست می‌کند. این رخدادها شامل اضافه کردن یک سهمی دیگر به خط ساحلی هستند (وقتی که خط جارویی از نقطۀ ورودی دیگری عبور می‌کند) و برداشتن منحنی از خط ساحلی (وقتی که خط جارویی با یک دایرۀ عبورکننده از سه نقطه، که سهمی‌هایشان بخش‌های متوالی خط ساحلی را تشکیل می‌دهند، مماس می‌شود). هر رخداد می‌تواند توسط محور xهای خط جارویی در محل وقوع رخداد، اولویت‌بندی شود. الگوریتم از برداشتن مکرر رخداد بعدی از صف اولویت‌دار، یافتن تغییراتی که آن رخداد در خط ساحلی ایجاد می‌کند و بهنگام‌سازی داده ساختارها، تشکیل می‌شود. از آنجا که formula_2 رخداد وجود دارند تا پردازش شوند (که هرکدام با برخی ویژگی‌های دیاگرام ورونی مرتبط هستند) و زمان formula_4 برای پردازش یک رخداد (که هرکدام شامل تعداد ثابتی از اعمال درخت جستجوی دودویی و صف اولویت‌دار هستند) زمان کلی الگوریتم formula_1 است.


title: الگوریتم فورچون

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


title: الگوریتم فورچون

text: زمانی که از نمودار ورونی برای ساخت treemapها استفاده می‌شود، می‌توان از بخش‌های وزن‌دار برای کنترل مکان‌های سلولی ورونی استفاده کرد. در یک دیاگرام ورونی وزن‌دار افزایشی، نیم‌ساز بین بخش‌ها به‌طور عمومی یک هذلولی است در حالی که در نمودارهای ورونی غیروزن‌دار و نمودار پاور دیسک‌ها نیم‌ساز یک خط مستقیم است.


title: درخت بازه

text: در علوم کامپیوتر، درخت بازه‌ای یک داده ساختار مرتب درختی برای نگهداری و ذخیره‌سازی بازه‌ها می‌باشد. می‌توان گفت این از درخت این امکان را فراهم می‌سازد تا همۀ بازه‌هایی را که با یک بازه یا نقطۀ خاص اشتراک دارند پیدا کنیم. درخت بازه‌ای به‌طور معمول برای پنجره دار کردن پرس و جوها به کار می‌رود. برای مثال، یافتن تمام راه‌های موجود بر روی یک نقشۀ کامپیوتری درون یک دید مستطیلی یا یافتن تمام نقاط قابل رویت درون یک چشم انداز سه بعدی. یک ساختار داده مشابه این داده ساختار، از درخت بخشی است.


title: درخت بازه

text: راه حل بدیهی این است که تمام بازه‌ها را ملاقات کرده و امتحان کنیم که آیا با نقطه یا بازه داده شده اشتراک دارند یا نه، که به theta(n) زمان نیاز دارد. (که n همان تعداد بازه‌های موجود در مجموعه است) از آنجایی که یک پرسش ممکن است تمام بازه‌ها را برگرداند، به‌طور مثال، اگر پرسش مورد نظر یک بازۀ بزرگ باشد که با همۀ بازه‌های موجود در مجموعه اشتراک داشته باشد، این به صورت مجانبی بهینه است؛ اگر که ما از الگوریتم‌های حساس به خروجی که در آن‌ها زمان اجرا بر اساس m (که همان تعداد بازه‌های تولید شده توسط پرس و جوست) بیان می‌شود استفاده کنیم می‌توانیم این فرایند را بهبود ببخشیم. درخت‌های بازه‌ای پویا هستند. آن‌ها اجازه درج و حذف بازه‌ها را می‌دهند. آن‌ها پرس و جو را در زمان O(logn) انجام می‌دهند. این در حالی است که زمان پیش پردازش برای ساخت این داده ساختار از O(nlogn) است (ولی فضای مصرف شده از O(n) است). اگر انتهای بازه‌ها در محدودۀ کوچکی قرار داشته باشند (مثلاً محدوده [1...,O(n)])، داده ساختارهای سریع‌تری با زمان پیش پردازش O(n) و زمان پرس و جوی O(1+m) وجود دارند که m بازه (شامل یک نقطه پرس و جو) را گزارش می‌کنند.


title: درخت بازه

text: در یک حالت ساده، بازه‌ها با هم هیچ گونه اشتراکی ندارند و می‌توانند در یک درخت جستجوی دودویی ساده درج شده و در زمان O(logn) پرس و جو شوند. این در حالی است که با وجود اشتراک‌های دلخواه میان بازه‌ها، به هیچ عنوان امکان مقایسه دو بازه برای درج در درخت وجود ندارد. زیرا مرتب سازی‌ها بر حسب نقاط شروع یا پایان ممکن است متفاوت باشد. یک عملکرد ساده این خواهد بود که دو درخت موازی بسازیم. یکی مرتب شده بر حسب نقاط شروع و دیگری مرتب شده بر حسب نقاط انتهای هر بازه. این کار اجازۀ رها کردن نصف درخت را در O(logn) می‌دهد ولی نتیجه‌ها باید ادغام شوند که به O(n) زمان نیاز دارد. این راه حل به ما پرس و جوهایی در زمان O(n) = O(n + logn) می‌دهد که بهتر از راه حل بدیهی نیست.


title: درخت بازه

text: پرس و جوها به زمان o(m + log(n)) نیاز دارند که در آن n تعداد کل بازه‌ها و m تعداد نتایج گزارش شده‌است. ساخت داده ساختار نیز به o(nlogn) زمان و O(n) فضا نیاز دارد.


title: درخت بازه

text: به ما یک مجموعه n تایی از بازه‌ها در خط اعداد داده می‌شود و ما می خواهیم یک داده ساختار بسازیم که بتواند به صورت مؤثری همه بازه‌هایی را که با یک نقطه یا بازه اشتراک دارند بازیابی کند.


title: درخت بازه

text: ما با مشخص کردن محدوده کل بازه‌ها و تقسیم کردن آن در x_center (در عمل، x_center باید مشخص شود تا درخت را نسبتاً متعادل نگه داریم) شروع می کنیم. این فرایند سه مجموعه از بازه‌ها را تولید می‌کند: 1. بازه‌هایی که کاملاً در سمت چپ x_center قرار می‌گیرند که ما آن‌ها را S_left نام‌گذاری می‌کنیم.


title: درخت بازه

text: 2. بازه‌هایی که کاملاً در سمت راست x_center قرار می‌گیرند که ما آن‌ها را S_right نام‌گذاری می‌کنیم.


title: درخت بازه

text: 3. آنهایی که با x_center اشتراک دارند که ما آن‌ها را S_center می‌نامیم.


title: درخت بازه

text: بازه‌های S_left و S_rightنیز به طریق مشابه به صورت بازگشتی تقسیم می‌شوند تا زمانی که هیچ بازه‌ای باقی نماند.


title: درخت بازه

text: بازه‌هایی از S_center که با نقطۀ مرکزی تلاقی دارند در یک داده ساختار جداگانه مرتب می‌شوند که به گره‌های درخت بازه‌ای پیوند داده شده‌است. این داده ساختار از دو لیست تشکیل شده‌است:


title: درخت بازه

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


title: درخت بازه

text: 1. یک نقطه مرکزی


title: درخت بازه

text: 2. یک اشاره‌گر به یک گره دیگر شامل همۀ بازه‌هایی که به‌طور کامل در سمت چپ نقطۀ مرکزی قرار می‌گیرند.


title: درخت بازه

text: 3. یک اشاره‌گر به یک گره دیگر شامل همۀ بازه‌هایی که به‌طور کامل در سمت راست نقطۀ مرکزی قرار می‌گیرند.


title: درخت بازه

text: 4. همۀ بازه‌های شامل نقطۀ مرکزی که بر اساس نقطۀ شروع‌شان مرتب شده‌اند.


title: درخت بازه

text: 5. همۀ بازه‌های شامل نقطۀ مرکزی که بر اساس نقطۀ پایان‌شان مرتب شده‌اند.


title: درخت بازه

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


title: درخت بازه

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


title: درخت بازه

text: یک جستجوی دودویی در زمان O(logn) برای شروع و پایان R، کمینه و بیشینۀ نقاطی را که باید در نظر گرفته شوند مشخص می‌کند. هر نقطه با این محدوده به تمام بازه‌هایی که با محدودۀ مورد نظر ما تلاقی دارند ارجاع می‌دهد و به لیست نتیجه اضافه می‌شود. باید توجه شود که از ایجاد تکرار جلوگیری شود، زیرا ممکن است هم شروع و هم پایان یک بازه با R باشد. این کار را می‌توان با استفاده از یک پرچم دودویی بر روی هر بازه برای مشخص کردن اینکه این بازه به مجموعۀ نتیجه اضافه شده‌است یا نه، انجام داد.


title: درخت بازه

text: تنها بازه‌هایی که هنوز در نظر گرفته نشده‌اند بازه‌هایی هستند که با R تلاقی دارند ولی نقاط پایان‌شان درون R نیست، به عبارت دیگر، بازه‌هایی که آن را در بر می‌گیرند. برای پیدا کردن آن‌ها ما هر نقطه در درون را در نظر می‌گیریم و از الگوریتم زیر استفاده می‌کنیم تا همۀ بازه‌هایی را که با آن نقطه اشتراک دارند بیابیم. (دوباره مواظب باشید که تکرارها را حذف کنید)


title: درخت بازه

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


title: درخت بازه

text: برای هر گره درخت، x با x_center مقایسه می‌شود، یعنی همان نقطۀ میانی که برای ساخت گره در بالا استفاده شده‌است. اگر x از x_center کوچک‌تر باشد، چپ‌ترین مجموعه از بازه‌ها S_left در نظر گرفته می‌شود. اگر x از x_center بزرگ‌تر باشد، راست‌ترین مجموعه از بازه‌ها S_right در نظر گرفته می‌شود.


title: درخت بازه

text: همین طور که هر گره پردازش می‌شود، وقتی ما درخت را از ریشه به یک برگ می‌پیماییم، محدوده‌های موجود در S_center آن پردازش می‌شوند. اگر x از x_center کوچک‌تر باشد، ما می‌دانیم که تمام بازه‌های موجود s_center بعد x تمام می‌شوند یا اینکه اصلاً با x_center برخورد ندارند. بنابراین ما تنها به یافتن بازه‌هایی از s_centerنیاز داریم که قبل از x شروع می‌شود. ما توانیم در مورد لیست‌های s_center که تاکنون ساخته شده‌اند بحث کنیم. از آنجایی که ما در این سناریو تنها به شروع بازه‌ها اهمیت می‌دهیم، می‌توانیم در مورد لیست مرتب شده بر اساس شروع بازه‌ها بحث کنیم. فرض کنید ما در لیست نزدیک‌ترین عددی که بزرگ‌تر از x نیست را بیابیم. تمام محدوده‌ها از شروع لیست تا آن نقطه یافته شده با x تلاقی دارند، چون قبل از x شروع شده و بعد از x تمام می‌شوند. (همان طور که می‌دانیم به علت این است که با x_center که بزرگ‌تر از x است تلاقی دارند) بنابراین می‌توانیم شروع به شماره‌گذاری بازه‌های موجود در لیست کنیم تا زمانی که مقدار نقطه پایانی از x بیشتر شود.


title: درخت بازه

text: همچنین اگر x از x_center بزرگ‌تر باشد، ما می‌دانیم که همۀ بازه‌های موجود در s_center باید قبل از x شروع شوند پس ما بازه‌هایی را که بعد از x پایان می‌یابند به وسیلۀ لیستی که بر اساس پایان بازه‌ها مرتب شده‌است می‌یابیم. اگر x دقیقاً منطبق بر x_center باشد، تمام فواصل را می‌توان بدون پردازش بیشتر به نتایج اضافه کرد و پیمایش درخت می‌تواند متوقف شود.


title: درخت بازه

text: ساختمان داده درخت را می‌توان با پرس و جو و زمان ساخت یکسان و فضای O(nlogn) به ابعاد بالاتر n تعمیم داد.


title: درخت بازه

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


title: درخت بازه

text: هر درخت بازه‌ای به یک چیز اضافه در ابعاد بالاتر نیز نیاز دارد. در هر گره که ما آن را در درخت پیمایش می‌کنیم برای پیدا کردن تلاقی‌ها x با s_center مقایسه می‌شود. به جای دو لیست مرتب شده از بازه‌ها که در حالت یک بعدی مورد استفاده قرار می‌گرفت یک درخت محدوده ساخته می‌شود. این امکان بازیابی کارآمد تمام بازه‌های موجود در s_center را (که با ناحیه R تلاقی دارند) فراهم می‌سازد.


title: درخت بازه

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


title: درخت بازه

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


title: درخت بازه

text: هم درج و هم حذف از O(logn) زمان می‌برند، که n همان تعداد کل بازه‌هاست.


title: درخت بازه

text: از یک درخت ساده مرتب استفاده کنید. برای مثال یک درخت جستجوی دودویی یا یک درخت خود-متعادل جستجوی دودویی، که درخت بر اساس نقاط پایین بازه‌ها مرتب شده‌است و یک توضیح اضافه به هر گره اضافه شده‌است که ماکزیمم نقاط بالای بازه‌ها را در زیر درخت‌های آن نگه می‌دارد. به دست آوردن این صفت در طی تنها O(h) مرحله هنگام حذف یا درج یک گره کار ساده‌ای است، که h همان ارتفاع گره درج یا حذف شده به وسیله به روز رسانی همۀ اجداد گره از پایین به بالا در درخت می‌باشد. به علاوه، چرخش‌های درخت که در حذف و درج مورد استفاده قرار می‌گرفت، ممکن است نیاز به به روز رسانی قسمت بالای گره‌های مورد تأثیر داشته باشد.


title: درخت بازه

text: در حال حاضر مشخص است که دو بازه A و B تلاقی دارند اگر و تنها اگر A.low ≤ B.high و A.high ≥ B.low. هنگام جستجوی درخت‌ها برای یافتن گره‌هایی که با یک بازه تلاقی دارند، شما می‌توانید بلافاصله از موارد زیر صرف نظر کنید:


title: درخت بازه

text: با مرتب کردن بازه‌ها ابتدا بر اساس مقدار پایین و سپس مقدار بالا یک ترتیب کلی را می‌توان برای بازه‌ها تعریف کرد. این مرتب‌سازی برای جلوگیری از درج بازه‌های تکراری در درخت در O(logn) می‌تواند در مقابل زمان o(k + logn) لازم برای یافتن تکرارها هنگامی کهk بازه با یک بازه جدید تلاقی دارند، مورد استفاده قرار گیرد.


title: درخت بازه

text: مثال Java :


title: درخت بازه

text: اضافه کردن یک بازه به درخت


title: درخت بازه

text: public void add(Interval i) {


title: درخت بازه

text: مثال Java : جستجو کردن یک نقطه یا بازه در درخت برای جستجو کردن یک بازه، باید درخت را پیمایش کرده و شاخه‌هایی را که نمی‌توانند شامل چیزهایی که شما به دنبال آن هستید باشند حذف کنید. حالت ساده جستجوی یک نقطه است:


title: درخت بازه

text: // Search for all intervals which contain "p", starting with the


title: درخت بازه

text: کد جستجوی یک بازه هم مشابه است به جز چک کردن قسمت میانی: // Check this node public boolean overlapsWith(Interval other) {


title: درخت بازه

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


title: درخت بازه

text: یک راه حل خیلی ساده‌تر استفاده از درخت‌های بازه‌ای تودرتو می‌باشد. ابتدا با استفاده از محدوده‌های y یک درخت بازه‌ای بسازید. حال برای هر گره درخت، برای همه عناصری که محدودۀ y آن‌ها با محدودۀ y آن گره اشتراک دارد، یک درخت بازه‌ای دیگر در محدودۀ x اضافه کنید. مزیت این راه حل این است که می‌تواند با یک کد پایه یکسان برای هر تعداد دلخواه از ابعاد گسترش یابد.


title: درخت بازه

text: در ابتدا هزینۀ درختان اضافی ممکن است سنگین به نظر برسد اما معمولاً چنین نیست. زیرا با راه حل فوق شما نیاز به یک گره در هر مختصات x دارید پس این هزینه در هر دو راه حل یکسان است. تنها تفاوت این است که شما نیاز به یک ساختار درختی اضافی در هر بازه عمودی دارید. این ساختار به‌طور معمول بسیار کوچک است. (یک اشاره‌گر به گره ریشه به علاوه شاید تعداد گره‌ها و ارتفاع درخت)


title: درخت بازه

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


title: درخت بازه

text: فرض کنیم دو بازه (a0, b0) , (a1, b1) را داریم. ابتدا و انتهای این بازه‌ها نسبت به یکدیگر می‌توانند یکی از 4 حالت زیر را داشته باشند:


title: درخت بازه

text: formula_1    OR    formula_2    OR    formula_3    OR    formula_4


title: درخت بازه

text: اما با تعریف 2 متغیر زیر:


درخت بازه


title: درخت بازه

text: تست هم‌پوشانی راحت‌تر خواهد شد:


title: درخت بازه

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


title: درخت بازه

text: از متغیرهای aq, bq, mq, dq برای بازۀ پرسش‌شده و از Mn برای کلید گره‌ای که (که با mi بازه‌ها مقایسه می‌شود) استفاده می کنیم.از گره ریشه شروع می کنیم. برای هر گره (که روی آن هستیم) ابتدا از طریق مقایسه کردن مقادیر ابتدا و انتهای بازۀ نظیر به گره بررسی می کنیم آیا بازهٔ پرس و جو شدۀ ما با گره‌های زیر درخت‌های گره فعلی می‌تواند هم‌پوشانی داشته باشد یا نه؟ اگر جواب منفی بود این روش را برای گره‌های زیر درخت‌های گره فعلی ادامه نمی‌دهیم.


title: درخت بازه

text: سپس ما را برای بازه‌های درون گره فعلی (نه فرزندهایش) برای بررسی هم‌پوشانی محاسبه می کنیم: (می‌دانیم )


title: درخت بازه

text: و برای هایی که از بزرگتر باشند یک درخواست روی Binary Heap می‌زنیم. سپس همین عمل را برای فرزندان راست و چپ گره انجام می‌دهیم. در بدترین حالت ما مجبور به دیدن تمامی گره‌های BST هستیم اما از آنجایی که درخواست روی Binary Heap بهینه است نباید نگران مرتبه الگوریتم باشیم. (یک مسئله دو بعدی نمی‌تواند در هر دو بعد بهینه باشد) انتظار می‌رفت که این الگوریتم از than traditional Interval Tree (Augmented tree) در عملیات جستجو سریعتر باشد درحالی که تنها کمی‌کندتر است و این اختلاف تأثیری در مرتبه زمانی ندارد. (مرتبه زمانی هر دو یکی است و تفاوت در ضرایب آن است)


title: نقطه در چندضلعی

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


title: نقطه در چندضلعی

text: ایوان سودرلند در سال ۱۹۷۴ دو راه‌حل (انتشار پرتو و جمع زوایا) برای این مسئله ارائه داد. تاریخچهٔ این مسئله و چند راه‌برد برای حل آن در یکی از شماره‌های مجلهٔ Ray Tracing News به چاپ رسیده‌است.


title: نقطه در چندضلعی

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


title: نقطه در چندضلعی

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


title: نقطه در چندضلعی

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


title: نقطه در چندضلعی

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


title: نقطه در چندضلعی

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


title: نقطه در چندضلعی

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


title: نقطه در چندضلعی

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


title: نقطه در چندضلعی

text: الگوریتم‌های بهتری برای چند ضلعی‌های یکنوا، ستاره‌گون یا محدب وجود دارند.


title: رادیو سوئد

text: رادیو سوئد () بنگاه سخن‌پراکنی بین‌المللی کشور سوئد است.


title: رادیو سوئد

text: تا سال ۲۰۱۲، رادیو سوئد اقدام به پخش به زبان‌های زیر کرده است:


title: الگوریتم لمکه-هاوسون

text: الگوریتم لمکه-هاوسون الگوریتمی برای محاسبه تعادل نش در بازی دوماتریسی (ماتریسی که در هر خانه‌اش دو عنصر دارد) است گفته می‌شود که این الگوریتم بهترین الگوریتم ترکیبیاتی برای یافتن تعادل نش است.


title: الگوریتم لمکه-هاوسون

text: ورودی الگوریتم یک بازی دو نفره G است. بازی G به صورت دو ماتریس n × m با نام A و B داده می‌شود که هر کدام از آنها شامل نتایج نهایی برای یکی از بازیکنان شماره ۱ و ۲ است که هر کدام به ترتیب، m و n استراتژی خالص دارند. در ادامه فرض می‌کنیم که نتایج مثبت هستند (هر بازی با تغییر مقیاس می‌تواند به بازی برابری از نظر استراتژی با نتایج مثبت تبدیل شود).


title: الگوریتم لمکه-هاوسون

text: بازی G دو چند وجهی متناظر دارد (که بهترین پاسخ بین چند وجهی‌ها نامیده می‌شوند)، به اسم‌های P و P که هر کدام به ترتیب m و n بعد دارند. در ادامه به تعریف این دو ماتریس می‌پردازیم.


title: الگوریتم لمکه-هاوسون

text: ماتریس P در R است. فرض کنید {"x"... ,"x"} مختصات را نشان می‌دهد. P به وسیله m نامساوی "x" ≥ ۰ برای همه {"i" ∈ {۱، ... , "m" و n نامساوی B"x"+... +B"x" ≤ ۱ برای همه {"j" ∈ {۱، ... , "n" تعریف می‌شود.


title: الگوریتم لمکه-هاوسون

text: ماتریس P در R است. فرض کنید {"x", ... , "x"} مختصات را نشان می‌دهد. P به وسیله n نامساوی "x" ≥ ۰ برای همه {"i" ∈ {۱، ... , "n" و m نامساوی A"x"+... +A"x" ≤ ۱ برای همه {"i" ∈ {۱، ... , "m" تعریف می‌شود.


title: الگوریتم لمکه-هاوسون

text: ماتریس "P" نشان‌دهنده مجموعه توزیع‌های احتمالاتی نُرمالایز نشده برای m استراتژی بازیکن اول است، هنگامی که نتیجه مورد انتظار بازیکن دوم حداکثر یک باشد. برای برقراری m شرط اول باید احتمالات نامنفی باشند و هر یک از n شرط بعد هم باعث می‌شود که n استراتژی خالص بازیکن دوم نتایجی با مقدار حداکثر یک داشته باشند. اگر نقش دو بازیکن را با هم عوض کنیم، ماتریس "P" نیز به همین ترتیب تعریف می‌شود.


title: الگوریتم لمکه-هاوسون

text: هر رأس v از ماتریس "P"، با مجموعه‌ای از برچسب‌ها (مقادیر) از مجموعه {۱،... ,"m" + "n"}، در ارتباط است. برای هر {"i" ∈ {۱، ... , "m" رأس v برچسب «i» را می‌پذیرد در صورتی که در رأس v شرط «"x" = ۰» برقرار باشد. برای هر "j" ∈ {۱، …, "n"}، v برچسب «m + j» را می‌پذیرد در صورتی که شرط «"B""x" + ...  + "B""x" = ۱» برقرار باشد. فرض کنید که "P" غیر تبهگن (nondegenerate) باشد، هر رأس بر m بعد از ماتریس "P" واقع است و m برچسب دارد. دقت کنید که ریشه که خود یک رأس از "P" می‌باشد، برچسب‌های {۱، …, m} را دارد.


title: الگوریتم لمکه-هاوسون

text: هر رأس w از از ماتریس "P" با مجموعه‌ای از برچسب‌ها از مجموعه {۱، …, "m + n"}، در ارتباط است. برای هر {"j" ∈ {۱، …, "n" رأس w برچسب «m + j» را می‌پذیرد در صورتی که در رأس w شرط «" x" = ۰» برقرار باشد. برای هر "i" ∈ {۱، …, "m"}، w برچسب «i» را می‌پذیرد در صورتی که شرط «"A""x" + ...  + "A""x" = ۱» برقرار باشد. فرض کنید که P غیر تبهگن باشد، هر رأس بر m بعد از ماتریس P واقع است و m برچسب دارد دقت کنید که ریشه که خود یک رأس از P می‌باشد، برچسب‌های {m + ۱، …, "m + n"} را دارد.


title: الگوریتم لمکه-هاوسون

text: عمل محوری شامل گرفتن زوج مرتبی مانند ("v", "w")، و عوض کردن v با یکی از همسایه‌هایش در P است یا عوض کردن w با یکی از همسایه‌هایش در P. در عمل محوری رأسی که عوض می‌شود را رها شده می‌نامیم. مثلاً اگر طی یک عمل محوری یک رأس از P جایگزین v شود، به اصطلاح می‌گوییم «v رها می‌شود». به ازای هر مقدار از v، می‌شود با انتقال به یک رأس همسایه که شامل ابرصفحه مرتبط با آن برچسب نباشد، آن برچسب را رها کرد.


title: الگوریتم لمکه-هاوسون

text: الگوریتم از زوج (v, w) شروع می‌شود که کاملاً برچسب‌گذاری (مقدار دهی) شده است که این زوج شامل زوج ریشه‌ها می‌باشد. برچسب دلخواه g را به دلخواه با انجام یک عمل محوری رها می‌کنیم. در نتیجه زوج مرتب ما به زوج تقریباً برچسب‌گذاری شدهٔ (’v’, w) تبدیل می‌شود (زوجی که تنها یک عنصر برچسب‌گذاری نشده دارد).


title: الگوریتم لمکه-هاوسون

text: هر زوج تقریباً برچسب‌گذاری شده (زوج مرتبی که تنها یک عنصر برچسب‌گذاری نشده دارد) دو عمل محوری می‌پذیرد که این عمل متناظر با رها کردن یک عنصر یا ایجاد یک کپی از برچسب‌های تکراری آن زوج می‌باشد. هر یک از این اعمال سرانجام به یک زوج کاملاً یا تقریباً برچسب‌گذاری شده ختم می‌گردد. در نهایت الگوریتم زوج مرتب کاملاً برچسب‌گذاری شدهٔ ("*"v"*", w) را بدست می‌آورد که مخالف ریشه است. زوج مرتب ("*"v"*", w) با یک زوج مرتب از توزیع‌های احتمالاتی نُرمالایز نشده متناظر است که در آن هر استراتژیِ بازیکن شماره یک مانند «i»، یا به بازیکن شماره یک می‌پردازد یا باید کمتر از یک واحد بپردازد و بازی با احتمال ۰ توسط آن بازیکن (بازیکن شماره یک) انجام می‌شود (برای بازیکن شماره دو نیز به همین ترتیب). با نُرمالایز کردن این مقادیر به توزیع‌های احتمال، تعادل نش بدست می‌آید (که در آن مقدار پرداختی به بازیکنان برابر وارون عوامل نرمال سازی می‌باشد).


title: الگوریتم لمکه-هاوسون

text: این الگوریتم حداکثر می‌تواند تا «n + m» تعادل نش متفاوت بیابد. هر برچسبی که در مرحله اولیه برای رها شدن انتخاب شود، تعیین کننده تعادل نشی است که الگوریتم می‌یابد. الگوریتم لمکه-هاوسون معادل رویکرد مبتنی بر هوموتوپی زیر است. بازیِ G را اینگونه تغییر می‌دهیم که یک استراتژی خالص دلخواه مانند g را انتخاب می‌کنیم و به بازیکنی که آن استراتژی را داشت مقدار زیاد «B» را می‌پردازیم تا حتماً آن را بازی کند. در این بازی تغییر یافته، می‌دانیم که استراتژی g با احتمال ۱ به وقوع می‌پیوندد و بازیکن مقابل نیز در جواب با احتمال ۱ بهترین بازی ممکن خود را انجام می‌دهد. زنجیره‌ای از بازی را در نظر بگیرید که در آن B به طور مداوم کاهش می‌یابد و به صفر میل می‌کند. یک مسیر تعادل نش وجود دارد که تعادل نش منحصربه‌فرد بازی جدید را به تعادلی در بازی اصلی G می‌رساند. استراتژی خالص انتخاب شدهٔ g برای دریافت جایزهٔ B، به برچسبی که در ابتدا رها می‌شود بستگی دارد.


title: الگوریتم لمکه-هاوسون

text: در حالی که این الگوریتم در عمل بهینه و کارآمد است، در بدترین حالت تعداد عملیات محوری لازم ممکن است تابعی نمایی از تعداد تمام استراتژی‌های خالص بازی باشد. متعاقباً نشان داده شده است که یافتن هر جوابی که با الگوریتم لمکه-هاوسون بدست می‌آید PSPACE-complete می‌باشد.


title: داسو اویاسیون

text: گروه هوانوردی داسو یک شرکت هواپیماسازی فرانسوی تولیدکننده هواپیماهای نظامی و هواپیماهای جت سفارشی و شخصی است که از زیرمجموعه‌های گروه صنعتی داسو محسوب می‌شود. مارسل داسو مهندس فرانسوی و از مخترعین علمی هواپیما در سال ۱۹۲۹ این شرکت هواپیماسازی را تأسیس کرد. داسو تنها شرکت هوانوردی دنیاست که هنوز در مالکیت خانواده بنیانگذار آن قرار دارد و نام آن‌ها هنوز بر روی آن مانده‌است. دفتر مرکزی شرکت داسو در پاریس پایتخت فرانسه قرار دارد و در بیش از ۸۳ کشور دنیا فعالیت تجاری دارد. حدود ۱۱۶۰۰ کارمند در گروه هوانوردی داسو مشغول به کار هستند که ۹۰۰۰ نفر آن در کارخانجات و دفاتر این شرکت در فرانسه کار می‌کنند.بیش از ۴۰ درصد سهام این شرکت و بیش از ۶۰ درصد حق رای شرکت در دست دولت فرانسه می باشد


title: داسو اویاسیون

text: از معروفترین تولیدات این شرکت هواپیماهای جنگنده سری میراژ از جمله میراژ ۳، میراژ اف۱ و میراژ-۲۰۰۰، جنگنده چند منظوره داسو رافال، جنگنده ضربتی سوپر اتاندارد و جت‌های تجاری سری فالکن از جمله داسو فالکون ۱۰ , داسو فالکون ۲۰ , داسو فالکون ۵۰ , داسو فالکون ۹۰۰ , داسو فالکون ۲۰۰۰ , داسو فالکون ۷ایکس هستند.


title: داسو اویاسیون

text: Wikipedia contributors, "Dassault_Aviation," Wikipedia, The Free Encyclopedia, (accessed December 21, 2009).


title: مسائل هیلبرت

text: مسائل هیلبرت شامل بیست‌و سه سؤال ریاضی است که در سال ۱۹۰۰ توسط ریاضی‌دان آلمانی دیوید هیلبرت منتشر شد. مسائل همگی در آن زمان حل نشده بودند و بعضی از آن‌ها تأثیر بسزایی بر ریاضیات قرن بیستم گذاشتند. هیلبرت ۱۰ تا از این سؤالات (۱ ،۲ ،۶ ،۷ ،۸ ،۱۳ ،۱۶ ،۱۹ ،۲۱ و ۲۲) را در کنگره جهانی ریاضیدانان، در هشتم اوت در سوربن پاریس ارائه کرد. لیست کاملی از ۲۳ سؤال بعدها در مجلهٔ انجمن ریاضی آمریکا عمدتاً با ترجمهٔ انگلیسی ماری فرانسیس وینستون نیوسون آمد.


title: مسائل هیلبرت

text: مسائل هیلبرت از لحاظ محتوا و دقت متفاوت هستند. بعضی از آن‌ها مانند سؤال سوم (احتمالاً راحت‌ترین سؤال برای درک توسط غیرمتخصص‌ها و اولین سؤال حل شده از بین مسائل) یا سؤال مشهور هشتم (فرضیهٔ ریمان)، به اندازه‌ای دقیق تعریف شده‌اند که جوابی روشن برای رد یا قبولشان وجود دارد. مسائل دیگری (مانند مسئلهٔ ۵) وجود دارند که متخصصان به تفسیری واحد از مسئله رسیده‌اند و پاسخی نیز برای آن تفسیر ارائه شده ولی به نظر می‌رسد هنوز بخشی از مسئله که شاید مورد نظر هیلبرت نیز بوده بدون حل باقی‌مانده است. گاهی بیان هیلبرت به اندازه‌ای دقیق نیست که مسئله مشخصی را مشخص کند ولی باعث تعریف مسائل مشخصی در حیطهٔ مورد نظر شده‌است. برای مثال بسیاری از دانشمندان حوزهٔ نظریهٔ اعداد احتمالاً سؤال ۹ام را اشاره‌ای به تناظر Langland به نمایندگی از گروه گالوایی مطلق یک میدان عددی می‌دانند. مسائل دیگری (مانند مسئله ۱۱ام و ۱۶ام) مورد توجه رشته‌های فرعی در حال پیشرفت ریاضی مانند نظریه فرم‌های درجه‌دوم و خم‌های جبری حقیقی قرار گرفته‌اند. مسائل ۶ام و ۴ام نه تنها هنوز حل نشده‌اند بلکه با توجه به استانداردهای جدید قابل حل نیستند. مسئلهٔ ششم، ساختاری اصول‌مند برای فیزیک می‌خواست، که با توجه به پیشرفت‌های قرن بیستم فیزیک (از جمله اینکه به عنوان شاخه‌ای مستقل از ریاضی شناخته شد) به نظر می‌رسد دیگر اهمیت زمان هیلبرت را ندارد. همچنین سؤال چهارم که ساختار هندسه را در نظر داشت به نظر می‌رسد که دیگر جواب قطعی ندارد. بیست‌ویک مسئلهٔ دیگر همگی مورد توجه زیاد ریاضی‌دانان قرار گرفتند و کار روی آن‌ها اهمیت زیادی داشت به گونه‌ای که پائول کوهن برای کارش روی مسئلهٔ اول در سال ۱۹۶۶ و ماتیاسویچ برای ارائهٔ پاسخ منفی سؤال دهم (ادامهٔ کار دیویس، پوتنام، رابینسون) در سال ۱۹۷۰ مدال فیلد گرفتند، و اثبات تقیض راه حل مسئلهٔ دهم در دههٔ ۱۹۷۰ توسط ماتیاسویچ نیز فیلد را به خود اختصاص داد. جنبه‌های این مسائل همچنان یکی از مورد علاقه‌ترین زمینه‌های تحقیق امروزی است.


title: مسائل هیلبرت

text: بعضی از مسائل هیلبرت به گونه‌ای عجیب یا حتی اذیت‌کننده برای هیلبرت حل شده‌اند. هیلبرت پیرو فرگه و راسل به دنبال تعریف منطقی با استفاده از سیستم فرمال، یعنی اثبات‌هایی متناهی از اصول موضوعهٔ پذیرفته‌شده، برای ریاضیات بود. یکی از مسائل هیلبرت (مسئلهٔ دوم) در واقع خواستار اثباتی متناهی برای استحکام اصول موضوعهٔ منطق است. به هر حال تئوری عدم کمال دوم گودل با دقت نشان می‌دهد که می‌توان ثابت کرد که چنین اثبات متناهی برای استحکام منطق غیرقابل ارائه است. هیلبرت ۱۲ سال بعد از گودل زندگی کرد ولی به نظر نمی‌رسد جواب رسمی به کارهای گودل نوشته باشد. بدون شک کارهای گودل بر روی کل ریاضیات (و نه تنها منطق) بسیار حائز اهمیت است هر چند که باعث حل شدن عجیب و شاید ناراحت‌کنندهٔ یکی از سؤالات هیلبرت شد. مسئلهٔ دهم هیلبرت نمی‌پرسد که آیا الگوریتمی برای حل معادلهٔ دیوفانتی وجود دارد یا نه. بلکه ساختار چنین الگوریتمی را مورد نظر دارد. «ارائهٔ پروسه‌ای که با انجام متنهای عمل بتوان معین کرد که آیا یک معادله در اعداد گویا قابل حل است یا خیر.» حل این مسئله که نشان می‌داد چنین الگوریتمی وجود ندارد برای وی بسیار عجیب بود. با توجه به نظر وی که هر مسئلهٔ ریاضی حتماً راه‌حلی دارد او این اجازه را داد که راه‌حل مسئله اثبات این باشد که حل مسئله اصلی امکان‌پذیر نیست. مشهور است که او بیان کرده مهم این است که آیا راه‌حلی وجود دارد یا نه؛ و او عقیده داشت که ما همواره می‌توانیم این نکته را بفهمیم. یعنی در ریاضیات گزارهٔ دارای ابهام (گزاره‌ای که هرگز ارزش درستی آن معلوم نشود) وجود ندارد. واضح نیست که آیا او پاسخ سؤال دهم را دارای ابهام تلقی کرده‌است یا نه: آنچه که ما اثبات نمی‌کنیم که مسئله پاسخ طبیعی ندارد بلکه تنها می‌توانیم بفهمیم که آیا مسئله در حالت کلی دارای جواب است یا خیر. از سوی دیگر وضعیت مسئلهٔ اول و دوم پیچیده‌تر است. هیچ اتفاق نظر واضح ریاضی وجود ندارد که آیا نتایج گودل (در مورد سؤال دوم) یا گودل و کوهن (در مورد سؤال اول) جواب منفی قطعی به مسئله می‌دهند یا نه. از آنجایی که این راه‌حل‌ها به شکل خاصی از سؤال جواب می‌دهند و ممکن این شکل‌بندی تنها شکل بندی موجود برای این دو مسئله نباشد.


title: مسائل هیلبرت

text: هیلبرت در واقع ۲۴ مسئله در لیستش آورده بود ولی از انتشار سؤال بیست‌وچهارم جلوگیری کرده بود. مسئله بیست‌وچهارم (ملاکی برای سادگی در نظریهٔ اثبات) توسط رودیگر تیله تاریخ‌دان آلمانی از دست‌نوشته‌های هیلبرت به دست آمد.


title: مسائل هیلبرت

text: از سال ۱۹۰۰ ریاضیدانان و مراکز ریاضی لیست‌هایی از مسائل را منتشر می‌کردند ولی این لیست‌ها به اندازهٔ مسائل هیلبرت تأثیر نداشت و برای ریاضی‌دانان کار ایجاد نمی‌کرد! یکی از موارد استثنای این لیست‌ها سه حدسی بودند که توسط آندره وِیل در اواخر دههٔ چهل میلادی ارائه شد (حدس‌های وِیل). حدس‌های ویل در زمینهٔ هندسهٔ جبری و نظریهٔ اعداد و ارتباط بین این دو بسیار مهم بودند. حدس اول توسط برنارد دیوُرک اثبات شد و اثباتی کاملاً متفاوت برای حدس اول و دوم توسط الکساندر گروتندیک با استفاده از همریختی مرتبهٔ اول ارائه شد. آخرین و عمیق‌ترین حدس وِیل توسط پییِر دلین! اثبات شد. هر دوی گروتندیک و دلین! مدال فیلدز گرفتند؛ ولی حدس‌های ویل در زمینهٔ خود به اندازهٔ یک سؤال هیلبرت اهمیت دارند و ویل هرگز آن‌ها را برنامه‌ای برای ریاضیات نخواند. این کمی طعنه‌آمیز است زیرا به اقرار بسیاری ویل ریاضی‌دان دهه‌های چهل و پنجاه میلادی بود که در شاخه‌های مختلف ریاضی نظری وارد شد و در گسترش آن‌ها اهمیت داشت و به بهترین نحو نقش هیلبرت را در آن برهه از زمان بازی کرد. پال اردوش به خاطر طرح صدها بلکه هزاران سؤال ریاضی مشهور است. بعضی از سؤالات وی عمیق هستند. اردوش برای مسائلش بسته به سختی پیش‌بینی شده‌اش جایزه‌ای در نظر می‌گرفت. پایان هزارهٔ دوم که مصادف با صدمین سالگرد انتشار مسائل هیلبرت بود زمان طبیعی مناسبی برای ارائهٔ مجموعهٔ جدید مسائل هیلبرت به‌شمار می‌رفت. چند تن از ریاضی‌دانان از جمله استیو اسمیل، برندهٔ مدال فیلدز درخواست ولادیمیر آرنولد را پذیرفت و لیستی شامل ۱۸ مسئله را پیشنهاد داد. جامعهٔ ریاضی اقبال چندانی به مسائل اسمیل نشان نداد و هنوز روشن نیست این مسائل چقدر مورد توجه ریاضی‌دانان قرار گیرند. حداقل در جریان اصلی جامعه متناظر مسائل هیلبرت برای قرن بیست‌ویکم لیستی از هفت مسئله جایزهٔ هزاره است که توسط مؤسسهٔ ریاضی کلِی در سال ۲۰۰۰ انتخاب شدند. بر خلاف مسائل هیلبرت که جایزهٔ اصلی آن‌ها تحسین هیلبرت و جامعهٔ ریاضی بود، هر سؤال به اندازهٔ یک میلیون دلار جایزه دارد. مانند سؤالات هیلبرت یکی از مسائل جایزه هزاره (حدس پوانکاره) نیز تقریباً با فاصلهٔ اندکی از زمان انتشار حل شد.


title: مسائل هیلبرت

text: حدس ریمان که هم در هر سه لیست هیلبرت، اسمیل و جایزهٔ هزاره -حتی شبیه هندسه‌ای آن در حدس‌های ویل- آمده است. از چنان اهمیتی برخوردار است که هنوز هم ریاضی‌دانان با آن درگیر هستند و بسیاری از متخصصین عقیده دارند که این مسئله تا قرن‌ها در لیست مسائل خواهد آمد. هیلبرت خود اعلام کرده: "اگر از یک خواب هزاران ساله بیدار شوم اولین سؤالم این خواهد بود که آیا حدس ریمان اثبات شده است؟" در سال ۲۰۰۸ دارپا لیست ۲۳تایی خود از مسائل ریاضی را اعلام کرد و امید داشت که این لیست به پیشرفت‌های بزرگی در ریاضیات منجر شود. "در نتیجه توانایی‌های علمی و فنی دپارتمان دفاعی را تقویت می‌کند."


title: مسائل هیلبرت

text: برای مسائل ۳، ۷، ۱۰، ۱۱، ۱۳، ۱۴، ۱۷، ۱۹، ۲۰و ۲۱ که به صورت واضحی فرموله شده‌اند، راه‌حل‌هایی پیدا شده‌اند که توسط اجتماع ریاضی قبول شده‌اند؛ ولی برای مسائل ۱، ۲، ۵، ۹، ۱۵، ۱۸و ۲۲ راه‌حل‌هایی وجود دارد که مورد پذیرش بخشی قرار گرفته‌اند البته بحث‌هایی وجود دارد که آیا آن راه‌حل‌ها مسائل را حل کرده‌اند یا نه. علامت + در بالای ۱۸ برای این است که راه حل حدس کپلر یک اثبات به کمک کامپیوتر است. اشاره‌ای نامربوط و تا حدی بحث‌برانگیز به مسئلهٔ هیلبرت، به خاطر این که خواننده انسانی نمی‌تواند در زمانی منطقی اثباتی برای آن بیابد. سؤالات ۱۶، ۸ (حدس ریمان) و ۱۲ حل نشده‌اند. در این طبقه‌بندی سؤالات ۴، ۱۶ و ۲۳ به اندازه‌ای مبهم هستند که حل شده محسوب می‌شوند. مسئلهٔ ۲۴ که بعداً ارائه شد نیز در این دسته قرار می‌گیرد. سؤال ۶ نیز بیشتر سؤالی فیزیکی محسوب می‌شود تا ریاضی.


title: مسائل هیلبرت

text: ۲۳ مسئلهٔ هیلبرت به شرح زیر است:


title: چاردرخت

text: چاردرخت یک داده ساختار درختی است که در آن هر گره داخلی دقیقاً چهار فرزند دارد. این داده‌ساختار معمولاً برای افراز یک فضای دوبعدی به صورت بازگشتی به تعدادی ناحیه (چارک) استفاده می‌شود. این ناحیه‌ها ممکن است مربع، مستطیل یا به هر شکل دیگری باشند. در سال ۱۹۷۴، Raphael Finkel و J.L. Bentley این داده‌ساختار را quadtree نامیدند. چنین افرازی Q-tree نیز خوانده می‌شود. همۀ انواع چاردرخت، در تعدادی ویژگی مشترکند:


title: چاردرخت

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


title: چاردرخت

text: این نوع چاردرخت، نمایشگر افرازی از یک صفحۀ دوبعدی است که در آن افراز، صفحۀ دوبعدی به چهار ناحیۀ برابر افراز شده و برخی ناحیه‌ها خود به چهار زیرناحیۀ برابر افراز شده‌اند و به همین ترتیب فرایند افراز می‌تواند ادامه پیدا کند. در چنین افرازی، هر گره، یا چهار فرزند دارد یا فرزندی ندارد (برگ است). هر برگ از درخت مربوط به یکی از زیر‌ناحیه‌های افراز است و اطلاعات آن زیرناحیه در آن برگ ذخیره می‌شود. چاردرخت ناحیه‌ای یک نوع ترای است.


title: چاردرخت

text: می‌توان از یک چاردرخت ناحیه‌ای با ارتفاع n برای نمایش یک تصویر با ابعاد 2 × 2 پیکسل (که مقدار هر پیکسل ۰ یا ۱ است) استفاده کرد. ریشۀ درخت، نمایشگر کل تصویر است. هر ناحیه‌ای که مقدار همۀ پیکسل‌هایش با هم برابر نیست، به ۴ زیرناحیه تقسیم می‌شود. در نهایت هر برگ از درخت، مجموعه‌ای مربع‌شکل از تعدادی پیکسل را نشان می‌دهد که همگی ۰ یا همگی ۱ هستند.


title: چاردرخت

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


title: چاردرخت

text: چاردرخت نقطه‌ای تعمیمی از درخت دودویی است. از یک درخت دودویی می‌توان برای ذخیره تعدادی عدد (از فضای یک‌بعدی) استفاده کرد. ولی از چاردرخت نقطه‌ای می‌توان برای ذخیره تعدادی نقطه (دوتایی مرتب) از فضای دوبعدی استفاده کرد. این درخت، همۀ ویژگی‌های چاردرخت را دارد و یک درخت واقعی است. یعنی گره‌های درخت، خود نقاطی هستند که می‌خواهیم نمایش دهیم (برخلاف چاردرخت ناحیه‌ای، وقتی که برای نمایش تعدادی نقطه مورد استفاده قرار بگیرد). شکل ناحیه‌های ایجاد شده به ترتیب اضافه کردن نقاط بستگی دارد (درست مثل درخت دودویی جستجو). چاردرخت نقطه‌ای، معمولاً برای مقایسه بین مجموعه‌ای از نقاط در صفحۀ دوبعدی بسیار بهینه (معمولاً از O(log n)) عمل می‌کند.


title: چاردرخت

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


title: چاردرخت

text: این چاردرخت برای ذخیرۀ خط و منحنی (به جای نقطه) استفاده می‌شود. یک منحنی با تقسیمات زیاد ناحیه‌ها تقریب زده می‌شود. این کار ممکن است باعث شود که یک درخت بسیار نامتوازن ایجاد شود که با هدف کاراتر شدن دسترسی‌ها تناقض دارد.


title: چاردرخت

text: این چاردرخت (PMQuadtree) نوعی چاردرخت است که برای ذخیرۀ مجموعه‌ای از چندضلعی‌ها استفاده می‌شود که ممکن است تبه‌گون باشند (یعنی یک ضلع مجزا یا یک رأس مجزا در میانشان باشد). سه ردۀ اصلی از PMQuadtree ها وجود دارد که به خاطر نوع داده‌هایی که در گره‌های سیاه ذخیره می‌شود تفاوت دارند. چاردرخت PM3 می‌تواند تعدادی ضلع نامتقاطع و حداکثر یک نقطه را ذخیره کند. چاردرخت PM2 همانند PM3 است با این تفاوت که همه ضلع‌ها باید نقطۀ پایانی یکسان داشته باشند. چاردرخت PM1 نیز شبیه PM2 است. ولی گره‌های سیاه می‌توانند یک نقطه و ضلع‌های متصل به آن یا فقط تعدادی ضلع که در یک نقطه مشترک هستند را در خود ذخیره کنند، ولی نمی‌توان یک نقطه و تعدادی ضلع که در آن نقطه مشترک نیستند را در گره ذخیره کرد.


title: چاردرخت

text: چاردرخت، معادل دوبعدی هشت‌درخت است.


title: چاردرخت

text: این شبه کد، روشی برای پیاده‌سازی یک چاردرخت است که فقط نقاط را ذخیره می‌کند. پیاده‌سازی‌های دیگری نیز برای این کار وجود دارد.


title: چاردرخت

text: در این پیاده‌سازی، از این ساختارها استفاده شده است: // Simple coordinate object to represent points and vectors struct XY


title: چاردرخت

text: // Axis-aligned bounding box with half dimension and center struct AABB


title: چاردرخت

text: این کلاس، ریشۀ یک چاردرخت را (که کل چاردرخت را مشخص می‌کند) ذخیره می‌کند. class QuadTree


title: چاردرخت

text: این تابع یک نقطه را در چارک (زیرناحیه) مناسب از چاردرخت ذخیره می‌کند و در صورت نیاز ناحیه را تکه می‌کند. class QuadTree


title: چاردرخت

text: این تابع، همۀ نقاطی که در یک بازه قرار دارند را پیدا می‌کند. class QuadTree


title: ماشین اوراکل

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


title: ماشین اوراکل

text: ماشین اوراکل را می‌توان یک ماشین تورینگ متصّل به یک اوراکل تصوّر کرد. اوراکل، در این مبحث، موجودیّتی قادر به حل یک سری مسائل است، که به عنوان مثال می‌تواند مسئلۀ تصمیم یا مسئلۀ تابع باشد. مسئله ممکن است محاسبه‌پذیر نباشد؛ اوراکل یک ماشین تورینگ یا برنامۀ کامپیوتری تلقّی نمی‌شود. اوراکل به طورِ ساده یک «جعبۀ سیاه» است که قادر به تولید پاسخی برای هر نمونه از یک مسئلۀ محاسباتی است:


title: ماشین اوراکل

text: یک ماشین اوراکل می‌تواند تمام اعمال معمول یک ماشین تورینگ را به انجام برساند، و هم‌چنین می‌تواند از اوراکل برای به دست آوردن پاسخی برای هر نمونه از مسئلۀ محاسباتی برای آن اوراکل بهره ببرد. برای مثال اگر مسئله یک مسئلۀ تصمیم بر روی یک مجموعۀ "A از اعداد طبیعی باشد، ماشین اوراکل یک عدد طبیعی به اوراکل عرضه می‌دارد، و اوراکل بسته به این که آن عدد عضو 'A' باشد با «بله» یا «نه» پاسخ می‌دهد.


title: ماشین اوراکل

text: تعاریف هم‌ارز متعدّدی برای ماشین تورینگ اوراکل وجود دارد، که در پایین در مورد آن‌ها بحث شده‌است. موردی که این‌جا ارائه شده‌است از van Melkebeek است (۲۰۰۰:۴۳).


title: ماشین اوراکل

text: یک ماشین اوراکل مانند یک ماشین تورینگ شامل اجزای زیر است:


title: ماشین اوراکل

text: علاوه بر این اجزا، یک ماشین اوراکل شامل اجزای زیر نیز هست:


title: ماشین اوراکل

text: گاه‌به‌گاه، ماشین اوراکل ممکن است وارد حالت "پرسش" شود. هنگام این رخ‌داد، اعمال زیر در یک مرحلۀ محاسباتی انجام می‌شوند: بنابراین تأثیر تغییر به حالت "پرسش"، گرفتن پاسخ، در یک مرحله، به نمونه‌ای از مسئله است که بر روی نوار اوراکل نوشته شده‌است.


title: ماشین اوراکل

text: علاوه بر تعریفی که در بالا ارائه شد تعاریف جای‌گزینِ دیگری نیز وجود دارند. تعدادی از آن‌ها خاصِّ موردی هستند که اوراکِل یک مسئلۀ تصمیم را حل می‌کند. در این مورد:


title: ماشین اوراکل

text: این تعاریف از منظر محاسبه‌پذیری تورینگ معادل هستند: تابعی که تحت اوراکِل یکی از این تعاریف، اوراکِل‌محاسبه‌پذیر باشد، تحت هر دیگری نیز اوراکِل‌محاسبه‌پذیر است. هرچند از منظر پیچیدگی محاسباتی، این تعاریف معادل نیستند. تعریفی مانند آن‌چه که van Melkebeek ارائه داده‌بود، که در آن از نوار اوراکِلی که ممکن است الفبای خود را داشته باشد استفاده می‌شود، در حالت عمومی لازم است.


title: ماشین اوراکل

text: کلاس پیچیدگی مسائل تصمیمِ حل‌پذیر توسّط الگوریتمی در کلاس A با استفاده از اوراکِلی برای زبان A، L نامیده می‌شود. به‌طور مثال، P کلاس مسائل حل‌پذیر در زمان چندجمله‌ای توسّط یک ماشین تورینگ قطعی با اوراکلی برای مسئلۀ ارضاپذیری بولی (SAT) است. نمادگذاری A را می‌توان برای مجموعۀ زبان‌های B (یا کلاس پیچیدگی B)، با استفاده از تعریف زیر، تعمیم داد:


title: ماشین اوراکل

text: زمانی که یک زبانِ L برای کلاس B کامل باشد، آن‌گاه A=A در صورتی که ماشین‌های درون A بتوانند تقلیل‌های استفاده‌شده در تعریف کامل بودن کلاس B را اجرا نمایند. به‌طور خاص، از آن‌جایی که مسئلۀ ارضاپذیریِ بولی نسبت به تقلیل‌های زمان چندجمله‌ای ان‌پی کامل است، P=P. هرچند، اگر A=DLOGTIME (کلاس مسائل حل‌پذیر در زمان لگاریتمی توسّط ماشین تورینگ قطعی)، آن‌گاه A ممکن است برابر با A نباشد.


title: ماشین اوراکل

text: واضح است که NP ⊆ P، ولی این پرسش که آیا NP، P، NP و P برابر هستند یا نه، در بهترین حالت عملی باقی می‌مانند. باور بر تفاوت آن‌هاست و این باعث تعریف سلسله‌مراتب چندجمله‌ای می‌شود.


title: ماشین اوراکل

text: ماشین‌های اوراکل، با در نظر گرفتن رابطۀ بین P و NP برای یک اوراکل A، برای بررسی رابطۀ بین کلاس‌های پیچیدگی P و NP مفید هستند. به‌طور خاص، نشان داده شده‌است که وجود دارند زبان‌های A و B، به قسمی که P=NP و (Gill P≠NP، Baker و Solovay 1975). این حقیقت که پرسش P = NP از هر دو جهت به صورت نسبی است، به این دلیل است که پاسخ به این پرسش دشوار است، زیرا تکنیک اثباتی که به صورت "نسبی" انجام می‌گیرد (بدون تأثیر گرفتن از اضافه شدن یک اوراکل) نمی‌تواند به پرسش P = NP پاسخ دهد. بسیاری از تکنیک‌های اثبات از نسبی سازی استفاده می‌کنند.


title: ماشین اوراکل

text: در نظر گرفتن حالتی که یک اوراکل از میان تمام اوراکل‌های ممکن(یک مجموعه بینهایت) به صورت تصادفی انتخاب شود، قابل توجه است. در این حالت نشان داده شده‌است که با احتمال یک، P≠NP (Bennet و Gill 1981). هنگامی که پاسخ سوالی برای همۀ اوراکل‌ها درست باشد، در آن صورت پاسخ پرسش برای یک اوراکل تصادفی نیز درست است. این انتخاب اصطلاحات با دانستن این حقیقت که اوراکل‌های تصادفی یک عبارت را فقط با احتمال 1 یا 0 تأیید می‌کنند، قابل توجیه است. (این از روی قانون یک‌صفر Kolmogorov بدست می‌آید.) به عنوان یک گواه P≠NP. یک عبارت ممکن است همزمان برای یک اوراکل تصادفی درست و برای یک ماشین تورینگ عادی غلط باشد؛ برای مثال برای اوراکل‌های A، IP≠PSPACE، در حالی که IP = PSPACE (Chang et al، 1994).


title: ماشین اوراکل

text: ممکن است که وجود اوراکلی را فرض کرد که قادر به محاسبۀ یک تابع محاسبه‌ناپذیر باشد، مانند پاسخ به مسئلۀ توقّف یا مسائل مشابه دیگر. ماشینی با چنین اوراکلی یک فراکامپیوتر است.


title: ماشین اوراکل

text: به طرز جالبی، پارادوکس پایان‌پذیری هنوز در مورد این ماشین‌ها نیز صدق می‌کند؛ با وجود اینکه این ماشین‌ها می‌توانند تعیین کنند که آیا ماشین تورینگ خاصی با ورودی‌های خاصی به حالت پایان خواهد رسید، به‌طور کلی، آن‌ها نمی‌توانند تعیین کنند که آیا ماشین‌های معادل خودشان به حالت پایان خواهند رسید. این حقیقت منجر به ایجاد سلسله مراتبی از ماشین‌ها به نام سلسله مراتب محاسباتی می‌شود، که هر رده دارای اوراکل پایان‌پذیری قوی‌تر و مسئلۀ پایان‌پذیری قوی‌تری است.


title: ماشین اوراکل

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


title: شاخه و برش

text: شاخه و برش (Branch and cut) روشی است در بهینه سازی ترکیبیاتی برای حل مسائل برنامه‌های خطی عدد صحیح، این مسائل، برنامه نویسی خطی هستند که در آن‌ها برخی یا همهٔ مجهولات به مقادیر اعداد صحیح محدود‌اند. شاخه و برش شامل اجرای یک الگوریتم شاخه و حد، و استفاده از سطح برش به منظور محدود کردن راحتی در برنامه‌نویسی خطی است. لازم به ذکر است که اگر برش‌ها تنها به منظور محدود کردن راحتی اولیه برنامه نویسی خطی مورد استفاده قرار گیرند؛ الگوریتم برش و شاخه نامیده می‌شود.


title: شاخه و برش

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


title: شاخه و برش

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


title: شاخه و برش

text: الگوریتم به صورت زیر خلاصه شده‌است. الگوریتم فرض می‌کند ILP (برنامه‌نویسی منطقی استقرایی) یک مسئلهٔ بیشینه سازی است.


title: شاخه و برش

text: یک مرحلهٔ مهم در الگوریتم شاخه و حد مرحلهٔ شاخه شدن است. در این مرحله انواع مختلفی از شاخه شدن‌های ابتکاری وجود دارد که می‌توان از آن‌ها استفاده کرد. تمامی استراتژی‌های شاخه شدنی که در زیر توضیح داده شده‌اند شامل موردی هستند به نام شاخه شدن بر روی متغیر. شاخه شدن بر روی متغیر شامل انتخاب یک متغیر، formula_14، و مقدار کسری formula_15 برای جواب راحتی lp کنونی و سپس اضافه کردن قیود formula_16 و formula_17 است. همچنین تعداد زیادی از گونه‌های این استراتژی‌های شاخه شدن وجود دارد. به عنوان مثال زمانی که شاخه شدن شبه هزینه نسبتاً بی ارزش است ابتدا از شاخه شدن قوی استفاده کرد سپس بعداً از شاخه شدن شبه هزینه استفاده کرد زمانی که به اندازهٔ کافی تاریخچهٔ شاخه کردن موجود باشد تا این روش مؤثر واقع شود.


title: الگوریتم تعمیم‌یافته اقلیدس

text: در علم حساب و برنامه نویسی کامپیوتر الگوریتم تعمیم یافته اقلیدس تعمیمی بر الگوریتم اقلیدس است که در کنار محاسبه بزرگترین مقسوم علیه مشترک دو عدد صحیح a,b ضرایب قضیه بزو را هم محاسبه می‌کند(x,y اعداد صحیح اند):  formula_1  همچنین می‌توان بدون هزینهٔ اضافی خارج قسمت a,b را با بزرگترین مقسوم علیه مشترک محاسبه کرد.


title: الگوریتم تعمیم‌یافته اقلیدس

text: الگوریتم تعمیم یافته اقلیدس به الگوریتمی بسیار مشابه به الگوریتمی برای محاسبه بزرگترین مقسوم علیه مشترک چندجمله ای و ضرایب قضیه بزو از دو چندجمله‌ای با یک متغیر، ارجاع دارد.  الگوریتم تعمیم یافته اقلیدس زمانی که a و b نسبت به هم اولند مفید تر است. چون x برابر وارون ضربی پیمانه‌ای a به پیمانه b و y برابر وارون ضربی پیمانه‌ای b به پیمانه a است. در الگوریتم اقلیدس برای چندجمله‌ای می‌توان وارون ضربی را در بسط‌های میدان جبری محاسبه کرد. که از آن نتیجه می‌شود هردو نوع الگوریتم اقلیدسی تعمیم یافته (معمولی و چندجمله‌ای) کاربردی گسترده در رمزنگاری دارند. به خصوص در محاسبه وارون ضربی پیمانه‌ای در روش RSA یک گام ضروریست.  در الگوریتم اقلیدسی معمولی فقط باقی‌مانده‌ها نگاه داشته می‌شوند و خارج قسمت استفاده نمی‌شود. اما در الگوریتم تعمیم یافته خارج قسمت‌های متوالی استفاده می‌شوند. به‌طور دقیقتر در الگوریتم تعمیم یافته که a، b را به عنوان ورودی می‌گیرد، دنبالهٔ  formula_2 از خارج قسمت‌ها و دنبالهٔ  formula_3 از باقی‌مانده‌ها را شامل می‌شود.


title: الگوریتم تعمیم‌یافته اقلیدس

text: مهمترین ویژگی تقسیم اقلیدسی نامساوی سمت راست است که  formula_5 را متفاوت از  formula_6 و formula_7 تعریف می‌کند. وقتی باقی‌مانده به صفر رسید محاسبه متوقف می‌شود، بزرگترین مقسوم علیه مشترک آخرین باقی‌مانده غیر صفر است. الگوریتم تعمیم یافته اقلیدسی روشی مشابه دارد با این تفاوت که دو دنبالهٔ زیر نیز به آن اضافه می‌شود:


title: الگوریتم تعمیم‌یافته اقلیدس

text: در این الگوریتم هم وقتی formula_9 میشود کار الگوریتم به اتمام می‌رسد.  formula_15 formula_16 و formula_17  به علاوه اگر a و b هردو مثبت باشند داریم:  که این یعنی جفت ضرایب بزو که از این الگوریتم به دست می‌آیند یکی از کمترین جفت ضرایب بزو هستند.


title: الگوریتم تعمیم‌یافته اقلیدس

text: جدول زیر رویه الگوریتم تعمیم یافته اقلیدسی را برای46 و240 را نشان می‌دهد. بزرگترین مقسوم علیه مشترک برابر ۲ است. محاسبه در ستون ۶ متوقف می‌شود، چون باقی‌مانده صفر می‌شود. ضرایب بزو هم در دو ستون آخر از سطر آخرند. تحقیق رابطه -9*240+47*46=2 راحت است. و سرانجام -120 و 23 بدون توجه به علامت برابر تقسیم ۲۴۰ و ۴۶ بر بزرگترین مقسوم علیه مشترک یعنی ۲ هستند


title: الگوریتم تعمیم‌یافته اقلیدس

text: چون  formula_19 و دنبالهٔ باقی‌مانده‌ها یک دنبالهٔ نزولی غیر منفی است در نتیجه باید حتماً با formula_20 متوقف شود. این نشان می‌دهد که الگوریتم متوقف می‌شود و کار به اتمام می‌رسد.


title: الگوریتم تعمیم‌یافته اقلیدس

text: چون formula_21 در نتیجه بزرگترین مقسوم علیه مشترک formula_22 و formula_23 برابر است. که از ان نتیجه می‌شود بزرگترین مقسوم علیه مشترک formula_24 برابر است با بزرگترین مقسوم علیه مشترک formula_25 وهمچنین نشان می‌دهد که formula_26 بزرگترین مقسوم علیه مشترک a و b است که آن را d می‌نامیم.


title: الگوریتم تعمیم‌یافته اقلیدس

text: formula_27 و formula_28  که برای i=0,1داریم: formula_29  برای هر i رابطهٔ بازگشتی خطی  برقرار است بخصوص برای i=k که formula_30 نشان میدهیم که formula_31 ضرایب بزواند.


title: الگوریتم تعمیم‌یافته اقلیدس

text: ماتریس زیر را در نظر بگیرید  رابطهٔ بازگشی را به شکل ماتریسی می‌نویسیم  ماتریس formula_34 ماتریس واحد است و دترمینان آن برابر ۱ است. دترمینان ماتریس سمت راست برابر -1 است که نتیجه می‌شود دترمینان formula_35 برابر formula_36 است و برای حالت خاص i=k+1 داریم formula_37 که نشان می‌دهد formula_38 و formula_39 نسبت بهم اولند. رابطهٔ formula_40 که در بالا اثبات شد و لم اقلیدس نشان می‌دهد که formula_38 مقسوم علیه b و formula_39 مقسوم علیه aاند. چون آن‌ها نسبت بهم اولاً بدون در نظر گرفتن علامتشان برابر خارج قسمت تقسیم a و b بر d می‌شوند.


title: الگوریتم تعمیم‌یافته اقلیدس

text: برای یک چندجمله‌ای با ضریب در یک میدان همه چیز مشابه حالت قبل است (تقسیم اقلیدسی، قضیه بزو، و تعمیم الگوریتم اقلیدس). اولین تفاوت در تقسیم اقلیدسی و الگوریتم، جایگذاری formula_43 بجای formula_44 است. بقیه مشابه حالت قبل باقی میماند.  تفاوت دوم در محدودیتی است که بر اندازهٔ ضرایب بزو که از تعمیم الگوریتم اقلیدس به دست میاید وجود دارد، که در مورد چندجمله‌ای دقیق تر است. اگر a و b دو چند جملۀ غیر صفر باشند الگوریتم تعمیم یافته (s,t) را به گونه‌ای به دست میاورد که در شرایط زیر صدق کند:  و   تفاوت سوم در این است که بزرگترین مقسوم علیه مشترک فقط به صورت ضرب یک ثابت غیر صفر تعریف می‌شود. راه‌های مختلفی برای تعریف بزرگترین مقسوم علیه مشترک به صورت غیر مبهم وجود دارد.  در ریاضیات معمولاً به چندجمله‌ای که ب.م.م همهٔ ضریب‌هایش یک هست نیاز است. برای رسیدن به این مقصود کافیست هر خروجی را بر ضریب بزرگترین توان formula_47   تقسیم کنیم. اگر a و b نسبت به هم اول باشند در سمت راست نامساوی بزو یکی ۱ می‌شود، در غیر این صورت یکی ممکن است هر مقدار ثابت غیر صفر شود. در جبر کامپیوتر، چندجمله‌ای معمولاً ضرایب صحیح را می‌پذیرد، و این راه ساده‌سازی بزرگترین مقسوم علیه مشترک برای سهولت تعداد بسیار زیادی بخش ایجاد می‌کند.  راه دوم ساده‌سازی بزرگترین مقسوم علیه مشترک در حالت چندجمله‌ای با ضرایب صحیح تقسیم بر بزرگترین عمل مشترک بین ضرایب formula_48 برای رسیدن به چندجمله‌ای اصلی (یعنی چندجمله‌ای که بزرگترین عامل مشترک ضرایبش ۱ است). اگر چند جمله‌ی‌های ورودی نسبت به هم اول باشند این نرمال‌سازی بزرگترین مقسوم علیه مشترک را یک می‌دهد. اشکال این روش محاسبه، وجود زیر مسئله‌های زیاد است که باید محاسبه و ساده شوند.   روش سوم شامل تعمیم الگوریتم subresultant pseudo-remainder sequences که مشابه تعمیم الگوریتم اقلیدسی به الگوریتم تعمیم یافته‌است. این روش این امکان را فراهم می‌کند که وقتی با چندجمله‌ای با ضرایب صحیح شروع می‌کنیم هر چندجمله‌ای که بدست میاید ضرایبش، صحیح باشد. علاوه بر این هر باقی‌مانده محاسبه شده یک چندجمله‌ای subresultant است. در حالت خاص اگر چند جمله‌ی‌های ورودی نسبت به هم اول باشند آنگاه طبق قضیه بزو می‌شود:   که formula_50 برابر resultant، a,bاست. در این فرم قضیه بزو مقسوم علیه دیده نمی‌شود. اگر همه چیز را بر resultant تقسیم کنیم قضیه کلاسیک بزو بدست می‌آید ، با یک مقسوم علیه مشترک ساده برای اعداد گویایی که در آن ظاهر می‌شوند.  برای پیاده‌سازی الگوریتمی که در بالا ذکر شد،اولاً باید توجه داشت که در هر مرحله تنها نیاز به نگهداری دو مقدار نهایی متغیرهای شاخص‌گذاری شده، هست. بنابراین برای صرفه جویی در حافظه هر متغیر شاخص‌گذاری شده باید با تنها دو متغیر جایگزین شود.  برای راحتی کار در الگوریتم زیر(و بقیهٔ الگوریتم‌ها در این مقاله) از مقداردهی موازی استفاده می‌شود.در زبانهای برنامه نویسی که از مقداردهی موازی پشتیبانی نمی‌کنند، باید اینکار را با کمک یک متغیر کمکی شبیه سازی کرد.


title: الگوریتم تعمیم‌یافته اقلیدس

text: برای مثال


title: الگوریتم تعمیم‌یافته اقلیدس

text: (old_r, r) := (r, old_r - quotient *r)


title: الگوریتم تعمیم‌یافته اقلیدس

text: برابر هست با


title: الگوریتم تعمیم‌یافته اقلیدس

text: prov := r;


title: الگوریتم تعمیم‌یافته اقلیدس

text: و مشابهاً برای بقیهٔ استفاده‌ها از مقداردهی موازی هم باید چنین کاری کرد.که اینکار به کد زیر می انجامد: function extended_gcd(a, b)


title: الگوریتم تعمیم‌یافته اقلیدس

text: باید به این نکته توجه داشت که خارج قسمت‌های a و b در تقسیم بر ب.م.م، که خروجی این الگوریتم هست، ممکن هست علامت نادرستی داشته باشند. رفع این مشکل در انتهای محاسبات بسیار ساده هست، اما در اینجا به دلیل سادگی کد بیان نشده‌است.  مشاب‌ها اگر یکی از دو مقدار a یا b منفی و دیگری صفر باشد، ب.م.م، که خروجی این الگوریتم هست، منفی می‌شود و باید علامت خروجی تغییر کند.


title: الگوریتم تعمیم‌یافته اقلیدس

text: الگوریتم تعمیم یافتهٔ اقلیدس وسیلهٔ اصلی برای محاسبهٔ وارون ضربی در ساختارهای پیمانه‌ای هست و اغلب در حساب پیمانه‌ای اعداد صحیح و تعمیم‌های میادین جبری به کار می‌آید.یک نمونهٔ مهم از مورد آخر میدان‌های متناهی با order غیر اول هست.  اگر n یک عدد صحیح مثبت باشد، حلقهٔ Z/nZ ممکن هست توسط مجموعه {0, 1, ..., n} از باقی‌مانده‌های تقسیم اقلیدسی بر n قابل شناسایی باشد،عمل جمع و ضرب همان محاسبه ی، باقی‌ماندهٔ نتیجهٔ جمع و ضرب اعداد صحیح، بر n هست.یک عضو از Z/nZ یک وارون ضربی دارد(اگر چنین باشد، به آن unit میگویند) اگر نسبت به n اول باشد.در حالت خاص اگر n اول باشد a وارون ضربی دارد،اگر مخالف صفر باشد(باقی‌مانده اش بر n).بنابراین Z/nZ یک میدان هست اگر و تنها اگر n اول باشد.  قضیه بزو بیان می‌کند که a و n نسبت به هم اولند اگر و تنها اگر اعداد صحیحی مانند s و t وجود داشته باشند که  که اگر از دوطرف بر n باقی‌مانده بگیریم:  بنابراین t یا، به‌طور دقیقتر، باقی‌ماندهٔ تقسیم t بر n، همان وارون ضربی a در پیمانهٔ n هست.  برای تطبیق دادن الگوریتم تعمیم یافتهٔ اقلیدس به نحوی که این مسئله را حل کند، باید در نظر داشته باشیم که نیازی به محاسبهٔ ضرایب بزو ی n نیست.همچنین برای اینکه نتیجه مثبت و کمتر از n باشد، باید از این موضوع که t همواره در رابطهٔ |t| شبه کد زیر آورده ایم که در آن n یک عدد صحیح بزرگتر از یک هست.


title: الگوریتم تعمیم‌یافته اقلیدس

text: الگوریتم پیشرفتهٔ اقلیدس همچنین ابزار اصلی برای محاسبهٔ وارون ضربی در تعمیم‌های میدان جبری ساده هست.یک نمونهٔ مهم که به‌طور گسترده‌ای در رمزنگاری و نظریه کدگذاری استفاده می‌شود میدان‌های جبری با اندازه (order) غیر اول هست.


title: الگوریتم تعمیم‌یافته اقلیدس

text: در واقع اگر p یک عدد اول باشد و q = pd، میدان با اندازه(order) q یک تعمیم سادهٔ جبری از میدان اول p عضو ، هست، که توسط یک ریشهٔ معادله چندجمله‌ای کاهش ناپذیر از درجه d ساخته شده‌است.  یک بسط سادهٔ جبری L از یک میدان K که توسط ریشه یک چندجمله‌ای کاهش ناپذیر از درجه d ساخته شده‌است، ممکن است توسط حلقهٔ خارج قسمت‌های formula_53 به‌طور یکتا شناسایی شود، و اعضایش در یک رابطهٔ یک به یک و و پوشا با چندجمله‌ای‌هایی با درجات کمتر از d هستند.عمل جمع در L همان جمع چندجمله‌ای ها است.عمل ضرب در L باقی‌ماندهٔ تقسیم اقلیدسی بر، p حاصلضرب چندجمله ای‌ها است.بنابراین برای تکمیل اعمال حسابی در L تنها کافیست نحوهٔ محاسبهٔ وارون ضربی را تعریف کنیم.که آن با استفاده از الگوریتم تعمیم یافتهٔ اقلیدسی انجام می‌شود.  این الگوریتم بسیار شبیه الگوریتمی است که در بالا برای محاسبهٔ وارون ضربی پیمانه‌ای بیان شده‌است.در اینجا دو تفاوت مهم وجود دارد:اولاً اینکه به خط آخر نیازی نیست، چون ضریب بزو همیشه یک درجه کمتر از d دارد.  دوم اینکه ب.م.م ای که بدست آمده‌است، وقتی که چندجمله‌ای‌های ورودی نسبت به هم اولند، ممکن هست هر عضو غیرصفری از K باشند، بنابراین ضریب بزو (یک چندجمله‌ای با درجهٔ مثبت) باید در وارون این عضو از K ضرب شود.  در شبه کد زیر p یک چندجمله‌ای از درجه بزرگتر از یک هست و a یک چندجمله‌ای هست.علاوه بر این div یک تابع کمکی است که خارج قسمت تقسیم اقلیدسی را حساب می‌کند.


title: الگوریتم تعمیم‌یافته اقلیدس

text: برای مثال اگر چندجمله‌ای که برای تعریف میدان متناهی  GF(28)  بکار میرود p = x8 + x4 + x3 + x + 1 باشد و a = x6 + x4 + x + 1  عضوی باشد که وارونش مطلوب ماست، نتایج اجرای هر مرحله از الگوریتم در جدول زیر مشاهده می‌شود.با توجه به اینکه میدان با order 2n برای هر عضو z عضو -z = z  و z + z = 0را هم دارد.توجه کنید که 1 تنها عضو غیرصفری از GF(2)هست که برایش تغییرات در خط آخر شبه کد مورد نیاز نبوده‌است.  بنابراین وارون مطلوب x7 + x6 + x3 + xهست، و می‌شود با انجام عمل ضرب دو عضو در هم و گرفتن باقی‌مانده بر pبه صحت آن پی برد.


title: الگوریتم تعمیم‌یافته اقلیدس

text: ما می‌توانیم در موردی که تعداد اعداد بیش از دو تا هست، به‌طور پشت سر هم(دو تا باهم و سپس حاصل آن‌ها با عدد بعدی) از این الگوریتم استفاده کنیم.اول باید اثبات کنیم که formula_54.برای این اثبات اگر formula_55باشد،طبق تعریف می‌توان گفت که d مقسوم علیه مشترک a و b هست.بنابراین برای یک مقدار خاص k داریمformula_56 .مشاب‌ها d مقسوم علیه c هم هست، پس برای یک مقدار خاصی ازj formula_57.اگر formula_58 با این تعریف ما از u، formula_59 اما چون d بزرگترین مقسوم علیه هستu وارون ضربی دارد.(unit هست.)  بنابراین اگر formula_60 پس مقادیر x و y وجود دارند به‌طوری‌که formula_61. بنابراین معادلهٔ نهایی به شکل : formula_62 خواهد بود.  پس اگر ما آن را با استقرا روی n عدد انجام دهیم به معادلهٔ زیر میرسیم  که همان چیز مورد انتظار ما هست.


title: فراوانی طبیعی

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


title: انرژی واپاشی

text: انرژی واپاشی عبارت است از انرژی که در حین واپاشی یک ایزوتوپ پرتوزا تولید می‌شود و با واحدهای MeV (مگا الکترون‌ولت) یا KeV (کیلو الکترونولت) گزارش می‌شود.


title: انرژی واپاشی

text: formula_1 formula_2


title: انرژی واپاشی

text: Radioactivity Radionuclides Radiation by Joseph Magill and Jean Galy, Springer Verlag, 2005


title: تقریب پد

text: تقریب پد یا تقریب پاده یا تقریب پده (Padé approximant)، بهترین تقریب یک تابع با یک تابع گویا از مرتبه معین است. با این تکنیک، سری توانی تقریب، با سری توانی تابعی که آن را تقریب می‌زنیم مطابقت دارد. این تکنیک در سال ۱۸۹۰ توسط هنری پد (Henri Padé) توسعه داده شد هرچند معرفی ایده این روش و بررسی ویژگی‌های تقریب یک تابع با یک تابع گویا و ویژگی‌های تقریب کسری سری‌های توانی به فروبنیوس (۱۹۱۷-۱۸۴۹) برمی گردد. اغلب اوقات تقریب پد تقریب بهتری در مقایسه با قطع کردن سری تیلور بدست می‌دهد و حتی وقتی که سری تیلور همگرا نباشد تقریب پد ممکن است کارایی داشته باشد. بر همین اساس، از این تقریب در محاسبات کامپیوتری استفاده می‌شود. همچنین از این تقریبات به عنوان تقریبات کمکی در تقریب دیوفانتی و نظریه اعداد متعالی استفاده شده است.


title: ایندرک پرتلسون

text: ایندرک پرتلسون (زاده ۲۱ آوریل ۱۹۷۱ - تالین) جودوکار اهل کشور استونی است.


title: ایندرک پرتلسون

text: از افتخارات وی میتوان به کسب دو مدال برنز در وزن ۱۰۰ کیلوگرم جودو بازی‌های المپیک ۲۰۰۲ و ۲۰۰۴ و همچنین کسب دو مدال نقره در بازی‌های جهانی جودو در سال‌های ۱۹۹۹ و ۲۰۰۳ اشاره کرد.


title: مسائل جایزه هزاره

text: مسائل جایزه هزاره ۷ مسئله در ریاضیات هستند که توسط انجمن ریاضی کلی در سال ۲۰۰۰ طرح شده‌اند. تا ژانویه سال ۲۰۱۳، ۶ تا از آنها حل نشده باقی مانده‌اند. جواب درست برای هر کدام از سؤالات منجر به جایزه ۱ میلیون دلاری (که با نام "جایزه هزاره" مشهور است) می‌شود که توسط انجمن داده می‌شود. حدس پوانکاره، تنها مسئله‌ای که اخیراً حل شده‌است، توسط گریگوری پرلمان حل شد اما او این جایزه را در سال ۲۰۱۰ نپذیرفت. او گفت «من همهٔ آنچه را که می‌خواهم، در اختیار دارم. من می‌توانم هستی را کنترل کنم؛ پس به من بگویید چرا باید دنبال یک میلیون دلار باشم؟».


title: مسائل جایزه هزاره

text: سؤال این است که آیا برای تمام مسائلی که الگوریتمی می‌تواند درستی یک جواب را بررسی کند (در زمان چند جمله‌ای)، الگوریتمی وجود دارد که بتواند آن جواب را به همان سرعت پیدا کند. الگوریتم اول، دسته‌ای از پرسش‌ها را که NP نامیده می‌شوند توصیف می‌کند و الگوریتم دوم، دستهٔ p را توصیف می‌کند. پرسش اصلی این است که آیا تمام پرسش‌هایی که در مجموعهٔ NP هستند، در مجموعهٔ P هم هستند یا خیر. مسئله P و NP به‌طور عمومی یکی از مهمترین سؤال‌های باز در ریاضیات و علوم نظری رایانه شناخته می‌شود؛ زیرا نتایج و تأثیرات زیادی بر روی مسائل دیگر در ریاضیات، زیست‌شناسی، فلسفه و رمزنگاری دارد (به نتایج اثبات مسئلهٔ P در برابر NP مراجعه کنید).


title: مسائل جایزه هزاره

text: بیشتر ریاضیدانان و دانشمندان علوم کامپیوتر، انتظار دارند که P≠NP باشد.


title: مسائل جایزه هزاره

text: بیان رسمی این مسئله توسط استفن کوک ارائه داده شده‌است.


title: مسائل جایزه هزاره

text: حدس هاج این است که برای چندگوناهای تصویری جبری است، دورهای هاج ترکیب خطی گویای دورهای جبری هستند.


title: مسائل جایزه هزاره

text: گفتار رسمی این مسئله توسط پیر دلین ارائه شده‌است.


title: مسائل جایزه هزاره

text: در توپولوژی، یک کره با سطح دوبعدی با این حقیقت رده‌بندی می‌شود که این فشرده و همبند ساده است. حدس پوانکاره این است که حتی برای بعد بالاتر نیز درست است. مسئله برای تمام بعدهای دیگر حل شده‌است. این حدس نقش محوری در مسئله دسته‌بندی 3-manifolds ایفا می‌کند.


title: مسائل جایزه هزاره

text: گفتار رسمی این مسئله توسط جان میلنور داده شده‌است.


title: مسائل جایزه هزاره

text: اثبات این حدس توسط گریگوری پرلمان در سال ۲۰۰۳ داده شده‌است؛ بازبینی آن در اگوست سال ۲۰۰۶ کامل شد، و پرلمان انتخاب شد تا مدال فیلدز را به خاطر راه حلش دریافت کند اما او نپذیرفت. پرلمان به‌طور رسمی مفتخر به دریافت جایزه هزاره در ۱۸ مارس ۲۰۱۰ شد، ولی باز جایزه مالی انجمن کلی را نپذیرفت زیرا "آژانش خبری اینترفکس" به نقل از پرلمان گفت که بنظرش جایزه ناعادلانه بوده‌است. پرلمان به اینترفکس گفت که به نظرش میزان مشارکتش در حل حدس پوانکاره بیشتر از زحماتی که ریچارد همیلتون، ریاضی‌دان دانشگاه کلمبیا کشیده، نبوده‌است."


title: مسائل جایزه هزاره

text: بنابر حدس ریمان، تمام صفرهای نابدیهی تابع تحلیلی زتای ریمان دارای بخش حقیقی ۱/۲ هستند. اثبات یا رد این مسئله نقش مهمی در نظریه اعداد، و به‌طور ویژه در توزیع اعداد اول دارد. این سؤال، هشتمین سؤال از مسائل هیلبرت بوده، سر مایکل آتیا از حل این مسئله ریاضی خبر داده که در ۱۶۰ سال اخیر راه حلی برای آن یافت نشده‌است. در صورتی که درستی راه حل این ریاضی‌دان انگلیسی به اثبات برسد، وی جایزه یک میلیون دلاری تعیین شده را تصاحب خواهد کرد. هم‌اکنون راه حل یادشده در حال بررسی مقدماتی است.


title: مسائل جایزه هزاره

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


title: مسائل جایزه هزاره

text: در فیزیک، نظریهٔ کلاسیک یانگ - میلز تعمیم نظریه الکترومغناطیس ماکسول است که در آن میدان الکترومغناطیس کرومی خودش حامل بار است. به عنوان یک مسئلهٔ میدان کلاسیک، این سؤال، جواب‌هایی دارد که با سرعت نور حرکت می‌کنند به‌طوری که نسخهٔ کوانتمی این سؤال باید ذرات بدون جرم (گلوئون) را توصیف کند. با این وجود پدیدهٔ بدیهی بهم‌پیوستگی رنگی که فقط حالات محدودی را برای گلوئون‌ها امکان‌پذیر می‌سازد، ذرات سنگینی را تشکیل می‌دهد. این همان شکاف جرم است. نمود دیگر بهم‌پیوستگی، آزادی مجانبی است که باعث می‌شود وجود نظریهٔ کوانتمی یانگ-میلز بدون محدودیت‌های مقیاس‌های کم انرژی امکان‌پذیر باشد. مسئله، معین کردن دقیق وجود نظریهٔ کوانتمی یانگ-میلز و شکاف جرم است.


title: مسائل جایزه هزاره

text: بیان رسمی این مسئله توسط آرتور جاف و ادوارد ویتن ارائه داده شده‌است.


title: مسائل جایزه هزاره

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


title: مسائل جایزه هزاره

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


title: مسائل جایزه هزاره

text: بیان رسمی مسئله توسط اندرو ویلز ارائه داده شده‌است.


title: الگوریتم پی-۱ پولارد

text: الگوریتم p-۱ پولارد یک الگوریتم تجزیه اعداد طبیعی در نظریه اعداد است که توسط سال ۱۹۷۴ ابداع شده‌است. این الگوریتم خاص منظوره است، بدین معنی که تنها مناسب اعداد طبیعی با انواع خاصی از عوامل است؛ این ساده‌ترین مثال از یک است.


title: الگوریتم پی-۱ پولارد

text: عواملی که این الگوریتم پیدا می‌کند، عدد اولی است که عدد ما قبل آن، "p-۱"، یک عدد توان-صاف است؛ مشاهدهٔ ابتدایی این است که با کار در گروه ضربی به یک عدد مرکب مانند "N"، در همهٔ گروه‌های ضربی عوامل اول "N" نیز کار خواهیم کرد.


title: الگوریتم پی-۱ پولارد

text: موجودیت این الگوریتم ما را به سمت مفهوم اعداد اول امن سوق می‌دهد که اعداد اولی هستند مانند "p" که "p-۱" دو برابر یک عدد اول مانند "q" است، بنابراین به صورت حداقلی عددی صاف است. بعضی مواقع این اعداد اول برای اهداف رمزنگاری امن تفسیر می‌شوند ولی ممکن است غیر امن باشند — در توصیه‌های فعلی برای اعداد اول قوی در رمزنگاری، این شرط لازم ولی غیرکافی است که p-۱ حداقل یک عامل اول بزرگ داشته باشد. اکثر اعداد اول به اندازه کافی بزرگ قوی هستند؛ اگر مشخص شود که یک عدد اول استفاده شده در رمزنگاری غیرقوی است، به نظر می‌رسد که بیشتر از روی عمد بوده تا اینکه از تولید اعداد تصادفی باشد. این کلمات فنی در صنعت رمزنگاری کهنه محسوب می‌شوند.


title: الگوریتم پی-۱ پولارد

text: فرض کنید "n" یک عدد مرکب و "p" یکی از عوامل اول آن باشد. از قضیهٔ کوچک فرما ، می‌دانیم که برای هر عدد صحیح مانند "a" که نسبت به "P" اول باشد و برای هر عدد طبیعی "k" داریم:


title: الگوریتم پی-۱ پولارد

text: اگر عدد "x" به پیمانهٔ یکی از عوامل "n" همنهشت با ۱ باشد، آنگاه ب.م. م (x-1,n) بر آن عامل بخش‌پذیر است.


title: الگوریتم پی-۱ پولارد

text: ایده اصلی این است که توان را عددی با تعداد بسیار زیادی عامل اول در نظر بگیریم تا یک مضرب بزرگ از p-۱ شود؛ به‌طور کلی ضرب تمام توان‌هایی از اعداد اول را در نظر می‌گیریم که این توان‌های اول از یک عدد مانند "B" بیشتر نباشند. با یک عدد تصادفی "x" شروع می‌کنیم، و مکرراً آن را با formula_2 جایگزین می‌کنیم که "w" از همان توان‌های اعداد اول بدست می‌آید. در هر مرحله یا اگر ترجیح می‌دهید در مرحلهٔ آخر چک می‌کنیم که آیا ب. م. م ("x-1","n") مخالف ۱ است یا نه.


title: الگوریتم پی-۱ پولارد

text: ممکن است که برای تمام عوامل اول "n" مانند "p-۱"، "p" بر اعداد اول کوچک بخش پذیر باشد که در این صورت الگوریتم "P-۱" پولارد دوباره "n" را برمی‌گرداند.


title: الگوریتم پی-۱ پولارد

text: الگوریتم را می‌توان به صورت زیر نوشت:


title: الگوریتم پی-۱ پولارد

text: ورودی : عدد مرکب "n"


title: الگوریتم پی-۱ پولارد

text: خروجی : یک عامل اول غیر بدیهی از "n" یا عدم موفقیت


title: الگوریتم پی-۱ پولارد

text: اگر در خط ۶، "g" برابر ۱ باشد، آنگاه مشخص می‌شود که تمام عوامل "B", "p-۱-توان-صاف" نبوده‌اند. اگر در خط ۷، "g = n" باشد، معمولاً این نشان می‌دهد که همهٔ عوامل "B-توان-صاف بوده‌اند"، ولی در موارد نادر ممکن است نشانهٔ این باشد که مرتبهٔ "a" به پیمانهٔ "n" کوچک بوده‌است. زمان اجرای این الگوریتم از ( است؛ مقادیر بزرگتر "B" باعث کندی الگوریتم می‌شود ولی با احتمال بیشتری عامل اول را پیدا می‌کند.


title: الگوریتم پی-۱ پولارد

text: از آنجا که الگوریتم افزایشی است، ممکن است به اجرای خود ادامه دهد و کران به‌طور ثابت افزایش یابد. فرض کنید "p-۱" که در آن "p" کوچکترین عامل اول "n" است را بتوان به صورت یک عدد تصادفی کوچکتر از n√ مدل کرد. ازقضیه دیکسون احتمال اینکه بزرگترین عامل اول n کمتر از "p" − ۱)) باشد تقریباً برابر "ε" است، بنابراین به احتمال تقریباً ۱/۲۷ عدد "B" با مقدار "n" یک عامل اول بدست می‌دهد. در عمل وقتی عوامل همگی بزرگ باشند سریع تر از روش p-۱ پولارد است؛ اجرای الگوریتم "p-۱" تا "B" = ۱۰، یک چهارم عوامل ۱۲ رقمی و ۱/۲۷ عوامل ۱۸ رقمی را قبل از روش‌های دیگر پیدا خواهد کرد.


title: الگوریتم پی-۱ پولارد

text: یک نوع دیگر از الگوریتم اصلی بعضی مواقع استفاده می‌شود؛ به جای اینکه نیاز باشد "p-۱" همهٔ عوامل اولش از "B" کمتر باشد، مستلزم این است که که همهٔ عواملش به جز یک عامل از یک عدد "B" کمتر باشند و عامل باقی‌مانده از یک عدد "B" کمتر باشد که . بعد از اتمام مرحله اول که مانند الگوریتم اصلی است، به جای اینکه


title: الگوریتم پی-۱ پولارد

text: " 'M " را برای "B" محاسبه کنیم و ب. م. م را چک کنیم، Q را محاسبه می‌کنیم:


title: الگوریتم پی-۱ پولارد

text: که در آن می‌باشد. همچنین چک می‌کنیم که ب. م. م ("Q", "n") یک عامل اول غیر بدیهی تولید می‌کند یا نه. دقت کنید مانند قبل، عملیات به توان رساندن می‌تواند به پیمانهٔ "n" باشد.


title: الگوریتم پی-۱ پولارد

text: فرض کنید { … ,"q", "q"} اعداد اول متوالی در بازهٔ باشند و "d" = "q" − "q" فاصلهٔ دو عدد اول پشت سرهم باشد. به‌طور معمول و اعداد زوج هستند. توزیع اعداد اول به گونه‌ای است که "d" همیشه نسبتاً کوچک خواهد بود. پیشنهاد می‌شود که ; بنابراین مقادیر ، ، ، … به پیمانهٔ n را می‌توان در یک جدول ذخیره کرد و را می‌توان از محاسبه کرد که این کار نیاز به توان رساندن را کم خواهد کرد.


title: محمدجواد جعفرپور

text: محمدجواد جعفرپور (زادهٔ ۱۶ مهر ۱۳۷۷ در تهران) بازیگر ایرانی است. وی از کودکی و با بازی در فیلم به همین سادگی (فیلم) ساخته رضا میرکریمی به سینما راه پیدا کرد. او در فیلمهایی چون شکارچی شنبه، با افرادی چون پرویز شیخ‌طادی و علی نصیریان و در نارنجی‌پوش با افرادی چون داریوش مهرجویی، حامد بهداد، لیلا حاتمی و میترا حجار همکاری داشته‌است. جعفر پور در فیلم‌هایی همچون به همین سادگی، ۱۲ روز، فقط بیست و مجموعه تلویزیونی امروز، فردا نیز نقش آفرینی کرده‌است. وی تاکنون توانسته در چندین جشنواره از جمله در بیست‌وسومین و بیست‌وچهارمین دورهٔ جشنوارهٔ فیلم کودک و نوجوان همدان، پروانهٔ زرین بهترین بازیگرکودک را به دست آورد.


title: هتل بین‌المللی تهران

text: هتل بین‌المللی تهران یا هتل اینترنشنال تهران نام هتل ۵ ستاره‌ای بود که در ضلع جنوب شرقی سیدخندان قرار داشت. این هتل که به‌نام هتل سیدخندان هم شناخته می‌شد، در سال ۱۳۵۶ و در زمینی به مساحت ۱۳ هزار متر مربع و زیربنای ۳۶ هزار مترمربع افتتاح شده بود. این هتل از مجلل‌ترین و پرامکانات‌ترین هتل‌های ایران بود. با وقوع انقلاب، این هتل توسط برخی انقلابیون تسخیر شد و سپس و در جریان مصادره‌های ابتدای انقلاب، مصادره شد. پس از مصادره به عنوان محلی برای مهاجران جنگی استفاده شد و از دهه هفتاد به بعد تبدیل به ساختمانی متروکه و پارکینگ شد. زمین این هتل به شرکت مخابرات داده شده است و در سال ۱۳۸۶ به شکل کامل ساختمان هتل تخریب شد. در حال حاضر مجتمع اداری- تجاری- اقامتی شرکت مخابرات ایران در زمینی به مساحت تقریبی ۹۵۰۰ متر مربع و در محل سابق هتل اینترنشنال در حال ساخت است.


title: هتل بین‌المللی تهران

text: اپیزود هفدهم رادیونیست به تاریخچه هتل اینترنشنال قبل و بعد از انقلاب می‌پردازد.


title: هتل بین‌المللی تهران

text: کار ساخت هتل اینترنشنال تهران در اواسط دهه ۱۳۴۰ خورشیدی آغاز شد و آغاز ساخت فاز اول هتل اینترنشنال در سال ۱۳۴۶ و در گلوگاه گذر مسافران و زائرانی که به قصد زیارت امامزاده صالح از جاده قدیم شمیران راهی میدان تجریش می‌شدند، شروع شد. هتل اینترنشنال تهران که متعلق به نادر باتمانقلیچ بود، بیشتر به قصد اسکان رجال و کارمندان متمول و سرشناس دولت که در شهرستان‌ها اقامت داشتند و به قصد سیاحت یا زیارت به تهران می‌آمدند، بنا شد. کار ساخت هتل اینترنشنال تهران در مساحتی نزدیک به ۴ هکتار با ۸۵۰ اتاق، ۴ سالن اجتماعات به همراه یک مجموعه ورزشی و ۳ آسانسور که از عمارت، هتلی ۵ ستاره می‌ساخت، سرانجام در سال ۱۳۵۶ خورشیدی به پایان رسید. این در حالی است که در آن سال‌ها پایتخت، شاهد حضور نمایندگان هتل‌های زنجیره‌ای بین‌المللی و ساخت چندین هتل ۵ یا ۴ ستاره بین‌المللی بود. هتل اینترنشنال تهران به عنوان رقیبی قدرتمند برای جذب گردشگر و مسافر با شعب هتل‌های بین‌المللی خودنمایی می‌کرد. هتل اینترنشنال فعالیت خود را تا انقلاب ۵۷ ادامه داد. این هتل تا روزگاری که رونق داشت، درآمد بسیار خوبی نیز کسب می‌کرد.


title: هتل بین‌المللی تهران

text: پس از انقلاب و تغییر و تحولات آن سال‌ها، ساختمان بدون مدیر هتل از سوی گروهی از دانشجویان دانشگاه علم و صنعت ایران مصادره می‌شود و با تبدیل شدن به خوابگاه به ناگهان تغییر کاربری می‌دهد. چندی بعد پرسنل نیروی دریایی هم همین استفاده را از هتل بردند، تا اینکه در اوایل دهه ۱۳۶۰ و درست در کوران جنگ ایران و عراق، هتل به صورت قطعی مصادره می‌شود و در اختیار بنیاد آسیب دیدگان جنگ قرار می‌گیرد. بدین سان آخرین کسانی که میهمان ناخوانده هتل اینترنشنال تهران شدند، حدود ۶۵۰ خانواده مهاجر جنگی بودند که از سال ۱۳۶۲ تا اوایل دهه ۷۰ یعنی چند سال پس از پذیرش قطعنامه ۵۹۸ در آنجا زندگی می‌کردند. زندگی این مهاجران جنگی در این مجتمع را ناصر غلامرضایی در فیلم حریم مهرورزی و همچنین قاضی ربیحاوی در کتاب "از این مکان" روایت کرده‌اند. فیلم آبادانی‌ها کیانوش عیاری (۱۳۷۱) نیز در همین مجتمع می‌گذرد. تأسیسات زیربنایی هتل، هر روز مستهلک تر از روز قبل می‌شد و در غفلت جمعی، بسیاری از اشیا و قطعات با ارزش تأسیساتی آن، مورد دستبرد قرار می‌گرفت. سال‌ها به همین منوال گذشت تا اینکه در سال ۱۳۷۲، تشکیلات مهاجران جنگی که آن زمان سرپرستی بقایای هتل اینترنشنال سابق را بر عهده داشت، با پرداخت حدود ۷۰ میلیون تومان به ۴۸۰ خانواده‌ای که از زمان جنگ در هتل باقی مانده بودند، هتل را به‌طور کامل خالی کرد. از این پس، اتاق‌های هتل اینترنشنال به محل امنی برای معتادان، بزهکاران و افراد فاسد تبدیل شد. در سال ۱۳۷۹، هتل اینترنشنال تهران را به شکل قطعی و به مبلغ یک میلیارد و ۲۰۰ میلیون تومان به وزارت پست و تلگراف و تلفن سابق منتقل شد و تا مدت‌ها به حال خود رها شد. سرانجام شرکت مخابرات ایران در سال ۱۳۸۶ این هتل را با صرف هزینه‌ای در حدود ۷۰۰ میلیون تومان تخریب کرد و کار ساخت مجتمع شرکت مخابرات ایران را در همان محل آغاز کرد.


title: هتل بین‌المللی تهران

text: در حال حاضر ساخت مجتمع اداری- تجاری- اقامتی شرکت مخابرات ایران که در زمینی به مساحت تقریبی ۹۵۰۰ متر مربع و در محل سابق هتل اینترنشنال قرار دارد در حال انجام است. فضای اداری با ۴۰هزار مترمربع که در یک برج ۲۵ طبقه قرار گرفته‌است بزرگ‌ترین کاربری این مجتمع را تشکیل می‌دهد. در کنار این برج اداری، یک هتل هشت طبقه با زیربنای ۱۴هزار متر مربع قرار گرفته و مجموعه تجاری نیز با زیربنای ۱۱هزار مترمربع کل فضای طبقات پایین مجموعه را اشغال کرده‌است.


title: فهرست استانداران فارس

text: این فهرست اسامی استانداران استان فارس (از سال تشکیل استان تاکنون) می‌باشد:


title: فهرست استانداران فارس

text: استان فارس یکی از استان‌های ایران است که در بخش جنوب این کشور واقع شده‌است. این استان با مساحتی در حدود ۱۲۲٬۶۰۸ کیلومتر مربع، چهارمین استان بزرگ ایران و با جمعیتی معادل ۴٬۸۵۱٬۲۷۴ تن، بر طبق برآورد جمعیتی سال ۱۳۹۵ خورشیدی مرکز آمار ایران، چهارمین استان پرجمعیت ایران به‌شمار می‌رود. بر اساس تقسیمات کشوری سال ۱۳۹۹ خورشیدی، استان فارس به ۳۶ شهرستان، ۹۴ بخش و ۱۱۴ شهر تقسیم شده‌است. مرکز استان فارس، کلانشهر شیراز است


title: فرانسیس بیکن (نقاش)

text: فرانسیس بیکن (زاده ۲۸ اکتبر ۱۹۰۹ – مرگ ۲۸ آوریل ۱۹۹۲) یکی از نقاش‌های نامی اکسپرسیونیست سده بیستم بود. این هنرمند ایرلندی بیشتر شهرت خود را مدیون از شکل‌افتادگی‌های خشنی است که در بدن و چهره‌های شخصیت‌های نقاشی‌هایش ایجاد می‌کرد. بیکن را نقاش بحران انسان پس از جنگ جهانی دوم نامیده‌اند.


title: فرانسیس بیکن (نقاش)

text: او در سال ۱۹۰۹در دوبلین (جمهوری ایرلند) به دنیا آمد. مادرش از خانواده‌ای ثروتمند برمی‌خاست و پدرش دریانورد بود اما سپس به پرورش اسب روی آورد. به دلایل متفاوتی، از جمله ابتلا به بیماری آسم و علاقه‌اش به همجنس خود، بیکن دوران کودکی‌اش را با سختی و تقلا سپری کرد. هفده ساله بود که از خانواده‌اش جدا شد و به لندن رفت.


title: فرانسیس بیکن (نقاش)

text: در دوران جنگ به دلیل بیماری‌اش از سربازی معاف شد. در دهه پنجاه با پیتر لیسی آشنا شد و در نقاشی‌هایش مضامین مرتبط با همجنس‌گرایی با تأثیر از صحنه‌های کُشتی عکس‌های ادوارد مایبریج پدیدار گردید. در سال ۱۹۵۴ به همراه بن نیکلسن، یک چهره برجسته هنر انتزاعی انگلیس، به بینال ونیز فرستاده شد.


title: فرانسیس بیکن (نقاش)

text: در سال ۱۹۶۱ کارگاه کوچک اما مشهوری را خرید که تا آخر عمر به عنوان فضای اصلی آفرینش هنری او عمل کرد. در همین زمان بود که نخستین مصاحبه‌اش را با دیوید سیلوستر انجام داد؛ مصاحبه‌ای که اکنون به عنوان یکی از منابع مهم زندگی‌نامه و اندیشه‌های بیکن تلقی می‌شود.


title: فرانسیس بیکن (نقاش)

text: در دهه شصت و هفتاد شهرت جهانی فرنسیس بیکن با برپایی نمایشگاه‌هایی در موزه‌های نامی جهان از جمله موزه گوگنهایم نیویورک و گرَن پَله تثبیت شد و رو به گسترش گذاشت. درست یک شب پیش از برگزاری یکی از همین نمایشگاه‌ها، جورج دایر، شریک زندگی بیکن در آن زمان دست به خودکشی زد. بیکن در ۲۸ آوریل سال ۱۹۹۲، به دلیل ناراحتی تنفسی‌اش درگذشت.


title: فرانسیس بیکن (نقاش)

text: نقاشی‌های بیکن با اقبال بازار هنر نیز رو به رو شده‌اند. در سال ۲۰۱۳ او لقب گران‌ترین هنرمندی که کارش در یک حراجی فروخته شده را از آن خود کرد. نقاشیِ «سه مطالعه بر لوسین فروید» به مبلغ ۱۴۲ میلیون دلار در خانه حراج کریستیز به فروش رفت تا رکورد تازه‌ای در اقتصاد هنر جهان رقم بخورد.


title: فرانسیس بیکن (نقاش)

text: نخستین نقاشی‌های بیکن نشان‌دهنده تاثیرپذیری هنرمند از پابلو پیکاسو، هنرمند برجسته کوبیست اسپانیایی، و نیز مکتب سوررئالیسم است که در دهه ۱۹۲۰ پدیدار شده بود. اما بیکن پس از جنگ جهانی دوم تقریباً همه آثار نخستین خود را از میان بُرد و اکنون آگاهی زیادی از دوره نخست فعالیت هنری او در دست نیست.


title: فرانسیس بیکن (نقاش)

text: یکی از مشهورترین نقاشی‌های بیکن با نام «سه مطالعه بر پیکره‌های پای صلیب» (حدود ۱۹۴۴) گاه به عنوان مهم‌ترین نقاشی اوج دوران حرفه‌ای هنرمند تلقی می‌شود. در این نقاشی سه لتی (یا سه بخشی)، موجوداتی نیمه‌انسان و نیمه‌حیوان را می‌بینیم که در وضعیتی شبیه به شکنجه اسیر شده و نعره می‌زنند. پیکرهای نقاشی‌های بیکن، مانند شخصیت‌های ادبیات اگزیستانسیالیسم، اغلب تنها و مسخ شده‌اند. این نقاشی، تصویر گویایی بود از اروپای پس از جنگ جهانی دوم.


title: فرانسیس بیکن (نقاش)

text: بیکن، در این دوره از سینما و عکاسی، به‌ویژه عکس‌های مجله‌های پزشکی، به عنوان منبع الهام اولیه برای نقاشی‌هایش استفاده می‌کند. او این تصویرها را کارگاهش می‌انباشت و از آن‌ها به عنوان منابع تصویری بسیاری از نقاشی‌هایش استفاده می‌کرد. به نظر او «به‌هم‌ریختگی در اطراف ما تا حدودی شبیه ذهن ماست. این می‌تواند تصویر خوبی از آنچه در من می‌گذرد باشد، درون من به این شکل است، زندگی من شبیه این است. به‌عبارتی: من در بی‌نظمی بهتر کار می‌کنم… بی‌نظمی تصویرها را برایم می‌پروراند».


title: آزمون اول بودن ای‌کی‌اس

text: آزمون اول بودن AKS (که همچنین به نام‌های آزمون اول بودن Agrawal-Kayal-Saxena و آزمون دایره بری AKS شناخته می‌شود) یک الگوریتم قطعی برای اثبات اول بودن یا نبودن اعداد طبیعی می‌باشد که توسط مانیندرا آرگاوال، نیراج کایال و نیتین ساکسنا –پژوهشگران علوم رایانه در موسسه هندی فناوری کانپور- در تاریخ ۶ اوت ۲۰۰۲ در مقاله‌ای با عنوان“prime is in P” منتشر شد. الگوریتم در زمان با پیچیدگی چندجمله‌ای می‌تواند تشخیص دهد که یک عدد اول یا مرکب است. در سال ۲۰۰۶ نویسندگان به خاطر نگارش این مقاله موفق به کسب جایزه گودل و جایزه فالکرسون شدند.


title: آزمون اول بودن ای‌کی‌اس

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


title: آزمون اول بودن ای‌کی‌اس

text: پایهٔ آزمون ای‌کی‌اس بر مبنای قضیه زیر است:


title: آزمون اول بودن ای‌کی‌اس

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


title: آزمون اول بودن ای‌کی‌اس

text: معادلهٔ (۱) که در بالا آورده‌ایم خود می‌تواند به عنوان آزمونی برای تشخیص اول بودن اعداد به کار رود اما مشکل آن در زمان اجرا است که از پیچیدگی زمانی نمایی می‌باشد. بنابراین برای کاهش پیچیدگی زمانی الگوریتم ای‌کی‌اس از معادلات همنهشتی زیر استفاده می‌کند:


title: آزمون اول بودن ای‌کی‌اس

text: که معادل است با:


title: آزمون اول بودن ای‌کی‌اس

text: که در آن f و g چندجمله‌ای‌های دلخواه می‌باشند. معادلهٔ همنهشتی بالا در زمان چندجمله‌ای بر حسب تعداد ارقام عدد n می‌تواند بررسی شود زیرا می‌توان ثابت کرد که کافی است r با n نسبت لگاریتمی داشته باشد. دقت کنید که تمامی اعداد اول در این معادله صدق می‌کنند (می‌توان در رابطهٔ (۳) به جای g چندجمله‌ای ثابت متحد با صفر را قرار داد و به رابطه (۱) رسید که برای n اول درست می‌باشد.) ولی بعضی از اعداد مرکب نیز در رابطهٔ (۳) صدق می‌کنند. نکتهٔ مهم در اثبات قضیه ای‌کی‌اس این است که به گونه‌ای عددی کوچک برای r و یک مجموعهٔ کوچک از اعداد طبیعی مثل A انتخاب می‌کند که اگر همنهشتی بالا برای r و تمامی aهای عضو A برقرار باشد انگاه n باید اول باشد.


title: آزمون اول بودن ای‌کی‌اس

text: در نسخهٔ اولیهٔ مقالهٔ بالا، نویسندگان توانستند اثبات کنند که پیچیدگی زمانی الگوریتم Õformula_6 می‌باشد.


title: آزمون اول بودن ای‌کی‌اس

text: به زبان دیگر الگوریتم بالا زمانی کمتر از لگاریتم تعداد ارقام ورودی به توان ۱۲ در یک عدد ثابت می‌باشد. اما این کران بالایی که در مقاله به دست آمده بود خیلی کران بالای مناسبی نبود، در واقع اگر حدس سوفی ژرمن در رابطه با توزیع اعداد اول را فرض کنیم آنگاه کران بالای داده شده را می‌توان تا Õformula_7 کاهش داد.


title: آزمون اول بودن ای‌کی‌اس

text: طی چند ماه پس از انتشار مقالهٔ فوق چندین مدل دیگر برای این الگوریتم داده شد که سرعت اجرای الگوریتم را از نظر اندازهٔ ضریب ثابت بهبود بخشید (نه از لحاظ مرتبهٔ زمانی). با توجه به وجود مدل‌های فراوان از الگوریتم AKS، Crandall و Papadopoulos در مقالهٔ خود با عنوان «در باب اجرای آزمون‌های اول بودن رده ای‌کی‌اس» که در مارس سال ۲۰۰۳ منتشر شد از الگوریتم‌های بالا با عنوان «کلاس ای‌کی‌اس» استفاده کرده‌اند.


title: آزمون اول بودن ای‌کی‌اس

text: به علت وجود مدل‌های جدید از الگوریتم ای‌کی‌اس و به علت وجود برخی بازخوردها از الگوریتم، نسخهٔ جدیدی از “Pimes is in P” با صورت‌بندی جدید از الگوریتم و اثباتی جدید از الگوریتم منتشر شد. (این نسخهٔ جدید در «سال‌نگاشت ریاضیات» منتشر شده‌است). در نسخهٔ جدید ایدهٔ کلی الگوریتم بدون تغییر باقی ماند و تغییر در نحوهٔ انتخاب r بوده و همچنین اثبات منسجم تری برای الگوریتم ارائه شد. اثبات قبلی الگوریتم از بر پایهٔ روش‌های متفاوتی بوده در اثبات جدید ایدهٔ اصلی که تقریباً تمامی کاراثبات را انجام می‌دهد بر پایه استفاده از چندجمله ای‌های دایره بر روی میدان‌های متناهی می‌باشد. همچنین در نسخهٔ جدید کران بالای الگوریتم به Õformula_8 کاهش یافت. با استفاده از نتایجی از قضیهٔ sieve می‌توان این الگوریتم را حتی تا Õformula_9 کاهش داد.


title: آزمون اول بودن ای‌کی‌اس

text: در سال ۲۰۰۵ Carl Pomerance و H.W.Lenstra,JR موفق شدند با ارایهٔ مدل جدیدی از الگوریتم AKS مرتبهٔ زمانی اجرای الگوریتم را تا Õ(log("n")) کاهش دهند.


title: آزمون اول بودن ای‌کی‌اس

text: همچنین Agarwal,Kayalو Saxena مدلی جدید از الگوریتم را پیشنهاد دادند که دارای مرتبهٔ زمانی Õformula_10 می‌باشد که بر پایهٔ حدسی از Bhattacharjee و Pandey که در سال 2002 بیان شد مبتنی است. اما تحلیل‌هایی که هندریک لنسترا و کارل پامرنس بر روی این حدس انجام داده‌اند نشان می‌دهد که به احتمال زیاد این حدس اشتباه می‌باشد.


title: آزمون اول بودن ای‌کی‌اس

text: ۰-عدد n>۱ را به عنوان ورودی وارد کن.


title: آزمون اول بودن ای‌کی‌اس

text: ۱-اگر به ازای a>۱و b>۱ ای طبیعی داشته باشیم n=a^b انگاه چاپ کنn مرکب است.


title: آزمون اول بودن ای‌کی‌اس

text: ۲-کوچک‌ترین عدد r را بیابید که o_r (n)>〖(log〖n)〗〗^۲


title: آزمون اول بودن ای‌کی‌اس

text: ۳-اگر ۱


title: جنبش استقلال‌طلبی هند

text: جنبش استقلال‌طلبی هند، سلسله‌ای از انقلابات بود که توسط مردم هندوستان و در جنگ با امپراتوری بریتانیا بر سر استقلال سیاسی هند صورت گرفت. جنبش از شورش ۱۸۵۷ میلادی شروع شد و در اواسط دههٔ ۴۰ میلادی با «جنبش خروج از هند» به رهبری مهاتما گاندی و تسخیر هند بریتانیا توسط ارتش ملی هند به رهبری سوبهاش چاندرا بوز اوج گرفت. آزادی نهایی بالاخره در ۱۵ اوت ۱۹۴۷ میلادی ممکن شد.


title: جنبش استقلال‌طلبی هند

text: مبارزات این جنبش با بسیاری از وقایع تاریخی و یگانه شناخته می‌شود. برای مثال اولین و بزرگ‌ترین مقاومت غیرخشونت‌آمیز توده‌ای که در آن ۵۰ میلیون نفر از ۱۹۱۸ میلادی تا ۱۹۴۵ میلادی به رهبری مهاتما گاندی شرکت کردند.


title: جنبش استقلال‌طلبی هند

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


title: جنبش استقلال‌طلبی هند

text: در طول چهل و پنج سال اول قرن نوزدهم، رام موهان روی آموزش و پرورش مدرن را به مردم هند معرفی کرد. سوامی ویوکاناندا توانست فرهنگ غنی هند را در پایان قرن نوزدهم به غرب بشناساند. بسیاری از رهبران سیاسی کشور در قرن ۱۹ و بیست همچون مهاتما گاندی و سوبهاس چاندرا بوس از آموزه‌های سوامی ویوکاناندا متأثر بوده‌اند. بنابر اظهارات سوبهاس چاندار بوس که مهم‌ترین طرفدار مبارزه مسلحانه برای استقلال هند بود، سوامی ویوکاناندا " خالق هند مدرن " بود و مهاتما گاندی در مورد وی می‌گوید که تأثیر آموزه‌های سوامی، عشق او (گاندی) را به کشورش هزار برابر کرده‌است. نوشته‌های او الهام بخش نسلی بود که برای آزادی می‌جنگیدند. سال‌ها بعد از مرگ سری اوروبیندو، رابیندرانات تاگور به نویسنده بزرگ فرانسوی رومن رولان گفت " اگر می‌خواهید هند را به درستی بشناسید، نوشته‌های ویوکاناندا رو مطالعه کنید در آن‌ها همه چیز مثبت است و هیچ چیزی منفی وجود ندارد".