Τα Μαθηματικά του Κωσταντίνου Δασκαλάκη

Με την ευκαιρία της πρόσφατης βράβευσης του κου Κωσταντίνου Δασκαλάκη, ας πούμε λίγα λόγια για τα Μαθηματικά για τα οποία έγινε αυτή η βράβευση:

Daskalakis was honored by the International Mathematical Union (IMU) for “transforming our understanding of the computational complexity of fundamental problems in markets, auctions, equilibria, and other economic structures.”
ΜΙΤ News: Constantinos Daskalakis wins prestigious Nevanlinna Prize

Πρόκειται, λοιπόν, για Μαθηματικά που βασίζονται κυρίως στο μαθηματικό αντικείμενο ονομάζεται Θεωρία Υπολογισμού (Theory of Computation) και κυρίως στον κλάδο του που ονομάζεται Θεωρία Πολυπλοκότητας (Computational Complexity Theory).

Αυτά τα μαθηματικά αντικείμενα διδάσκονται σχεδόν αποκλειστικά όσον αφορά το υποχρεωτικό κομμάτι των προγραμμάτων σπουδών, στα τμήματα Πληροφορικής της τριτοβάθμιας εκπαίδευσης – δεν θα βρει κανείς αυτά τα αντικείμενα στην λίστα των υποχρεωτικών μαθημάτων του Μαθηματικού του ΕΚΠΑ για παράδειγμα, τουλάχιστον έτσι όπως αναφέρει ο οδηγός σπουδών 2017-2018 ο οποίος ανακτήθηκε στις 6/8/2018. Εξάλλου, όπως ίσως εύκολα μπορεί να καταλάβει κανείς από τα ονόματα αυτών των μαθηματικών αντικειμένων, για να έχεις μια οποιαδήποτε επαφή μ΄ αυτά πρέπει να γνωρίζεις πολύ καλά Προγραμματισμό Υπολογιστών, αφού αφορούν την μελέτη ιδιοτήτων των Προγραμμάτων.

Ο Προγραμματισμός Υπολογιστών είναι θεμέλιο των Επιστημών σήμερα, παρόλα αυτά στην Ελλάδα το μάθημα αυτό είναι ένα πανελλαδικό μάθημα της γενικής εκπαίδευσης που διδάσκεται μόνο στην Β και Γ’ Λυκείου (ΑΕΠΠ) και μάλιστα λιγότερο από κάθε άλλο πανελλαδικό μάθημα (μόνο δύο ώρες στην Γ’ και μία ώρα στην Β’) – με μια μικρή εισαγωγή από το μονόωρο (!) μάθημα Πληροφορικής της Β’ Λυκείου. Ακόμα και με αυτές τις δύο ώρες ΑΕΠΠ, όμως, ένας μαθητής που έχει επιλέξει την κατεύθυνση Οικονομίας και Πληροφορικής μπορεί να έχει μια εικόνα για τα Μαθηματικά για τα οποία βραβεύτηκε ο Κωσταντίνος Δασκαλάκης. Το κεφάλαιο 5 μάλιστα του σχολικού βιβλίου περιλαμβάνει παράγραφο με θέμα «Πολυπλοκότητα Αλγορίθμων». Το ίδιο τυχεροί είναι και οι μαθητές του ΕΠΑΛ που εξετάζονται στο μάθημα Προγραμματισμός Υπολογιστών (με Python). Δυστυχώς αυτό δεν συμβαίνει με τους υποψήφιους της Ομάδας Προσανατολισμού Θετικών Σπουδών από την οποία έχει αποκλειστεί το μάθημα της Πληροφορικής (πρακτικά και ουσιαστικά, αφού δεν εξετάζεται στις Πανελλαδικές), λες και η Πληροφορική δεν είναι πρώτα από όλα Θετική Επιστήμη!

Αυτή η υποβάθμιση της Πληροφορικής στην β/βάθμια εκπαίδευση, όπως μπορεί να αντιληφθεί οποιοσδήποτε έχει μια ενημερωμένη εικόνα για το γενικότερο επίπεδο των Επιστημών σήμερα, υποβαθμίζει τη συνολική ποιότητα της επιστημονικής εκπαίδευσης στην Ελλάδα. Σήμερα, είτε πρόκειται για Οικονομικές, είτε για Θετικές, είτε για Επιστήμες Υγείας είτε για οποιοδήποτε άλλο είδος Επιστήμης, αυτό που έχει ολοένα μεγαλύτερη σημασία είναι η μοντελοποίηση και μοντελοποίηση χωρίς Προγραμματισμό δεν υπάρχει, όχι μόνο ως εφαρμοστικό εργαλείο που συνοδεύει την “διακριτοποίηση”, αλλά και ως πρωτεύον μαθηματικό εργαλείο σε κάποιες περιπτώσεις: ένα παράδειγμα εδώ είναι το μοντέλο ροής υγρών/αερίων FHP, το οποίο είναι πλήρως διακριτό. Αξίζει να σημειώσουμε ότι η έννοια του «διακριτού» σχετίζεται με τους ακέραιους αριθμούς, ενώ η έννοια του «συνεχούς» με τους πραγματικούς αριθμούς (οι οποίοι, εξάλλου, είναι γνωστοί και ως «το συνεχές»). Το μοντέλο FHP, για παράδειγμα, είναι διακριτό γιατί περιγράφεται και λειτουργεί με χρήση μόνο ακέραιων αριθμών, όπως άλλωστε και ο ίδιος ο Προγραμματισμός!

Επιπλέον, πολλά φαινόμενα στην οικονομία, στην κοινωνία, στο διαδίκτυο και αλλού, δεν περιγράφονται πρωτογενώς με συνεχή εργαλεία, αλλά με διακριτά. Για παράδειγμα, «η εξάπλωση μιας άποψης στα κοινωνικά δίκτυα». Ακόμα και για τα φυσικά φαινόμενα, όμως, υπάρχει η διαίσθηση σ’ ένα μέρος της επιστημονικής κοινότητας ότι είναι και αυτά κατά βάση διακριτά! Η δήλωση του πολυβραβευμένου Φυσικού John Archibald Wheeler είναι ενδεικτική:

«It from bit. Otherwise put, every it — every particle, every field of force, even the space-time continuum itself — derives its function, its meaning, its very existence entirely — even if in some contexts indirectly — from the apparatus-elicited answers to yes-or-no questions, binary choices, bits. It from bit symbolizes the idea that every item of the physical world has at bottom — a very deep bottom, in most instances — an immaterial source and explanation; that which we call reality arises in the last analysis from the posing of yes-no questions and the registering of equipment-evoked responses; in short, that all things physical are information-theoretic in origin and that this is a participatory universe»

Ελπίζω, το Νέο Λύκειο που έχει εξαγγείλει, και θα ανακοινώσει εντός των ημερών, ο κος Γαβρόγλου να αποκαταστήσει την Πληροφορική εκπαίδευση στην Ελλάδα, εισάγοντας το μάθημα της Πληροφορικής και στις Θετικές Επιστήμες όπου είναι η φυσική του θέση, αυξάνοντας υπέρ του δέοντος  και τις ώρες διδασκαλίας του μαθήματος. Καλό θα ήταν να εισαχθεί και στο ΓΕΛ η γλώσσα προγραμματισμού Python μαζί με τα αντίστοιχα Μαθηματικά, γιατί όχι και λίγη Θεωρία Υπολογισμού μαζί με Μαθηματική Λογική!

Και πριν το Νέο Λύκειο (από την επόμενη χρονιά ουσιαστικά),  ήδη από φέτος θα μπορούσε να δοθεί η επιλογή στους υποψήφιους των Πανελλαδικών να έχουν πρόσβαση σ’ όλες τις σχολές της ΟΠ Θετικών Σπουδών διαγωνιζόμενοι στα ακόλουθα τέσσερα μαθήματα:

Γλώσσα, ΑΕΠΠ, Μαθηματικά Προσανατολισμού, Φυσική

(Δηλαδή με Φυσική αντί για ΑΟΘ στην ΟΠ Σπουδών Οικονομίας και Πληροφορικής να «ξεκλειδώνονται» όλες οι σχολές της ΟΠ Θετικών Σπουδών).

Γιώργος Μπουγιούκας

Σημειώσεις πάνω στο θεώρημα Bolzano

Το θεώρημα Bolzano, σύμφωνα με την διατύπωση του σχολικού βιβλίου, είναι:

i)   Απόδειξη «σχολίου» του σχολικού βιβλίου Μαθηματικών Προσανατολισμού

Θα αποδείξουμε τον ισχυρισμό που εμφανίζεται στο σχόλιο για το θεώρημα Bolzano στο σχολικό βιβλίο στην σελίδα 74:

«Αν μια συνάρτηση f είναι συνεχής σε ένα διάστημα Δ και δε μηδενίζεται σ’ αυτό, τότε αυτή ή είναι θετική για κάθε x∈Δ ή είναι αρνητική για κάθε x∈Δ, δηλαδή διατηρεί πρόσημο στο διάστημα Δ»

Απόδειξη:

Θα δείξουμε το ζητούμενο με απαγωγή σε άτοπο.

Υποθέτουμε ότι υπάρχει συνάρτηση f συνεχής στο Δ και χωρίς να μηδενίζεται σ’ αυτό, για την οποία ισχύουν και οι δύο παρακάτω ισχυρισμοί:

f(x)>0, για κάθε x∈Δ   (1)

f(x)<0, για κάθε x∈Δ   (2)

Από τον (1), αφού το Δ δεν είναι το κενό σύνολο, συνεπάγεται ότι υπάρχει x∈Δ τέτοιο ώστε f(x)>0, ενώ από τον (2) συνεπάγεται ότι δεν υπάρχει x∈Δ τέτοιο ώστε f(x)≥0, από το οποίο συνεπάγεται ότι δεν υπάρχει x∈Δ τέτοιο ώστε f(x)>0, άτοπο.

Υποθέτουμε τώρα ότι υπάρχει συνάρτηση f συνεχής στο Δ και χωρίς να μηδενίζεται σ’ αυτό, για την οποία δεν ισχύει κανένας από τους ισχυρισμούς (1), (2), με άλλα λόγια ισχύουν και οι δύο παρακάτω ισχυρισμοί:

Υπάρχει (τουλάχιστον ένα) x∈Δ τέτοιο ώστε f(x)≤0  (3)

Υπάρχει (τουλάχιστον ένα) x∈Δ τέτοιο ώστε f(x)≥0  (4)

Με βάση τον (3) θεωρούμε ένα στοιχείο α του Δ με f(α)≤0, και επειδή η f από την υπόθεσή μας δεν μηδενίζεται στο Δ, συνεπάγεται f(α)<0. Με βάση τον (4) θεωρούμε ένα στοιχείο β του Δ με f(β)≥0, και επειδή η f από την υπόθεσή μας δεν μηδενίζεται στο Δ, συνεπάγεται f(β)>0. Από τα προηγούμενα συνεπάγεται ότι f(α)∙f(β)<0, αλλά και α≠β (από τον ορισμό της συνάρτησης, αφού f(α)≠f(β)). Ακόμη, η f είναι συνεχής στο [α,β], εφόσον από την υπόθεσή μας είναι συνεχής στο Δ.

Θεωρώντας ότι α<β (δεν αλλάζει κάτι ουσιαστικά στην απόδειξη αν θεωρήσουμε την άλλη επιλογή, δηλαδή α>β), από το θεώρημα Bolzano (του οποίου οι προϋποθέσεις ισχύουν για το διάστημα [α,β] από την προηγούμενη παράγραφο), παίρνουμε ότι υπάρχει (τουλάχιστον ένα) x0∈(α,β), και επομένως υπάρχει (τουλάχιστον ένα) x0∈Δ όπου η f μηδενίζεται, άτοπο, αφού με βάση την υπόθεσή μας η f δεν μηδενίζεται στο Δ.

Επομένως, για τους ισχυρισμούς (1), (2) αποδείξαμε ότι δεν μπορεί να ισχύουν και οι δύο μαζί, αλλά δεν μπορεί να μην ισχύει και κανένας, άρα ισχύει ακριβώς ένας, αυτό που έπρεπε να δείξουμε. ∎

ii) Μια άλλη συνέπεια του θεωρήματος Bolzano

Έστω μια συνάρτηση f, ορισμένη σε ένα κλειστό διάστημα [α,β]. Αν δεν υπάρχει (κανένα) x0∈(α,β) τέτοιο ώστε f(x0)=0 (δηλαδή αν η εξίσωση f(x)=0 δεν έχει καμία ρίζα στο (α,β)), τότε ισχύει τουλάχιστον ένας από τους παρακάτω δύο ισχυρισμούς:
– Η f δεν είναι συνεχής στο [α,β] (5)
– f(α)∙f(β)≥0 (6)

Απόδειξη*:

Θα δείξουμε το ζητούμενο με απαγωγή σε άτοπο.

Υποθέτουμε ότι ο παραπάνω ισχυρισμός δεν ισχύει. Επομένως, υπάρχει συνάρτηση f ορισμένη στο [α,β] για την οποία δεν υπάρχει (κανένα) x0∈(α,β) τέτοιο ώστε f(x0)=0, χωρίς όμως να ισχύει τουλάχιστον ένας από τους παραπάνω ισχυρισμούς (5), (6). Ισχύει, δηλαδή, ότι και οι δύο ισχυρισμοί (5), (6) δεν ισχύουν, με άλλα λόγια ισχύει ότι η f είναι συνεχής στο [α,β] και f(α)∙f(β)<0.

Αφού, όμως, ισχύει ότι f είναι συνεχής στο [α,β] και f(α)∙f(β)<0, από το θεώρημα Bolzano παίρνουμε ότι υπάρχει (τουλάχιστον ένα) x0∈(α,β) τέτοιο ώστε f(x0)=0, το οποίο έρχεται σε αντίφαση με το συμπέρασμα που προκύπτει από την υπόθεσή μας σύμφωνα με το οποίο δεν υπάρχει (κανένα) x0∈(α,β) τέτοιο ώστε f(x0)=0. ∎

Εφαρμογή

Ισχύει ή όχι ο παρακάτω ισχυρισμός;

Αν μια συνάρτηση f ορισμένη στο [α,β] δεν μηδενίζεται στο (α, β) και επιπλέον ισχύει f(α)>0 και f(β)<0, τότε η f δεν είναι συνεχής στο [α,β].

Απάντηση:

Αφού η f δεν μηδενίζεται στο (α,β), από την ii) συνεπάγεται ότι ισχύει τουλάχιστον ένας από τους ισχυρισμούς (5), (6). Όμως, ο (6) αποκλείεται να ισχύει αφού από την υπόθεσή μας παίρνουμε ότι f(α)∙f(β)<0. Άρα, ισχύει ο (5), δηλαδή η f δεν είναι συνεχής στο [α,β]. Ο παραπάνω ισχυρισμός, επομένως, ισχύει.


* Η ii) προκύπτει και μέσω του νόμου της Μαθηματικής Λογικής ο οποίος είναι γνωστός ως «αντιθετοαντιστροφή» και μας λέει ότι αν p, q είναι δύο ισχυρισμοί, τότε οι παρακάτω δύο ισχυρισμοί είναι ισοδύναμοι:

  • p ⇒ q
  • όχι q ⇒ όχι p

Για την απόδειξη της ii) μ’ αυτόν τον τρόπο θα χρειαστούμε επιπλέον και τον ακόλουθο νόμο της Μαθηματικής Λογικής:

Η άρνηση του ισχυρισμού «ισχύει ο ισχυρισμός r1 και (επιπλέον) ο r2»  είναι ισοδύναμη με τον παρακάτω ισχυρισμό:

Ισχύει τουλάχιστον ένας από τους παρακάτω ισχυρισμούς:

α) δεν ισχύει ο r1

β) δεν ισχύει ο r2

Αυτός ο τελευταίος νόμος της Μαθηματικής Λογικής είναι γνωστός και ως ένας από τους «Νόμους De Morgan»  (ιδιαίτερο ενδιαφέρον παρουσιάζει η χρήση αυτών των νόμων και στο μάθημα της ΑΕΠΠ! – βλ. την δημοσίευση Σχετικά με το θέμα Α1 των πανελλαδικών της ΑΕΠΠ του 2017.)

Οπότε, θεωρώντας τους παρακάτω τρεις ισχυρισμούς για κάθε συνάρτηση f ορισμένη σε κάποιο [α,β],

Η f είναι συνεχής στο [α,β]  (7)

f(α)∙f(β)<0  (8)

Υπάρχει (τουλάχιστον ένα) x0∈(α,β) τέτοιο ώστε f(x0)=0  (9),

το θεώρημα Bolzano είναι η συνεπαγωγή, για κάθε συνάρτηση f ορισμένη σε κάποιο [α,β]:

(Ισχύει ο (7) και επιπλέον ο (8)) ⇒ (9)

Μέσω αντιθετοαντιστροφής, παίρνουμε:

όχι (9) ⇒ όχι (Ισχύει ο (7) και επιπλέον ο (8))

Και μέσω του Νόμου De Morgan:

όχι (9) ⇒ ισχύει τουλάχιστον ένας από τους (όχι (7)), (όχι (8))

Γιώργος Μπουγιούκας

Ενδεικτικές απαντήσεις πανελληνίων θεμάτων ΑΕΠΠ 2017

PDF: Ενδεικτικές απαντήσεις πανελληνίων θεμάτων ΑΕΠΠ 2017 – v.2

ΕΠΑΝΑΛΗΠΤΙΚΕΣ ΑΣΚΗΣΕΙΣ ΑΕΠΠ 2017 (Ι)

1) Ένας τετραγωνικός δισδιάστατος πίνακας S[ν,ν], όπου ν “τέλειο τετράγωνο” (δηλαδή η τετραγωνική του ρίζα είναι φυσικός αριθμός), είναι “πίνακας sudoku” όταν:

– Κάθε στοιχείο του S ανήκει στο σύνολο T={1,2,3,…,v}

– Κάθε γραμμή του S περιέχει κάθε στοιχείο του T.

– Κάθε στήλη του S περιέχει κάθε στοιχείο του T.

– Κάθε τετραγωνικός “υποπίνακας” με  γραμμές και στήλες του S, έτσι όπως οριοθετείται από τις έντονες διαχωριστικές γραμμές στο παρακάτω σχήμα/παράδειγμα για ν=9, περιέχει κάθε στοιχείο του Τ (σε κάθε πίνακα sudoku ν γραμμών και στηλών υπάρχουν ν τέτοιοι υποπίνακες).

Πίνακας sudoku για ν=9, με εννέα τετραγωνικούς υποπίνακες τριών γραμμών και τριών στηλών

Κατασκευάστε μία συνάρτηση σε “Γλώσσα” η οποία να δέχεται ως παράμετρο έναν δισδιάστατο πίνακα 100 γραμμών και 100 στηλών, και να επιστρέφει Αληθής αν ο πίνακας είναι sudoku, αλλιώς Ψευδής. Μπορείτε να κατασκευάσετε και να χρησιμοποιήσετε όσες επιπλέον συναρτήσεις θέλετε.

2) Ορίζουμε “γειτονιά Moore ακτίνας 1” (στο εξής γειτονιά Moore) ενός στοιχείου ενός δισδιάστατου πίνακα, έναν δισδιάστατο πίνακα 9 στοιχείων, ο οποίος περιέχει τα αμέσως γειτονικά στοιχεία βόρεια, βορειοδυτικά, δυτικά, νοτιοδυτικά, νότια, νοτιοανατολικά, ανατολικά και βορειοανατολικά του αρχικού στοιχείου (του δισδιάστατου πίνακα), καθώς και το ίδιο το αρχικό στοιχείο.

Γειτονιά Moore του C: συνίσταται στα κόκκινα κελιά, καθώς και το ίδιο το κελί C (Πηγή: Wikipedia)

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

Κατασκευάστε μια διαδικασία η οποία δέχεται ως παράμετρο τον πίνακα λογικού τύπου Προηγούμενος[100,100] και επιστρέφει τον πίνακα λογικού τύπου Επόμενος[100,100], ο οποίος διαμορφώνεται με βάση τον ακόλουθο κανόνα:

Το τυχαίο στοιχείο του πίνακα Επόμενος, Επόμενος[i,j], ισούται με Αληθής, όταν το πλήθος των στοιχείων της γειτονιάς Moore του στοιχείου Προηγούμενος[i,j], από την οποία εξαιρούμε το στοιχείο Προηγούμενος[i,j], τα οποία έχουν την τιμή Αληθής είναι περιττός αριθμός.. Σε διαφορετική περίπτωση (αν είναι άρτιος αριθμός) ισούται με Ψευδής. Για τα στοιχεία εκείνα κάποιας γειτονιάς Moore, τα οποία υπερβαίνουν τα όρια του πίνακα, θεωρείστε τιμή ίση με Ψευδής.

3) Ένα χρώμα στον Η/Υ κωδικοποιείται συνήθως με μια τριάδα φυσικών αριθμών (r, g, b), όπου οι φυσικοί αριθμοί r(ed), g(reen), b(lue) ανήκουν συνήθως στο σύνολο {0, 1, 2, 3,…, 255} και ονομάζονται “συνιστώσες” του χρώματος. Για παράδειγμα η τριάδα (0, 0, 0) κωδικοποιεί το μαύρο χρώμα, η (255, 255, 255) το λευκό, η (255, 0, 0) το κόκκινο, κλπ. Μια ψηφιακή εικόνα κωδικοποιείται ως ένας δισδιάστατος πίνακας του οποίου κάθε στοιχείο είναι μια τριάδα (r, g, b) και αντιστοιχεί σε ένα στοιχειώδες τετραγωνίδιο της εικόνας (και της οθόνης του Η/Υ) γνωστό ως pixel (PICTureELement). Οι διαστάσεις αυτού του πίνακα ονομάζονται συνήθως “ανάλυση” της εικόνας (πχ 1024 ✕ 768). Ένας τρόπος για να αναπαρασταθεί στην “Γλώσσα” της ΑΕΠΠ  ένας δισδιάστατος πίνακας από τριάδες ακέραιων είναι ένας…τρισδιάστατος πίνακας ακέραιων. Για παράδειγμα για μια εικόνα με ανάλυση 1024 ✕ 768 μπορεί να χρησιμοποιηθεί ένας πίνακας Image[1024, 768, 3], όπου, για παράδειγμα, η συνιστώσα r του pixel στην 15η γραμμή και 25η στήλη του πίνακα δίνεται από το στοιχείο Image[15, 25, 1], η συνιστώσα g δίνεται από το Image[15, 25, 2], ενώ η συνιστώσα b από το Image[15, 25, 3].

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

Σε κάθε pixel, κάθε συνιστώσα τίθεται ίση με το ακέραιο μέρος του μέσου όρου των συνιστωσών.

Κατασκευάστε μια διαδικασία η οποία δέχεται ως παράμετρο έναν τρισδιάστατο πίνακα διαστάσεων 1024,  768, 3 ο οποίος κωδικοποιεί μια έγχρωμη εικόνα και επιστρέφει έναν άλλον τρισδιάστατο πίνακα των ίδιων διαστάσεων ο οποίος κωδικοποιεί την μετατροπή της προηγούμενης σε ασπρόμαυρη.

4) Δίνεται το παρακάτω τμήμα προγράμματος, όπου η μεταβλητή κ είναι ακέραιου τύπου και στο σημείο έναρξης της δομής επανάληψης ΟΣΟ έχει τιμή μεγαλύτερη από 1:

Άραγε, το παραπάνω τμήμα προγράμματος πληρεί το κριτήριο της “περατότητας” αλγορίθμου για κάθε τιμή μεγαλύτερη του 1 της ακέραιας μεταβλητής κ αμέσως πριν την έναρξη της δομής επανάληψης; Με άλλα λόγια η δομή επανάληψης κατά την εκτέλεσή της τερματίζει μετά από πεπερασμένο πλήθος βημάτων, για κάθε αρχική τιμή του κ μεγαλύτερη από 1; Ο γνωστός μαθηματικός Erdos έχει δηλώσει σχετικά με το προηγούμενο ερώτημα ότι “τα μαθηματικά δεν είναι έτοιμα ακόμα για τέτοια προβλήματα”. Το πρόβλημα αυτό είναι γνωστό ως “εικασία του Collatz” (η εικασία είναι ότι η δομή επανάληψης τερματίζει για κάθε κ>1) και παραμένει άλυτο μέχρι και σήμερα.

Θεωρείστε τον παρακάτω αλγόριθμο σε φυσική γλώσσα με βήματα:

1. Αν το παραπάνω τμήμα προγράμματος πληρεί το κριτήριο της περατότητας για κάθε αρχική τιμή της μεταβλητής κ, πήγαινε στο βήμα 4.

2. Γράψε “ΟΧΙ”.

3. Πήγαινε στο βήμα 5.

4. Γράψε “ΝΑΙ”

5. Τέλος αλγορίθμου.

Ποιο/ποια από τα παρακάτω χαρακτηριστικά του αλγορίθμου παραβιάζει ο προηγούμενος αλγόριθμος (τουλάχιστον την δεδομένη χρονική στιγμή, όπου η εικασία του Collatz δεν έχει αποδειχτεί, ούτε καταρριφθεί) και γιατί;

– Αποτελεσματικότητα

– Περατότητα

– Καθοριστικότητα

Γιώργος Μπουγιούκας

Γιατί 0,999… = 1 και κάποιες σημειώσεις πάνω στην ισότητα πραγματικών αριθμών

Γνωρίζουμε ότι δύο πραγματικοί αριθμοί είναι ίσοι αν και μόνο αν η διαφορά τους είναι ίση με 0. Γνωρίζουμε, ακόμα, ότι όλοι οι πραγματικοί αριθμοί έχουν άπειρα δεκαδικά ψηφία, για την ακρίβεια τόσα όσοι είναι και οι φυσικοί αριθμοί: σε κάθε φυσικό αριθμό αντιστοιχίζεται και ένα δεκαδικό ψηφίο στην αντίστοιχη θέση (η πρώτη θέση από αριστερά είναι η 0, η δεύτερη η 1, κοκ – ο πρώτος φυσικός αριθμός είναι πάντα το 0). Αυτή η συνάρτηση από τους φυσικούς αριθμούς (“άπειρη ακολουθία”) είναι σημαντική, διότι, για παράδειγμα, ο συμβολισμός 0,000…1 (τον οποίο κάπου έχει πάρει το μάτι μου), με τον υπαινιγμό άπειρα μηδενικά δεκαδικά και στο τέλος το ένα, δεν είναι πραγματικός αριθμός, αφού δεν υπάρχει “τελευταίος” φυσικός αριθμός (στον οποίο θα αντιστοιχούσε ο άσσος). Ακόμα και αν ένας αριθμός είναι ακέραιος, όπως το 1, ως πραγματικός αναπαριστάνεται ως 1,000… Θα δείξουμε, λοιπόν, ότι η παρακάτω αφαίρεση δίνει αποτέλεσμα 0:

Θα δείξουμε πρώτα ότι κάθε δεκαδικό ψηφίο του παραπάνω αποτελέσματος είναι ίσο με 0. Θα το δείξουμε αυτό θεωρώντας ένα τυχαίο δεκαδικό ψηφίο, χωρίς κάποια ιδιαίτερη ιδιότητα, επομένως μ’ αυτόν τον τρόπο θα το έχουμε δείξει για κάθε δεκαδικό ψηφίο. Έστω, λοιπόν, το τυχαίο δεκαδικό ψηφίο στην (δεκαδική) θέση k του παραπάνω αποτελέσματος. Το τελευταίο υπολογίζεται αν στο 9 προσθέσουμε το δανεικό (αν υπάρχει) το οποίο πάρθηκε στην (δεκαδική) θέση k+1, και αφαιρέσουμε αυτό το άθροισμα από το 10 (δανειζόμαστε σίγουρα στην θέση k, εφόσον η αφαίρεση του 9 ή του 9+1=10 από το 0 δίνει αρνητικό αποτέλεσμα). Το δανεικό στην θέση k+1 σίγουρα υπάρχει (αφού ανεξάρτητα από το αν υπάρχει δανεικό στην θέση k+2, χρειάζεται ήδη για την αφαίρεση του 9 από το 0), επομένως για την θέση k του αποτελέσματος γίνεται η αφαίρεση 10-(9+1), η οποία δίνει 0.

Θα δείξουμε τώρα ότι και αριστερά της υποδιαστολής του παραπάνω αποτελέσματος προκύπτει το 0. Θεωρώντας την δεκαδική θέση 0 (την πρώτη από αριστερά δεκαδική θέση), παρατηρούμε ότι υπάρχει σίγουρα δανεικό, οπότε αριστερά της υποδιαστολής έχουμε το αποτέλεσμα της αφαίρεσης 1-(0+1) = 0.

Επομένως, το αποτέλεσμα είναι:

0,000… = 0

Σημειώσεις πάνω στην ισότητα πραγματικών αριθμών

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

-Κάθε ρητός δεκαδικός αριθμός, εκτός από το 0, με περίοδο το 0, είναι ίσος με έναν ρητό δεκαδικό αριθμό με περίοδο το 9.

Για παράδειγμα (οι τρεις τελείες “…” υποδεικνύουν περίοδο το 9), 3 = 2,999…, 1 = 0,999…, 10 = 9,999…, -3 = -2,999…, -1 = -0,999…, -10 = -9,999…, 2,46 = 2,45999…, -1,387 = -1,386999… κλπ.

– Το πρόβλημα της ισότητας δύο πραγματικών αριθμών είναι μη-αποφασίσιμο.

Ένα μαθηματικό πρόβλημα ορίζεται ως πρόβλημα απόφασης αν η απάντηση σ’ αυτό το πρόβλημα είναι της μορφής ΝΑΙ-ΟΧΙ.

Για παράδειγμα, με δεδομένο έναν φυσικό αριθμό, είναι ο αριθμός αυτός άρτιος, ή με δεδομένους δύο πραγματικούς αριθμούς, είναι αυτοί ίσοι;

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

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

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

Να σημειώσουμε εδώ, ότι ένας σύγχρονος ηλεκτρονικός υπολογιστής είναι η ισχυρότερη υπολογιστική μηχανή που έχει ανακαλύψει ο άνθρωπος μέχρι τώρα, όχι μόνο ποσοτικά αλλά και ποιοτικά, με άλλα λόγια σε 4.000 περίπου χρόνια μαθηματικής ιστορίας κανείς δεν έχει παρουσιάσει κάποιον υπολογισμό με χαρτί και μολύβι ή με οποιοδήποτε άλλο μέσο, ο οποίος να μην μπορεί να προσομοιωθεί από έναν σύγχρονο ηλεκτρονικό υπολογιστή. Η υπόθεση ότι μια ισχυρότερη υπολογιστική μηχανή δεν υπάρχει, είναι γνωστή ως “θέση Church-Turing”).

Το πρόβλημα της ισότητας δύο ρητών αριθμών είναι αποφασίσιμο, αφού ο ορισμός της ισότητας δύο ρητών αριθμών είναι και πρόγραμμα το οποίο την αποφασίζει:

Για παράδειγμα, το παρακάτω πρόγραμμα σε γλώσσα προγραμματισμού ΑΕΠΠ αποφασίζει το πρόβλημα:

Υποψιαζόμασταν ότι αυτό το πρόγραμμα υπάρχει, αφού εύκολα μπορούμε να αποφασίσουμε το πρόβλημα με χαρτί και μολύβι: μάλλον δεν καταρρίπτεται έτσι εύκολα η θέση Church-Turing.

Όμως, στα μαθηματικά οι ορισμοί δεν είναι πάντα και προγράμματα που μπορούν να αποφασίσουν αυτό που ορίζουν. Ο ορισμός της ισότητας για τους πραγματικούς αριθμούς, είναι χαρακτηριστικό παράδειγμα:

Ορίζουμε πρώτα την ισότητα με το 0:

Ένας πραγματικός αριθμός είναι ίσος με το 0, αν και μόνο αν το ακέραιο μέρος του είναι ίσο με 0 και κάθε δεκαδικό ψηφίο του είναι ίσο με 0.

Οπότε, μπορούμε τώρα να ορίσουμε γενικότερα την ισότητα οποιωνδήποτε δύο πραγματικών αριθμών:

Δύο πραγματικοί αριθμοί είναι ίσοι αν και μόνο αν η διαφορά τους είναι ίση με 0.

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

Ο ορισμός αυτός, όμως, υπαγορεύει και κάποιο πρόγραμμα, το οποίο αποφασίζει το πρόβλημα της ισότητας δύο πραγματικών αριθμών για κάθε ζεύγος πραγματικών αριθμών, όπως συμβαίνει και με τον ορισμό της ισότητας των ρητών αριθμών; Είδαμε παραπάνω ότι αυτό μπορεί να γίνει για τους πραγματικούς αριθμούς 1 και 0,999…Ας εξετάσουμε ένα άλλο στιγμιότυπο του προβλήματος:

Είναι ίσοι οι πραγματικοί, και μάλιστα άρρητοι, αριθμοί π και e;

Υπολογίζουμε κάποιο ικανό πλήθος δεκαδικών ψηφίων του αποτελέσματος της αφαίρεσης π-e:

Παρατηρούμε ότι το αποτέλεσμα σίγουρα είναι 0 αριστερά της υποδιαστολής αφού στην δεκαδική θέση 0 υπάρχει δανεισμός, ενώ το δεκαδικό ψηφίο στην θέση 0 είναι το 4, αφού στην δεκαδική θέση 1 δεν γίνεται δανεισμός, ανεξάρτητα από το τι γίνεται στην θέση 2! Επομένως, έχουμε π-e ≥ 0,4, επομένως η διαφορά είναι διάφορη του 0, επομένως οι αριθμοί αυτοί δεν είναι ίσοι.

Τι γίνεται, όμως, με το ακόλουθο στιγμιότυπο του προβλήματος;

Είναι ίσοι οι πραγματικοί αριθμοί 0 και d; – όπου ο d ορίζεται ως εξής:

Ακέραιο μέρος ίσο με 0 και:
Δεκαδικό ψηφίο στην θέση 0: 0 αν αριθμός 4 εκφράζεται ως άθροισμα δύο πρώτων, αλλιώς 1
Δεκαδικό ψηφίο στην θέση 1: 0 αν αριθμός 6 εκφράζεται ως άθροισμα δύο πρώτων, αλλιώς 1
Δεκαδικό ψηφίο στην θέση 2: 0 αν αριθμός 8 εκφράζεται ως άθροισμα δύο πρώτων, αλλιώς 1

Υπενθυμίζεται ότι πρώτος είναι ο φυσικός αριθμός του οποίου το σύνολο των διαιρετών έχει πλήθος στοιχείων ίσο με 2. Για παράδειγμα το 0 δεν είναι πρώτος, αφού έχει άπειρους διαιρέτες, το 5 είναι, αφού το σύνολο των διαιρετών του είναι το {1,5}, ενώ το 8 δεν είναι αφού το σύνολο {1,2,8} είναι υποσύνολο του συνόλου των διαιρετών του.

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

Είναι προφανές ότι ο αριθμός d είναι ίσος με το 0 αν και μόνο αν κάθε άρτιος φυσικός αριθμός μεγαλύτερος του 2 εκφράζεται ως άθροισμα δύο πρώτων. Αυτή, όμως, είναι και η διατύπωση του περίφημου μαθηματικού προβλήματος το οποίο είναι γνωστό ως η εικασία του Goldbach, το οποίο παραμένει άλυτο εδώ και τουλάχιστον 250 χρόνια. Αν ήταν έτσι εύκολο να έχουμε ένα πρόγραμμα που να αποφασίζει την ισότητα πραγματικών αριθμών, θα είχαμε λύσει και την εικασία του Goldbach. Αυτό, βέβαια, δεν αποδεικνύει ότι το πρόγραμμα αυτό δεν υπάρχει, αλλά μόνο ότι δεν το έχουμε ανακαλύψει ως τώρα. Ωστόσο, αποδεικνύεται μαθηματικά, πράγματι, ότι ένα τέτοιο πρόγραμμα δεν υπάρχει.

Γιώργος Μπουγιούκας

Ταληράκια

Γράψτε ένα πρόγραμμα σε Γλώσσα το οποίο να επιλύει το ακόλουθο πρόβλημα:

Θεωρείστε δύο (ίσως φανταστικούς) τύπους κερμάτων αξίας α1 και α2 λεπτών, όπου α1 και α2 είναι οποιοιδήποτε θετικοί ακέραιοι με τον περιορισμό α1α2. Θεωρείστε ακόμη έναν μη-αρνητικό ακέραιο c. Υπάρχει τρόπος επιλέγοντας κάποια ποσότητα (ίσως 0) από το ένα κέρμα και κάποια ποσότητα (ίσως 0) από το άλλο, το άθροισμα των αξιών αυτών των κερμάτων να είναι ίσο με c;

(υποθέστε ότι υπάρχει διαθέσιμο πλήθος κερμάτων κάθε τύπου όσο χρειαστεί)

Παράδειγμα:

Για αξίες κερμάτων 5 και 7 υπάρχει τρόπος να σχηματιστεί το ποσό 17, αλλά δεν υπάρχει τρόπος να σχηματιστεί το ποσό 23.

Λύση

psila

Η απόδειξη ορθότητας παραλείπεται ως άσκηση.

Ιστορικό σημείωμα

Το παραπάνω πρόβλημα στην γενική του μορφή, δηλαδή όχι μόνο για δύο τύπους κερμάτων, αλλά για οποιοδήποτε πεπερασμένο (θετικό ακέραιο) πλήθος κερμάτων (ανά δύο με άνισες αξίες) είναι γνωστό ως εκδοχή εφικτότητας του προβλήματος “κάνω ψιλά” (Change Making Problem – CMP). Ο καλύτερος αλγόριθμος ο οποίος έχει βρεθεί μέχρι τώρα για το τελευταίο αυτό πρόβλημα είναι πολύ αργός για την ανθρώπινη κλίμακα χρόνου για είναι χρήσιμος. Αν καταφέρνατε να βρείτε έναν «γρήγορο» αλγόριθμο γι’ αυτό το πρόβλημα, θα κερδίζατε το βραβείο του ενός εκατομμυρίου δολαρίων του Ινστιτούτου Μαθηματικών Clay, καθώς θα είχατε λύσει το μεγαλύτερο (ίσως) πρόβλημα πληροφορικής/μαθηματικών της εποχής μας και (ίσως) όλων των εποχών: το πρόβλημα “P versus NP”.

Άσκηση για εμβάθυνση

Θεωρείστε το παραπάνω πρόβλημα με τρεις (αντί για δύο) τύπους κερμάτων (με αξίες ανά δύο άνισες). Γράψτε ένα πρόγραμμα σε Γλώσσα για την επίλυση αυτού του προβλήματος.

Το κόσκινο του Ερατοσθένη

Τελευταία ενημέρωση: 5/10/2016

Πρόβλημα

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

1. Αν n<2 τερμάτισε – δεν υπάρχει πρώτος αριθμός μικρότερος του 2.

2. Γράψε κατά αύξουσα σειρά διάταξης όλους τους φυσικούς αριθμούς οι οποίοι είναι μεγαλύτεροι ή ίσοι του 2 και μικρότεροι ή ίσοι του n.

3. Διάγραψε όλα τα πολλαπλάσια του 2 (πχ επισημαίνοντάς τα με μια διαγώνια μολυβιά) τα οποία είναι μεγαλύτερα από το 2.

4.Βρες τον πρώτο (όσο αφορά την διάταξη) αριθμό που είναι μεγαλύτερος του 2 και δεν έχει διαγραφτεί – αν δεν υπάρχει τέτοιος αριθμός πήγαινε στο βήμα 5. Πήγαινε στο βήμα 3 και εκτέλεσέ το, αυτό και το επόμενο (το 4, δηλαδή το τρέχον), θεωρώντας αντί για τον αριθμό 2, τον αριθμό που βρήκες στην αρχή αυτού του βήματος.

5. Οι πρώτοι αριθμοί οι οποίοι είναι μικρότεροι ή ίσοι από τον n είναι οι αριθμοί που δεν είναι διαγραμμένοι.

Γράψτε ένα πρόγραμμα σε Γλώσσα το οποίο με εφαρμογή του παραπάνω αλγόριθμου εμφανίζει στην οθόνη όλους τους πρώτους αριθμούς οι οποίοι είναι μικρότεροι ή ίσοι από κάποιον φυσικό αριθμό n ≥ 2.

Λύση

eratosth

Η απόδειξη ορθότητας παραλείπεται ως άσκηση.

Ασκήσεις για εμβάθυνση

1) Γιατί θεωρείτε ότι ο παραπάνω αλγόριθμος ονομάζεται «κόσκινο»;

2) Τροποποιείστε το παραπάνω πρόγραμμα θεωρώντας ως δεδομένο ότι στο βήμα 3 του αλγόριθμου ο οποίος αναφέρεται στην διατύπωση του προβλήματος αρκεί να διαγραφτούν τα πολλαπλάσια του τρέχοντος αριθμού τα οποία είναι μεγαλύτερα ή ίσα από το τετράγωνο του τρέχοντος αριθμού, διότι τα υπόλοιπα έχουν ήδη διαγραφτεί πριν ο αλγόριθμος φτάσει σ’ αυτό το σημείο. Αν το τετράγωνο του τρέχοντος αριθμού είναι μεγαλύτερο από τον αριθμό n, ο αλγόριθμος πρέπει να μεταβαίνει στο βήμα 5.

Βίντεο

Πολλαπλάσια και ημίτονα

Τελευταία ενημέρωση 18/10/2016

Πρόβλημα

Χωρίς να χρησιμοποιήσετε τους τελεστές MOD, DIV και /, αλλά ούτε και την ενσωματωμένη συνάρτηση Α_Μ (Ακέραιο Μέρος), να συμπληρώσετε την εντολή στην παρακάτω συνάρτηση ώστε να επιστρέφει “Αληθές” αν η παράμετρος είναι άρτιος φυσικός αριθμός και “Ψευδές” αν είναι περιττός.

ΣΥΝΑΡΤΗΣΗ is_even(n): ΛΟΓΙΚΗ

ΜΕΤΑΒΛΗΤΕΣ

ΑΚΕΡΑΙΕΣ: n

ΑΡΧΗ

is_even <- …

ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Λύση

is_even <-  ΗΜ(n*90) = 0

Απόδειξη ορθότητας

Αν θεωρήσουμε τον τριγωνομετρικό κύκλο, είναι προφανές ότι τα άρτια πολλαπλάσια των 90 μοιρών (π/2 ακτίνια) έχουν ημίτονο 0, ενώ τα περιττά 1 ή -1.

Άσκηση για εμβάθυνση

Συμπληρώστε την εντολή στην παρακάτω συνάρτηση ώστε να επιστρέφει “Αληθές” αν η παράμετρος n διαιρείται (ακριβώς) με την m και “Ψευδές” αν δεν διαιρείται. Θεωρείστε ότι κατά την κλήση της συνάρτησης τα ορίσματα είναι φυσικοί αριθμοί.

ΣΥΝΑΡΤΗΣΗ div_n_by_m(n, m): ΛΟΓΙΚΗ

ΜΕΤΑΒΛΗΤΕΣ

ΑΚΕΡΑΙΕΣ: n, m

ΑΡΧΗ

div_n_by_m <-  ΗΜ(…) = …

ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Βίντεο

Ακριβής λειτουργία της δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ

Τελευταία ενημέρωση 22/9/2016

Θεωρούμε τις ακέραιες* μεταβλητές ι, α, β, γ με τον περιορισμό γ≠0 και την γενική μορφή αυτής της δομής επανάληψης:

(*Σημείωση: Οι μεταβλητές ι, α, β και γ μπορεί να είναι και πραγματικές. Η γενική λογική παραμένει η ίδια με την διαφορά ότι ο τύπος α + (Α_Τ(α – β)  DIV  Α_Τ(γ) + 1) * γ ο οποίος παρουσιάζεται παρακάτω δεν ισχύει σ’ αυτήν την περίπτωση)

ΓΙΑ  ι  ΑΠΟ  α  ΜΕΧΡΙ  β  ΜΕ_ΒΗΜΑ  γ

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Η ακριβής λειτουργία αυτής της δομής επανάληψης είναι η εξής (με την αυστηρή σειρά βημάτων που υποδεικνύει ο παρακάτω αλγόριθμος):

1) Εκχώρησε στην μεταβλητή ι την τιμή της α.

2)

α) Εάν η μεταβλητή γ (βήμα) είναι θετική

Εάν η λογική συνθήκη ι <= β (η ι είναι μικρότερη ή ίση της β) είναι αληθής, τότε εκτέλεσε το σώμα του βρόγχου, αλλιώς τερμάτισε την δομή επανάληψης (οπότε το πρόγραμμα συνεχίζεται με τις εντολές που βρίσκονται ακριβώς μετά την εντολή “ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ”)

β) Εάν η μεταβλητή γ (βήμα) είναι αρνητική

Εάν η λογική συνθήκη ι >= β (η ι είναι μεγαλύτερη ή ίση της β) είναι αληθής, εκτέλεσε το σώμα του βρόγχου, αλλιώς τερμάτισε την δομή επανάληψης (οπότε το πρόγραμμα συνεχίζεται με τις εντολές που βρίσκονται ακριβώς μετά την εντολή “ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ”).

3) Εκχώρησε στην τιμή του ι την τρέχουσα τιμή του ι συν την τιμή του βήματος:

ι  <-  ι + γ

(Αν το γ (βήμα) είναι αρνητικό, πχ -4, έχουμε ι  <-  ι + (-4), ή ισοδύναμα    ι  <-  ι – 4 )

4) Πήγαινε στο βήμα 2).

Σημείωση 1:

Για την δομή επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ είναι δυνατό να μην εκτελεστεί καμία (!) επανάληψη, εάν η λογική συνθήκη που ελέγχεται είναι ψευδής χωρίς να έχει εκτελεστεί προηγούμενα καμία επανάληψη. Αυτό γενικά είναι “νόμιμο” και μάλιστα χρήσιμο σε πολλές περιπτώσεις τόσο στην Γλώσσα όσο και σε πραγματικές γλώσσες προγραμματισμού.

Σημείωση 2:

Ακριβώς μετά τον τερματισμό της δομής επανάληψης η μεταβλητή ι έχει τιμή:

α) Εάν δεν έχει εκτελεστεί καμία επανάληψη (δηλαδή αν ι =α )

Ίση με το α

Σημείωση:

Μετά το τέλος της  δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ δεν έχει εκτελεστεί καμία επανάληψη αν και μόνο αν η λογική συνθήκη ι=α είναι αληθής.

β) Εάν έχει εκτελεστεί τουλάχιστον μία επανάληψη (δηλαδή αν ι <> α)

Ίση με  α + (Α_Τ(α – β)  DIV  Α_Τ(γ) + 1) * γ

(όπου Α_Τ η ενσωματωμένη συνάρτηση που επιστρέφει την απόλυτη τιμή της παραμέτρου)

Σημείωση:

Μετά το τέλος της  δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ έχει εκτελεστεί τουλάχιστον μία επανάληψη αν και μόνο αν η λογική συνθήκη ι<>α είναι αληθής.

Παραδείγματα

A)

ΓΙΑ ι ΑΠΟ 5 ΜΕΧΡΙ 3
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = 5
β = 3
γ = 1

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή 5

2) Ελέγχεται η συνθήκη 5 <= 3 η οποία είναι ψευδής και η δομή επανάληψης τερματίζει.

Βλέπουμε δηλαδή ότι δεν εκτελείται καμία επανάληψη.

Κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή σύμφωνα με τα παραπάνω:
ίση με α, δηλαδή 5

Β)

ΓΙΑ ι ΑΠΟ 5 ΜΕΧΡΙ 15 ΜΕ_ΒΗΜΑ 5
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = 5
β = 15
γ = 5

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή 5

2) Ελέγχεται η συνθήκη 5 <= 15 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή 5.

3) Η τιμή του ι αυξάνεται κατά 5, δηλαδή γίνεται 10.

4) Ελέγχεται η συνθήκη 10 <= 15 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή 10.

5) Η τιμή του ι αυξάνεται κατά 5, δηλαδή γίνεται 15.

6) Ελέγχεται η συνθήκη 15 <= 15 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή 15.
.
7) Η τιμή του ι αυξάνεται κατά 5, δηλαδή γίνεται 20.

8) Ελέγχεται η συνθήκη 20 <= 15 η οποία είναι Ψευδής, άρα η δομή επανάληψης τερματίζει.

Άρα, κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή 20, αυτό όμως μπορεί να υπολογιστεί σύμφωνα με τον παραπάνω τύπο και χωρίς την προηγούμενη προσομοίωση εκτέλεσης του αλγορίθμου:

5 + (Α_Τ(5 – 15)  DIV  Α_Τ(5) + 1) * 5 = 5 + (Α_Τ(-10)  DIV  Α_Τ(5) + 1) * 5 =
5 + (10 DIV  5 + 1) * 5 = 5 + (2 + 1) * 5 = 5 + (2 + 1) * 5 = 5+3*15  = 5+15 = 20

Γ)

ΓΙΑ ι ΑΠΟ -5 ΜΕΧΡΙ -2 ΜΕ_ΒΗΜΑ -1
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = -5
β = -2
γ = -1

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή -5

2) Ελέγχεται η συνθήκη -5 >= -2 η οποία είναι ψευδής και η δομή επανάληψης τερματίζει.

Βλέπουμε δηλαδή ότι δεν εκτελείται καμία επανάληψη.

Κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή σύμφωνα με τα παραπάνω:
ίση με α, δηλαδή -5

Δ)

ΓΙΑ ι ΑΠΟ -5 ΜΕΧΡΙ -8 ΜΕ_ΒΗΜΑ -2
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = -5
β =  -8
γ = -2

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή -5

2) Ελέγχεται η συνθήκη -5 >= -8 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή -5.

3) Η τιμή του ι μειώνεται κατά 2, δηλαδή γίνεται -7.

4) Ελέγχεται η συνθήκη -7 >= -8 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή -7.

5) Η τιμή του ι μειώνεται κατά -2, δηλαδή γίνεται -9.

6) Ελέγχεται η συνθήκη -9 >= -8 η οποία είναι Ψευδής, άρα η δομή επανάληψης τερματίζει.

Άρα, κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή -9, αυτό όμως μπορεί να υπολογιστεί σύμφωνα με τον παραπάνω τύπο και χωρίς την προηγούμενη προσομοίωση εκτέλεσης του αλγορίθμου:

-5 + (Α_Τ(-5 – (-8))  DIV  Α_Τ(-2) + 1) * (-2) = -5 + (Α_Τ(-5 + 8)  DIV  Α_Τ(-2) + 1)* (-2)=
-5 + (Α_Τ(3)  DIV  Α_Τ(-2) + 1) * (-2) = -5 + (3  DIV 2 + 1) * (-2) = -5 + (1 + 1) * (-2) =
-5 + 2 * (-2) = -5-4 = -9

Ιστορικό σημείωμα

Μια πρώιμη μορφή της δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ εμφανίστηκε στον χώρο των μαθηματικών το 1931 με την ονομασία «πρωτόγονη αναδρομική συνάρτηση» κατά την δημοσίευση των αποδείξεων των θεωρημάτων μη-πληρότητας του Κουρτ Γκέντελ. Οι πρωτόγονες αναδρομικές συναρτήσεις είχαν προταθεί 8 χρόνια νωρίτερα από τον Σκόλεμ.

Ψηφιακή ρίζα

Πρόβλημα

Η ψηφιακή ρίζα ενός αριθμού είναι ο μονοψήφιος αριθμός που προκύπτει αν αθροίσουμε αναδρομικά τα ψηφία του. Θεωρείστε ως δεδομένο ότι αυτή η διαδικασία καταλήγει πάντα σε μονοψήφιο αριθμό σε πεπερασμένο πλήθος βημάτων. Για παράδειγμα, η ψηφιακή ρίζα του 217 είναι:

2+1+7=10→1+0=1

Γράψτε μία συνάρτηση με μια ακέραια παράμετρο η οποία αντιστοιχεί στον αριθμό του οποίου την ψηφιακή ρίζα επιστρέφει.

Λύση

! χρησιμοποιούνται οι συναρτήσεις digit_trunc και nth_digit οι οποίες
!ορίζονται στην δημοσίευση «ν-οστό ψηφίο»
dr

Απόδειξη ορθότητας

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

Σχόλια

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

– Η συνθήκη ν > 9 σημαίνει ότι ο αριθμός ν έχει περισσότερα από 1 ψηφία (αφού είναι μεγαλύτερος του 9).

– Η συνθήκη digit_trunc(ν, ι) = 0 (στον εμφωλευμένο βρόγχο) με βάση τον ορισμό της συνάρτησης digit_trunc σημαίνει ότι ο αριθμός ν περικόπηκε κατά ι ψηφία και απέμεινε ο αριθμός 0, δηλαδή ότι ο ι είναι μεγαλύτερος ή ίσος από το πλήθος των ψηφίων του ν. Επειδή όμως στο σώμα του βρόγχου η μεταβλητή ι αυξάνεται κάθε φορά κατά 1, η συγκεκριμένη σημασία της παραπάνω συνθήκης είναι ότι εξαντλήθηκαν τα ψηφία του αριθμού ν.

-Στην αρχή του εξωτερικού βρόγχου μηδενίζεται το άθροισμα των ψηφίων του ν (μεταβλητή αθροισμα_ψηφίων) και η μεταβλητή ι η οποία εκφράζει το πλήθος των ψηφίων του ν που περικόπτονται κάθε φορά. Επειδή η μεταβλητή ι ξεκινάει με αρχική τιμή 1, ενώ η θέση του ψηφίου ξεκινάει από το 0 (με βάση τον ορισμό της συνάρτησης nth_digit), η θέση του ψηφίου εκφράζεται σε κάθε επανάληψη του εμφωλευμένου βρόγχου ως ν-1.

– Στη δομή επανάληψης ΟΣΟ…ΜΕΧΡΙΣ_ΟΤΟΥ πρώτα εκτελείται το σώμα του βρόγχου και μετά ελέγχεται η συνθήκη εξόδου από αυτόν, σε αντίθεση με την δομή επανάληψης ΟΣΟ…ΕΠΑΝΑΛΑΒΕ, όπου πρώτα ελέγχεται η συνθήκη εξόδου και μετά εκτελείται το σώμα του βρόγχου (ως συνέπεια: η δομή επανάληψης ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ…ΜΕΧΡΙΣ_ΟΤΟΥ εκτελείται τουλάχιστον μία φορά, ενώ η δομή επανάληψης ΟΣΟ…ΕΠΑΝΑΛΑΒΕ είναι δυνατό να μην εκτελεστεί καμία φορά). Η επιλογή της πρώτης μορφής δομής επανάληψης στον εμφωλευμένο βρόγχο της παραπάνω λύσης είναι αναγκαία καθώς η τελευταία επανάληψη του βρόγχου θα είναι όταν το ι πάρει τιμή ίση με το πλήθος ψηφίων του ν, οπότε η έκφραση digit_trunc(ν, ι) παίρνει τιμή 0. Για αυτήν την τιμή όμως θέλουμε να εκτελεστεί το σώμα του βρόγχου όπου προσθέτεται το τελευταίο ψηφίο του ν, αυτό στην θέση ι-1, πριν ελεγχθεί η συνθήκη εξόδου.

– Ο,τιδήποτε εμφανίζεται στα δεξιά του συμβόλου “!” θεωρείται σχόλιο, δηλαδή δεν θεωρείται “ενεργό” κομμάτι του προγράμματος.

Άσκηση για εμβάθυνση

Δίνεται η παρακάτω συνάρτηση:

ΣΥΝΑΡΤΗΣΗ x(ν): ΑΚΕΡΑΙΑ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ν
ΑΡΧΗ
  ν <- ν MOD 9
  ΑΝ ν <> 0 ΤΟΤΕ
    x <- ν
  ΑΛΛΙΩΣ
    x <- 9
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Υπολογίστε (χωρίς την χρήση του διερμηνευτή) την τιμή που επιστρέφει αυτή η συνάρτηση και η συνάρτηση της λύσης για τα ορίσματα του παρακάτω συνόλου:

{99, 78, 44, 35, 29}

Τι παρατηρείτε;