12/6/11

Η ακολουθία Fibonacci




Στα μαθηματικά η ακολουθία Fibonacci είναι η παρακάτω ακολουθία αριθμών:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ..
Εξ ορισμού οι δύο πρώτοι όροι της ακολουθίας είναι το 0 και το 1, ενώ κάθε επόμενος αριθμός ισούται με το άθροισμα των δύο προηγούμενων όρων. Στη μαθηματική ορολογία οι όροι της ακολουθίας ορίζονται από τον εξής αναδρομικό τύπο:
\,F_n=F_{n-1}+F_{n-2}
με \,F_0=0 και \,F_1=1.


Προέλευση
Η ακολουθία πήρε το όνομα της από τον Λεονάρντο της Πίζας, ή αλλιώς γνωστός και ως Fibonacci. Ο Fibonacci εισήγαγε την ακολουθία στη Δυτική Ευρώπη το 1202, στο βιβλίο του "Liber Abaci" ή "Βιβλίο των υπολογισμών" ένα βιβλίο γεμάτο με τις μαθηματικές γνώσεις που είχε περισυλλέξει στα ταξίδια του αν και η ακολουθία τελικά ήταν γνωστή ήδη από τα Ινδικά μαθηματικά. Στο βιβλίο του η ακολουθία έχει ως πρώτο όρο το 1, δηλαδή παραλείπεται το 0. Στα Ινδικά μαθηματικά η ακολουθία εμφανίζεται σε σύνδεση με την προσωδία και τον επιτονισμό της γλώσσας των Σανσκρίτ. Στη σανσκριτική προφορική και γλωσσική παράδοση κυρίως στην ποίηση, υπήρξε πολλή έμφαση στο πόσο χρονικό διάστημα μεγάλες(σε διάρκεια) συλλαβές αναμειγνύονται με τις σύντομες. Η μέτρηση των διάφορων μοντέλων που εμφανίζονταν στο "μήκος" των συλλαβών μέσα σε συγκεκριμένο διάστημα είχαν ως αποτέλεσμα  τους αριθμούς Fibonacci. Στη Δύση ο Fibonacci παρομοιάζει και παρουσιάζει την ακολουθία με το εξής πρόβλημα αναπαραγωγής λαγών:  
Ένα πρόσφατα γεννημένο ζευγάρι κουνελιών, ένα αρσενικό και ένα θηλυκό, τοποθετείτε σε μία φάρμα. Τα κουνέλια είναι σε θέση να ζευγαρώσουν στην ηλικία του ενός μηνός, έτσι ώστε στο τέλος του δεύτερου μήνα, ένα θηλυκό να μπορεί να αναπαράγει άλλο ένα ζεύγος κουνελιών. Τα κουνέλια δε θα πεθαίνουν ποτέ και ένα ζευγάρι παράγει πάντα ένα νέο ζευγάρι(ένα αρσενικό και ένα θηλυκό) κάθε μήνα ξεκινώντας από το δεύτερο μήνα. Το πρόβλημα, το οποίο θέτει Fibonacci ήταν: πόσα ζευγάρια θα υπάρχουν σε ένα χρόνο; Η ονομασία "ακολουθία Fibonacci" χρησιμοποιήθηκε για πρώτη φορά τον 19ο αιώνα από τον μαθηματικό Édouard Lucas.
 
Εφαρμογές
Η ακολουθία Fibonacci έχει συνδεθεί με την Χρυσή Τομή. Το πηλίκο δύο διαδοχικών όρων τείνει στη χρυσή τομή. Η ακολουθία μάλιστα έχει και πολλές σημαντικές εφαρμογές σε  δομές δεδομένων όπως οι Σωροί Φιμπονάτσι(Fibonacci heap), ή αλγορίθμους προγραμματισμού όπως η Μέθοδος Αναζήτησης Φιμπονάτσι(Fibonacci search technique) αλλά και γραφήματα(κύβοι/υπερκύβοι Φιμπονάτσι) που χρησιμοποιούνται στην τοπολογία δικτύων και στον παράλληλο προγραμματισμό.


Άλλες εφαρμογές στον προγραμματισμό: 
- Οι αριθμοί Fibonacci είναι σημαντικοί για την υπολογιστική ανάλυση του χρόνου εκτέλεσης του αλγορίθμου του Ευκλείδη για τον καθορισμό του μέγιστο κοινό διαιρέτη δύο ακεραίων:. η χειρότερη περίπτωση για αυτόν τον αλγόριθμο είναι η εισαγωγή ενός ζεύγους διαδοχικών αριθμών Fibonacci.
- Ο Yuri Matiyasevich κατάφερε να αποδείξει ότι οι αριθμοί Fibonacci είναι δυνατόν να ορίζονται από μια Διοφαντική εξίσωση, η οποία οδήγησε στην αρχική λύση του το δέκατου πρόβληματος του Hilbert.
- Οι αριθμοί Fibonacci είναι επίσης ένα παράδειγμα μιας πλήρους ακολουθίας. Αυτό σημαίνει ότι κάθε θετικός ακέραιος μπορεί να γραφεί ως άθροισμα των αριθμών Fibonacci, όπου κάθε ένας αριθμός θα χρησιμοποιηθεί το πολύ μία φορά. Συγκεκριμένα, κάθε θετικός ακέραιος μπορεί να γραφεί με έναν μοναδικό τρόπο ενός ή περισσοτέρων διακριτών αριθμών Fibonacci με τέτοιο τρόπο ώστε να μην περιλαμβάνει δύο διαδοχικών αριθμών Fibonacci. Αυτό είναι γνωστό και ως Θεώρημα Zeckendorf.
- Οι αριθμοί Fibonacci χρησιμοποιούνται από ορισμένες γεννήτριες (ψευδο)τυχαίων αριθμών ή αλλιώς pseudorandom number generator (PRNG).

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

Η συμβολή της ακολουθίας Fibonacci επεκτείνετε και στην τέχνη. Στην αρχιτεκτονική κτιρίων(Eden Project), ενώ έχει υπάρξει αντικείμενο έμπνευσης για πολλούς καλλιτέχνες στη Μουσική(Krzysztof Meyer), στον Κινηματογράφο(Pi, The Da Vinci Code, 21), στη Λογοτεχνία(The Da Vinci Code, The Wright 3, Decipher), στην τηλεόραση, σε ψηφιακά εφέ και σε κόμικ.

1 σχόλιο: