Skip to main content
SUPERVISOR
Reza Rezaeian farashahi,Amir Hashemi
رضا رضائیان فراشاهی (استاد مشاور) امیر هاشمی (استاد راهنما)
 
STUDENT
Samira Abolhasani
سمیرا ابوالحسنی کوپائی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1396

TITLE

Grobner Basis Conversion
One of the most powerful computational tools associated with polynomial ideals is the concept of Gr?bner bases. In fact, the main purpose of introducing the Gr?bner bases is to find a basis for an ideal quotient space (as a vector space). Gr?bner bases together with the first algorithm to compute them were introduced by Buchberger in his PhD thesis [10]. The Buchberger algorithm has in practice a high computational complexity. To solve this problem, Buchberger proposed two criteria to make his algorithm faster and more powerful. In 1983, Lazard [32] developed a new approach by using linear algebra techniques to compute Gr?bner bases. In 1992, M?ller et al. in [35], calculated the Gr?bner bases with a less complexity and higher velocity with the optimal use of the reduction to zero. In 1999 Faugère [22], designed the F4 algorithm using the relation between the Gr?bner bases and linear algebra.
پایه گربنر یکی از ابزارهای محاسباتی برای مطالعه ایده‌آل‌های چندجمله‌ای است که توسط بوخبرگر در سال 19?? معرفی شد. محاسبه پایه گربنر به عوامل زیادی وابسته است که یکی از آن‌ها ترتیب تک‌جمله‌ای است. در صورتی که فقط یک پایه گربنر مورد نیاز باشد از ترتیب الفبایی معکوس مدرج ( ?drl) برای محاسبه آن استفاده می شود، زیرا از لحاظ زمانی سریع‌تر و دارای پیچیدگی محاسباتی کمتری است. اما در بسیاری از کاربردها نیاز به محاسبه پایه گربنر نسبت به ترتیب الفبایی ( ?lex) است. یکی از سوالات مطرح در این زمینه این است که چگونه می‌توان یک پایه گربنر نسبت به ( ?drl) حساب کرد و آن را به یک پایه گربنر نسبت به ( ?lex) تبدیل کرد. برای ایده‌آل‌های صفر بعدی، فوژر و همکاران با معرفی الگوریتم FGLM و با استفاده از تکنیک‌های جبرخطی یک پایه گربنر را به صورت خیلی سریع به یک پایه گربنر دیگر تبدیل می‌کنند. البته برای ایده‌آل‌های با بعد مثبت این کار خیلی سخت‌تر است و کلارت و همکاران الگوریتم Gr?bnerWalk را برای این موضوع مطرح کردند. در این پایان نامه، به معرفی، بررسی و تحلیل پیچیدگی این الگوریتم ها خواهیم پرداخت.

ارتقاء امنیت وب با وف بومی