Μια εισαγωγή στις βάσεις Gröbner

An Introduction to Gröbner Bases (Αγγλική)

  1. MSc thesis
  2. ΓΕΩΡΓΙΟΣ ΓΙΑΝΝΟΠΟΥΛΟΣ
  3. Μεταπτυχιακές Σπουδές στα Μαθηματικά (ΜΣΜ)
  4. 23 Σεπτεμβρίου 2023
  5. Ελληνικά
  6. 176
  7. ΑΡΒΑΝΙΤΟΓΕΩΡΓΟΣ ΑΝΔΡΕΑΣ
  8. ΠΑΠΑΔΟΠΟΥΛΟΣ ΒΑΣΙΛΕΙΟΣ
  9. Μονώνυμα | Πολυώνυμα | Δακτύλιος | Iδεώδη | Σώμα | Aλγόριθμος της Διαίρεσης | Ευκλείδειος Aλγόριθμος | Διάταξη Μονωνύμων | Λήμμα του Dickson | Βάση του Hilbert | Αλγόριθμος του Buchberger | Γραμμικά Συστήματα | Απαλοιφή Gauss | Αφινικές Πολλαπλότητες | Βάσεις Gröbner | Wolfram Mathematica | Τορικά ιδεώδη | Nullstellensatz | Ομοπαραλληλική (Αφινική) γεωμετρία
  10. Άλγεβρα και Γεωμετρία /MSM 85
  11. 4
  12. 8
  13. Συμπεριλαμβλάνονται σχήματα, εικόνες, γραφήματα δισδιάστατα-τρισδιάστατα
    • Η παρούσα διπλωματική εργασία είναι ένας συνδυασμός της αντιμεταθετικής άλγεβρας και της αλγεβρικής γεωμετρίας, στοχεύει στον τρόπο επίλυσης τεσσάρων προβλημάτων που θα μας ήταν αδύνατον να λύσουμε ή να αναζητήσουμε λύσεις κάποιας μορφής, χωρίς την κατάλληλη μεθοδολογία και τεχνολογία. Η εργασία είναι χωρισμένη σε έξι κεφάλαια .
      Αρχικά, στο πρώτο κεφάλαιο, στην εισαγωγή γίνεται αναφορά στη χρήση των βάσεων Gröbner, αλλά και σε ιστορικά στοιχεία. Στη συνέχεια, μελετάμε την αφηρημένη άλγεβρα και τις αλγεβρικές δομές, εισάγουμε περιληπτικά βασικούς ορισμούς και θεωρήματα χωρίς αιτιολόγηση, παραδείγματα και αποδείξεις, επειδή τα θεωρούμε ήδη γνωστά .
      Στο δεύτερο κεφάλαιο, μελετάμε πιο ενδελεχώς τις μαθηματικές έννοιες και τους ορισμούς, επικεντρωνόμαστε στα ιδεώδη και χρησιμοποιούμε διάφορους αλγορίθμους οι οποίοι είναι γραμμένοι σε μορφή «ψευδοκώδικα» .
      Στο τρίτο κεφάλαιο, απαριθμούμε τα προβλήματα που δεν θα μπορούσαμε να επιλύσουμε χωρίς την βοήθεια των βάσεων Gröbner, καθώς και προεισαγωγικά στοιχεία που μας είναι απαραίτητα πριν δώσουμε τον τελικό ορισμό. Όπως την διάταξη των μονωνύμων, αναλύουμε τρεις διατάξεις τη λεξικογραφική, τη διαβαθμισμένη και την ανάποδη διαβαθμισμένη διάταξη, από τις άπειρες που υπάρχουν. Το επίπεδο σαφώς γίνεται πιο σύνθετο, καθώς μελετάμε δακτυλίους πολυωνύμων περισσοτέρων μεταβλητών, βλέπουμε τη μορφή του αλγόριθμου της διαίρεσης περισσοτέρων μεταβλητών πως λειτουργεί με παραδείγματα αλλά και σε κώδικα και εν τέλει μελετάμε το λήμμα του Dickson.
      Στο τέταρτο κεφάλαιο, εισάγουμε τον ορισμό της βάσης Hilbert ταυτόχρονα με των βάσεων Gröbner που είναι και το κύριο θέμα της εργασίας μας και βλέπουμε διάφορες εφαρμογές και ιδιότητές τους. Η πιο σημαντική είναι το λεγόμενο κριτήριο του Buchberger, ο οποίος είναι και ο δημιουργός των βάσεων Gröbner, που κάνει εκτεταμένη την χρήση τους πάνω σε αλγορίθμους που χειρίζονται συστήματα πολυωνυμικών εξισώσεων.

      Ωστόσο, όπως θα δούμε και στην εργασία μας ο αρχικός αλγόριθμός του Buchberger επιδέχεται τροποποίηση και βελτίωση, ώστε να γίνει αποδοτικότερος, πιο δαιχειρίσιμος και πιο κατανοητός, όπως μπορεί να γίνει αυτό αντιληπτό από το πέμπτο κεφάλαιο της εργασίας. Επομένως, στο ίδιο κεφάλαιο βλέπουμε διάφορες εφαρμογές, προχωράμε αναλυτικά στην επίλυση των προβλημάτων που θεσπίσαμε στο πρώτο κεφάλαιο με πληθώρα παραδειγμάτων και γραφημάτων με την βοήθεια προγράμματος ηλεκτρονικού υπολογιστή. Λόγω της εξέλιξης και της ανάπτυξης ηλεκτρονικών υπολογιστών, που είναι αρκετά γρήγοροι για να τρέχουν αυτούς τους αλγόριθμους, μπορούμε να προχωρήσουμε στην επίλυση τέτοιων προβλημάτων που θα μας ήταν αδύνατον να τα επιλύσουμε δια χειρός και έχουν κατορθώσει να αλλάξουν τον τρόπο που οι μελετητές προσεγγίζουν τα θέματα που αφορούν την αλγεβρική γεωμετρία αλλά και την αντιμεταθετική άλγεβρα. Για αυτό λόγο η συγκεκριμένη εργασία δεν επικεντρώνεται μόνο σε όσους έχουν μαθηματικό ενδιαφέρον αλλά και σε όσους ασχολούνται με τον τομέα των υπολογιστών και της μηχανικής, οι οποίοι χρησιμοποιούν αυτές τις τεχνικές σε πληθώρα προβλημάτων. Αυτό, μπορεί να το παρατηρήσει κανείς και οπτικά, αφού στα τέλη του πέμπτου κεφαλαίου της εργασίας, απεικονίζονται και τρισδιάστατα μοντέλα προβλημάτων, που αναζητούν επίλυση, καθώς και η χρήση της Mathematica που με την πολύτιμη βοήθειά της μπορούμε να βρούμε βάσεις Gröbner που αναφέρονται σε πολύ απαιτητικά συστήματα εξισώσεων πολύ γρήγορα με μία μονάχα εντολή. Όπως προαναφερθήκαμε, θα μας ήταν αρκετά χρονοβόρο εάν το επιχειρούσαμε χωρίς την χρήση ηλεκτρονικού υπολογιστή .
      Στο τελευταίο κεφάλαιο μελετάμε πιο σύνθετες εφαρμογές των βάσεων Gröbner σε τομείς της τοπολογίας και της θεωρίας γράφων περιληπτικά, όπως και στο συσχετισμό μεταξύ άλγεβρας και γεωμετρίας, απεικονίζοντας τα ιδεώδη σε πολλαπλότητες και το αντίστροφο.

    • The present thesis is a combination of commutative algebra and algebraic geometry, aims at how to solve four problems that would be impossible for us to solve or seek solutions of some form, without the appropriate methodology and technology. The paper is divided into six chapters .
      In the first chapter, in the introduction we refer to their use and to historical facts of Gröbner bases. Then, we study abstract algebra and algebraic structures, we briefly introduce basic definitions and theorems without justification, examples and proofs, because we consider them familiar .
      In the third section, we list the problems that we could not solve without Gröbner bases, as well as preliminary elements that are necessary before we give the final definition. Like the ordering of monomials, we analyze three orders the lexicographic, the graded and the inverse graded ordering, out of the infinite ones that exist. The level clearly is more complex, because of the more variables, we see the form of the algorithm of the division of more variables how it works with examples and in code and finally we study Dickson's lemma .
      In the fourth chapter, we introduce the definition of Hilbert basis at the same time as Gröbner bases which is the main topic of our paper and we see their various applications and properties. The most important one is the so-called Buchberger criterion, who is also the creator of Gröbner bases, which makes extensive use of them over algorithms handling systems of polynomial equations .
      However, as we will see in our paper, Buchberger's original algorithm is amenable to modification and improvement in order to make it more efficient, more manageable and more understandable, as can be seen from the fifth chapter of. Therefore, in the same chapter we see various applications, we proceed in detail to solve the problems established in the first chapter with a wealth of examples, graphs with the help of a computer program. Due to the evolution and development of computers, which are fast enough to run these algorithms, we can proceed to solve such problems that would have been impossible for us to solve by hand and have managed to change the way scholars approach the topics concerning algebraic geometry and commutative algebra. For this reason, this paper focuses not only on those with a mathematical interest but also on those in the field of computers and engineering, who use these techniques in a multitude of problems. This, can also be observed visually, since at the end of the paper, three-dimensional models of problems, which were looking for a solution, are also illustrated, as well as the use of Mathematica, with its valuable help we can find Gröbner bases referring to very demanding systems of equations very quickly with a single command. Otherwise, it would be quite time-consuming if we attempted it without the use of a computer .
      In the last chapter we study more complex applications of Gröbner bases in the fields of topology and graph theory briefly, as in the correlation between algebra and geometry, mapping ideals into varieties and vice versa .

  14. Hellenic Open University
  15. Αναφορά Δημιουργού - Μη Εμπορική Χρήση - Παρόμοια Διανομή 4.0 Διεθνές