payamvha/North_RAG 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
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
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.append(p); return
&lt; QT_NODE_CAPACITY) points.append(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]))
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 با استفاده از
حل‌پذیر توسّط الگوریتمی در کلاس A با استفاده از اوراکِلی برای زبان AL، L نامیده می‌شود. به‌طور مثال، PSAT کلاس مسائل حل‌پذیر در زمان چندجمله‌ای توسّط یک ماشین تورینگ قطعی با اوراکلی برای مسئلۀ ارضاپذیری بولی (SAT) است. نمادگذاری AB را می‌توان برای مجموعۀ زبان‌های B (یا کلاس پیچیدگی B)، با استفاده از تعریف زیر، تعمیم داد: زمانی که یک زبانِ L برای کلاس B کامل باشد، آن‌گاه AL=AB در صورتی که ماشین‌های درون A بتوانند تقلیل‌های استفاده‌شده در تعریف کامل بودن کلاس B را اجرا نمایند. به‌طور خاص، از آن‌جایی که مسئلۀ
B را اجرا نمایند. به‌طور خاص، از آن‌جایی که مسئلۀ ارضاپذیریِ بولی نسبت به تقلیل‌های زمان چندجمله‌ای ان‌پی کامل است، PSAT=PNP. هرچند، اگر A=DLOGTIME (کلاس مسائل حل‌پذیر در زمان لگاریتمی توسّط ماشین تورینگ قطعی)، آن‌گاه ASAT ممکن است برابر با ANP نباشد. واضح است که NP ⊆ PNP، ولی این پرسش که آیا NP، PNP، NPNP و P برابر هستند یا نه، در بهترین حالت عملی باقی می‌مانند. باور بر تفاوت آن‌هاست و این باعث تعریف سلسله‌مراتب چندجمله‌ای می‌شود. ماشین‌های اوراکل، با در نظر گرفتن رابطۀ بین PA و NPA برای یک اوراکل A، برای
گرفتن رابطۀ بین 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 بدست
است. (این از روی قانون یک‌صفر Kolmogorov بدست می‌آید.) به عنوان یک گواه P≠NP. یک عبارت ممکن است همزمان برای یک اوراکل تصادفی درست و برای یک ماشین تورینگ عادی غلط باشد؛ برای مثال برای اوراکل‌های A، IPA≠PSPACEA، در حالی که IP = PSPACE (Chang et al، 1994). اوراکِل‌ها و مسئلۀ پایان‌پذیری. ممکن است که وجود اوراکلی را فرض کرد که قادر به محاسبۀ یک تابع محاسبه‌ناپذیر باشد، مانند پاسخ به مسئلۀ توقّف یا مسائل مشابه دیگر. ماشینی با چنین اوراکلی یک فراکامپیوتر است. به طرز جالبی، پارادوکس پایان‌پذیری هنوز در مورد این
طرز جالبی، پارادوکس پایان‌پذیری هنوز در مورد این ماشین‌ها نیز صدق می‌کند؛ با وجود اینکه این ماشین‌ها می‌توانند تعیین کنند که آیا ماشین تورینگ خاصی با ورودی‌های خاصی به حالت پایان خواهد رسید، به‌طور کلی، آن‌ها نمی‌توانند تعیین کنند که آیا ماشین‌های معادل خودشان به حالت پایان خواهند رسید. این حقیقت منجر به ایجاد سلسله مراتبی از ماشین‌ها به نام سلسله مراتب محاسباتی می‌شود، که هر رده دارای اوراکل پایان‌پذیری قوی‌تر و مسئلۀ پایان‌پذیری قوی‌تری است. کاربردها در رمزنگاری. در رمزنگاری، اوراکل‌ها برای استدلال در
رمزنگاری. در رمزنگاری، اوراکل‌ها برای استدلال در مورد امنیت قراردادهای رمزنگاری که در آن‌ها یک تابع درهم‌ساز استفاده شده‌است، به کار می‌رود. یک کاهش امنیت برای یک قرارداد در حالتی داده می‌شود که، به جای یک تابع درهم‌ساز، یک اوراکل تصادفی به هر درخواست به صورت تصادفی ولی سازگار پاسخ می‌دهد؛ فرض می‌شود که اوراکل در دسترس همۀ طرف‌ها، از جمله حمله‌کننده قرار دارد، همان‌گونه که تابع درهم‌ساز در دسترس همه می‌باشد. چنین اثباتی نشان می‌دهد که مگر در حالتی که حمله‌کننده مسئلۀ دشوار را در قلب کاهش امنیت حل کند،
مسئلۀ دشوار را در قلب کاهش امنیت حل کند، حمله‌کننده باید از خواص جالب توجه تابع درهم‌ساز برای شکستن قرارداد استفاده کند؛ آن‌ها نمی‌توانند با تابع درهم‌ساز به عنوان یک جعبۀ سیاه برخورد کنند (به عنوان یک اوراکل تصادفی). منابع. صفحۀ ماشین اوراکِل در ویکی‌پدیایِ انگلیسی
شاخه و برش (Branch and cut) روشی است در بهینه سازی ترکیبیاتی برای حل مسائل برنامه‌های خطی عدد صحیح، این مسائل، برنامه نویسی خطی هستند که در آن‌ها برخی یا همهٔ مجهولات به مقادیر اعداد صحیح محدود‌اند. شاخه و برش شامل اجرای یک الگوریتم شاخه و حد، و استفاده از سطح برش به منظور محدود کردن راحتی relaxation در برنامه‌نویسی خطی است. لازم به ذکر است که اگر برش‌ها تنها به منظور محدود کردن راحتی اولیه برنامه نویسی خطی مورد استفاده قرار گیرند؛ الگوریتم برش و شاخه نامیده می‌شود. شرح الگوریتم. این روش برنامه‌های خطی بدون
می‌شود. شرح الگوریتم. این روش برنامه‌های خطی بدون قید اعداد صحیح را با استفاده از الگوریتم غیر مرکب معمولی حل می‌کند. زمانی که یک راه حل بهینه پیدا شد، و این راه حل یک مقدار غیر صحیح برای متغیری که قرار بود مقدارش صحیح باشد داشت؛ برای یافتن قیود خطی بیشتر که توسط تمام نقاط صحیح ممکن ارضا شوند ولی به وسیله جواب کسری حاضر نقض شوند ممکن است از الگوریتم سطح برش استفاده شود. این نامساوی‌ها ممکن است به برنامه خطی اضافه شوند، به طوری که دوباره حل کردن آن به جوابی متفاوت منجر خواهد شد که اگر امیدوار باشیم «کمتر
متفاوت منجر خواهد شد که اگر امیدوار باشیم «کمتر کسری» است. در این نقطه، بخش شاخه و حد الگوریتم آغاز شده‌است. مسئله به چندین (معمولاً دو) نسخه تقسیم می‌شود. برنامه‌های خطی جدید به وسیلهٔ روش غیر مرکب حل می‌شوند و فرایند تکرار می‌شود. در طول فرایند شاخه و حد، جواب‌های غیر انتگرالی برای، راحتی برنامه نویسی خطی، به عنوان حد بالا به کار گرفته می‌شوند و جواب‌های انتگرالی به عنوان حد پایین. یک گره می‌تواند هرس شود اگر یک حد بالا، پایین‌تر از حد پایین موجود باشد. همچنین در هنگام حل راحتی lp ممکن است سطح برش اضافی
در هنگام حل راحتی 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 را نشان می‌دهد.
یافته اقلیدسی را برای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_31 ضرایب بزواند. ماتریس زیر را در نظر بگیرید رابطهٔ بازگشی را به شکل ماتریسی می‌نویسیم ماتریس 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‌اند. چون آن‌ها نسبت بهم اولاً بدون در نظر گرفتن علامتشان برابر خارج قسمت تقسیم a و b بر d می‌شوند. الگوریتم اقلیدسی برای چندجمله‌ای. برای یک چندجمله‌ای با ضریب در یک میدان همه چیز مشابه حالت قبل است (تقسیم اقلیدسی، قضیه بزو، و تعمیم الگوریتم اقلیدس). اولین تفاوت در تقسیم اقلیدسی و الگوریتم، جایگذاری formula_43 بجای formula_44 است. بقیه مشابه حالت قبل باقی میماند. تفاوت دوم در محدودیتی است که بر اندازهٔ ضرایب بزو که از تعمیم الگوریتم اقلیدس به دست میاید وجود دارد، که در مورد چندجمله‌ای دقیق تر است. اگر a
دارد، که در مورد چندجمله‌ای دقیق تر است. اگر a و b دو چند جملۀ غیر صفر باشند الگوریتم تعمیم یافته (s,t) را به گونه‌ای به دست میاورد که در شرایط زیر صدق کند: و تفاوت سوم در این است که بزرگترین مقسوم علیه مشترک فقط به صورت ضرب یک ثابت غیر صفر تعریف می‌شود. راه‌های مختلفی برای تعریف بزرگترین مقسوم علیه مشترک به صورت غیر مبهم وجود دارد. در ریاضیات معمولاً به چندجمله‌ای که ب.م.م همهٔ ضریب‌هایش یک هست نیاز است. برای رسیدن به این مقصود کافیست هر خروجی را بر ضریب بزرگترین توان formula_47 تقسیم کنیم. اگر a و b نسبت
توان formula_47 تقسیم کنیم. اگر a و b نسبت به هم اول باشند در سمت راست نامساوی بزو یکی ۱ می‌شود، در غیر این صورت یکی ممکن است هر مقدار ثابت غیر صفر شود. در جبر کامپیوتر، چندجمله‌ای معمولاً ضرایب صحیح را می‌پذیرد، و این راه ساده‌سازی بزرگترین مقسوم علیه مشترک برای سهولت تعداد بسیار زیادی بخش ایجاد می‌کند. راه دوم ساده‌سازی بزرگترین مقسوم علیه مشترک در حالت چندجمله‌ای با ضرایب صحیح تقسیم بر بزرگترین عمل مشترک بین ضرایب formula_48 برای رسیدن به چندجمله‌ای اصلی (یعنی چندجمله‌ای که بزرگترین عامل مشترک ضرایبش ۱
(یعنی چندجمله‌ای که بزرگترین عامل مشترک ضرایبش ۱ است). اگر چند جمله‌ی‌های ورودی نسبت به هم اول باشند این نرمال‌سازی بزرگترین مقسوم علیه مشترک را یک می‌دهد. اشکال این روش محاسبه، وجود زیر مسئله‌های زیاد است که باید محاسبه و ساده شوند. روش سوم شامل تعمیم الگوریتم subresultant pseudo-remainder sequences که مشابه تعمیم الگوریتم اقلیدسی به الگوریتم تعمیم یافته‌است. این روش این امکان را فراهم می‌کند که وقتی با چندجمله‌ای با ضرایب صحیح شروع می‌کنیم هر چندجمله‌ای که بدست میاید ضرایبش، صحیح باشد. علاوه بر این هر