Payamvdn/NorthPersian_fa_wiki huggingface dataset:
زیرا به اقرار بسیاری ویل ریاضی دان دهه های چهل و پنجاه میلادی بود که در شاخه های مختلف ریاضی نظری وارد شد و در گسترش آن ها اهمیت داشت و به بهترین نحو نقش هیلبرت را در آن برهه از زمان بازی کرد. پال اردوش به خاطر طرح صدها بلکه هزاران سؤال ریاضی مشهور است. بعضی از سؤالات وی عمیق هستند. اردوش برای مسائلش بسته به سختی پیش بینی شده اش جایزه ای در نظر می گرفت. پایان هزارهٔ دوم که مصادف با صدمین سالگرد انتشار مسائل هیلبرت بود زمان طبیعی مناسبی برای ارائهٔ مجموعهٔ جدید مسائل هیلبرت به شمار می رفت. چند تن از ریاضی دانان از جمله استیو اسمیل، برندهٔ مدال فیلدز درخواست ولادیمیر آرنولد را پذیرفت و لیستی شامل ۱۸ مسئله را پیشنهاد داد. جامعهٔ ریاضی اقبال چندانی به مسائل اسمیل نشان نداد و هنوز روشن نیست این مسائل چقدر مورد توجه ریاضی دانان قرار گیرند. حداقل در جریان اصلی جامعه متناظر مسائل هیلبرت برای قرن بیست ویکم لیستی از هفت مسئله جایزهٔ هزاره است که توسط مؤسسهٔ ریاضی کلِی در سال ۲۰۰۰ انتخاب شدند. برخلاف مسائل هیلبرت که جایزهٔ اصلی آن ها تحسین هیلبرت و جامعهٔ ریاضی بود، هر سؤال به اندازهٔ یک میلیون دلار جایزه دارد. مانند س
ؤالات هیلبرت یکی از مسائل جایزه هزاره (حدس پوانکاره) نیز تقریباً با فاصلهٔ اندکی از زمان انتشار حل شد. حدس ریمان که هم در هر سه لیست هیلبرت، اسمیل و جایزهٔ هزاره -حتی شبیه هندسه ای آن در حدس های ویل- آمده است. از چنان اهمیتی برخوردار است که هنوز هم ریاضی دانان با آن درگیر هستند و بسیاری از متخصصین عقیده دارند که این مسئله تا قرن ها در لیست مسائل خواهد آمد. هیلبرت خود اعلام کرده: "اگر از یک خواب هزاران ساله بیدار شوم اولین سؤالم این خواهد بود که آیا حدس ریمان اثبات شده است؟" در سال ۲۰۰۸ دارپا لیست ۲۳تایی خود از مسائل ریاضی را اعلام کرد و امید داشت که این لیست به پیشرفت های بزرگی در ریاضیات منجر شود. «در نتیجه توانایی های علمی و فنی دپارتمان دفاعی را تقویت می کند.» خلاصه. برای مسائل ۳، ۷، ۱۰، ۱۱، ۱۳، ۱۴، ۱۷، ۱۹، ۲۰و ۲۱ که به صورت واضحی فرموله شده اند، راه حل هایی پیدا شده اند که توسط اجتماع ریاضی قبول شده اند؛ ولی برای مسائل ۱، ۲، ۵، ۹، ۱۵، ۱۸+و ۲۲ راه حل هایی وجود دارد که مورد پذیرش بخشی قرار گرفته اند البته بحث هایی وجود دارد که آیا آن راه حل ها مسائل را حل کرده اند یا نه. علامت + در بالای ۱۸ برای این است که
راه حل حدس کپلر یک اثبات به کمک کامپیوتر است. اشاره ای نامربوط و تا حدی بحث برانگیز به مسئلهٔ هیلبرت، به خاطر این که خواننده انسانی نمی تواند در زمانی منطقی اثباتی برای آن بیابد. سؤالات ۱۶، ۸ (حدس ریمان) و ۱۲ حل نشده اند. در این طبقه بندی سؤالات ۴، ۱۶ و ۲۳ به اندازه ای مبهم هستند که حل شده محسوب می شوند. مسئلهٔ ۲۴ که بعداً ارائه شد نیز در این دسته قرار می گیرد. سؤال ۶ نیز بیشتر سؤالی فیزیکی محسوب می شود تا ریاضی. مسائل هیلبرت. ۲۳ مسئلهٔ هیلبرت به شرح زیر است:
چاردرخت یک داده ساختار درختی است که در آن هر گره داخلی دقیقاً چهار فرزند دارد. این داده ساختار معمولاً برای افراز یک فضای دوبعدی به صورت بازگشتی به تعدادی ناحیه (چارک) استفاده می شود. این ناحیه ها ممکن است مربع، مستطیل یا به هر شکل دیگری باشند. در سال ۱۹۷۴، Raphael Finkel و J.L. Bentley این داده ساختار را quadtree نامیدند. چنین افرازی Q-tree نیز خوانده می شود. همه انواع چاردرخت، در تعدادی ویژگی مشترکند: انواع. چاردرخت ها را می توان بر اساس نوع داده ای که نمایش می دهند (مثل سطح، نقطه، خط یا منحنی) تقسیم بندی کرد. یک نحوه دیگر تقسیم بندی بر این اساس است که آیا شکل درخت ایجادشده مستقل از ترتیب پردازش داده ها است یا خیر. تعدادی از چاردرخت های متداول عبارتند از: چاردرخت ناحیه ای. این نوع چاردرخت، نمایشگر افرازی از یک صفحه دوبعدی است که در آن افراز، صفحه دوبعدی به چهار ناحیه برابر افراز شده و برخی ناحیه ها خود به چهار زیرناحیه برابر افراز شده اند و به همین ترتیب فرایند افراز می تواند ادامه پیدا کند. در چنین افرازی، هر گره، یا چهار فرزند دارد یا فرزندی ندارد (برگ است). هر برگ از درخت مربوط به یکی از زیر ناحیه های اف
راز است و اطلاعات آن زیرناحیه در آن برگ ذخیره می شود. چاردرخت ناحیه ای یک نوع ترای است. می توان از یک چاردرخت ناحیه ای با ارتفاع n برای نمایش یک تصویر با ابعاد 2n × 2n پیکسل (که مقدار هر پیکسل ۰ یا ۱ است) استفاده کرد. ریشه درخت، نمایشگر کل تصویر است. هر ناحیه ای که مقدار همه پیکسل هایش با هم برابر نیست، به ۴ زیرناحیه تقسیم می شود. در نهایت هر برگ از درخت، مجموعه ای مربع شکل از تعدادی پیکسل را نشان می دهد که همگی ۰ یا همگی ۱ هستند. اگر چاردرخت ناحیه ای برای نمایش مجموعه ای از نقاط (مثلاً تعدادی شهر که با طول و عرض جغرافیایی مشخص شده اند) استفاده شود، ناحیه ها تا جایی تقسیم می شوند که هر زیرناحیه حداکثر یک نقطه را شامل شود. چاردرخت نقطه ای. چاردرخت نقطه ای تعمیمی از درخت دودویی است. از یک درخت دودویی می توان برای ذخیره تعدادی عدد (از فضای یک بعدی) استفاده کرد. ولی از چاردرخت نقطه ای می توان برای ذخیره تعدادی نقطه (دوتایی مرتب) از فضای دوبعدی استفاده کرد. این درخت، همه ویژگی های چاردرخت را دارد و یک درخت واقعی است. یعنی گره های درخت، خود نقاطی هستند که می خواهیم نمایش دهیم (برخلاف چاردرخت ناحیه ای، وقتی که برای
نمایش تعدادی نقطه مورد استفاده قرار بگیرد). شکل ناحیه های ایجاد شده به ترتیب اضافه کردن نقاط بستگی دارد (درست مثل درخت دودویی جستجو). چاردرخت نقطه ای، معمولاً برای مقایسه بین مجموعه ای از نقاط در صفحه دوبعدی بسیار بهینه (معمولاً از O(log n)) عمل می کند. ساختار گره ها در یک چاردرخت نقطه ای. در یک چاردرخت نقطه ای، گره ها مشابه گره های درخت دودویی هستند. با این تفاوت که در این جا هر گره به جای دو اشاره گر «راست» و «چپ» درخت دودویی، چهار اشاره گر دارد (به ازای هر زیرناحیه یک اشاره گر). همچنین کلید عناصر ذخیره شده به دو قسمت تقسیم می شود (نشان دهنده طول و عرض نقاط). با این توضیحات، در هر گره از درخت این اطلاعات وجود دارد: چاردرخت یالی. این چاردرخت برای ذخیره خط و منحنی (به جای نقطه) استفاده می شود. یک منحنی با تقسیمات زیاد ناحیه ها تقریب زده می شود. این کار ممکن است باعث شود که یک درخت بسیار نامتوازن ایجاد شود که با هدف کاراتر شدن دسترسی ها تناقض دارد. چاردرخت نقشه چندضلعی. این چاردرخت (PMQuadtree) نوعی چاردرخت است که برای ذخیره مجموعه ای از چندضلعی ها استفاده می شود که ممکن است تبه گون باشند (یعنی یک ضلع مجزا یا
یک رأس مجزا در میانشان باشد). سه رده اصلی از PMQuadtree ها وجود دارد که به خاطر نوع داده هایی که در گره های سیاه ذخیره می شود تفاوت دارند. چاردرخت PM3 می تواند تعدادی ضلع نامتقاطع و حداکثر یک نقطه را ذخیره کند. چاردرخت PM2 همانند PM3 است با این تفاوت که همه ضلع ها باید نقطه پایانی یکسان داشته باشند. چاردرخت PM1 نیز شبیه PM2 است. ولی گره های سیاه می توانند یک نقطه و ضلع های متصل به آن یا فقط تعدادی ضلع که در یک نقطه مشترک هستند را در خود ذخیره کنند، ولی نمی توان یک نقطه و تعدادی ضلع که در آن نقطه مشترک نیستند را در گره ذخیره کرد. کاربردهای دیگر. چاردرخت، معادل دوبعدی هشت درخت است. شبه کد. این شبه کد، روشی برای پیاده سازی یک چاردرخت است که فقط نقاط را ذخیره می کند. پیاده سازی های دیگری نیز برای این کار وجود دارد. مقدمات. در این پیاده سازی، از این ساختارها استفاده شده است: // Simple coordinate object to represent points and vectors struct XY float x; float y; // Axis-aligned bounding box with half dimension and center struct AABB XY center; XY halfDimension; کلاس چاردرخت. این کلاس، ریشه یک چاردرخت را (که کل چارد
رخت را مشخص می کند) ذخیره می کند. class QuadTree // Arbitrary constant to indicate how many elements can be stored in this quad tree node constant int QT_NODE_CAPACITY = 4; // Axis-aligned bounding box stored as a center with half-dimensions // to represent the boundaries of this quad tree AABB boundary; // Points in this quad tree node Array of XY [size = QT_NODE_CAPACITY] points; // Children QuadTree* northWest; QuadTree* northEast; QuadTree* southWest; QuadTree* southEast; // Methods function subdivide() {...} // create four children which fully divide this quad into four quads of equal area درج. این تابع یک نقطه را در چارک (زیرناحیه) مناسب از چاردرخت ذخیره می کند و در صورت نیاز ناحیه را تکه می کند. class QuadTree ... // Insert a point into the QuadTree function insert(XY p) // Ignore objects which do not belong in this quad tree if (!boundary.containsPoint(p)) return false; // object cannot be added // If there is space in this quad tree, add the object here if (points.size &lt; QT_NODE_CAPACITY) points.a
ppend(p); return true; // Otherwise, we need to subdivide then add the point to whichever node will accept it if (northWest == null) subdivide(); if (northWest-&gt;insert(p)) return true; if (northEast-&gt;insert(p)) return true; if (southWest-&gt;insert(p)) return true; if (southEast-&gt;insert(p)) return true; // Otherwise, the point cannot be inserted for some unknown reason (which should never happen) return false; یافتن نقاط در یک بازه. این تابع، همه نقاطی که در یک بازه قرار دارند را پیدا می کند. class QuadTree ... // Find all points which appear within a range function queryRange(AABB range) // Prepare an array of results Array of XY pointsInRange; // Automatically abort if the range does not collide with this quad if (!boundary.intersectsAABB(range)) return pointsInRange; // empty list // Check objects at this quad level for (int p := 0; p &lt; points.size; p++) if (range.containsPoint(points[p])) pointsInRange.append(points[p]); // Terminate here, if there are no children if (northWest == null) return
pointsInRange; // Otherwise, add the points from the children pointsInRange.appendArray(northWest-&gt;queryRange(range)); pointsInRange.appendArray(northEast-&gt;queryRange(range)); pointsInRange.appendArray(southWest-&gt;queryRange(range)); pointsInRange.appendArray(southEast-&gt;queryRange(range)); return pointsInRange;
در نظریه پیچیدگی و نظریه محاسبه پذیری، ماشین اوراکل (یا ماشین سروش) یک ماشین انتزاعی برای مطالعه مسائل تصمیم است. می توان آن را به عنوان ماشین تورینگ همراه با یک جعبه سیاه ، که به آن اوراکل گفته می شود، در نظر گرفت که قادر به تصمیم گیریِ مسائل تصمیم خاصّی در یک تک اقدام است. مسئله می تواند از هر رده پیچیدگی باشد. حتّی مسائل تصمیم ناپذیر، مثلِ مسئله توقّف، می توانند استفاده شوند. اوراکِل ها. ماشین اوراکل را می توان یک ماشین تورینگ متصّل به یک اوراکل تصوّر کرد. اوراکل، در این مبحث، موجودیّتی قادر به حل یک سری مسائل است، که به عنوان مثال می تواند مسئله تصمیم یا مسئله تابع باشد. مسئله ممکن است محاسبه پذیر نباشد؛ اوراکل یک ماشین تورینگ یا برنامه کامپیوتری تلقّی نمی شود. اوراکل به طورِ ساده یک «جعبه سیاه» است که قادر به تولید پاسخی برای هر نمونه از یک مسئله محاسباتی است: یک ماشین اوراکل می تواند تمام اعمال معمول یک ماشین تورینگ را به انجام برساند، و هم چنین می تواند از اوراکل برای به دست آوردن پاسخی برای هر نمونه از مسئله محاسباتی برای آن اوراکل بهره ببرد. برای مثال اگر مسئله یک مسئله تصمیم بر روی یک مجموعه "A از ا
عداد طبیعی باشد، ماشین اوراکل یک عدد طبیعی به اوراکل عرضه می دارد، و اوراکل بسته به این که آن عدد عضو 'A' باشد با «بله» یا «نه» پاسخ می دهد. تعاریف. تعاریف هم ارز متعدّدی برای ماشین تورینگ اوراکل وجود دارد، که در پایین در مورد آن ها بحث شده است. موردی که این جا ارائه شده است از van Melkebeek است (۲۰۰۰:۴۳). یک ماشین اوراکل مانند یک ماشین تورینگ شامل اجزای زیر است: علاوه بر این اجزا، یک ماشین اوراکل شامل اجزای زیر نیز هست: گاه به گاه، ماشین اوراکل ممکن است وارد حالت "پرسش" شود. هنگام این رخ داد، اعمال زیر در یک مرحله محاسباتی انجام می شوند: بنابراین تأثیر تغییر به حالت "پرسش"، گرفتن پاسخ، در یک مرحله، به نمونه ای از مسئله است که بر روی نوار اوراکل نوشته شده است. تعاریف جای گزین. علاوه بر تعریفی که در بالا ارائه شد تعاریف جای گزینِ دیگری نیز وجود دارند. تعدادی از آن ها خاصِّ موردی هستند که اوراکِل یک مسئله تصمیم را حل می کند. در این مورد: این تعاریف از منظر محاسبه پذیری تورینگ معادل هستند: تابعی که تحت اوراکِل یکی از این تعاریف، اوراکِل محاسبه پذیر باشد، تحت هر دیگری نیز اوراکِل محاسبه پذیر است. هرچند از منظر پی
چیدگی محاسباتی، این تعاریف معادل نیستند. تعریفی مانند آن چه که van Melkebeek ارائه داده بود، که در آن از نوار اوراکِلی که ممکن است الفبای خود را داشته باشد استفاده می شود، در حالت عمومی لازم است. کلاس های پیچیدگی ماشین اوراکِل. کلاس پیچیدگی مسائل تصمیمِ حل پذیر توسّط الگوریتمی در کلاس A با استفاده از اوراکِلی برای زبان AL، L نامیده می شود. به طور مثال، PSAT کلاس مسائل حل پذیر در زمان چندجمله ای توسّط یک ماشین تورینگ قطعی با اوراکلی برای مسئله ارضاپذیری بولی (SAT) است. نمادگذاری AB را می توان برای مجموعه زبان های B (یا کلاس پیچیدگی B)، با استفاده از تعریف زیر، تعمیم داد: زمانی که یک زبانِ L برای کلاس B کامل باشد، آن گاه AL=AB در صورتی که ماشین های درون A بتوانند تقلیل های استفاده شده در تعریف کامل بودن کلاس B را اجرا نمایند. به طور خاص، از آن جایی که مسئله ارضاپذیریِ بولی نسبت به تقلیل های زمان چندجمله ای ان پی کامل است، PSAT=PNP. هرچند، اگر A=DLOGTIME (کلاس مسائل حل پذیر در زمان لگاریتمی توسّط ماشین تورینگ قطعی)، آن گاه ASAT ممکن است برابر با ANP نباشد. واضح است که NP ⊆ PNP، ولی این پرسش که آیا NP، PNP، NPNP
و P برابر هستند یا نه، در بهترین حالت عملی باقی می مانند. باور بر تفاوت آن هاست و این باعث تعریف سلسله مراتب چندجمله ای می شود. ماشین های اوراکل، با در نظر گرفتن رابطه بین PA و NPA برای یک اوراکل A، برای بررسی رابطه بین کلاس های پیچیدگی P و NP مفید هستند. به طور خاص، نشان داده شده است که وجود دارند زبان های A و B، به قسمی که PA=NPA و (Gill PB≠NPB، Baker و Solovay 1975). این حقیقت که پرسش P = NP از هر دو جهت به صورت نسبی است، به این دلیل است که پاسخ به این پرسش دشوار است، زیرا تکنیک اثباتی که به صورت "نسبی" انجام می گیرد (بدون تأثیر گرفتن از اضافه شدن یک اوراکل) نمی تواند به پرسش P = NP پاسخ دهد. بسیاری از تکنیک های اثبات از نسبی سازی استفاده می کنند. در نظر گرفتن حالتی که یک اوراکل از میان تمام اوراکل های ممکن(یک مجموعه بینهایت) به صورت تصادفی انتخاب شود، قابل توجه است. در این حالت نشان داده شده است که با احتمال یک، PA≠NPA (Bennet و Gill 1981). هنگامی که پاسخ سوالی برای همه اوراکل ها درست باشد، در آن صورت پاسخ پرسش برای یک اوراکل تصادفی نیز درست است. این انتخاب اصطلاحات با دانستن این حقیقت که اوراکل های تصادف
ی یک عبارت را فقط با احتمال 1 یا 0 تأیید می کنند، قابل توجیه است. (این از روی قانون یک صفر Kolmogorov بدست می آید.) به عنوان یک گواه P≠NP. یک عبارت ممکن است همزمان برای یک اوراکل تصادفی درست و برای یک ماشین تورینگ عادی غلط باشد؛ برای مثال برای اوراکل های A، IPA≠PSPACEA، در حالی که IP = PSPACE (Chang et al، 1994). اوراکِل ها و مسئله پایان پذیری. ممکن است که وجود اوراکلی را فرض کرد که قادر به محاسبه یک تابع محاسبه ناپذیر باشد، مانند پاسخ به مسئله توقّف یا مسائل مشابه دیگر. ماشینی با چنین اوراکلی یک فراکامپیوتر است. به طرز جالبی، پارادوکس پایان پذیری هنوز در مورد این ماشین ها نیز صدق می کند؛ با وجود اینکه این ماشین ها می توانند تعیین کنند که آیا ماشین تورینگ خاصی با ورودی های خاصی به حالت پایان خواهد رسید، به طور کلی، آن ها نمی توانند تعیین کنند که آیا ماشین های معادل خودشان به حالت پایان خواهند رسید. این حقیقت منجر به ایجاد سلسله مراتبی از ماشین ها به نام سلسله مراتب محاسباتی می شود، که هر رده دارای اوراکل پایان پذیری قوی تر و مسئله پایان پذیری قوی تری است. کاربردها در رمزنگاری. در رمزنگاری، اوراکل ها برای استد
لال در مورد امنیت قراردادهای رمزنگاری که در آن ها یک تابع درهم ساز استفاده شده است، به کار می رود. یک کاهش امنیت برای یک قرارداد در حالتی داده می شود که، به جای یک تابع درهم ساز، یک اوراکل تصادفی به هر درخواست به صورت تصادفی ولی سازگار پاسخ می دهد؛ فرض می شود که اوراکل در دسترس همه طرف ها، از جمله حمله کننده قرار دارد، همان گونه که تابع درهم ساز در دسترس همه می باشد. چنین اثباتی نشان می دهد که مگر در حالتی که حمله کننده مسئله دشوار را در قلب کاهش امنیت حل کند، حمله کننده باید از خواص جالب توجه تابع درهم ساز برای شکستن قرارداد استفاده کند؛ آن ها نمی توانند با تابع درهم ساز به عنوان یک جعبه سیاه برخورد کنند (به عنوان یک اوراکل تصادفی). منابع. صفحه ماشین اوراکِل در ویکی پدیایِ انگلیسی
شاخه و برش (Branch and cut) روشی است در بهینه سازی ترکیبیاتی برای حل مسائل برنامه های خطی عدد صحیح، این مسائل، برنامه نویسی خطی هستند که در آن ها برخی یا همهٔ مجهولات به مقادیر اعداد صحیح محدود اند. شاخه و برش شامل اجرای یک الگوریتم شاخه و حد، و استفاده از سطح برش به منظور محدود کردن راحتی relaxation در برنامه نویسی خطی است. لازم به ذکر است که اگر برش ها تنها به منظور محدود کردن راحتی اولیه برنامه نویسی خطی مورد استفاده قرار گیرند؛ الگوریتم برش و شاخه نامیده می شود. شرح الگوریتم. این روش برنامه های خطی بدون قید اعداد صحیح را با استفاده از الگوریتم غیر مرکب معمولی حل می کند. زمانی که یک راه حل بهینه پیدا شد، و این راه حل یک مقدار غیر صحیح برای متغیری که قرار بود مقدارش صحیح باشد داشت؛ برای یافتن قیود خطی بیشتر که توسط تمام نقاط صحیح ممکن ارضا شوند ولی به وسیله جواب کسری حاضر نقض شوند ممکن است از الگوریتم سطح برش استفاده شود. این نامساوی ها ممکن است به برنامه خطی اضافه شوند، به طوری که دوباره حل کردن آن به جوابی متفاوت منجر خواهد شد که اگر امیدوار باشیم «کمتر کسری» است. در این نقطه، بخش شاخه و حد الگوریتم آغاز
شده است. مسئله به چندین (معمولاً دو) نسخه تقسیم می شود. برنامه های خطی جدید به وسیلهٔ روش غیر مرکب حل می شوند و فرایند تکرار می شود. در طول فرایند شاخه و حد، جواب های غیر انتگرالی برای، راحتی برنامه نویسی خطی، به عنوان حد بالا به کار گرفته می شوند و جواب های انتگرالی به عنوان حد پایین. یک گره می تواند هرس شود اگر یک حد بالا، پایین تر از حد پایین موجود باشد. همچنین در هنگام حل راحتی lp ممکن است سطح برش اضافی تولید گردد، که یا برش های سراسری هستند به عنوان مثال معتبر برای تمام جواب های صحیح، ویا برش های محلی، به آن معنی که آن ها به وسیلهٔ تمامی جوابهایی که قیود جانبی زیر درخت شاخه و حد در نظر گرفته شدهٔ کنونی را برآورده می کنند، ارضا می شوند. الگوریتم به صورت زیر خلاصه شده است. الگوریتم فرض می کند ILP (برنامه نویسی منطقی استقرایی) یک مسئلهٔ بیشینه سازی است. راهبردهای شاخه شدن. یک مرحلهٔ مهم در الگوریتم شاخه و حد مرحلهٔ شاخه شدن است. در این مرحله انواع مختلفی از شاخه شدن های ابتکاری وجود دارد که می توان از آن ها استفاده کرد. تمامی استراتژی های شاخه شدنی که در زیر توضیح داده شده اند شامل موردی هستند به نام شاخه ش
دن بر روی متغیر. شاخه شدن بر روی متغیر شامل انتخاب یک متغیر، formula_14، و مقدار کسری formula_15 برای جواب راحتی lp کنونی و سپس اضافه کردن قیود formula_16 و formula_17 است. همچنین تعداد زیادی از گونه های این استراتژی های شاخه شدن وجود دارد. به عنوان مثال زمانی که شاخه شدن شبه هزینه نسبتاً بی ارزش است ابتدا از شاخه شدن قوی استفاده کرد سپس بعداً از شاخه شدن شبه هزینه استفاده کرد زمانی که به اندازهٔ کافی تاریخچهٔ شاخه کردن موجود باشد تا این روش مؤثر واقع شود.
در علم حساب و برنامه نویسی کامپیوتر الگوریتم تعمیم یافته اقلیدس تعمیمی بر الگوریتم اقلیدس است که در کنار محاسبه بزرگترین مقسوم علیه مشترک دو عدد صحیح a,b ضرایب قضیه بزو را هم محاسبه می کند(x,y اعداد صحیح اند): formula_1 همچنین می توان بدون هزینهٔ اضافی خارج قسمت a,b را با بزرگترین مقسوم علیه مشترک محاسبه کرد. الگوریتم تعمیم یافته اقلیدس به الگوریتمی بسیار مشابه به الگوریتمی برای محاسبه بزرگترین مقسوم علیه مشترک چندجمله ای و ضرایب قضیه بزو از دو چندجمله ای با یک متغیر، ارجاع دارد. الگوریتم تعمیم یافته اقلیدس زمانی که a و b نسبت به هم اولند مفید تر است. چون x برابر وارون ضربی پیمانه ای a به پیمانه b و y برابر وارون ضربی پیمانه ای b به پیمانه a است. در الگوریتم اقلیدس برای چندجمله ای می توان وارون ضربی را در بسط های میدان جبری محاسبه کرد. که از آن نتیجه می شود هردو نوع الگوریتم اقلیدسی تعمیم یافته (معمولی و چندجمله ای) کاربردی گسترده در رمزنگاری دارند. به خصوص در محاسبه وارون ضربی پیمانه ای در روش RSA یک گام ضروریست. توضیح الگوریتم. در الگوریتم اقلیدسی معمولی فقط باقی مانده ها نگاه داشته می شوند و خارج قسمت استف
اده نمی شود. اما در الگوریتم تعمیم یافته خارج قسمت های متوالی استفاده می شوند. به طور دقیقتر در الگوریتم تعمیم یافته که a، b را به عنوان ورودی می گیرد، دنبالهٔ formula_2 از خارج قسمت ها و دنبالهٔ formula_3 از باقی مانده ها را شامل می شود. مهمترین ویژگی تقسیم اقلیدسی نامساوی سمت راست است که formula_5 را متفاوت از formula_6 و formula_7 تعریف می کند. وقتی باقی مانده به صفر رسید محاسبه متوقف می شود، بزرگترین مقسوم علیه مشترک آخرین باقی مانده غیر صفر است. الگوریتم تعمیم یافته اقلیدسی روشی مشابه دارد با این تفاوت که دو دنبالهٔ زیر نیز به آن اضافه می شود: در این الگوریتم هم وقتی formula_9 میشود کار الگوریتم به اتمام می رسد. formula_15 formula_16 و formula_17 به علاوه اگر a و b هردو مثبت باشند داریم: که این یعنی جفت ضرایب بزو که از این الگوریتم به دست می آیند یکی از کمترین جفت ضرایب بزو هستند. مثال. جدول زیر رویه الگوریتم تعمیم یافته اقلیدسی را برای46 و240 را نشان می دهد. بزرگترین مقسوم علیه مشترک برابر ۲ است. محاسبه در سطر ۶ متوقف می شود، چون باقی مانده صفر می شود. ضرایب بزو هم در دو ستون آخر از سطر آخرند. تحقیق راب
طه -9*240+47*46=2 راحت است. و سرانجام -120 و 23 بدون توجه به علامت برابر تقسیم ۲۴۰ و ۴۶ بر بزرگترین مقسوم علیه مشترک یعنی ۲ هستند اثبات. چون formula_19 و دنبالهٔ باقی مانده ها یک دنبالهٔ نزولی غیر منفی است در نتیجه باید حتماً با formula_20 متوقف شود. این نشان می دهد که الگوریتم متوقف می شود و کار به اتمام می رسد. چون formula_21 در نتیجه بزرگترین مقسوم علیه مشترک formula_22 و formula_23 برابر است. که از ان نتیجه می شود بزرگترین مقسوم علیه مشترک formula_24 برابر است با بزرگترین مقسوم علیه مشترک formula_25 وهمچنین نشان می دهد که formula_26 بزرگترین مقسوم علیه مشترک a و b است که آن را d می نامیم. formula_27 و formula_28 که برای i=0,1داریم: formula_29 برای هر i رابطهٔ بازگشتی خطی برقرار است بخصوص برای i=k که formula_30 نشان میدهیم که formula_31 ضرایب بزواند. ماتریس زیر را در نظر بگیرید رابطهٔ بازگشی را به شکل ماتریسی می نویسیم ماتریس formula_34 ماتریس واحد است و دترمینان آن برابر ۱ است. دترمینان ماتریس سمت راست برابر -1 است که نتیجه می شود دترمینان formula_35 برابر formula_36 است و برای حالت خاص i=k+1 داریم formul
a_37 که نشان می دهد formula_38 و formula_39 نسبت بهم اولند. رابطهٔ formula_40 که در بالا اثبات شد و لم اقلیدس نشان می دهد که formula_38 مقسوم علیه b و formula_39 مقسوم علیه a اند. چون آن ها نسبت بهم اولاً بدون در نظر گرفتن علامتشان برابر خارج قسمت تقسیم a و b بر d می شوند. الگوریتم اقلیدسی برای چندجمله ای. برای یک چندجمله ای با ضریب در یک میدان همه چیز مشابه حالت قبل است (تقسیم اقلیدسی، قضیه بزو، و تعمیم الگوریتم اقلیدس). اولین تفاوت در تقسیم اقلیدسی و الگوریتم، جایگذاری 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 تقسیم کنیم قضیه کلاسیک بزو بدست می آید ، با یک مقسوم علیه مشترک ساده برای اعداد گویایی که در آن ظاهر می شوند. شبه کد. برای پیاده سازی الگوریتمی که در بالا ذکر شد،اولاً باید توجه داشت که در هر مرحله تنها نیاز به نگهداری دو مقدار نهایی متغیرهای شاخص گذاری شده، هست. بنابراین برای صرفه جویی در حافظه هر متغیر شاخص گذاری شده باید با تنها دو متغیر جایگزین شود. برای راحتی کار در الگوریتم زیر(و بقیهٔ الگوریتم ها در این مقاله) از مقداردهی موازی استفاده می شود.در زبانهای برنامه نویسی که از مقداردهی موازی پشتیبانی نمی کنند، باید اینکار را با کمک یک متغیر کمکی شبیه سازی کرد. برای مثال (old_r, r) := (r, old_r - quotient *r) برابر هست با prov := r; r := old_r - quotient * prov; old_r := prov; و مشابهاً برای بقیهٔ استفاده ها از مقداردهی موازی هم باید