Ακολουθία Φιμπονάτσι

Στα Μαθηματικά, οι Αριθμοί Φιμπονάτσι είναι οι αριθμοί της παρακάτω ακέραιας ακολουθίας:

Εξ ορισμού, οι πρώτοι δύο αριθμοί Φιμπονάτσι είναι το 0 και το 1, και κάθε επόμενος αριθμός είναι το άθροισμα των δύο προηγούμενων.

Σε μαθηματικούς όρους, η ακολουθία Fn των αριθμών Φιμπονάτσι ορίζεται από τον αναδρομικό τύπο:

με και . [1]

Η Ακολουθία Φιμπονάτσι ονομάστηκε έτσι από τον Λεονάρντο της Πίζας, γνωστό και ως Φιμπονάτσι. Το βιβλίο του Φιμπονάτσι, το 1202, με τίτλο Liber Abaci, εισήγαγε την ακολουθία στα Μαθηματικά της Δυτικής Ευρώπης,[2] αν και η ακολουθία είχε περιγραφεί πιο πριν από τους Ινδούς.[3][4][5] (Κατά μία πιο σύγχρονη σύμβαση, η ακολουθία ξεκινάει με F0=0. Στο Liber Abaci, όμως, η ακολουθία ξεκινάει με F1=1, παραλείποντας το αρχικό 0, κάτι που ακολουθείται από κάποιους ακόμη και σήμερα).

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

Ιστορία

Η Ακολουθία Φιμπονάτσι εμφανίζεται στα Μαθηματικά των Ινδών και συγκεκριμένα σε Σανσκριτικές Προσωδίες.[4] Στην Σανσκριτική προφορική παράδοση, δίνονταν μεγάλη έμφαση κατά πόσο οι μακρόσυρτες συλλαβές (Μ) συνέπιπταν με τις σύντομες (Σ), και μετρούσαν τα διαφορετικά πρότυπα των Μ και των Σ μέσα σε ένα προκαθορισμένο διάστημα, κάτι που οδήγησε στους αριθμούς Φιμπονάτσι. Ο αριθμός των προτύπων που γίνονται m σύντομες συλλαβές μακρόσυρτες είναι ο αριθμός Φιμπονάτσι Fm+1.[5]

Η ανάπτυξη τη ακολουθίας αποδίδεται στον Pingala (200 π.Χ.), αλλά η πρώτη ξεκάθαρη αναφορά στην Ακολουθία γίνεται στα έργα του Virahanka (700 μ.Χ.), τα έργα του οποίου δε σώζονται, αλλά μεταφέρθηκαν αυτούσια στα έργα του Gopala (1153 μ.Χ.).

Liber abbaci magliab f124r
Μία από τις σελίδες του βιβλίου Liber Abaci του Φιμπονάτσι όπου περιέχεται η συγκεκριμένη ακολουθία.

Στη Δύση, οι αριθμοί Φιμπονάτσι εμφανίζονται για πρώτη φορά στο βιβλίο Liber Abaci (1202) του Λεονάρντο της Πίζας, γνωστού και ως Φιμπονάτσι.[2] Ο Φιμπονάτσι παίρνει ως δεδομένο ένα ιδανικό πληθυσμό κουνελιών και κάνει τις εξής υποθέσεις: έχουμε ένα νεογέννητο ζευγάρι κουνελιών (αρσενικό και θηλυκό) σε ένα χωράφι, τα κουνέλια είναι σε θέση να ζευγαρώσουν σε ηλικία ενός μήνα από τη γέννησή τους, έτσι ώστε στο τέλος του δεύτερου μήνα το θηλυκό να μπορεί να γεννήσει ένα ζευγάρι κουνελιών, τα κουνέλια δε πεθαίνουν ποτέ και κάθε ζευγάρι κουνελιών γεννάει ένα νέο ζευγάρι (ένα αρσενικό και ένα θηλυκό) κάθε μήνα από τον δεύτερο μήνα και μετά. Το ερώτημα που έθεσε ο Φιμπονάτσι ήταν: πόσα ζεύγη κουνελιών θα έχουν γεννηθεί μέσα σε ένα έτος;

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

Στο τέλος του νιοστού μήνα, το πλήθος των ζευγών των κουνελιών είναι ίσος με το πλήθος των νέων ζεύγων (n-2) προσθέτοντας το πλήθος ζεύγων που υπήρχαν στο χωράφι τον προηγούμενο μήνα (n-1). Αυτός είναι ο νιοστός αριθμός Φιμπονάτσι.[6]

Ο Leonardo de Pisa ή Fibonacci έζησε κοντά στην πόλη της Bejaia, η οποία αποτελούσε ένα σημαντικό εξαγωγέα κεριού την εποχή του Fibonacci (από εκεί προέρχεται και η γαλλική εκδοχή του ονόματος της πόλης αυτής, “bougie”, που σημαίνει" κερί "στα γαλλικά). Μια πρόσφατη μαθηματικο-ιστορική ανάλυση της περιόδου και της περιοχής στην οποία έζησε ο Fibonacci προτείνει ότι στην πραγματικότητα οι μελισσοκόμοι της Bejaia και οι γνώσεις τους σχετικά με την αναπαραγωγή των μελισσών αποτέλεσαν την πηγή έμπνευσης της ακολουθίας Fibonacci και όχι το ευρύτερα ίσως γνωστό μοντέλο της αναπαραγωγής κουνελιών.[7].

Ο όρος «Ακολουθία Φιμπονάτσι» χρησιμοποιήθηκε για πρώτη φορά τον 19ο αιώνα από τον Γάλλο μαθηματικό Εδουάρδο Λούκας. [8]

Λίστα των Αριθμών Φιμπονάτσι

Οι πρώτοι 21 αριθμοί Φιμπονάτσι Fn για n= 0, 1, 2, …, 20 είναι: [9]

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19 F20
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Η ακολουθία μπορεί να επεκταθεί και σε αρνητικό δείκτη n χρησιμοποιώτας αναδιαταγμένη την αναδρομική σχέση

που παράγει την ακολουθία των αρνητικών αριθμών Φιμπονάτσι και ικανοποιεί τη σχέση: [10]

Οπότε η πλήρης ακολουθία είναι η εξής:

F−8 F−7 F−6 F−5 F−4 F−3 F−2 F−1 F0 F1 F2 F3 F4 F5 F6 F7 F8
−21 13 −8 5 −3 2 −1 1 0 1 1 2 3 5 8 13 21

Συνάφεια με τη Χρυσή Αναλογία

Έκφραση Κλειστής Μορφής

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

όπου

είναι η χρυσή αναλογία, και

[11]

Για να το δούμε αυτό,[12] θα πρέπει το φ και το ψ να είναι και τα δύο λύσεις της εξίσωσης

οπότε οι δυνάμει των φ και ψ ικανοποιούν την αναδρομική σχέση Φιμπονάτσι. Δηλαδή

και

Αυτό ισχύει για κάθε τιμή των a και b και η ακολουθία ορίζεται από

και ικανοποιεί την ίδια αναδρομική σχέση

Εάν a και b επιλεγούν έτσι ώστε U0 = 0 και U1 = 1 τότε η ακολουθία Unπου προκύπτει είναι η ακολουθία Φιμπονάτσι. Αυτό είναι το ίδιο αν απαιτήσουμε τα a και b να ικανοποιούν το παρακάτω σύστημα εξισώσεων:

το οποίο έχει λύση

και παράγει την απαιτούμενη φόρμουλα.

Υπολογισμός με στρογγυλοποίηση

Εάν

για κάθε n ≥ 0, ο αριθμός Fn είναι ο κοντινότερος ακέραιος του

Επομένως μπορεί να βρεθεί στρογγυλοποιώντας

Ομοίως, εάν ήδη γνωρίζουμε ότι ο αριθμός F > 1 είναι αριθμός Φιμπονάτσι, μπορούμε να προσδιορίσουμε το δείκτη του μέσα στην ακολουθία με

Όριο συνεχόμενων πηλίκων

Ο Γιοχάνες Κέπλερ παρατήρησε ότι η αναλογία συνεχόμενων αριθμών Φιμπονάτσι συγκλίνει. Συγκεκριμένα έγραψε ότι "ότι είναι το 5 για το 8 είναι το 8 για το 13, πρακτικά, ότι είναι το 8 για το 13, είναι το 13 για το 21 σχεδόν" και κατέληξε ότι το όριο τείνει στη χρυσή αναλογία .[13]

Η σύγκλιση αυτή δεν εξαρτάται από τις αρχικές τιμές, εξαιρώντας το 0, 0. Για παράδειγμα, οι αρχικές τιμές 19 και 31 παράγουν την ακολουθία 19, 31, 50, 81, 131, 212, 343, 555 ... κλπ. Η αναλογία συνεχόμενων όρων σε αυτή την ακολουθία παρουσιάζει την ίδια σύγκλιση προς τη χρυσή αναλογία.

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

Ανάλυση δυνάμεων της χρυσής αναλογίας

Εφόσον η χρυσή αναλογία ικανοποιεί την εξίσωση

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

Η έκφραση αυτή είναι αληθής και για εάν η ακολουθία Φιμπονάτσι επεκταθεί και σε αρνητικούς ακέραιους χρησιμοποιώντας τη σχέση

Πίνακες

Ένα σύστημα διαφορικών εξισώσεων δύο διαστάσεων που περιγράφει την ακολουθία Φιμπονάτσι είναι το εξής:

ή

Οι ιδιοτιμές του πίνακα Α είναι και , και τα ιδιοδιανύσματά του A, και , είναι σε αναλογίες και Έχοντας αυτά τα στοιχεία, και τις ιδιότητες των ιδιοτιμών, μπορούμε να βρούμε τη φόρμουλα του n-οστού στοιχείου στην ακόλουθη σειρά Φιμπονάτσι:

Ο πίνακας έχει ορίζουσα -1, οπότε έχουμε έναν 2x2 πίνακα. Αυτό μπορεί να γίνει κατανοητό από το διαδοχικό κλάσμα της χρυσής αναλογίας:

Οι αριθμοί Φιμπονάτσι προκύπτουν από τα διαδοχικά πηλίκα του διαδοχικού κλάσματος της χρυσής αναλογίας , και ο πίνακας δημιουργείται από τα διαδοχικά πηλίκα οποιουδήποτε διαδοχικού κλάσματος που έχει ορίζουσα +1 ή -1.

Η αναπαράσταση σε πίνακα δίνει την ακόλουθη κλειστή έκφραση των αριθμών Φιμπονάτσι:

Παίρνοντας τις ορίζουσες και των δύο μερών προκύπτει η ταυτότητα του Κασίνι

Επιπρόσθετα, αν για κάθε τετραγωνικό πίνακα A, προκύπτουν οι ακόλουθες ταυτότητες:

Ιδιαίτερα, αν ,

Αναγνώριση αριθμών Φιμπονάτσι

Το ερώτημα που προκύπτει είναι αν ένας θετικός ακέραιος αριθμός z είναι αριθμός Φιμπονάτσι. Εφόσον είναι ο πιο κοντινός ακέραιος του , η πιο άμεση δοκιμή είναι η ταυτότητα:

Μία συνέπεια της παραπάνω σχέσης είναι ότι αν είναι γνωστό ότι ένας αριθμός z είναι αριθμός Φιμπονάτσι, μπορούμε να προσδιορίσουμε το n έτσι ώστε F(n) = z με το ακόλουθο:

Εναλλακτικά, ένας ακέραιος αριθμός z είναι αριθμός Φιμπονάτσι αν και μόνο αν μία από τις σχέσεις ή είναι τέλειο τετράγωνο.[14]

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

(με coprime ακέραιους αριθμούς p, q) είναι αληθής αν και μόνο αν τα p και q είναι διαδοχικοί αριθμοί Φιμπονάτσι. Από αυτό προκύπτει το κριτήριο ότι ο z είναι αριθμός Φιμποινάτσι αν και μόνο αν το κλειστό διάστημα

περιέχει έναν θετικό ακέραιο.[15] Για , είναι εύκολο να δείξουμε ότι αυτό το διάστημα περιέχει το πολύ έναν ακέραιο, και στην περίπτωση που το z είναι αριθμός Φιμπονάτσι, ο ακέραιος αυτός είναι ίσος με τον επόμενο διαδοχικό αριθμό Φιμπονάτσι μετά το z. Είναι εντυπωσιακό, ότι αυτό το αποτέλεσμα ισχύει και για την περίπτωση , αλλά θα πρέπει να δηλωθεί επακριβώς γιατί το 1 εμφανίζεται δύο φορές στην ακολουθία Φιμπονάτσι και έχει δύο διαφορετικούς διαδοχικούς επόμενους αριθμούς στην ακολουθία.

Δείτε επίσης

Σημειώσεις

  1. Lucas p. 3
  2. 2,0 2,1 Sigler, Laurence E. (trans.) (2002). Fibonacci's Liber Abaci. Springer-Verlag. ISBN 0-387-95419-8. Chapter II.12, pp. 404–405.
  3. Susantha Goonatilake (1998). Toward a Global Science. Indiana University Press. σελ. 126. ISBN 9780253333889.
  4. 4,0 4,1 Singh, Parmanand (1985). «The So-called Fibonacci numbers in ancient and medieval India». Historia Mathematica 12 (3): 229–244. doi:10.1016/0315-0860(85)90021-7.
  5. 5,0 5,1 Donald Knuth (2006). The Art of Computer Programming: Generating All Trees—History of Combinatorial Generation; Volume 4. Addison–Wesley. σελ. 50. ISBN 9780321335708.
  6. Knott, Ron. «Fibonacci's Rabbits». University of Surrey Faculty of Engineering and Physical Sciences.
  7. Scott, T.C.; Marketos, P. (March, 2014), On the Origin of the Fibonacci Sequence, MacTutor History of Mathematics archive, University of St Andrews, http://www-history.mcs.st-andrews.ac.uk/Publications/fibonacci.pdf
  8. Martin Gardner (1996). Mathematical Circus. The Mathematical Association of America. ISBN 0883855062. p.133
  9. Η ιστοσελίδα [1] έχεις τους πρώτους 300 Fn και περισσότερες πληροφορίες.
  10. Knuth, Donald. "Negafibonacci Numbers and the Hyperbolic Plane" Εργασία που παρουσιάστηκε στα πλαίσια της Ετήσιας Συνάντησης της Mathematical Association of America, The Fairmont Hotel, San Jose, CA. 2008-12-11 <http://www.allacademic.com/meta/p206842_index.html>
  11. Ball p. 156
  12. Following Ball p. 155-156
  13. Kepler, Johannes (1966). A New Year Gift: On Hexagonal Snow. Oxford University Press. σελ. 92. ISBN 0198581203. Strena seu de Nive Sexangula (1611).
  14. Posamentier, Alfred (2007). The (Fabulous) FIBONACCI Numbers. Prometheus Books. σελ. 305. ISBN 978-1-59102-475-0. Unknown parameter |coauthors= ignored (|author= suggested) (βοήθεια)
  15. M. Möbius, Wie erkennt man eine Fibonacci Zahl?, Math. Semesterber. (1998) 45; 243–246.
1919 (αριθμός)

Το 1919 (χίλια εννεακόσια δέκα εννέα) είναι σύνθετος αριθμός μετά το 1918 και πριν το 1920.

1944 (αριθμός)

Το 1944 (χίλια εννεακόσια σαράντα τέσσερα) είναι σύνθετος αριθμός μετά το 1943 και πριν το 1945.

Scheme

Η Scheme είναι η μια από τις δύο βασικές διαλέκτους της γλώσσας προγραμματισμού Lisp. Σε αντίθεση με την Common Lisp, την άλλη βασική διάλεκτο, η Scheme ακολουθεί μια μινιμαλιστική φιλοσοφία σχεδίασης, ορίζοντας ένα μικρό βασικό πυρήνα με ισχυρά εργαλεία για επέκταση της γλώσσας. Λόγω του μικρού της μεγέθους και της κομψότητάς της είναι δημοφιλής ανάμεσα στους εκπαιδευτικούς, τους σχεδιαστές γλωσσών, τους προγραμματιστές και τους ερασιτέχνες, και αυτή η ευρεία της διάδοση θεωρείται τόσο πλεονέκτημά της, όσο και μειονέκτημα, λόγω της ποικιλίας ανάμεσα στις υλοποιήσεις της.Η Scheme αναπτύχθηκε στο MIT AI Lab του MIT από τον Guy L. Steele και τον Gerald Jay Sussman, οι οποίοι την παρουσίασαν στην ακαδημαϊκή κοινότητα μέσα από μια σειρά σημειωμάτων (memos), τα οποία σήμερα ονομάζονται "Lambda Papers", κατά την περίοδο 1975-1980. Η γλώσσα Scheme προτυποποιήθηκε σε επίσημο πρότυπο της IEEE, και σε ένα ντε φάκτο πρότυπο που ονομάζεται Αναθεωρημένηn Αναφορά πάνω στην Αλγοριθμική Γλώσσα Scheme (Revisedn Report on the Algorithmic Language Scheme ή RnRS). Το πρότυπο που υλοποιείται πιο συχνά είναι το R5RS (1998), και το 2007 αναγνωρίστηκε το νέο πρότυπο R6RS.Η Scheme ήταν η πρώτη διάλεκτος της Lisp που επέλεξε τη λεκτική εμβέλεια και η πρώτη που απαίτησε από τις υλοποιήσεις της να κάνουν βελτιστοποίηση κλήσης ουράς (tail-call optimization). Ήταν επίσης μια από τις πρώτες γλώσσες προγραμματισμού που υποστήριξαν συνέχειες πρώτης κλάσης. Επηρέασε σε μεγάλο βαθμό τις προσπάθειες που οδήγησαν στην ανάπτυξη της γλώσσας Common Lisp.

Άλυτα προβλήματα της θεωρίας αριθμών

Τα κλασικά άλυτα προβλήματα της θεωρίας αριθμών παραδοσιακά ήταν τρία:

Η Εικασία του Γκόλντμπαχ: Κάθε άρτιος θετικός ακέραιος μεγαλύτερος του 2 μπορεί να γραφτεί ως άθροισμα δύο πρώτων αριθμών, έτσι ώστε για κάθε n ≧ 2, , όπου p, q πρώτοι αριθμοί. Η υπόθεση του Ρήμαν: Το πραγματικό μέρος κάθε μη τετριμμένης μηδενικής ρίζας της συνάρτησης ζ του Ρήμαν είναι ½. Το τελευταίο Θεώρημα του Φερμά: Δεν υπάρχουν θετικοί ακέραιοι x, y, και z τέτοιοι ώστε , όπου n θετικός ακέραιος μεγαλύτερος του 2.

Σημείωση: Το τελευταίο θεώρημα του Fermat αποδείχθηκε πρόσφατα από τους μαθηματικούς Andrew Wiles και Richard Taylor στο πανεπιστήμιο Princeton.

Άλλα άλυτα προβλήματα της θεωρίας αριθμών είναι:

Ιάννης Ξενάκης

Ο Ιάννης Ξενάκης (29 Μαΐου 1922 – 4 Φεβρουαρίου 2001) ήταν ένας από τους σημαντικότερους Έλληνες συνθέτες και αρχιτέκτονες του 20ού αιώνα, διεθνώς γνωστός ως Iannis Xenakis. Οι πρωτοποριακές συνθετικές μέθοδοι που ανέπτυξε συσχέτιζαν τη μουσική και την αρχιτεκτονική με τα μαθηματικά και τη φυσική, μέσω της χρήσης μοντέλων από τη θεωρία των συνόλων, τη θεωρία των πιθανοτήτων, τη θερμοδυναμική, τη Χρυσή Τομή, την ακολουθία Φιμπονάτσι κ.ά. Παράλληλα, οι φιλοσοφικές του ιδέες για τη μουσική έθεσαν καίρια το αίτημα για ενότητα φιλοσοφίας, επιστήμης και τέχνης, συμβάλλοντας στο γενικότερο προβληματισμό για την κρίση της σύγχρονης ευρωπαϊκής μουσικής των δεκαετιών του 1950 και 1960. Οι ιδέες του θεωρείται ότι υπήρξαν προσκείμενες με τα κομμουνιστικά ιδεώδη.

Λεονάρντο της Πίζας

Ο Λεονάρντο της Πίζας (Σεπτέμβριος 1175 – 1240), γνωστός και ως Λεονάρντο Πιζάνο (Leonardo Pisano) ή Φιμπονάτσι (Fibonacci) ήταν Ιταλός μαθηματικός που έμεινε στην ιστορία για την περίφημη Ακολουθία Φιμπονάτσι και για την εισαγωγή στην Ευρώπη του αραβικού δεκαδικού συστήματος αρίθμησης καθώς και άλλων μαθηματικών καινοτομιών σε μια σκοτεινή εποχή για τις επιστήμες στην Ευρώπη.

Μ-αναδρομική συνάρτηση

Στη μαθηματική λογική και την επιστήμη των υπολογιστών, οι μ-αναδρομικές συναρτήσεις είναι μια κατηγορία μερικών συναρτήσεων από φυσικούς αριθμούς σε φυσικούς αριθμούς που είναι "υπολογίσιμη" σε μια διαισθητική αίσθηση. Στην πραγματικότητα, στη θεωρία υπολογισιμότητας έχει αποδειχθεί ότι οι μ-αναδρομικές συναρτήσεις είναι ακριβώς οι συναρτήσεις που μπορούν να υπολογιστούν από μηχανές Τιούρινγκ. Οι μ-αναδρομικές συναρτήσεις συνδέονται στενά με πρωτόγονες αναδρομικές συναρτήσεις, και ο επαγωγικός ορισμός τους (κάτω) βασίζεται σε αυτές τις πρωτόγονες αναδρομικές συναρτήσεις. Ωστόσο, κάθε μ-αναδρομική συνάρτηση δεν είναι μια πρωτόγονη αναδρομική συνάρτηση—το πιο διάσημο παράδειγμα είναι η συνάρτηση Άκερμαν.

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

Το σύνολο όλων των αναδρομικών συναρτήσεων είναι γνωστό ως R στην θεωρία υπολογιστικής πολυπλοκότητας .

Παράλληλος προγραμματισμός

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

Τα παράλληλα συστήματα διακρίνονται σε πολυεπεξεργαστές κοινής μνήμης, όπου πολλαπλοί επεξεργαστές επικοινωνούν με μία κοινή μνήμη ενιαίου χώρου διευθύνσεων, και σε πολυυπολογιστές κατανεμημένης μνήμης, όπου πολλαπλά πακέτα επεξεργαστή-ιδιωτικής μνήμης, με τον δικό του χώρο διευθύνσεων το καθένα, διασυνδέονται και επικοινωνούν μεταξύ τους· και στις δύο περιπτώσεις η επικοινωνία γίνεται μέσω ενός «δικτύου διασύνδεσης». Τα μοντέλα παράλληλου προγραμματισμού για πολυεπεξεργαστές και πολυυπολογιστές είναι το μοντέλο κοινού χώρου διευθύνσεων (π.χ. πολλαπλές διεργασίες ή νήματα, OpenMP) και το μοντέλο μεταβίβασης μηνυμάτων (π.χ. PVM, MPI), αντιστοίχως. Στο πρώτο οι επεξεργαστικές μονάδες ανταλλάσσουν πληροφορίες προσπελαύνοντας κοινόχρηστες μεταβλητές στην κοινή μνήμη, ενώ στο δεύτερο ανταλλάσσοντας μηνύματα. Κάθε προγραμματιστικό μοντέλο μπορεί να εφαρμοστεί και σε σύστημα μιας αρχιτεκτονικής που δεν είναι η φυσική του (π.χ. πολυνηματικό πρόγραμμα σε πολυυπολογιστή ή πρόγραμμα MPI σε πολυεπεξεργαστή) αλλά συνήθως με χαμηλότερες επιδόσεις.

Άλλες γλώσσες

This page is based on a Wikipedia article written by authors (here).
Text is available under the CC BY-SA 3.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.