توپولوژی محاسباتی
 | این مقاله نیازمند تمیزکاری است. لطفاً تا جای امکان آنرا از نظر املا، انشا، چیدمان و درستی بهتر کنید، سپس این برچسب را بردارید. محتویات این مقاله ممکن است غیر قابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد. |
توپولوژی الگوریتمی یا توپولوژی محاسباتی یک زیر مجموعه از توپولوژی است که بخش‌هایی از علم کامپیوتر را نیز تحت پوشش قرار می‌دهد به ویژه هندسه محاسباتی و نظریه پیچیدگی محاسباتی.
هدف اصلی از توپولوژی الگوریتمی، همان‌طور که از نام ان معلوم است، توسعه الگوریتم‌های کارآمد برای حل مسائلی در زمینه‌هایی مانند هندسه محاسباتی، گرافیک، روباتیک، زیست‌شناسی ساختاری و شیمی، به وسیلهٔ روش‌های توپولوژی محاسباتی است.
الگوریتم‌های مهم براساس موضوع[ویرایش]
تئوری الگوریتم ۳-فیلد[ویرایش]
یک خانواده بزرگ از الگوریتم‌های مربوط به ۳-فیلدی در اطراف تئوری سطح عادی چرخش می‌شود، که شامل چندین تکنیک برای تبدیل مشکلات در نظریهٔ ۳-فیلدی به مشکلات برنامه‌نویسی خطی عددی می‌شود.
الگوریتم شناسایی ۳ حلقه رابینستن و تامپسون. این یک الگوریتم است که به عنوان ورودی یک ۳-فیلدی مثلثی را می‌گیرد و تعیین می‌کند که آیا این فیلد به کره ۳ خانه متوسل است یا نه. این دوره زمان‌سنجی در تعداد سمپل‌های چهارگانه در ابتدای ۳-فیلدی و همچنین یک پروفایل حافظه نمایشی است. علاوه بر این، آن در بسته نرم‌افزاری Regina اجرا می‌شود. ساول شلیمر در ادامه نشان داد که مشکل در کلاس پیچیدگی NP است. علاوه بر این، رافائل زنتنر نشان داد که مشکل در کلاس پیچیدگی coNP، با فرض فرضیه عمومی ریمان، وجود دارد. او از تئوری هندسه سازی ۳-فیلدی‌ها و کار گرگ کاپربرگ در پیچیدگی تشخیص گره استفاده می‌کند.
تجزیه حاصل از اتصال۳-فیلدی‌ها نیز در Regina اجرا می‌شود که دارای زمان اجرا نمایی است و براساس یک الگوریتم مشابه الگوریتم شناسایی سه‌بعدی است.
تعیین اینکه ۳ فیلدی‌ها دارای هیچ سطح تراکم ناپذیر نیست توسط برتون، رابین اشتین و و براساس تئوری سطح نرمال پیاده‌سازی شده‌است.
الگوریتم مانینگ الگوریتمی است برای پیدا کردن ساختارهای هذلولی در ۳-فیلدی‌ها است که گروه اصلی آن‌ها راه‌حل مشکل کلمه را دارد.
در حال حاضر تجزیه JSJ الگوریتمی در نرم‌افزار رایانه انجام نشده‌است. همچنین تجزیه فشرده ساز بدن. برخی از اکتشافات بسیار محبوب و موفقیت‌آمیز مانند SnapPea وجود دارد که ساختار تقریبی هذلولی را در محورهای سه بعدی منحصر به فرد دارد. شناخته شده‌است که طبقه‌بندی کامل ۳-فیلدی‌ها می‌تواند به صورت الگوریتمی انجام شود.
الگوریتم تبدیل[ویرایش]
SnapPea یک الگوریتم را برای تبدیل یک گره فلانار یا پیوند به یک مثلث کلاسیک پیاده‌سازی می‌کند. این الگوریتم دارای زمان اجرا تقریباً خطی در تعداد عبور در نمودار و مشخصات حافظه پایین است. الگوریتم شباهت به الگوریتم Wirthinger برای ساخت سخنرانی‌های گروه پایه مکمل‌های پیوند داده شده توسط نمودارهای مسطح است. به همین ترتیب، SnapPea می‌تواند ارائه‌های جراحی ۳ مینی فولد را به سه دسته ای از مینی فولد ارائه شده تبدیل کند.
D.Thurston و F.Costantino یک روش برای ساخت یک چهارم منیفولد مثلثی از یک مینی فولد مثلثی سه بعدی دارند. به همین ترتیب می‌توان آن را برای ساخت ارائه‌های جراحی از سه مونوفولد مثلثی استفاده کرد، اگرچه روش به‌طور الگوریتم به‌طور الگوریتم به‌طور اصولی نوشته نشده‌است، اما باید زمان چندجمله‌ای را در تعداد تتراهدهای سه بعدی مثلثی سه بعدی ایجاد کرد.]
S. Schleimer دارای یک الگوریتم است که یک منحنی triangulated 3-manifold را تولید می‌کند، با توجه به ورودی کلمه (در ژنراتور پیچ و تاب دنی) برای گروه طبقه‌بندی سطح. ۳-مانیفولد آن است که کلمه را به عنوان نقشه اتصال برای تقسیم Heegaard از مینی فوله ۳ استفاده می‌کند. الگوریتم بر اساس مفهوم triangulation لایه ای است.
نظریهٔ گرهٔ الگوریتمی[ویرایش]
شناختن اینکه آیا گره بی‌اهمیت است یا نه، شناخته شده‌است در کلاس پیچیدگی NP
مشکل تعیین جنس گره شناخته شده‌است که کلاس پیچیدگی PSPACE دارد.
الگوریتم‌های چندجمله‌ای زمان برای محاسبه چندجمله‌ای الکساندر گره وجود دارد.
هماتوتیپی محاسباتی[ویرایش]
روش‌های محاسباتی برای گروه‌های homotopy از کره.
روش‌های محاسباتی برای حل سیستم‌های معادلات چند جمله ای.
براون یک الگوریتم را برای محاسبه گروه‌های هماتوپیپی از فضاهایی که مجتمع‌های Postnicovov محدود است، گرچه به‌طور گسترده قابل اجرا نیست.
هماهنگی محاسباتی[ویرایش]
محاسبه گروه‌های همولوگ از مجتمع‌های سلولی به آوردن ماتریس مرز به فرم طبیعی اسمیت کاهش می‌یابد. اگرچه این الگوریتم به‌طور کامل حل شده‌است، اما محاسبات کارآمد برای مجتمع‌های بزرگ، موانع فنی متعددی وجود دارد. دو موانع مرکزی وجود دارد. اولاً، الگوریتم فرم اسمیت اساسی پیچیدگی مکعبی در اندازه ماتریس است، زیرا از عملیات ردیف و ستون استفاده می‌کند که برای مجموعه‌های بزرگ سلولی نامناسب است. در مرحله دوم، ماتریس‌های متوسط که نتیجه استفاده از الگوریتم فرم اسمیت را پر می‌کنند، حتی اگر یک شروع و پایان با ماتریس‌های نزولی باشد.
الگوریتم شکل طبیعی فرم اسمیت کارآمد و احتمالی است، همان‌طور که در کتابخانه LinBox یافت می‌شود.
کاهش هماتوپونیک ساده برای محاسبات هماهنگی قبل از پردازش، همان‌طور که در بسته نرم‌افزاری Perseus است.
الگوریتم برای محاسبه همگرایی پایدار از مجموعه‌های فیلتر شده.