stanford-oval/wikipedia huggingface dataset:
باین‌بریج، پنسیلوانیا

| باین‌بریج، پنسیلوانیا | باین‌بریج، پنسیلوانیا |
| --- | --- |
حوزه سرشماری: حوزه سرشماری
باین‌بریج، پنسیلوانیا: باین‌بریج، پنسیلوانیا
BainbridgeLocation within the U.S. state of Pennsylvaniaنمایش نقشه پنسیلوانیاBainbridgeBainbridge (ایالات متحده آمریکا)نمایش نقشه ایالات متحده آمریکا: BainbridgeLocation within the U.S. state of Pennsylvaniaنمایش نقشه پنسیلوانیاBainbridgeBainbridge (ایالات متحده آمریکا)نمایش نقشه ایالات متحده آمریکا
مختصات: ۴۰°۰۵′۲۷″ شمالی ۷۶°۴۰′۰۳″ غربی﻿ / ﻿۴۰٫۰۹۰۸۳°شمالی ۷۶٫۶۶۷۵۰°غربی﻿ / 40.09083; -76.66750: مختصات: ۴۰°۰۵′۲۷″ شمالی ۷۶°۴۰′۰۳″ غربی﻿ / ﻿۴۰٫۰۹۰۸۳°شمالی ۷۶٫۶۶۷۵۰°غربی﻿ / 40.09083; -76.66750
کشور:  ایالات متحده آمریکا
ایالت: پنسیلوانیا
شهرستان: شهرستان لنکستر، پنسیلوانیا
جمعیت (سرشماری ۲۰۱۰ ایالات متحده آمریکا): جمعیت (سرشماری ۲۰۱۰ ایالات متحده آمریکا)
 • کل: ۱۳۵۵
منطقهٔ زمانی: یوتی‌سی -۵ (منطقه زمانی شرقی)
 • تابستانی (DST): یوتی‌سی -۴ (EDT)
زیپ‌کد: ۱۷۵۰۲
باین‌بریج (به انگلیسی: Bainbridge) یک منطقهٔ مسکونی در ایالات متحده آمریکا است که در شهرستان لنکستر، پنسیلوانیا واقع شده‌است. باین‌بریج ۱٬۳۵۵ نفر جمعیت دارد.
بوهوتیتسه

| بوهوتیتسه | بوهوتیتسه |
| --- | --- |
شهر: شهر
  پرچمنشان:   پرچمنشان
بوهوتیتسه: بوهوتیتسه
مختصات: ۴۸°۵۹′۲۶″ شمالی ۱۶°۲۱′۲۳″ شرقی﻿ / ﻿۴۸٫۹۹۰۵۶°شمالی ۱۶٫۳۵۶۳۹°شرقی﻿ / 48.99056; 16.35639: مختصات: ۴۸°۵۹′۲۶″ شمالی ۱۶°۲۱′۲۳″ شرقی﻿ / ﻿۴۸٫۹۹۰۵۶°شمالی ۱۶٫۳۵۶۳۹°شرقی﻿ / 48.99056; 16.35639
کشور:  جمهوری چک
منطقه: منطقه موراویای جنوبی
ناحیه: Znojmo
مساحت: مساحت
 • کل: ۷٫۱۶ کیلومتر مربع (۲٫۷۶ مایل مربع)
ارتفاع: ۲۵۸ متر (۸۴۶ فوت)
جمعیت (۲۰۰۶): جمعیت (۲۰۰۶)
 • کل: ۶۱۵
 • تراکم: ۸۶/کیلومتر مربع (۲۲۰/مایل مربع)
کد پستی: 671 76 to ۶۷۲ ۰۱
بوهوتیتسه (به چکی: Bohutice) یک منطقهٔ مسکونی در جمهوری چک است که در ناحیه زنویمو واقع شده‌است. بوهوتیتسه ۷٫۱۶ کیلومتر مربع مساحت و ۶۱۵ نفر جمعیت دارد و ۲۵۸ متر بالاتر از سطح دریا واقع شده‌است.
اندیس روستای چشمه سیر

| روستای چشمه سیر> موقعیت | روستای چشمه سیر> موقعیت |
| --- | --- |
استان: استان خراسان
شهر: حوالی سلطان آباد
مشخصات فنی معدن: مشخصات فنی معدن
مشخصات فنی کانی: مشخصات فنی کانی
فرمول شیمیایی: Cu۲(CO۳)(OH)۲
نوع کانه: مالاکیت
پاراژنز: هماتیت
سنگ معدن: سنگ معدن
ژنز: دگرگونی
سنگ میزبان: سرپانتینیت
شکل: رگه ای
زلزله: زلزله
وضعیت لرزه‌خیزی ناحیه: غیر فعال
نام اندیس: روستای چشمه سیر
نوع اندیس: فلزی
نام ماده: مس
نوع ماده: فلزی
روستای چشمه سیر یک اندیس فلزی است که در حوالی شهر سلطان آباد استان خراسان قرار دارد و مادهٔ معدنی موجود در آن، مس است.سنگ میزبان این اندیس سرپانتینیت است  در این اندیس، پاراژنز‌های هماتیت یافت می‌شوند.
بایه

| بایه Bayé | بایه Bayé |
| --- | --- |
بایهموقعیت در نقشه بورکینافاسو: بایهموقعیت در نقشه بورکینافاسو
مختصات: ۱۲°۰۴′ شمالی ۴°۰۵′ غربی﻿ / ﻿۱۲٫۰۶۷°شمالی ۴٫۰۸۳°غربی﻿ / 12.067; -4.083: مختصات: ۱۲°۰۴′ شمالی ۴°۰۵′ غربی﻿ / ﻿۱۲٫۰۶۷°شمالی ۴٫۰۸۳°غربی﻿ / 12.067; -4.083
کشور:  بورکینافاسو
منطقه: منطقه بوکله دو موهان
استان: استان بانوا
شهرستان: شهرستان سولنزو
جمعیت (2005): جمعیت (2005)
 • کل: ۵٬۴۷۸
منطقهٔ زمانی: یوتی‌سی +۰ (GMT 0)
بایه شهری در شهرستان سولنزو در استان بانوا در بورکینافاسوی غربی است و جمعیت آن ۵,۴۷۸ نفر است.
یانوشووا

| یانوشووا | یانوشووا |
| --- | --- |
Village: Village
یانوشووا: یانوشووا
مختصات: ۴۹°۳۸′۴۵″ شمالی ۲۰°۴۴′۹″ شرقی﻿ / ﻿۴۹٫۶۴۵۸۳°شمالی ۲۰٫۷۳۵۸۳°شرقی﻿ / 49.64583; 20.73583: مختصات: ۴۹°۳۸′۴۵″ شمالی ۲۰°۴۴′۹″ شرقی﻿ / ﻿۴۹٫۶۴۵۸۳°شمالی ۲۰٫۷۳۵۸۳°شرقی﻿ / 49.64583; 20.73583
کشور:  لهستان
استان‌های لهستان: استان لهستان کوچک‌تر
County: شهرستان نوو سانچ
گمینا: گمینا خومیتس
جمعیت: ۵۲۸
یانوشووا (به لاتین: Januszowa) یک روستا در لهستان است که در گمینا خومیتس واقع شده‌است. یانوشووا ۵۲۸ نفر جمعیت دارد.
الگوریتم DPLL

| 0 | 1 |
| --- | --- |
در یک فرمول CNF-SAT این مراحل را انجام دهید: ۱-یک لیترال را انتخاب کنید، ۲- یک مقدار درستی به آن منتسب کنید، ۳-فرمول را ساده کنید، ۴-صدق‌پذیری را بررسی کنید، ۵-اگر صادق نیست، پسگرد انجام دهید.: در یک فرمول CNF-SAT این مراحل را انجام دهید: ۱-یک لیترال را انتخاب کنید، ۲- یک مقدار درستی به آن منتسب کنید، ۳-فرمول را ساده کنید، ۴-صدق‌پذیری را بررسی کنید، ۵-اگر صادق نیست، پسگرد انجام دهید.
رده: مسئله صدق‌پذیری دودویی
ساختمان داده: درخت دودویی
کارایی بدترین حالت:  O(2^{n})
کارایی بهترین حالت:  O(1) (ثابت)
پیچیدگی فضایی:  O(n) (الگوریتم اصلی)
الگوریتم DPLL (کوته‌نوشت Davis–Putnam–Logemann–Loveland) در منطق و علوم رایانه، یک الگوریتم جستجوی کامل و مبتنی بر پس‌گرد برای تصمیم‌گیری درمورد صدق‌پذیری برای فرمول‌های منطق گزاره‌ای در حالت نرمال عطفی است، به عبارت دیگر الگوریتم DPLL دارد مسئله CNF-SAT را حل می‌کند.
این الگوریتم در سال ۱۹۶۱ توسط مارتین دیویس، جرج لاگِمن، و دونالد لاولند معرفی گردید، که یک روش اصلاحی برای الگوریتم پیشین دیویس-پاتنام بود. بخصوص در نشریات قدیمی، به الگوریتم دیویس-پاتانم-لاولند، «روش دیویس-پاتنام» یا «الگوریتم DP» گفته می‌شد. نام‌های معمول‌تر دیگری که این تفاوت را حفظ نموده‌اند، DLL و DPLL می‌باشند.
بعد از حدود ۵۰ سال، هنوز هم فرایند DPLL مبنایی برای موثرترین حل‌کننده‌های کامل SAT می‌باشد. این الگوریتم، امروزه، این الگوریتم، در زمینه اثبات قضیه خودکار برای قطعه‌هایی از منطق مرتبه اول، به روش الگوریتم DPLL(T) گسترش داده شده‌است.
پیاده‌سازی و کاربردها

مسئله SAT هم از دیدگاه نظری و هم عملی مهم می‌باشد. در نظریه پیچیدگی، این الگوریتم، اولین مسئله‌ای بود که ثابت شد که ان‌پی کامل است. مسئله SAT در موارد متنوع و گسترده‌ای مثل «وارسی مدل»، «زمان‌بندی و برنامه‌ریزی خودکار» و «تشخیص در هوش مصنوعی» کاربرد دارد.
از این رو، این الگوریتم سال‌ها مورد پژوهش‌های فراوان بوده‌است، و به صورت منظم صحنه رقابت‌های زیادی بین حل‌کننده‌های SAT بوده‌است. در سال‌های اخیر، پیاده‌سازی‌های نوین DPLL مثل چاف و زدچاف، GRASP یا MiniSat در مقام اول این رقابت‌ها بوده‌اند.
یک کاربرد دیگر که DPLL را درگیر نموده‌است، اثبات قضیه خودکار، یا رضایت به پیمانه نظریات (SMT) است. SMT یک نظریه SAT است که در آن متغیرهای گزاره‌ای توسط فرمول‌های دیگر نظریهٔ ریاضیاتی جایگزین شده‌اند.
الگوریتم

الگوریتم پس‌گرد اصلی توسط انتخاب یک لیترال، انتساب یک مقدار درستی به آن، ساده‌سازی فرمول، و سپس بررسی بازگشتی این موضوع رخ می‌دهد که آیا فرمول ساده‌سازی شده صدق‌پذیر هست یا نه؛ اگر صدق‌پذیر بود، یعنی فرمول اصلی صدق‌پذیر است، در غیر این صورت، با فرض مقدار درستی معکوس، بررسی بازگشتی مشابهی باید انجام شود. به این موضوع «قاعده جداسازی» گفته می‌شود، زیرا مسئله را به دو زیرمسئله ساده‌تر جداسازی می‌کند. گام ساده‌سازی به صورت اساسی این است که همه بندهایی که تحت انتساب از فرمول، «درست» می‌شوند، و همه لیترال‌هایی که از بندهای باقیمانده «نادرست» می‌شوند، را حذف می‌کند.
با استفاده حریصانه این قواعد در هر گام، الگوریتم DPLL روی الگوریتم پسگرد، افزایش می‌یابد:
الگوریتم > حذف لیترال خالص

یک انتساب جزئی داده شده موقعی صدق‌ناپذیری اش تشخیص داده می‌شود که یکی از بندها «خالی» شود، یعنی همه متغیرهایش به شیوه ای منتسب شوند که لیترال‌های متناظر را نادرست کنند. صدق‌پذیری فرمول در دو حالت تشخیص داده می شود: یا موقعی که همه متغیرها را انتساب دهیم اما بند خالی تولید نشود، یا در پیاده‌سازی‌های نوین، اگر همه بندها صادق شوند. صدق‌ناپذیری کامل فرمول تنها پس از «جستجوی جامع» تشخیص داده می‌شود.
الگوریتم DPLL را می‌توان در شبه کد زیر خلاصه کرد، که در آن Φ همان فرمول CNF است:
Algorithm DPLL
 Input: A set of clauses Φ.
 Output: A Truth Value.
function DPLL(Φ)
 if Φ is a consistent set of literals then
 return true;
 if Φ contains an empty clause then
 return false;
 for every unit clause {l} in Φ do
 Φ ← unit-propagate(l, Φ);
 for every literal l that occurs pure in Φ do
 Φ ← pure-literal-assign(l, Φ);
 l ← choose-literal(Φ);
 return DPLL(Φ ∧ {l}) or DPLL(Φ ∧ {not(l)});
"←" denotes assignment.  For instance, "largest ← item" means that the value of largest changes to the value of item.
"return" terminates the algorithm and outputs the following value.
در این شبه‌کدunit-propagate(l, Φ) و pure-literal-assign(l, Φ) توابعی هستند که نتیجه اعمال «انتشار واحد» و «قاعده لیترال خالص» را برای لیترال l و فرمول Φ به ترتیب برمی‌گردانند. به زبان دیگر، این توابع در فرمول Φ هر رخداد l را به «درست» و هر رخداد not l را با «نادرست» جایگزین می‌کنند، و سپس فرمول نتیجه‌شده را ساده‌سازی می‌کنند. or موجود در عبارت return یک عملگر اتصال کوتاه است. Φ ∧ {l} نشان دهنده نتیجه ساده‌سازی‌شده جایگزینی «درست» برای l در Φ است.
این الگوریتم در یکی از این دو حالت خاتمه می‌یابد: یا اینکه فرمول CNF ای با نام Φ پیدا می‌شود که شامل مجموعه سازگاری از لیترال‌ها باشد، یعنی هیچ l و ¬l ای برای لیترال l در فرمول موجود نباشد. اگر این موضوع رخ دهد، متغیرها را به صورت بدیهی با تنظیم آن‌ها به قطبیت متناظر لیترال شامل‌شونده در ارزیابی صادق می‌کنیم. در غیر این صورت، موقعی که فرمول شامل یک بند خالی باشد، این بند به صورت پوچ «نادرست» است، زیرا یک فصل حتماً نیاز دارد تا حداقل یک عضوش درست باشد تا مجموعه کلی درست شود. در این حالت، وجود چنین بندی به معنی آن است که فرمول (که به صورت عطف همه بندها ارزیابی می‌شود) را نمی‌توان «درست» ارزیابی کرد، و فرمول باید صدق‌ناپذیر باشد.
شبه‌کد تابع DPLL فقط این موضوع را برمی‌گرداند که آیا انتساب نهایی برای فرمول، صدق‌پذیر هست یا نه. در یک پیاده‌سازی واقعی، یک انتساب نیمه‌صادق نیز معمولاً موفقیت را برمی‌گرداند؛ این موضوع از مجموعه سازگار لیترال‌های بیانیه if اول در تابع، قابل دستیابی است.
الگوریتم دیویس-لاگمن-لاولند به گزینه «لیترال انتشعابی» بستگی دارد، که همان لیترالی است که در گام پسگرد درنظرگرفته شده‌است. و این موضوع، یعنی الگوریتم DPLL یک الگوریتم دقیق نیست، بلکه «خانواده‌ای از الگوریتم‌ها» است، که هر عضو آن خانواده یک روش ممکن برای انتخاب لیترال انشعاب دارد. «کارایی» الگوریتم به شدت از نحوه انتخاب گزینه لیترال انشعاب تأثیر می‌پذیرد: نمونه‌هایی وجود دارد که در آن زمان اجرایی ثابت است، و همچنین در نمونه‌هایی زمان‌اجرا نمایی است، این موضوع بستگی به نحوه انتخاب لیترال‌های انشعابی دارد. به این توابع انتخابی، «توابع اکتشاف»، یا «اکتشاف برای انشعاب» هم گفته می‌شود.
الگوریتم > نحوه تصور

در سال ۱۹۶۱ دیویس، لاگمن، لاومن این الگوریتم را ایجاد کردند. بعضی از ویژگی‌های این الگوریتم از این قرار است:
بر اساس جستجو می‌باشد.
مبنای تقریباً همه حل‌کننده‌های SAT نوین است.
از پسگردهایی که یادگیرنده اند یا غیرزمانی اند استفاده نمی‌کند.
یک مثال با تصور مرتبط با آن از یک الگوریتم DPLL که پسگرد زمانی دارد:
همه بندهای سازنده یک فرمول CNF اینجا آمده‌است.
یک متغیر را انتخاب کنید.
یک تصمیم‌گیری انجام دهید، یعنی a = False (0)، از این رو بندهای سبز «درست» می‌شوند.
بعد از انجام چندین انتخاب، ما به یک گراف پیامد می‌رسیم که منجر به تعارض شده‌است.
اکنون به مرحله میانی واگردانی می‌کنیم، و مقدار مخالف را به آن متغیر انتساب اجباری می‌کنیم.
اما انتخاب اجباری منجر به تعارض دیگری شده‌است.
بازگشت به مرحله قبلی و انتخاب اجباری دیگری انجام می‌شود.
یک انتخاب دیگر انجام شده‌است، اما آن هم منجر به تعارض شده.
یک انتخاب اجباری دیگر، اما بازهم منجر به تعارض شده‌است.
بازگشت به مرحله قبلی
به همین روش ادامه داده‌ایم و این گراف پیامد نهایی است.
کارهای جدید روی الگوریتم

در سال‌های دهه ۲۰۱۰، کار روی بهبود الگوریتم در سه جهت انجام شد:
تعریف سیاست‌های متنوع برای انتخاب لیترال انتشعاب.
تعریف ساختمان داده‌های جدید برای سریع‌سازی الگوریتم، که مخصوصاً مرتبط با بخش انتشار واحد بود.
تعریف انواع الگوریتم پسگرد اصلی. که این جهت آخر شامل «پسگردهای غیرزمانی» (که به آن پس‌پرش گفته می‌شود) و یادگیری بند است. این اصلاحات توصیف‌کننده یک روش پسگرد بعد از رسیدن به یک بند متعارض است، که یعنی بند ریشه‌ای (انتساب به متغیرها) موجود در تعارض را با هدف جلوگیری از رسیدن به تعارض‌های مشابه در آینده «یادمی‌گیرد». حل‌کننده‌های SAT نتیجه‌شده، که حالت یادگیری بند مبتنی بر تعارض دارند، موضوع پژوهش‌های جدید و زیادی در سال ۲۰۱۴ بوده‌اند.
یک الگوریتم جدیدتر از سال ۱۹۹۰، روش استالمارک است. از این رو از سال ۱۹۸۶، از نمودارهای تصمیم دودویی (با مرتبه پایین) برای حل SAT استفاده شده‌است.
ارتباط با دیگر مفاهیم

اجرای الگوریتم‌های مبتنی بر DPLL روی نمونه‌های صدق‌ناپذیر با «اثبات‌های انکار وجود رزلوشن درختی» متناظر است.
تول‌پادل

منطقه مسکونی در England
| تول‌پادل | تول‌پادل |
| --- | --- |
 Parish Church of St John the Evangelist:  Parish Church of St John the Evangelist
تول‌پادلتول‌پادل نمایش داده شده در  دورست (انگلستان): تول‌پادلتول‌پادل نمایش داده شده در  دورست (انگلستان)
جمعیت: ۴۲۰ 
مرجع شبکه OS: SY792944 
منطقه: West Dorset
Shire county: دورست (انگلستان)
ناحیه: جنوب غربی انگلستان
کشور: England
کشور مستقل: بریتانیا
پلیس: Dorset
آتشنشانی: Dorset
آمبولانس: South Western
 :  
مجلس انگلستان: West Dorset
 فهرست مکان‌‌ها بریتانیا انگلستان Dorset ۵۰°۴۴′۵۸″شمالی ۲°۱۷′۴۶″غربی﻿ / ﻿۵۰٫۷۴۹۵°شمالی ۲٫۲۹۶۲°غربی﻿ / 50.7495; -2.2962:  فهرست مکان‌‌ها بریتانیا انگلستان Dorset ۵۰°۴۴′۵۸″شمالی ۲°۱۷′۴۶″غربی﻿ / ﻿۵۰٫۷۴۹۵°شمالی ۲٫۲۹۶۲°غربی﻿ / 50.7495; -2.2962
تول‌پادل (به انگلیسی: Tolpuddle) یک روستا و محله مدنی در بریتانیا است که در West Dorset واقع شده‌است. تول‌پادل ۴۲۰ نفر جمعیت دارد.
اورانیا ۳۰

| کشف | کشف |
| --- | --- |
تاریخ کشف: ژوئیه ۲۲, ۱۸۵۴
طبقه‌بندی: طبقه‌بندی
رده ریزسیاره: کمربند سیارک‌ها
ویژگی‌های مداری: ویژگی‌های مداری
مبدأ ژوئن ۱۴, ۲۰۰۶ (JD ۲۴۵۳۹۰۰٫۵): مبدأ ژوئن ۱۴, ۲۰۰۶ (JD ۲۴۵۳۹۰۰٫۵)
اوج: ۳۹۸٫۸۱۷ Gm (2.666 AU)
حضیض: ۳۰۹٫۳۳۸ Gm (2.068 AU)
نیم‌قطر بزرگ: ۳۵۴٫۰۷۷ Gm (۲٫۳۶۷ AU)
خروج از مرکز مداری: ۰٫۱۲۶
تناوب مداری: ۱۳۳۰٫۰۱۷ d (۳٫۶۴ a)
میانگین سرعت مداری: ۱۹٫۲۸ km/s
آنومالی متوسط: ۱۹۶٫۵۴۹°
انحراف: ۲٫۰۹۷°
ویژگی‌های فیزیکی: ویژگی‌های فیزیکی
ابعاد: ۱۰۰٫۱۵ km †
جرم: ۱٫۱‎×۱۰۱۸? kg
میانگین چگالی: ۲٫۰? g/cm³
گرانش سطحی استوایی: ۰٫۰۲۸۰? m/s²
سرعت گریز استوایی: ۰٫۰۵۲۹? km/s
سپیدایی هندسی: ۰٫۱۷۱۴ (geometric)†
قدر مطلق (H): ۷٫۵۷
 :  
سیارک ۳۰ (به انگلیسی: 30 Urania) سیمین سیارک کشف شده‌است که در ۲۲ ژوئیه ۱۸۵۴ و در لندن کشف شد.
قدر مطلق سیارک برابر ۷٫۵۳ است.
ریوبرگوس

| ریوبرگوس | ریوبرگوس |
| --- | --- |
Municipality: Municipality
ریوبرگوس: ریوبرگوس
Santa Maria del Priorat: Santa Maria del Priorat
  نشان:   نشان
ریوبرگوسLocation in Cataloniaنمایش نقشه استان بارسلونریوبرگوسریوبرگوس (اسپانیا)نمایش نقشه اسپانیا: ریوبرگوسLocation in Cataloniaنمایش نقشه استان بارسلونریوبرگوسریوبرگوس (اسپانیا)نمایش نقشه اسپانیا
مختصات: ۴۱°۴۶′۴۰″ شمالی ۱°۲۶′۲۲″ شرقی﻿ / ﻿۴۱٫۷۷۷۷۸°شمالی ۱٫۴۳۹۴۴°شرقی﻿ / 41.77778; 1.43944: مختصات: ۴۱°۴۶′۴۰″ شمالی ۱°۲۶′۲۲″ شرقی﻿ / ﻿۴۱٫۷۷۷۷۸°شمالی ۱٫۴۳۹۴۴°شرقی﻿ / 41.77778; 1.43944
کشور:  اسپانیا
بخش خودمختار:  کاتالونیا
استان:  استان بارسلون
Comarca: آنیویا
حکومت: حکومت
 • شهردار: Jordi Cases Camats
مساحت: مساحت
 • کل: ۲۶٫۲ کیلومتر مربع (۱۰٫۱ مایل مربع)
جمعیت (۲۰۱۸): جمعیت (۲۰۱۸)
 • کل: ۱۵۶
 • تراکم: ۶٫۰/کیلومتر مربع (۱۵/مایل مربع)
وبگاه: www.riubregos.cat
ریوبرگوس (به اسپانیایی: Castellfollit de Riubregós) یک منطقهٔ مسکونی در اسپانیا است که در آنیویا واقع شده‌است. ریوبرگوس ۲۶٫۲ کیلومتر مربع مساحت دارد.
الگوریتم FKT

الگوریتم FKT که نام آن از ابتدای نام‌های Fisher, Kasteleyn و Temperley گرفته شده‌است، الگوریتمی است که به شمارش تعداد تطابق کامل در یک گراف مسطح با زمان چندجمله ای می‌پردازد. این کار برای گراف‌های عمومی به صورت P-کامل می‌باشد. شمارش تعداد تطابق، حتی برای گراف‌های مسطح نیز به صورت P-کامل می‌باشد. ایده اصلی، تبدیل مسئله به یک پردازش
از ماتریس متقارن مورب که از جاسازی مسطح گراف به دست آمده است می‌باشد. بدین ترتیب این ماتریس به سرعت از الگوریتم استاندارد دترمینان محاسبه می‌گردد.
تاریخچه

مسئله شمارش تعداد تطابق کامل مسطح، ریشه در مکانیک آماری و شیمی دارد، در آنجا سؤال اصلی این بوده‌است که آیا مولکول‌های دو اتمی که بر روی یک سطح جذب می‌شوند و تشکیل یک لایه می‌دهند به چند طریق می‌توان آن‌ها را مرتب نمود؟
تابع پارتیشن یک کمیت بسیار مهم می‌باشد که ویژگی‌های آماری یک سیستم در حال تعادل را رمز می‌کند و می‌توان از آن برای حل مسئله پیشین استفاده نمود. هرچند که تلاش برای محاسبه تابع پارتیشن از تعریف آن، چندان عملی نیست؛ بنابراین برای حل دقیق یک سیستم فیزیکی باید شکل مشابهی از تابع پارتیشن را برای آن سیستم فیزیکی خاص پیدا کنیم که محاسبه آن به اندازه کافی ساده باشد.
در اوایل ۱۹۶۰، تعریف دقیقاً قابل حل، چندان ملموس نبود.
در ۱۹۶۵، علم کامپیوتر یک تعریف جدی با معرفی زمان چندجمله‌ای ارائه نمود. به‌طور مشابه در سال ۱۹۷۹، تعریف نه چندان دقیق قابل حل که به مسائل P-سختی برمی گردد، ارائه شد.
نوع دیگری از سیستم فیزیکی که قابل بررسی است ترکیبی از دیمرها می‌باشد. دیمرها، پلیمری با دو اتم می‌باشند. مدل دیمر، تعداد پوشش‌های دیمر از یک گراف را می‌شمارد. یک سیستم فیزیکی قابل بررسی دیگر، اتصال مولکول‌های آب H2O که تشکیل یخ می‌دهند می‌باشد . این سیستم را می‌توان به عنوان یک گراف جهت دار منظم ۳ تایی که جهت یال‌ها در هر راس آن نمی‌تواند یکسان باشد، مدل نمود. سؤال این است که چه تعداد جهت یال در این گراف می‌تواند در این گراف وجود داشته باشد؟
با انگیزه سیستم‌های فیزیکی که دیمرها هم شامل آن‌ها می‌شود در سال ۱۹۶۱، Kasteleyn, Temperley و Fisher هر کدام به‌طور مستقل تعداد کاشی کاری‌های دومینو را برای یک مستطیل m در n پیدا کردند. این فرمول برابر با شمارش تعداد تطابق کامل برای یک یک گراف شبکه m در n می‌باشد. در ۱۹۶۷، Kasteleyn این نتیجه را برای تمام گراف‌های مسطح گسترش داد.
الگوریتم > شرح

دید کلی این است که هر جمله غیر صفر در Pfaffian از ماتریس مجاورت گراف G با یک تطابق کامل مرتبط است؛ بنابراین اگر جهت‌گیری ای از G پیدا شود که مطابق تمام علائم جملات موجود در Pfaffian باشد (مثبت یا منفی بودن فرقی نمی‌کند)، آنگاه می‌توان گفت قدرمطلق Pfaffian نشان دهنده تعداد تطابق کامل گراف G می‌باشد. الگوریتم FKT این کار را برای یک گراف مسطح G انجام می‌دهد.
فرض کنیم (G = (V, E یک گراف بدون جهت با ماتریس مجاورت A باشد. (PM(n را به عنوان مجموعه ای از پارتیشن‌های عناصر n به صورت جفتی تعریف می‌کنیم، سپس تعداد تطابق کامل در G به صورت زیر بدست می‌آید:
\operatorname {PerfMatch} (G)=\sum _{M\in PM(|V|)}\prod _{(i,j)\in M}A_{ij}.
فرمول مرتبط به این موضوع، فرمول Pfaffian برای هر ماتریس n در n مانند A می‌باشد:
\operatorname {pf} (A)=\sum _{M\in PM(n)}\operatorname {sgn} (M)\prod _{(i,j)\in M}A_{ij},
در نهایت، برای هر ماتریس متقارن مورب A داریم:
\operatorname {pf} (A)^{2}=\det(A),
که در آن (det(A نشان دهنده دترمینان A می‌باشد. این نتجه از زحمات Cayley می‌باشد. از آنجا که دترمینان به راحتی قابل محاسبه است، فرمول بدست آمده هم قابل محاسبه خواهد بود.
الگوریتم > توضیحات سطح بالا

محاسبه مسطح تعبیه شده G
محاسبه درخت پوشای T1 از گراف ورودی G
به هر یال از G که از T1 نیز می‌باشد یک جهت اختیاری تخصیص می‌دهیم
ساخت یک گراف بدون جهت به نام T2 با مجموعه راس‌های گراف همزاد G با استفاده از مسطح تعبیه شده
ساخت یک یال در T2 که بین دو راس آن در گراف متناظر آن در G یالی اینچنین وجود ندارد (دقت داشته باشید که T2 یک درخت می‌باشد)
برای هر یال v در T2 (که ریشه نیست):
فرض کنید e تنها یال G می‌باشد در مقابل v که هنوز جهتی به آن اختصاص داده نشده‌است
به e یک جهت اختصاص دهید به گونه ای که تعداد یال‌هایی که جهت آن‌ها پاد ساعتگرد می‌باشد، فرد گردد.
یال v را از T2 حذف کنید
قدر مطلق Pfaffian از ماتریس مجاورت (۰و۱-و۱) گراف G را باز گردان، که برابر است با قدر مطلق توان دوم دترمینان.
الگوریتم > تعمیم

مجموع تطابق کامل وزن دار را نیز می‌توان با استفاده از ماتریس Tutte برای ماتریس مجاورت در گام نهایی انجام داد.
تئوری Kuratowski اثبات می‌کند که:
یک گراف کامل، مسطح است اگر و فقط اگر شامل هیچ زیر گرافی که با گراف کامل ۵ تایی یا با گراف جفت کامل سه تایی (گرافی جفت کامل با دو بخش با اندازه 3) homeomorphic نباشد.
Vijay Vazirani الگوریتم FKT را برای گراف‌هایی که شامل زیر گراف جفت کامل سه تایی نمی‌شوند گسترش داده است. از آنجا که شمارش تعداد تطابق کامل در یک گراف عمومی P-کامل می‌باشد، محدودیت‌هایی بر روی گراف ورودی باید اعمال شود مگر اینکه FP (نسخه ای تابعی از P) برابر با P باشد. شمارش تطابق‌ها، که با نام اندیس Hosoya شناخته می‌شود نیز حتی برای گراف‌های مسطح هم، یک مسئله P-کامل می‌باشد.
الگوریتم > کاربردها

الگوریتم FKT کاربرد زیادی در الگوریتم‌های هولوگرافیک بر روی گراف‌های مسطح در میان دروازه‌های انطباق دارد. برای مثال، نسخه مسطح از مدل یخ آورده شده در بالا را در نظر بگیرید که نام تکنیکی آن PL-3-NAE-SAT می‌باشد (که NAE در آن به معنای همه برابر نیستند می‌باشد). Valiant یک الگوریتم زمان چندجمله ای برای این مسئله پیدا نموده است که از دروازه‌های انطباق استفاده می‌کند.
منابع و مراجع

↑  Hayes, Brian (January–February 2008), "Accidental Algorithms", American Scientist
↑  Baxter, R. J. (2008) [1982]. Exactly Solved Models in Statistical Mechanics (Third ed.). Dover Publications. p. 11. ISBN 978-0-486-46271-4. Archived from the original on 20 March 2012. Retrieved 9 June 2015.
↑  Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji (2010). Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. Las Vegas, NV, USA: IEEE. arXiv:1008.0683. {{cite conference}}: External link in |conferenceurl= (help); Unknown parameter |conferenceurl= ignored (|conference-url= suggested) (help)
↑  Cayley, Arthur (1847). "Sur les determinants gauches" [On skew determinants]. Crelle's Journal. 38: 93–96.
↑  Vazirani, Vijay V. (1989). "NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems". Information and Computation. 80 (2): 152–164. doi:10.1016/0890-5401(89)90017-5. ISSN 0890-5401.
↑  Jerrum, Mark (1987), "Two-dimensional monomer-dimer systems are computationally intractable", Journal of Statistical Physics, 48 (1): 121–134, doi:10.1007/BF01010403.
↑  Valiant, Leslie G. (2004). "Holographic Algorithms (Extended Abstract)". Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. FOCS'04. Rome, Italy: IEEE Computer Society. pp. 306–315. doi:10.1109/FOCS.2004.34. ISBN 0-7695-2228-9. {{cite conference}}: |access-date= requires |url= (help); |archive-url= requires |url= (help); External link in |conferenceurl= (help); Unknown parameter |conferenceurl= ignored (|conference-url= suggested) (help)
لینک‌های مرتبط

Presentation by Ashley Montanaro about the FKT algorithm
More history, information, and examples can be found in chapter 2 and section 5.3.2 of Dmitry Kamenetsky's PhD thesis
مثالی برای روش پیدا کردن جهات Pfaffian با استفاده از الگوریتم FKT
اندیس مس شوین (۳)

| مس شوین (۳)> موقعیت | مس شوین (۳)> موقعیت |
| --- | --- |
استان: استان سیستان و بلوچستان
فاصله: فاصله
فاصله تا فرودگاه: ۱۳۵ کیلومتر
فاصله تا راه‌آهن: ۱۳۵ کیلومتر
فاصله تا نزدیک‌ترین شهر: ۱۳۵ کیلومتر
فاصله تا نزدیک‌ترین روستا: ۱۰ کیلومتر
فاصله تا مرکز استان: ۱۳۵ کیلومتر
ارتفاع بلندترین نقطه: ۱۶۹۳ متر
ارتفاع: ۱۸۴۸ متر
مشخصات فنی معدن: مشخصات فنی معدن
مشخصات فنی کانی: مشخصات فنی کانی
فرمول شیمیایی: Cu۲CO۳(OH)۲
نوع کانه: مالاکیت
سنگ معدن: سنگ معدن
ژنز: آذرین
سنگ میزبان: کالرد ملانژ-هورنفلس
سن سنگ میزبان: کرتاسه بالایی- پالئوسن
شکل: رگه ای
زلزله: زلزله
وضعیت لرزه‌خیزی ناحیه: غیر فعال
نام اندیس: مس شوین (۳)
نوع اندیس: فلزی
نام ماده: مس
نوع ماده: فلزی
مس شوین (۳) یک اندیس فلزی است که در  استان سیستان و بلوچستان قرار دارد و مادهٔ معدنی موجود در آن، مس است.سنگ میزبان این اندیس کالرد ملانژ-هورنفلس است و دیرینگی آن به دوران کرتاسه بالایی- پالئوسن می‌رسد.
بازوپیمایی

میمون عنکبوتی جفری در حال بازوپیمایی.
بازوپیمایی (به انگلیسی: Brachiation) شیوه‌ای از جابجایی مکانی در درختان است که در آن، جانور با استفاده از بازوها و دست‌های خود تاب می‌خورد و از درختی به درخت دیگر می‌رود.
بازوپیماهای اصلی در میان جانوران، میمون‌ها، میمون‌های درازدست و سیامانگ‌ها هستند.
میمون‌های درازدست می‌توانند با سرعت ۵۵ کیلومتر در ساعت حرکت کنند و در هر تاب‌خوردن مسافت ۶ متر را بپیمایند.
میمون‌های عنکبوتی و اورانگوتان‌ها را جانورانی نیمه‌بازوپیما می‌نامند.
داشتن ناخن‌های کوتاه به‌جای پنجه، انگشت‌های چنگکی، انگشت شست روبروی هم، ساعدهای دراز، و مفصل‌های چرخندهٔ شانه، از ویژگی‌هایی هستند که بازوپیمایی در نخستی‌ها را تسهیل کرده‌است.
ویژگی‌های جسمانی انسان امروزی نشان می‌دهد که انسان‌ها نیایی بازوپیما داشته‌اند. مفصل‌های انعطاف‌پذیر شانه‌ها و انگشت‌های مناسبِ گیرش در انسان‌ها، از جملهٔ این نشانه‌ها هستند. کالبدشناسی انسان نشان می‌دهد که بازوپیمایی احتمالاً یک پیش‌سازگاری برای راه رفتن بر روی دو پا بوده‌است.
یانوشوویتسه (گمینا ژلونکی)

| یانوشوویتسه (گمینا ژلونکی) | یانوشوویتسه (گمینا ژلونکی) |
| --- | --- |
Village: Village
یانوشوویتسه (گمینا ژلونکی): یانوشوویتسه (گمینا ژلونکی)
مختصات: ۵۰°۸′۴۴″ شمالی ۱۹°۵۳′۴۴″ شرقی﻿ / ﻿۵۰٫۱۴۵۵۶°شمالی ۱۹٫۸۹۵۵۶°شرقی﻿ / 50.14556; 19.89556: مختصات: ۵۰°۸′۴۴″ شمالی ۱۹°۵۳′۴۴″ شرقی﻿ / ﻿۵۰٫۱۴۵۵۶°شمالی ۱۹٫۸۹۵۵۶°شرقی﻿ / 50.14556; 19.89556
کشور:  لهستان
استان‌های لهستان: استان لهستان کوچک‌تر
County: شهرستان کراکوف
گمینا: گمینا ژلونکی
یانوشوویتسه (به لاتین: Januszowice) یک روستا در لهستان است که در گمینا ژلونکی واقع شده‌است.
اندرو جانسون (بازیکن فوتبال)

| 0 | 1 | 2 | 3 |
| --- | --- | --- | --- |
 Johnson training with باشگاه فوتبال فولام in 2008:  Johnson training with باشگاه فوتبال فولام in 2008
اطلاعات شخصی: اطلاعات شخصی
نام کامل:  Andrew Johnson
زادروز:  ۱۰ فوریهٔ ۱۹۸۱ ‏(۴۳ سال)
زادگاه:  بدفورد، انگلستان
قد:  ۵ فوت ۹ اینچ (۱٫۷۵ متر)
پست:  مهاجم
باشگاه‌های جوانان: باشگاه‌های جوانان
:  لوتون تاون
۰۰۰–۱۹۹۸:  بیرمنگام سیتی
باشگاه‌های حرفه‌ای*: باشگاه‌های حرفه‌ای*
| سال‌ها |  باشگاه‌ها |  بازی† |  (گل)† |
| ۱۹۹۸–۲۰۰۲ |  بیرمنگام سیتی |  ۸۳ |  (۸) |
| ۲۰۰۲–۲۰۰۶ |  کریستال پالاس |  ۱۴۰ |  (۷۴) |
| ۲۰۰۶–۲۰۰۸ |  اورتون |  ۶۱ |  (۱۷) |
| ۲۰۰۸–۲۰۱۲ |  فولام |  ۸۶ |  (۱۳) |
| ۲۰۱۲–۲۰۱۴ |  کویینز پارک رنجرز |  ۲۰ |  (۲) |
| ۲۰۱۴–۲۰۱۵ |  کریستال پالاس |  ۰ |  (۰) |
| مجموع |   |  ۳۹۰ |  (۱۱۴) |
تیم ملی: تیم ملی
| ۲۰۰۵–۲۰۰۷ |  تیم ملی فوتبال انگلستان |  ۸ |  (۰) |
 تعداد بازی‌ها و گل‌ها فقط مربوط به بازی‌های لیگ داخلی است. :  تعداد بازی‌ها و گل‌ها فقط مربوط به بازی‌های لیگ داخلی است. 
اندرو جانسون (انگلیسی: Andrew Johnson؛ زادهٔ ۱۰ فوریهٔ ۱۹۸۱) یک بازیکن فوتبال در پست مهاجم اهل انگلستان است.