payamvha/North_RAG huggingface dataset:
او با تصویب فرمانی مبنی بر نکته «ایمان هدیه خداوند»، محدودیت‌های مذهبی را فراتر از استانداردهای اروپایی در اواخر قرن شانزدهم لغو کرد. ساپویائی سرانجام به‌عنوان پادشاه منتخب مجارستان در کنار گذاشته‌شد و در جایگاه پرنس ترانسیلوانی و فرمانروای بخش‌هایی از پادشاهی مجارستان حکومت کرد. پس از درگذشت او بدون وارث ایشتوان باتوری معتقد به کلیسای کاتولیک جانشین او شد.
صدق‌پذیری یا ارضاپذیری در دانش رایانه پرسمانی است که می‌پرسد آیا می‌توان ارزش متغیرهای فرمولی دودویی را به گونه‌ای یافت که فرمول درست باشد؟ بنابراین اگر چنین ارزش‌دهی پیدا شود، گوییم پرسمان "صدق‌پذیر" است. وگرنه، بی‌گمان این فرمول همواره نادرست است و گوییم که فرمول "صدق‌ناپذیر" است. برای نمونه، فرمول formula_1 صدق‌پذیر است چون اگر ارزش‌های formula_2 و formula_3 درست باشند، فرمول همواره درست است. پرسمان صدق‌پذیری نخستین پرسمانی است که ان‌پی کامل بودنش نشان داده شده‌است. کوک و لوین نشان دادند الگوریتمی
داده شده‌است. کوک و لوین نشان دادند الگوریتمی شناخته‌شده‌ای نیست که در زمانی کوتاه پرسمان صدق‌پذیری را حل کند. محدودهٔ وسیعی از بقیهٔ مسائل تصمیم‌گیری و بهینه‌سازی طبیعی می‌توانند به موارد مسئلهٔ صدق‌پذیری تبدیل شوند. یک رده از الگوریتم‌ها به نام حل‌کننده‌های SAT به‌طور کارآمد می‌توانند زیرمجموعه‌ای به اندازهٔ کافی بزرگ از موارد SAT را حل کنند تا در حوزه‌های مختلف عملی از جمله طراحی مدار و قضیهٔ اثبات اتوماتیک مفید باشند. وسیعتر کردن قابلیت‌های الگوریتم‌های حل‌کنندهٔ SAT یک حوزهٔ در حال پیشرفت است. هرچند
حل‌کنندهٔ SAT یک حوزهٔ در حال پیشرفت است. هرچند هیچ‌کدام از روش‌های کنونی نمی‌توانند "همه‌ی" موارد مسئلهٔ صدق‌پذیری را به‌طور کارآمد حل کنند. تعریف‌ها، واژگان و کاربردها. در نظریه پیچیدگی محاسباتی مسئلهٔ صدق‌پذیری یک مسئلهٔ تصمیم است که نمونهٔ آن یک عبارت بولی می‌باشد که فقط با AND، OR، NOT، متغیرها و پرانتز نوشته شده‌است. سؤال این است که: آیا می‌توان به متغیرها مقادیر "درست" و "نادرست" داد تا عبارت موردنظر همواره درست باشد؟ یک فرمول از منطق گزاره‌ای صدق‌پذیر است اگر به متغیرهای آن بتوان مقادیر منطقی داد
است اگر به متغیرهای آن بتوان مقادیر منطقی داد تا فرمول همواره درست باشد. مسئلهٔ صدق‌پذیری دودویی یک ان‌پی کامل است. مسئلهٔ صدق‌پذیری گزاره‌ای (PSAT)، که مشخص می‌کند آیا یک فرمول گزاره‌ای صدق‌پذیر هست یا نه، مهم‌ترین مسئله در حوزه‌های مختلف علوم رایانه است؛ نظیر علوم نظری رایانه، الگوریتم‌ها، هوش مصنوعی، طراحی پردازنده، اتوماسیون طراحی الکترونیکی و تایید. یک متغیر یا خود آن متغیر یا نقیضش است. به‌طور مثال x۱ یک متغیر مثبت و (not(x۲ یک متغیر منفی است. یک عبارت فصل منطقی از متغیرهاست. به‌طور مثال (x۱ V not(x۲
فصل منطقی از متغیرهاست. به‌طور مثال (x۱ V not(x۲ یک عبارت است. در بعضی حالت‌های مسئله صدق‌پذیری دودویی، نیاز است که فرمول عطف منطقی چند عبارت باشد. حالتی که صدق‌پذیری یک فرمول به شکل عطف معمولی را بررسی می‌کنیم که هر عبارت حداکثر دارای سه متغیر باشد، ان‌پی کامل است؛ این مسئله "۳SAT" یا "۳CNFSAT" یا "۳-صدق‌پذیری" نامیده می‌شود. حالتی که فرمول موردبررسی دارای عبارت‌هایی با حداکثر دو متغیر باشد، ان‌ال کامل است؛ این مسئله "۲SAT" نامیده می‌شود. حالتی که فرمول موردبررسی دارای عبارت‌های هورن (که حداکثر یک متغیر
دارای عبارت‌های هورن (که حداکثر یک متغیر مثبت دارند.) باشد، پی کامل است؛ این مسئله صدق‌پذیری هورن نامیده می‌شود. قضیه کوک لوین عنوان می‌کند که مسئله دودویی صدق‌پذیری یک ان‌پی کامل است، در واقع این اولین مسئله‌ایست که اثبات شده ان‌پی کامل است. پیچیدگی و نسخه‌های محدود. ان‌پی کامل. همانطور که استفن کوک در سال ۱۹۷۱ اثبات کرد، مسئلهٔ SAT اولین مسئلهٔ ان‌پی کامل شناخته شد. (اثبات را در قضیه کوک لوین ببینید.) تا آن زمان مفهومی به نام ان‌پی کامل وجود نداشت. این مسئله ان‌پی کامل باقی می‌ماند هرچند که همهٔ عبارات
ان‌پی کامل باقی می‌ماند هرچند که همهٔ عبارات به صورت عطفی معمولی با سه متغیر در هر عبارت (۳-CNF) باشند؛ یعنی عبارت به شکل زیر است: در اینجا هر x یک "متغیر" است و هر متغیر می‌تواند چندبار در عبارت تکرار شوند. یک ویژگی مهم اختصار کوک آن است که تعداد جواب‌های درست را نگه می‌دارد. به‌طور مثال اگر یک گراف 17 رنگ‌آمیزی سه‌گانه معتبر داشته باشد، قاعدهٔ SAT دارای 17 واگذاری ارضاپذیر است. ان‌پی کامل فقط به زمان اجرا در بدترین حالت ارجاع می‌دهد. بسیاری از مواردی که در کاربردهای عملی اتفاق می‌افتند می‌توانند خیلی
در کاربردهای عملی اتفاق می‌افتند می‌توانند خیلی سریعتر حل شوند. مسئلهٔ SAT آسان‌تر است اگر فرمول‌ها به صورت فصلی معمولی باشند، یعنی بین عبارات OR و در هر عبارت بین متغیرها AND قرار گرفته باشد. این فرمول‌ها صدق‌پذیر هستند اگر و تنها اگر حداقل یکی از عبارات آن صدق‌پذیر باشند، و یک عبارت صدق‌پذیر است اگر و تنها اگر به ازای هر متغیر x هم خودش و هم NOT آن را دربرنداشته باشد. این موضوع می‌تواند در زمان چندجمله‌ای بررسی شود. 2-صدق‌پذیری. همچنین مسئلهٔ SAT آسان‌تر است اگر تعداد متغیرهای یک عبارت به 2 محدود شده
است اگر تعداد متغیرهای یک عبارت به 2 محدود شده باشد، که در این حالت مسئله 2SAT نامیده می‌شود. این مسئله نیز می‌تواند در زمان چندجمله‌ای حل شود و در واقع برای ردهٔ ان‌ال کامل است. به‌طور مشابه اگر تعداد متغیرهای هر عبارت را به 2 محدود کرده و اعمال AND را به XOR تغییر دهیم، نتیجه یک "2-صدق‌پذیری XOR" است که یک مسئلهٔ کامل برای SL = L می‌باشد. یکی از مهم‌ترین محدودیت‌های SAT، مسئلهٔ HORNSAT می‌باشد که فرمول، یک عطف از چند عبارت هورن باشد. این مسئله با الگوریتم ارضاپذیری هورن با زمان چندجمله‌ای قابل حل است، و
ارضاپذیری هورن با زمان چندجمله‌ای قابل حل است، و در اصل پی-کامل می‌باشد. می‌تواند به صورت نسخه‌ای از ردهٔ پی برای مسئلهٔ صدق‌پذیری دودویی دیده شود. در صورتی که رده‌های پیچیدگی پی و ان‌پی یکسان نباشند، برخلاف SAT هیچ‌کدام از این محدودیت‌ها ان‌پی کامل نیستند. این فرضیه که پی و ان‌پی یکسان نیستند هنوز اثبات نشده‌است. 3-صدق‌پذیری. 3-صدق‌پذیری یک حالت خاص از k-SAT یا به‌طور ساده‌شده SAT است که هر عبارت دقیقاً k = 3 متغیر را شامل می‌شود. این یکی از 21 مسئله ان‌پی-کامل کارپ است. در اینجا یک مثال می‌زنیم: (¬
ان‌پی-کامل کارپ است. در اینجا یک مثال می‌زنیم: (¬ نشان‌دهندهٔ نقیض است.) E دارای دو عبارت (که با پرانتز مشخص شده‌اند)، چهار متغیر ("x"1, "x"2, "x"3, "x"4) و k = 3 (سه متغیر در هر عبارت) می‌باشد. برای آنکه این مثال از مسئلهٔ تصمیم‌گیری را حل کنیم باید مشخص کنیم که آیا یک جدول درستی برای متغیرها وجود دارد به‌طوری‌که کل عبارت همواره درست باشد یا خیر. در این مثال با "درست" قرار دادن همه متغیرها، می‌توان E را همواره درست در نظر گرفت. واگذاری‌های متنوعی می‌توان انجام داد. اگر هیج واگذاری‌ای امکان‌پذیر نبود، جواب
داد. اگر هیج واگذاری‌ای امکان‌پذیر نبود، جواب "خیر" خواهد بود. 3-SAT ان‌پی کامل است و به عنوان یک نقطهٔ شروع برای اثبات آنکه بقیهٔ مسائل هم ان‌پی سخت هستند استفاده می‌شود. این عمل با محدودیت زمانی چندجمله‌ای قابل انجام است. 3-SAT می‌تواند به یک-در-سه 3-صدق‌پذیری محدود شود که در آن ما "دقیقاً" می‌پرسیم که آیا یکی از متغیرها در هر عبارت درست هست یا خیر، به جای اینکه "حداقل" یک متغیر را بررسی کنیم. این محدودیت نیز ان‌پی کامل باقی می‌ماند. بر اساس نظر شونینگ (1990) یک الگوریتم سادهٔ تصادفی وجود دارد که در زمان
یک الگوریتم سادهٔ تصادفی وجود دارد که در زمان formula_5 اجرا می‌شود (n تعداد عبارات). این الگوریتم به احتمال قوی موفق می‌شود تا دربارهٔ 3-SAT درست تصمیم بگیرد. فرضیهٔ نمایی زمان آن است که هیچ الگوریتمی نمی‌تواند 3-SAT را در زمان formula_6 حل کند. صدق‌پذیری هورن. یک عبارت هورن است اگر حداکثر یک متغیر مثبت داشته باشد. این‌گونه عبارت‌ها مورد توجه هستند چون می‌توانند استلزام یک متغیر از مجموعه‌ای از متغیرها را بیان کنند. در واقع یک عبارت مانند formula_7 می‌تواند به شکل formula_8 بازنویسی شود، یعنی اگر
می‌تواند به شکل formula_8 بازنویسی شود، یعنی اگر formula_9 همه "درست" باشند، y هم باید "درست" باشد. مسئلهٔ تصمیم‌گیری در مورد صدق‌پذیری عبارات هورن در پی (P) است. این مسئله نیز می‌تواند با یک مرحله از انتشار واحد حل شود که مدل کمینهٔ واحد از مجموعه‌ای از عبارات هورن ایجاد می‌کند. یک تعمیم از ردهٔ فرمول‌های هورن، فرمول با قابلیت اسم‌گذاری دوبارهٔ هورن است که یک مجموعه از فرمول‌ها می‌باشد که با فرمت هورن می‌تواند با چند متغیر به همراه نقیض مربوطهٔ آن‌ها جایگزین شود. بررسی وجود این جایگزینی می‌تواند در زمان
شود. بررسی وجود این جایگزینی می‌تواند در زمان خطی انجام بگیرد؛ پس صدق‌پذیری همچین فرمولی در پی (P) است، چون می‌تواند اول با این جایگزینی و سپس بررسی صدق‌پذیری فرمول هورن نتیجه شده حل شود. صدق‌پذیری XOR. یک حالت خاص دیگر مسائلی هستند که در آن‌ها هر عبارت فقط اعمال XOR را شامل می‌شود. چون عمل XOR معادل جمع در زمینهٔ گالویس از اندازهٔ 2 است، عبارات می‌توانند مانند یک دستگاه معادلات خطی دیده شوند و از روش‌های متناظر مانند حذف گاوسی می‌توان برای یافتن راه‌حل آن‌ها استفاده کرد. قضیهٔ دوگانگی شافر. محدودیت‌های
استفاده کرد. قضیهٔ دوگانگی شافر. محدودیت‌های بالا (CNF، 2CNF، 3CNF، هورن) فرمول موردبررسی را به عطفی بودن زیرفرمول محدود می‌کنند؛ هر محدودیت یک شکل خاص برای همهٔ زیرفرمول‌ها مشخص می‌کند: به‌طور مثال، فقط عبارات دودویی می‌توانند یک زیرفرمول در 2CNF باشند. قضیهٔ دوگانگی شافر عنوان می‌کند که برای هر محدودیتی بر اعمال بولی که می‌توانند این زیرفرمول‌ها را شکل دهند، مسئلهٔ صدق‌پذیری متناظر یک پی یا ان‌پی کامل است. عضویت در پی (P) برای صدق‌پذیری 2CNF و فرمول هورن، حالت‌های خاصی از این قضیه هستند. رفتار در زمان
حالت‌های خاصی از این قضیه هستند. رفتار در زمان اجرا. همانطور که در بالا به‌طور خلاصه بیان شد، هرچند که مسئله، ان‌پی کامل است، مثال‌های عملی زیادی می‌توانند خیلی زود حل شوند. اکثر مسائل عملی در حقیقت "آسان" هستند، پس حل‌کنندهٔ SAT به آسانی می‌تواند یک راه‌حل بیابد یا اثبات کند که وجود ندارد؛ با وجود آنکه آن مورد هزاران متغیر و ده‌ها هزار محدودیت دارد. بقیهٔ مسائل کوچک زمان‌های اجرایی را ارائه می‌دهند که به صورت نمایی باشند و به مرور غیرعملی شده‌اند. متأسفانه هیچ راه قابل اطمینانی وجود ندارد که سختی مسئله را
هیچ راه قابل اطمینانی وجود ندارد که سختی مسئله را بدون امتحان آن بیان کند. پس تقریباً همهٔ حل‌کننده‌های SAT شامل زمان‌های اضافه می‌شوند، پس با آنکه هیچ راه‌حلی نیافته‌اند اما به پایان خواهند رسید. در نهایت حل‌کننده‌های SAT مختلفی موارد مختلف آسان یا سخت را پیدا خواهند کرد و بعضی از آن‌ها در اثبات صدق‌ناپذیری و دیگران در یافتن راه‌حل برترند. همهٔ آن رفتارها در مسابقه‌های حل SAT دیده می‌شوند. قابلیت کاهش دادن خود. از یک الگوریتم که به درستی می‌گوید یک مثال از SAT قابل‌حل است یا نه، می‌توان برای یافتن واگذاری
SAT قابل‌حل است یا نه، می‌توان برای یافتن واگذاری صدق‌پذیر استفاده کرد. در ابتدا سؤال از فرمول formula_10 پرسیده می‌شود. اگر جواب "خیر" باشد، فرمول صدق‌ناپذیر است. در غیر این صورت سؤال از formula_11 پرسیده می‌شود، یعنی اولین متغیر 0 در نظر گرفته می‌شود. اگر جواب "خیر" باشد، فرض می‌کنیم formula_12. به همین ترتیب مقادیر بقیهٔ متغیرها به دست می‌آیند. این ویژگی در تئوری‌های مختلفی از قضیهٔ پیچیدگی استفاده می‌شود: الگوریتم‌های حل‌کنندهٔ SAT. دو رده از الگوریتم‌های با کارایی بالا برای حل مسائل SAT وجود دارد:
با کارایی بالا برای حل مسائل SAT وجود دارد: الگوریتم تضاد-راندهٔ شناختن عبارت، که می‌توان به عنوان نوعی دیگر از الگوریتم‌های DPLL به آن نگاه کرد، و همچنین الگوریتم‌های اتفاقی جستجوی محلی مانند WalkSAT. یک حل‌کنندهٔ مسئلهٔ صدق‌پذیری DPLL، یک روند جستجوی بازگشتی اصولی را به کار می‌گیرد تا فاصلهٔ واگذاری متغیرها برای یافتن واگذاری صدق‌پذیر را کشف کند. در اوایل دههٔ 60 میلادی، روند اصلی جستجو در دو مقاله مطرح شد (منابع زیر را ببینید) و حال به عنوان الگوریتم دیویس-پاتنام-لاگمن-لاولند (یا به اختصار DPLL یا DLL)
(یا به اختصار DPLL یا DLL) مشهور است. از لحاظ تئوری کران پایین نمایی برای خانوادهٔ الگوریتم‌های DPLL اثبات شده‌است. حل‌کننده‌های SAT نوین (که در 10 سال گذشته ایجاد شدند) در دو نوع بیان می‌شوند: "تضاد-رانده" و "پیش‌بین". حل‌کننده‌های تضاد-رانده الگوریتم جستجوی DPLL اصلی را با تحلیل تضاد کارآمد، شناختن عبارت، بازگشت بدون ترتیب زمانی (الگوریتم پس‌پرش)، و همچنین انتشار واحد "دو-متغیر-تماشا"، انشعاب انطباقی و راه‌اندازی مجدد تصادفی، افزایش می‌دهند. نشان داده شده‌است که این "الحاقات" اصولی جستجو به صورت تجربی
که این "الحاقات" اصولی جستجو به صورت تجربی برای رسیدگی به موارد زیادی از SAT که در اتوماسیون طراحی الکترونیکی (EDA) به وجود می‌آیند ضروری هستند. حل‌کننده‌های پیش‌بین به خصوص کاهش‌ها (رفتن به ورای انتشار عبارت واحد) و کشف‌کننده‌ها را تشدید کردند و در کل در موارد پیچیده از حل‌کننده‌های تضاد-رانده قوی‌تر عمل می‌کنند. حل‌کننده‌های SAT نوین تأثیرات مهمی بر زمینه‌های تأیید نرم‌افزاری، حل‌کردن محدودیت‌های هوش مصنوعی و تحقیق در عملیات دارند. حل‌کننده‌های قوی به آسانی به صورت نرم‌افزار آزاد و متن‌باز در دسترس
آسانی به صورت نرم‌افزار آزاد و متن‌باز در دسترس هستند. به‌طور خاص نرم‌افزار تضاد-راندهٔ MiniSAT که در مسابقهٔ SAT در سال 2005 نسبتاً موفق بود، فقط دارای حدود 600 خط برنامه است. یک مثال از حل‌کننده‌های پیش‌بین march_dl است که در مسابقهٔ SAT در سال 2007 برنده شد. انواع خاصی از موارد بزرگ تصادفی صدق‌پذیر از SAT با انتشار نظرسنجی (SP) قابل حل هستند. به خصوص در طراحی پردازنده و برنامه‌های تایید، صدق‌پذیری و دیگر خواص منطقی از فرمول گزاره‌ای داده‌شده بعضی اوقات بر پایهٔ نمایشی از فرمول در نمودار تصمیم‌گیری
بر پایهٔ نمایشی از فرمول در نمودار تصمیم‌گیری دودویی (BDD) تصمیم‌گیری می‌شوند. پیوند به بیرون. اطلاعات بیشتر در مورد SAT: برنامه‌های SAT: حل‌کننده‌های SAT: کنفرانس بین‌المللی دربارهٔ قضیه و برنامه‌های آزمایش صدق‌پذیری: انتشارات: برنامه‌های محک: حل کردن SAT در حالت کلی: ارزیابی حل‌کننده‌های SAT: "این مقاله شامل موادی از یک ستون در ACM SIGDA e-newsletter توسط Prof. Karem Sakallah می‌باشد."
فردیناند چهارم (آلمانی:Ferdinand IV، مجاری:IV. Ferdinánd)(زادهٔ ۸ سپتامبر ۱۶۳۳- مرگ ۹ ژوئیهٔ ۱۶۵۴) پادشاه رومن‌ها، پادشاه مجارستان و بوهم بود. او پسر فردیناند سوم، امپراتور مقدس روم از همسر نخستش ماریا آنا بود. نیای مادری او فلیپه سوم، پادشاه اسپانیا بود. او همچنین برادر بزرگتر لئوپولد یکم، امپراتور مقدس روم بود. او در ۱۶۴۶ به پادشاهی بوهم و سال پس از آن به پادشاهی مجارستان رسید. در ۱۶۵۳ میلادی به عنوان پادشاه رومن‌ها رسید تا زمینه برای رسیدنش به مقام امپراتور مقدس روم فراهم شود، ولی بیماری آبله او را زودتر
مقدس روم فراهم شود، ولی بیماری آبله او را زودتر از پدر از پای درآورد. در نتیجه تاج امپراتور مقدس روم برادر کوچکتر او لئوپولد گردید. مرگ او در وین رخ‌داد. منابع. Wikipedia contributors, "Ferdinand IV, King of the Romans," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Ferdinand_IV,_King_of_the_Romans&amp;oldid=451996464 (accessed December 8, 2011).
شراره درشتی (زاده ۲۱ اردیبهشت۱۳۵۴) بازیگر تئاتر، سینما و تلویزیون ایرانی است. زندگی شخصی. وی همسر، رضا ژیان بود. او پس از درگذشت همسرش به سوئیس مهاجرت کرد و از صحنهٔ هنری ایران فاصله گرفت. درشتی در خرداد ۱۳۹۸ در پستی در صفحهٔ اینستاگرامش خبر داد که به علت ابتلا به سرطان در بیمارستان بستری شده‌است.
جستجو سه‌تایی در علوم کامپیوتر رویه ی جستجو ترنری مهارتی برای پیدا کردن مقدار بیشینه یا کمینه در توابع أکید است. در این رویه مشخص می‌کنیم که مقدار بیشینه یا کمینه تابع نمی‌تواند در یک سوم ابتدا یا انتهای دامنه ی تابع وجود داشته باشد. سپس همین شیوه را بر روی دو سوم باقی‌مانده به کار می‌بریم. جستجو سه‌تایی نمونه‌ای از روش الگوریتم تقسیم و حل است(الگوریتم جستجو را ببینید.)Ternary search تابع. فرض کنید ما به دنبال بیشینۀ formula_1 هستیم و می دانیم این مقدار بین formula_2 و formula_3 قرار دارد. برای این که
بین formula_2 و formula_3 قرار دارد. برای این که الگوریتم قابل اعمال باشند، یک مقدار formula_4 باید وجود داشته باشد به طوری که: الگوریتم. تابع اکید formula_1 را روی بازۀ formula_12 در نظر بگیرید. دو نقطه ی formula_13 و formula_14 را در این بازه انتخاب می‌کنیم. بنابراین formula_15در این صورت سه حالت وجود دارد : این فرایند تا زمانی ادامه پیدا می‌کند که بازۀ حاصل از مقدار ثابت از پیش تعیین شده کوچکتر شود. انتخاب نقاط formula_13 و formula_14 : زمان اجرا. T(n) = T(2/3 * n) + c (Θ(log n رویۀ بازگشتی. def
T(n) = T(2/3 * n) + c (Θ(log n رویۀ بازگشتی. def ternarySearch(f, left, right, absolutePrecision): #left and right are the current bounds; the maximum is between them if (right - left) &lt;absolutePrecision: return (left + right)/2 leftThird = (2*left + right)/3 rightThird = (left + 2*right)/3 if f(leftThird)&gt; f(rightThird): return ternarySearch(f, leftThird, right, absolutePrecision) else: return ternarySearch(f, left, rightThird, absolutePrecision) Ternary search درخت جستجوی سه‌تایی. درخت جستجوی
Ternary search درخت جستجوی سه‌تایی. درخت جستجوی سه‌تایی یکی از جالب‌ترین داده‌ساختارهادر زمینه دانش خوداست، زیرا این درخت ذخیره‌سازی بهینه را با سریع پیدا کردن ترکیب می‌کندو توانایی جستجوی پیشوندرا نیز دارد. قسمتی از نظریه. درخت جستجو سه تایی کمی پیچیده‌تر از درخت جستجو دوتایی است. علاوه بر درخت جستجوی دودویی، اشاره گر سومی در هر گره وجود دارد. زمانی که بر روی درخت حرکت می‌کنیم، این اشاره‌گرهنگامی که مقداری که مقایسه می‌شود؛ با مقدار گره برابر باشد، استفاده می‌گردد.در نتیجه این درخت سه اشاره‌گر چپ، راست، و
می‌گردد.در نتیجه این درخت سه اشاره‌گر چپ، راست، و برابر دارد. که در شکل زیر مشاهده می‌کنید. شکل زیر درخت جستجو سه تایی رشته‌های "as", "at", "cup", "cute", "he", "i" and "us" را نشان می‌دهد: c a u h t t e u s p e i s پیاده‌سازی. پیاده‌سازی تابع search : def search(string) return false unless (string &amp;&amp; !string.empty? &amp;&amp; self.value) head, tail = string.partition if head &lt;self.value return @left.search(string) if @left elsif head == self.value return true if !tail &amp;&amp; self.ending?
return true if !tail &amp;&amp; self.ending? return @equal.search(tail) if @equal elsif head&gt; self.value return @right.search(string) if @right end end پیاده‌سازی کلاس string : def search(string)class String def partition [head, tail] end # First character. def head (self.length&gt;= 1) ? self[0].chr : nil end # Cut the first character from the string and return the tail. def tail (self.length&gt;= 2) ? self[1..-1] : nil end end پیاده‌سازی کلاس درخت جستجوی سه‌تایی : class Tst def initialize @left =
جستجوی سه‌تایی : class Tst def initialize @left = @equal = @right = nil @ending = false end def insert(string) raise ArgumentError unless string.is_a?(String) head, tail = string.partition if self.value.nil? # self.value ? self.value = head # self.value ? end if head &lt;self.value @left = Tst.new unless @left @left.insert(string) elsif head == self.value if tail @equal = Tst.new unless @equal @equal.insert(tail) else self.ending_here() end elsif head&gt; self.value @right = Tst.new unless @right
self.value @right = Tst.new unless @right @right.insert(string) end end def search(string) return false unless (string &amp;&amp; !string.empty? &amp;&amp; self.value) head, tail = string.partition if head &lt;self.value return @left.search(string) if @left elsif head == self.value return true if !tail &amp;&amp; self.ending? return @equal.search(tail) if @equal elsif head&gt; self.value return @right.search(string) if @right end end alias :«:insert alias :[] :search protected def value @value end def
:[] :search protected def value @value end def value=(value) raise ArgumentError unless acceptable?(value) @value = value end def acceptable?(value) value.is_a?(String) &amp;&amp; value.length == 1 end def ending_here @ending = true end def ending? @ending end end
در قضیه با نظریه گراف، یکی از شاخه‌های ریاضیات، قیاس دست به دست موقعیتی است که در آن هر گراف متناهی غیرجهت‌دار، تعداد رأس‌های با درجه فرد آن زوج است. به اصطلاح، در یک مهمانی که افراد با هم دست می‌دهند، تعداد زوجی از افراد هستند که با تعداد فردی از افراد دیگر دست داده باشند. قیاس منطقی دست به دست نتیجه فرمول مجموع درجه است (که در بعضی مواقع قیاس منطقی دست به دست نامیده می‌شود) در یک گرافی که در آن v راس و E یال می‌باشد . هر دو نتایج توسط لئونهارد اویلر(۱۷۳۶)در روزنامه معروف وی در سون بریج کونیگز برگ اثبات
روزنامه معروف وی در سون بریج کونیگز برگ اثبات گردیدند که سبب آغاز مطالعه نظریه گراف شد. رئوس با درجه فرد در یک گراف در بعضی مواقع گره‌های فرد یا رئوس فرد نامیده می‌شوند; در این مجموعه اصطلاحات، قیاس منطقی دست به دست می‌تواند این توضیح را ارائه دهد که هر گراف‌ زوج تا گره فرد دارد. اثبات. اثبات فرمول مجموع درجه اویلر از تکنیک دو بار شمارش استفاده می‌کند : او تعداد جفتهای وابسته یا متلاقی( v،e) را که در آن e یال و v نقطه پایانی هستند به دو صورت شمارش می‌کند . راس v به جفت (deg(v تعلق دارد که در آن (deg(v (
. راس v به جفت (deg(v تعلق دارد که در آن (deg(v ( درجه v ) تعداد یال‌های وابسته با آن است. بنابراین تعداد جفتهای وابسته ( متلاقی) مجموع درجات می‌باشد. در حالی که، هر یال در نمودار دقیقاً به دو جفت متلاقی متعلق است، برای هر کدام از نقاط پایانی یک جفت وجود دارد، در نتیجه تعداد جفتهای متلاقی۲|"E"| است . از آنجایی که این دو فرمول عناصر مشابهی را شمارش می‌کنند باید ارزش‌های برابر داشته باشند. در یک مجموعه اعداد صحیح، توازن ( زوجیت ) مجموعه با ارقام زوج در جمع تأثیری نمی‌گذارد ; جمع کل در صورتی زوج می‌شود که یک
نمی‌گذارد ; جمع کل در صورتی زوج می‌شود که یک تعداد زوج از ارقام فرد وجود داشته باشد و زمانی که یک تعداد فرد از اعداد فرد موجود باشد آنگاه فرد می‌گردد. از آنجایی که یک طرف فرمول مجموع درجات عدد زوج ۲|"E"| است، مجموع طرف دیگر باید تعداد زوجی از ارقام فرد را داشته باشد. این بدین معنی است که باید تعداد زوجی از رئوس درجه فرد وجود داشته باشد. گراف‌های منظم. فرمول مجموع درجات این را متذکر می‌شود که هر گراف‌های منظم (r) با n راس rn/۲ یال دارد. خصوصاً، اگر r فرد است، تعداد یال‌ها باید به صورت زوج به r بخشپذیر
است، تعداد یال‌ها باید به صورت زوج به r بخشپذیر باشند. گراف‌های نامحدود. قیاس دست به دست به گراف‌های نامحدود صدق نمی‌کند، حتی زمانی که آن‍ها تنها یک تعداد متناهی از رئوس درجه فرد دارند. به عنوان مثال، گراف مسیر نامحدود با یک نقطه پایانی تنها دارای یک راس درجه فرد به جای داشتن یک تعداد زوج از رئوس است. گراف‌های تبادل. ساختارهای ترکیبی متعددی که توسط رادموندز و کامرون ۱۹۹۹ فهرست شده اند، ممکن است با ارتباط دادنشان به رئوس فرد در یک " گراف تبادل" مناسب به صورت عدد زوج نشان داده شوند . برای مثال، همانگونه که
عدد زوج نشان داده شوند . برای مثال، همانگونه که C.A.B smithاثبات کرد، در هر گراف مکعبی G باید یک تعداد زوج از دایره‌های همیلتونی در مسیر هر یال ثابت uv وجود داشته باشد; توماسون (۱۹۷۸) از یک اثبات بر اساس قیاس منطقی دست به دست استفاده کرد تا بتواند این نتیجه را به گراف‌های G در آن‌ها همه رئوس درجات فرد دارند تعمیم دهد . توماسون یک گراف تبادل H تعریف کرد که در آن رئوسش تبادل یک به یک با راه‌های همیلتون دارند که از u شروع می‌شوند و در مسیر v ادامه پیدا می‌کنند. دو تا از این راه‌ها p۱ و p۲ از یک یال به H وصل
دو تا از این راه‌ها p۱ و p۲ از یک یال به H وصل هستند، اگر یکی با اضافه کردن یک یال جدید به انتهای P۱ و حذف کردن یال دیگر از وسط P۱ به P۲ برسد، این یک رابطه سیستماتیک می‌شود. در نتیجه H یک نمودار غیرمستقیم است . اگر راه P در راس W ختم شود، پس راس مرتبط با P در H درجه برابر با تعداد راه‌هایی دارد که در آن P می‌تواند از طریق یک یال که با u ارتباط بازگشتی ندارد گسترده شود. این بدین معنی است که درجه این راس در H یا deg(w)-۱ ( یک عدد زوج) می‌باشد در صورتی که P یک بخشی از دایره همیلتونی را در مسیر uv تشکیل ندهند،
بخشی از دایره همیلتونی را در مسیر uv تشکیل ندهند، یا deg(w)-۲ ( یک عدد فرد ) می‌شود اگر P بخشی از دایره همیلتونی را در مسیرuv تشکیل دهد. از آنجایی که H تعداد زوجی از رئوس فرد را دارد، G باید یک تعداد زوج از دایره‌های همیلتونی در مسیر uv را داشته باشد. پیچیدگی محاسبات. در ارتباط با روش گراف تبادل برای اثبات موجودیت ساختارهای ترکیبی، جالب است که بپرسیم این ساختارها چقدر کاربردی می‌توانند باشند. برای مثال، فرض کنید به یکی یک دایره همیلتونی در گراف مکعبی به عنوان ورودی داده شده‌است ; در فرضیه smith این گفته
ورودی داده شده‌است ; در فرضیه smith این گفته می‌شود که در ادامه آن یک دایره دومی هم وجود دارد. با چه سرعتی این دایره دوم پیدا می‌شود؟ پاپادی میتریو (۱۹۹۴) پیچیدگی محاسباتی این‌گونه سوالات را یا به‌طور کلی تر پیدا کردن یک راس درجه فرد دومی را در زمانی که یک راس فرد تنها در یک گراف تعریف شده مجازی داده شده‌است بررسی کرد . او مقطع پیچیدگی PPA را تعریف کرد تا اینکه بتواند از این قبیل مسئله‌ها را حقظ کند; یک مقطع خیلی مربوط به روی گراف‌های مستقیم تعریف گردید، PPAD، و توجه ویژه‌ای را در نظریه بازی الگوریتمی به
و توجه ویژه‌ای را در نظریه بازی الگوریتمی به خود جلب کرد زیرا محاسبه موازنه نش (Nash) از نظر محاسباتی با سخت‌ترین مسائل در این مقطع برابری می‌کند. دیگر کاربردها. قیاس منطقی دست به دست در اثباتهای قیاس منطقی اسپرنر و موقعیت طولی ( خطی) تکه‌ای در مسئله کوهنوردی نیز استفاده می‌شود .
این صفحه را حذف نکنید
در گرافیک کامپیوتر، زد بافر الگوریتمی برای مدیریت عمق تصویر در گرافیک سه بعدی است. این الگوریتم عموماً توسط سخت افزار پیاده‌سازی می‌شود و معمولاً فقط هنگام عدم وجود سخت افزار لازم یا هنگام انجام آزمایش‌های در حالت نرم‌افزاری اجرا می‌شود. این الگوریتم برای پیدا کردن جواب مسئله پدیداری، که عبارت است از اینکه کدامیک از عناصر محیط روی تصویر دیده می‌شوند، طراحی شده‌است. این الگوریتم فقط برای اجسام کدر طراحی شده و در صورت وجود اجسام شفاف یا نیمه شفاف در محیط می‌توان از الگوریتم پینتر که البته کندتر است استفاده
از الگوریتم پینتر که البته کندتر است استفاده کرد. هنگامی که یک شیئ به وسیله کارت گرافیکی کشیده می‌شود، عمق هر پیکسل شیئ (مختصات z آن) در یک آرایه (معمولاً دو بعدی) ذخیره می‌شود. اگر یک پیکسل دیگر بخواهد در همان محل نمایش داده شود، باید به دوربین نزدیکتر باشد تا پیکسل‌های قبلی را بپوشاند، یا به عبارت دیگر در زد بافر عمق کمتری داشته باشد. به این کار حذف زد می گویند. زد بافر به جز در کشیدن تصاویر سه بعدی کاربردهای دیگری نیز به خصوص در تولید جلوه‌های ویژه ای چون عبور اجسام از دیوارها (مانند ارواح)، قرار دادن
عبور اجسام از دیوارها (مانند ارواح)، قرار دادن انیمیشن‌ها روی یک صفحه خاص از فضا و الگوریتم‌های تولید سایه دارد. الگوریتم. مقادیر ورودی: لیستی از چند ضلعی‌ها برای کشیدن. مقدار بازگشتی: یک آرایه رنگ، که شدت رنگ در آن نقطه را نشان می‌دهد. مقدار تمام عناصر (z-buffer(x,y را برابر حداکثر عمق قرار بده. مقدار تمام عناصر (Color(x,y را برابر رنگ پس زمینه قرار بده. برای هر چند ضلعی P انجام بده: برای هر پیکسل (x,y) که هنگام کشیدن P در صفحه خروجی قرار می‌گیرد انجام بده مقدار عمق این پیکسل را برای P محاسبه کن. اگر این