Ανοίγουμε μια οθόνη εντολών (terminal) και δημιουργούμε έναν κατάλογο (directory) στο home
directory του λογαριασμού μας ή οπουδήποτε αλλού, δίνοντάς του ένα όνομα της αρεσκείας μας π.χ. sagemath
.
mkdir sagemath/
Μπαίνουμε στο directory που δημιουργήσαμε
cd sagemath/
και τρέχουμε
/opt/sage-7.4/./sage -n jupyter
Η εντολή αυτή μας ανοίγει μια web σελίδα στον mozilla/chrome, ανάλογα ποιό πρόγραμμα χρησιμοποιoύμε για web-browser. Η σελίδα που ανοίγει το Sage είναι ένα περιβάλλον εργασίας που ονομάζεται jupyter notebook. Πάνω-δεξιά υπάρχει ένα κουμπί επιλογών
New
. Σ' αυτό επιλέγουμε SageMath 7.4
/opt/sage-7.4/./sage -n jupyter
Μπορείτε να εγκαταστήσετε το Sage
στον προσωπικό σας υπολογιστή (Windows/Mac/Linux) ακολουθώντας τις οδηγίες εδώ.
Μπορούμε να χρησιμοποιήσουμε το Sage [εδώ](https://cloud.sagemath.com/), δίχως καμία εγκατάσταση του λογισμικού στον υπολογιστή μας, αρκεί να έχουμε σύνδεση στο διαδίκτυο. Όμως, ο server που χρησιμοποιείται γι' αυτό τον σκοπό ορισμένες φορές δεν είναι διαθέσιμος λόγω υπερφόρτωσης.
Όλα τα παραπάνω αφορούν πως τρέχουμε το Sage σε περιβάλλον jupyter notebook. Εναλλακτικά μπορούμε να τρέξουμε από μια οθόνη τερματικού στο εργαστήριο
/opt/sage-7.4/./sage --notebook
το οποίο ανοίγει τον πυρήνα του Sage σε ένα άλλο γραφικό περιβάλλον. Ακόμη, υπάρχει η δυνατότητα να τρέξουμε το Sage και σε τερματικό με γραμμές εντολών, τρέχοντας
/opt/sage-7.4/./sage
ή ακόμα και μέσα από τον επεξεργαστή κειμένου emacs
εγκαθιστώντας το κατάλληλο περιβάλλον (shell).
Προτείνεται, χωρίς να είναι απαραίτητο, να χρησιμοποιήσουμε το Sage στο γραφικό περιβάλλον jupyter notebook επειδή: α) έχετε ήδη εξοικειωθεί με το τελευταίο σε προηγούμενα μαθήματα που διδαχτήκατε (π.χ. Python) και β) το jupyter notebook προσφέρει την δυνατότητα να εναλλάσσουμε γρήγορα από κελί κώδικα (code) SageMath σε κελί markdown, o οποίος προσφέρει εύκολη διαμόρφωση απλού και σύνθετου κειμένου καθώς και εισαγωγή σχημάτων. Ακόμα περισσότερο προσφέρει διαμόρφωση μαθηματικού κειμένου, μέσω του $\rm\LaTeX$, και να σώζουμε τα notebooks σε διαφορετικές μορφές (html, pdf κα). Οι σημειώσεις και τα σχήματα σε ένα notebook έχουν καθοριστική σημασία τόσο στην περιγραφή όσο και στην κατανόηση των μαθηματικών προβλημάτων που θα διαπραγματευτούμε κατά την διάρκεια του μαθήματος.
Επιπλέον, η χρήση κειμένου εμβόλιμα στις εντολές κώδικα του Sage βοηθά να κατανοήσουμε καλύτερα στο τι ακριβώς κάνει η κάθε μία εντολή που χρησιμοποιούμε.
Μπορείτε να περιηγηθείτε στα προγράμματα που προαναφέραμε στους παρακάτω συνδέσμους:
Στις ιστοσελίδες αυτές θα βρείτε επίσης πολλές εύχρηστες κάρτες εγχειριδίων (quick reference cards) τις οποίες μπορείτε να τυπώσετε. Για παράδειγμα, σε κάποια κάρτα του jupyter notebook αναφέρεται ότι πληκτρολογώντας Ctrl+Shift+P
μπορούμε να δούμε μια σειρά από συντομεύσεις για εντολές πληκτρολογίου που μας επιτρέπουν να διαχειριστούμε εύκολα τα κελιά (cells) εντολών, τον πυρήνα (kernel) που τρέχει το Sage, και γενικότερα το notebook που δουλεύουμε.
Οι σημειώσεις αυτές γράφονται στο περιβάλλον του jupyter notebook, χρησιμοποιώντας συνδυασμό markdown και html τα οποία είναι απόλυτα συμβατά μεταξύ τους, και η όποια επιπλέον επεξεργασία του κειμένου χρειάσθηκε έγινε με το $\rm \LaTeX$. Το σύνολο των προγραμμάτων που χρησιμοποιήθηκαν είναι ελεύθερα λογισμικά ανοιχτού κώδικα για το λειτουργικό σύστημα GNU/Linux με πυρήνα 3.16.7.
Το Sage είναι ένα σύνολο λογισμικών που εκτελούν συμβολικούς υπολογισμούς. Συστήματα που εκτελούν συμβολικούς υπολογισμούς είναι ικανά να αντιμετωπίζουν τα μαθηματικά αντικείμενα συμβολικά. Αυτό σημαίνει ότι τα μαθηματικά αντικείμενα παριστάνονται ακριβώς, και όχι προσεγγιστικά, και συνεπώς διάφορες μαθηματικές εκφράσεις στις οποίες εμφανίζονται μεταβλητές που δεν έχουν συγκεκριμένες τιμές, αφήνονται σε συμβολική μορφή.
Για παράδειγμα, αν ζητήσουμε να κατασκευασθεί ένα αριθμητικό πρόγραμμα για να "λύσει την εξίσωση sin(x)=0
, ως προς x", η πιο πιθανή απάντηση που θα παίρναμε θα ήταν μια ποσότητα με ακρίβεια 32-bit, την οποία το πρόγραμμα θα τύπωνε σαν 0.0
, και όχι μια απάντηση της μορφής "{ n π | integer(n)
} ". Από μαθηματική σκοπιά, ένα λογισμικό που έχει την δυνατότητα να μας παρέχει την τελευταία συμβολική, παραμετρική μορφή, υπερέχει από ένα αντίστοιχο που μας δίνει μια και μόνη αριθμητική τιμή. Μια και μόνο αριθμητική τιμή μπορεί να είναι χρήσιμη για έναν συγκεκριμένο σκοπό, όμως όσο απλή κι αν είναι, δεν παύει να είναι ένας συμβιβασμός.
Αν επιπλέον το πρόβλημα που θέλουμε να επιλύσουμε απαιτεί υπολογισμούς που αφορούν σύνολα, συναρτήσεις, μαθηματικές εκφράσεις (πολυωνυμικές, ρητές, αλγεβρικές κλπ), γεωμετρικά χωρία, παραγωγίσεις, θεωρήματα, αποδείξεις κτλ, τότε είναι εύλογο να υποθέσει κανείς ότι ένα υπολογιστικό σύστημα που είναι ικανό να εκτελεί συμβολικούς υπολογισμούς, να έχει κάποια χρησιμότητα.
Το Sage είναι ένα σύνολο λογισμικών τα οποία είνα ικανά να εκτελούν τόσο συμβολικούς υπολογισμούς, όσο και αριθμητικούς, και αναφέρεται από τα αρχικά Software for Algebra, Geometry and Experimentation.
Ορισμένα κύρια χαρακτηριστικά του Sage είναι:
Τρέχουμε τις εντολές του Sage σε jupyter notebook σε κελιά (cells) κώδικα (code
). Οι εντολές εκτελούνται πατώντας:
Ctrl-Enter
για να εκτελέσουμε το κελί που βρισκόμαστε, Alt-Enter
για να εκτελέσουμε το κελί που βρισκόμαστε και να εισαγάγουμε ένα νέο κελί αμέσως μετά,Shift-Enter
για να εκτελέσουμε το κελί που βρισκόμαστε και να επιλέξουμε το κελί αμέσως μετά. Enter
, ή αριστερό click στο ποντίκι.
Στο jupyter notebook πληκτρολογούμε Ctrl-Shift-P
για να δούμε όλες τις διαθέσιμες συντομεύσεις πληκτρολογίου και διάφορες επιλογές για να επεξεργαζόμαστε τα cells καθώς και τον πυρήνα. Ορισμένες από αυτές τις επιλογές είναι διαθέσιμες και στο menu επιλογών του jupyter στο πάνω μέρος του notebook.
print pi
print sin(pi)
print(pi)
print type(_)
print type(pi)
graf = plot(exp(-x^2)*sin(16*x),(x,-pi,pi),figsize=4); show(graf)
Το Sage είναι κατά κύριο λόγο είναι ένα σύστημα που εκτελεί συμβολικούς υπολογισμούς. Για αριθμητικούς υπολογισμούς δεν περιορίζεται στην αριθμητική ακρίβεια του επεξεργαστή ενός υπολογιστή. Για παράδειγμα, για να δούμε τον $\pi$ με 20 δεκαδικά ψηφία τρέχουμε
pi20 = pi.n(digits=20); print pi20
print sin(pi20)
print type(pi20)
Παρατηρούμε ότι σε αντίθεση με την τιμή του ημιτόνου στο $\pi$, η τιμή sin(pi20)
δεν είναι πλέον μηδέν.
from sage.misc.citation import get_systems
print get_systems('Rational(0.75)')
print get_systems('RealField(10)(pi)')
import sage.misc.citation
help(sage.misc.citation)
print sage.misc.citation.systems.keys()
Αν θέλουμε να εκτελέσουμε υπολογισμούς με αυθαίρετη ακρίβεια, τότε πρέπει να αυξήσουμε την ακρίβεια στο σώμα των πραγματικών για να έχουμε σωστή στρογγυλοποίηση
print 37^37
Με ένα underscore
παίρνουμε το αποτέλεσμα από τον αμέσως προηγούμενο υπολογισμό. Με δυο underscore
παίρνουμε το αποτέλεσμα του προτελευταίου υπολογισμού και με τρία, πριν τρεις υπολογισμούς. Περαιτέρω χρήση τους δεν είναι δυνατή.
Ας θεωρήσουμε τώρα ότι θέλουμε να υπολογίσουμε την διαφορά ανάμεσα στην πραγματική τιμή του $\pi$ και την αριθμητική του τιμή με μια ακρίβεια 30 ψηφίων. Ο πιο γρήγορος τρόπος για να βρούμε την τελευταία είναι μέσω της συνάρτησης
numerical_approx
.
print numerical_approx(pi,digits=30)
Όμως συχνά θέλουμε οι υπολογισμοί μας να εκτελούνται με καθορισμένη ακρίβεια, για παράδειγμα 30 δεκαδικών ψηφίων. Τότε χρησιμοποιούμε την συνάρτηση RealField
με δεδομένη ακρίβεια, για παράδειγμα για τον υπολογισμό του $\pi$ με προσέγγιση 30 ψηφίων δίνουμε
R = RealField(30*log(10,2))
pi30 = R(pi) ; print pi30
Με log(10,2)
υπολογίζουμε τον λογάριθμο του 10 με βάση το 2, γιατί το όρισμα στην RealField
εκφράζεται σε bits
, και για κάθε δεκαδικό ψηφίο χρειαζόμαστε $\log_2 10\approx 3.32$ bits. Μετά την δημιουργία του R
, μετατρέπουμε το σύμβολο για την μαθηματική σταθερή $\pi$ σε μια προσέγγιση 30 ψηφίων, την οποία καταχωρούμε στην τιμή pi30
. Για να ελέγξουμε την διαφορά του $\pi$ και του pi30
με την δεδομένη ακρίβεια των 30 ψηφίων δίνουμε
print R(pi-pi30)
print RealField(40*log(10,2))(pi-pi30)
οπότε η τιμή pi30
έχει
την επιθυμητή ακρίβεια 30 δεκαδικών ψηφίων. Για να πάρουμε βοήθεια για κάποια συνάρτηση/εντολή του Sage εκτελούμε για παράδειγμα
help(RealField)
ή εναλλακτικά
RealField?
Η τελευταία εντολή μας ανοίγει αυτόματα μια νέα υποσελίδα στο κάτω μέρος της web-σελίδας που δουλεύουμε, στην οποία εμφανίζεται το κείμενο με την βοήθεια.
Ένας εναλλακτικός τρόπος αριθμητικής προσέγγισης οποιουδέποτε πραγματικού αριθμού είναι με την χρήση απλών συνεχών κλασμάτων. Ένα απλό συνεχές κλάσμα ορίζεται από μια λίστα $[b_0;b_1,b_2,b_3,\ldots]$, όπου $b_i$, $i=1,2\ldots$ είναι θετικοί ακέραιοι και μόνο ο $b_0$ μπορεί να είναι μή-θετικός ακέραιος. Κάθε πραγματικός αριθμός $x$ (ρητός, άρρητος ή υπερβατικός) έχει την αναπαράσταση $$x = b_0 + \frac{1}{ b_1 + \frac{1}{ b_2 + \frac{1}{ b_3 + \cdots}} } \,. $$ Οι ρητοί αριθμοί που προκύπτουν κρατώντας μόνο ένα πεπερασμένο πλήθος όρων στο συνεχές κλάσμα λέγονται συγκλίνοντες. Για παράδειγμα
x = sqrt(2)
c = continued_fraction(x); print c
Δηλαδή $$\sqrt{2} = 1 + \frac{1}{ 2 + \frac{1}{ 2 + \frac{1}{ 2 + \cdots}} } \,. $$ και οι συγκλίνοντες είναι $$ 1 \,,\quad \frac{3}{2} = 1+ \frac{1}{2}\,,\quad \frac{7}{5} = 1+ \frac{1}{2+\frac{1}{2}} \,,\cdots$$ Στο Sage εκτελούμε
print c.convergents()
print c.convergent(15)
print c.numerator(153)
print c.denominator(153)
όπου οι συναρτήσεις numerator(n)
, και denominator(n)
μας δίνουν τον αριθμητή και τον παρονομαστή του $n$-στού συγκλίνοντα στην αναπαράσταση του πραγματικού $x$ με απλά συνεχή κλάσματα.
Στο Sage το σώμα των μιγαδικών αριθμών είναι γνωστό ως ComplexField()
, όπου στο όρισμα μπορούμε να θέσουμε (σε bits) την ακρίβεια που θέλουμε να χρησιμοποιήσουμε στους υπολογισμούς. Όμως, δεν πρέπει να μας διαφεύγει ότι το βασικό χαρακτηριστικό του Sage είναι ότι πρόκειται για ένα λογισμικό που εκτελεί συμβολικούς υπολογισμούς. Στο Sage η φανταστική μονάδα δηλώνεται με I
.
C = ComplexField(100); print C
print sqrt(-1)
print I^2
a = (-1+I)^2; b = (1 - I)^2;
print a
print b
Το Sage γνωρίζει να λύνει πολυωνυμικές εξισώσεις με συντελεστές στους μιγαδικούς αριθμούς. Για παράδειγμα θα λύσουμε την εξίσωση
$$ z^3=i$$
Ορίζουμε με την συνάρτηση var
μια (συμβολική έκφραση) μεταβλητή $z$ και με την εντολή solve
λύνουμε την παραπάνω εξίσωση. Χρησιμοποιούμε το προαιρετικό όρισμα solution_dict=True
για να πούμε στην συνάρτηση solve
να μας επιστρέψει τις λύσεις στην μορφή μιας λίστας Python
με ανάλογο λεξικό.
var("z")
rizes=solve(z^3==I,z,solution_dict=True); print rizes; print type(rizes)
Στην συνέχεια ρησιμοποιούμε ένα βρόχο (loop) και καταχωρούμε τις λύσεις σε μια νέα λίστα που την ονομάζουμε lyseis
. Με τον ίδιο τρόπο δημιουργούμε τις λίστες metra
, gwnies
, που περιέχουν τα μέτρα και τις γωνίες των λύσεων, αντίστοιχα. Στο Sage το πραγματικό και το φανταστικό μέρος ενός μιγαδικού αριθμού δίνονται με τις συναρτήσεις
real_part()
και imag_part()
, αντίστοιχα.
Οι εντολές abs()
και arg()
, μας δίνουν το μέτρο και το όρισμα (argument) ενός μιγαδικού αριθμού, αντίστοιχα.
lyseis=[];shmeia=[];metra=[];gwnies=[];
for i in [0..(len(rizes)-1)]:
lyseis.append( real_part( rizes[i][z] ) + I*imag_part( rizes[i][z]) )
metra.append( abs( rizes[i][z] ).simplify() )
gwnies.append( arg( rizes[i][z] ).simplify() )
print lyseis
print metra
print gwnies
Παρατηρούμε ότι και οι τρείς λύσεις έχουν μέτρο μονάδα, συνεπώς βρίσκονται πάνω στον μοναδιαίο κύκλο, και σε γωνίες
$$ \frac{5\,\pi}{6} \,,\quad -\frac{\pi}{2} \,,\quad \frac{\pi}{6}\,. $$
αντίστοιχα.
Τέλος, απεικονίζουμε γραφικά τα αποτελέσματά μας στο μιγαδικό επίπεδο. Οι αντίστοιχες εντολές για γραφικές παραστάσεις σε δυο και τρεις διαστάσεις θα μας απασχολήσουν εκτενέστερα σε άλλη ενότητα. Προς το παρόν δώστε μεγαλύτερη έμφαση στο γεγονός ότι το Sage μας πληροφορεί ότι οι λύσεις της εξίσωσης $$z^3=i $$ είναι το σύνολο των μιγαδικών αριθμών
$$ \left\lbrace \frac{\sqrt{3}}{2} + \frac{i}{2} \,, \quad -\frac{\sqrt{3}}{2} + \frac{i}{2} \,,\quad -i\right\rbrace\,. $$var("x y")
kyklos=implicit_plot(x^2+y^2==1,(x,-1,1),(y,-1,1))
pp=sum([point( ( (real_part( rizes[i][z]) , imag_part( rizes[i][z])) ),
color=rainbow(3)[i] , size=50) for i in [0..(len(rizes)-1)]])
show(kyklos+pp,figsize=4)
Ο πραγματικός αριθμός $\sqrt{2}$ είναι ένας αλγεβρικός αριθμός. Το ελάχιστο πολυώνυμο που έχει ρίζα έναν αλγεβρικό αριθμό, λέγεται το ελάχιστο πολυώνυμο του αριθμού. Για παράδειγμα, η εντολή
print sqrt(2).minpoly()
μας επιστρέφει ότι το ελάχιστο πολυώνυμο του $\sqrt{2}$ είναι το $x^2-2$. Το αποτέλεσμα της παραγοντοποίησης ενός πολυωνύμου εξαρτάται από το σώμα των αριθμών που είναι ορισμένο.
print factor(x^2-1)
print factor(x^2-2)
Το πολυώνυμο $x^2-1$ παραγοντοποιείται σε $(x+1)(x-1)$, ενώ το πολυώνυμο $x^2-2$ δεν παραγοντοποιείται πάνω στο προεπιλεγμένο σώμα, που είναι το σύνολο $\mathbb{Q}$ των ρητών. Αν ένα πολυώνυμο δεν παραγοντοποιείται σε ένα συγκεκριμένο σώμα λέγεται ανάγωγο στο αντίστοιχο σώμα. Μπορούμε να ορίσουμε ένα σώμα $K$ στο οποίο το $c$ είναι η τετραγωνική ρίζα του $2$, και να υπολογίζουμε και να απλοποιούμε εκφράσεις στο K, έχοντας ενσωματώσει την πληροφορία ότι το ελάχιστο πολυώνυμο του $\sqrt{2}$ είναι το $x^2-2$.
K.<c> = NumberField(x^2-2); print K
print c^2
print c^3
Αν θεωρήσουμε τώρα το δακτύλιο των πολυωνύμων με συντελεστές στο σώμα $K$, τότε το πολυώνυμο $x^2-2$ παραγοντοποιείται στο $K$. Πραγματικά
R.<x> = PolynomialRing(K)
p = x^2 - 2
print factor(p)
Στην παράγραφο αυτή αναφέρονται κάποιες έννοιες στις οποίες ο αναγνώστης ίσως να μην είναι τόσο εξοικειωμένος. Μπορείτε να συνεχίσετε στην επόμενη παράγραφο. Όμως ενθαρρύνω τον αναγνώστη να "βουτήξει" δίχως κανένα ενδοιασμό, όπως ακριβώς τον ενθαρρύνω να κάνει το ίδιο και με το Sage. Απλά, ας βουτήξουμε!!!
Στην Θεωρία Κωδικοποίησης και στην Κρυπτογραφία συχνά δουλεύουμε με ένα πεπερασμένο σώμα. Ένα πεπερασμένο σώμα, ή σώμα Galois, δηλώνεται με $\mathbb{F}_{p^n}$, και έχει ένα πεπερασμένο πλήθος στοιχείων. Αποδεικνύεται ότι (μέχρι ισομορφισμού) υπάρχει ένα και μόνο ένα πεπερασμένο σώμα που περιέχει $p^n$ στοιχεία, για κάθε δύναμη πρώτου $p$. Ο πρώτος $p$ αναφέρεται ως η χαρακτηριστική του πεπερασμένου σώματος. Τα στοιχεία του $\mathbb{F}_{p^n}$ μπορούν να αναπαρασταθούν ως πολυώνυμα $g(x)$ βαθμού $d$, αυστηρά μικρότερου από $n$ ($d\leq n-1$), με συντελεστές στο ελάχιστο υποσώμα $\mathbb{F}_{p}=\mathbb{Z}_p$.
Για να κατασκευάσουμε ένα πεπερασμένο σώμα $\mathbb{F}_{p^n}$, θεωρούμε ένα ανάγωγο πολυώνυμο $f(x)$, πάνω στο ελάχιστο υποσώμα $\mathbb{F}_{p}$, και θεωρούμε μια πρωταρχική ρίζα $a$ του $f(x)$, δηλαδή $f(a)=0$, και $a^{p^n-1}=1$. Αποδεικνύεται ότι η πολλαπλασιαστική ομάδα του $\mathbb{F}_{p^n}$, είναι κυκλική (άρα και αντιμεταθετική), οπότε το σώμα έχει την αναπαράσταση $$ $$ $$\mathbb{F}_{p^n} = \lbrace\, 0,\,a,\,a^2,\,\ldots, a^{p^n-1} = 1 \rbrace\,,$$ $$ $$ και τότε λέμε ότι έχουμε κατασκευάσει το $\mathbb{F}_{p^n}$ ως την αλγεβρική επέκταση $\mathbb{F}_{p}[x]\,/\,f(x)$ του ελάχιστου υποσώματος $\mathbb{F}_{p}$.
Για παράδειγμα, θεωρούμε $a\in \mathbb{F}_{3^2}$, πρωταρχική ρίζα του ανάγωγου πολυωνύνου $f(x)=x^2+x+2$, με συντελεστές στο $\mathbb{Z}_3$. Αφού $a$ ρίζα του $f(x)$, αυτό σημαίνει ότι $f(a)=0$, και άρα $a^2 = 2\,a +1$ ($\mod 3$). Τότε έχουμε $$ $$ $$ a^8 = (a^4)^2 = (a^2\,a^2)^2 = (2a+1)^2 (2a+1)^2 = (4 a^2+4a+1)(4a^2+4a+1) = $$ $$ $$ $$\quad=(2a+1+a+1)(2a+1+a+1) = (3a+2)(3a+2)=4=1 \qquad \mod 3\,.$$
και τα στοιχεία του πεπερασμένου σώματος $\mathbb{F}_{3^2}$ μπορούν να αναπαρασταθούν ως δυνάμεις του $a$, ως εξής
$$ $$
$$\mathbb{F}_{3^2} = \lbrace 0,a,a^2,\ldots, a^7,1 \rbrace \,.$$
Παίρνοντας πολυωνυμικές κλάσεις ισοϋπόλοιπων $\mod f(x)$, τα στοιχεία του $\mathbb{F}_{3^2}$ αντιστοιχούν στα $3^2$ το πλήθος πολυώνυμα πρώτου βαθμού, $g(x)=a_1\,x+a_0$, με $a_0,a_1 \in \mathbb{F}_{3}$.
Στο Sage τα παραπάνω υλοποιούνται πολύ εύκολα χρησιμοποιώντας την συνάρτηση GF
(Galois Field) όπου σαν ορίσματα δίνουμε το πλήθος των στοιχείων του $\mathbb{F}_{3^2}$, το όνομα της πρωταρχικής ρίζας του πολυωνύμου $f(x)$, και τέλος το ανάγωγο πολυώνυμο $f(x)$ με συντελεστές στον $\mathbb{Z}_3$, το οποίο στο συγκεκριμένο παράδειγμα είναι το $f(x)=x^2+x+2$.
reset()
F.<a> = GF(3^2, name='a', modulus = x^2 + x + 2 ); print F
for i,x in enumerate(F): print("{} {}".format(i, x))
Ο παραπάνω πίνακας είναι γνωστός ως πίνακας του σώματος, όπου ο δείκτης στην αριστερή στήλη δηλώνει τον εκθέτη του κάθε στοιχείου $a^k$ (εκτός από τον δείκτη $k=0$ που αντιστοιχεί στο μηδέν), και η δεξιά στήλη δηλώνει σε ποιό στοιχείο του πολυωνύμου $g(x)=a_1\,x + a_0$ αντιστοιχεί το στοιχείο $a^k$, με $a_0, a_1 \in \mathbb{F}_3$. Για παράδειγμα
print a^3
print a^4
print a^7
print a^8
Κάθε μή μηδενικό στοιχείο του πεπερασμένου σώματος που κατασκευάσαμε έχει πολλαπλασιαστικό αντίστροφο. Μπορούμε να ελέγξουμε το γεγονός αυτό κατασκευάζοντας τον πίνακα πολλαπλασιασμού του σώματος ως εξής:
print F.multiplication_table()
ενώ ο πίνακας της πρόσθεσης είναι
print F.addition_table()
Προεπιλεγμένα, το Sage παρουσιάζει τους παραπάνω πίνακες έχοντας αντιστοιχήσει τα εννέα στοιχεία του F, με τα εννέα γράμματα του λατινικού αλφάβητου a,b,c...i. Πως μπορούμε να φτιάξουμε αντίστοιχους, δικούς μας, πίνακες στους οποίους να εμφανίζονται τα στοιχεία του σώματος με την αναπαράστασή τους ως πολυώνυμα πρώτου βαθμού; Παρατηρούμε ότι τα στοιχεία του σώματος είναι καταχωρημένα στο Sage σε μια λίστα
print F.list()
Για την πολλαπλασιαστική ομάδα δεν έχει νόημα να συμπεριλάβουμε το στοιχείο μηδέν, οπότε από την λίστα αυτή μεταφέρουμε όλα τα στοιχεία του σώματος, εκτός από το μηδέν, σε ένα πίνακα-γραμμή με την εντολή
multgroupF = matrix([x for x in F.list()[1:9]]); print multgroupF
Προσοχή!!!
Παρατηρήστε ότι στο Sage τα στοιχεία μια λίστας, μιας ν-άδας, ενός διανύσματος, ενός πίνακα κτλ αρχίζουν από την θέση 0 και όχι 1!!!
Για αναφορά, καταχωρούμε ξεχωριστά σε ένα πίνακα με ένα και μόνο στοιχείο που δηλώνει ότι υπολογίζουμε το γινόμενο $x \, y$ των στοιχείων του F
x , y = var('x, y')
prod = matrix([ x*y ]); print prod
Με ένα διπλό loop
υπολογίζουμε τα γινόμενα x*y
, καθώς τα x
και y
διατρέχουν τα μη μηδενικά στοιχεία του σώματος F
, και τα καταχωρούμε σ' ένα τετραγωνικό πίνακα 8x8
ως εξής
MultTable = matrix( [ [x*y for x in F.list()[1:9] ] for y in F.list()[1:9] ] ); print MultTable
Τέλος, διαμορφώνουμε ένα πίνακα κατά blocks
που μας δίνει έναν εύχρηστο τρόπο για να χρησιμοποιούμε τον πίνακα πολλαπλασιασμού του σώματος F.
groupF = block_matrix([[prod, multgroupF],[multgroupF.transpose(), MultTable]]) ; print groupF
Στην αριστερή στήλη και την πρώτη γραμμή αναφέρονται τα στοιχεία της πολλαπλασιαστικής ομάδας του F. Το στοιχείο που είναι στην $(i,j)$ θέση, του μεγάλου 8x8
τετραγωνικού block
πίνακα, αναφέρεται στο γινόμενο του στοιχείου που είναι στην $i$ θέση στην αριστερή στήλη, με εκείνο που είναι στην $j$ θέση στην πάνω γραμμή. Αυτός είναι ο πίνακας της πολλαπλασιαστικής ομάδας του πεπερασμένου σώματος $\mathbb{F}_{3^2}[x]\,/\,f(x)$.
Παρατηρώντας τις μονάδες που εμφανίζονται στην αντιδιαγώνιο, διαπιστώνουμε εύκολα ότι, για παράδειγμα, τα στοιχεία $2\,a+2=a^3$ και $2\,a=a^5$, είναι το ένα πολλαπλασιαστικό αντίστροφο του άλλου, καθώς και ότι το $2=a^4$ είναι πολλαπλασιαστικό αντίστροφο του εαυτού του, αφού $2\cdot 2 = 4 = 1 \mod 3$. Πράγματι στο Sage ελέγχουμε
print (2*a+2)*(2*a)
print a^3*a^5
print a^4*a^4
print Mod(2*2,3)
Μπορούμε να παραγοντοποιήσουμε και να αναπτύξουμε πολυώνυμα πάνω σε πεπερασμένα σώματα. Δημιουργούμε ένα δακτύλιο πολυωνύμων με μεταβλητή x
και συντελεστές πάνω στο πεπερασμένο σώμα που κατασκευάσαμε παραπάνω ως εξής
R.<x> = PolynomialRing(F); print R
print factor(x^2+x+2)
print expand((x-a)*(x-a^3))
print factor(x^2+1)
print expand((x-a^2)*(x-a^6))
print factor(x^2+2*x+2)
print expand((x-a^5)*(x-a^7))
από τα οποία συμπεραίνουμε εύκολα ότι στο πεπερασμένο σώμα που κατασκευάσαμε ισχύουν οι εξής παραγοντοποιήσεις: $$ $$ $$ x^2+x+2 = (x-a)(x-a^3) = (x + a + 1)(x + 2\,a) $$ $$ \quad\qquad x^2+1 = (x-a^2)(x-a^6) = (x + a + 2)(x + 2\,a + 1) $$ $$ x^2+2\,x+2 = (x-a^5)(x-a^7) = (x + a )(x + 2\,a + 2) \,.$$
Οι δυνάμεις της ρίζας $a$ δεν εμφανίζονται τυχαία στους όρους που παραγοντοποιούνται τα παραπάνω (ελάχιστα) πολυώνυμα. Έχουν να κάνουν με τον λεγόμενο αυτομορφισμό Frobenious, ο οποίος υλοποιείται κι αυτός στο Sage!!!
Frob = F.frobenius_endomorphism(); print Frob
Το παραπάνω ενδεικτικό παράδειγμα μας επιτρέπει να ισχυριστούμε ότι το Sage είναι ένα πανίσχυρο σύστημα που εκτελεί συμβολικούς υπολογισμούς .
Το Sage δουλεύει παρόμοια όπως η Python, όμως ορισμένες φορές πρέπει να ορίζουμε τις μεταβλητές μας με ρητό τρόπο xρησιμοποιώντας την συνάρτηση var
. Σε προηγούμενα παραδείγματα είχαμε χρησιμοποιήσει την συνάρτηση αυτή ώς εξής var('x')
.
Κάθε μεταβλητή στο Sage έχει έναν τύπο (type
). Βάζοντας εισαγωγικά ('
ή "
) γύρω από τα ονόματα των μεταβλητών αποτρέπουμε στο να δοθεί στην μεταβλητή μια συγκεκριμένη τιμή.
Το Sage μας παρέχει ένα σύνολο από μαθηματικές σταθερές, όπως το pi
.
Μπορούμε να εργαζόμαστε με το pi
ως συμβολική μεταβλητή και να του δίνουμε οποιαδήποτε τιμή.
print(pi), type(pi)
το οποίο μας πληροφορεί ότι το pi
είναι μια συμβολική έκφραση. Ας του θέσουμε μια τιμή να δούμε τι θα συμβεί.
pi = 3.14
print(pi), type(pi)
Μετά την εκχώρηση της τιμή 3.14 στο pi
έπαψε να είναι συμβολική έκφραση και το Sage μας πληροφορεί ότι απέκτησε τύπο sage.rings.real_mpfr.RealLiteral
. Δηλαδή την χάσαμε την τιμή του pi
ως μαθηματική σταθερή;
Με την εντολή restore
μπορούμε να ανακτήσουμε τον τύπο του pi
ως συμβολική έκφραση καθώς και την τιμή του
restore('pi')
print pi, type(pi)
print numerical_approx(pi, digits=30)
Δώστε προσοχή στα εισαγωγικά στο όρισμα της συνάρτησης restore
. Μετά από την εκτέλεση της εντολής restore
διαπιστώνουμε ότι το pi
ανακτά και πάλι την ιδιότητά του ως έκφραση, και φυσικά την τιμή του με την ακρίβεια που περιγράψαμε στα προηγούμενα.
Μια τιμή μπορεί να καταχωρηθεί ως ένα string
, η οποία μπορεί να υπολογισθεί αργότερα με την εντολή eval
x = 3.14
timh = 'x'
print x , timh, eval(timh)
Χρησιμοποιώντας την συνάρτηση solve
θα πάρουμε μια λίστα από εκφράσεις.
var('z')
equ = z**2 - 3 == 0
sols = solve(equ, z); print sols
print type(sols)
Το Sage μας παρέχει την επιλογή να εξαγάγουμε το αποτέλεσμα ως μια λεξικογραφική λίστα, χρησιμοποιώντας το όρισμα solution_dict=True
sols = solve(equ, z, solution_dict=True); print sols
Κάθε όρος της τελευταίας λίστας περιέχει το όνομα της μεταβλητής και δίπλα της την αντίστοιχη τιμής της z, που ικανοποιεί την εξίσωση. Για παράδειγμα, για να επιλέξουμε την τιμή της πρώτης λύσης, εκτελούμε
print sols[0]; print type(sols[0])
print sols[0][z]
Η λεξικογραφική λίστα είναι χρήσιμη όταν θέλουμε να αντικαταστήσουμε μια συγκεκριμένη τιμή της μεταβλητής z
, σε μια άλλη έκφραση, όπως για παράδειγμα στην ίδια εξίσωση για να επαληθεύσουμε ότι είναι πράγματι λύση της. Αυτό επιτυγχάνεται με την εντολή substitute()
print equ.substitute(sols[0])
print equ.substitute(sols[1])
Ας υποθέσουμε ότι δίνουμε μια συγκεκριμένη αυθαίρετη τιμή στην μεταβλητή z, π.χ. z = 3. Τότε δεν μπορούμε να έχουμε άμεση πρόσβαση στην λεξικογραφική λίστα όπως προηγουμένως, γιατί τώρα η z αναφέρεται σε μια τιμή. Όμως με την επιλογή keys()
ανακτούμε την τιμή της μεταβλητής z, πριν της δώσουμε την τιμή 3. Επιπλέον παρατηρούμε ότι η εντολή αντικατάστασης substitute
εξακολουθεί να δουλεύει :
z = 3; print 'z = ', z
print sols[0].keys(), sols[0].values()
print equ.substitute(sols[0])
Δηλαδή, έστω κι αν δεν μπορούμε να χρησιμοποιήσουμε την z ως μια μεταβλητή, η προηγούμενη ιδιότητά της ως λύσης μιας εξίσωσης εξακολουθεί να περιέχεται στην λεξικογραφική λίστα sols
. Για να πληροφορηθούμε για την τρέχουσα τιμή που αναφέρεται η μεταβλητή z, εκτελούμε την εντολή
print eval(str(sols[0].keys()))
Ας υποθέσουμε ότι θέλουμε να βρούμε τις ρίζες μιας πολυωνυμικής εξίσωσης τρίτου βαθμού, όπου οι συντελεστές είναι συμβολικές εκφράσεις. Πριν προχωρήσουμε στην επίλυση του προβλήματος, επαναφέρουμε όλες τις μεταβλητές μας στην αρχική τους κατάσταση με την εντολή reset()
reset()
var('x, a, b, c')
p = x^3 + a*x^2 + b*x + c
s = solve(p == 0, x, solution_dict=True)
print s
Με πρώτη ματιά, οι τύποι δείχνουν αρκετά περίπλοκοι. Ας ελέγξουμε λοιπόν ότι το αποτέλεσμα που μας έδωσε το Sage είναι πράγματι σωστό, θέτοντας συγκεκριμένες απλές τιμές στις παραμέτρους a,b,c, για παράδειγμα, a=1, b=2, c=3.
Υπενθυμίζουμε ότι η Python μας επιτρέπει να θέτουμε τιμές ταυτόχρονα ως εξής:
(a,b,c) = (1,2,3)
print a, b, c
print p
print s[0]
Όπως παρατηρούμε το αποτέλεσμα δεν είναι αυτό που αναμέναμε. Τόσο το πολυώνυμο p, όσο και οι λύσεις εξακολουθούν να είναι σε συμβολική μορφή. Ίσως κάποιος να δοκίμαζε να ξανατρέξει τον ορισμό του πολυωνύμου p με τις τρέχοντες τιμές των παραμέτρων. Όμως αυτό δεν είναι και τόσο ικανοποιητική λύση, αφού θα μπορούσαμε να έχουμε ορίσει ένα πλήθος από συμβολικές εκφράσεις που να περιείχαν τα a, b, c, οι οποίες μάλιστα να είναι διάσπαρτες στο notebook.
Πως λοιπόν να αναγκάσουμε το πολυώνυμο και τις λύσεις να υπολογισθούν με τις συγκεκριμένες τιμές των a,b,c;
Μια συμβολική έκφραση υπολογίζεται για συγκεκριμένες τιμές των συμβολικών μεταβλητών της, με την παρακάτω εντολή
print p(x=x, a=a, b=b, c=c)
s0 = s[0][x](x=x, a=a, b=b, c=c); print s0
Τώρα μάλιστα! Μπορούμε να δούμε και το πολυώνυμο και μια ρίζα του, υπολογισμένα για την συγκεκριμένη επιλογή των παραμέτρων. Επιπλέον, τώρα υπάρχει τρόπος και να υπολογίσουμε το πολυώνυμο p, όπου x να είναι η τιμή μιας ρίζας!!
print p(x=s0,a=a,b=b,c=c)
Για να ελέγξουμε αν ο αριθμός αυτός είναι πράγματι μηδέν, βρίσκουμε την αριθμητική του τιμή
print n(p(x=s0,a=a,b=b,c=c))
Παρατηρήστε ότι τόσο το πραγματικό όσο και το φαναταστικό μέρος του προηγούμενου μιγαδικού αριθμού είναι πάρα πολύ μικροί αριθμοί, της τάξης $10^{-15}$ και $10^{-16}$, αντίστοιχα, το οποίο σημαίνει ότι είναι κοντά στο μηδέν με ακρίβεια που εκτελεί ο υπολογιστής μας.
Επαναφέρουμε όλες τις τιμές μας στην αρχική τους κατάσταση με την συνάρτηση reset()
, και τρέχουμε
reset()
var('x, y, z')
x=y
y=z
z=3
print x, y, z
δηλαδή η x αναφέρεται στην y, η y αναφέρεται στην z, και η z αναφέρεται στο 3. Μπορούμε να ανιχνεύσουμε τις αναφορικές αυτές τιμές με την εντολή eval()
. Η εντολή αυτή δέχεται ως όρισμα ένα string
. Με διαδοχικές χρήσεις της eval()
μπορούμε να φτάσουμε από το x μέχρι το 3
ex = eval(str(x)); print ex
ey = eval(str(ex)); print ey
print eval(str(eval(str(x))))
Η πρώτη χρήση της eval()
μας δίνει z, ενώ η δεύτερη και η τρίτη εφαρμογή της μας δίνει 3. Παρατηρήστε ότι η σειρά που γίνεται η ανάθεση τιμών σε μεταβλητές παρουσιάζει διαφοροποιήσεις.
reset()
var('x, y, z')
z=3
y=z
x=y
print x, y, z
Επειδή ανατίθεται μια συγκεκριμένη τιμή στο δεξί μέρος μιας έκφρασης, όλες οι μεταβλητές αποκτούν την ίδια τιμή 3. Για να αποτρέψουμε την ανάθεση τιμών στο δεξί μέρος χρησιμοποιούμε εισαγωγικά.
reset()
var('x, y, z')
z= 3
y= 'z'
x= 'y'
print x, y, z
Κάθε αντικείμενο στο Sage έχει έναν τύπο. Ο τύπος ενός αντικειμένου καθορίζει τι είδους χειρισμοί μπορούν να εφαρμοσθούν στο αντικείμενο. Οι κύριοι τύποι δεδομένων στην Python είναι οι εξής: lists
, dictionaries
και tuples
.
Οι κύριοι τύποι αριθμών στο Sage είναι οι ακέραιοι, οι ρητοί, οι πραγματικοί κι οι μιγαδικοί και έχουν τις συντομεύσεις ZZ, QQ, RR
και CC
, αντίστοιχα. Στην παράγραφο αυτή θα δούμε πως μπορούμε να περιορίζουμε τον τύπο ενός αριθμού, και πως μπορούμε να διαλέξουμε έναν τυχαίο αριθμό το οποίο είναι αρκετά χρήσιμο. Επίσης θα δούμε πως μπορούμε να επιλέξουμε κάποιο από τα δυο μέλη μιας εξίσωσης.
Οι κύριοι τύποι αριθμών στο Sage είναι οι ακέραιοι, οι ρητοί, οι πραγματικοί κι οι μιγαδικοί και έχουν τις συντομεύσεις ZZ, QQ, RR
και CC
, αντίστοιχα.
print ZZ
Μπορούμε να μετατρέψουμε ένα string από 16αδική ή 8δική μορφή, σε δεκαδική μορφή
a = ZZ('0x10'); print a
b = ZZ('010'); print b
Δοσμένης μιας λίστας συντελεστών, μπορούμε να βρούμε την τιμή οποιουδήποτε αριθμού, σε κάθε βάση.
c = ZZ(range(10), base=10); print c
d = ZZ(range(10), base=3); print d
Ο αριθμός c παίρνει την λίστα των αριθμών απο το 0 μέχρι το 9 για να μας δώσει στην
γνωστή μας δεκαδική μορφή τον αριθμό
$$ 9876543210 = 0\cdot 10^0 + 1\cdot 10^1 + 2\cdot 10^2 + \ldots + 9\cdot 10^9\,,$$
ενώ ο αριθμός d χρησιμοποιεί την ίδια λίστα συντελεστών για να μας δώσει στην βάση του 3 τον αριθμό
$$ 250959 = 0\cdot 3^0 + 1\cdot 3^1 + 2\cdot 3^2 + \ldots + 9\cdot 3^9$$
Ένας γρήγορος τρόπος για να έχουμε την αναπαράσταση ενός αριθμού με κινητή υποδιαστολή (floating-point) από έναν ρητό αριθμό είναι να περιοριστούμε στο σύνολο QQ
, δηλαδή το σώμα των ρητών αριθμών
print QQ
x = numerical_approx(pi, digits=20)
y = QQ(x); print y
Δεν μπορούμε άμεσα να περιoρίσουμε το pi σε έναν ρητό, γιατί
z = RR(y); print z
print QQ(z)
Παρατηρήστε την διαφορά μεταξύ της τιμής 21053343141/6701487259 του y, και της τιμής 245850922/78256779 του QQ(RR(y))
. Η διαφοροποίηση οφείλεται στο ότι η ακρίβεια του RR
είναι η ίδια με αυτή των 53 bits (αποθηκεύονται 52) ενός επεξεργαστή που εκτελεί πράξεις διπλής κινητής υποδιαστολής.
print RR
print RDF
print RR == RDF
Αν και το RR
έχει ακρίβεια 53 bits, η τελευταία δεν είναι η ίδια με αυτή του RealDoubleField
(RDF
). Η διαφορά αυτή γίνεται αντιληπτή γεννώντας
έναν τυχαίο αριθμό στα σώματα RR
και RDF
αντίστοιχα
x = RR.random_element(); print x, type(x)
y = RDF.random_element(); print y, type(y)
Ο τύπος του x είναι sage.rings.real_mpfr.RealNumber
, ενώ του y είναι
sage.rings.real_double.RealDoubleElement
. Η ίδια διαφορά διατηρείται και για τους μιγαδικούς
x = CC.random_element(); print x, type(x)
y = CDF.random_element(); print y, type(y)
Συχνά δουλεύουμε με εξισώσεις
reset()
eqn = x^2 + 3*x + 2 == 0
print type(eqn)
Ο τύπος της εξίσωσης είναι sage.symbolic.expression.Expression
, δηλαδή μια συμβολική έκφραση. Η έκφραση που δηλώσαμε με eqn
έχει έναν χειριστή (operator
)
print eqn.operator()
Στο Sage επιλέγουμε το αριστερό και το δεξί μέλος της εξίσωσης, αντίστοιχα, ως εξής:
print eqn.lhs()
print eqn.rhs()
Εναλλακτικές εντολές της lhs()
, είναι η left()
και
left_hand_side()
, ενώ της εντολής rhs()
, είναι οι right()
και right_hand_side()
, αντίστοιχα.
Το επόμενο παράδειγμα είναι από το βιβλίο του πρωτεργάτη του Sage, William Stein, με τίτλο
Sage for Power Users.
Στο Sage μπορούμε να αποθηκεύουμε έμμεσες αναφορές για συμβολικά αντικείμενα χρησιμοποιώντας συναρτήσεις (functions
). Για παράδειγμα:
def our_append(item, L=[]):
L.append(item)
print L
our_append(1/3)
our_append('1/3')
our_append(1.0/3)
Για να ανιχνεύσουμε τι συμβαίνει με την συνάρτηση our_append
) που ορίσαμε, ας την τροποποιήσουμε ελαφρώς, με την our_append2
), στην οποία
τυπώνουμε επιπλέον την ταυτότητα του L
def our_append2(item, L=[]):
L.append(item)
print L, id(L)
return id(L)
idL = our_append2(1/3)
idL = our_append2('1/3')
idL = our_append2(1.0/3)
Την πρώτη φορά που καλέσαμε την συνάρτηση our_append2
δημιουργήθηκε μια άδεια λίστα L = [ ], η οποία τοποθετήθηκε κάπου στην μνήμη. Κάθε φορά που καλείται η συνάρτηση με κάποιο όρισμα, το Sage ανατρέχει στην L, στην ίδια διεύθυνση στην μνήμη. Παρατηρήστε ότι η L δεν υπάρχει έξω από την συνάρτηση!
print L
Με την βιβλιοθήκη ctypes
μπορούμε να ανακτούμε την διεύθυνση στην οποία είναι τοποθετημένο ένα αντικείμενο
id = our_append2(0)
import ctypes
print ctypes.cast(idL, ctypes.py_object).value
Σε αυτή την παράγραφο θα δούμε πως είναι η εσωτερική δομή εκφράσεων στο Sage σε μεγαλύτερο βάθος
from sage.ext.fast_callable import ExpressionTreeBuilder
etb = ExpressionTreeBuilder(vars=['x','y'])
x = etb.var('x')
y = etb.var('y')
print x+y
print x-y
print x*y
print x / y
print x^y
Επιβάλλαμε στις μεταβλητές x,y να αλλάξουν τύπο και να γίνουν fast_callable
s = x + y; print type(s)
p = x^3 + 4*x*y^2 - 7*y + 2
print p
Με βάση την προηγούμενη έκφραση του πολυωνύμου p σε δυο μεταβλητές x,y, μπορούμε να φτιάξουμε το παρακάτω δέντρο.
add
|
+-- sub
| |
| +-- add
| | |
| | +-- ipow
| | | |
| | | +-- v_0
| | | |
| | | +-- 3
| | |
| | +-- mul
| | |
| | +-- mul
| | | |
| | | +-- 4
| | | |
| | | +-- v_0
| | |
| | +-- ipow
| | |
| | +-- v_1
| | |
| | +-- 2
| |
| +-- mul
| |
| +-- 7
| |
| +-- v_1
|
+-- 2