Payamvdn/NorthPersian_fa_wiki huggingface dataset:
ت را می توان با پرس و جو و زمان ساخت یکسان و فضای O(nlogn) به ابعاد بالاتر n تعمیم داد. اول یک درخت محدوده در ابعاد N ساخته شده است که اجازه بازیابی کارآمد از تمام فواصل با شروع و پایان نقاط در داخل منطقه پرس و جو Rرا می دهد. هنگامی که تمام بازه های مربوطه یافت شدند، تنها چیزی که باقی می ماند آن بازه هایی است که ناحیه را بعضی ابعاد در بر می گیرند. برای پیدا کردن این همپوشانی ها، N درخت بازه ای به وجود می آیند و یک محور متقاطع با R برای هرکدام پرس و جو می شود. برای مثال، در دو بعد، پایین مربع R (یا هر خط افقی متقاطع با R) در برابر درخت بازه ای ساخته شده برای محور افقی پرس و جو می شود. به همین ترتیب سمت چپی (یا هر خط عمودی متقاطع با R) در برابر درخت بازه ای ساخته شده بر محور عمودی پرس و جو می شود. هر درخت بازه ای به یک چیز اضافه در ابعاد بالاتر نیز نیاز دارد. در هر گره که ما آن را در درخت پیمایش می کنیم برای پیدا کردن تلاقی ها x با s_center مقایسه می شود. به جای دو لیست مرتب شده از بازه ها که در حالت یک بعدی مورد استفاده قرار می گرفت یک درخت محدوده ساخته می شود. این امکان بازیابی کارآمد تمام بازه های موجود در s
_center را (که با ناحیه R تلاقی دارند) فراهم می سازد. حذف. اگر پس از حذف یک بازه از درخت، گره شامل آن بازه شامل هیچ بازه دیگری نباشد، آن گره ممکن است از درخت حذف شود. این فرایند پیچیده تر از عملیات حذف در یک درخت معمولی دودویی است. یک بازه ممکن است با مرکز چند گره در درخت تلاقی داشته باشد. از آنجایی که هر گره بازه هایی را که با آن تلاقی دارند ذخیره می کند، به همراه تمام بازه های به طور کامل سمت چپ نقطه مرکز آن در زیر درخت سمت چپ و به طور مشابه برای زیر درخت راست. این نتیجه می دهد که هر بازه از بین بازه هایی که با مرکز آن ها تلاقی دارد در نزدیک ترین گره به ریشه ذخیره می شود. عملیات حذف عادی در یک درخت دودویی (برای حالتی که گره در حال حذف شدن دارای دو فرزند باشد) شامل ارتقاء یک گره دورتر از ریشه به جایگاه گره در حال حذف است (معمولاً چپ ترین درخت زیردرخت راست یا راست ترین درخت زیر درخت چپ). به عنوان یک نتیجه این ارتقاء، بعضی از گره هایی که بالای گره ارتقاء یافته بودند به نوادگان آن تبدیل خواهند شد. لازم است که این گره ها را برای بازه هایی که با گره ارتقاء یافته تلاقی دارند نیز جستجو کنیم و آن بازه ها را به داخل
گره های ارتقاء یافته منتقل کنیم. در نتیجه این ممکن است باعث ایجاد گره های خالی جدیدی شود که دوباره طبق همان الگوریتم باید حذف شوند. ایجاد تعادل. همان مسائلی که بر روی عملیات حذف تأثیر می گذارند، بر روی عملیات چرخش نیز تأثیر می گذارند. چرخش باید ثابتی را که بازه ها ذخیره شده اند تا حد امکان نزدیک به ریشه نگه دارد. درخت افزوده. هم درج و هم حذف از O(logn) زمان می برند، که n همان تعداد کل بازه هاست. از یک درخت ساده مرتب استفاده کنید. برای مثال یک درخت جستجوی دودویی یا یک درخت خود-متعادل جستجوی دودویی، که درخت بر اساس نقاط پایین بازه ها مرتب شده است و یک توضیح اضافه به هر گره اضافه شده است که ماکزیمم نقاط بالای بازه ها را در زیر درخت های آن نگه می دارد. به دست آوردن این صفت در طی تنها O(h) مرحله هنگام حذف یا درج یک گره کار ساده ای است، که h همان ارتفاع گره درج یا حذف شده به وسیله به روز رسانی همه اجداد گره از پایین به بالا در درخت می باشد. به علاوه، چرخش های درخت که در حذف و درج مورد استفاده قرار می گرفت، ممکن است نیاز به به روز رسانی قسمت بالای گره های مورد تأثیر داشته باشد. در حال حاضر مشخص است که دو بازه A و B
تلاقی دارند اگر و تنها اگر A.low ≤ B.high و A.high ≥ B.low. هنگام جستجوی درخت ها برای یافتن گره هایی که با یک بازه تلاقی دارند، شما می توانید بلافاصله از موارد زیر صرف نظر کنید: با مرتب کردن بازه ها ابتدا بر اساس مقدار پایین و سپس مقدار بالا یک ترتیب کلی را می توان برای بازه ها تعریف کرد. این مرتب سازی برای جلوگیری از درج بازه های تکراری در درخت در O(logn) می تواند در مقابل زمان o(k + logn) لازم برای یافتن تکرارها هنگامی کهk بازه با یک بازه جدید تلاقی دارند، مورد استفاده قرار گیرد. مثال Java : اضافه کردن یک بازه به درخت public void add(Interval i) { put(i, i.getEnd()); مثال Java : جستجو کردن یک نقطه یا بازه در درخت برای جستجو کردن یک بازه، باید درخت را پیمایش کرده و شاخه هایی را که نمی توانند شامل چیزهایی که شما به دنبال آن هستید باشند حذف کنید. حالت ساده جستجوی یک نقطه است: // Search for all intervals which contain "p", starting with the // node "n" and adding matching intervals to the list "result" public void search(IntervalNode n, Point p, List&lt;Interval&gt; result) { // Don't search nodes that don't ex
ist if (n == null) return; // If p is to the right of the rightmost point of any interval // in this node and all children, there won't be any matches. if (p.compareTo(n.getValue())&gt; 0) return; // Search left children if (n.getLeft() != null) search(IntervalNode (n.getLeft()), p, result); // Check this node if (n.getKey().contains(p)) result.add(n.getKey()); // If p is to the left of the start of this interval, // then it can't be in any child to the right. if (p.compareTo(n.getKey().getStart()) &lt;0) return; // Otherwise, search right children if (n.getRight() != null) search(IntervalNode (n.getRight()), p, result); کد جستجوی یک بازه هم مشابه است به جز چک کردن قسمت میانی: // Check this node if (n.getKey().overlapsWith(i)) result.add (n.getKey()); overlapswith() این گونه تعریف شده است: public boolean overlapsWith(Interval other) { return start.compareTo(other.getEnd()) &lt;= 0 &amp;&amp; end.compareTo(other.getStart())&gt;= 0; ابعاد بالاتر. این را می توان با چرخیدن در ابعاد مختلف در هر سطح از درخت به ابعا
د بالاتر گسترش داد!!! برای مثال، برای دو بعد، سطوح فرد درخت باید شامل محدوده هایی برای مختصات x و سطوح زوج باید شامل محدوده هایی برای مختصات x باشند. البته خیلی واضح نیست که منطق چرخشی چگونه باید برای چنین حالت هایی گسترش یابد تا درخت متعادل بماند. یک راه حل خیلی ساده تر استفاده از درخت های بازه ای تودرتو می باشد. ابتدا با استفاده از محدوده های y یک درخت بازه ای بسازید. حال برای هر گره درخت، برای همه عناصری که محدوده y آن ها با محدوده y آن گره اشتراک دارد، یک درخت بازه ای دیگر در محدوده x اضافه کنید. مزیت این راه حل این است که می تواند با یک کد پایه یکسان برای هر تعداد دلخواه از ابعاد گسترش یابد. در ابتدا هزینه درختان اضافی ممکن است سنگین به نظر برسد اما معمولاً چنین نیست. زیرا با راه حل فوق شما نیاز به یک گره در هر مختصات x دارید پس این هزینه در هر دو راه حل یکسان است. تنها تفاوت این است که شما نیاز به یک ساختار درختی اضافی در هر بازه عمودی دارید. این ساختار به طور معمول بسیار کوچک است. (یک اشاره گر به گره ریشه به علاوه شاید تعداد گره ها و ارتفاع درخت) درخت میانی / طول گرا. این درخت مشابه درخت افزوده است اما
به صورت متقارن. در حالی که درخت جستجوی دودویی بر اساس نقطه میانی بازه ها مرتب شده است و یک heap دودویی حداکثر گرا در هر گره وجود دارد و بر اساس طول بازه ها (یا نصف طول آن) مرتب شده است. همچنین ما به علت تقارن، علاوه بر بیشترین مقدار ممکن، حداقل مقدار ممکن در زیر درخت را نیز در هر گره ذخیره می کنیم. آزمون همپوشانی. فرض کنیم دو بازه (a0, b0) , (a1, b1) را داریم. ابتدا و انتهای این بازه ها نسبت به یکدیگر می توانند یکی از 4 حالت زیر را داشته باشند: formula_1 OR formula_2 OR formula_3 OR formula_4 اما با تعریف 2 متغیر زیر: formula_5 formula_6 تست هم پوشانی راحت تر خواهد شد: formula_7 اضافه کردن بازه. اضافه کردن یک بازه به درخت بازه ها شبیه اضافه کردن در درخت جستجوی دودویی است تنها با این تفاوت که از وسط بازه به عنوان کلید مقایسه برای پیدا کردن یا ساختن گره مناسب برای درج بازه diاستفاده می شود. باید diرا در پشته دودویی نظیرشده به گره درج کنیم و برای تمامی گره هایی که در درخت بازه ها بالاتر از گره مدنظر هستند، مقدار کمینه و بیشینه نظیر به آن ها را به روز رسانی کرد. جستجو برای یافتن تمامی بازه های هم پوشا. از متغیره
ای aq, bq, mq, dq برای بازه پرسش شده و از Mn برای کلید گره ای که (که با mi بازه ها مقایسه می شود) استفاده می کنیم.از گره ریشه شروع می کنیم. برای هر گره (که روی آن هستیم) ابتدا از طریق مقایسه کردن مقادیر ابتدا و انتهای بازه نظیر به گره بررسی می کنیم آیا بازهٔ پرس و جو شده ما با گره های زیر درخت های گره فعلی می تواند هم پوشانی داشته باشد یا نه؟ اگر جواب منفی بود این روش را برای گره های زیر درخت های گره فعلی ادامه نمی دهیم. سپس ما را برای بازه های درون گره فعلی (نه فرزندهایش) برای بررسی هم پوشانی محاسبه می کنیم: (می دانیم ) و برای هایی که از بزرگتر باشند یک درخواست روی Binary Heap می زنیم. سپس همین عمل را برای فرزندان راست و چپ گره انجام می دهیم. در بدترین حالت ما مجبور به دیدن تمامی گره های BST هستیم اما از آنجایی که درخواست روی Binary Heap بهینه است نباید نگران مرتبه الگوریتم باشیم. (یک مسئله دو بعدی نمی تواند در هر دو بعد بهینه باشد) انتظار می رفت که این الگوریتم از than traditional Interval Tree (Augmented tree) در عملیات جستجو سریعتر باشد درحالی که تنها کمی کندتر است و این اختلاف تأثیری در مرتبه زمانی ندارد
. (مرتبه زمانی هر دو یکی است و تفاوت در ضرایب آن است)
مسئله نقطه در چندضلعی در هندسه محاسباتی مسئلهٔ تعیین قرارگیری یک نقطهٔ مشخص نسبت به یک چندضلعی داده شده است. یک نقطه می تواند داخل، خارج یا روی محیط چندضلعی قرار داشته باشد. این مسئله حالت خاص مسئلهٔ محل یابی نقطه است و در زمینه های پردازش اطلاعات گرافیکی، مانند گرافیک رایانه ای، بینایی رایانه ای، سامانه اطلاعات جغرافیایی، برنامه ریزی حرکت و طراحی رایانه ای کاربرد دارد. ایوان سودرلند در سال ۱۹۷۴ دو راه حل (انتشار پرتو و جمع زوایا) برای این مسئله ارائه داد. تاریخچهٔ این مسئله و چند راه برد برای حل آن در یکی از شماره های مجلهٔ Ray Tracing News به چاپ رسیده است. الگوریتم انتشار اشعه. یک راه ساده برای آزمودن قرارگیری نقطه در داخل یک چندضلعی ساده، شمارش تعداد دفعات تقاطع یک پرتوی دلخواه با شروع از نقطهٔ مورد نظر با چندضلعی داده شده است. اگر نقطه داخل چندضلعی قرار داشته باشد، تعداد تقاطع ها فرد باشد نقطه داخل چندضلعی قرار دارد و اگر زوج باشد، نقطه خارج چندضلعی قرار دارد. از این الگوریتم با نام الگوریتم تعداد تقاطع یا الگوریتم قاعدهٔ زوج و فرد نیز یاد می شود و حداقل در سال ۱۹۶۲ کشف شده بوده است. این الگوریتم بر اساس
این ایدهٔ ساده است که اگر یک نقطه از بی نهایت در جهت دلخواه حرکت کند و چندضلعی را چند بار قطع کند، در این صورت با هر بار قطع کردن چندضلعی به طور متناوب یک بار از بیرون چندضلعی به درون آن و یک بار از درون چندضلعی به بیرون آن جابجا می شود. در نتیجه با هر دو بار قطع کردن چندضلعی در همان سمت چندضلعی باقی می ماند. این مشاهده را می توان به طور ریاضیاتی توسط قضیهٔ خم جردن اثبات کرد. اگر این الگوریتم در رایانه ای با ممیز_شناور پیاده سازی شود و نقطهٔ مورد نظر نزدیک مرز چندضلعی باشد، ممکن است این الگوریتم جواب نادرست دهد. البته این ایراد زیاد حائز توجه نیست، زیرا آن چه بیشتر مورد توجه است زمان اجرای الگوریتم است و نه صحت کامل الگوریتم. با این وجود برای اصلاح این مشکل، ثابت آنالیز_عددی رواداری_(مهندسی) با نام formula_1 تعریف می کنیم و قبل از اجرای الگوریتم بررسی می کنیم که اگر فاصلهٔ نقطه تا اضلاع چندضلعی کمتر از formula_1 باشد، الگوریتم را متوقف کرده و نزدیک بودن بیش از اندازهٔ نقطه به اضلاع چندضلعی را گزارش می دهیم. برای پیاده سازی این الگوریتم معمولاً به این صورت عمل می شود که وجود تقاطع بین پرتو و اضلاع متوالی چندض
لعی بررسی می شوند. در چنین پیاده سازی ای باید به این مسئله توجه کرد که اگر پرتو از رأس_(هندسه) مشترک دو ضلع چندضلعی عبور کند، آن گاه این تقاطع دو بار شمرده می شود. در مثال این بخش، این اتفاق در مورد بالاترین راس مشکلی ایجاد نمی کند ولی در مورد راست ترین راس، باعث بروز جواب نادرست خواهدشد. این مشکل را به این صورت برطرف می کنیم: اگر نقطهٔ تقاطع پرتو و یک ضلع، یکی از دو انتهای ضلع بود، در این صورت این تقاطع را تنها در صورتی شمارش می کنیم (و فقط یک بار شمارش می کنیم) که دو ضلع مجاور آن راس در دو طرف پرتو قرار گرفته باشند. این کار معادل این است که راس مورد نظر را اندکی به سمت بالای پرتو جابجا کرده باشیم. مسئلهٔ عبور پرتو از رئوس در ممیز_شناور نیز مشکل ساز خواهدبود. در صورتی که پرتو از یک راس عبور کند، ممکن است که هنگام بررسی تقاطع دو ضلع مجاور، در هر دو مورد متوجه قرار گرفتن نقطهٔ تقاطع روی انتهای ضلع نشویم. اگر چندضلعی به وسیلهٔ رئوسش مشخص شده باشد، می توان قبل از محاسبهٔ محل نقطهٔ تقاطع بررسی کرد که آیا پرتو از یکی از رئوس مجاور ضلعی مورد بررسی می گذرد یا خیر. اگر چندضلعی به وسیلهٔ اطلاعاتی به جز رئوس آن مشخص شد
ه باشد، باید از روش های دیگری برای اطمینان از درستی محاسبات استفاده کرد. الگوریتم عدد پیچش. الگوریتم دیگر حل این مسئله الگوریتم محسابهٔ عدد پیچش نسبت به چندضلعی است. اگر این عدد ناصفر باشد نقطه در درون چندضلعی قرار دارد. برای محاسبه عدد پیچش، می توان زوایای داخلی متناظر با هر یک از اضلاع چندضلعی را جمع کرد. اما این روش به دفعات از معکوس توابع مثلثاتی استفاده می کند که باعث می شود در حالت کلی الگوریتم انتشار اشعه از نظر زمانی بهتر باشد. خوشبختانه لزومی به محاسبهٔ این معکوس توابع مثلثاتی نیست، چرا که نتیجه، یعنی جمع کل زوایای متناظر اضلاع، یا formula_3 است یا formula_4 (یا هر مضربی از formula_4 ). پس فقط کافی است که حرکت چندضلعی را در ربع های مختصاتی حول نقطهٔ مورد نظر را دنبال کنیم. به این صورت این الگوریتم از نظر سرعت قابل مقایسه با الگوریتم انتشار پرتو خواهدبود. مقایسه. برای چندضلعی ساده هر دو الگوریتم به ازای هر نقطهٔ ورودی جواب یکسانی را تولید خواهندکرد. اما برای چندضلعی غیرساده این دو الگوریتم ممکن است نتایج متفاوتی تولید کنند، مانند حالتی که چندضلعی خودش را قطع می کند یا وقتی که تعریف درون و بیرون چندضلع
ی دقیقاً مشخص نیست. پرسمان های نقطه در چندضلعی. مسئلهٔ نقطه در چندضلعی را می توان نوعی نوعی از پرسمان هندسی مکرر دانست. یعنی بخواهیم با داشتن یک چندضلعی مشخض، قرار داشتن هر یک از اعضای یک دنباله از نقاط را در داخل چندضلعی بررسی کنیم. روشن است که می توان از هر یک از الگوریتم های مکان یابی نقطه در صفحهٔ مسطح برای حل این نوع مسائل استفاده کرد. راه حل های ساده تری نیز برای برخی چندضلعی های خاص وجود دارند. حالت های خاص. الگوریتم های بهتری برای چند ضلعی های یکنوا، ستاره گون یا محدب وجود دارند.
رادیو سوئد () بنگاه سخن پراکنی بین المللی کشور سوئد است. زبان ها. تا سال ۲۰۱۲، رادیو سوئد اقدام به پخش به زبان های زیر کرده است:
الگوریتم لمکه-هاوسون الگوریتمی برای محاسبه تعادل نش در بازی دوماتریسی (ماتریسی که در هر خانه اش دو عنصر دارد) است گفته می شود که این الگوریتم بهترین الگوریتم ترکیبیاتی برای یافتن تعادل نش است. الگوریتم. ورودی الگوریتم یک بازی دو نفره G است. بازی G به صورت دو ماتریس n × m با نام A و B داده می شود که هر کدام از آنها شامل نتایج نهایی برای یکی از بازیکنان شماره ۱ و ۲ است که هر کدام به ترتیب، m و n استراتژی خالص دارند. در ادامه فرض می کنیم که نتایج مثبت هستند (هر بازی با تغییر مقیاس می تواند به بازی برابری از نظر استراتژی با نتایج مثبت تبدیل شود). بازی G دو چند وجهی متناظر دارد (که بهترین پاسخ بین چند وجهی ها نامیده می شوند)، به اسم های P۱ و P۲ که هر کدام به ترتیب m و n بعد دارند. در ادامه به تعریف این دو ماتریس می پردازیم. ماتریس P۱ در R"m" است. فرض کنید {"x"۱... ,"x""m"} مختصات را نشان می دهد. P۱ به وسیله m نامساوی "xi" ≥ ۰ برای همه {"i" ∈ {۱، ... , "m" و n نامساوی B۱،j"x"۱+... +B"m","j""x"m ≤ ۱ برای همه {"j" ∈ {۱، ... , "n" تعریف می شود. ماتریس P۲ در R"n" است. فرض کنید {"x""m"+۱, ... , "x""m"+"n"} مختصات را نشا
ن می دهد. P۲ به وسیله n نامساوی "x"m"+"i"" ≥ ۰ برای همه {"i" ∈ {۱، ... , "n" و m نامساوی A"i"،۱"x""m"+۱+... +A"i","n""x""m"+"n" ≤ ۱ برای همه {"i" ∈ {۱، ... , "m" تعریف می شود. ماتریس "P"۱ نشان دهنده مجموعه توزیع های احتمالاتی نُرمالایز نشده برای m استراتژی بازیکن اول است، هنگامی که نتیجه مورد انتظار بازیکن دوم حداکثر یک باشد. برای برقراری m شرط اول باید احتمالات نامنفی باشند و هر یک از n شرط بعد هم باعث می شود که n استراتژی خالص بازیکن دوم نتایجی با مقدار حداکثر یک داشته باشند. اگر نقش دو بازیکن را با هم عوض کنیم، ماتریس "P"۲ نیز به همین ترتیب تعریف می شود. هر رأس v از ماتریس "P"۱، با مجموعه ای از برچسب ها (مقادیر) از مجموعه {۱،... ,"m" + "n"}، در ارتباط است. برای هر {"i" ∈ {۱، ... , "m" رأس v برچسب «i» را می پذیرد در صورتی که در رأس v شرط «"x"i"" = ۰» برقرار باشد. برای هر "j" ∈ {۱، …, "n"}، v برچسب «m + j» را می پذیرد در صورتی که شرط «"B"۱،"j""x"۱ + ... + "B""m","j""x""m" = ۱» برقرار باشد. فرض کنید که "P"۱ غیر تبهگن (nondegenerate) باشد، هر رأس بر m بعد از ماتریس "P"۱ واقع است و m برچسب دارد. دقت کنید که ریش
ه که خود یک رأس از "P"۱ می باشد، برچسب های {۱، …, m} را دارد. هر رأس w از از ماتریس "P"۲ با مجموعه ای از برچسب ها از مجموعه {۱، …, "m + n"}، در ارتباط است. برای هر {"j" ∈ {۱، …, "n" رأس w برچسب «m + j» را می پذیرد در صورتی که در رأس w شرط «" x"m"+"j"" = ۰» برقرار باشد. برای هر "i" ∈ {۱، …, "m"}، w برچسب «i» را می پذیرد در صورتی که شرط «"A""i"،۱"x""m"+۱ + ... + "A""i","n""x""m"+"n" = ۱» برقرار باشد. فرض کنید که P۲ غیر تبهگن باشد، هر رأس بر m بعد از ماتریس P۲ واقع است و m برچسب دارد دقت کنید که ریشه که خود یک رأس از P۲ می باشد، برچسب های {m + ۱، …, "m + n"} را دارد. عمل محوری شامل گرفتن زوج مرتبی مانند ("v", "w")، و عوض کردن v با یکی از همسایه هایش در P۱ است یا عوض کردن w با یکی از همسایه هایش در P۲. در عمل محوری رأسی که عوض می شود را رها شده می نامیم. مثلاً اگر طی یک عمل محوری یک رأس از P۱ جایگزین v شود، به اصطلاح می گوییم «v رها می شود». به ازای هر مقدار از v، می شود با انتقال به یک رأس همسایه که شامل ابرصفحه مرتبط با آن برچسب نباشد، آن برچسب را رها کرد. الگوریتم از زوج (v, w) شروع می شود که کاملاً برچسب گذار
ی (مقدار دهی) شده است که این زوج شامل زوج ریشه ها می باشد. برچسب دلخواه g را به دلخواه با انجام یک عمل محوری رها می کنیم. در نتیجه زوج مرتب ما به زوج تقریباً برچسب گذاری شدهٔ (’v’, w) تبدیل می شود (زوجی که تنها یک عنصر برچسب گذاری نشده دارد). هر زوج تقریباً برچسب گذاری شده (زوج مرتبی که تنها یک عنصر برچسب گذاری نشده دارد) دو عمل محوری می پذیرد که این عمل متناظر با رها کردن یک عنصر یا ایجاد یک کپی از برچسب های تکراری آن زوج می باشد. هر یک از این اعمال سرانجام به یک زوج کاملاً یا تقریباً برچسب گذاری شده ختم می گردد. در نهایت الگوریتم زوج مرتب کاملاً برچسب گذاری شدهٔ ("*"v"*", w) را بدست می آورد که مخالف ریشه است. زوج مرتب ("*"v"*", w) با یک زوج مرتب از توزیع های احتمالاتی نُرمالایز نشده متناظر است که در آن هر استراتژیِ بازیکن شماره یک مانند «i»، یا به بازیکن شماره یک می پردازد یا باید کمتر از یک واحد بپردازد و بازی با احتمال ۰ توسط آن بازیکن (بازیکن شماره یک) انجام می شود (برای بازیکن شماره دو نیز به همین ترتیب). با نُرمالایز کردن این مقادیر به توزیع های احتمال، تعادل نش بدست می آید (که در آن مقدار پرداختی به ب
ازیکنان برابر وارون عوامل نرمال سازی می باشد). خصوصیات الگوریتم. این الگوریتم حداکثر می تواند تا «n + m» تعادل نش متفاوت بیابد. هر برچسبی که در مرحله اولیه برای رها شدن انتخاب شود، تعیین کننده تعادل نشی است که الگوریتم می یابد. الگوریتم لمکه-هاوسون معادل رویکرد مبتنی بر هوموتوپی زیر است. بازیِ G را اینگونه تغییر می دهیم که یک استراتژی خالص دلخواه مانند g را انتخاب می کنیم و به بازیکنی که آن استراتژی را داشت مقدار زیاد «B» را می پردازیم تا حتماً آن را بازی کند. در این بازی تغییر یافته، می دانیم که استراتژی g با احتمال ۱ به وقوع می پیوندد و بازیکن مقابل نیز در جواب با احتمال ۱ بهترین بازی ممکن خود را انجام می دهد. زنجیره ای از بازی را در نظر بگیرید که در آن B به طور مداوم کاهش می یابد و به صفر میل می کند. یک مسیر تعادل نش وجود دارد که تعادل نش منحصربه فرد بازی جدید را به تعادلی در بازی اصلی G می رساند. استراتژی خالص انتخاب شدهٔ g برای دریافت جایزهٔ B، به برچسبی که در ابتدا رها می شود بستگی دارد. در حالی که این الگوریتم در عمل بهینه و کارآمد است، در بدترین حالت تعداد عملیات محوری لازم ممکن است تابعی نمایی از تعد
اد تمام استراتژی های خالص بازی باشد. متعاقباً نشان داده شده است که یافتن هر جوابی که با الگوریتم لمکه-هاوسون بدست می آید PSPACE-complete می باشد.
گروه هوانوردی داسو یک شرکت هواپیماسازی فرانسوی تولیدکننده هواپیماهای نظامی و هواپیماهای جت سفارشی و شخصی است که از زیرمجموعه های گروه صنعتی داسو محسوب می شود. مارسل داسو مهندس فرانسوی و از مخترعان علمی هواپیما در سال ۱۹۲۹ این شرکت هواپیماسازی را تأسیس کرد. داسو تنها شرکت هوانوردی دنیاست که هنوز در مالکیت خانواده بنیانگذار آن قرار دارد و نام آن ها هنوز بر روی آن مانده است. دفتر مرکزی شرکت داسو در پاریس پایتخت فرانسه قرار دارد و در بیش از ۸۳ کشور دنیا فعالیت تجاری دارد. حدود ۱۱۶۰۰ کارمند در گروه هوانوردی داسو مشغول به کار هستند که ۹۰۰۰ نفر آن در کارخانجات و دفاتر این شرکت در فرانسه کار می کنند.بیش از ۴۰ درصد سهام این شرکت و بیش از ۶۰ درصد حق رای شرکت در دست دولت فرانسه می باشد از معروفترین تولیدات این شرکت هواپیماهای جنگنده سری میراژ از جمله میراژ ۳، میراژ اف۱ و میراژ-۲۰۰۰، جنگنده چند منظوره داسو رافال، جنگنده ضربتی سوپر اتاندارد و جت های تجاری سری فالکن از جمله داسو فالکون ۱۰ , داسو فالکون ۲۰ , داسو فالکون ۵۰ , داسو فالکون ۹۰۰ , داسو فالکون ۲۰۰۰ , داسو فالکون ۷ایکس هستند. منابع. Wikipedia contributors, "Dassau
lt_Aviation," Wikipedia, The Free Encyclopedia, (accessed December 21, 2009).
مسائل هیلبرت شامل بیست و سه سؤال ریاضی است که در سال ۱۹۰۰ توسط ریاضی دان آلمانی، دیوید هیلبرت منتشر شد. مسائل همگی در آن زمان حل نشده بودند و بعضی از آن ها هنوز هم حل نشده اند. این مسائل تأثیر بسزایی بر ریاضیات قرن بیستم گذاشتند. هیلبرت ۱۰ تا از این سؤالات (۱ ،۲ ،۶ ،۷ ،۸ ،۱۳ ،۱۶ ،۱۹ ،۲۱ و ۲۲) را در کنگره جهانی ریاضیدانان، در هشتم اوت در سوربن پاریس ارائه کرد. لیست کاملی از ۲۳ سؤال بعدها در مجلهٔ انجمن ریاضی آمریکا عمدتاً با ترجمهٔ انگلیسی ماری فرانسیس وینستون نیوسون آمد. طبیعت و اثر مسائل. مسائل هیلبرت از لحاظ محتوا و دقت متفاوت هستند. بعضی از آن ها مانند سؤال سوم (احتمالاً راحت ترین سؤال برای درک توسط غیرمتخصص ها و اولین سؤال حل شده از بین مسائل) یا سؤال مشهور هشتم (فرضیهٔ ریمان)، به اندازه ای دقیق تعریف شده اند که جوابی روشن برای رد یا قبولشان وجود دارد. مسائل دیگری (مانند مسئلهٔ ۵) وجود دارند که متخصصان به تفسیری واحد از مسئله رسیده اند و پاسخی نیز برای آن تفسیر ارائه شده ولی به نظر می رسد هنوز بخشی از مسئله که شاید مورد نظر هیلبرت نیز بوده بدون حل باقی مانده است. گاهی بیان هیلبرت به اندازه ای دقیق نیست که
مسئله مشخصی را مشخص کند ولی باعث تعریف مسائل مشخصی در حیطهٔ مورد نظر شده است. برای مثال بسیاری از دانشمندان حوزهٔ نظریهٔ اعداد احتمالاً سؤال ۹ام را اشاره ای به تناظر لنگلندز به نمایندگی از گروه گالوایی مطلق یک میدان عددی می دانند. مسائل دیگری (مانند مسئله ۱۱ام و ۱۶ام) مورد توجه رشته های فرعی در حال پیشرفت ریاضی مانند نظریه فرم های درجه دوم و خم های جبری حقیقی قرار گرفته اند. مسائل ۶ام و ۴ام نه تنها هنوز حل نشده اند بلکه با توجه به استانداردهای جدید قابل حل نیستند. مسئلهٔ ششم، ساختاری اصول مند برای فیزیک می خواست، که با توجه به پیشرفت های قرن بیستم فیزیک (از جمله اینکه به عنوان شاخه ای مستقل از ریاضی شناخته شد) به نظر می رسد دیگر اهمیت زمان هیلبرت را ندارد. همچنین سؤال چهارم که ساختار هندسه را در نظر داشت به نظر می رسد که دیگر جواب قطعی ندارد. بیست ویک مسئلهٔ دیگر همگی مورد توجه زیاد ریاضی دانان قرار گرفتند و کار روی آن ها اهمیت زیادی داشت به گونه ای که پل کوهن برای کارش روی مسئلهٔ اول در سال ۱۹۶۶ و یوری ماتیاسویچ برای ارائهٔ پاسخ منفی سؤال دهم (ادامهٔ کار مارتین دیویس، هیلاری پاتنم، جولیا رابینسون) در سال ۱۹
۷۰ مدال فیلدز گرفتند، و اثبات تقیض راه حل مسئلهٔ دهم در دههٔ ۱۹۷۰ توسط ماتیاسویچ نیز فیلدز را به خود اختصاص داد. جنبه های این مسائل همچنان یکی از مورد علاقه ترین زمینه های تحقیق امروزی است. ابهام. بعضی از مسائل هیلبرت به گونه ای عجیب یا حتی اذیت کننده برای هیلبرت حل شده اند. هیلبرت پیرو فرگه و راسل به دنبال تعریف منطقی با استفاده از دستگاه صوری، یعنی اثبات هایی متناهی از اصول موضوعهٔ پذیرفته شده، برای ریاضیات بود. یکی از مسائل هیلبرت (مسئلهٔ دوم) در واقع خواستار اثباتی متناهی برای استحکام اصول موضوعهٔ منطق است. به هر حال تئوری عدم کمال دوم گودل با دقت نشان می دهد که می توان ثابت کرد که چنین اثبات متناهی برای استحکام منطق غیرقابل ارائه است. هیلبرت ۱۲ سال بعد از گودل زندگی کرد ولی به نظر نمی رسد جواب رسمی به کارهای گودل نوشته باشد. بدون شک کارهای گودل بر روی کل ریاضیات (و نه تنها منطق) بسیار حائز اهمیت است هر چند که باعث حل شدن عجیب و شاید ناراحت کنندهٔ یکی از سؤالات هیلبرت شد. مسئلهٔ دهم هیلبرت نمی پرسد که آیا الگوریتمی برای حل معادلهٔ دیوفانتی وجود دارد یا نه. بلکه ساختار چنین الگوریتمی را مورد نظر دارد. «ارا
ئهٔ پروسه ای که با انجام متنهای عمل بتوان معین کرد که آیا یک معادله در اعداد گویا قابل حل است یا خیر.» حل این مسئله که نشان می داد چنین الگوریتمی وجود ندارد برای وی بسیار عجیب بود. با توجه به نظر وی که هر مسئلهٔ ریاضی حتماً راه حلی دارد او این اجازه را داد که راهحل مسئله اثبات این باشد که حل مسئله اصلی امکان پذیر نیست. مشهور است که او بیان کرده مهم این است که آیا راه حلی وجود دارد یا نه؛ و او عقیده داشت که ما همواره می توانیم این نکته را بفهمیم؛ یعنی در ریاضیات گزارهٔ دارای ابهام (گزاره ای که هرگز ارزش درستی آن معلوم نشود) وجود ندارد. واضح نیست که آیا او پاسخ سؤال دهم را دارای ابهام تلقی کرده است یا نه: آنچه که ما اثبات نمی کنیم که مسئله پاسخ طبیعی ندارد بلکه تنها می توانیم بفهمیم که آیا مسئله در حالت کلی دارای جواب است یا خیر. از سوی دیگر وضعیت مسئلهٔ اول و دوم پیچیده تر است. هیچ اتفاق نظر واضح ریاضی وجود ندارد که آیا نتایج گودل (در مورد سؤال دوم) یا گودل و کوهن (در مورد سؤال اول) جواب منفی قطعی به مسئله می دهند یا نه. از آنجایی که این راه حل ها به شکل خاصی از سؤال جواب می دهند و ممکن این شکل بندی تنها شکل ب
ندی موجود برای این دو مسئله نباشد. مسئله بیست وچهارم. هیلبرت در واقع ۲۴ مسئله در لیستش آورده بود ولی از انتشار سؤال بیست وچهارم جلوگیری کرده بود. مسئله بیست وچهارم (ملاکی برای سادگی در نظریهٔ اثبات) توسط رودیگر تیله تاریخ دان آلمانی از دست نوشته های هیلبرت به دست آمد. دنباله. از سال ۱۹۰۰ ریاضیدانان و مراکز ریاضی لیست هایی از مسائل را منتشر می کردند ولی این لیست ها به اندازهٔ مسائل هیلبرت تأثیر نداشت و برای ریاضی دانان کار ایجاد نمی کرد! یکی از موارد استثنای این لیست ها سه حدسی بودند که توسط آندره وِیل در اواخر دههٔ چهل میلادی ارائه شد (حدس های وِیل). حدس های ویل در زمینهٔ هندسهٔ جبری و نظریهٔ اعداد و ارتباط بین این دو بسیار مهم بودند. حدس اول توسط برنارد دیوُرک اثبات شد و اثباتی کاملاً متفاوت برای حدس اول و دوم توسط الکساندر گروتندیک با استفاده از همریختی مرتبهٔ اول ارائه شد. آخرین و عمیق ترین حدس وِیل توسط پییِر دلین! اثبات شد. هر دوی گروتندیک و دلین! مدال فیلدز گرفتند؛ ولی حدس های ویل در زمینهٔ خود به اندازهٔ یک سؤال هیلبرت اهمیت دارند و ویل هرگز آن ها را برنامه ای برای ریاضیات نخواند. این کمی طعنه آمیز است