Skip to main content
SUPERVISOR
Mehdi Tatari varnosfaderani,Amir Hashemi
مهدی تاتاری ورنوسفادرانی (استاد مشاور) امیر هاشمی (استاد راهنما)
 
STUDENT
Fateme Akbari
فاطمه اکبری

FACULTY - DEPARTMENT

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

TITLE

Computing Grobner basis for an ideal of points and studing its complexity
This master thesis has been prepared based on the \\cite{A}, \\cite{5A} and \\cite{Gao} . Let $P= k[x_{1}, \\ldots ,x_{n} ]$ be the polynomial ring in $ n $ variables over a field $ k$ . The vanishing ideal with respect to a set of points $ \\mathbb{X}= \\{p_{1}, \\ldots ,p_{m} \\} \\subseteq k^{n}$ is defined as the set of all elements in $P$ that are zero on all of the $ p_{i}$ 's (this set is an ideal of P and is denoted by $ I( \\mathbb{X} )$ ). The problem that we address in this thesis to compute the reduced Gr{\\ quot;o}bner basis for the vanishing ideal of any finite set of points, under any given monomial order. A polynomial time algorithm for this problem was first given by Buchberger and M{\\ quot;o}ller (1982) \\cite{53} , and significantly improved by Marinari, M{\\ quot;o}ller and Mora (1993) \\cite{510} , and Abbott, Bigatti, Kreuzer and Robbiano (2000) \\cite{51} . These algorithms perform Gauss elimination on a generalized Vandermonde matrix and have a polynomial time complexity.
امروزه مجموعه‌های متناهی از نقاط و ایده‌آل نظیر آن یک شاخه فعال و مورد توجه در هندسه جبری است. اهمیت استفاده از مجموعه نقاط در مدل‌سازی‌های جبری برای حل برخی مسائل در علوم دیگر ، نظیر زیست‌شناسی و کدگذاری ، موجب شده است که مطالعه جبری مجموعه نقاط به یک ابزار قوی در هندسه جبری تبدیل شود. در محاسبه یک مجموعه مولد برای ایده‌آل نظیر یک مجموعه متناهی نقاط، بر خلاف روند حل دستگاه‌های معادلات چندجمله‌ای ، به دنبال یافتن چندجمله‌ای‌هایی هستیم که مقدار آن‌ها در نقاط مجموعه صفر شود. الگوریتم محاسبه چنین مجموعه مولدی در سال 1982 توسط بوخبرگر و مولر معرفی شد. این مجموعه مولد ، نوع خاصی از مجموعه مولد ایده‌آل‌ها ، به نام پایه گربنر است. لازم به ذکر است که این پایه در سال 1965 در رساله دکتری بوخبرگر ارائه شده و یکی از مهم‌ترین ابزارهای مطالعه ایده‌آل‌ها در جبر محاسباتی است. در این رساله به مطالعه ایده‌آل نقاط ، الگوریتم محاسبه پایه گربنر این ایده‌آل، پیچیدگی محاسباتی آن و ویژگی‌های خاص فضای برداری نظیر آن می‌پردازیم.

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