Κεφάλαιο 1





1. Εισαγωγή στο Sage text

1.1 Πως τρέχουμε το Sage σε jupyter notebook

Α. Στο Εργαστήριο ΗΥtext


Ανοίγουμε μια οθόνη εντολών (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


Εναλλακτικά στο menu των προγραμμάτων έχει δημιουργηθεί μια συντόμευση που τρέχει αυτόματα την εντολή text


/opt/sage-7.4/./sage -n jupyter


Αν επιλέξετε τον δεύτερο τρόπο μην ξεχάσετε να δημιουργήσετε ένα directory στο οποίο θα σώζετε και θα αναζητάτε τα notebooks που θα δημιουργούμε στα μαθήματα!

Β. Στον προσωπικό σας υπολογιστή

Μπορείτε να εγκαταστήσετε το Sage στον προσωπικό σας υπολογιστή (Windows/Mac/Linux) ακολουθώντας τις οδηγίες εδώ.

Γ. Στο sagemathcloud

text

Μπορούμε να χρησιμοποιήσουμε το 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 notebooks

Προτείνεται, χωρίς να είναι απαραίτητο, να χρησιμοποιήσουμε το 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.

1.2 Τι είναι το Sage

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

Για παράδειγμα, αν ζητήσουμε να κατασκευασθεί ένα αριθμητικό πρόγραμμα για να "λύσει την εξίσωση sin(x)=0, ως προς x", η πιο πιθανή απάντηση που θα παίρναμε θα ήταν μια ποσότητα με ακρίβεια 32-bit, την οποία το πρόγραμμα θα τύπωνε σαν 0.0, και όχι μια απάντηση της μορφής "{ n π | integer(n) } ". Από μαθηματική σκοπιά, ένα λογισμικό που έχει την δυνατότητα να μας παρέχει την τελευταία συμβολική, παραμετρική μορφή, υπερέχει από ένα αντίστοιχο που μας δίνει μια και μόνη αριθμητική τιμή. Μια και μόνο αριθμητική τιμή μπορεί να είναι χρήσιμη για έναν συγκεκριμένο σκοπό, όμως όσο απλή κι αν είναι, δεν παύει να είναι ένας συμβιβασμός.

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

Το Sage είναι ένα σύνολο λογισμικών τα οποία είνα ικανά να εκτελούν τόσο συμβολικούς υπολογισμούς, όσο και αριθμητικούς, και αναφέρεται από τα αρχικά Software for Algebra, Geometry and Experimentation.

Ορισμένα κύρια χαρακτηριστικά του Sage είναι:

  • Είναι ελεύθερο λογισμικό ανοικτού κώδικα και είναι διαθέσιμο με την άδεια GNU General Public License.
  • Ως γλώσσα προγραμματισμού χρησιμοποιεί την Python, και έχει μια αρκετά μεγάλη κοινότητα προγραμματιστών.
  • Από τον σχεδιασμό του το Sage δεν "ανακαλύπτει τον τροχό", αλλά ενσωματώνει διάφορα ισχυρά μαθηματικά λογισμικά ανοικτού κώδικα τα οποία εκτελούν συμβολικούς και αριθμητικούς υπολογισμούς, όπως τα GAP, maxima, R, Singular, sympy, numpy κτλ. Επιπλέον το SageMath μπορεί να τρέξει και εντολές εμπορικών μαθηματικών λογισμικών κλειστού κώδικα, όπως το Mathematica, Maple, Matlab κτλ, αρκεί ο χρήστης να έχει εγκατεστημένα τα τελευταία στο υπολογιστή του. Οπότε κάποιος θα μπορούσε να ισχυρισθεί, και όχι άδικα, ότι το Sage είναι ένα από τα ισχυρότερα συστήματα συμβολικών υπολογισμών που είναι διαθέσιμα αυτή την στιγμή.
text
Το ρητό του Sage: Κατασκευάζουμε το αυτοκίνητο αντί να ανακαλύπτουμε τον τροχό.

1.3 Πρώτη επαφή με το Sage.

Τρέχουμε τις εντολές του Sage σε jupyter notebook σε κελιά (cells) κώδικα (code). Οι εντολές εκτελούνται πατώντας:

  • Ctrl-Enter για να εκτελέσουμε το κελί που βρισκόμαστε,
  • Alt-Enter για να εκτελέσουμε το κελί που βρισκόμαστε και να εισαγάγουμε ένα νέο κελί αμέσως μετά,
  • Shift-Enter για να εκτελέσουμε το κελί που βρισκόμαστε και να επιλέξουμε το κελί αμέσως μετά.

Επιλέγουμε για να γράψουμε μέσα σε ένα cell με Enter , ή αριστερό click στο ποντίκι. Στο jupyter notebook πληκτρολογούμε Ctrl-Shift-P για να δούμε όλες τις διαθέσιμες συντομεύσεις πληκτρολογίου και διάφορες επιλογές για να επεξεργαζόμαστε τα cells καθώς και τον πυρήνα. Ορισμένες από αυτές τις επιλογές είναι διαθέσιμες και στο menu επιλογών του jupyter στο πάνω μέρος του notebook.

In [1]:
print pi
pi
In [2]:
print sin(pi)
0
In [3]:
print(pi)
pi
In [4]:
print type(_)
<type 'str'>
In [5]:
print type(pi)
<type 'sage.symbolic.expression.Expression'>
In [6]:
graf = plot(exp(-x^2)*sin(16*x),(x,-pi,pi),figsize=4); show(graf)

Το Sage είναι κατά κύριο λόγο είναι ένα σύστημα που εκτελεί συμβολικούς υπολογισμούς. Για αριθμητικούς υπολογισμούς δεν περιορίζεται στην αριθμητική ακρίβεια του επεξεργαστή ενός υπολογιστή. Για παράδειγμα, για να δούμε τον $\pi$ με 20 δεκαδικά ψηφία τρέχουμε

In [7]:
pi20 = pi.n(digits=20); print pi20
3.1415926535897932385
In [8]:
print sin(pi20)
6.5640070857470010853e-22
In [9]:
print type(pi20)
<type 'sage.rings.real_mpfr.RealNumber'>

Παρατηρούμε ότι σε αντίθεση με την τιμή του ημιτόνου στο $\pi$, η τιμή sin(pi20) δεν είναι πλέον μηδέν.

1.4 Ποιά συστήματα χρησιμοποιούνται στο Sage;

In [10]:
from sage.misc.citation import get_systems
print get_systems('Rational(0.75)')
['MPFR']
In [11]:
print get_systems('RealField(10)(pi)')
['MPFR', 'ginac']
In [12]:
import sage.misc.citation
help(sage.misc.citation)
Help on module sage.misc.citation in sage.misc:

NAME
    sage.misc.citation - File: sage/misc/citation.pyx (starting at line 1)

FILE
    /home/tasos/sage-7.5.1/local/lib/python2.7/site-packages/sage/misc/citation.so

DESCRIPTION
    Dependency usage tracking for citations

FUNCTIONS
    get_systems(...)
        get_systems(cmd)
        File: sage/misc/citation.pyx (starting at line 50)
        
            Returns a list of the systems used in running the command
            cmd.  Note that the results can sometimes include systems
            that did not actually contribute to the computation. Due
            to caching and the inability to follow all C calls, it
            could miss some dependencies as well.
        
            INPUT:
        
            - ``cmd`` - a string to run
        
            EXAMPLES::
        
                sage: from sage.misc.citation import get_systems
                sage: s = get_systems('integrate(x^2, x)'); #priming coercion model
                sage: get_systems('integrate(x^2, x)')
                ['ginac', 'Maxima']
                sage: R.<x,y,z> = QQ[]
                sage: I = R.ideal(x^2+y^2, z^2+y)
                sage: get_systems('I.primary_decomposition()')
                ['Singular']
        
                sage: a = var('a')
                sage: get_systems('((a+1)^2).expand()')
                ['ginac']

DATA
    SAGE_ROOT = '/home/tasos/sage-7.5.1'
    systems = {'Axiom': ['sage.interfaces.axiom'], 'ECM': ['sage.interface...


In [13]:
print sage.misc.citation.systems.keys()
['Mathematica', 'M4RI', 'PARI', 'Frobby', 'MuPAD', 'mwrank', 'Axiom', 'LiE', 'Macaulay2', 'MPFI', 'Singular', 'ECM', 'Linbox', 'GAP', 'FLINT', 'matlab', 'Octave', 'povray', 'numpy', 'MPFR', 'qsieve', 'ginac', 'gfan', 'scipy', 'KASH', 'GMP', 'Maxima', 'Symmetrica', 'PolyBoRi', 'Tachyon', 'Magma', 'R', 'NTL', 'Givaro', 'Maple']

1.5 Το Sage ως ένας υπολογιστής

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

In [14]:
print 37^37
10555134955777783414078330085995832946127396083370199442517

Με ένα underscore παίρνουμε το αποτέλεσμα από τον αμέσως προηγούμενο υπολογισμό. Με δυο underscore παίρνουμε το αποτέλεσμα του προτελευταίου υπολογισμού και με τρία, πριν τρεις υπολογισμούς. Περαιτέρω χρήση τους δεν είναι δυνατή.

Ας θεωρήσουμε τώρα ότι θέλουμε να υπολογίσουμε την διαφορά ανάμεσα στην πραγματική τιμή του $\pi$ και την αριθμητική του τιμή με μια ακρίβεια 30 ψηφίων. Ο πιο γρήγορος τρόπος για να βρούμε την τελευταία είναι μέσω της συνάρτησης numerical_approx.

In [15]:
print numerical_approx(pi,digits=30)
3.14159265358979323846264338328

Όμως συχνά θέλουμε οι υπολογισμοί μας να εκτελούνται με καθορισμένη ακρίβεια, για παράδειγμα 30 δεκαδικών ψηφίων. Τότε χρησιμοποιούμε την συνάρτηση RealField με δεδομένη ακρίβεια, για παράδειγμα για τον υπολογισμό του $\pi$ με προσέγγιση 30 ψηφίων δίνουμε

In [16]:
R = RealField(30*log(10,2))
pi30 = R(pi) ; print pi30
3.1415926535897932384626433833

Με log(10,2) υπολογίζουμε τον λογάριθμο του 10 με βάση το 2, γιατί το όρισμα στην RealField εκφράζεται σε bits, και για κάθε δεκαδικό ψηφίο χρειαζόμαστε $\log_2 10\approx 3.32$ bits. Μετά την δημιουργία του R, μετατρέπουμε το σύμβολο για την μαθηματική σταθερή $\pi$ σε μια προσέγγιση 30 ψηφίων, την οποία καταχωρούμε στην τιμή pi30. Για να ελέγξουμε την διαφορά του $\pi$ και του pi30 με την δεδομένη ακρίβεια των 30 ψηφίων δίνουμε

In [17]:
print R(pi-pi30)
0.00000000000000000000000000000
In [18]:
print RealField(40*log(10,2))(pi-pi30)
1.69568553528388823010177990083205496387e-31

οπότε η τιμή pi30 έχει την επιθυμητή ακρίβεια 30 δεκαδικών ψηφίων. Για να πάρουμε βοήθεια για κάποια συνάρτηση/εντολή του Sage εκτελούμε για παράδειγμα

In [19]:
help(RealField)

ή εναλλακτικά

In [20]:
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}} } \,. $$ Οι ρητοί αριθμοί που προκύπτουν κρατώντας μόνο ένα πεπερασμένο πλήθος όρων στο συνεχές κλάσμα λέγονται συγκλίνοντες. Για παράδειγμα

In [21]:
x = sqrt(2)
c = continued_fraction(x); print c
[1; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...]

Δηλαδή $$\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 εκτελούμε

In [22]:
print c.convergents()
lazy list [1, 3/2, 7/5, ...]
In [23]:
print c.convergent(15)
665857/470832
In [24]:
print c.numerator(153)
44302225809207714047802677511548402965313235415702533504483
In [25]:
print c.denominator(153)
31326404291348457390865124320006534354088526499185529979738

όπου οι συναρτήσεις numerator(n), και denominator(n) μας δίνουν τον αριθμητή και τον παρονομαστή του $n$-στού συγκλίνοντα στην αναπαράσταση του πραγματικού $x$ με απλά συνεχή κλάσματα.

1.6 Μιγαδικοί, αλγεβρικοί αριθμοί και πεπερασμένα σώματα

1.6.1 Μιγαδικοί αριθμοί

Στο Sage το σώμα των μιγαδικών αριθμών είναι γνωστό ως ComplexField(), όπου στο όρισμα μπορούμε να θέσουμε (σε bits) την ακρίβεια που θέλουμε να χρησιμοποιήσουμε στους υπολογισμούς. Όμως, δεν πρέπει να μας διαφεύγει ότι το βασικό χαρακτηριστικό του Sage είναι ότι πρόκειται για ένα λογισμικό που εκτελεί συμβολικούς υπολογισμούς. Στο Sage η φανταστική μονάδα δηλώνεται με I.

In [26]:
C = ComplexField(100); print C
Complex Field with 100 bits of precision
In [27]:
print sqrt(-1)
I
In [28]:
print I^2
-1
In [29]:
a = (-1+I)^2; b = (1 - I)^2;
In [30]:
print a
-2*I
In [31]:
print b
-2*I


Το Sage γνωρίζει να λύνει πολυωνυμικές εξισώσεις με συντελεστές στους μιγαδικούς αριθμούς. Για παράδειγμα θα λύσουμε την εξίσωση $$ z^3=i$$ Ορίζουμε με την συνάρτηση var μια (συμβολική έκφραση) μεταβλητή $z$ και με την εντολή solve λύνουμε την παραπάνω εξίσωση. Χρησιμοποιούμε το προαιρετικό όρισμα solution_dict=True για να πούμε στην συνάρτηση solve να μας επιστρέψει τις λύσεις στην μορφή μιας λίστας Python με ανάλογο λεξικό.

In [32]:
var("z")
rizes=solve(z^3==I,z,solution_dict=True); print rizes;  print type(rizes)
[{z: 1/2*I*sqrt(3)*(-1)^(1/6) - 1/2*(-1)^(1/6)}, {z: -1/2*I*sqrt(3)*(-1)^(1/6) - 1/2*(-1)^(1/6)}, {z: (-1)^(1/6)}]
<type 'list'>


Στην συνέχεια ρησιμοποιούμε ένα βρόχο (loop) και καταχωρούμε τις λύσεις σε μια νέα λίστα που την ονομάζουμε lyseis. Με τον ίδιο τρόπο δημιουργούμε τις λίστες metra, gwnies, που περιέχουν τα μέτρα και τις γωνίες των λύσεων, αντίστοιχα. Στο Sage το πραγματικό και το φανταστικό μέρος ενός μιγαδικού αριθμού δίνονται με τις συναρτήσεις real_part() και imag_part(), αντίστοιχα.
Οι εντολές abs() και arg(), μας δίνουν το μέτρο και το όρισμα (argument) ενός μιγαδικού αριθμού, αντίστοιχα.

In [33]:
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() )
In [34]:
print lyseis
[-1/2*sqrt(3) + 1/2*I, -I, 1/2*sqrt(3) + 1/2*I]
In [35]:
print metra
[1, 1, 1]
In [36]:
print gwnies
[5/6*pi, -1/2*pi, 1/6*pi]


Παρατηρούμε ότι και οι τρείς λύσεις έχουν μέτρο μονάδα, συνεπώς βρίσκονται πάνω στον μοναδιαίο κύκλο, και σε γωνίες $$ \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\,. $$
In [37]:
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)

1.6.2 Αλγεβρικοί αριθμοί

Ο πραγματικός αριθμός $\sqrt{2}$ είναι ένας αλγεβρικός αριθμός. Το ελάχιστο πολυώνυμο που έχει ρίζα έναν αλγεβρικό αριθμό, λέγεται το ελάχιστο πολυώνυμο του αριθμού. Για παράδειγμα, η εντολή

In [38]:
print sqrt(2).minpoly()
x^2 - 2

μας επιστρέφει ότι το ελάχιστο πολυώνυμο του $\sqrt{2}$ είναι το $x^2-2$. Το αποτέλεσμα της παραγοντοποίησης ενός πολυωνύμου εξαρτάται από το σώμα των αριθμών που είναι ορισμένο.

In [39]:
print factor(x^2-1)
(x + 1)*(x - 1)
In [40]:
print factor(x^2-2)
x^2 - 2

Το πολυώνυμο $x^2-1$ παραγοντοποιείται σε $(x+1)(x-1)$, ενώ το πολυώνυμο $x^2-2$ δεν παραγοντοποιείται πάνω στο προεπιλεγμένο σώμα, που είναι το σύνολο $\mathbb{Q}$ των ρητών. Αν ένα πολυώνυμο δεν παραγοντοποιείται σε ένα συγκεκριμένο σώμα λέγεται ανάγωγο στο αντίστοιχο σώμα. Μπορούμε να ορίσουμε ένα σώμα $K$ στο οποίο το $c$ είναι η τετραγωνική ρίζα του $2$, και να υπολογίζουμε και να απλοποιούμε εκφράσεις στο K, έχοντας ενσωματώσει την πληροφορία ότι το ελάχιστο πολυώνυμο του $\sqrt{2}$ είναι το $x^2-2$.

In [41]:
K.<c> = NumberField(x^2-2); print K
Number Field in c with defining polynomial x^2 - 2
In [42]:
print c^2
2
In [43]:
print c^3
2*c

Αν θεωρήσουμε τώρα το δακτύλιο των πολυωνύμων με συντελεστές στο σώμα $K$, τότε το πολυώνυμο $x^2-2$ παραγοντοποιείται στο $K$. Πραγματικά

In [44]:
R.<x> = PolynomialRing(K)
p = x^2 - 2
print factor(p)
(x - c) * (x + c)

1.6.3 Πεπερασμένα σώματα

Στην παράγραφο αυτή αναφέρονται κάποιες έννοιες στις οποίες ο αναγνώστης ίσως να μην είναι τόσο εξοικειωμένος. Μπορείτε να συνεχίσετε στην επόμενη παράγραφο. Όμως ενθαρρύνω τον αναγνώστη να "βουτήξει" δίχως κανένα ενδοιασμό, όπως ακριβώς τον ενθαρρύνω να κάνει το ίδιο και με το 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$.

In [45]:
reset()
F.<a> = GF(3^2, name='a', modulus = x^2 + x + 2 ); print F
Finite Field in a of size 3^2
In [46]:
for i,x in enumerate(F):  print("{} {}".format(i, x))
0 0
1 a
2 2*a + 1
3 2*a + 2
4 2
5 2*a
6 a + 2
7 a + 1
8 1

Ο παραπάνω πίνακας είναι γνωστός ως πίνακας του σώματος, όπου ο δείκτης στην αριστερή στήλη δηλώνει τον εκθέτη του κάθε στοιχείου $a^k$ (εκτός από τον δείκτη $k=0$ που αντιστοιχεί στο μηδέν), και η δεξιά στήλη δηλώνει σε ποιό στοιχείο του πολυωνύμου $g(x)=a_1\,x + a_0$ αντιστοιχεί το στοιχείο $a^k$, με $a_0, a_1 \in \mathbb{F}_3$. Για παράδειγμα

In [47]:
print a^3
2*a + 2
In [48]:
print a^4
2
In [49]:
print a^7
a + 1
In [50]:
print a^8
1

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

In [51]:
print F.multiplication_table()
*  a b c d e f g h i
 +------------------
a| a a a a a a a a a
b| a c d e f g h i b
c| a d e f g h i b c
d| a e f g h i b c d
e| a f g h i b c d e
f| a g h i b c d e f
g| a h i b c d e f g
h| a i b c d e f g h
i| a b c d e f g h i

ενώ ο πίνακας της πρόσθεσης είναι

In [52]:
print F.addition_table()
+  a b c d e f g h i
 +------------------
a| a b c d e f g h i
b| b f i e g a d c h
c| c i g b f h a e d
d| d e b h c g i a f
e| e g f c i d h b a
f| f a h g d b e i c
g| g d a i h e c f b
h| h c e a b i f d g
i| i h d f a c b g e

Προεπιλεγμένα, το Sage παρουσιάζει τους παραπάνω πίνακες έχοντας αντιστοιχήσει τα εννέα στοιχεία του F, με τα εννέα γράμματα του λατινικού αλφάβητου a,b,c...i. Πως μπορούμε να φτιάξουμε αντίστοιχους, δικούς μας, πίνακες στους οποίους να εμφανίζονται τα στοιχεία του σώματος με την αναπαράστασή τους ως πολυώνυμα πρώτου βαθμού; Παρατηρούμε ότι τα στοιχεία του σώματος είναι καταχωρημένα στο Sage σε μια λίστα

In [53]:
print F.list()
[0, a, 2*a + 1, 2*a + 2, 2, 2*a, a + 2, a + 1, 1]

Για την πολλαπλασιαστική ομάδα δεν έχει νόημα να συμπεριλάβουμε το στοιχείο μηδέν, οπότε από την λίστα αυτή μεταφέρουμε όλα τα στοιχεία του σώματος, εκτός από το μηδέν, σε ένα πίνακα-γραμμή με την εντολή

In [54]:
multgroupF = matrix([x for x in  F.list()[1:9]]); print multgroupF
[      a 2*a + 1 2*a + 2       2     2*a   a + 2   a + 1       1]

Προσοχή!!! Παρατηρήστε ότι στο Sage τα στοιχεία μια λίστας, μιας ν-άδας, ενός διανύσματος, ενός πίνακα κτλ αρχίζουν από την θέση 0 και όχι 1!!!

Για αναφορά, καταχωρούμε ξεχωριστά σε ένα πίνακα με ένα και μόνο στοιχείο που δηλώνει ότι υπολογίζουμε το γινόμενο $x \, y$ των στοιχείων του F

In [55]:
x , y = var('x, y')
prod = matrix([ x*y ]); print prod
[x*y]

Με ένα διπλό loop υπολογίζουμε τα γινόμενα x*y, καθώς τα x και y διατρέχουν τα μη μηδενικά στοιχεία του σώματος F, και τα καταχωρούμε σ' ένα τετραγωνικό πίνακα 8x8 ως εξής

In [56]:
MultTable = matrix( [ [x*y for x in  F.list()[1:9] ] for y in F.list()[1:9] ] ); print MultTable
[2*a + 1 2*a + 2       2     2*a   a + 2   a + 1       1       a]
[2*a + 2       2     2*a   a + 2   a + 1       1       a 2*a + 1]
[      2     2*a   a + 2   a + 1       1       a 2*a + 1 2*a + 2]
[    2*a   a + 2   a + 1       1       a 2*a + 1 2*a + 2       2]
[  a + 2   a + 1       1       a 2*a + 1 2*a + 2       2     2*a]
[  a + 1       1       a 2*a + 1 2*a + 2       2     2*a   a + 2]
[      1       a 2*a + 1 2*a + 2       2     2*a   a + 2   a + 1]
[      a 2*a + 1 2*a + 2       2     2*a   a + 2   a + 1       1]

Τέλος, διαμορφώνουμε ένα πίνακα κατά blocks που μας δίνει έναν εύχρηστο τρόπο για να χρησιμοποιούμε τον πίνακα πολλαπλασιασμού του σώματος F.

In [57]:
groupF = block_matrix([[prod, multgroupF],[multgroupF.transpose(), MultTable]]) ; print groupF
[    x*y|      a 2*a + 1 2*a + 2       2     2*a   a + 2   a + 1       1]
[-------+---------------------------------------------------------------]
[      a|2*a + 1 2*a + 2       2     2*a   a + 2   a + 1       1       a]
[2*a + 1|2*a + 2       2     2*a   a + 2   a + 1       1       a 2*a + 1]
[2*a + 2|      2     2*a   a + 2   a + 1       1       a 2*a + 1 2*a + 2]
[      2|    2*a   a + 2   a + 1       1       a 2*a + 1 2*a + 2       2]
[    2*a|  a + 2   a + 1       1       a 2*a + 1 2*a + 2       2     2*a]
[  a + 2|  a + 1       1       a 2*a + 1 2*a + 2       2     2*a   a + 2]
[  a + 1|      1       a 2*a + 1 2*a + 2       2     2*a   a + 2   a + 1]
[      1|      a 2*a + 1 2*a + 2       2     2*a   a + 2   a + 1       1]

Στην αριστερή στήλη και την πρώτη γραμμή αναφέρονται τα στοιχεία της πολλαπλασιαστικής ομάδας του 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 ελέγχουμε

In [58]:
print (2*a+2)*(2*a)
1
In [59]:
print a^3*a^5
1
In [60]:
print a^4*a^4
1
In [61]:
print Mod(2*2,3)
1

Μπορούμε να παραγοντοποιήσουμε και να αναπτύξουμε πολυώνυμα πάνω σε πεπερασμένα σώματα. Δημιουργούμε ένα δακτύλιο πολυωνύμων με μεταβλητή x και συντελεστές πάνω στο πεπερασμένο σώμα που κατασκευάσαμε παραπάνω ως εξής

In [62]:
R.<x> = PolynomialRing(F); print R
Univariate Polynomial Ring in x over Finite Field in a of size 3^2
In [63]:
print factor(x^2+x+2)
(x + a + 1) * (x + 2*a)
In [64]:
print expand((x-a)*(x-a^3))
x^2 + x + 2
In [65]:
print factor(x^2+1)
(x + a + 2) * (x + 2*a + 1)
In [66]:
print expand((x-a^2)*(x-a^6))
x^2 + 1
In [67]:
print factor(x^2+2*x+2)
(x + a) * (x + 2*a + 2)
In [68]:
print expand((x-a^5)*(x-a^7))
x^2 + 2*x + 2

από τα οποία συμπεραίνουμε εύκολα ότι στο πεπερασμένο σώμα που κατασκευάσαμε ισχύουν οι εξής παραγοντοποιήσεις: $$ $$ $$ 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!!!

In [69]:
Frob = F.frobenius_endomorphism(); print Frob
Frobenius endomorphism a |--> a^3 on Finite Field in a of size 3^2

Το παραπάνω ενδεικτικό παράδειγμα μας επιτρέπει να ισχυριστούμε ότι το Sage είναι ένα πανίσχυρο σύστημα που εκτελεί συμβολικούς υπολογισμούς .

1.7 Σύμβολα και μεταβλητές

Το Sage δουλεύει παρόμοια όπως η Python, όμως ορισμένες φορές πρέπει να ορίζουμε τις μεταβλητές μας με ρητό τρόπο xρησιμοποιώντας την συνάρτηση var. Σε προηγούμενα παραδείγματα είχαμε χρησιμοποιήσει την συνάρτηση αυτή ώς εξής var('x').

Κάθε μεταβλητή στο Sage έχει έναν τύπο (type). Βάζοντας εισαγωγικά (' ή ") γύρω από τα ονόματα των μεταβλητών αποτρέπουμε στο να δοθεί στην μεταβλητή μια συγκεκριμένη τιμή.

1.7.1 Εκφράσεις και ονόματα

Το Sage μας παρέχει ένα σύνολο από μαθηματικές σταθερές, όπως το pi. Μπορούμε να εργαζόμαστε με το pi ως συμβολική μεταβλητή και να του δίνουμε οποιαδήποτε τιμή.

In [70]:
print(pi), type(pi)
pi <type 'sage.symbolic.expression.Expression'>

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

In [71]:
pi = 3.14
print(pi), type(pi)
3.14000000000000 <type 'sage.rings.real_mpfr.RealLiteral'>

Μετά την εκχώρηση της τιμή 3.14 στο pi έπαψε να είναι συμβολική έκφραση και το Sage μας πληροφορεί ότι απέκτησε τύπο sage.rings.real_mpfr.RealLiteral. Δηλαδή την χάσαμε την τιμή του pi ως μαθηματική σταθερή;

Με την εντολή restore μπορούμε να ανακτήσουμε τον τύπο του pi ως συμβολική έκφραση καθώς και την τιμή του

In [72]:
restore('pi')
print pi, type(pi)
print numerical_approx(pi, digits=30)
pi <type 'sage.symbolic.expression.Expression'>
3.14159265358979323846264338328

Δώστε προσοχή στα εισαγωγικά στο όρισμα της συνάρτησης restore. Μετά από την εκτέλεση της εντολής restore διαπιστώνουμε ότι το pi ανακτά και πάλι την ιδιότητά του ως έκφραση, και φυσικά την τιμή του με την ακρίβεια που περιγράψαμε στα προηγούμενα.

Μια τιμή μπορεί να καταχωρηθεί ως ένα string, η οποία μπορεί να υπολογισθεί αργότερα με την εντολή eval

In [73]:
x = 3.14
timh = 'x'
print x , timh, eval(timh)
3.14000000000000 x 3.14000000000000

1.7.2 Επαλήθευση λύσεων

Χρησιμοποιώντας την συνάρτηση solve θα πάρουμε μια λίστα από εκφράσεις.

In [74]:
var('z')
equ = z**2 - 3 == 0
sols = solve(equ, z); print sols
print type(sols)
[
z == -sqrt(3),
z == sqrt(3)
]
<class 'sage.structure.sequence.Sequence_generic'>

Το Sage μας παρέχει την επιλογή να εξαγάγουμε το αποτέλεσμα ως μια λεξικογραφική λίστα, χρησιμοποιώντας το όρισμα solution_dict=True

In [75]:
sols = solve(equ, z, solution_dict=True); print sols
[{z: -sqrt(3)}, {z: sqrt(3)}]

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

In [76]:
print sols[0]; print type(sols[0])
{z: -sqrt(3)}
<type 'dict'>
In [77]:
print sols[0][z]
-sqrt(3)

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

In [78]:
print equ.substitute(sols[0])
0 == 0
In [79]:
print equ.substitute(sols[1])
0 == 0

Ας υποθέσουμε ότι δίνουμε μια συγκεκριμένη αυθαίρετη τιμή στην μεταβλητή z, π.χ. z = 3. Τότε δεν μπορούμε να έχουμε άμεση πρόσβαση στην λεξικογραφική λίστα όπως προηγουμένως, γιατί τώρα η z αναφέρεται σε μια τιμή. Όμως με την επιλογή keys() ανακτούμε την τιμή της μεταβλητής z, πριν της δώσουμε την τιμή 3. Επιπλέον παρατηρούμε ότι η εντολή αντικατάστασης substitute εξακολουθεί να δουλεύει :

In [80]:
z = 3; print 'z = ', z
z =  3
In [81]:
print sols[0].keys(), sols[0].values()
[z] [-sqrt(3)]
In [82]:
print equ.substitute(sols[0])
0 == 0

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

In [83]:
print eval(str(sols[0].keys()))
[3]

1.7.2 Υπολογισμός της τιμής μιας έκφρασης

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

In [84]:
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
[{x: -1/18*(a^2 - 3*b)*(-I*sqrt(3) + 1)/(-1/27*a^3 + 1/6*a*b - 1/2*c + 1/6*sqrt(-1/3*a^2*b^2 + 4/3*b^3 + 2/3*(2*a^3 - 9*a*b)*c + 9*c^2))^(1/3) - 1/2*(-1/27*a^3 + 1/6*a*b - 1/2*c + 1/6*sqrt(-1/3*a^2*b^2 + 4/3*b^3 + 2/3*(2*a^3 - 9*a*b)*c + 9*c^2))^(1/3)*(I*sqrt(3) + 1) - 1/3*a}, {x: -1/18*(a^2 - 3*b)*(I*sqrt(3) + 1)/(-1/27*a^3 + 1/6*a*b - 1/2*c + 1/6*sqrt(-1/3*a^2*b^2 + 4/3*b^3 + 2/3*(2*a^3 - 9*a*b)*c + 9*c^2))^(1/3) - 1/2*(-1/27*a^3 + 1/6*a*b - 1/2*c + 1/6*sqrt(-1/3*a^2*b^2 + 4/3*b^3 + 2/3*(2*a^3 - 9*a*b)*c + 9*c^2))^(1/3)*(-I*sqrt(3) + 1) - 1/3*a}, {x: -1/3*a + 1/9*(a^2 - 3*b)/(-1/27*a^3 + 1/6*a*b - 1/2*c + 1/6*sqrt(-1/3*a^2*b^2 + 4/3*b^3 + 2/3*(2*a^3 - 9*a*b)*c + 9*c^2))^(1/3) + (-1/27*a^3 + 1/6*a*b - 1/2*c + 1/6*sqrt(-1/3*a^2*b^2 + 4/3*b^3 + 2/3*(2*a^3 - 9*a*b)*c + 9*c^2))^(1/3)}]

Με πρώτη ματιά, οι τύποι δείχνουν αρκετά περίπλοκοι. Ας ελέγξουμε λοιπόν ότι το αποτέλεσμα που μας έδωσε το Sage είναι πράγματι σωστό, θέτοντας συγκεκριμένες απλές τιμές στις παραμέτρους a,b,c, για παράδειγμα, a=1, b=2, c=3.
Υπενθυμίζουμε ότι η Python μας επιτρέπει να θέτουμε τιμές ταυτόχρονα ως εξής:

In [85]:
(a,b,c) = (1,2,3)
In [86]:
print a, b, c
1 2 3
In [87]:
print p
a*x^2 + x^3 + b*x + c
In [88]:
print s[0]
{x: -1/18*(a^2 - 3*b)*(-I*sqrt(3) + 1)/(-1/27*a^3 + 1/6*a*b - 1/2*c + 1/6*sqrt(-1/3*a^2*b^2 + 4/3*b^3 + 2/3*(2*a^3 - 9*a*b)*c + 9*c^2))^(1/3) - 1/2*(-1/27*a^3 + 1/6*a*b - 1/2*c + 1/6*sqrt(-1/3*a^2*b^2 + 4/3*b^3 + 2/3*(2*a^3 - 9*a*b)*c + 9*c^2))^(1/3)*(I*sqrt(3) + 1) - 1/3*a}

Όπως παρατηρούμε το αποτέλεσμα δεν είναι αυτό που αναμέναμε. Τόσο το πολυώνυμο p, όσο και οι λύσεις εξακολουθούν να είναι σε συμβολική μορφή. Ίσως κάποιος να δοκίμαζε να ξανατρέξει τον ορισμό του πολυωνύμου p με τις τρέχοντες τιμές των παραμέτρων. Όμως αυτό δεν είναι και τόσο ικανοποιητική λύση, αφού θα μπορούσαμε να έχουμε ορίσει ένα πλήθος από συμβολικές εκφράσεις που να περιείχαν τα a, b, c, οι οποίες μάλιστα να είναι διάσπαρτες στο notebook.
Πως λοιπόν να αναγκάσουμε το πολυώνυμο και τις λύσεις να υπολογισθούν με τις συγκεκριμένες τιμές των a,b,c;
Μια συμβολική έκφραση υπολογίζεται για συγκεκριμένες τιμές των συμβολικών μεταβλητών της, με την παρακάτω εντολή

In [89]:
print p(x=x, a=a, b=b, c=c)
x^3 + x^2 + 2*x + 3
In [90]:
s0 = s[0][x](x=x, a=a, b=b, c=c); print s0
-1/2*(I*sqrt(3) + 1)*(5/6*sqrt(7/3) - 65/54)^(1/3) + 5/18*(-I*sqrt(3) + 1)/(5/6*sqrt(7/3) - 65/54)^(1/3) - 1/3

Τώρα μάλιστα! Μπορούμε να δούμε και το πολυώνυμο και μια ρίζα του, υπολογισμένα για την συγκεκριμένη επιλογή των παραμέτρων. Επιπλέον, τώρα υπάρχει τρόπος και να υπολογίσουμε το πολυώνυμο p, όπου x να είναι η τιμή μιας ρίζας!!

In [91]:
print p(x=s0,a=a,b=b,c=c)
-1/5832*(9*(I*sqrt(3) + 1)*(5/6*sqrt(7/3) - 65/54)^(1/3) - 5*(-I*sqrt(3) + 1)/(5/6*sqrt(7/3) - 65/54)^(1/3) + 6)^3 + 1/324*(9*(I*sqrt(3) + 1)*(5/6*sqrt(7/3) - 65/54)^(1/3) - 5*(-I*sqrt(3) + 1)/(5/6*sqrt(7/3) - 65/54)^(1/3) + 6)^2 - (I*sqrt(3) + 1)*(5/6*sqrt(7/3) - 65/54)^(1/3) + 5/9*(-I*sqrt(3) + 1)/(5/6*sqrt(7/3) - 65/54)^(1/3) + 7/3

Για να ελέγξουμε αν ο αριθμός αυτός είναι πράγματι μηδέν, βρίσκουμε την αριθμητική του τιμή

In [92]:
print n(p(x=s0,a=a,b=b,c=c))
1.88737914186277e-15 - 4.44089209850063e-16*I

Παρατηρήστε ότι τόσο το πραγματικό όσο και το φαναταστικό μέρος του προηγούμενου μιγαδικού αριθμού είναι πάρα πολύ μικροί αριθμοί, της τάξης $10^{-15}$ και $10^{-16}$, αντίστοιχα, το οποίο σημαίνει ότι είναι κοντά στο μηδέν με ακρίβεια που εκτελεί ο υπολογιστής μας.

1.7.3 Αναφορικές και κοινόχρηστες τιμές

Επαναφέρουμε όλες τις τιμές μας στην αρχική τους κατάσταση με την συνάρτηση reset(), και τρέχουμε

In [93]:
reset()
var('x, y, z')
x=y
y=z
z=3
print x, y, z
y z 3

δηλαδή η x αναφέρεται στην y, η y αναφέρεται στην z, και η z αναφέρεται στο 3. Μπορούμε να ανιχνεύσουμε τις αναφορικές αυτές τιμές με την εντολή eval(). Η εντολή αυτή δέχεται ως όρισμα ένα string. Με διαδοχικές χρήσεις της eval() μπορούμε να φτάσουμε από το x μέχρι το 3

In [94]:
ex = eval(str(x)); print ex
ey = eval(str(ex)); print ey
print eval(str(eval(str(x))))
z
3
3

Η πρώτη χρήση της eval() μας δίνει z, ενώ η δεύτερη και η τρίτη εφαρμογή της μας δίνει 3. Παρατηρήστε ότι η σειρά που γίνεται η ανάθεση τιμών σε μεταβλητές παρουσιάζει διαφοροποιήσεις.

In [95]:
reset()
var('x, y, z')
z=3
y=z
x=y
print x, y, z
3 3 3

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

In [96]:
reset()
var('x, y, z')
z= 3
y= 'z'
x= 'y'
print x, y, z
y z 3

1.8 Τύποι δεδομένων και δομές

Κάθε αντικείμενο στο Sage έχει έναν τύπο. Ο τύπος ενός αντικειμένου καθορίζει τι είδους χειρισμοί μπορούν να εφαρμοσθούν στο αντικείμενο. Οι κύριοι τύποι δεδομένων στην Python είναι οι εξής: lists, dictionaries και tuples.


Οι κύριοι τύποι αριθμών στο Sage είναι οι ακέραιοι, οι ρητοί, οι πραγματικοί κι οι μιγαδικοί και έχουν τις συντομεύσεις ZZ, QQ, RR και CC, αντίστοιχα. Στην παράγραφο αυτή θα δούμε πως μπορούμε να περιορίζουμε τον τύπο ενός αριθμού, και πως μπορούμε να διαλέξουμε έναν τυχαίο αριθμό το οποίο είναι αρκετά χρήσιμο. Επίσης θα δούμε πως μπορούμε να επιλέξουμε κάποιο από τα δυο μέλη μιας εξίσωσης.

1.8.1 Περιορισμός στους βασικούς τύπους αριθμών

Οι κύριοι τύποι αριθμών στο Sage είναι οι ακέραιοι, οι ρητοί, οι πραγματικοί κι οι μιγαδικοί και έχουν τις συντομεύσεις ZZ, QQ, RR και CC, αντίστοιχα.

In [97]:
print ZZ
Integer Ring

Μπορούμε να μετατρέψουμε ένα string από 16αδική ή 8δική μορφή, σε δεκαδική μορφή

In [98]:
a = ZZ('0x10'); print a
b = ZZ('010'); print b
16
8

Δοσμένης μιας λίστας συντελεστών, μπορούμε να βρούμε την τιμή οποιουδήποτε αριθμού, σε κάθε βάση.

In [99]:
c = ZZ(range(10), base=10); print c
d = ZZ(range(10), base=3); print d
9876543210
250959

Ο αριθμός 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, δηλαδή το σώμα των ρητών αριθμών

In [100]:
print QQ
x = numerical_approx(pi, digits=20)
y = QQ(x); print y
Rational Field
21053343141/6701487259

Δεν μπορούμε άμεσα να περιoρίσουμε το pi σε έναν ρητό, γιατί

In [101]:
z = RR(y); print z
print QQ(z)
3.14159265358979
245850922/78256779

Παρατηρήστε την διαφορά μεταξύ της τιμής 21053343141/6701487259 του y, και της τιμής 245850922/78256779 του QQ(RR(y)). Η διαφοροποίηση οφείλεται στο ότι η ακρίβεια του RR είναι η ίδια με αυτή των 53 bits (αποθηκεύονται 52) ενός επεξεργαστή που εκτελεί πράξεις διπλής κινητής υποδιαστολής.

In [102]:
print RR
print RDF
print RR == RDF
Real Field with 53 bits of precision
Real Double Field
False

Αν και το RR έχει ακρίβεια 53 bits, η τελευταία δεν είναι η ίδια με αυτή του RealDoubleField (RDF). Η διαφορά αυτή γίνεται αντιληπτή γεννώντας έναν τυχαίο αριθμό στα σώματα RR και RDF αντίστοιχα

In [103]:
x = RR.random_element(); print x, type(x)
y = RDF.random_element(); print y, type(y)
-0.279272246012211 <type 'sage.rings.real_mpfr.RealNumber'>
-0.100211279974 <type 'sage.rings.real_double.RealDoubleElement'>

Ο τύπος του x είναι sage.rings.real_mpfr.RealNumber, ενώ του y είναι sage.rings.real_double.RealDoubleElement. Η ίδια διαφορά διατηρείται και για τους μιγαδικούς

In [104]:
x = CC.random_element(); print x, type(x)
y = CDF.random_element(); print y, type(y)
-0.641974472817350 - 0.155632078593336*I <type 'sage.rings.complex_number.ComplexNumber'>
-0.871544587945 + 0.950657873775*I <type 'sage.rings.complex_double.ComplexDoubleElement'>

1.8.2 Μέλη εξισώσεων

Συχνά δουλεύουμε με εξισώσεις

In [105]:
reset()
eqn = x^2 + 3*x + 2 == 0
print type(eqn)
<type 'sage.symbolic.expression.Expression'>

Ο τύπος της εξίσωσης είναι sage.symbolic.expression.Expression, δηλαδή μια συμβολική έκφραση. Η έκφραση που δηλώσαμε με eqn έχει έναν χειριστή (operator)

In [106]:
print eqn.operator()
<built-in function eq>

Στο Sage επιλέγουμε το αριστερό και το δεξί μέλος της εξίσωσης, αντίστοιχα, ως εξής:

In [107]:
print eqn.lhs()
x^2 + 3*x + 2
In [108]:
print eqn.rhs()
0

Εναλλακτικές εντολές της lhs(), είναι η left() και left_hand_side(), ενώ της εντολής rhs(), είναι οι right() και right_hand_side(), αντίστοιχα.

1.8.3 Αποθήκευση δεδομένων με συναρτήσεις

Το επόμενο παράδειγμα είναι από το βιβλίο του πρωτεργάτη του Sage, William Stein, με τίτλο Sage for Power Users. Στο Sage μπορούμε να αποθηκεύουμε έμμεσες αναφορές για συμβολικά αντικείμενα χρησιμοποιώντας συναρτήσεις (functions). Για παράδειγμα:

In [109]:
def our_append(item, L=[]):
    L.append(item)
    print L
In [110]:
our_append(1/3)
our_append('1/3')
our_append(1.0/3)
[1/3]
[1/3, '1/3']
[1/3, '1/3', 0.333333333333333]

Για να ανιχνεύσουμε τι συμβαίνει με την συνάρτηση our_append) που ορίσαμε, ας την τροποποιήσουμε ελαφρώς, με την our_append2), στην οποία τυπώνουμε επιπλέον την ταυτότητα του L

In [111]:
def our_append2(item, L=[]):
    L.append(item)
    print L, id(L)
    return id(L)
In [112]:
idL = our_append2(1/3)
idL = our_append2('1/3')
idL = our_append2(1.0/3)
[1/3] 140310394115928
[1/3, '1/3'] 140310394115928
[1/3, '1/3', 0.333333333333333] 140310394115928

Την πρώτη φορά που καλέσαμε την συνάρτηση our_append2 δημιουργήθηκε μια άδεια λίστα L = [ ], η οποία τοποθετήθηκε κάπου στην μνήμη. Κάθε φορά που καλείται η συνάρτηση με κάποιο όρισμα, το Sage ανατρέχει στην L, στην ίδια διεύθυνση στην μνήμη. Παρατηρήστε ότι η L δεν υπάρχει έξω από την συνάρτηση!

In [113]:
print L
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
/home/tasos/sage-7.5.1/local/lib/python2.7/site-packages/sage/all_cmdline.pyc in <module>()
----> 1 print L

NameError: name 'L' is not defined

Με την βιβλιοθήκη ctypes μπορούμε να ανακτούμε την διεύθυνση στην οποία είναι τοποθετημένο ένα αντικείμενο

In [114]:
id = our_append2(0)
import ctypes
print ctypes.cast(idL, ctypes.py_object).value
[1/3, '1/3', 0.333333333333333, 0] 140310394115928
[1/3, '1/3', 0.333333333333333, 0]

1.8.3 Δέντρα συμβολικών εκφράσεων

Σε αυτή την παράγραφο θα δούμε πως είναι η εσωτερική δομή εκφράσεων στο Sage σε μεγαλύτερο βάθος

In [115]:
from sage.ext.fast_callable import ExpressionTreeBuilder
etb = ExpressionTreeBuilder(vars=['x','y'])
x = etb.var('x')
y = etb.var('y')
print x+y
add(v_0, v_1)
In [116]:
print x-y
print x*y
print x / y
print x^y
sub(v_0, v_1)
mul(v_0, v_1)
div(v_0, v_1)
pow(v_0, v_1)

Επιβάλλαμε στις μεταβλητές x,y να αλλάξουν τύπο και να γίνουν fast_callable

In [117]:
s = x + y; print type(s)
<type 'sage.ext.fast_callable.ExpressionCall'>
In [118]:
p = x^3 + 4*x*y^2 - 7*y + 2
print p
add(sub(add(ipow(v_0, 3), mul(mul(4, v_0), ipow(v_1, 2))), mul(7, v_1)), 2)

Με βάση την προηγούμενη έκφραση του πολυωνύμου p σε δυο μεταβλητές x,y, μπορούμε να φτιάξουμε το παρακάτω δέντρο.

add
 |
 +-- sub
 |    |
 |    +-- add
 |    |    |
 |    |    +-- ipow
 |    |    |    |
 |    |    |    +-- v_0
 |    |    |    |
 |    |    |    +-- 3
 |    |    |
 |    |    +-- mul
 |    |         |
 |    |         +-- mul
 |    |         |    |
 |    |         |    +-- 4
 |    |         |    |
 |    |         |    +-- v_0
 |    |         |
 |    |         +-- ipow
 |    |              |
 |    |              +-- v_1
 |    |              |
 |    |              +-- 2
 |    |
 |    +-- mul
 |         |
 |         +-- 7
 |         |
 |         +-- v_1
 |
 +-- 2