Υπολογιστική άλγεβρα

Συμβολική ολοκλήρωση της αλγεβρικής συνάρτησης] $f (x) = x / \sqrt x 4 + 10 x 2 - 96 x - 71$ με τη χρήση του συστήματος άλγεβρας υπολογιστών ΄΄Άξιωμα (σύστημα άλγεβρας υπολογιστών)

Στα μαθηματικά και την επιστήμη των υπολογιστών,^[1] η υπολογιστική άλγεβρα, επίσης γνωστή ως συμβολικός υπολογισμός ή αλγεβρικός υπολογισμός, είναι ένα επιστημονικό πεδίο που αναφέρεται στη μελέτη και την ανάπτυξη αλγορίθμων και λογισμικού για τον χειρισμό μαθηματικών εκφράσεων και άλλων μαθηματικών αντικειμένων. Αν και η υπολογιστική άλγεβρα μπορεί να θεωρηθεί υποπεδίο του επιστημονικού λογισμού, γενικά θεωρούνται διακριτοί τομείς, επειδή ο επιστημονικός λογισμός βασίζεται γενικά στον αριθμητικό υπολογισμό με προσεγγιστικούς αριθμούς κινητής υποδιαστολής, ενώ ο συμβολικός λογισμός δίνει έμφαση στον ακριβή υπολογισμό με εκφράσεις που περιέχουν μεταβλητές που δεν έχουν δεδομένη τιμή και χειρίζονται ως σύμβολα.

Οι εφαρμογές λογισμικού που εκτελούν συμβολικούς υπολογισμούς ονομάζονται συστήματα άλγεβρας υπολογιστών, με τον όρο σύστημα να υποδηλώνει την πολυπλοκότητα των κύριων εφαρμογών που περιλαμβάνουν, τουλάχιστον, μια μέθοδο για την αναπαράσταση μαθηματικών δεδομένων σε έναν υπολογιστή, μια γλώσσα προγραμματισμού χρήστη (συνήθως διαφορετική από τη γλώσσα που χρησιμοποιείται για την υλοποίηση), έναν ειδικό διαχειριστή μνήμης, μια διεπαφή χρήστη για την είσοδο/έξοδο μαθηματικών εκφράσεων, ένα μεγάλο σύνολο συνηθισμένων πράξεων, όπως απλοποίηση εκφράσεων, διαφοροποίηση με χρήση αλυσιδωτού κανόνα, παραγοντοποίηση πολυωνύμων, αόριστη ολοκλήρωση, κ.λπ.

Η υπολογιστική άλγεβρα χρησιμοποιείται ευρέως για πειράματα στα μαθηματικά και για το σχεδιασμό των τύπων που χρησιμοποιούνται σε αριθμητικά προγράμματα. Χρησιμοποιείται επίσης για πλήρεις επιστημονικούς υπολογισμούς, όταν οι αμιγώς αριθμητικές μέθοδοι αποτυγχάνουν, όπως στην κρυπτογραφία δημόσιου κλειδιού, ή για ορισμένα μη γραμμικά προβλήματα.

Ορολογία[Επεξεργασία | επεξεργασία κώδικα]

Ορισμένοι συγγραφείς διακρίνουν την υπολογιστική άλγεβρα από τον συμβολικό υπολογισμό χρησιμοποιώντας το τελευταίο όνομα για να αναφερθούν σε είδη συμβολικού υπολογισμού εκτός από τον υπολογισμό με μαθηματικούς τύπους. Ορισμένοι συγγραφείς χρησιμοποιούν τον συμβολικό υπολογισμό για την πτυχή της επιστήμης των υπολογιστών και την "υπολογιστική άλγεβρα" για τη μαθηματική πτυχή^[2]. Χαρακτηριστικά, ονομάζεται calcul formel στα γαλλικά, που σημαίνει "τυπικός υπολογισμός". Το όνομα αυτό αντανακλά τους δεσμούς που έχει το πεδίο αυτό με τις τυπικές μεθόδους.

Ο συμβολικός υπολογισμός έχει επίσης αναφερθεί, στο παρελθόν, ως συμβολικός χειρισμός, αλγεβρικός χειρισμός, συμβολική επεξεργασία, συμβολικά μαθηματικά ή συμβολική άλγεβρα, αλλά αυτοί οι όροι, οι οποίοι επίσης αναφέρονται σε μη υπολογιστικό χειρισμό, δεν χρησιμοποιούνται πλέον σε σχέση με την υπολογιστική άλγεβρα.

Επιστημονική κοινότητα[Επεξεργασία | επεξεργασία κώδικα]

Δεν υπάρχει καμία επιστημονική εταιρεία που να ασχολείται ειδικά με την υπολογιστική άλγεβρα, ωστόσο αυτή τη δραστηριότητα ανέλαβε η ομάδα ειδικού ενδιαφέροντος της Ένωσης για τα Μηχανήματα Υπολογιστών (Association for Computing Machinery) με την ονομασία SIGSAM (Ειδική ομάδα ενδιαφέροντος για τον συμβολικό και αλγεβρικό χειρισμό)^[3].

Υπάρχουν διάφορα ετήσια συνέδρια για την υπολογιστική άλγεβρα, με κυριότερο το ISSAC (International Symposium on Symbolic and Algebraic Computation), το οποίο χρηματοδοτείται τακτικά από το SIGSAM^[4].

Υπάρχουν αρκετά περιοδικά που ειδικεύονται στην υπολογιστική άλγεβρα, με κορυφαίο το Journal of Symbolic Computation που ιδρύθηκε το 1985 από τον Μπρούνο Μπούχμπεργκερ.^[5] Υπάρχουν επίσης πολλά άλλα περιοδικά που δημοσιεύουν τακτικά άρθρα σχετικά με την υπολογιστική άλγεβρα^[6].

Πτυχές της επιστήμης των υπολογιστών[Επεξεργασία | επεξεργασία κώδικα]

Αναπαράσταση δεδομένων[Επεξεργασία | επεξεργασία κώδικα]

Καθώς το αριθμητικό λογισμικό είναι ιδιαίτερα αποτελεσματικό για προσεγγιστικούς αριθμητικούς υπολογισμούς, είναι σύνηθες, στην υπολογιστική άλγεβρα, να δίνεται έμφαση στους ακριβείς υπολογισμούς με πιστά αναπαριστώμενα δεδομένα. Μια τέτοια ακριβής αναπαράσταση συνεπάγεται ότι, ακόμη και όταν το μέγεθος της εξόδου είναι μικρό, τα ενδιάμεσα δεδομένα που παράγονται κατά τη διάρκεια ενός υπολογισμού μπορεί να αυξάνονται με απρόβλεπτο τρόπο. Αυτή η συμπεριφορά ονομάζεται διόγκωση της έκφρασης. Για να αποφευχθεί αυτό το πρόβλημα, χρησιμοποιούνται διάφορες μέθοδοι στην αναπαράσταση των δεδομένων, καθώς και στους αλγορίθμους που τα χειρίζονται.

Αριθμοί[Επεξεργασία | επεξεργασία κώδικα]

Τα συνήθη συστήματα αριθμών που χρησιμοποιούνται στους αριθμητικούς υπολογισμούς είναι οι αριθμοί κινητής υποδιαστολής και οι ακέραιοι αριθμοί σταθερού περιορισμένου μεγέθους. Κανένα από αυτά δεν είναι βολικό για την υπολογιστική άλγεβρα, λόγω της διόγκωσης της έκφρασης^[7].

Ως εκ τούτου, οι βασικοί αριθμοί που χρησιμοποιούνται στην υπολογιστική άλγεβρα είναι οι ακέραιοι αριθμοί των μαθηματικών, που συνήθως αναπαρίστανται με μια απεριόριστη προσημασμένη ακολουθία ψηφίων σε κάποια βάση αρίθμησης, συνήθως τη μεγαλύτερη βάση που επιτρέπει η λέξη της μηχανής. Αυτοί οι ακέραιοι αριθμοί χρησιμοποιούνται τον ορισμό των ρητών αριθμών, οι οποίοι είναι μη αναγώγιμα κλάσματα δύο ακεραίων αριθμών.

Ο προγραμματισμός μιας αποδοτικής υλοποίησης των αριθμητικών πράξεων είναι ένα δύσκολο έργο. Ως εκ τούτου, τα περισσότερα ελεύθερα συστήματα υπολογιστικής άλγεβρας και ορισμένα εμπορικά, όπως το Mathematica και το Maple (λογισμικό),^[8]^[9] χρησιμοποιούν τη βιβλιοθήκη GMP, η οποία αποτελεί έτσι ένα εκ των πραγμάτων πρότυπο.

Εκφράσεις[Επεξεργασία | επεξεργασία κώδικα]

Αναπαράσταση της έκφρασης $(8 - 6) \times (3 + 1)$ ως δέντρο Lisp, από μια μεταπτυχιακή διατριβή του 1985.^[10]

Εκτός από τους αριθμούς και τις μεταβλητές, κάθε μαθηματική έκφραση μπορεί να θεωρηθεί ως το σύμβολο ενός τελεστή ακολουθούμενο από μια ακολουθία τελεστών. Στο λογισμικό υπολογιστικής άλγεβρας, οι εκφράσεις αναπαρίστανται συνήθως με αυτόν τον τρόπο. Αυτή η αναπαράσταση είναι πολύ ευέλικτη, και πολλά πράγματα που με την πρώτη ματιά δεν φαίνονται να είναι μαθηματικές εκφράσεις, μπορούν να αναπαρασταθούν και να χειριστούν ως τέτοιες. Παραδείγματος χάριν, μια εξίσωση είναι μια έκφραση με το "=" ως τελεστή, ένας πίνακας μπορεί να αναπαρασταθεί ως μια έκφραση με το " πίνακα" ως τελεστή και τις γραμμές του ως τελεστές.

Ακόμα και τα προγράμματα μπορούν να θεωρηθούν και να αναπαρασταθούν ως εκφράσεις με τελεστή "διαδικασία" και, τουλάχιστον, δύο τελεστές, τον κατάλογο των παραμέτρων και το σώμα, το οποίο είναι το ίδιο μια έκφραση με τον τελεστή "σώμα" και μια ακολουθία εντολών ως τελεστές. Αντίστροφα, οποιαδήποτε μαθηματική έκφραση μπορεί να θεωρηθεί ως πρόγραμμα. Παραδείγματος χάριν, η έκφραση $a' + b$ μπορεί να θεωρηθεί ως πρόγραμμα για την πρόσθεση, με $a$ και $b$ ως παραμέτρους. Η εκτέλεση αυτού του προγράμματος συνίσταται στην αξιολόγηση της έκφρασης για δεδομένες τιμές των $a$ και $b$ - αν δεν τους δοθούν τιμές, το αποτέλεσμα της αξιολόγησης είναι απλώς η είσοδός του.

Αυτή η διαδικασία της καθυστερημένης αξιολόγησης είναι θεμελιώδης στην υπολογιστική άλγεβρα. Παραδείγματος χάριν, ο τελεστής "=" των εξισώσεων είναι επίσης, στα περισσότερα συστήματα άλγεβρας υπολογιστών, το όνομα του προγράμματος του τεστ ισότητας: κανονικά, η αξιολόγηση μιας εξίσωσης οδηγεί σε μια εξίσωση, αλλά, όταν απαιτείται ένα τεστ ισότητας, είτε ζητείται ρητά από τον χρήστη μέσω μιας εντολής " αξιολόγησης σε Boolean", είτε ξεκινά αυτόματα από το σύστημα στην περίπτωση ενός τεστ μέσα σε ένα πρόγραμμα, τότε εκτελείται η αξιολόγηση σε ένα boolean αποτέλεσμα.

Καθώς το μέγεθος των τελεστών μιας έκφρασης είναι απρόβλεπτο και μπορεί να αλλάξει κατά τη διάρκεια μιας συνεδρίας εργασίας, η ακολουθία των τελεστών αναπαρίσταται συνήθως ως μια ακολουθία είτε από δείκτες (όπως στο Macsyma)^[11] είτε από καταχωρήσεις σε έναν πίνακα κατακερματισμού (όπως στο Maple).

Απλοποίηση[Επεξεργασία | επεξεργασία κώδικα]

Η απλή εφαρμογή των βασικών κανόνων της διαφοροποίησης ως προς $x$ στην έκφραση $a^{x}$ δίνει το αποτέλεσμα

x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}{a}}\right).

Μια απλούστερη έκφραση είναι γενικά επιθυμητή και η απλοποίηση είναι απαραίτητη όταν δουλεύει κανείς με γενικές εκφράσεις.

Αυτή η απλοποίηση γίνεται συνήθως μέσω κανόνων επαναγραφής^[12]. Οι απλούστεροι είναι οι κανόνες που μειώνουν πάντα το μέγεθος της έκφρασης, όπως $E - E \to 0$ ή $sin(0) \to 0$ . Εφαρμόζονται συστηματικά στα συστήματα υπολογιστικής άλγεβρας.

Η δυσκολία εμφανίζεται με πράξεις προσεταιριστικές, όπως η πρόσθεση και ο πολλαπλασιασμός. O συνήθης τρόπος αντιμετώπισης της προσεταιριστικοτητας είναι να θεωρήσουμε ότι η πρόσθεση και ο πολλαπλασιασμός έχουν αυθαίρετο αριθμό τελεστών, δηλαδή ότι $a + b + c$ αναπαρίσταται ως $"+"(a, b, c)$ . Άρα $a + (b + c)$ και $(a + b) + c$ απλοποιούνται και οι δύο σε $"+"(a', b, c)$ , το οποίο εμφανίζεται $a + b + c$ . Στην περίπτωση εκφράσεων όπως $a - b + c$ , ο απλούστερος τρόπος είναι να ξαναγράψουμε συστηματικά $- E$ , $E - F$ , $E / F$ ως, αντίστοιχα, $(-1)\cdot E$ , $E + (-1)\cdot F$ , $E \cdot F -1$ . Με άλλα λόγια, στην εσωτερική αναπαράσταση των εκφράσεων, δεν υπάρχει ούτε αφαίρεση ούτε διαίρεση ούτε μοναδιαίο μείον, εκτός της αναπαράστασης των αριθμών.

Μια άλλη δυσκολία εμφανίζεται με την αντιμεταθετικότητα της πρόσθεσης και του πολλαπλασιασμού. Το πρόβλημα είναι να αναγνωρίσει κανείς γρήγορα τους όμοιους όρους για να τους συνδυάσει ή να τους ακυρώσει. Ο έλεγχος κάθε ζεύγους όρων είναι δαπανηρός με πολύ μεγάλα αθροίσματα και γινόμενα. Για να αντιμετωπιστεί αυτό, το Macsyma ταξινομεί τους τελεστές των αθροισμάτων και των γινομένων σε μια σειρά που τοποθετεί τους όμοιους όρους σε διαδοχικές θέσεις, επιτρέποντας την εύκολη ανίχνευση. Στο Maple, μια συνάρτηση κατακερματισμού έχει σχεδιαστεί για τη δημιουργία συγκρούσεων όταν εισάγονται όμοιοι όροι, επιτρέποντας το συνδυασμό τους μόλις εισαχθούν. Αυτό επιτρέπει σε υποεκφράσεις που εμφανίζονται πολλές φορές σε έναν υπολογισμό να αναγνωρίζονται αμέσως και να αποθηκεύονται μόνο μία φορά. Αυτό εξοικονομεί μνήμη και επιταχύνει τον υπολογισμό αποφεύγοντας την επανάληψη των ίδιων πράξεων σε πανομοιότυπες εκφράσεις.

Ορισμένοι κανόνες επαναγραφής άλλοτε αυξάνουν και άλλοτε μειώνουν το μέγεθος των εκφράσεων στις οποίες εφαρμόζονται. Αυτή είναι η περίπτωση της επιμεριστικότητας ή των τριγωνομετρικών ταυτοτήτων. Παραδείγματος χάριν, ο νόμος διανεμητικότητας επιτρέπει την αναγραφή $(x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1$ και $(x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.$ Καθώς δεν υπάρχει τρόπος να γίνει μια καλή γενική επιλογή για την εφαρμογή ή όχι ενός τέτοιου κανόνα επαναγραφής, η επαναγραφή αυτή γίνεται μόνο όταν την επικαλείται ρητά ο χρήστης. Για τη διανεμητικότητα, η συνάρτηση του υπολογιστή που εφαρμόζει αυτόν τον κανόνα επαναγραφής ονομάζεται συνήθως " επέκταση ". Ο αντίστροφος κανόνας επανεγγραφής, που ονομάζεται " παράγοντας", απαιτεί έναν μη τετριμμένο αλγόριθμο, ο οποίος αποτελεί επομένως μια βασική λειτουργία στα συστήματα άλγεβρας υπολογιστών (βλ. Παραγοντοποίηση πολυωνύμων).

Μαθηματικές πτυχές[Επεξεργασία | επεξεργασία κώδικα]

Ορισμένα θεμελιώδη μαθηματικά ερωτήματα προκύπτουν όταν κάποιος θέλει να χειριστεί μαθηματικές εκφράσεις σε έναν υπολογιστή. Εξετάζουμε κυρίως την περίπτωση των πολυμεταβλητών ορθολογικών κλασμάτων. Αυτός δεν είναι ένας πραγματικός περιορισμός, διότι, μόλις απλοποιηθούν οι ρητές συναρτήσεις που εμφανίζονται σε μια έκφραση, συνήθως θεωρούνται ως νέα απροσδιόριστα. Παραδείγματος χάριν,

(\sin(x+y)^{2}+\log(z^{2}-5))^{3}

θεωρείται ως πολυώνυμο ως προς $\sin(x+y)$ και $\log(z^{2}-5)$

Ισότητα[Επεξεργασία | επεξεργασία κώδικα]

Υπάρχουν δύο έννοιες της ισότητας για τις μαθηματικές εκφράσεις. Συντακτική ισότητα είναι η ισότητα της αναπαράστασής τους σε έναν υπολογιστή. Αυτό είναι εύκολο να ελεγχθεί σε ένα πρόγραμμα. Σημασιολογική ισότητα είναι όταν δύο εκφράσεις αναπαριστούν το ίδιο μαθηματικό αντικείμενο, όπως στο

(x+y)^{2}=x^{2}+2xy+y^{2}.

Το θεώρημα του Ρίτσαρντσον δείχνει ότι δεν μπορεί να υπάρξει αλγόριθμος για να προσδιοριστεί αν δύο εκφράσεις που αναπαριστούν αριθμούς είναι σημασιολογικά ίσες, αν στις εκφράσεις επιτρέπονται εκθετικοί και λογάριθμοι. Ως αποτέλεσμα, η (σημασιολογική) ισότητα μπορεί να ελεγχθεί μόνο σε ορισμένες κατηγορίες εκφράσεων, όπως τα πολυώνυμα και τα ρητά κλάσματα.

Στην υπολογιστική άλγεβρα, η "κανονική μορφή" και η " φυσιολογική μορφή" δεν είναι συνώνυμες^[13]. Μια κανονική μορφή είναι τέτοια ώστε δύο εκφράσεις σε κανονική μορφή να είναι σημασιολογικά ίσες αν και μόνο αν είναι συντακτικά ίσες, ενώ μια φυσιολογική μορφή είναι τέτοια ώστε μια έκφραση σε φυσιολογική μορφή να είναι σημασιολογικά μηδενική μόνο αν είναι συντακτικά μηδενική. Με άλλα λόγια, το μηδέν έχει μια μοναδική αναπαράσταση ως έκφραση σε κανονική μορφή.

Οι κανονικές μορφές προτιμώνται συνήθως στην υπολογιστική άλγεβρα για διάφορους λόγους. Πρώτον, οι κανονικές μορφές μπορεί να είναι πιο δαπανηρές στον υπολογισμό από τις κανονικές μορφές. Παραδείγματος χάριν, για να θέσει κανείς ένα πολυώνυμο σε κανονική μορφή, πρέπει να αναπτύξει κάθε γινόμενο μέσω της επιμεριστικής ιδιότητας, ενώ αυτό δεν είναι απαραίτητο με μια κανονική μορφή (βλ. παρακάτω). Δεύτερον, μπορεί να συμβαίνει, όπως για εκφράσεις που περιλαμβάνουν ρίζες, ότι μια κανονική μορφή, αν υπάρχει, εξαρτάται από κάποιες αυθαίρετες επιλογές και ότι αυτές οι επιλογές μπορεί να είναι διαφορετικές για δύο εκφράσεις που έχουν υπολογιστεί ανεξάρτητα. Αυτό μπορεί να καταστήσει ανέφικτη τη χρήση μιας κανονικής μορφής.

Ιστορία[Επεξεργασία | επεξεργασία κώδικα]

Υπολογιστική άλγεβρα με γνώμονα τον άνθρωπο[Επεξεργασία | επεξεργασία κώδικα]

Τα πρώιμα υπολογιστικά συστήματα, όπως ο ENIAC στο Πανεπιστήμιο της Πενσυλβάνια, εξαρτώνταν από υπολογιστές ή προγραμματιστές για τον επαναπρογραμματισμό τους μεταξύ των υπολογισμών, τον χειρισμό των πολλών φυσικών μονάδων (ή πάνελ) και την τροφοδοσία του αναγνώστη καρτών IBM^[14]. Γυναίκες μαθηματικοί ανέλαβαν το μεγαλύτερο μέρος του προγραμματισμού των υπολογιστών του ENIAC με ανθρώπινη καθοδήγηση: οι Τζιν Τζένινγκς, Μάρλιν Γουέσκοφ, Ρουθ Τάιτελμπαουμ, Μπέτι Χόλμπερτον, Φράνσις Σπενς και Κέι ΜακΝάλτι ηγήθηκαν αυτών των προσπαθειών^[15].

Θεμέλια και πρώτες εφαρμογές[Επεξεργασία | επεξεργασία κώδικα]

Το 1960, ο Τζον Μακάρθι διερεύνησε μια επέκταση των πρωτόγονων αναδρομικών συναρτήσεων για τον υπολογισμό συμβολικών εκφράσεων μέσω της γλώσσας προγραμματισμού Lisp, ενώ εργαζόταν στο Τεχνολογικό Ινστιτούτο της Μασαχουσέτης.^[16] Αν και η σειρά του με θέμα "Αναδρομικές συναρτήσεις συμβολικών εκφράσεων και ο υπολογισμός τους από μηχανή" παρέμεινε ανολοκλήρωτη,^[17] ο McCarthy και οι συνεισφορές του στον προγραμματισμό τεχνητής νοημοσύνης και στην άλγεβρα υπολογιστών μέσω της Lisp βοήθησαν στη δημιουργία του Project MAC στο Ινστιτούτο Τεχνολογίας της Μασαχουσέτης και του οργανισμού που αργότερα έγινε το Εργαστήριο Τεχνητής Νοημοσύνης του Στάνφορντ (Stanford AI Laboratory - SAIL) στο Πανεπιστήμιο του Στάνφορντ, ο ανταγωνισμός του οποίου διευκόλυνε τη σημαντική ανάπτυξη της άλγεβρας υπολογιστών καθ' όλη τη διάρκεια του τέλους του 20ού αιώνα.

Οι πρώτες προσπάθειες συμβολικού υπολογισμού, στις δεκαετίες του 1960 και 1970, αντιμετώπισαν προκλήσεις γύρω από την αναποτελεσματικότητα των από καιρό γνωστών αλγορίθμων όταν μεταφέρθηκαν σε συστήματα υπολογιστικής άλγεβρας^[18]. Οι προκάτοχοι του Project MAC, όπως το ALTRAN, προσπάθησαν να ξεπεράσουν τους αλγοριθμικούς περιορισμούς μέσω της εξέλιξης του υλικού και των διερμηνέων, ενώ οι μεταγενέστερες προσπάθειες στράφηκαν προς τη βελτιστοποίηση του λογισμικού^[19].

Ιστορικά προβλήματα[Επεξεργασία | επεξεργασία κώδικα]

Ένα μεγάλο μέρος της εργασίας των ερευνητών του τομέα συνίστατο στην επανεξέταση της κλασικής άλγεβρας για την αύξηση της αποτελεσματικότητάς της, ενώ παράλληλα αναπτύσσονταν αποτελεσματικοί αλγόριθμοι για χρήση στην υπολογιστική άλγεβρα. Ένα παράδειγμα αυτού του είδους εργασίας είναι ο υπολογισμός των πολυωνυμικών μεγαλύτερων κοινών διαιρετών, μια εργασία που απαιτείται για την απλοποίηση κλασμάτων και αποτελεί βασικό συστατικό της υπολογιστικής άλγεβρας. Οι κλασικοί αλγόριθμοι για αυτόν τον υπολογισμό, όπως ο αλγόριθμος του Ευκλείδη, παρείχαν αναποτελεσματικότητα σε άπειρα πεδία- οι αλγόριθμοι από τη γραμμική άλγεβρα αντιμετώπιζαν παρόμοιους αγώνες.^[20] Έτσι, οι ερευνητές στράφηκαν στην ανακάλυψη μεθόδων αναγωγής πολυωνύμων (όπως αυτά που βρίσκονται πάνω σε έναν δακτύλιο ακεραίων ή σε ένα μοναδικό πεδίο παραγοντοποίησης) σε μια παραλλαγή που μπορεί να υπολογιστεί αποτελεσματικά μέσω ενός ευκλείδειου αλγορίθμου.

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

Για αναλυτικό ορισμό του θέματος:

Buchberger, Bruno (1985). «Symbolic Computation (An Editorial)». Journal of Symbolic Computation 1 (1): 1–6. doi:10.1016/S0747-7171(85)80025-0. http://www3.risc.jku.at/publications/download/risc_2749/1985-03-00-C.pdf.

Για εγχειρίδια αφιερωμένα στο θέμα:

Davenport, James H.· Siret, Yvon· Tournier, Èvelyne (1988). Computer Algebra: Systems and Algorithms for Algebraic Computation. Translated from the French by A. Davenport and J. H. Davenport. Academic Press. ISBN 978-0-12-204230-0.
von zur Gathen, Joachim· Gerhard, Jürgen (2003). Modern computer algebra (2nd έκδοση). Cambridge University Press. ISBN 0-521-82646-2.
Geddes, K. O.· Czapor, S. R.· Labahn, G. (1992). Algorithms for Computer Algebra. Bibcode:1992afca.book.....G. doi:10.1007/b102438. ISBN 978-0-7923-9259-0.
Buchberger, Bruno· Collins, George Edwin· Loos, Rüdiger· Albrecht, Rudolf, επιμ. (1983). Computer Algebra: Symbolic and Algebraic Computation. Computing Supplementa. 4. doi:10.1007/978-3-7091-7551-4. ISBN 978-3-211-81776-6.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ «ACM Association in computer algebra».
↑ Watt, Stephen M. (2006). «Making Computer Algebra More Symbolic (Invited)». Transgressive Computing 2006: A conference in honor of Jean Della Dora, (TC 2006), pp. 43–49. ISBN 9788468983813. OCLC 496720771. http://www.csd.uwo.ca/~watt/pub/reprints/2006-tc-sympoly.pdf.
↑ SIGSAM official site
↑ «SIGSAM list of conferences». Αρχειοθετήθηκε από το πρωτότυπο στις 8 Αυγούστου 2013. Ανακτήθηκε στις 15 Νοεμβρίου 2012.
↑ Cohen, Joel S. (2003). Computer Algebra and Symbolic Computation: Mathematical Methods. AK Peters. σελ. 14. ISBN 978-1-56881-159-8.
↑ SIGSAM list of journals
↑ Richard Liska Expression swell, from "Peculiarities of programming in computer algebra systems"
↑ "The Mathematica Kernel: Issues in the Design and Implementation". October 2006. Retrieved 2023-11-29.
↑ "The GNU Multiple Precision (GMP) Library". Maplesoft. Retrieved 2023-11-29.
↑ Cassidy, Kevin G. (Δεκ. 1985). The Feasibility of Automatic Storage Reclamation with Concurrent Program Execution in a LISP Environment (PDF) (Master's thesis). Naval Postgraduate School, Monterey/CA. σελ. 15. ADA165184.
↑ Macsyma Mathematics and System Reference Manual (PDF). Macsyma. 1996. σελ. 419.
↑ Buchberger, Bruno· Loos, Rüdiger (1983). «Algebraic simplification» (PDF). Στο: Buchberger, Bruno· Collins, George Edwin· Loos, Rüdiger· Albrecht, Rudolf. Computer Algebra: Symbolic and Algebraic Computation. Computing Supplementa. 4. σελίδες 11–43. doi:10.1007/978-3-7091-7551-4_2. ISBN 978-3-211-81776-6.
↑ Davenport, J. H.· Siret, Y.· Tournier, É. (1988). Computer Algebra: Systems and Algorithms for Algebraic Computation. Academic. ISBN 0-12-204230-1. OCLC 802584470.
↑ "ENIAC in Action: What it Was and How it Worked". ENIAC: Celebrating Penn Engineering History. University of Pennsylvania. Retrieved December 3, 2023.
↑ Light, Jennifer S. (1999). «When Computers Were Women» (στα αγγλικά). Technology and Culture 40 (3): 455–483. doi:10.1353/tech.1999.0128. ISSN 1097-3729. https://muse.jhu.edu/article/33396.
↑ McCarthy, John (1960-04-01). «Recursive functions of symbolic expressions and their computation by machine, Part I». Communications of the ACM 3 (4): 184–195. doi:10.1145/367177.367199. ISSN 0001-0782. https://dl.acm.org/doi/10.1145/367177.367199.
↑ Wexelblat, Richard L. (1981). History of programming languages. ACM monograph series. History of programming languages conference, Association for computing machinery. New York London Toronto: Academic press. ISBN 978-0-12-745040-7.
↑ «Symbolic Computation (An Editorial)». Journal of Symbolic Computation 1 (1): 1–6. 1985-03-01. doi:10.1016/S0747-7171(85)80025-0. ISSN 0747-7171. https://www.sciencedirect.com/science/article/pii/S0747717185800250.
↑ Feldman, Stuart I. (1975-11-01). «A brief description of Altran». ACM SIGSAM Bulletin 9 (4): 12–20. doi:10.1145/1088322.1088325. ISSN 0163-5824. https://dl.acm.org/doi/10.1145/1088322.1088325.
↑ Kaltofen, E. (1983), Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger και άλλοι, επιμ., Factorization of Polynomials, 4, Vienna: Springer Vienna, σελ. 95–113, doi:10.1007/978-3-7091-7551-4_8, ISBN 978-3-211-81776-6, http://link.springer.com/10.1007/978-3-7091-7551-4_8, ανακτήθηκε στις 2023-11-29

[1] «ACM Association in computer algebra».

[2] Watt, Stephen M. (2006). «Making Computer Algebra More Symbolic (Invited)». Transgressive Computing 2006: A conference in honor of Jean Della Dora, (TC 2006), pp. 43–49. ISBN 9788468983813. OCLC 496720771. http://www.csd.uwo.ca/~watt/pub/reprints/2006-tc-sympoly.pdf.

[3] SIGSAM official site

[4] «SIGSAM list of conferences». Αρχειοθετήθηκε από το πρωτότυπο στις 8 Αυγούστου 2013. Ανακτήθηκε στις 15 Νοεμβρίου 2012.

[5] Cohen, Joel S. (2003). Computer Algebra and Symbolic Computation: Mathematical Methods. AK Peters. σελ. 14. ISBN 978-1-56881-159-8.

[6] SIGSAM list of journals

[7] Richard Liska Expression swell, from "Peculiarities of programming in computer algebra systems"

[8] "The Mathematica Kernel: Issues in the Design and Implementation". October 2006. Retrieved 2023-11-29.

[9] "The GNU Multiple Precision (GMP) Library". Maplesoft. Retrieved 2023-11-29.

[10] Cassidy, Kevin G. (Δεκ. 1985). The Feasibility of Automatic Storage Reclamation with Concurrent Program Execution in a LISP Environment (PDF) (Master's thesis). Naval Postgraduate School, Monterey/CA. σελ. 15. ADA165184.

[11] Macsyma Mathematics and System Reference Manual (PDF). Macsyma. 1996. σελ. 419.

[12] Buchberger, Bruno· Loos, Rüdiger (1983). «Algebraic simplification» (PDF). Στο: Buchberger, Bruno· Collins, George Edwin· Loos, Rüdiger· Albrecht, Rudolf. Computer Algebra: Symbolic and Algebraic Computation. Computing Supplementa. 4. σελίδες 11–43. doi:10.1007/978-3-7091-7551-4_2. ISBN 978-3-211-81776-6.

[13] Davenport, J. H.· Siret, Y.· Tournier, É. (1988). Computer Algebra: Systems and Algorithms for Algebraic Computation. Academic. ISBN 0-12-204230-1. OCLC 802584470.

[14] "ENIAC in Action: What it Was and How it Worked". ENIAC: Celebrating Penn Engineering History. University of Pennsylvania. Retrieved December 3, 2023.

[15] Light, Jennifer S. (1999). «When Computers Were Women» (στα αγγλικά). Technology and Culture 40 (3): 455–483. doi:10.1353/tech.1999.0128. ISSN 1097-3729. https://muse.jhu.edu/article/33396.

[16] McCarthy, John (1960-04-01). «Recursive functions of symbolic expressions and their computation by machine, Part I». Communications of the ACM 3 (4): 184–195. doi:10.1145/367177.367199. ISSN 0001-0782. https://dl.acm.org/doi/10.1145/367177.367199.

[17] Wexelblat, Richard L. (1981). History of programming languages. ACM monograph series. History of programming languages conference, Association for computing machinery. New York London Toronto: Academic press. ISBN 978-0-12-745040-7.

[18] «Symbolic Computation (An Editorial)». Journal of Symbolic Computation 1 (1): 1–6. 1985-03-01. doi:10.1016/S0747-7171(85)80025-0. ISSN 0747-7171. https://www.sciencedirect.com/science/article/pii/S0747717185800250.

[19] Feldman, Stuart I. (1975-11-01). «A brief description of Altran». ACM SIGSAM Bulletin 9 (4): 12–20. doi:10.1145/1088322.1088325. ISSN 0163-5824. https://dl.acm.org/doi/10.1145/1088322.1088325.

[20] Kaltofen, E. (1983), Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger και άλλοι, επιμ., Factorization of Polynomials, 4, Vienna: Springer Vienna, σελ. 95–113, doi:10.1007/978-3-7091-7551-4_8, ISBN 978-3-211-81776-6, http://link.springer.com/10.1007/978-3-7091-7551-4_8, ανακτήθηκε στις 2023-11-29

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]