| σύντομη περιγραφή: Είμαστε, λοιπόν, στην αρχή της δεύτερης φάσης του μαθήματος. Ανατρέχω τώρα από την αρχή του εξαμήνου ανακοινωμένο και αναρτημένο πρόγραμμα μαθημάτων. Αυτήν την εβδομάδα στο εργαστήριο θα δουλέψουμε σε κάποιες ασκήσεις επανάληξης. Αυτήν την εβδομάδα στο εργαστήριο θα δουλέψουμε σε κάποιες ασκήσεις επανάληξης. Αυτήν την εβδομάδα στο εργαστήριο θα δουλέψουμε σε κάποιες ασκήσεις επανάληξης που μαζί με τα αποτελέσματα του πρώτου θέματος θα μας δώσουν τη δυνατότητα να δούμε και να διαπιστώσουμε τυχόν προβλήματα, τυχόν ελλείψεις μας και να επιχειρήσουμε στον δυνατό τρόπο να καλύψουμε αυτά τα θέματα στο υπόλοιπο του εξαμήνου και της δουλειάς μας. Ταυτόχρονα, από σήμερα θα μπούμε και σε κάποιες καινούργιες έννοιες, οι οποίες ακόμη και για όσους και όσους από εσάς έχετε μια προπαρασκευή σε θέματα προγραμματισμού, είναι θεέλεγα σχετικά καινούργιες και έχουν να κάνουν και με την έννοια της αναδρομικότητας Εβραίος γνωστή βέβαια, αλλά θα δούμε πώς αυτήν νοείται στα πλαίσια ενός υπολογιστικού κώδικα και με την έννοια της πολυπλοκότητας της μαθηματικής ή για να είμαι ακριβής της υπολογιστικής πολυπλοκότητας. Ξεκινώ με το παράδειγμα μιας της ακολουθίας που φέρει ένα όνομα διάσημο θα έλεγα, της ακολουθίας Φιμπονάτσι, να αντλήσω έτσι αντιδράσεις σε ποιους λέει κάτι αυτό το όνομα, σε αρκετούς λέει και σε αρκετούς δεν λέει. Άρα, για να δούμε λοιπόν ποια είναι αυτή η ακολουθία και για ποιον λόγο μας ενδιαφέρει. Είναι μια διάσημη ακολουθία ιδιαίτερα γνωστή για όσους ασχολούνται αρχικά με την κονικλοτροφία. Εκτρέφουν κουνέλια. Έτσι λοιπόν στις απαρχές της αναγέννησης, λίγο πριν ανατείλει ο ήλιος της αναγέννησης επί ευρωπαϊκού εδάφους, την εποχή που τα μαθηματικά μαζί και με όλες τις υπόλοιπες επιστήμες συντηρούνταν αποκλειστές κοινότητες ανθρώπων που είχαν το προνόμιο να έχουν άμεση σχέση με κείμενα των παλαιωτέρων, είτε αυτά ήταν κείμενα των αρχαίων Ελλήνων είτε κείμενα μεταφρασμένα στα λατινικά και βέβαια εκείνη την περίοδο και στα αραβικά μέσω της διήσδυσης των νεοτεριστών Αράβων στην Ιβηρική. Μέσω αυτό λοιπόν των ανθρώπων καλλιεργήθηκαν νέες κατευθύνσεις στα μαθηματικά και στις υπόλοιπες επιστήμες. Ο Φιμπονάτσι ήταν ένας μοναχός λοιπόν ο οποίος ασχολήθηκε ανάμεσα σε άλλα με το πρόβλημα της αναπαραγωγής αυτών των πολύ συμπαθών πλασμάτων, το οποίο είναι ένα ιδιαίτερα γνωστό χαρακτηριστικό, τον πολύ μεγάλο ρυθμό αναπαραγωγής. Γνωρίζουμε δηλαδή ότι ένα ζευγάρι μπορεί να οδηγήσει σε μεγάλους πληθυσμούς. Αυτό απασχόλησε ήδη εκείνη την εποχή και προσπάθησε με έναν πολύ χονδροειδή τρόπο, ομολογό, να βρει μία μέθοδο με τη βοήθεια της οποίας θα μπορούσε να προβλέψει ποιος θα είναι ο αριθμός ο πληθυσμός των ζώων αυτών μετά από έναν χρόνο, εάν κάνουμε τις ακόλουθες παραδοχές. Μπορεί να αναπαραχθεί το ζευγάρι με το που θα γίνει ενός μηνός, πρώτη αφθαίρετη παραδοχή, και ότι κάθε ζευγάρι γεννά ένα ζευγάρι. Δηλαδή το αρσενικό θηλυκό γεννά αρσενικό θηλυκό. Δεν χρειάζεται να πάμε περισσότερο σε βάθος, γιατί προφανώς ήταν πολύ αδραίες και πολύ χονδροειδείς και άραλα χασμένες οι παραδοχές αυτές. Παρ' όλα αυτά όμως, η ακολουθία αριθμών που προέκυψε, το ένα ζευγάρι παράγει άλλο ένα και αυτά τα δύο ζευγάρια θα παράξουν δύο, και μετά τρία, δύο και τρία, πέντε, τρία και πέντε, οχτώ. Αυτή η ακολουθία αριθμών έγινε πάρα πολύ γνωστή για λόγους που προέκυψαν αργότερα. Ήταν λοιπόν ο Λεωνάρντο Πισάνο, ο Λεωνάρντο Φιμπονάτσι, που σημαίνει ο γιος του Μπονάτσι, του Μπονάκιο. 1175-1250 κατεκτίμηση, πρότεινε την ομώνημη ακολουθία στο βιβλίο του «The Book of the Abacus», το βιβλίο του αριθμητηρίου. Τώρα, αυτή η σειρά αριθμών είναι η περίφημη, όντως περίφημη, ακολουθία Θιμπονάτσι και είναι περίφημη για πολλούς λόγους. Θα σας δείξω ένα βίντεο που θα βάλω να παίζει κατά τη διάρκεια του διαλύματος, που θεωρώ ότι πολύ ωραία παρουσιάζει πολλούς από τους λόγους αυτούς. Ένα βασικό χαρακτηριστικό είναι ότι υπάρχει μια προσεγγιστική σχέση, με βάση την οποία μπορούμε να υπολογίσουμε τον ιωστό όρο. Προσεγγιστική σημαίνει στο περίπου. Δηλαδή, ότι αν θέλω τον όρο 110, βάζω σε αυτή τη σχέση, όπου είναι τον αριθμό 110. Και έτσι, λοιπόν, προκύπτει στο περίπου 110 όρους. Για μεγάλες, λοιπόν, τιμές του αριθμού ν, ο ρυθμός ανάπτυξης της ακολουθίας είναι ίσως με μια σταθερά επί 1,618 εις την ν. Και αυτό το 1,618 είναι η περίφημη χρυσή αναλογία. Θα το δούμε και αυτό. Ήδη σας δείχνει ένα διάγραμμα που δείχνει την σχέση αυτή, δηλαδή σε ποιον αριθμό συγκλίνει το κλάσμα του επόμενου προς τον προηγούμενο όρο, καθώς ο αριθμός των όρων μεγαλώνει. Αυτή η χρυσή αναλογία είναι γνωστή και ως ο χρυσός κανόνας. Έτσι, λοιπόν, ένα ορθογώνιο του οποίου οι πλευρές ακολουθούν αυτή τη χρυσή αναλογία, το οποίο μπορούμε να δημιουργήσουμε με τον εξής τρόπο. Έχω ένα οποιοδήποτε τετράγωνο πλευράς b, το χωρίζω στη μέση, διαγώνιος του μέσου με το διαβήτη μου κάτω, αυτό είναι το α, α δια b ίσον με φ, ίσον με 1,618. Είναι η χρυσή αναλογία. Αυτό το ορθογώνιο θεωρείται αρχιτεκτονικά και σε επίπεδο τέχνης το ιδανικό ορθογώνιο. Έχει βρεθεί, δηλαδή, ότι είναι το ορθογώνιο που όλοι ανεξάρτητος κουλτούρας φιλής και φίλου θεωρούν ως το σχήμα με την ιδανική αναλογία και γι' αυτό το λόγο και προφανώς, κάποιοι θα το ξέρετε, η πρόοψη του Παρθενώνα βρίσκεται εδώ μέσα. Και είναι ακριβώς στις διαστάσεις του ιδανικού ορθογωνίου. Στα έργα του Λεωνάρντον Νταβίντσι, οι μορφές είναι η μία μέσα στην άλλη μέσα σε ιδανικά ορθογόνια. Και αυτός ο λόγος αναλογίας θεωρείται ο ιδανικός λόγος που επιδεικνύει το χαρακτηριστικό της ομορφιάς και είναι η απόσταση ζυγοματικών προσμύτη, ανεξαρτήτως φιλής, και αυτό έχει, μάλιστα, αναγνωριστεί σε πειράματα με παιδιά. Τα παιδιά έχουν εξαίρεται σε μικρή ηλικία αυτήν την μαγική ικανότητα να βλέπουν ένα πρόσωπο και χωρίς να μπορούν να το δουν καθαρά, στη βάση και μόνο των αρχικών αναλογιών, να χαμογελούν αν το πρόσωπο είναι ευχάριστο για αυτά. Τα παιδιά λοιπόν χαμογελούν ανεξάρτητα από αν είναι άσπρα, μαύρα, κίτρινα, κόκκινα, μπλε, αρσενικά ή θηλυκά. Αυτός λοιπόν ο χρυσός κανόνας ακολουθείται στην αρχιτεκτονική, αλλά κυρίως ακολουθείται στη φύση. Τον βρίσκουμε σε σπύρες λουλουδιών, τον βρίσκουμε σε αναλογίες στον περίφημο ναυτίλο ένα κοχύλι των θαλασσών και μπορεί να κατασκευαστεί αυτή η σπύρα ουσιαστικά στη βάση ορθογωνίων, τα οποία έχουν ως πλευρές την ακολουθία φιμπονάτση. Με αυτό τον τρόπο. Τώρα, είπα ότι θα σας δείξω ένα βίντεο που πολύ καλύτερα από εμένα επιδεικνύει το τι γίνεται. Βρίσκουμε αυτές τις δομές και σε φυτά, από κουνουπίδια και κουγουνάρια μέχρι μαργαρίτες και οτιδήποτε άλλο. Επίσης, είπα ότι το βρίσκουμε ως αναλογία στο ανθρώπινο σώμα και βέβαια στα πολύ γνωστά έργα τέχνης. Παρεπιπτόντος, θεωρώ να σχολιάσω το γεγονός ότι ο Παρθενώνας είναι ένα αρχιτεκτόνοιμα το οποίο για εμάς τους μηχανικούς έχει ιδιαίτερο ενδιαφέρον. Και παρά το ότι είμαστε σε μάθημα πληροφορικής, είμαστε σε ένα τέτοιο μάθημα εντός ενός τμήματος μηχανικών. Άρα, ο πειρασμός για εμένα είναι μεγάλος και ναι, είμαι αδύναμος άνθρωπος και ρέπω σε τέτοιους αμαρτίες. Θα μπω λοιπόν στον πειρασμό να πω ότι, όπως ξέρουν και εσάς, τα σκαλοπάτια του Παρθενώνα δεν είναι ευθείες, είναι καμπύλες. Δηλαδή, αν σταθείς στο ένα άκρο όσο το έχετε κάνει, το έχετε διαπιστώσει, δεν βλέπεις το άλλο άκρο. Οι κύωνες στις γωνίες, πρώτα απ' όλα οι κύωνες δεν είναι κύλινδροι, είναι βαρελάκια. Δηλαδή, αν πραγματικά δει κανείς την γεωμετρία του κύωνα, δεν είναι αυτό που νομίζουμε, μεγαλύτερη διάμετρο σκάτω, μικρότερη επάνω, είναι αυτό. Το κάνω στον υπερβολικό βαθμό. Και οι κύωνες στους γωνίες είναι πιο παχουλή από τους κύωνες του μέσου, διότι φωτίζονται περισσότερο και αν ήταν της ίδιας διαμέτρου, τότε θα φέρονταν λεπτότερη, γιατί το φως αδυνατίζει. Όλα αυτά, η ένταξη των καμπυλών, αυτός ο δυναμικός παλμός, δημιουργήθηκαν επίτηδες, προφανώς σε γνώση των κατασκευαστών, οι οποίοι ήταν σπουδαίοι μηχανικοί και αρχιτέκτονες, με στόχο να δώσουν στο κατασκεύασμα έναν παλμό, μια ζωντανιά, να μην το καταστήσουν ψυχρό σώμα, η φύση επεχθάνεται τις ευθείες, ο ορίζοντας δεν είναι ευθεία, αλλά να του δώσουν την καμπυλότητα που θα το ενέτασε στο φυσικό περιβάλλον. Ταυτόχρονα, αν σας δείξω αυτή την εικόνα, όχι τόσο καλή η προβολή, και αυτή την εικόνα και σας ζητήσω να διαλέξετε ποια από τις δύο προτιμάτε αισθητικά, ποια θα διαλέγατε? Πρώτη, δεύτερη, να ψηφίσουμε, πρώτη, δεύτερη, και το καμία. Μεταξύ των δύο λοιπόν διαλέγατε την δεύτερη, διότι η δεύτερη ακολουθεί τον κανόνα των τρίτων. Αυτόν δηλαδή το κανόνα. Τοποθετούμε το αντικείμενο σε μία σχέση που περίπου ως προς το πλαίσιο, εντάσσεται ακολουθεί το χρυσό κανόνα, δεν βρίσκεται στο κέντρο, βρίσκεται σε μία θέση που ακολουθεί το χρυσό κανόνα. Τώρα, όλα αυτά έχουν ιδιαίτερη γοητεία και είναι πολύ ενδιαφέροντα. Πάμε στο να δούμε πώς υπολογίζεται το περιεχόμενο της ακολουθίας Φιμπονάτση, δηλαδή πώς μπορώ να υπολογίσω τους όρους. Η διαδικασία είναι πάρα πολύ απλή, αλλά όπως έχουμε αντιληφθεί, η διαδικασία χρησιμοποιεί τον εαυτό της. Δηλαδή, στην πραγματικότητα, οι όροι της ακολουθίας είναι πολύ συγκεκριμένοι. Οι δύο πρώτοι φέρουν ως περιεχόμενο το μέγεθος 1, ο πρώτος όρος είναι 1, ο δεύτερος είναι 1, ο τρίτος είναι το άθλισμα των δύο προηγούμενων, ο τέταρτος είναι το άθλισμα των δύο προηγούμενων, ο πέμπτος είναι το άθλισμα των δύο προηγούμενων. Άρα, ο πέμπτος είναι το άθλισμα των δύο προηγούμενων, οι οποίοι είναι το άθλισμα των δύο προηγούμενων, οι οποίοι είναι το άθλισμα των δύο προηγούμενων, οι οποίοι καταλήγουν να είναι το άθλισμα των δύο πρώτων όρων. Οπότε, λοιπόν, τι κάνει η ακολουθία? Χρησιμοποιεί τον ορισμό της για να υπολογίσει τον εαυτό της. Αυτό σημαίνει ότι είναι αναδρομικού τύπου. Είναι αναδρομικός αυτός που συμβαίνει στο παρόλο αλλά έχει ισχύει και στο παρεθόν. Στην περίπτωση των αλγορύθμων, αυτοί οι οποίοι χρησιμοποιούν τον εαυτό τους για να επαναλαμβάνονται, για να υπολογίσουν το μέγεθός τους, ή για να υπολογίσουν ένα πρόβλημα, ονομάζονται αλγόριθμοι αναδρομικού τύπου. Και βασίζονται στο ότι υπάρχει μια βασική περίπτωση και μια επαγωγική περίπτωση. Υπάρχει δηλαδή, στη δική μας περίπτωση, το ζεύγος των δύο πρώτων όρων και επαγωγικά προκύπτει ότι κάθε επόμενη τιμή είναι το άθροισμα των αμέσως δύο προηγούμενων τιμών. Να δώσω ένα παράδειγμα πολύ απλό. Έστω ότι δεν γνωρίζαμε την πράξη που ονομάζεται ύψωση σε δύναμη. Δεν την γνωρίζαμε. Γνωρίζαμε όμως την πράξη του πολλαπλασιασμού. Και ουσιαστικά όταν κάνουμε την ύψωση σε δύναμη έτσι δουλεύουμε. Τότε πώς θα υψώναμε σε δύναμη έναν αριθμό? Αυτό που ουσιαστικά θα κάναμε θα ήταν το πολύ απλό δηλαδή ότι το β' στην η ορίζεται ως 1 εφόσον το ν είναι 0 και ως β' επί β' στην η πλυν ένα για κάθε άλλο ν. Αυτή δεν είναι η έννοια της ύψωσης σε δύναμη. Το οποίο β' στην η πλυν ένα ορίζεται ως β' επί β' στην η πλυν δύο, το οποίο β' στην η πλυν δύο κτλ κτλ. Ώστε να καταλήξουμε κάποια στιγμή που εδώ. Και έτσι να κλείσει αυτή η αλυσίδα υπολογισμών. Αναδρομικά λοιπόν, εδώ έρχεται η αναδρομικότητα, ουσιαστικά χρησιμοποιούμε τον ορισμό της ύψωσης σε δύναμη για να υπολογίσουμε τον κάθε ώρα πηγαίνοντας προς τα πίσω. Για να είναι λοιπόν ισομετρία γνωρίζουμε ποιο θα ήταν το αποτέλεσμα. Σε επίπεδο κώδικα, επειδή εμείς έχουμε πλέον αρχίσει και να δουλεύουμε με MATLAB και έχουμε εξυπηρεθεί με τις συναρτήσεις, να μία συναρτήση η οποία θα μπορούσε να κάνει αυτή τη δουλειά. Έχω τη συναρτήση δύναμη, η οποία λαμβάνει ως ίσοδο δύο πράγματα, τον αριθμό και τον εκθέτη, αποδίδει το αποτέλεσμα σε μία τιμή και ουσιαστικά εάν ο εκθέτης είναι ίσως με 1, τότε εξ ορισμού η τιμή είναι ο αρχικός αριθμός. Εδώ θα μπορούσα να προσθέσω και το αν ο εκθέτης είναι 0, τότε η τιμή είναι το 1. Ένα δεύτερο έλεγχο για να έχω πληρότητα. Διαφορετικά, η τιμή είναι ίσοδο επί τη δύναμη, την ίδια τη συναρτήση δηλαδή, για τον ίδιο αριθμό αλλά για τον εκθέτη, τον αμέσως μικρότερο κατά 1. Θέλω να καθίσουμε και να το δούμε αυτό γιατί φαντάζομαι ότι κάνει εντύπωση. Δηλαδή βλέπουμε για πρώτη φορά μέσα σε έναν κώδικα να χρησιμοποιείται, να ορίζεται μια συναρτήση και ταυτόχρονα να χρησιμοποιείται για να υπολογιστεί το περιεχόμενό της. Όταν έχω εγώ τη συναρτήση δύναμη με τη βοήθεια της οποίας θέλω να υπολογίσω το αριθμό αυτό σε έναν εκθέτη που θα δίνει ο χρήστης. Η συναρτήση λοιπόν αυτή διαβάζει δύο πράγματα. Έχει δύο ορίσματα όπως λέμε εισόδου. Θα διαβάσει τον αριθμό που θέλω να υψώσω και τον εκθέτη που θέλω να χρησιμοποιήσω. Εάν ο εκθέτης είναι 1 τότε η δύναμη είναι ίση με τον αριθμό αυτό καθ' αυτό. Διάφορετικά είναι ίση με τον αριθμό επί την δύναμη του ίδιου αριθμού για εκθέτη κατά ένα μικρότερο. Οπότε λοιπόν όταν θα πάνε να υπολογίσει αυτό θα πει μα εγώ δεν ξέρω το δύναμη number power μειών 1. Α αυτό είναι το δύναμη είναι λοιπόν όλο αυτό με number επειδή είναι με το number power μειών 2. Και πάλι μειών 3, μειών 4, μειών 5. Κάποια στιγμή αυτός εδώ εκθέτης θα γίνει 1. Διότι κάθε φορά τι κάνω πηγαίνω και υπολογίζω τα πάντα έτσι δεν είναι. Ας το δούμε πως θα τρέξει αυτό. Για παράδειγμα εάν ο αριθμός εδώ number είναι 2 και ο εκθέτης είναι 3. Τότε λοιπόν θα γίνει ορχικός έλεγχος. Είναι το power 1 όχι τότε η τιμή της εξυνάρτησης είναι ίση με τον αριθμό δηλαδή πόσο 2 επί την συναρτηση δύναμη για τον αριθμό 2 και ποιον εκθέτει τον power μειών 1, 3 μειών 1. Αυτό όμως εδώ θα πάει να το ξαναϋπολογήσει. Θα πει που την ξέρω εγώ αυτή τη δύναμη, την ξέρω γιατί ορίστηκε αμέσως πιο πάνω. Είναι το power 1 όχι άρα ισχύει το δεύτερο όπου πλέον αυτό το σκέλος είναι ίση με τον αριθμό επί το δύναμη του 2. Αυτό το εκθέτει μειών 1. Άρα είναι 2 επί 2, επί την δύναμη του 2 ως προς 1, σωστά. Το οποίο όμως είναι, επειδή το power είναι 1 τώρα, αυτό είναι ο αριθμός αυτός καθ' αυτός. Άρα είναι 2 επί 2, επί 2. 2 εις την τρίτη, αυτό που ήθελα να υπολογίσω. Έτσι λοιπόν μπορούμε να δούμε το πως υλοποιείται ο αναδρομικός υπολογισμός, ο οποίος προφανώς είναι διαφορετικός από τον απευθείας υπολογισμό. Εάν δηλαδή είχαμε στη φαρέτρα μας την ύψωση σε δύναμη, τότε θα μπορούσαμε και θέλεμε να χρησιμοποιήσουμε ως πράξη για τον υπολογισμό σε μια συνάρτηση, θα μπορούσαμε να χρησιμοποιήσουμε μια τέτοιου είδους συνάρτηση, η τιμή είναι ο αριθμός, η steam power. Και με αυτόν τον τρόπο άμεσα να το υπολογίσουμε. Τρακτικά εμείς δεν χρειάζεται να το κάνουμε αυτό, γνωρίζουμε ότι είναι η γεννήση συνάρτηση της ύψωσης σε δύναμη, έτοιμη δηλαδή προς χρήση από εμάς. Υπάρχει ένα ερώτημα. Ναι, εννοείται ότι έχουμε κάνει όλους αυτούς τους ελέγχους και ότι έχουμε λάβει πρόνοιες για όλα αυτά. Προφανώς λοιπόν έχουμε δύο διαφορετικούς τρόπους να υπολογίσουμε εδώ. Και θα ήθελα να θέσω το εξής ερώτημα σε εσάς. Είναι αυτοί οι δύο τρόποι σε αυτό το απλό παράδειγμα ύψωση σε δύναμη. Είναι υπολογιστικά ισοδύναμη ως προς τον χρόνο που απαιτείται για να γίνει ο υπολογισμός. Εδώ θα ήθελα να σκεφτούμε το εξής. Πόσες ενέργειες πρέπει να επιτελεστούν στην μία περίπτωση και πόσες στην άλλη. Η απευθείας ύψωση σε δύναμη είναι μία πράξη, έτσι δεν είναι. Μία πράξη. Δύο ή στην τρίτη. Μία πράξη. Εδώ πόσες ενέργειες χρειάζεται να γίνουν. Αρχικά να φέρω επί της οθόνης τον κώδικα. Αρχικά μία ενέργεια. Έλεγχος. If power is on me. Δεν γίνεται αυτό. Μία ενέργεια. Δεύτερη ενέργεια. Ένας αισθητημής με ένας πολλαπλασιασμός. Σωστά. Άρα ένας έλεγχος και ένας πολλαπλασιασμός για κάθε τιμή της power. Τρεις αλλαγές στις τιμές εδώ, επειδή το power είναι τρία. Άρα λοιπόν έξι ενέργειες. Θα γίνει λοιπόν ένας έλεγχος και ένας πολλαπλασιασμός για power ίσον τρία. Έτσι δεν είναι. Νάτο. Θα οδηγήσει σε αυτή την πράξη. Ένας έλεγχος έχει γίνει πιο πριν για το αν το power είναι ένα. Και αμέσως μετά ο πολλαπλασιασμός. Ξαναγίνεται έλεγχος και πολλαπλασιασμός. Ξαναγίνεται έλεγχος και πολλαπλασιασμός. Αυτή λοιπόν η αλληλουχία ενεργειών φαίνεται ότι είναι μεγαλύτερη. Έτσι δεν είναι. Περισσότερες πράξεις κάνω, περισσότερη ενέργεια καταναλώνω. Άρα έχει αντίκτυπο υπολογιστικό. Προφανώς δεν περιμένουμε ο υπολογιστής να κάνει αυτές τις έξι πράξεις στον ίδιο χρόνο που του χρειάζεται για να κάνει την μία πράξη της απευθείας ύψωσης δύναμη. Και αυτό μπορούμε μάλιστα αν θέλετε και πειραματικά, αν και δεν είναι δόκιμος ο όρος, να το επιβεβαιώσουμε με τον εξής τρόπο. Να αναρωτηθούμε πρώτα απ' όλα πόσος χρόνος χρειάζεται. Και να θυμηθούμε ότι στο MATLAB έχουμε πολύ ωραίους τρόπους για να μετράμε το χρόνο. Να θυμίσω τις δύο εντολές TIK και TOK, οι οποίες υπολογίζουν τον χρόνο που απαιτείται για οτιδήποτε λαμβάνει η χώρα μεταξύ αυτών των δύο εντολών. Άρα λοιπόν, εγώ στην αρχική μου συνάρτηση, ακριβώς όπως είναι, έχω προσθέσει και αυτές τις δύο εντολές. TIK πριν τον πρώτο ενέργεια, δηλαδή και TOK αμέσως μετά το τέλος της συνάντησης. Οπότε λοιπόν, εγώ ξέρω ότι θα ξεκινήσει το TIK είναι σαν ένα χρονόμετρο. Το πατάω και τρέχει ο χρόνος. Ωραία. Θα κάνει έλεγχο προπλασιασμό, έλεγχο πολλαπλασιασμό, έλεγχο πολλαπλασιασμό, έλεγχο πολλαπλασιασμό. Κάποια στιγμή θα τελειώσει. Μετά που θα τελειώσει η συνάντηση και πριν φύγει από αυτήν θα δει και το TOK. Θα πατήσει πάλι το STOP, θα σταματήσει ο χρόνος. Θα μας δείξει το αποτέλεσμα. Εγώ τα έκανα στο σπίτι για δύναμη του 2%. Δηλαδή το 2% στην εκατοστή. Και σας γράφω εδώ, έκανα copy-paste δηλαδή, τα τρία τελευταία αποτελέσματα. Ο τελευταίος χρόνος που με έδωσε ήταν 0,001191 δευτερόλεπτα. Τόσο χρειάστηκε για να υπολογίσει ο συγκεκριμένος υπολογιστής με το συγκεκριμένο φόρτο δουλειάς που είχε εκείνη τη στιγμή, το 2 στην εκατοστή σε περιβάλλον MATLAB, το οποίο είναι κάτι σαν 1,26 επί 10 στην 30. Έκανα το ίδιο, δηλαδή προσέφεσα αρχή και τέλος χρονομέτρησης, στον άλλον τρόπο, ο οποίος τι κάνει, απλά υψώνησε στην power. Δηλαδή, πατάω το χρονόμετρο λίγο πριν γίνει η πράξη, αμέσως πριν την πράξη και αμέσως μετά το σταματώ. Για το ίδιο μέγεθος είναι 0,00008. Ποιέση με το, άρα να σημειώσουμε τους χρόνους αν θέλετε, στη δεύτερη περίπτωση, ας την ονομάσουμε την fast. Ο χρόνος ήταν 0,00008 και στην slow ήταν, επειδή δεν το θυμάμαι, 0,001191. Είναι μια μεγάλη διαφορά. Εδώ έχουμε μια ποσότητα στην τάξη του χιλιοστού και εδώ έχουμε μια ποσότητα που είναι στην τάξη του 1 προς 100 χιλιάδες. Εδώ είναι στο 1 προς 1000 και εδώ στο 1 προς 100 χιλιάδες. Άρα έχουμε δύο τάξεις με διάφορους διαφοράς χρόνου. Σκεφτείτε λοιπόν τι θα συμβεί σε ένα μεγαλύτερο πρόβλημα. Αυτή η προσέγγιση είναι μια καινούργια προσέγγιση για εμάς. Εντάσσεται δηλαδή πλέον στη συλλογιστική μας και στον προβληματισμό μας όταν δημιουργούμε τον αλγόριθμο για την επίλυση ενός προβλήματος και η έννοια του χρόνου. Ίσως θα θυμάστε ότι είχαμε αναφέρει στην αρχή του εξαμίνου ότι δεν απαιτείται μόνο το να λύσουμε το πρόβλημα, αλλά να το λύσουμε σε πεπερασμένο χρόνο. Και εκείνη τη στιγμή φαντάζομαι ότι όλοι, ή οι περισσότεροι και οι περισσότερες θα σκεφτήκατε και πολύ λογικά αυτό που σκέφτηκα και εγώ ως κοινόθνητος όταν το πρωτοάκουσα, τι λένε τώρα, τι σημαίνει σε πεπερασμένο χρόνο. Θα δούμε σήμερα τι σημαίνει σε πεπερασμένο χρόνο ξανασκαλίζοντας προβλήματα τα οποία σας είναι γνωστά και απλά, όπως ας πούμε τον υπολογισμό των οριζουσών. Προς το παρόν ας δούμε εδώ το τι μπορούμε να κάνουμε διαφορετικό. Έχουμε την ακολουθή αφιμπονάτση. Άρα λοιπόν, για να δούμε πόσους τρόπους υπολογισμού μπορούμε να έχουμε και τι επίπτωση έχουν αυτή οι τρόποι υπολογισμού στον χρόνο, στην αποτελεσματικότητα ως προς τον χρόνο λοιπόν της επίλυσης αυτού του προβλήματος. Η ακολουθή αορίζεται με τον εξής πολύ απλό τρόπο. Αν το ν είναι 0, τότε η τιμή είναι 0, αν το ν είναι 1, τότε η τιμή του όρου είναι 1 και για οποιαδήποτε άλλη τιμή αθρίζω τους δύο προηγούμενους όρους. Έτσι δεν είναι. Άρα αρχική τιμή γεννή 0, ο όρος έχει τη τιμή 0. Γεννήσων 1, ο όρος έχει τη τιμή 1. Άρα γεννήσων 2, ο όρος έχει τη τιμή των δύο προηγούμενων 1. Γεννήσων 3 είναι 1 και 1, 2, 1 και 2, 3 και πάει λέγοντας. Πώς θα την υλοποιούσαμε, για να το σκεφτούμε λίγο. Θέλουμε μια συνάρτηση, άρα θα χρησιμοποιήσουμε μια συνάρτηση, εντάξει. Και από εκεί και πέρα προφανώς θέλουμε μια διαδικασία η οποία να ελέγχει αν το ν είναι 0, να ελέγχει αν το ν είναι 1 και από εκεί και πέρα για οποιαδήποτε άλλη τιμή του ν, να χρησιμοποιεί για τον υπολογισμό της τιμής του όρου, τις τιμές που έχουν οι δύο αμέσως προηγούμενοι όροι. Αυτό δεν κάνουμε. Μπορούμε να το κάνουμε, έτσι όπως το περιγράφουμε λεκτικά, όχι μόνο με έναν τρόπο, έτσι δεν είναι. Δηλαδή ένας τρόπος θα είναι ακριβώς η υλοποίηση αυτού με ελέγχο. Έλεγχο σημαίνει, το κάνουμε δομές ελέγχου. Εάν λοιπόν το ν είναι 0, τότε να η πρώτη τιμή του όρου, εάν το ν είναι 1, ειδού η δεύτερη τιμή, για οποιαδήποτε άλλη τιμή, else, προσέθεσε τους δύο προηγούμενους. Κάτι τέτοιο. Δεν είναι η μόνη υλοποίηση, μην τρελαθούμε, μια γρήγορη υλοποίηση είναι. Δηλαδή, εάν το ν είναι διπλό ίσον 0, σχολιάζω γιατί το είδα και σε κάποια από τα θέματά σας, χρησιμοποίησατε κατά λάθος το απλό ίσον, το οποίο δεν είναι λογικός έλεγχος, είναι ανάθεστη τιμή. Εάν λοιπόν το ν φέρει την τιμή 0, τότε ο ίδιος έχει την τιμή 0. Εάν το ν φέρει την τιμή 1, ο όρος έχει την τιμή 1, για οποιαδήποτε άλλη τιμή, ο όρος είναι ο προ-προηγούμενος και ο προηγούμενος. Το άθλημα του προ-προηγούμενου και του προηγούμενου. Αυτός είναι ένας τρόπος. Βέβαια, θα μπορούσα να το κάνω και διαφορετικά, σωστά. Δηλαδή, εδώ κάνω ελέγχους. Κάθε φορά τρέχω μια διαδικασία ελέγχου. Θα μπορούσα να το κάνω όμως με έναν άλλο τρόπο. Ευθύ τρόπο, να του πω, άκου να δεις. Έχουν ως εξής τα πράγματα. Για ν1 η τιμή σου είναι 1, για ν2 η τιμή σου είναι 2, είναι επίσης 1, συγγνώμη. Και για οποιαδήποτε άλλη τιμή, από το 3 μέχρι το ν, όποιο και να είναι αυτό το ν, η τιμή σου είναι το άθλημα το 2 προηγούμενο. Φαίνονται να είναι ισοδύναμοι, σωστά. Θέλω να μείνουμε σε αυτό. Πρώτος τρόπος. Σκεφτείτε ότι έχετε αυτό το μαύρο κουτί τη συνάρτηση, το οποίο λαμβάνει σαν είσοδο μόνο τον αριθμό ν. Δηλαδή θέλω τον όρο 32, ν ίσον 32. Τι θα πει το μαύρο κουτί, λοιπόν, πρώτο πράγμα που πρέπει να ελέγξω, είναι το ν0. Σύμφωνα με αυτή τη διαδικασία. Όχι, είναι το ν1. Όχι, τότε η τιμή του όρου για ν32, είναι η τιμή του όρου για ν31, συν την τιμή του όρου για ν30, σωστά. Μετά κάθετε και λέει, ξέρω τη τιμή του όρου για ν31. Όχι, αλλά η τιμή του όρου για ν31. Άρα, να ελέγξω. Προσοχή, εδώ θέλω τώρα τη συμμετοχή σας, παρακαλώ. Για ν ίσον 32, λοιπόν, έχω κάνει τους δύο ελέγχους και έχω καταλήξει, ο κώδικας έχει καταλήξει, στο τι είναι ο όρος 31 και ο όρος 30. Μέχρι εδώ, όταν θα ξαναπάει να υπολογίσει τον όρο 31, τι θα κάνει, σύμφωνα με αυτόν τον κώδικα. Θα ξαναπάει εδώ, θα πει, είναι το ν, το 31 δηλαδή είναι 0, όχι. Είναι 1, όχι. Άρα, ο όρος, ο 31, είναι ο 30 και 29. Το ίδιο θα πει και για τον 29, το ίδιο θα κάνει και για τον 28. Κάθε φορά, δηλαδή, τρέχει τους δύο ελέγχους και κάνει τη μία πρόσθεση. Έως ότου όλο αυτό σπάσει και καταλήξει να είναι πολλές φορές το άθλισμα των αρχικών που ξέρω ποια τιμή φέρουν. Εδώ, πώς θα δουλέψει ο κώδικας μου. Εδώ του λέω ποια είναι η τιμή του πρώτου και του δεύτερου όρου. Και από εκεί και πέρα χτίζω. Δηλαδή, δεν πηγαίνω προς τα πίσω για να φτάσω σε κάτι απλό, χτίζω. Θέλω να τη δούμε, παρακαλώ, αυτή τη διαφορά. Στην πρώτη περίπτωση, πάω προς τα πίσω. Επιτρέψτε μου, δηλαδή, να ζητήσω τη συμμετοχή σας. Εδώ, οι κύριοι. Ο ένας είναι ο προηγούμενος και ο άλλος ο προπροηγούμενος. Άρα, στο παράδειγμα του N32. Έρχεται σε μένα που είμαι συνάντης, είμαι 32, ελέγχω, είναι το N0, όχι. Είναι το N1, ούτε. Άρα, είναι το 32, όρος 31 και όρος 30. Ξέρεις τον 31. Όχι. Αλλά, για να τον βρεις, θα τρέξεις την ίδια διαδικασία. Τι θα πεις. Είναι αυτή η τιμή του N. Το 31 είναι 0. Όχι. Είναι 1. Όχι. Θα την αναθέσεις πίσω. Είναι το 30 και το 29. Το 30 θα πάει στο 29 και στο 28. Το 28 θα πάει στο 27 και στο 26. Και θα μαζεύονται έτσι συνεχώς πράγματα. Πίσω, δηλαδή, θα μεγαλώνει και θα μεγαλώνει και θα μεγαλώνει και θα μεγαλώνει έως ότι το σακούλι του υπολογισμού μας να έχουμε μόνο τους αρχικούς όρους που τους ξέρουμε. Θα δούμε πόσες φορές προκύπτουν. Προφανώς τόσες, ώστε να μας δώσουν το αποτέλεσμα που παράγεται. Στην δεύτερη περίπτωση, το χτίζω, λέω, ο πρώτος όρος είναι 1, ο δεύτερος 1. Ο τρίτος είναι το άθεσμα των δύο προηγούμενων. Άρα, την έχω την τιμή. Ο επόμενος είναι το άθεσμα των δύο προηγούμενων που τις έχω, δεν χρειάζεται να πάνε πιο πίσω οι υπολογισμοί. Τις έχω τις τιμές. Άρα, ενώ στην πρώτη περίπτωση ξεκινάω από μπροστά από πάνω και πάω προς τα κάτω, στη δεύτερη περίπτωση χτίζω από τη βάση προς τα πάνω. Είναι ισοδύναμες αυτές οι δύο διαδικασίες υπολογιστικά. Ωέω! Θα ξαφνιαστείτε εάν δείτε πόσο χρόνο απαιτεί ο υπολογισμός του Φιμπονάτσι με την πρώτη μέθοδο, για να είναι πάνω από 30, για παράδειγμα. Δεν μπορείτε να φανταστείτε γιατί μέγεθος χρόνου συζητούμε. Και θα το υπολογίσουμε αμέσως μετά. Γεγονός είναι ότι, ξαναθυμίζω, έχουμε τη χρυσή αναλογία και το θυμίζω αυτό, γιατί κάποιος μπορεί να πει και γιατί ρε φίλε δεν πηγαίνουμε να υπολογίσουμε με την προσεγγιστική σχέση που την ξέρουμε, επειδή δεν μας δίνει την ακριβή τιμή, εμείς αυτή θέλουμε. Μπορώ όμως να υπολογίσω, είπαμε, αυτό το κλάσμα. Πόσος χρόνος απαιτείτε τώρα, εδώ θέλω την προσοχή σας. Λοιπόν, θα γυρίσω τον κώδικα εδώ και θα το υπολογίσουμε μαζί. Για μικρούς αριθμούς, έτσι, έστω ότι δεν πάμε στο 30, πάμε στο 10, και αυτό αρκετό θα είναι. Πάμε στο 5, ο φι του 5, ο φιμπονάτσι 5, σύμφωνα με αυτή τη μέθοδο. Θέλω να υπολογιστεί, μετρήστε τώρα, αυτός είναι ο στόχος μας, έτσι. Άρα για να δούμε διαδικασίες, έλεγχη και πράξεις, να μετρήσω ελέγχους και πράξεις, σωστά. Λοιπόν, για ν-5 ξεκινώ, θέλω τον φιμπονάτσι τον 5, σύμφωνα με αυτή τη μέθοδο. Πόσους ελέγχους θα κάνω, πρώτος, είναι το ν0, είναι το ν1. Δεν είναι τίποτα αυτά τα δύο, είναι ο 4 και ο 3, μια πράξη. 4 και 3, σωστά. Τώρα, έχω εδώ το f4 συν f3, προσέξτε τώρα τι θα γίνει. Για να υπολογίσω για ν4, τον έναν από αυτούς τους δύο, θέλω πάλι τους δύο ελέγχους και μία πράξη. Έτσι δεν είναι. Και για να υπολογίσω τον ν3, θέλω πάλι δύο ελέγχους και μία πράξη. Άρα, αν το δω μάλιστα σαν δένδρο, γιατί αυτό θα μου βοηθήσει περισσότερο, ο 5ος όρος είναι το άθρησμα του 4ου και του 3ου όρου. Αλλά ο 4ος όρος είναι το άθρησμα του 3ου και του 2ου όρου. Και εγώ θέλω να φτάσω στο f1 και f0 εδώ, σωστά. Ο 3ος είναι ο f2 και ο f1. Ο f2 είναι ο f1 και ο f0. Τον ξέρω λοιπόν αυτόν. Και εδώ είμαι πάλι στον f1 και f0 και με τον ίδιο τρόπο f2, f1, f1, f0. Κάθε φορά λοιπόν θέλω δύο ελέγχους και μία πράξη. Θα δείτε ότι ουσιαστικά, αν μετρήσετε τις πράξεις και τις αθρήσετε, ο μεγάλος ο σημαντικός όρος για κάθε τιμή του ν είναι το δύο εις την ν. Για ν εις τον πέμπτη λοιπόν, απαιτούνται δύο εις την πέμπτη πράξης. Για ν εις τον δέκα, δύο εις την δεκάτη πράξης. Άρα για ν εις τον, το παράδειγμα της Κακέρας το θυμάστε, για ν εις τον οχτώ, οχτώ, εξιντατέσσερα, θέλω τόσες πράξεις που ο αριθμός τους είναι μεγαλύτερος από τον αριθμό των μωρίων του σύμπαντος. Άρα μπορώ να τα υπολογίσω αυτά με έναν υπολογιστή. Σήμερα όχι, θα μπορέσω αύριο, θα μπορέσω εάν οι υπολογιστές του μέλλοντος γίνουν ένα εκατομμύριο φορές πιο γρήγοροι από τους υπολογιστές τους σήμερα. Όχι, ένα απλό πρόβλημα, η ακολουθή αφιμπονάτση καθίσταται μη υπολογίσιμο. Έτσι δεν είναι. Ξαναλέω, ο πέμπτος αυτό πρέπει να το δούμε. Ο πέμπτος όρος δεν θέλει δύο ελέγχους, ελέγχω αν το ν είναι μηδέν, κάθε φορά το κάνω αυτό, έτσι, να μην το ξεχνάμε, δύο έλεγχοι και μία πράξη. Ο τέταρτος είναι δύο έλεγχοι και μία πράξη, ο τρίτος είναι δύο έλεγχοι και μία πράξη, άρα χρήζονται μία συν δύο, συν δύο εις την τετρά δεφέρα, τέσσερις, συν δύο εις την τρίτη, οχτώ πράξεις, είναι το άστισμα του ένα, συν δύο, συν τέσσερα, συν οχτώ, συν κτλ κτλ, δυνάμεις του δύο. Αυτό, λοιπόν, το μέγεθος είναι το μέγεθος των πράξεων που απαιτείται για να υπολογίσουμε τον νιωστό όρο της ακολουθίας Φιβονάτση. Ερώτημα. Έτσι πώς είναι αυτό το 1 και το 0 σαν το λειτουργείς, όπως θα μπορεί να αποκλείσει... Του λέω, αν το ν είναι μηδέν, ο όρος γενή μηδέν, έχει την τιμή μηδέν. Ναι, αλλά το τέλος, όπως την αρχή... Όταν θα φτάσω, λοιπόν, εδώ, είμαι στον όρο δύο, για να είναι δύο, σωστά, και λέω ότι ο όρος δύο είναι ο ένα και ο μηδέν. Ξέρω τον ένα? Ναι, έχει την τιμή μηδέν. Ξέρω τον μηδέν? Ναι, έχει την τιμή μηδέν. Δεν χρειάζεται να πάω από πίσω. Πρέπει όμως όλοι οι όροι να φτάσουν να είναι άθλησμα F1 και F0. Πολλών F1 και F0. Και κάθε φορά επαναλαμβάνω αυτή τη διαδικασία. Άρα, λοιπόν, με αυτόν τον τρόπο, οι πράξεις είναι πολλές. Με αυτόν τον τρόπο, όμως, πόσες είναι οι πράξεις μας? Για να δούμε λίγο. Ποιο είναι το σημαντικό μέγεθος, δηλαδή, εδώ. Είδαμε ότι στην πρώτη περίπτωση, στον προηγούμενο κώδικα, στον προηγούμενο αλγόριθμο, το σημαντικό μέγεθος ήταν το δύο ιστινή. Το καθοριστικό μέγεθος. Εδώ, ποιο είναι το σημαντικό μέγεθος. 1. Στην αρχή, έναν ορισμό. Για ν-1, η τιμή του φύμπου είναι 1. Για ν-2, είναι 1. Για κάθε άλλον ν, είναι το άσθημα των δύο προηγούμενων. Άρα, για ν-3, μία πράξη. Για ν-4, δύο πράξεις. Για ν-5, τρεις πράξεις. Είναι γραμμική σχέση του ν. Αυξάνει το ν, αυξάνει και ο αριθμός των φράξεων, αλλά αυξάνει γραμμικά. Εδώ, το αποδίδουμε, δεν το έχω βάλει στη σωστή θέση, συγγνώμη, με αυτούς τους τις καμπύλες. Στην πρώτη περίπτωση, όπου πρέπει κάθε φορά να ελέγχουμε αν το ν είναι 0, αν το ν είναι 1, και να σπάμε προς τα κάτω, να αποδομούμε δηλαδή το ν, έτσι ώστε να καταλήξουμε να φτάσουμε στις αρχικές τιμές, κοιτάξτε πώς εκτινάσσεται ο χρόνος. Όταν δηλαδή ο σημαντικός παράγοντας είναι το δύο εις τη ν μετά από κάποια ν, ο χρόνος, ενώ είναι πολύ χαμηλός, εκτινάσσεται, είναι εκθετικού τύπου. Γι' αυτό και λέμε ότι σε επίπεδο υπολογιστικό, εδώ έχουμε εκθετική πολυπλοκότητα. Και επειδή έχουμε μια κατηγορία συναρτήσεων στην περιοχή των αλγορίθμων που ονομάζονται συναρτήσεις υπολογιστικής πολυπλοκότητας και αυτές, οι οικογένειες συναρτήσεων λέγονται συναρτήσεις όμικρων, μεγάλων όμικρων, για λόγους που δεν μας αφορούν αυτή τη στιγμή, λέμε ότι σε αυτή την περίπτωση η συναρτήση είναι αυτού του τύπου. Ο χρόνος δηλαδή εις τη ν και ποιος συγκεκριμένα, εδώ είναι του δύο εις τη ν. Άρα αυτός θεωρούμε, αυτός είναι ο σημαντικός όρος, ο καθοριστικός όρος, αυτός που βαραίνει τον υπολογισμό. Ενώ, με παραλλαγές, δύο εις τη ν λοιπόν, αυτό είναι το δύο εις τη ν στην πραγματικότητα. Η προηγούμενη καμπύλη είναι ο φιμπονάτσι, πώς συμπεριφέρεται και αυτή είναι η καμπύλη του δύο εις τη ν, βλέπετε πόσο κοντά είναι. Και ο δεύτερος υπολογισμός, κοιτάξτε πώς είναι, είναι μια γραμμή. Αυξάνει το ν, αυξάνει γραμμικά και πολύ ομαλά ο χρόνος. Γιατί εδώ είναι το 8 επί 10 στην μειών 5 ως προς τους χρόνους. Θα μας απασχολήσουν μετά. Άρα λοιπόν εδώ έχω γραμμικές συναρτήσεις χρόνου. Για να δούμε λοιπόν τι είδαμε. Είδαμε ότι ένα απλό πρόβλημα, ο υπολογισμός της ακολουθίας φιμπονάτσι, μπορεί να έχει τουλάχιστον, και δεν έχει σίγουρα μόνο αυτές, τουλάχιστον δύο λύσεις, οι οποίες όμως οδηγούν σε δύο τελείως διαφορετικούς χρόνους υπολογισμού. Στην πρώτη περίπτωση, ο χρόνος υπολογισμού είναι κολοσιαίως, πρέπει να σας πω ότι πρακτικά όντως, γεννή πάνω από 30 δεν είναι εύκολος ο υπολογισμός, δηλαδή ο χρόνος μετρυέται σε εκατομμύρια χρόνια. Προσοχή, ο χρόνος μετρυέται σε εκατομμύρια χρόνια. Για να βρούμε το Φιμπονάτσι-Γιαννίσων 100 με την πρώτη μέθοδο, θέλουμε τόσο χρόνο όσο και ηλικία του σύμπαντος. Άρα δεν υπάρχει περίπτωση να πούμε «Α, έλα μωρέ, θα προκύψει ένας γρηγορότερος υπολογιστής και θα του δώσει να καταλάβει». Όχι, δεν θα του δώσει να καταλάβει, ό,τι και να γίνει. Στην δεύτερη περίπτωση, ο χρόνος είναι γραμμικός, άρα μπορούμε. Αυτή, λοιπόν, πιστεύω, είναι η πρώτη φορά που συναντάτε την έννοια της διαφορετικότητας όσο προς τον χρόνο υπολογισμού, που ελπίζω ότι σας δείχνει πως ένα πρόβλημα πρέπει να μπορεί να λυθεί πραγματικά σε επεπερασμένο χρόνο. Τι να το κάνω εγώ που ο αλγόριθμος είναι σωστός στην πρώτη περίπτωση. Λύνει πρόβλημα, όχι. Άρα, αν εσείς τον βαθμολογούσατε, πώς θα τον βαθμολογούσατε, χαμηλά. Είναι άψογος, τεχνικά, λειτουργικά. Ναι, δεν λύνει το πρόβλημα. Άρα, δεν είναι αυτό που θέλουμε. Να σας προσκαλέσω να ψάξετε και να βρείτε αποδοτικότερους τρόπους υπολογισμού της Φιμπονάτση και να τους δούμε την επόμενη φορά. Προφανώς, υπάρχουν καλύτεροι από τους δύο που σας έχω δείξει. Ο πρώτος είναι καταστροφή, όπως καταλάβαμε. Ο δεύτερος είναι μια διαδικασία υπολογιστική που λειτουργεί, παράγει αποτελέσματα. Αλλά μπορώ να σας πω ότι δεν είναι οι καλύτεροι. Άρα, εάν ενδιαφέρεστε, ψάξτε. Εγώ την επόμενη φορά, στην αρχή του μαθήματος, θα σας δείξω κάνα δυο ακόμη μεθόδους. Και θα δείξω ακόμη μερικά πράγματα. Όμως, θα ήθελα να κάνουμε χρήση του υπόλοιπου χρόνου, όχι μόνο για τη Φιμπονάτση, που την είδαμε εδώ. Οπ, κλέβω. Αλλά, για να μιλήσω για άλλα προβλήματα, στα οποία η υπολογιστική πολυπλοκότητα είναι ζήτημα εξόχως σημαντικό. Ένα από τα πιο γνωστά προβλήματα γενικά, στην περιοχή της εφοδιαστικής, και όχι μόνο, και θα δείτε για ποιο λόγο το αναφέρω αυτό, είναι το πρόβλημα του περιοδεύοντος πολιτή. Το πρόβλημα του περιοδεύοντος πολιτή, περιγράφεται σχετικά απλά. Ας δούμε μερικά εισαγωγικά τον ορισμό του, χαρακτηριστικά, μεθόδος επίλυσης, την τρέχουσα κατάσταση, όπως επίσης και εφαρμογές. Γιατί μας ενδιαφέρει το πρόβλημα του περιοδεύοντος πολιτή, διότι είναι μια διαδικασία υπολογιστική, που συναντούμε πολύ συχνά και της οποίας η υπολογιστική πολυπλοκότητα είναι όμια με την υπολογιστική πολυπλοκότητα που συναντούμε, για παράδειγμα, στον υπολογισμό οριζουσών. Άρα, αυτή τη στιγμή, αν σας ρωτήσω, μπορείτε να υπολογίσετε την ορίζουσα ενός πίνακα δέκα επί δέκα. Φαντάζομαι ότι ναι, η απάντηση θα είναι ναι. Μπορείτε να εκτιμήσετε τον χρόνο που θα σας χρειαστεί, για να υπολογίσετε μια ορίζουσα δέκα επί δέκα με το χέρι. Ή για να το θέσω αλλιώς, σε όρους που γίνονται πιο αντιληπτοί. Σε επίπεδο εξέτασης γραπτεί στα μαθηματικά, εάν σας ζητηθεί να υπολογίσετε με το χέρι μια ορίζουσα πέντε επί πέντε, δύο ώρες εξέτασης φτάνουν? Μην διαστείτε να απαντήσετε. Εξαντάται από τη μέθοδο. Τώρα, για να δούμε το πρόβλημα του παιδιωδεύοντος πολιτή. Έστω ότι έχω έναν πολιτή, ο οποίος θέλει να κάνει μια διαδρομή, περνώντας μία μόνο φορά από κάθε πόλη και επιστρέφοντας στην αφετηρία, με στόχο να διανύει κάποια προϊόντα. Ποια διαδρομή αντιστοιχεί στη συνολικά μικρότερη διανυόμενη, από το σύνολο δηλαδή των διαδρομών που μπορεί κανείς να αποφασίσει να ακολουθήσει. Ποια είναι η συμφερότερη από πλευράς συνολικά διανυόμενης απόστασης? Υπάρχει αναλυτική λύση σε αυτό το πρόβλημα. Υπάρχει σχέση. Υπάρχει υπολογισμού που να μας δίνει με απόλυτη σαφήνεια την απάντηση. Για να δούμε λοιπόν κάποιους ορισμούς. Επειδή είναι ένα πρόβλημα γραφικού τύπου, το προσεγγίζουμε με γραφήματα. Πλήρες γράφημα ονομάζουμε την μοναδική σύνδεση κορυφών σημείων επί του επιπέδου. Γράφημα βαρών ονομάζουμε την περίπτωση όπου αυτή η σύνδεση έχει κόστος. Τι σημαίνει αυτό? Εάν είσαστε στην παραλία της Χαλκιδικής, μια παραλία και θέλετε να επισκεφτείτε το βουνό, μπορεί τα χιλιόμετρα να είναι τα ίδια και στην άνοδο και στην κάθοδο, αλλά η βενζίνη που θα ξοδέσετε στην άνοδο είναι περισσότερη από αυτή που θα ξοδέσετε στην κάθοδο. Γιατί? Διότι η ύπαρξη της κλήσης συνεπάγεται πως το γράφημα της διαδρομής δεν είναι συμμετρικό. Άρα υπάρχει κόστος και μάλιστα το κόστος δεν είναι ισοδύναμο. Η μετακίνηση από το Α στο Β δεν κοστίζει το ίδιο σε σχέση με τη μετακίνηση από το Β στο Α. Στον πραγματικό κόσμο λοιπόν κινεί το πολιτής μας και προφανώς υπάρχει κόστος. Μια προσέγγιση θα μπορούσε να είναι του τύπου επίπεδη και κάθε μετακίνηση κοστίζει το ίδιο ανεξαρτήτος κατεύθυνσης. Και μετά να επιχειρήσουμε να κάνουμε τη Γη μια επίπεδη όπως πραγματικά είναι. Εδώ λοιπόν έχουμε το πλήρες γράφημα, τη μοναδική σύνδεση και γράφημα με βάρη όταν η σύνδεση έχει κόστος. Το κόστος της βενζίνης, οποιονδήποτε. Το χρόνο, ο χρόνος που θα διανύσετε δεν είναι κόστος. Δεν έχει κόστος. Η χαμηλτονιανή διαδρομή ονομάζεται το πλήρες γράφημα βαρών με επιστροφή στην αρχή από το μεγάλο μαθηματικό Χάμιλτον. Βέλτιστη χαμηλτονιανή διαδρομή είναι αυτό που ζητούμε στην περίπτωση του προβλήματος του περιοδεύοντος πολιτή. Έχω για παράδειγμα αυτές τις τελείες. Ποιος είναι ο βέλτιστος τρόπος για να τις συνδέσω μεταξύ τους. Είναι ένα επίκαιρο πρόβλημα με πολλές εφαρμογές και μπορώ να σας πω από τώρα ότι δεν υπάρχει αναλυτική λύση. Προσέξτε τώρα τι γίνεται. Όταν είμαστε σε πρόβλημα όπου δεν υπάρχει αναλυτική λύση, ο μόνος τρόπος για να βρούμε την λύση είναι να δοκιμάσουμε όλους τους δυνατούς συνδυασμούς. Όμως, αυτού του είδους ο υπολογισμός δεν είναι πολυπλοκότητας απλά διοιστηνή, είναι πολυπλοκότητας νηπαραγοντικό, που είναι της κλάσης του διοιστηνή και λίγο περισσότερο. Τράγμα που σημαίνει ότι για περισσότερες από 30 πόλεις είμαστε καταδικασμένοι. Δεν υπάρχει περίπτωση να βρούμε λύση. Τι λοιπόν διαδικασίες επίλυσης έχουμε. Μία είναι η αναλυτική. Παίρνω όλες τις διαδρομές και αρχίζω και τις μετετώ. Πολύ μεγάλο αριθμό συνδυασμών. Γενικά, όταν έχω νη αντικείμενα, ο τρόπος με τον οποίο μπορώ να τα συνδυάσω είναι νηπαραγοντικό. Έχω δεύτερους τρόπους επίλυσης που δεν τους έχετε ξαναδεί και δεν τους έχετε ξανακούσει ενδεχομένως. Είναι η βελτιστοποίηση, η μέθα τη βελτιστοποίηση. Είναι προσεγγιστικού τύπου και είναι και ευρεστικού τύπου. Τι σημαίνει ευρεστικού τύπου? Να δώσω ένα πολύ απλό παράδειγμα. Έχει βρεθεί ότι ο άνθρωπος, ο μέσος άνθρωπος, χωρίς καμία εκπαίδευση, εφόσον κοιτάξει ένα πρόβλημα περιοδεύοντος πολιτή που εμπλέκει 10-20 πόλεις, μπορεί με το μάτι, αυτό που ονομάζουμε με το μάτι, να δώσει μια λύση η οποία είναι κοντά στην βελτιστή, χωρίς να κάνει κανέναν υπολογισμό. Υποθέτουμε εμείς ότι δεν κάνει υπολογισμό. Στην πραγματικότητα γίνονται και μάλιστα πολλοί υπολογισμοί. Έτσι δεν είναι. Άρα λοιπόν, ποιος είναι ο τρόπος με τον οποίο βρίσκουμε λύση σε αυτό το πρόβλημα? Επίσης, υπάρχουν υπολογιστικές μέθοδοι που ονομάζονται ευρεστικές και βασίζονται σε στοιχεία βιολογικής νοημοσύνης, όπως τα νευρονικά δίκτυα, όπως η νοημοσύνη τους μήνους, η νοημοσία της απειδικήας μυρμυγκιών, ant colony optimization, όπου έχουμε παρατηρήσει πως αυτά τα όντα, πρικισμένα με πολύ χαμηλή νοημοσύνη σε σχέση με τα ελαστικά, είναι σε θέση να επιλύσουν πολύπλοκα προβλήματα. Κλασικό παράδειγμα είναι ο περίφημος χορός της Μέλησας, με τη βοήθεια του οποίου δείχνει την διαδρομή που πρέπει το Μελήσι να ακολουθήσει, την βέλτιστη διαδρομή, την εγκύτερη διαδρομή που πρέπει να ακολουθήσει το Μελήσι για να προσεγγίσει τροφή. Υπάρχουν λοιπόν διάφορες μέθοδοι. Η ακμή με το χαμηλότερο κόστος επιλέγεται πρώτοι, ακολουθεί αυτή με το αμέσως επόμενο κτλ κτλ. Εγώ δεν θα επιμείνω σε αυτό περισσότερο. Θέλω όμως να σας δείξω μερικές προσεγγίσεις, γιατί θα τις χρησιμοποιήσουμε μετά ως υπολογιστικούς τρόπους, όταν θα πάμε και σε άλλους προβλήματα. Έχω τη μέθοδο του εγκύτερου γείτονα, ξεκινώ από οποιαδήποτε κορυφή και πηγαίνω στην εγκύτερη. Η λογική είναι ξεκινώ από οποιαδήποτε πόλη και πηγαίνω στην αμέσως κοντινότερη μου. Και από εκεί πηγαίνω στην αμέσως επόμενη κοντινότερη. Και από εκεί στην αμέσως επόμενη κοντινότερη, εκτός από αυτήν από την οποία έχω προέλθει, με στόχο τελικά να καταλήξω στην τελευταία που δεν έχω επισκεφθεί και από εκεί να επιστρέψω στην αρχική. Έχω λοιπόν διάφορες μεθόδους και για να δούμε ποια είναι η τρέχουσα κατάσταση, για ποιον λόγο. Διότι αυτό το πρόβλημα, ακριβώς λόγω του μεγάλου ενδιαφέροντος, γιατί έχει επασχολήσει πάρα πολλούς. Σκεφτείτε τι συζητούμε. Συζητούμε το να μπορεί κανείς να συνδέσει συγκεκριμένους προορισμούς, όλους τους προορισμούς, με τον βέλτιστο τρόπο. Ποιοι άραγε θα αντιμετωπίζουν ένα τέτοιο πρόβλημα στον πραγματικό κόσμο? Ποιες εμπορικές, επιχειρηματικές δραστηριότητες θα ενδιαφέρονταν για απαντήσεις σε αυτό το πρόβλημα. Πώς μπορώ να συνδέσω έναν αριθμό από πόλεις μεταξύ τους, έτσι ώστε να τις επισκεφθώ όλες με το ελάχιστο κόστος. Αντιπρόσωποι εταιριών γενικά. Εγώ θα πω και κάτι άλλο. Είστε αεροπορική εταιρεία. Θέλετε να συνδέσετε τα νησιά του Αιγαίου. Όλα με το μικρότερο κόστος. Πώς πρέπει να χτίσετε το δίκτυο των δρομολογίων σας. Η τρέχουσα κατάσταση είναι εξής. Επειδή δίνονται πάρα πολλά προβλήματα προς επίλυση, ένα πρόβλημα είναι πολιτείες στην Αμερική, 13.500 πόλεις στις ΗΠΑ και μια λύση που δόθηκε πριν από μερικά χρόνια, η οποία θεωρείται μία από τις καλύτερες που μπορούν να υπάρξουν και την πολυπλοκότητα της διαδρομής. Τέτοιοι είδους προβλήματα είναι προβλήματα πριν από 20 χρόνια. Χρειάστηκαν περίπου 5 CPU years. Τι σημαίνει 5 CPU years με τις υπολογιστικές ικανότητες εκείνης της εποχής. Ένας υπολογιστής θα έπρεπε να δουλεύει 5 χρόνια για να παράξει τη λύση. Προφανώς δεν ήταν μόνο ένας υπολογιστής, ήταν πολλοί της εποχής εκείνης. Μιλούμε για μια περίοδο ήδη 20 χρόνια πριν. Και τώρα τρέχουν τέτοιοι διαγωνισμοί. Ένας σχετικά σύγχρονος πριν από 15 χρόνια. 15.000 πόλεις και χωριά στη Γερμανία. Περίπου 40.000 μίλια. Συνολικός χρόνος υπολογισμού 22,5 χρόνια. Αυτού του είδους τα μεγέθη είναι δεδομένα. Δηλαδή, όταν θέλεις 22,5 χρόνια υπολογισμού για να λύσεις κάτι τέτοιο, προφανώς η υπολογιστική στρατηγική σου είναι πάρα πολύ συγκεκριμένη. Ειδικά, εάν λάβετε υπόψη σας, ότι εάν θελήσεις να χρησιμοποιήσεις υπολογιστικούς πόρους κλάσης υπερυπολογιστή, αυτοί κοστίζουν. Τι σημαίνει αυτό, ότι αν θέλετε να πάτε ένα πρόβλημα και το τρέξει ένα υπολογιστικό κέντρο που είναι εξοπλισμένο με υπερυπολογιστές, πληρώνεται ανα ώρα, ανα CPU ώρα. Κατά βάση, ένα λεπτό πληρώνεται. Και το κόστος αυτό δεν είναι αμεληταίο. Δεν είναι δωρεάν. Δεν μοιάζει, δηλαδή, ως να το έχουμε στο σπίτι μας, στο μηχάνημα, αυτό, έτσι. Και υπάρχουν κι άλλους τους προβλήματα. 2 εκατομμύρια πόλη σε όλο τον κόσμο, τον Μάρτιο του 2004. Που χρειάζονται τώρα όλα αυτά και γιατί σας το αναφέρω, εφοδιαστική και μεταφορές. Διαδρομές φορτηγών. Είσαστε σχολικό λεωφορείο και θέλετε να περάσετε από τα σπίτια όλων των μαθητών και να τους παραλάβετε το πρωί και να τους επιστρέψετε το μεσημέρι. Προφανώς σας ενδιαφέρει η βέλση στη διαδρομή. Είσαστε το φορτηγό που κουβαλά τα ψιλικά της γειτονιάς, το γάλα, οποιαδήποτε ευπαθή προϊόντα τα οποία καθημερινά διακινούνται. Θέλετε να ελαχιστοποιήσετε τη διαδρομή. Είσαστε τα απορριματοφόρα του δήμου. Και θέλετε να περάσετε από όλα τα σημεία εξυπηρέτησης στον μικρότερο δυνατό χρόνο. Ποια είναι τα στοιχεία κόστους εκεί εξατάται από την ώρα της ημέρας. Μπορεί να είναι ο χρόνος, μπορεί να είναι η απόσταση. Μπορεί δηλαδή ένα πρόβλημα βέλτιστο ως προς το χρόνο της διαδρομής να μην αντιπροσωπεύει τη βέλτιστη λύση όσο στην διανιώμενη απόσταση, έτσι δεν είναι. Γιατί μπορείτε να πάτε από μακρύτερες διαδρομές, που όμως τις διανιέται συντομότερα γιατί δεν έχουν κυκλοφοριακή συμφόρηση. Βλέπετε πόσο δυναμικό μπορεί να είναι αυτό το πρόβλημα. Σκεφτείτε λοιπόν να πρέπει να σχεδιάσετε κάτι τέτοιο. Και να σας δώσω και το άλλο παράδειγμα. Πείτε ότι είστε ιδιοκτήτες, διαχειριστές των διαδρομών μεγάλων κάργοπλοίων, τα οποία διακινούν εμπορεύματα σε όλο τον κόσμο μέσω θαλασσών. Ποιο είναι λέτε το μέσο, σας το είχα αναφέρει, πιστεύω για να δούμε αν κάποιος το θυμάται, ποιο είναι το μέσο ημερήσιο κόστος αναμονής ενός τέτοιου πλοίου σε λιμάνι, θυμάται κανείς. Και όταν βλέπετε ένα λιμάνι στη Θεσσαλονίκη, ένα πλοίο με κοντέινερ να περιμένει τη σειρά του στο λιμάνι της Θεσσαλονίκης για να εξυπηρετηθεί. Είναι 50.000 δολάρια τη μέρα. Δηλαδή αν φτάσει νωρίτερα ή αργότερα, κι άρα αν δεν φτάσει εντός του προγράμματος ώστε να εξυπηρετηθεί όταν είχε προγραμματιστεί, διότι όταν είχε κλειστεί το ραντεβού με τους γερανούς και με το σύστημα logistics, τότε είναι 50.000 δολάρια τη μέρα. Δεν είναι μικρό ποσό, έτσι δεν είναι. Έχουμε μηχανικό ρομπότ το οποίο επεξεργάζεται επιφάνειες. Έχω ένα σώμα και ένα ρομπότ το οποίο θέλει να κάνει ένα σύνολο από 38 τρύπες και θέλει να το κάνει αυτό σε 10.000 θεμάχια. Δεν είναι πρόβλημα περιοδεύοντος πολιτή. Ποια είναι η βέλτιστη αλληλουχία διάτρισης που πρέπει να ακολουθήσει ώστε να κάνει τη διάτριση στον ελάχιστο χρόνο, διότι θα το κάνει 10.000 φορές και μπορεί η μηχανή να κοστίζει ας πούμε 1.000 ευρώ την ώρα. Τέτοια είναι τα κόστι. Είσαστε πάροχος κινητής τηλεφωνίας. Έχετε το δυναμικό σύστημα δίκτυο των χρηστών κινητών. Τι είναι αυτή? Είναι συσκευές που θέλουν εξυπηρέτηση, θέλουν δρομολόγηση του σηματός τους. Αλλάζει η θέση των καταναλωτών. Πώς θα δρομολογήσετε βέλτιστα έτσι ώστε να ελεγχιστοποιηθεί τι? Ο χρόνος ανταπόκρισης, αυτό σας ενδιαφέρει και το κόστος για εσάς. Εδώ μιλάμε λοιπόν για πολύ σημαντικά προβλήματα. Όλα αυτά είναι προβλήματα περιοδεύοντας πολιτή. Να και κάτι το οποίο μπορεί και να μην το είχατε φανταστεί. Είναι ένα χαλί στο οποίο πρέπει να γίνει με τη βοήθεια ενός βιομηχανικού ρομπότ ένα σύνολο από σχέδια. Ή μπορεί να είναι ένα τεράστιο τσάμι στο οποίο θα γίνει μια αμοβολή με τη βοήθεια βιομηχανικού ρομπότ. Είναι ένα σύνολο διαδρομής αυτοί που πρέπει να διανηθεί για να μπορέσουν να χαρακτούν τα συγκεκριμένα σχέδια. Είναι το ελάχιστο μήκος διαδρομής με τη βοήθεια του οποίου θα επιτευχθεί ο στόχος. Όμοιο πρόβλημα, αν και φαίνεται παράξενο, είναι οποιονδήποτε σχεδόν πρόβλημα βελτιστοποίησης. Τα προβλήματα βελτιστοποίησης. Το πρόβλημα του περιοδεύοντας πολιτή λοιπόν είναι ένα πρόβλημα βελτιστοποίησης. Τα προβλήματα αυτά μας ζητούν να βρούμε το κατάλληλο σύνολο παραμέτρων που μεγιστοποιούν ή ελαχιστοποιούν μια συνάρτηση. Ξέρετε ποιο είναι το πρόβλημα ότι στο φυσικό, στον πραγματικό κόσμο, επειδή τα προβλήματα είναι πολύ παραμετρικά, εδώ έχουμε μόνο τρεις διαστάσεις, μπορεί να έχουμε μια τέτοια κατάσταση. Οπότε αν είσαστε πάνω σε αυτή εδώ την ραχούλα, επιτρέψτε μου την έκφραση, τότε έχετε την εντύπωση ότι είστε σε τοπικό μέγιστο. Και μάλιστα το δείτε και μαθηματικά, να θυμίσω ότι ο μηχανικός χρησιμοποιεί τα εργαλεία του. Ποια είναι τα κριτήρια του μεγίστου, έτσι, οι παράγωγοι. Αν κοιτάξετε την παράγωγο και δεξιά και αριστερά, τι κάνει, έτσι, μόνο σε ποιο σημείο, εδώ δεν μηδενίζεται, είναι flat. Άρα λοιπόν, αν μετρήσετε την παράγωγο προς οποιαδήποτε κατεύθυνση, την βρίσκετε διαφορετική από την μηδενική, αλλά λέτε είμαι εδώ σε σημείο μεγίστου ή ελαχής του, βλέπετε και τις τιμές, άρα οι τιμές μικραίνουν αν πάω αριστερά ή δεξιά, άρα είμαι σε μέγιστο. Είναι έτσι, υπάρχει ένα απόλυτο μέγιστο. Όπως επίσης εδώ, στην περίπτωση του μεγίστου, έχω ένα απόλυτο. Για κοιτάξτε την περίπτωση του ελαχής του, αν υποθέσουμε ότι αυτό το βαθούλομα είναι το ελάχιστο, τότε έχετε ένα σημείο ελαχής του. Όχι, έχετε πολλά. Παραδείγματα βελτιστοποίησης. Είσαστε ο κατασκευαστής ενός αυτοκινήτου. Είσαστε η ομάδα μηχανικών που σχεδιάζει το αυτοκίνητο και σχεδιάζεται το καινούριο μοντέλο. Σας λέει λοιπόν η ομάδα που είναι υπεύθυνη για τις αναρτήσεις και για τον κινητήρα, ότι κοίταξε να δεις, όταν βάλαμε καινούριο κινητήρα, καινούριες αναρτήσεις και τα λοιπά, θα φάμε κάποιο τμήμα από τους θόλους, εκεί όπου από κάτω έχουμε το σύστημα αναρτήσεων και τροχών, θα μεγαλώσουμε λίγο τους θόλους, θα τους μετακινήσουμε λίγο και έτσι θα αλλάξουμε τη γεωμετρία του πόρτ μπαγάς σε σχέση με το προηγούμενο μοντέλο. Αλλά ο ανταγωνισμός έχει βγάλει ένα καινούριο μοντέλο, το οποίο σου λέει ότι έχω 450 λιτραχωρητικότητας, καθαρά. Και εσύ με αυτό το setup, με αυτό το στήσιμο πας τα 380 λιτρα. Είσαι πιο κάτω από τον ανταγωνισμό. Τι κάνεις? Τι δυνατότητες έχεις να μετακινήσεις τους θόλους, ελάχιστες. Πρέπει να μιλήσεις με τους μηχανικούς που είναι υπεύθυνοι για τη γεωμετρία του αμαξώματος και τα λοιπά, θα σου πουν τι μπορείς να κάνεις. Από εκεί και πέρα μπορεί να αλλάξεις όμως λίγο τη γεωμετρία των θόλων. Με στόχο τι? Στα τεστ που κάνουν αναλυτικά κάποια περιοδικά, όπως αυτά της Αντέα Τσε, τα μεγάλα σοβαρά περιοδικά αυτοκινήτου, τα οποία δεν σου λένε μόνο ποια είναι η χωρητικότητα του πόρτ μπαγάζ, αλλά σου λένε ότι σε αυτό το πόρτ μπαγάζ μπορείς, για παράδειγμα, να βάλεις 180 φιάλες νερού του 1,5 λίτρου. Διότι το έχουμε κάνει, σου λένε. Οπότε λοιπόν, μετά αρχίζεις και παίζεις με τέτοιου θέμα. Πώς μπορείς να χωρέσεις έναν αριθμό κυβωτήων. Και βέβαια, αν το αυτοκίνητό σου είναι αυτοκίνητο που επιτελεί μεταφορές, τότε αυτό καθίστεται ο κύριος στόχος. Βγάζεις έναν καινούριο βανάκι στην αγορά, το οποίο θα πρέπει να έχει όλα τα χαρακτηριστικά που θα το καταστήσουν αντογωνιστικό και ταυτόχρονα να έχει κάποια πλεονεκτήματα. Βγάζεις έναν καινούριο ελεωφορείο για τον ΟΑΣ. Και ο ΆΣ να αγοράσει ένα καινούριο ελεωφορείο, έτσι. Ανακοίνωσε επαρρυπτόντας ότι θα υπάρξει κάποια στιγμή μια ανανέωση του στόλου. Όλοι το κάνουν αυτό. Πώς θα επιλέξει, πώς θα πείσει ο κατασκευαστής τον υποψήφιο αγοραστή, πώς συγχωρούν και από ποια συνθήκη, όχι ο Σαρδέλες, όχι ο Ριζόντιας να είναι δέματα ξύλων, έτσι. Μιλάμε για ανθρώπινο επιβατικό κοινό λοιπόν. Αυτά είναι κάποια παραδείγματα. Να σας πω ότι αν έχετε μη κουτιά, υπάρχουν δύο ιστινοί συνδυασμοί, με βάση τους οποίους μπορείτε να τα τοποθετήσετε μέσα σε ένα πορτοβαγάζ. Για αυτό το λόγο και είναι πρόβλημα περιοδεύοντος πολιτή, της ίδιας τάξης δηλαδή. Ποιος είναι από αυτούς ο συνδυασμός, δηλαδή αν έχετε μη κουτιά, υπάρχουν οι τρόποι να τα τοποθετήσετε ένα δίπλα στο άλλο, δύο στη μη. Ποιος από αυτούς τους συνδυασμούς παράγει τον μικρότερο όγκο, ο ΕΛΑΔΑ. Δύσκολα. Ερωτήματα. Και υπάρχει και ως παιχνίδι online βέβαια, έτσι. Οπότε υπάρχει και ως παιχνίδι υποφορά την Ελλάδα, γενικά διαδρομές από όλα τα νησιά και τα λοιπά. Έχοντας λοιπόν όλα αυτά κατα νου, πιστεύω ότι τώρα μπορούμε πολύ καλύτερα να δούμε... Με άλλο μάτι ελπίζω, όχι μόνο το πρόβλημα του περιοδεύοντος πολιτή, αλλά προβλήματα υπολογιστικής πολυπλοκότητας ευρύτερα. Κοιτάξτε εδώ τι έχουμε. Έχουμε ένα συγκεκριμένο πρόβλημα. Έχω αυτές τις πόλεις κόκκινες, τις έχω αριθμίσει 1 έως 5 και για κάθε διαδρομή έχω σημειώσει το κόστος. Τα φράστε το όπως θέλετε. Είναι συμμετρικό, δηλαδή από την 3 στην 4 το κόστος είναι 9 και 9 παραμένει αν πάω και από την 4 στην 3. Είναι σαν να λέμε το κάψιμο που θα δοπανίσουμε, ο χρόνος που θα χρειαστούμε, οτιδήποτε τέτοιο. Τι είναι λοιπόν οι συναρτήσεις υπολογιστικής πολυπλοκότητας τελικά? Είναι οι συναρτήσεις που μας κάνουν μια πολύ καλή εκτίμηση αφενός του χρόνου που χρειάζεται για να επιλυθεί ένα πρόβλημα και αφετέρου του χώρου αποθήκευσης δεδομένων. Διότι και αυτό επίσης είναι μία μελητέο. Και βασίζω την έννοια της βασικής πράξης. Κοιτάξτε εδώ έναν απλό αλγόριθμο. Θα σας βοηθήσω για όσους δεν είναι εξικοιωμένοι με τέτοιους συμβολισμούς. Ξεκινώ με αρχική τιμή της παραμέτρου α, τίση με μηδέν, για i από 1 έως ν. Προσθέτω στην α την προηγούμενη τιμή της α, στην τιμή χ΄i ενός στοιχείου ενός διανύσματος. Έχω έναν διανύσμα ν στοιχείων, έτσι, 10, 20, 30. Το πρώτο, το δεύτερο, το τρίτο, το δεύτερο στοιχείο κτλ. Και στο τέλος υπολογίζω την τετραγωνική ρίζα. Πόσες πράξεις, πόσες στοιχειώδεις πράξεις χρειάζομαι για να κάνω αυτό τον υπολογισμό. Αν δηλαδή θέλω να αθρίσω τα ν στοιχεία ενός διανύσματος, να αθρίσω τα τετράγωνα των στοιχείων ενός διανύσματος και να βρω την τετραγωνική τους ρίζα. Πόσες στοιχειώδεις πράξεις χρειάζομαι, για να δούμε ξανά. Βαφτίζω την μεταβλητή μου α και μετά λέω ότι καινούργια σου τιμή είναι αυτή που είχες συν το πρώτο στοιχείο στο τετράγωνο. Μετά του λέω τώρα είναι η παλιά που είχες, δηλαδή το πρώτο στοιχείο στο τετράγωνο είχες ήδη συν το δεύτερο στοιχείο στο τετράγωνο. Στο τρίτο βήμα λέω αυτά που έχεις κάνει μέχρι τώρα, πρώτο και το δεύτερο στοιχείο, συν το τρίτο στοιχείο στο τετράγωνο. Το ξανεπαναλαμβάνω, το τέταρτο, το πέμπτο, το νιωστό. Και στο τέλος υψώνω στο τετράγωνο. Πόσες φορές θα την κάνω αυτή τη δουλειά. Δεν έχω 10, 20, 30 μη στοιχεία. Πόσες φορές θα φέρω το καινούριο στοιχείο μέσα στο άθρησμα. Όσα στοιχεία έχω, τόσες φορές θα κάνω και αυτή την πρόσθεση. Σωστά. Συμφωνούμε. Διαφωνούμε. Ή τι άποψη έχουμε. Για να μπορέσουμε λίγο να το παρακολουθήσουμε. Ξαναλέω. Θέλω να προσθέσω. Ορίστε. Διότι πρέπει να τα γράφουμε επίσης. Θέλω να προσθέσω. Όλα τα στοιχεία χειάει στο τετράγωνο. Χειάει από ένα έως νι. Και να υπολογίσω την τετραγωνική ρίζα αυτού του αθρίσματος. Πώς μπορώ να το κάνω αυτό. Πώς μπορώ να κάνω τον υπολογισμό. Χωρίς να χρησιμοποιώ διανισματικό τρόπο συμβατικά. Ξεκινώ από το πρώτο τοιχείο. Και λέω, για Ά-1 υπολόγησε μου το χει τετράγωνο. Και προσθέθησα έτω στην αρχική τιμία α, η οποία τι τιμία έχει στην αρχή. Και να κοιτάς με απορία. Τι τιμία έχει στην αρχή. Τι τιμία έχει στην αρχή. Μηδέν. Άρα αν του προσθέσω το χει 1 τετράγωνο, τώρα έχει χει 1 τετράγωνο ως καινούργια τιμή. Αν του προσθέσω για το επόμενο Ά, θα πάει σε ποιο χει στο δεύτερο. Να το διανισμα χει. Είναι οι τιμές 1, 2, 5, μειών 3. Αυτό είναι το χει 1 έστω, το χει 2, το χει 3, το χει 4. Άρα λοιπόν το τετράγωνο του πρώτου, το βάζω στο α. Η καινούργια τιμή του α είναι το μηδέν συν το τετράγωνο του 1. Η επόμενη επανάληψη θα μου πει ότι η καινούργια τιμή του α είναι η προηγούμενη συν το τετράγωνο του 2. Συν το τετράγωνο του 5, συν το τετράγωνο του μειών 3. Άρα στο τέλος είμαι σίγουρος, σίγουρη ότι έχω αθρίσει τα τετράγωνα όλων των στοιχείων του διανισματός μου. Και άρα μπορώ να υπολογίσω την τετραγωνική ρίζα. Πόσες πράξεις θέλει αυτή η διαδικασία για να επιτελεστεί. Αυτό το ερώτημα πρέπει να θέσουμε. Πρώτο στοιχείο, δεύτερο στοιχείο, τρίτο στοιχείο, τέταρτο στοιχείο, μειωστό στοιχείο. Σωστά. Μη στοιχεία, μη πράξεις. Μη υψώσεις στο τετράγωνο και προσθέσεις. Άρα για κάθε ν τι κάνω. Μια ύψη στο τετράγωνο και μια πρόσθεση. Άρα δύο ν. Σωστά. Αν για παράδειγμα έχω ν ίσον 10, πόσες στοιχειώδες πράξεις θα κάνω για κάθε ν. Δεν υψώνω στο τετράγωνο και δεν προσθέτω. Ε, δύο φορές δύο πράξεις για κάθε ν. Άρα θα κάνω 20 στοιχειώδες πράξεις και μια τετραγωνική ρίζα στο τέλος, 21. Λέμε λοιπόν ότι σε αυτή την περίπτωση, ο χρόνος υπολογισμού ταφ, ως προς το μέγεθος του προβλήματος ν, είναι ίσως με ν. Είναι, για να είμαι πιο ακριβής, ανάλογος του ν. Έτσι δεν είναι. Έχω δέκα βήματα, έχω δέκα στοιχεία, θέλω δέκα στοιχειώδες υπολογισμούς. 20, 30, γραμμική σχέση του ν. Άρα, αν έχω ένα εκατομμύριο στοιχεία, θέλω ένα εκατομμύριο υπολογισμούς. Οπότε, εάν έχω έναν επεξεργαστή που έχει συχνότητα, πείτε μου μια συχνότητα επεξεργαστή. Τρία, να το κάνω στον κιλό. Τρία τι είναι αυτά? ΓιγαΧερίς. Τι σημαίνει τρία ΓιγαΧερίς συχνότητα? Άλλος, έχετε έναν υπολογιστή στο σπίτι. Τα βασικά, τρία ΓιγαΧερίς συχνότητα σημαίνει ότι το εσωτερικό ρολόι, να το πούμε έτσι, δουλεύει τόσο γρήγορα ώστε να μπορεί να επιτελέσει... Έλα, κάποιος... Ναι, όχι, όπως θέλεις. Χονδρικά τρία εκατομμύρια υπολογισμούς στο δευτερόλεπτο. Άρα, λοιπόν, αν έχω ένα πρόβλημα υπολογισμού του αθρίσματος των τετραγώνων και της τετραγωνικής ιδρίας στο τέλος για ένα εκατομμύριο στοιχείο, τότε θέλω ένα τρίτο του δευτερολέπτου σε έναν τέτοιο υπολογιστή. Σωστά, έτσι δεν είναι. Μπορείτε, λοιπόν, να έχετε μια άμεση αίσθηση, μια εικόνα του πόσο χρόνο θέλετε για να υπολογίσετε κάτι. Σε αυτό το πρόβλημα, λοιπόν, ο χρόνος είναι γραμμική σχέση του ν. Δείτε κάτι άλλο, όμως. Θέλει την προσοχή σας αυτή η διαδικασία, γιατί είναι απαιτητική. Προσέξτε αυτούς τους αριθμούς. Έχω ένα σύνολο αριθμών, δεν έχουν κάποια λογική, μου τους δίνει κάποιος, υπάρχουν σε μια λίστα αριθμών και με ρωτά κάποιος, εδώ, εάν υποθέσεις ότι είναι διατεταγμένη από τον μικρότερο προς τον μεγαλύτερο. Σου το λέω αυτό για να μην νομίζεις ότι σου κάνω πλάκα, ότι κρύβεται κάποιο κόλπο, ότι δεν το τυρώ. Είναι από τον μικρότερο προς τον μεγαλύτερο. Υπάρχει εδώ μέσα ο αριθμός 32. Πώς θα το κάναμε συμβατικά, είναι το ίδιο με το να πούμε ανάμεσα στους, πόσοι είσαστε εδώ, χονδρικά, 80% άτομα ας πούμε, έστω ανάμεσα στους 100, υπάρχει κάποιος του οποίου το πρώτο γράμμα του μικρού του ονόματος είναι το Α. Υποθέτουμε πως ναι, αλλά εάν δεν ξέρω, επειδή δεν είσαστε σε μια διατεταγμένη σειρά, δεν έχετε καθίσει δηλαδή έτσι ώστε αυτοί που έχουν ως πρώτο γράμμα το Α να είναι δεξιά, δίπλα τους η Β, δίπλα τους η Γ, μέχρι το Ω, ώστε αμέσως να τους εντοπίσουμε, έτσι δεν είναι. Πρέπει να ρωτήσουμε το καθένα εξαιχωριστά, σωστά. Άρα, αν έχω 100 στοιχεία, πόσους ελέγχους πρέπει να κάνω, 100. Αν έχω 1000 στοιχεία, 1000 ελέγχους. Τι πρόβλημα είναι αυτό? Δεν μοιάζει με το προηγούμενο. 1000 στοιχεία, 1000 έλεγχοι. Έχω άλλους τρόπους να το κάνω αυτό, εάν ξέρω ότι τα στοιχεία μου είναι διατεταγμένα το μικρότερο προς το μεγαλύτερο. Δηλαδή, ξέρω ότι μεταξύ 100 ανθρώπων, αν κάνω 100 ερωτήσεις, θα βρω την απάντηση. Σωστά. Το ζήτημα είναι, εάν αυτούς τους έχω διατεταγμένους, όπως εδώ, μεταξύ αυτών των αριθμών, αν ψάξω, κάνω τον έλεγχος στον καθένα, τι σημαίνει έλεγχος για τον καθένα, παίρνω την ποσότητα που μου δίνουν και πηγαίνω. Είσαι εσύ στη θέση 1 ίσο με 32, όχι στη θέση 2, είσαι στη θέση 3, στη θέση 4, για να δω αν υπάρχει θέση αυτής της λίστας, αυτού του διανύσματος αριθμών, που φιλοξενεί, την τιμή 32. Ξαναρωτό, υπάρχει τρόπος να το κάνω αυτό πιο αποτελεσματικά, να μην χρειαστεί να κάνω πόσους ελέγχους έχω εγώ, 10, 20, 30, 50, 100. Λοιπόν, λέει εδώ ο συνάδελφός σας κάτι, το οποίο θα πρέπει να εξηγήσουμε. Όταν έχω διατεταγμένους τους αριθμούς μου, ένας τρόπος για να το κάνω αυτό είναι ο εξής, να πω, παίρνω τον μεσαίο αριθμό από τη λίστα, παίρνω τον μεσαίο αριθμό, που εδώ είναι το 56. Και λέω, ο αριθμός που ψάχνω είναι μεγαλύτερος ή μικρότερος από το 56. Είναι μικρότερος. Άρα, το δεύτερο μισό, σας θυμίζει κάτι, η μέθοδος της διχοτόμησης, έτσι, ή η διαδική μέθοδος, η αδικία αναζήτηση. Το δεύτερο μισό, μπορώ να το πετάξω. Δεν υπάρχει περίπτωση να ανακοιμάσω ο αριθμός, γιατί, διότι μου έχουν πει ότι είναι διατεταγμένο το μικρότερο στο μεγαλύτερο. Άρα, με μία κίνηση, ξεφορτώθηκα τους μισούς ελέγχους. Φοβερό, δεν είναι. Σκεφτείτε το λίγο, δηλαδή. Είναι πραγματικά εκπληκτικό. Με τη μία κίνηση, οι μισοί έλεγχοι έφυγαν από πάνω μου. Πάω μετά στο μισό του μισού, στο μεσαίο στοιχείο του πρώτου μέρους, το 31. Είσαι εσύ μεγαλύτερο ή μικρότερο στοιχείο από αυτό που ψάχνω, φτου για την αρχή. Εδώ είναι μικρότερο. Άρα, πετάω εκείνο το σκέλος. Με αυτόν τον τρόπο, λοιπόν, ξεκινώ από μια τεράστια λίστα, την κόβω στη μέση, αυτή την ξανακόβω στη μέση, αυτή την ξανακόβω στη μέση. Και βέβαια, πλέον, το ερώτημα είναι το εξής. Πόσες φορές θα κόψω στη μέση? Πόσες φορές θα κόψω στη μέση? Μπορούμε να το υπολογίσουμε. Έχουμε κάποια εικόνα, προσέξτε. Εάν έχω ένα σύνολο από νη στοιχεία, για να το γράψουμε λίγο, για να δούμε τι γίνεται, να το κάνουμε με ένα συγκεκριμένο παράδειγμα και μετά να προσπαθήσουμε να το γενικεύσουμε. Εάν έχω λοιπόν, θα προκύψει μια λογαρυθμική σχέση. Για να δούμε πώς θα μας προκύψει αυτή η σχέση τώρα. Είναι στοιχεία που ξέρω ότι κάποια από εσάς τα έχετε δει στο επίπεδο Λυκείου, αλλά οι περισσότεροι θεωρώ πως δεν τα έχετε δει. Αυτό που συμβαίνει είναι το εξής. Για παράδειγμα, 10 αριθμούς και ας δουλέψω με συγκεκριμένους αριθμούς για να είμαστε 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Ωραία. Έχω λοιπόν 10 αριθμούς και ψάχνω να βρω κάποιον συγκεκριμένο εδώ. Αρχικά θα κόψω στη μέση και αυτό θα το κάνω με ένα συγκεκριμένο τρόπο κάθε φορά. Εάν το σύνολο των αριθμών είναι ζυγό, τότε χωρίζεται απευθείας σε δύο εισάριθμα υποσύνολα. Εάν δεν είναι ζυγός αριθμός το σύνολο των αριθμών, τότε θα είναι 11, για παράδειγμα, εδώ. Θα πρέπει να ελέγξω το μεσαίο στοιχείο αν είναι αυτό που ψάχνω και αν είναι καλός, αν όχι θα πάρω το πρώτο μισό ή το δεύτερο μισό. Συμφωνούμε? Αν, όμως, είναι ζυγός αριθμός, τότε το κόβω στη μέση για πρέπει να ελέγξω την άκρη του ενός, το τέλος του ενός διαστήματος και την αρχή του άλλου. Ή, αλλιώς, τη μέση τιμή των δύο και να συγκρίνω με αυτό που ψάχνω. Και τα δύο μπορώ να τα κάνω. Κάθε προσέγγιση ισχύει. Άρα, λοιπόν, αν έχω 10 αριθμούς ή, αν θέλετε, 100 ηχείλιους, τότε οι 1000 αριθμοί θα γίνουν στην πρώτη διαίρεση πόση 250. Στη δεύτερη διαίρεση θα γίνουν 125. Στην τρίτη διαίρεση θα γίνουν χονδρικά 62. Στην τέταρτη διαίρεση θα γίνουν 31. Στην πέμπτη θα γίνουν… Ξανά. Είναι 1000. Πρώτη διαίρεση 500. Σωστά. Δεύτερη 250. Τρίτη διαίρεση 125. Τέταρτη διαίρεση 62. Πέμπτη διαίρεση 31. Έκτη διαίρεση 15. Δεκαπέντε. Έβδομη διαίρεση 7. Όγδοη διαίρεση 3. Στην ένατη διαίρεση το έχουμε βρει. Άρα, αντί να κάνουμε 1000 συγκρίσεις, έτσι δεν είναι, χονδρικά το περιγράφω, με λιγότερες από 10 συγκρίσεις έχουμε τελειώσει. Στη γενική περίπτωση, η κατάσταση είναι η εξής, και τώρα πρέπει να σας το περιγράψω αυτό. Είχαμε δει ακριβώς, είμαστε ακριβώς στη στιγμή όπου από μία λίστα αδιατεταγμένων αριθμών, ζητούσαμε να βρούμε έναν συγκεκριμένο και αναρωτιόμασταν εάν υπάρχει διαδικασία υπολογιστική, η οποία να το κάνει αυτό, δηλαδή να βρίσκει, μάλλον να αποφαίνεται εάν ο ζητούμενος αριθμός βρίσκεται εντός της λίστας ή όχι, με έναν τρόπο πιο αποτελεσματικό από το να ψάχνουμε τον κάθε αριθμό ξεχωριστά. Σε επίπεδο αλγοριθμικό, αυτή είναι μια διαδικού τύπου αναζήτηση, δηλαδή συνεπάγεται πως σπάμε την λίστα στα δύο κάθε φορά, συγκρίνοντας με το εκάς τότε μέσω της, και αυτό που πρακτικά κάνουμε και περιγράφει ο αλγόριθμος που βλέπετε αριστερά σας, και θέλω να τον δείτε σε αυτή τη μορφή, διότι σε πολλά από τα βιβλία που κυκλοφορούν αυτή η μορφή τύπου ψευδοκώδικα είναι η μορφή που συναντάτε. Ξεκινούμε ουσιαστικά με το ότι θεωρούμε πως έχουμε μια λογική μεταβλητή, την found, η οποία έχει την τιμή false, άρα εξ ορισμού δεν υπάρχει ο αριθμός στη λίστα, και αμέσως μετά, βαφτίζοντας τον πρώτο αριθμό στη λίστα ως 1 και τον δεύτερο ως ν, έχουμε μια δομή ελέγχου, η οποία κάνει το εξής, δείτε, αυτή εδώ είναι η δομή ελέγχου από το όσο μέχρι το τέλος του όσο, και αυτό που κάνει είναι το εξής, όσο η τιμή της first, η οποία αρχικά τίθεται ίση με 1, είναι μικρότερη από την τιμή της last, η οποία αρχικά τίθεται ίση με ν, ίση με τον αριθμό των στοιχείων μέσα στη λίστα που ψάχνουμε. Και η found είναι false, αυτό που κάνουμε είναι ότι ορίζουμε μια καινούργια M μεταβλητή, η οποία είναι το στρογγυλεμένο προς τα κάτω ακέραιο μέρος του last in first διά δύο, και εάν το χ είναι το στοιχείο του διανύσματος στη θέση μη στο μέσο δηλαδή, τότε η found είναι true, αυτό δεν κάνουμε εμείς, προσέξτε, διαφορετικά χωρίζουμε τη λίστα στη μέση, έχουμε λοιπόν τη λίστα ρυθμών k ίσο με 3, 5, 8, 13, 38, 102, 1084, έστω. Αρχικά λοιπόν, εδώ έχω first ίσο με 1, last ίσο με το ν, το οποίο εδώ είναι πόσο, έχω 2, 4, 6, 7 στοιχείες στη λίστα μου, το last είναι 7, και άρα λοιπόν για first ίσον 1, last ίσον 7 και found ίσον false δεν υπάρχει ο αριθμός που ψάχνω στη λίστα, έστω ότι ψάχνω τον αριθμό 9. Ψάχνω τον αριθμό λοιπόν 9. Τότε αρχικά υπολογίζω το M που είναι last sin first δυα δύο στον κυλεμένο προς τα κάτω, εδώ είναι 1, sin 7, 8, δυα δύο, τέσσερα, άρα υπολογίζω ως τον νεο αυτό, τη νέα αυτή θέση, M, 1, sin 7, δυα δύο, ίσον τέσσερα και ελέγχω αρχικά εάν το στοιχείο που ψάχνω βρίσκεται στη θέση τέσσερα. Ελέγχω δηλαδή το κ του μ. Βρίσκεται στη θέση τέσσερα, 1, 2, 3, 4. Βρίσκεται το 9 στη θέση τέσσερα, όχι. Εάν βρισκόταν τότε αυτόματα I found θα γινόταν true, μπορείτε. Διαφορετικά εάν το X που ψάχνω είναι μικρότερο από την θημή στη θέση τέσσερα, η περίπτωσή μας, θέτω last is on M πλην 1. Δηλαδή πλέον η νέα τιμή της last δεν είναι 7, είναι η 4 μειών 1. 1, 2, 3, 4 μειών 1. Γιατί, διότι έχω ελέγξει το τέταρτο στοιχείο αλλά που κλείται έναν αυτό. Οπότε πλέον περιορίζω στο προηγούμενο που είναι το 8 εδώ. Άρα το last γίνεται πλέον 1, 2, 3. 4 μειών 1 ίσον με 3. Διαφορετικά το first γίνεται M συν 1 και επαναλαμβάνεται αυτός ο έλεγχος με αυτό τον τρόπο, αυτό που μπορώ να πετύχω, είναι κάθε φορά να τραβώ τα όρια του διαστήματος προς την περιοχή που βρίσκεται η τιμή που ψάχνω, κόβοντας το διάστημα αρχικά στο μισό, μετά στο μισό του μισού και πάλι λέγοντας. Και βέβαια εδώ θα δούμε τη θέση μου στον επόμενο έλεγχο. Έχω πάλι το first μικρότερο του last βέβαια. Το 1 είναι μικρότερο του 3. Το found συνεχίζει να είναι false. Βέβαια ισχύει. Άρα θα βρω τώρα το M που είναι last συν first, 1 συν 3. Προστά. Νάτο, 2 2. Άρα το καινούριο M είναι τώρα 1 συν 3 2 2 ίσομαι 2. Βρίσκομαι πλέον σε αυτό το διάστημα. Εδώ δηλαδή έχω περιοριστεί. Ελέγχω εάν ο αριθμός που ψάχνω βρίσκεται στη θέση του καινούριου M. Το K του M, το K του 2 είναι το 9. Όχι, είναι το 5. Αφού λοιπόν είναι το 5, τότε είναι μεγαλύτερο το 9. Λοιπόν το X ίσομαι το K του M. Όχι, είναι το X μικρότερο από το K του M. Το K του M είναι 5, το X είναι 9. Όχι, αφού λοιπόν δεν ισχύει αυτό, το first γίνεται M συν 1. Το first γίνεται M συν 1. Πόσο είναι το M? 2. Συν 1, 3. Νέα τιμή του first, 3. Τρέχωσα τιμή του last, 3. Τρέχωσα τιμή του found, false. Είναι πλέον first μικρότερο ίσο του last. Είναι μικρότερο ίσο. Το 3 είναι μικρότερο ίσο του 3. Είναι το found, false βεβαίως. Από την αρχή. Ποιο είναι το M που έχω τώρα? 2. Ποιο είναι το first, 3. Το last, 3. Άρα το καινούργιο M, first συν last δια 2. Θα είναι 3. Ελέγχω λοιπόν. Είναι το K στη θέση 3. Αυτό που ψάχνω. Όχι. Είναι το X μικρότερο από αυτό το K στη θέση 3. Όχι. Είναι μεγαλύτερο. Είναι το 9 αυτό που ψάχνω. Είναι μεγαλύτερο από το K στη θέση 3. Άρα θα πάω στο first ίσον M συν 1. Η νέα τιμή του first λοιπόν πόσο θα γίνει? 3 συν 1 ίσο με 4. Στο νέο λοιπόν κύκλο τρεξήματος του αλγορίθμου, όταν η τιμή first είναι 4, η τιμή last δεν άλλαξε, παραμένει 3, η τιμή found παραμένει false, αλλά όταν τώρα θα τρέξω τον έλεγχο, είναι το first μικρότερο ίσιο του last. Όχι. Αυτό λοιπόν πρακτικά σημαίνει ότι δεν έχω βρει τον αριθμό που αναζητώ μέσα στη συγκεκριμένη λίστα. Μα τούτε λοιπόν ο έλεγχος και το found, αν το found είναι true τότε δίνω την θυμή, διαφορετικά παράγω το σχετικό μήνυμα. Βλέπουμε λοιπόν ότι αυτή η διαδικασία τρέχει έτσι ώστε, ξαναλέω, να χωρίζει το διάστημα στη μέση κάθε φορά και με τον κατάλληλο τρόπο, ώστε στο τέλος να μπορούμε να αποφανθούμε με απόλυτη βεβαιότητα, αυτό κατά πόσο είναι true ή false το γεγονός πως βρίσκεται ο αναζητούμενος αριθμός μέσα στη λίστα που μας έχει δοθεί. Ερωτήσεις εδώ. Αυτή η άλλα και που κάναμε το last που πήγαμε, ξέρω, σε τέσσερα πληλημένα, θα ερωτήσουμε μαζί με συνέχεια περί τα πληλημένα. Δεν μας κοστίζει αν τόσο υποδοχιστούμε. Μπορούμε να το κουρδίσουμε καλύτερα. Σας δείχνω μια βασική λογική εδώ. Εννοείται ότι μπορούμε να έχουμε και κάποια βελτιστοποίηση εδώ. Με ενδιαφέρει να δω ερωτήσεις και απορίες επί της διαδικασίας υπολογισμού, γιατί πλέον πρέπει να είμαστε σε θέση να αντιληφθούμε για να μπορέσουμε να υπολογίσουμε τα βήματα. Αυτό ακριβώς, αυτή η αγγείλη που βλέπετε εκεί δεν είναι ακριβώς αγγείλη, είναι υπολογισμός. Σημαίνει ότι παίρνεις κουρεμένο ακέραιο. Άρα, αν το αποτέλεσμα της πράξης είναι 3,2, θα πάρεις το 3 σαν αποτέλεσμα. Πάντα λοιπόν λαμβάνεις ακέραιο ρυθμό. Σωστά, διαφορετικά δεν μπορείς να κάνεις τον υπολογισμό. Λοιπόν, τώρα το ερώτημα είναι πόση είναι η υπολογισμή μας. Η υπολογισμή μας είναι ένας λογάριθμος με βάση το 2 του ν. Και αυτό προκύπτει εξαιτίας του ότι χωρίζουμε το διάστημα στην μέση. Άρα λοιπόν, κάθε φορά, οι σημαντικοί παράμετρας εδώ είναι ποια, ότι κάνουμε μία σύγκριση και μία ακόμη. Σε κάθε βήμα κάνουμε δύο συγκρίσεις. Μία πράξη, εδώ, έναν υπολογισμό του m, κάθε φορά και συγκρίσεις. Αν το χ είναι ίσο με το κ του μ, διαφορετικά είναι ένα μεγαλύτερο ή μικρότερο. Συνολικά, λοιπόν, σε κάθε βήμα, πόσες στοιχειώδεις ενέργειες επιτελούμε, πόσες στοιχειώδεις πράκτης εκτελούμε. Ένα, θα κάνω αυτόν τον έλεγχο, κάθε φορά, σωστά. Δεύτερο, θα κάνω και αυτόν τον έλεγχο, όσο λοιπόν, άρα έχω αυτούς τους δύο ελέγχους. Θα υπολογίσω καινούριο m, τρία πράγματα. Θα κάνω τον έλεγχο αν το χ είναι ίσο με το κ του μ, τέσσερα πράγματα. Αν είναι το χ μικρότερο, πέντε, διαφορετικά, άρα θέλω πέντε ενέργειες. Πέντε ενέργειες έχω τελειώσει τη δουλειά μου σε κάθε βήμα, έτσι δεν είναι. Κάθε βήμα λοιπόν συνοδεύεται από πέντε ενέργειες. Το θέμα είναι πόσα είναι τα βήματα. Αυτό είναι το σημαντικό ερώτημα. Και εδώ το θέμα είναι να υπολογίσουμε συναρτήση του ν, τον αριθμό των δημάτων. Πώς προκύπτει λοιπόν ο λογάριθμος του 2, με βάση το 2. Διότι όταν έχω ένα αρχικό διάστημα με ν αριθμούς, μετά το χωρίζω σε ν δεύτερα, αμέσως μετά χωρίζω το ν δεύτερα στα δύο, δηλαδή σε ν τέταρτα, μετά χωρίζω το ν τέτατα στα δύο, δηλαδή σε ν όγδωα, γενικά χωρίζω το διάστημα των αριθμών σε ν προς δύο ή στην ν. Έτσι δεν είναι. Πράγμα που σημαίνει ότι αν θέλω να βρω τον αριθμό του βήματος, ή μάλλον, συγγνώμη, σε ν προς δύο ή στην κ, όπου κ το βήμα υπολογισμού στο οποίο βρίσκομαι. Το πρώτο βήμα υπολογισμού είναι το να χωρίσω τη λίστα μου στη μέση, τους χίλιους αριθμούς μου στη μέση. Το δεύτερο βήμα είναι να χωρίσω τους είδη μισούς, τους πεντακόσχους στη μέση. Είναι δύο στο τετράγωνο λοιπόν το 4, το 8 είναι δύο στην τρίτη, δύο στην κ. Άρα πώς εγώ μπορώ να βρω, έχω το ν προς δύο ή στην κ, το οποίο πρέπει να είναι περίπου ίσο με 1. Όταν αυτό γίνει 1, σημαίνει ότι έχω κόψει τόσο πολύ το μεγάλο διάστημα, ώστε έχω βρει τον αριθμό μου ή έχω αποφανθεί για το ότι δεν υπάρχει. Πρακτικά λοιπόν αυτό σημαίνει ότι το 2 στην κ πρέπει να είναι ν, άρα αν λογαριθμίσω και τα δύο σκέλη ως προς δύο, λογάριθμος του 2 στην κ μου δίνει τον λογάριθμο με βάση 2 του ν και στη βάση αυτού το κ, ο αριθμός των βημάτων που θέλω δηλαδή, είναι ο λογάριθμος με βάση 2 του ν. Γι' αυτό το λόγο προκύπτει η λογαριθμική συνάρτηση ως συνάρτηση υπολογιστικής πολυπλοκότητας χρόνου. Ξέρουμε λοιπόν, ξαναλέω, ότι κάθε βήμα υπολογισμού συνεπάγεται στις διακοιμένες ενέργειες τις ίδιες κάθε φορά. Πέμπτος έλεγχος. First and last. Δεύτερος έλεγχος. Found, είσαι false ή όχι. Τρίτο πράγμα, καινούργιο M. Τέταρτο πράγμα, έλεγχος αν το χ είναι το κ στην θέση μ. Πέμπτος έλεγχος. Πέμπτο πράγμα ο έλεγχος. Αυτά τα πέντε πράγματα τα κάνουμε κάθε φορά, δεν τα αλλάζουμε, επανελαμβάνονται. Άρα, πέντε φορές επί τον αριθμό των δυμάτων. Οπότε λοιπόν, ξαναλέω, τι είναι σημαντικό εδώ, να υπολογίσουμε τον αριθμό των δυμάτων. Και ο αριθμός των δυμάτων προκύπτει πάλι με ποιον τρόπο. Έχω τα 10, 20, 50, 100, 1.000, 1 εκατομμύριο στοιχεία στη λίστα μου, τα ν. Τα χωρίζω στη μέση, γίνονται ν δεύτερα. Χωρίζω τα μισά στη μέση, γίνονται ν τέταρτα. Γενικά γίνονται ν διαδύο εις την κάπα, όπου κάπα το βήμα χωρισμού στη μέση. Το πρώτο βήμα χωρισμού, δύο εις την πρώτη. Το δεύτερο βήμα χωρισμού, δύο εις την δευτέρα. Το τρίτο, δύο εις την τρίτη. Το κάπα βήμα χωρισμού στη μέση, δύο εις την κάπα. Όταν αυτό το πράγμα γίνει περίπου ίσο με το ένα, τότε έχουμε αποφανθεί πλήρως. Λογαριθμίζω τα δύο μέρη και έτσι προκύπτει ότι ο αριθμός των βημάτων υπολογισμού, ίσουτε με τον λογαριθμό του ν, του αριθμού των στοιχείων, με βάση το δύο. Αυτή λοιπόν είναι η λογαριθμική συνάρτηση πολυπλοκότητας χρόνου, της λεγόμενης διαδικής αναζήτησης. Υπάρχουν και άλλου είδους συναρτήσεις που εμπλέκουν τον λογαριθμό με βάση στο δύο. Ένα παράδειγμα είναι η ταξινόμηση με επιλογή. Δηλαδή, έστω ότι έχω έναν αταξινόμητο πίνακα, έχουμε προβλήματα αυτού του τύπου. Δηλαδή, μας δίνουν ένα σύνολο αριθμών, εδώ ένα διάνισμα μάλιστα, αταξινόμητο. Πώς να το πω, χήμα, καμία σειρά. Και μας λένε, ταξινομείστε σε μη φθύνουσα σειρά, σε αύξουσα δηλαδή. Άρα θα είναι ίσα τα στοιχεία το ένα δίπλος το άλλο ή θα είναι σε αύξουσα σειρά. Πώς το κάνω αυτό, για να το σκεφτούμε λίγο. Έχω ένα σύνολο από αριθμούς και προφανώς θα πρέπει να ελέγξω τον κάθε αριθμό σε σχέση με όλους τους υπόλοιπους. Δεν μπορεί διαφορετικά να αποφανθεί κανείς, έτσι δεν είναι. Διότι δεν έχω ιδέα για το πού μπορεί να βρίσκεται μεγαλύτερος ή μικρότερος μέσα στη λίστα. Άρα αναγκαστικά θα τους αρρώσω όλους. Τι ξέρω όμως, ότι κάθε φορά που θα πάρω τον πρώτο αριθμό θα σαρώσω για όλους τους υπόλοιπους, αυτός ο αριθμός φέρνει από τη μέση. Την επόμενη φορά το σύνολο των αριθμών προς σάρωμα δεν είναι το αρχικό, είναι μικρότερο. Άρα, ακούμε ιδέες, επανάληψη λοιπόν, και θα πρέπει κάθε φορά το μήνυμα των υπόλοιπων υποχείων. Δηλαδή, την πρώτη φορά θα τρέξει για όλους τους υπόλοιπους. Θα πάρει το ελάχιστο. Την δεύτερη φορά θα το βάλει στην πρώτη θέση, στην i θέση. Την επόμενη φορά που θα τρέξει για το i σαν 2 θα εξαιρέσει το i είναι 1 στοιχείο. Θα το κάνει από το επόμενο. Άρα λοιπόν λέει ο συνάδελφός σας ότι θα πάρω και θα σαρώσω όλο τον πίνακα για να βρω το ελάχιστο. Θα το βάλω πρώτο. Θα το πάρω από τη θέση του και θα το βάλω πρώτο. Μετά θα ξεκινήσω να σαρώνω όλο τον πίνακα εκτός από την πρώτη θέση, γιατί ξέρετε εκεί υπάρχει ελάχιστο. Θα βρω το επόμενο ελάχιστο. Θα το βάλω πωπ. Θα πρέπει να κρατήσουμε το στοιχείο της πρώτης θέσης κάθε φορά. Άρα θα τα βάζουμε συνεχώς μπροστά. Άρα λοιπόν θα ψάχνουμε το υπόλοιπο και το υπόλοιπο και το υπόλοιπο. Άρα ψαρεύουμε με μια κατάλληλη μέθοδο έβρεσης του ελαχίστου το ελάχιστο και θα το τοποθετούμε το ένα διπλώς το άλλο. Αυτό ουσιαστικά κάνουμε εδώ. Η γραφή είναι πάρα πολύ γενική. Οπότε λοιπόν, πρακτικά, αυτό που κάνουμε είναι ότι βρίσκουμε το ελάχιστο, βρίσκουμε στη χρήση μας διαδικασίες έβρεσης. Έχουμε συναρτήσει σε MATLAB και σε άλλες γλώσσες έβρεσης ελαχίστου. Τώρα το βάζουμε μπροστά, είτε στον ίδιο πίνακα, είτε σε ένα διαφορετικό που είναι ακόμα πιο εύκολο. Δημιουργούμε δηλαδή έναν δεύτερο πίνακα με αριθμό στοιχείων, ίσο με τον πίνακα τον αριθμό που θέλουμε να ταξινομίσουμε. Και με το που θα βρούμε το ελάχιστο το βάζουμε πρώτο στον καινούριο πίνακα, το δεύτερο δεύτερο στον καινούριο πίνακα, το τρίτο τρίτο στον καινούριο πίνακα και πάει λέγοντας. Γιατί με αυτόν τον τρόπο αριθμούμε πολύ εύκολα τα στοιχεία. Αυτό, εάν υπολογίσουμε πάλι την υπολοιπλοκότητά του, προκύπτει ότι είναι ένα πρόβλημα παραπλήσιας υπολογιστικής υπολοιπλοκότητας, απλά πολλαπλασιάζουμε τον λογάριθμο με τον ί. Άρα, είναι ένα πρόβλημα που κοστίζει περισσότερο ή λιγότερο ας πω στον χρόνο, σε σχέση με το προηγούμενο. Το προηγούμενο, αν έχω χίλια στοιχεία, είναι λογάριθμος με βάση 2 του χίλια. Εδώ, αν έχω χίλια στοιχεία, είναι χίλια επί λογάριθμος με βάση 2 του χίλια. Άρα, προφανώς, αυτό το πρόβλημα υπολογιστικά κοστίζει περισσότερο. Τι σημαίνει αυτό ότι θέλω περισσότερο χρόνο. Άρα, θέλω πόσο λιγότερο χρόνο, να το πω αλλιώς, αν έχω τώρα τα δύο προβλήματα. Πάω και συγκρίνω προβλήματα πλέον και μάλλον για πρώτη φορά στη ζωή μας το κάνουμε αυτό. Έχω από τη μία, τον τηλεφωνικό κατάλογο ή αλλιώς, έχω ένα λεξικό, στο οποίο προφανώς όλα τα λήματα έχουν μπει με αλφαβητική σειρά, 10.000 λέξεων. Και προσπαθώ να δω στα ελληνικά, εάν η λέξη αυγοτάραχο βρίσκεται μέσα σε αυτήν την σειρά λέξεων. Ας το κάνουμε αυτή τη μέθοδο της διαδικής αλληλευθίσθησης, θα βρω τη μεσαία λέξη από τις 10.000, θα ελέγξω αν αυτή είναι μεγαλύτερη πάνω ή κάτω από την αυγοτάραχο και πάει λέγοντας. Τι πολυπλοκότητα έχει, άρα πόσα υπολογιστικά βήματα, θέλουμε περίπου λογάριθμος με βάση 2 του 10.000, που πόσο περίπου είναι, ας κάνει κάποιος μια εκτίμηση, λογάριθμος με βάση 2 του 10.000, με κανένα υπολογιστάκο, οτιδήποτε. Εδώ, έτσι, μια εκτίμηση μπορούμε να κάνουμε εδώ. Αν ήταν λογάριθμος με βάση το 10, του 10.000 θα ήταν εύκολο, λογάριθμος με βάση 2 είναι λίγο πιο πολυπλοκό. Εάν έχω τώρα το ανάποδο πρόβλημα, έχω 10.000 λέξεις και θέλω να τις βάλω στη σειρά από την πρώτη μέχρι την τελευταία αλφαβητικά, πόσο θα μου κοστίσει αυτό σε επίπεδο χρόνου, θα μου κοστίσει 10.000 φορές περισσότερο από το να βρω μια συγκεκριμένη λέξη στο ταξιδιωμένο λεξικό, διότι είναι το ένα υπολογιστικής πολυπλοκότητας λογάριθμος με βάση 2 του 10.000, έτσι δεν είναι, και το άλλο είναι μη επί λογάριθμος, άρα 10.000 φορές επί αυτό, οπότε το δεύτερο πρόβλημα είναι 10.000 φορές πιο κοστοβόρο από πλευράς χρόνου. Αναμενόμενο μεν, εντυπωσιακό δε θα έλεγα. Πλωβλήματα που έχουν άλλου είδους συναρτήσεις υπολογιστικής πολυπλοκότητας, για να δούμε. Κοιτάξτε αυτό, είναι μία επαναληπτική διαδικασία που τρέχει για i από 1 ως ν, για j από 1 ως ν, και ουσιαστικά υπολογίζει το γινόμενο δύο στοιχείων ενός πίνακα. Πράγμα που σημαίνει ότι, πηγαίνω να σας το δείξω, για i από 1 ως ν και για j από 1 ως ν και για k από 1 ως ν, υπάρχει ένα σύνολο από πράξεις. Αυτό τι σημαίνει, για να το δούμε. Βλέψτε, ζητήσω την υποίθηση εσάς των τριών μπροστά. i, j, k, είσαι το i, από 1 ως ν, λαμβάνεις την τιμή 1, δώσεις πάσα στο επόμενο δίκτη, το j, που θα λάβει την τιμή 1, σωστά, και θα δώσεις πάσα στο επόμενο δίκτη για να ξεκινήσει να μετά, είσαι το, ποιος είναι ο τρίτος δίκτης, k, για να μετρήσεις από τα 1. Πόσες φορές θα μετρήσεις, σε ποια τιμή πρέπει να φτάσεις για να αλλάξει η τιμή ο δίκτης που σου έδωσε την πάσα. Θα πάσαι από το 1 έως το ν, έτσι δεν είναι. Με το που θα τελειώσεις, τελείωσες τη δουλειά σου. Ο δίκτης που σου έδωσε την πάσα θα πει, εγώ σου έδωσα πάσα για j1. Άρα, ξανακάνετε ίδια για j2, ξανά υπάλλασες ένα. Για j3, για j4, πόσες φορές θα το κάνεις αυτό. Κάθε φορά κάνεις πόσες φορές την επανάληψη. Νή. Πόσες φορές θα το κάνεις, όταν σου πει ο προηγούμενος δίκτης. Νή, επεινή, νή, τετράβουνο. Πόσες φορές ο προηγούμενος δίκτης θα λάβει εντολή από τον πρώτο δίκτη να το κάνει. Νή, επεινή, επεινή. Άρα εδώ, πόσα είναι τα βήματα υπολογισμού, νή στην τρίτη. Είναι η κυβική συναρτηση υπολογιστικής πολυπλοκότητας. Οπότε λοιπόν, σε μια τέτοια περίπτωση, έχω νή στην τρίτη ως τη συναρτηση εκτίμησης του χρόνου υπολογισμού. Επίσης, μπορώ να δω άλλου είδους συναρτήσεις που έχουν μεγαλύτερο ενδιαφέρον υπό την έννοια πως δίνουν μεγαλύτερους χρόνους υπολογισμού. Έστω ότι έχω ένα σύνολο νή αριχμών. Υπάρχει υπό σύνολό του τέτοιό αυτό το άθλισμα των στοιχείων του να εισούνται με δεδομένο αριθμό. Πρακτικά, ας πούμε ότι έχω εγώ ένα σύνολο S που αποτελείται από τους πρώτους 100 φυσικούς. Να το κάνω συγκεκριμένο. Έχω δηλαδή το σύνολο S που αποτελείται από τους αριθμούς 1, 2, κτλ. 100. Είναι οι 100 πρώτοι φυσικοί αριθμοί, σωστό. Ερώτημα. Υπάρχει υπό σύνολο αυτού του συνολου το οποίον έχει στοιχεία που το άθλισμά τους να εισούνται με το 666. Πώς θα απαντήσω σε αυτό το ερώτημα. Φαίνεται να υπάρχει, ναι. Αλλά επειδή δεν μπορώ με βεβαιότητα να απαντήσω στο ερώτημα αυτό, θα πρέπει αναγκαστικά να δημιουργήσω όλα τα πιθανά υποσύνολα. Έτσι δεν είναι. Άρα το 1 μόνο του. Το 1 με το 2, το 1 με το 3, το 1 με το 4, το 1 με το 5, το 1 με το 6, το 1 με το 7, το 1 με το 8, μέχρι το 100. Ωραία. Πάμε τώρα. Το 2 με το 3, το 2 με το 4, το 2 με το 5, το 2 με το 6 και τα λοιπά. Έτσι. Άρα το 1, το 2, το 3 με το 4, με το 5, με το 6, με το 7, με το 8. Όλα αυτά λοιπόν τα δυνατά υποσύνολα είναι τελικά ίσα με το 2 η στινή. Εάν δεν έχω άλλον τρόπο να υπολογίσω το υποσύνολο που αναζητώ, θα πρέπει να υπολογίσω όλους αυτούς τους συνδυασμούς, οπότε αναγκαστικά η υπολογιστική μου πολυπλοκότητα καθορίζεται αυστηρά από το ότι έχω 2 η στινή συνδυασμούς. Δεν μπορώ λοιπόν να πετάξω απ' έξω κάποιο συνδυασμό. Και αν είναι εκεί μέσα αυτό που ψάχνω, θα κάνω 2 η στινή δουλειές. Τεράστιος αριθμός. Γυρνάμε σε αυτό που λέγαμε πιο πριν, το σκάκι, έτσι, το πρόβλημα του περιοδεύοντος πολιτή είναι λοιπόν της ίδιας υπολογιστικής πολυπλοκότητας αυτό το πρόβλημα. Όπως για παράδειγμα ερωτήματα του τύπου, ανάμεσα στους 100 περίπου φοιτητές που μπορεί να είναι εδώ, υπάρχει υποσύνολο φοιτητών των οποίων η ημερομηνία γέννησης, μάλλον οι ημέρες, γεννήθηκα την πρώτη του μηνός, δεύτερη, τρίτη και τα λοιπά, αυτοί οι αριθμοί, οι ημέρες γέννησης θα δίνουν άθρησμα 8.763. Καμία ιδέα. Πώς μπορούμε να απαντήσουμε σε κάτι τέτοιο. Ή υπάρχει υποσύνολο φοιτητών οι οποίοι να έχουν γενέθλια μεταξύ της πρώτης και της πέμπτης ενός μήνα. Προφανώς. Ποιο είναι αυτό. Μπορώ να το εκτιμήσω. Να έχει δηλαδή το υποσύνολο μια συγκεκριμένη ιδιότητα. Τέτοιους υπολογιστικές πολυπλοκότητες εκθετικού χρόνου βρίσκουμε όταν έχουμε να κάνουμε προβλήματα με προβλήματα όπου εντός ενός συνολου στοιχείων αναζητούμε στοιχεία με συγκεκριμένη ιδιότητα. Από έναν σύνολο λέξεων αναζητούμε αυτές οι οποίες τονίζονται στην παραλίγουσα λέμε τώρα. Έτσι. Αναζητούμε αυτές οι οποίες έχουν λατινική καταγωγή. Ανυζητούμε αυτές οι οποίες πρέπει να έρχονται από το φοιτικό βασίλειο. Όλα αυτά τα προβλήματα αναζήτησης εντός συνολου αριθμών έχουν εκθετική υπολογιστική πολυπλοκότητα. Και γι' αυτό και ο υπολογισμός είναι πάρα πολύ δαπανηρός, κοστοβόρος, διότι είναι δύο ιστιμπί. Τώρα προφανώς μπορούμε να συγκρίνουμε υπολογιστικές πολυπλοκότητες. Κοιτάξτε τι γίνεται. Αν έχω ένα πρόβλημα που έχει γραμμική υπολογιστική πολυπλοκότητα, για ν ίσον 2, 10, 100, 1.000 και 10.000, κοιτάξτε πόσα είναι τα υπολογιστικά βήματα κατεκτήμηση. Αυτό που αναρωτιόμασταν πιο πριν. Ο λογάριθμος με βάση 2 του ν για ν ίσον 10.000 είναι 13,28. Άρα σε 13-14 υπολογιστικά βήματα το βρήκαμε τη λέξη στο λεξικό μας με τη μέθοδο που λέγαμε, έτσι δεν είναι. Δηλαδή, αν θέλουμε να φτιάξουμε αυτή τη λίστα, θέλουμε 10.000 φορές περισσότερα βήματα, θέλουμε 13.000, γιατί είναι ν επί αυτό, έτσι. Τώρα, ν τετράγωνο, ν στην τρίτη, 2 στην ν. Κοιτάξτε, κολοσιαίος αριθμός, έτσι, είναι ασύλληκτο, αυτός ο αριθμός είναι ασύλληκτος, 10 στην 2.500. Δεν υπάρχει αυτό το πράγμα, όπως έμαθα κι εγώ να λέω. Είναι ασύλληπτη υποσότητα, πρακτικά είναι μη υπολογίσιμο μέγεθος. Αυτό σημαίνει δηλαδή ότι είμαστε βέβαιοι ότι ο αλγόριθμος υπολογισμού θα τερματίσει κάποια στιγμή, είμαστε βέβαιοι ότι εμείς δεν θα υπάρχουμε τη στιγμή εκείνη και μπορούμε επίσης να είμαστε βέβαιοι ότι πιθανά και το σύμπανδε θα υπάρχει εκείνη τη στιγμή. Και αυτό βέβαια μας φέρνει σε επαφή με κοσμολογικού, φιλοσοφικού, θεολογικού και άλλου χαρακτήρα ερωτήματα, όπως το κι αν το σύμπανδεν είναι τίποτα άλλο παρά μόνο ένας μεγάλος υπολογιστής, ο οποίος αυτή τη στιγμή επιτελεί υπολογισμούς και αυτό που βλέπουμε είναι το αποτέλεσμα των πράξεων του. Το κλείνω αυτό το θέμα γιατί θα ξεφύγουμε απόλυτα. Έχουμε ευτυχώς έναν γραφικό τρόπο υπολογισμού. Καμπύλες. Βλέπετε πόσο... Τι θέλουμε εμείς, προσέξτε, τι θέλουμε, όλα τα προβλήματά μας θα θέλαμε να είναι κάπως έτσι. Ούτε καν γραμμικά. Τα γραμμικά δεν μας ικανοποιούν. Γραμμικά σημαίνει για 10.000, για ενίσον 10.000, 10.000 βήματα, 10.000 ποσότητες χρόνου. Για 100.000, 100.000. Δεν μας συμφέρει αυτό. Δηλαδή, εάν είναι έτσι και θέλω εγώ να κάνω πράξεις, να ρωτήσω το εξής. Επειδή ο υπολογισμός μιας ορίζουσας με τη μέθοδο Kramer, μπορείτε ήδη εσείς που έχετε κατανού την μέθοδο να το φέρετε στο μυαλό σας και να πιστέψετε αυτό που θα σας πω, ότι έχει υπολογιστική πολυπλοκότητα ίση με το πρόβλημα του περιοδεύοντος πολιτή. Ένα πράγμα που σημαίνει ότι αν σας ζητήσω εγώ να μην πολυήσετε μια ορίζουσα δύο επί δύο, τον είναι δύο, έτσι, θέλετε δύο ιστινή βήματα. Άρα το δύο εις την δύο τρώγεται, έτσι, είναι δύο εις την δευτέρα τέσσερα βήματα. Το δύο εις την, αν είναι, τον ίσο με το εφτά όμως, πόσα βήματα θέλετε και είστε με το χέρι. Γι' αυτό σας είπα, σας στάνει ο χρόνος, αν σας το ζητήσω σε γραφτή εξάσκηση, υποτεθείστο, είναι δύο εις την δύο, εις την δύο, άρα είναι τέσσερα επί δύο. Οχτώ, επί δύο, δεκάξι, επί δύο, τριάντα δύο, εξήντα τέσσερα, εκατόν εικοσιοχτώ βήματα με το χέρι. Άρχιζε και γίνεται αφυγιεινό, έτσι δεν είναι. Οπότε, θέλουμε κάτι τέτοιο εμείς, θέλουμε αυτή την υπολογιστική πολυπλοκότητα. Δηλαδή, όσο πιο πολύ αυξάνει το ν, τόσο εμείς να είμαστε σίγουροι ότι παραμένουμε σε χαμηλές τιμές. Είναι λογ δύο του ν, αυξάνει πολύ αργά, έτσι. Από εκεί και πέρα, δυστυχώς, έχουμε προβλήματα μηχανικού, τα οποία ανήκουν σε αυτές εδώ τις σφαίρες. Είναι τα λεγόμενα προβλήματα εκθετικού χρόνου ή εκθετικής κλάσης υπολογιστικής πολυπλοκότητας. Είδαμε ήδη ότι είναι ευθική μας επιλογή, να σας θυμίσω την μέθοδο υπολογισμού των τιμών της Φιμπονάτση. Θυμάστε πόσο διαφορετικά πράγματα συναντήσαμε. Στη μια περίπτωση εκθετικό χρόνο, στην άλλη περίπτωση γραμμικό χρόνο. Στη μια περίπτωση είμαστε καταδικασμένοι, στην άλλη περίπτωση θα βρούμε λύση. Και βέβαια έχουμε και ενδιάμεσες ποσότητες. Έχουμε από την άλλη, επειδή τα πράγματα γίνονται ακόμη πιο πολύπλοκα και ενδιαφέρονται ταυτόχρονα. Πολλές πολυπλοκότητες, να ήταν μόνο μία, έχουμε την πολυπλοκότητα της καλής, της μέσης και της χείρις της περίπτωσης. Να σας το δώσω ως παράδειγμα. Εάν εγώ ψάχνω σε μια λίστα αριθμών, έναν συγκεκριμένο αριθμό, στους χείριους αριθμούς ψάχνω έναν, ο μέσος χρόνος είναι, είπαμε πόσο, έτσι, 7 βήματα, 8 όσα είπαμε, όσο βγαίνουν. Αλλά υπάρχει περίπτωση να βρω τον αριθμό μου στο πρώτο βήμα. Υπάρχει περίπτωση να βρω τον αριθμό μου στο έβδομο βήμα. Στατιστικά τι συμβαίνει. Δηλαδή, αν εμένα μου δώσουν χίλια φορές λίστες χιλίων αριθμών, ο μέσος όρος δεν θα είναι ούτε το ένα, δεν θα τους βρω αυτούς τους αριθμούς που ψάχνω με το πρώτο βήμα, ούτε θα τους βρω, ούτε θα αποφανθώ, συγγνώμη, για το αν υπάρχουν στη λίστα στο έβδομο βήμα. Άλλες φορές, στο έβδομο, στο έκτο, θα υπάρχει ένας μέσος όρος. Άρα υπάρχει η πολυπλοκότητα της βέλτης της περίπτωσης να σταθώ τυχερός, πάω για λαχείο, να σταθώ άτυχος, πάω πάλι για λαχείο, πάω για ανάποδη, ή να είμαι στο μέσο όρο. Εάν έχω προβλήματα τα οποία λύνω πολλές φορές, με ενδιαφέρει να δω ποιο είναι αυτό το εύρος, έτσι δεν είναι, διότι αλλιώς θα συμπεριφερθώ, αν ξέρω ότι είμαι μεταξύ του 1 και του 7, σε μια πολυπλοκότητα λογαριθμική, αυτός μου δεν είναι μεγάλο, αλλά αν είμαι στην εκθετική, γενικώς χαμένος από χέρι δηλαδή, έχω λοιπόν πολυπλοκότητα καλύτερης μέσης και χείρις της περίπτωσης. Είναι ο αλγόριθμος έρμεο του προβλήματος. Στο παράδειγμα της ακολουθιακής αναζήτησης, αυτό που λέγαμε δηλαδή με τους αριθμούς, φαίνεται ότι υπάρχει μια μέσης συμπεριφορά και γι' αυτό το λόγο μιλούμε και για ασιμπτοτική πολυπλοκότητα, μια πολυπλοκότητα που την προσεγγίζουμε και επειδή στην επιστήμη του μηχανικού, γενικά συζητούμε ή μας ενδιαφέρουν πολλές φορές τα λεγόμενα μεγάλα προβλήματα. Μεγάλα όχι απαραίτητα υπό την έννοια της επίδρασης που έχουν στην τύχη της ανθρωπότητας και στην εξέλιξή της, μεγάλα υπό την έννοια του μεγέθους, πολύ μεγάλοι πίνακες οι οποίοι υπολογίζονται. Να δώσω ένα παράδειγμα, εάν θελήσουμε να υπολογίσουμε αναλυτικά τις κινήσεις του ανθρωπίνου σώματος με μέθοδο πεπερασμένος στοιχείων ή την αντοχή της μοντυλικής μας τύλης, θα φτάσουμε πολύ εύκολα σε πίνακες της τάπελς του 60.000 x 60.000, 70.000 x 70.000. Μιλάμε για τέτοια γραμμικά, θυμάστε είναι μη γραμμικά συστήματα. Εμείς έχουμε λύσει και εσείς έχετε λύσει μέχρι τώρα με το χέρι συστήματα 2x2, 3x3, μέχρι εκεί. Ναι, 60.000 x 60.000 δεν βγαίνει. Και υπολογιστικά ακόμη, εάν με τη φιμπονάτσι μπορώ να φάω τέτοια τρικλοποδιά, με την επίλυση ενός γραμμικού συστήματος μπορώ να υποστώ χειρότερα, έτσι δεν είναι. Άρα πρέπει να διαλέξω κατάλληλα τη μέθοδό μου. Μάθετε λοιπόν το μάθημα της αριθμητικής ανάλυσης για μεθόδους που επιλέγουμε στις συναρτήσεις του χαρακτηριστικού του προβλήματος. Δεν πάμε πάντοτε με την ίδια μέθοδο στο χέρι. Δεν πάς πάντοτε με το ίδιο πριώνι να κόψεις το κάθε υλικό. Πιο γρήγορα θα κόψεις μεταλλικά υλικά με το κατάλληλο εργαλείο, τα ξύλινα με κάτι άλλο, τα πλέξιγκλας με ένα τρίτο, τα πλαστικά με ένα τέταρτο. Αυτά το κατάλληλο εργαλείο, ο κατάλληλος αργόριθμος για προβλήματα κατάλληλής φύσης. Μας ενδιαφέρει λοιπόν το να αναλύουμε την πολυπλοκότητα γιατί με αυτόν τον τρόπο έχουμε καλή εικόνα της τελικής συμπεριφοράς αργορίθμων. Μπορεί για παράδειγμα δύο διαφορετικοί αργόριθμοι να έχουν δύο διαφορετικές συναρτήσεις υπολογιστικής πολυπλοκότητας. Έτσι όπως υπολογίσαμε τα βήματα, να πούμε ότι στη μια περίπτωση μου προκύπτει για ότι είναι 100 φορές το νίο που νει το μέγεθος του προβλήματος, η αριθμή, η διάσταση ενός πίνακα κτλ. ή 0,1 πινή τετράγωνο. Με αυτά λοιπόν τα στοιχεία είδαμε σήμερα τα εξής. Ξεκινώντας από τη Φιμπονάτση, είδαμε μια απλή ακολουθία το πόσο πολύπλοκος μπορεί να γίνει ο υπολογισμός της συναρτήσει του αριθμού των υπολογιστικών βημάτων. Να θυμίσω το ερώτημα εδώ. Υπάρχει καλύτερη μέθοδος από τη γραμμική. Σας λέω πως υπάρχει. Όποιος θέλει μπορεί να την αναζητήσει θα δώσω εξηγήσεις την επόμενη φορά. Πήγαμε μετά με τη βοήθεια του προβλήματος του περιοδεύοντος πολιτή και μιλήσαμε με πρωτοκότητες εκθετικού τύπου, δύο η στινή και τελικά με τη βοήθεια κάποιων άλλων προβλημάτων είδαμε πολυπλοκότητες γραμμικού, εκθετικού και λογαρυθμικού τύπου. Συνεχίζουμε με τις ασκήσεις αυτής της εβδομάδας και την επόμενη εβδομάδα δυνατότερα. |
