Payamvdn/NorthPersian_fa_wiki huggingface dataset:
ست. پروژه هایی که از راست استفاده می کنند. پروژه های توسعه یافته در Rust شامل: مبتنی بر مرورگر: مبتنی بر ابزار ساخت: پروژه های دیگر: نصب و راه اندازی Rust. برای استفاده از زبان Rust، باید ابتدا کامپایلر آن که با نام codice_1 شناخته می شود، نصب شود. بهترین و توصیه شده ترین روش برای نصب Rust استفاده از ابزار خط فرمان codice_2 است. این ابزار مدیریت نسخه های مختلف Rust و ابزارهای جانبی آن را بر عهده دارد و امکان به روزرسانی، حذف و نصب آسان کامپایلر را فراهم می کند. نصب بر روی لینوکس و macOS. در سیستم عامل های یونیکسی، می توان با اجرای دستور زیر در ترمینال، ابزار rustup و کامپایلر Rust را به سادگی نصب کرد: curl --proto '=https' --tlsv1.2 https://sh.rustup.rs -sSf | sh همچنین برای کامپایل صحیح برخی بسته ها که به کدهای C وابسته اند، وجود یک کامپایلر C مانند codice_3 یا codice_4 ضروری است. در توزیع هایی مانند Ubuntu توصیه می شود از دستور زیر برای نصب ابزارهای توسعه استفاده شود: sudo apt install build-essential نصب روی ویندوز. کاربران ویندوز می توانند با دانلود فایل نصب از وب سایت رسمی Rust یا اجرای دستور زیر در محیط
PowerShell (در ویندوز ۱۰ یا ۱۱ که winget پشتیبانی می شود) اقدام به نصب کنند: winget install rustup در طول فرایند نصب ممکن است نیاز به نصب ابزارهای ساخت مانند Build Tools for Visual Studio باشد، مخصوصاً برای پشتیبانی از برخی بسته های وابسته به کد ++C. به روزرسانی و حذف. ابزار codice_2 امکان به روزرسانی نسخه Rust و یا حذف کامل آن را فراهم می کند: rustup update rustup self uninstall بررسی نصب موفق. برای اطمینان از نصب صحیح Rust، می توان دستور زیر را اجرا کرد: rustc --version که در صورت موفقیت، شماره نسخه نصب شده را نمایش می دهد. مستندات محلی. پس از نصب Rust، یک نسخه از مستندات زبان نیز به صورت آفلاین بر روی سیستم قرار می گیرد. با اجرای دستور زیر، این مستندات در مرورگر باز می شوند: rustup doc نمونه ها. نمونه کد زیر برای Rust نسخه ۰٫۸ معتبر می باشد. نحو و معناشناسی ممکن است در نسخه های بعدی تغییر یابد.برنامه Hello World: fn main() { println!("Hello, World"); دو نمونه از تابع فاکتوریل در ساختارهای بازگشتی و ترتیبی : /* The branches in this function exhibit Rust's optional implicit return values, which can be utiliz
ed where a more "functional" style is preferred. Unlike C++ and related languages, Rust's `if` construct is an expression rather than a statement, and thus has a return value of its own. */ fn recursive_factorial(n: i32) -&gt; i32 { fn iterative_factorial(n: i32) -&gt; i32 { // Variables are declared with `let`. // The `mut` keyword allows these variables to be mutated. let mut i = 1; let mut result = 1; while i &lt;= n { result *= i; i += 1; return result; // An explicit return, in contrast to the prior function. fn main() { println!("Recursive result: {:?}", recursive_factorial(10)); println!("Iterative result: {:?}", iterative_factorial(10)); یک نمایش ساده از قابلیت همزمانی ساده از Rust: /* This function creates ten "tasks" that all execute concurrently. Run it several times and observe the irregular output that results as each task races on stdout, due to the fact that each task may yield both between successive calls to `println` and within the `println` function itself. */ fn main() { // This string is
immutable, so it can safely be accessed from multiple tasks. let message = "Look at me, I'm in a lightweight thread!"; // `for` loops work with any type that implements the `Iterator` trait. for num in range(0, 10) { do spawn { println(message); // `println!` is a macro that statically verifies a format string. // Macros are structural (as in Scheme) rather than textual (as in C). println!("This message brought to you by task {:?}.", num); یک نمایش ساده از اشاره گرهای هوشمند یگانی همراه با tagged unions و روش ها: use IntList::{Node, Empty}; // This program defines a recursive data structure and implements methods upon it. // Recursive data structures require a layer of indirection, which is provided here // by a unique pointer, constructed via the `Box::new` constructor. These are // analogous to the C++ library type `std::unique_ptr`, though with more static // safety guarantees. fn main() { let list = IntList::new().prepend(3).prepend(2).prepend(1); println!("Sum of all values in the list: {}.", list.sum())
; println!("Sum of all doubled values in the list: {}.", list.multiply_by(2).sum()); // `enum` defines a tagged union that may be one of several different kinds of values at runtime. // The type here will either contain no value, or a value and a pointer to another `IntList`. enum IntList { Node(i32, Box&lt;IntList&gt;), Empty // An `impl` block allows methods to be defined on a type. impl IntList { fn new() -&gt; Box&lt;IntList&gt; { Box::new(Empty) fn prepend(self, value: i32) -&gt; Box&lt;IntList&gt; { Box::new(Node(value, Box::new(self))) fn sum(&amp;self) -&gt; i32 { // `match` expressions are the typical way of employing pattern-matching, // and are somewhat analogous to the `switch` statement from C and C++. match *self { Node(value, ref next) =&gt; value + next.sum(), Empty =&gt; 0 fn multiply_by(&amp;self, n: i32) -&gt; Box&lt;IntList&gt; { match *self { Node(value, ref next) =&gt; Box::new(Node(value * n, next.multiply_by(n))), Empty =&gt; Box::new(Empty) بدافزارها. در مواردی، نویسندگان بدافزار نیز
از زبان برنامه نویسی راست استفاده کرده اند. برای مثال، باج افزار BlackCat به زبان راست برنامه نویسی شده است.
الگوریتم تارژان (نام گذاری: مبدع، رابرت تارژان)، از الگوریتم های تئوری گراف است که برای پیدا کردن مؤلفه های قویاً همبند در یک گراف استفاده می شود. با وجود اینکه، این الگوریتم از نظر زمانی مقدم بوده است، می توان دید که نسخهٔ بهبود یافته الگوریتم کساراجو و از نظر کارایی (بازده) با الگوریتم مؤلفه قوی مبتنی بر مسیر قابل مقایسه است. نمای کلی. الگوریتم به عنوان ورودی گراف جهت داری را می گیرد، و افرازی از رئوس گراف به مؤلفه های قویاً همبند تولید می کند. هر راسی (گره) از گراف، دقیقاً یک بار در مؤلفه های همبند ظاهر می شود. هر راس که در یک دور جهت دار نیست، خودش به عنوان یک مؤلفه های قویاً همبند انتخاب می شود: برای مثال، راسی که درجه ورودی و درجه خروجی آن صفر باشد، یا هر راس از گراف بدون دور به تنهایی یک مؤلفهٔ قویاً همبند حساب می شوند. ایدهی ابتدایی این الگوریتم: الگوریتم جستجو عمق اول با راس دلخواه شروع می کند (و جستجوی بعدی عمق اول، بر روی راس هایی اعمال می شود که دیده نشدهاند). با الگوریتم جستجوی عمق اول، جستجو، هر راسی گراف را دقیقاً یک بار می بیند؛ بنابراین، مجموعه ی درخت جستجو، یک جنگل پوشا از گراف است. مؤلفه ها
ی قویاً همبند، به عنوان زیردرختهای معین این درخت پوشا، به دست خواهد آمد. ریشهی این زیردرختها را، ریشهی مؤلفه های قویاً همبند می گویند. هر راسی از مؤلفه های قویاً همبند ممکن است به عنوان ریشه به کار گرفته شود، اگر اولین راسی باشد که از آن مؤلفه دیده می شود. پشته ثابت. راس ها به ترتیبی که دیده می شوند در داخل پشته جای می گیرند. زمانی که جستجوی عمق اول به صورت بازگشتی، راسی V و فرزاندانش را ملاقات کند، آن راس ها، نباید تا قبل از بازگشت این فراخوانی بازگشتی از پشته، POP شوند. خاصیت یکسانی (ثابت)، این است که، یک راس بعد از پیمایش، بر روی پشته باقی می ماند، اگر و تنها اگر مسیری به برخی از راس های پایین تر در پشه وجود داشته باشد. بعد از اتمام فراخوانی ای که V و فرزاندان آن را پیدا می کند، ما می دانیم که آیا V به هر راسی قبل از خودش در پشته مسیر دارد یا خیر. اگر چنین بود فراخوانی بازمی گردد. V را در پشته به عنوان ثابت، نگاه می دارد. اگر نه، V باید ریشهی مؤلفه های قویاً همبند باشد که شامل V و راس های بعدی در پشته است. (راس هایی که به V مسیر دارند ولی به ماقبل V مسیری ندارند). تمام مؤلفه ها، POP می شود و ثابت را نگه می
دارد. پیاده سازی. هر راسی v به یک عدد صحیح، v.index اختصاص داده می شود که اعداد راس ها بصوت متوالی، بترتیبی که پیدا شدهاند، قرار داده می شود. همچنین یک مقدار، v.lowlink که کوچکترین اندیس هر راسی شناخته شدهی قابل دسترس از v، شامل خود v را نمایش می دهد، نگه داشته می شود؛ بنابراین، v باید سمت چپ پشته باشد اگر v.lowlinke &lt;v.index در حالی که، v باید به عنوان ریشه مؤلفه قویاً همبند حذف شود اگر v.lowlink==v.index. مقدار v.lowlink، در حین جستجوی عمق اول از v محاسبه می شود، همان طور که راس های قابل دسترس از v را پیدا می کند. شبه کد. algorithm tarjan is input: graph G = (V, E) output: set of strongly connected components (sets of vertices) index := ۰ S := empty for each v in V do if (v.index is undefined) then strongconnect(v) end if end for function strongconnect(v) // Set the depth index for v to the smallest unused index v.index := index v.lowlink := index index := index + 1 S.push(v) // Consider successors of v for each (v, w) in E do if (w.index is undefined) then // Successor w has not yet been visited; recur
se on it strongconnect(w) v.lowlink := min(v.lowlink, w.lowlink) else if (w is in S) then // Successor w is in stack S and hence in the current SCC v.lowlink := min(v.lowlink, w.index) end if end for // If v is a root node, pop the stack and generate an SCC if (v.lowlink = v.index) then start a new strongly connected component repeat w := S.pop() add w to current strongly connected component until (w = v) output the current strongly connected component end if end function index variable همان شماره راس (گره) در الگوریتم جستجوی اول عمق می باشد. S پشتهٔ راس ها می باشد که در ابتدا خالی می باشد و برای ذخیره سازی راس هایی که دیده شده اند ولی هنوز به مؤلفه های قویاً همبند ملحق نشده اند می باشد. ذکر این نکته مهم است که این پشته همان پشتهٔ جستجوی اول عمق نمی باشد در واقع با خروج آن راس در الگوریتم جستجوی اول عمق از پشته حذف نمی شود و تنها در صورتی راس ها حذف می شوند که یک مؤلفهٔ قویاً همبند پیدا شود تا تمامی رأس های آن حذف شود. بیرونی ترین حلقه در کد بالا در بین راس هایی که هنوز دیده نشده اند جستجو می کند تا تضمین کند
که راس هایی که از راس اول قابل دسترسی نیستند نیز دیده خواهند شد. تابع strongconnect یک جستجوی اول عمق را انجام می دهد که تمامی فرزندان راس v را می بیند و تمامی مؤلفه های قویاً همبند آن زیر گراف را پیدا می کند. هنگامی که هر راسی تابع بازگشتی جستجوی اول عمقش تمام می شود اگر مقدار lowlink آن برابر اندیس آن باشد یعنی آن راس ریشهٔ یک مؤلفهٔ قویاً همبند شامل تمام راس های بالاتر از آن درون پشته خواهد بود. الگوریتم تمامی راس های بالاتر از انرا از پشته خارج می کند و همهٔ آنهارا به عنوان یک مؤلفه در نظر می گیرد.
مسئلهٔ پایان خوش (که توسط پل اردیش نامگذاری شده است، چرا که به ازدواج جورج سیکریس و استر کلاین منجر شد) گزارهٔ ذیل است: این قضیه یکی از نتایج اصلی است که منجر به ظهور نظریهٔ رمزی شد. قضیهٔ پایان خوش، با تحلیل یک حالت ساده اثبات می شود: اگر چهار یا تعداد بیش تری نقطه، رأس های یک بدنهٔ محدب باشند، هر چهار نقطه ای به این شکل می توانند انتخاب شوند. از طرفی دیگر، اگر مجموعهٔ نقاط به فرم یک مثلث با دو نقطه درون آن باشند، دو نقطهٔ درونی و یکی از اضلاع مثلث می توانند انتخاب شوند. برای توضیح مصور این اثبات، پترسون (۲۰۰۰) را ببینید و برای بررسی دقیق تر این مسئله نسبت به آنچه اینجا ارائه شده است، موریس و سالتن (۲۰۰۰) را ببینید. تخمین اردوش-سیکریس رابطهٔ کلی بین تعداد نقاطی که در یک مجموعهٔ نقاط با موقعیت عمومی هستند و بزرگ ترین چندضلعی محدب آن را به طور دقیق بیان می کند. این مسئله اثبات نشده باقی می ماند، اما مرزهای دقیق کم تری شناخته شده است. چندضلعی های درجهٔ بالاتر. دو دانشمند به نام های اردوش و سیکریس این قضیه را به صورت زیر تعمیم داده اند: اثبات قضیه اردیش–ژکرس در مقاله ای که قضیهٔ زیردنباله های یکنواخت در دنباله ه
ای عددی را اثبات می کند آمده است. فرض کنید ("f"("N" کمترین مقدار "M" را نشان دهد که برای هر مجموعه از "M" نقطه در موقعیت عمومی یک "N"ضلعی محدب وجود داشته باشد. داریم: بر مبنای مقادیر مشخص ("f"("N"، یعنی برای N" = ۳, ۴, ۵"، اردوش و سیکریس در مقالهٔ اصلی خود رابطهٔ زیر را تخمین زدند: به ازای هر N" ≥ ۳" بعدها این دو نفر با زدن مثال های خارجی دیگر ثابت کردند که: اما بهترین کران بالا برای حالت هایی که N" ≥ ۷" است، به صورت زیر است: چندضلعی های خالی. ممکن است سؤال پیش بیاید که آیا برای هر مجموعهٔ کافی از نقاط در موقعیت عمومی دارای یک چهارضلعی، پنج ضلعی و.. هست یا نه، به این معنی که نیاز به نقطه ورودی جدید نداشته باشد. راه حل اصلی مسئلهٔ پایان خوش را می توان طوری تطابق داد که نشان دهد به ازای هر پنج نقطه با وضعیت موقعیت عمومی در صفحه یک چهارضلعی محدب خالی وجود دارد، همان طور که در تصویر نشان داده شده، و به ازای هر ده نقطه با شرایط فوق یک پنج ضلعی محدب خالی وجود دارد. اگرچه مجموعه های بزرگ و دلخواهی از نقاط با موقعیت عمومی ممکن است وجود داشته باشند که هیچ هفت ضلعی خالی برای آن ها یافت نشود. برای مدت طولانی این سؤال که
آیا شش ضلعی خالی وجود دارد یا نه، بدون پاسخ ماند، ولی نیکولاس (۲۰۰۷) و گرکن (۲۰۰۸) ثابت کردند که به ازای هر مجموعهٔ کافی از نقاط با موقعیت عمومی در صفحه یک شش ضلعی محدب خالی وجود دارد. به صورت خاص، گرکن نشان داد که تعداد نقاط مورد نیاز بیشتر از (f"(۹" نیست. ("f" در بالا تعریف شده) درحالیکه نیکولاس نشان داد این مقدار حداکثر به اندازهٔ (f"(۲۵" است. (Valtr(۲۰۰۶ اثبات گرکن را ساده می کند و نشان می دهد که به نقاط بیشتری از (f"(۹"، یعنی به اندازهٔ (f"(۱۵" که برابر ۳۰ نقطه می شود، نیاز داریم، چرا که یک مجموعه از ۲۹ نقطه در موقعیت عمومی در صفحه وجود دارد که برای آن شش ضلعی محدب خالی وجود ندارد. مسائل مرتبط. مسئلهٔ پیدا کردن مجموعه عای شامل "n" نقطه به طوری که تعداد چندضلعی های محدب را کمینه کند، مشابه کمینه کردن تعداد عبور در یک ترسیمِ خطِ مستقیمِ یک گراف کامل است. تعداد چندضلعی ها باید متناسب با توان چهارم "n" باشد، اما مقدار ثابت دقیقی، مشخص نیست. به طور سرراست می توان نشان داد که در فضای اقلیدسی با ابعاد بالاتر، مجموعه های به اندازهٔ کافی بزرگ از نقاط، یک زیرمجموعه از "k" نقطه خواهند داشت که رأس های یک چندبر محدب
را تشکیل می دهند، برای هر "k" بزرگ تر از بُعد: این مسئله خیلی سریع از موجود بودن "k"-ضلعی محدب در مجموعه های نقاط مسطح به اندازهٔ کافی بزرگ پیروی می کند، به این صورت که مجموعه نقاط با ابعاد بالاتر را در یک شبه فضای دوبعدی اختیاری طراحی می کند. اما تعداد نقاط لازم برای پیدا کردن "K" نقطه در حالت محدب ممکن است در ابعاد بالاتر نسبت به حالتی که در صفحه است، کم تر باشد، و همچنین پیدا کردن زیرمجموعه هایی که محدودتر هستند، امکان پذیر است. به طور مشخص، در "d" بعد، هر d" + ۳" نقطه در موقعیت عمومی، یک زیرمجموعه از d" + ۲" نقطه دارد که رئوس یک چندبر چرخه ای را تشکیل می دهند. در حالت کلی تر، برای هر "d" و "k"&gt; "d"، عدد ("m"("d", "k" وجود دارد به گونه ای که هر مجموعه از ("m"("d", "k" نقطه در موقعیت عمومی یک زیر مجموعه از "k" نقطه خواهد داشت که رئوس یک چندبر همسایگی را تشکیل می دهد.
در ریاضیات، حوزهٔ نظریهٔ گرافها، گراف وتری گرافی است که هر دور به طول چهار یا بیشتر از آن شامل وتر باشد. (وتر: یالی است که دو رأس نامتوالی از دور را به هم وصل می کند). به عبارت دیگر، هر دور القایی در گراف می بایست حداکثر سه رأس داشته باشد. گراف های وتری زیرمجموعه ای از گراف های آرمانی می باشند که در مدت زمانی چندجمله ای شناسایی می شوند. اگر ورودی مسایلی همچون رنگ آمیزی گراف، گرافی وتری باشد در مدت زمانی چندجمله ای حل می شوند. طرد آرمانی و شناسایی بهینه. formula_1 یک ترتیب طرد آرمانی از رئوس گراف است به طوری که به ازای هر راس formula_2، زیرگراف القایی ناشی از رئوس formula_2 وهمسایه های آن در زیرگراف القایی ناشی از formula_4 گرافی کامل باشد. نشان دادند که یک ترتیب طرد آرمانی از گرافی وتری را می توان به طور بهینه با الگوریتمی به نام پیدا کرد. خوشه های فرین و رنگ آمیزی گراف. کاربرد دیگر ترتیب طرد آرمانی پیدا کردن خوشهٔ فرین در یک گراف وتری در مدت زمانی چندجمله ای است، در حالی که این مسئله در حالت کلی از مسائل NP-complete است. در حالت کلی یک گراف وتری تعدادی خطی خوشهٔ فرین دارد در حالی که این تعداد در گراف های دیگ
ر می تواند نمایی باشد. برای بدست آوردن خوشه های فرین از گراف وتری، ابتدا یک ترتیب طرد آرمانی (در صورت وجود) پیدا می کنیم. سپس از ابتدای این ترتیب شروع کرده و به ازای هر رأس formula_2 زیرگراف القایی ناشی از این رأس و رئوس قبلی آن در ترتیب را (که تشکیل خوشه می دهند) را در نظر می گیریم. خوشهٔ با اندازهٔ بیشینه در میان این خوشه ها، خوشهٔ فرین خواهد بود. از آنجا که گراف وتری آرمانی است، اندازهٔ خوشهٔ فرین، همان عدد رنگی گراف خواهد بود. گراف های وتری، هستند: با اعمال رنگ آمیزی حریصانه بر روی ترتیب معکوس طرد آرمانی می توان به طور بهینه آن را رنگ کرد. جداساز مینیمال. در هر گراف، مجموعه ای از رئوس است که با حذف آن ها گراف ناهمبند می شود. جداساز مینیمال است اگر هیچ زیرمجموعهٔ محضی از آن این ویژگی را نداشته باشد. برطبق قضیهٔ در گراف های وتری، هر جداساز مینیمال یک خوشه است. Dirac با این ویژگی آرمانی بودن گراف های وتری را اثبات کرد. گراف های وتری به طور استقرایی توسط گراف هایی تعریف می شوند که رئوس آن ها به سه زیرمجموعهٔ ناتهی formula_6 افراز شوند، به طوری که formula_7 و formula_8 هردو تشکیل یک زیرگراف القایی وتری دهند، f
ormula_9 خوشه باشد و هیچ یالی بین formula_10 و formula_11 نباشد. گراف تقاطع زیردرخت ها. ویژگی دیگر گراف های وتری مربوط به درخت و زیردرخت ها است. در یک درخت گراف تقاطع آن این گونه ساخته می شود: به ازای هر زیر درخت آن یک رأس در نظر می گیریم. دو رأس از این گراف مجاورند اگر زیردرخت متناظر آن ها در حداقل یک رأس مشترک باشند. نشان داد که این گراف، گرافی وتری است. نمایش گراف وتری به صورت تقاطع زیردرخت ها، یک درخت تفکیک با پهنا درخت یکی کمتر از بزرگترین خوشهٔ گراف بدست می دهد. درخت تفکیک هر گراف را می توان به صورت نمایش زیرگرافی از گراف وتری در نظر گرفت. درخت تفکیک، همان درخت اتصال در است. مکمل وتری و پهنا درخت. "مکمل وتری" گراف دلخواه formula_12، گرافی وتری است که formula_12 زیرگراف آن باشد. اگر formula_14 "مکمل وتری" گراف formula_12 با عدد خوشه ای (تعداد رئوس خوشهٔ بیشینه گراف) کمینه باشد، در آن صورت پهنادرخت formula_12 یکی کمتر از عدد خوشه ای formula_14 است. " k-درخت" گرافی است که افزودن یک یال به آن، پهنادرخت آن را بزرگتر از k می کند. بنابراین " k-درخت" مکمل وتری خودش است و رده ای از گراف های وتری را تشکیل می دهد.
ساموئل ماریل وودبریج (زاده ۵ آوریل ۱۸۱۹ و در گذشته ۲۳ ژوئن ۱۹۰۵ میلادی) روحانی، کشیش و استاد دانشگاه اهل آمریکا بود. وی اهل گرینفیلد، ماساچوست بود. ساموئل ماریل وودبریج از دانش آموختگان دانشگاه نیویورک بود و در دانشگاه راتگرز تدریس می کرد.
درخت تِنِرِه ، ، یک درخت تنهای آکاسیا (سَمُر) یا آکاسیای چتری بود که روزگاری به عنوان تنهاترین و دورافتاده ترین درخت جهان به حساب می آمد. (نزدیک ترین درخت، حدود ۴۰۰ کیلومتر از آن فاصله داشت) مکان این درخت در روزگاران پیش، محل توقف کاروان های عازم منطقه تنره در صحرای بزرگ آفریقا در شمال شرقی نیجر بود. این درخت و درخت "آربر پِردو" (درخت گم شده) تنها درختانی هستند که در نقشه ای با مقیاس ۱:۴۰۰٬۰۰۰ دیده می شوند. این درخت در سال ۱۹۷۳ توسط یک رانندهٔ کامیون احتمالاً مست زیر گرفته شد و از بین رفت. تاریخچه. درخت تنره، آخرین درخت از درختانی بود که روزگاری که هنوز صحرا چون امروز نبود در مکان فعلی قرار داشتند. در طول زمستان ۱۹۳۸–۱۹۳۹، چاهی در کنار این درخت حفر شد و متوجه شدند که ریشه های این درخت تا عمق ۳۳–۳۶ متری (۱۰۸ تا ۱۱۸ فوت) پیش رفته و به داخل سطح ایستابی رسیده است. در کتاب L'épopée du Ténéré، هنری لوت، نژادشناس و جهانگرد فرانسوی، به شرح دو دیدار خود از درخت تنره پرداخته است. او ابتدا در سال ۱۹۳۴ به طور تصادفی در سفر خود با اتومبیل از جانت به اغادیز، درخت تنره را دید و آنرا "یک درخت آکاسیا با بدنی پوسیده که مریض به
نظر می آید اما با این حال برگ های سبز زیبا و گل های زرد دارد" توصیف کرد. او ۲۵ سال بعد در ۲۶ نوامبر ۱۹۵۹ در طی عملیات برلیت-تنره از درخت تنره دوباره بازدید کرد اما درخت را از برخورد یک ماشین بسیار آسیب دیده یافت. مرگ. گفته می شود که درخت تنره در سال ۱۹۷۳ توسط یک راننده کامیون مست لیبیایی سرنگون شد. در ۸ نوامبر ۱۹۷۳، درخت مرده را به "موزه ملی نیجر" در نیامی منتقل کردند و به جای آن یک میله فلزی به عنوان یادبود قرار دادند.
الگوریتمی که پوش محدب اشیای مختلف را به دست می دهد کاربردهای وسیعی در ریاضیات و علوم کامپیوتر دارد. در هندسه محاسباتی، الگوریتم های متعددی با پیچیدگی های محاسباتی گوناگون برای محاسبه پوش محدب مجموعه ای محدود از نقاط مطرح شده است. محاسبه پوش محدب به معنی ارائه نمایشی نامبهم و کارا از شکل مطلوب می باشد. پیچیدگیهای الگوریتم های مربوطه معمولاً بر حسب n، تعداد نقاط ورودی، و h، تعداد نقاط درون پوش محدب، سنجیده می شوند. حالت دو بعدی. اگر همهٔ نقاط روی یک صفحه نباشند آنگاه پوش محدب حاصلچندظلعی محدبی می شود که رأس های آن زیر مجموعه ای از رأس های ورودی می باشد. معمولترین نمایش پوشه محدب به صورت لیستی از رأس های آن می باشد که ترتیب آن بر اساس پیمایشی ساعتگرد یا پادساعتگرد بر روی مرز پوش محدب می باشد. در بعضی از کاربردها نمایش این چندظلعی محدب به صورت اشتراک تعدادی نیم صفحه مناسب تر می باشد. کران پایین پیچیدگی محاسباتی. کران پایین محاسباتی برای پیدا کردن پوش محدب و نمایش آن به صورت چند ضلعی محدب، مشابه این کران برای مرتب سازی می باشد و به سادگی می توان این مطلب را با کاهش نشان داد. برای نقاط formula_1 که می خواهیم مرتب ک
نیم، نقاط formula_2 را بر روی صفحه در نظر بگیرید. حال چون این نقاط بر روی سهمی که منحنی محدب است قرار دارند به راحتی می توان دید که پیمایش بر روی مرز پوش محدب آن ها ترتیب مرتب شدهٔ این اعداد را می دهد. به وضوح زمان خطی برای تبدیل اعداد به نقاط و سپس به دست آوردن ترتیب مرتب شده، نیاز می باشد. از این رو به دست آوردن پوش محدب n نقطه نمی تواند سریعتر از مرتبسازی عمل کند. کران پایین محاسباتی استاندارد به کمک مدل درخت تصمیمformula_3 می باشد که البته در این مدل تنها مقایسه انجام می شود و نه عملیات محاسباتی. به هر حال پوش محدب در این مدل نمی تواند محاسبه شود. مرتب سازی در مدلدرخت تصمیم جبری نیز از formula_3 می باشد که این مدل برای پوش محدب مناسبتر می باشد که در این مدل نیز به دست آوردن پوش محدب ها زمانی از formula_3 می خواهد. هر چند در مدل هایی که اجازه می دهند که اعداد سریعتر از formula_6 مرتب شودند، برای نمونه الگوریتم هایinteger sorting، پوش محدب نیز می تواند سریعتر محاسبه شود: الگوریتم پیمایش گراهام شامل یک مرحله سادهٔ مرتب سازی است که به دنبال مقداری کار اضافه که در زمان خطی انجام می شوند امده اند. الگوریتم حساس
به خروجی بهینه. همان که در بالا ذکر شد پیچیدگی پیدا کردن پوش محدب به صورت تابعی از تعداد نقاط ورودی formula_3 می باشد. هر چند که پیچیدگی بعضی از الگوریتم های پوش محدب بر حسب سایز ورودی n و سایز خروجی h (تعداد نقاط روی پوش محدب) عنوان می شود. این گونه الگورتم ها حساس به خروجی نامیده می شوند. این الگوریتم ها ممکن است به طور مجانبی کارا تر از formula_3 باشند در حالتی که formula_9 کران پایین در بدترین حالت زمانی الگوریتم های مربوط به پوش محدب حساس به خروجی در حالت دوبعدی formula_3می باشد.الگوریتم های متعددی وجود دارند که این پیچیدگی بهینه را به دست می دهند. اولین آن ها در سال ۱۹۸۶ توسط Kirkpatrick و Seidel معرفی شد (که آن را الگوریتم نهایی پوش محدب نامیدند.)الگوریتم ساده تر توسط Chan در ۱۹۹۶ داده شد که الگوریتم چان نامیده شد. الگوریتم ها. الگوریتم های شناخته شدهٔ مربوط به پوش محدب در زیر لیست شده اند که آن ها را بر اساس اولین تاریخ انتشار مرتب کرده ایم. پیچیدگی زمانی این الگوریتم ها بر اساس تعداد نقاط ورودی n و تعداد نقاط روی پوش محدب h بیان شده اند. توجه شود که در بدترین حالت h ممکن است به بزرگی n باشد. یکی از
ساده ترین (اگر چه مؤثرترین در بدترین حالت نمی باشد) الگوریتم های صفحه ای می باشد که به طور مستقل توسط Chand و Kapur در ۱۹۹۰ و R.A.Jarvis در ۱۹۷۳ کشف شد. این الگوریتم دارای پیچیدگی زمانی formula_11 می باشد و در بدترین حالت این پیچیدگی از مرتبه formula_12 است. یک الگوریتم با کمی پیچیدگی بیشتر ولی کاراتر که در سال ۱۹۷۲ توسط رونالد گراهام انتشار یافت. اگر نقاط قبلاً بر اساس یکی از مؤلفه های مختصاتشان یا بر اساس زاویه با برداری ثابت مرتب شده باشند آنگاه این الگوریتم از formula_13 می باشد. به طور مستقل توسط W.Eddy در ۱۹۷۷ و A.Bykat در ۱۹۷۸ کشف شد. درست مانند مرتب سازی سریع به طور میانگین ازformula_14 است ولی ممکن است در بدترین حالت به formula_15 برسد. الگوریتم دیگری از formula_6 که در سال ۱۹۷۷ توسطPreparata و Hong انتشار یافت. این اگوریتم برای حالت سه بعدی نیز قابل اجرا می باشد. در سال ۱۹۷۹ توسط A.M.Andrew انتشار یافت. به این الگوریتم می توان به دید تغییر شکل یافتهٔ Graham scan نگاه کرد که در آن نقاط بر اساس مؤلفه هایشان مرتب می شوند. اگر نقاط ورودی از قبل مرتب شده باشند این الگوریتم از formula_13 خواهد بود. منشتر
شده در سال ۱۹۸۴ توسط Michael Kallay. اولین الگوریتم بهینه حساس به خروجی که در آن از تکنیک marriage-before-conquest استفاده می شود. در سال ۱۹۸۶ توسطKirkpatrick و Seidel انتشار یافت. الگوریتم بهینه و ساده تر حساس به خروجی که در سال ۱۹۹۶ توسط Chan کشف شد. الگوریتم ابتکاری (heuristic) Alk-Toussaint. ابتکار ساده ای که در ادامهٔ کار می آید اغلب اولین مرحله در پیاده سازی الگوریتم پوش محدب برای بهبود کارایی آن می باشد. پایهٔ آن بر اساس اگوریتمی کارا که در سال ۱۹۷۸ توسطSelim Akl و G.T.Toussaint ارائه شد. ایدهٔ کار به این صورت است که به طور سریع نقاطی که به هیچ وجه نمی توانند در پوش محدب باشند را حذف کنیم. این روش بر مبنای آن است که در ادامه می آید. دو نقطه ای را که دارای کمترین و بیشترین مختصات x می باشند و به همین ترتیب دو نقطه ای که دارای کمترین و بیشترین مختصات y اند را پیدا می کنیم.(این کار در formula_13 انجام می شود.)این چهار نقطه تشکیل یک چهار ظلعی محدب را می دهند و تمام نقاطی که در این چهار ظلعی قرار می گیرند (غیر از چهار نقطهٔ ابتدایی) نمی توانند درون پوش محدب باشند. پیدا کردن تمامی نقاطی که درون این چهار ظلعی