Τεκμηριώνεται επιστημονικά η Β’ (και η Α’) ανάθεση του μαθήματος των μαθηματικών σε πληροφορικούς στην β/βάθμια εκπαίδευση;

Ως γνωστόν, με βάση το άρθρο 30 του Ν.2009/1992 (ΦΕΚ 18/14-2-1992, τ.Α ́) “Εθνικό Σύστημα Επαγγελματικής Εκπαίδευσης και Κατάρτισης και άλλες διατάξεις” μετατάχθηκαν στον νεοσύστατο τότε εκπαιδευτικό κλάδο Π19, λόγω έλλειψης απόφοιτων πληροφορικής, εκπαιδευτικοί χωρίς πτυχίο πληροφορικής, κυρίως μαθηματικοί. Θεωρώ ότι δικαιωματικά ένας μαθηματικός είναι η πρώτη επιλογή αναπλήρωσης ενός πληροφορικού όταν προκύψει ανάγκη, θα δείξω, μάλιστα, ότι αυτή η “συνάρτηση” είναι “αντιστρέψιμη”, δηλαδή ότι και ένας πληροφορικός είναι η πρώτη επιλογή αναπλήρωσης ενός μαθηματικού.

Η σχέση πληροφορικής-μαθηματικών είναι εσωτερική-δομική και όχι εξωτερική-εργαλειακή.

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

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

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

-Οι αλγόριθμοι είναι θεμέλιο των μαθηματικών.

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

-Τα θεμέλια συναντούν πολύ συχνά τα άλλα θεμέλια (προτασιακό και κατηγορηματικό λογισμό).

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

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

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

  • Aνάλυση
  • Γραμμική άλγεβρα
  • Θεωρία πιθανοτήτων
  • Θεωρία συνόλων
  • Συνδυαστική
  • Θεωρία των γράφων
  • Θεωρία υπολογισιμότητας
  • Θεωρία αυτομάτων και τυπικών γλωσσών
  • Θεωρία πολυπλοκότητας
  • Θεωρία πληροφορίας
  • Κρυπτογραφία
  • Γραμμικός προγραμματισμός
  • Άλγεβρα Μπουλ
  • Θεωρία παιγνίων

-Οι αλγόριθμοι είναι παντού στα μαθηματικά.

Ξεκινώντας την μαθηματική εκπαίδευση ήδη από τις πρώτες τάξης του Δημοτικού και συνεχίζοντας σε υψηλότερες βαθμίδες της εκπαίδευσης, διδάσκονται:

  • Ο αλγόριθμος της προπαίδειας.
  • Ο αλγόριθμος της κάθετης πρόσθεσης και αφαίρεσης.
  • Ο αλγόριθμος του κάθετου πολλαπλασιασμού και της κάθετης διαίρεσης.
  • Αλγόριθμοι εύρεσης του ελάχιστου κοινού πολλαπλασίου (ΕΚΠ).
  • Αλγόριθμοι εύρεσης του μέγιστου κοινού διαιρέτη (ΜΚΔ.)
  • Αλγόριθμοι για την μετατροπή δύο κλασμάτων σε ομώνυμα.
  • Αλγόριθμοι πρόσθεσης κλασμάτων.
  • Ο αλγόριθμος «το κόσκινο του Ερατοσθένη».
  • Ο αλγόριθμος κατασκευής ισοσκελούς τριγώνου με χάρακα και διαβήτη.
  • Ο αλγόριθμος διχοτόμησης ευθύγραμμου τμήματος με χάρακα και διαβήτη.
  • Ο αλγόριθμος διχοτόμησης γωνίας με χάρακα και διαβήτη.
  • Ο αλγόριθμος υπολογισμού ρητής προσέγγισης τετραγωνικής ρίζας φυσικού αριθμού.
  • Ο αλγόριθμος επίλυσης (στο ℝ) μονομεταβλητής πρωτοβάθμιας εξίσωσης με ρητούς συντελεστές.
  • Ο αλγόριθμος επίλυσης (στο ℝ) μονομεταβλητής δευτεροβάθμιας εξίσωσης με ρητούς συντελεστές.
  • Αλγόριθμοι παραγώγισης για διάφορες κλάσεις συναρτήσεων.
  • Αλγόριθμοι ολοκλήρωσης για διάφορες κλάσεις συναρτήσεων.

Οι αλγόριθμοι οριοθετούν τα μαθηματικά.

Η οριοθέτηση μιας επιστήμης είναι απαραίτητη, χρήσιμη, και προσδίδει κύρος σ’ αυτήν. Συνεισφέρει στo να μην καταβάλλεται μάταιη προσπάθεια σε ανέφικτους στόχους. Αν το θεώρημα Lindemann–Weierstrass από το οποίο συνεπάγεται ότι δεν είναι δυνατός ο τετραγωνισμός του κύκλου αποδεικνυόταν νωρίτερα από το 1882, αυτό το πρόβλημα θα απασχολούσε την επιστήμη των μαθηματικών για λιγότερο χρόνο από όσο τελικά την απασχόλησε. Έτσι, τα θεωρήματα μη-πληρότητας του Γκέντελ, η απόδειξη των οποίων όπως είδαμε θεμελιώνεται πάνω στους αλγόριθμους, συνεισφέρουν, για παράδειγμα, στο να μην ασχολούνται οι μαθηματικοί με την απόδειξη της συνέπειας της συνολοθεωρίας ZFC εντός του ZFC, εκτός κι αν θέλουν να αποδείξουν ότι το ZFC είναι ασυνεπές.

Οι αλγόριθμοι όμως δεν οριοθετούν τα μαθηματικά μόνο μέσω των θεωρημάτων μη-πληρότητας του Γκέντελ, αλλά και πιο άμεσα, μέσω του θεωρήματος του τερματισμού του “πατέρα της πληροφορικής”, Άλαν Τούρινγκ. Το πρόβλημα του τερματισμού, το οποίο ο Τούρινγκ απέδειξε ότι είναι “μη-αποφασίσιμο, “ανάγεται” σε διάφορα γνωστά προβλήματα στα μαθηματικά, τα οποία, ως συνέπεια, αποδεικνύονται και αυτά “μη-αποφασίσιμα”. Για παράδειγμα, γνωρίζουμε ότι δεν υπάρχει αλγόριθμος ο οποίος επιλύει στο ℝ κάθε δευτεροβάθμια εξίσωση με πραγματικούς συντελεστές. Επίσης, ότι δεν υπάρχει αλγόριθμος για το πρόβλημα της ισότητας δύο πραγματικών αριθμών, καθώς και για πληθώρα άλλων προβλημάτων.

Η ύπαρξη αλγορίθμων είναι τόσο σημαντική για τα μαθηματικά, όσο και η ανυπαρξία τους!

-Όλα (σχεδόν) τα μαθηματικά μέσα σ’ έναν αλγόριθμο.

Η συνολοθεωρία ZFC αποτελεί δικαιολογημένα θεμέλιο των μαθηματικών, αφού μέχρι τώρα σχεδόν όλα (πλην ελάχιστων εξαιρέσεων) τα μαθηματικά θεωρήματα, αποδεικνύονται μέσα σ΄ αυτήν. Και επειδή πρόκειται για μια “πρωτοβάθμια” θεωρία, το πρόβλημα της “k-αποδειξιμότητας” (k-provability problem) γι’ αυτήν είναι αποφασίσιμο.

Με απλά λόγια αυτό μας λέει ότι δεδομένου ενός ισχυρισμού ο οποίος μπορεί να διατυπωθεί μέσα στην ZFC, υπάρχει αλγόριθμος ο οποίος απαντάει σωστά “ναι” ή “όχι” στο ακόλουθο ερώτημα:

υπάρχει απόδειξη στην ZFC για τον δεδομένο ισχυρισμό της οποίας το μέγεθος είναι το πολύ k σύμβολα; (μια απόδειξη είναι τυπικά μια συμβολοσειρά).

-Ένα από τα μεγαλύτερα ανοιχτά προβλήματα των μαθηματικών σήμερα (αν όχι το μεγαλύτερο) είναι ένα πρόβλημα πληροφορικής: το πρόβλημα P versus NP.

Το ινστιτούτο μαθηματικών Clay έχει ανακηρύξει επτά μαθηματικά βραβεία για την επίλυση αντίστοιχων επτά μαθηματικών προβλημάτων, γνωστών ως Millenium Problems (Προβλήματα της Χιλιετίας). Κάθε βραβείο συνοδεύεται από το χρηματικό ποσό του ενός εκατομμυρίου δολαρίων. Ένα από τα προβλήματα αυτά είναι το P versus NP, το οποίο μπορεί να διατυπωθεί στην ακόλουθη (σχετικά απλοποιημένη) μορφή:

Ο καλύτερος αλγόριθμος μέχρι τώρα για την επίλυση του προβλήματος της k-αποδειξιμότητας της θεωρίας ZFC (το οποίο διατυπώθηκε παραπάνω) είναι αρκετά αργός (“εκθετικός”) για να είναι χρήσιμος-αποδοτικός. Υπάρχει ένας αρκετά γρήγορος (“πολυωνυμικός”) αλγόριθμος, ώστε να είναι χρήσιμος-αποδοτικός;

Επίλογος

Τεκμηριώνεται, λοιπόν, επιστημονικά η Β’ (και η Α’) ανάθεση του μαθήματος των μαθηματικών σε πληροφορικούς στην δευτεροβάθμια εκπαίδευση; Τα συμπεράσματα δικά σας.

Μια δευτεροβάθμια εξίσωση με πραγματικούς συντελεστές η οποία είναι αδύνατο να επιλυθεί στο ℝ

τελευταία αναθεώρηση 4/3/2017, 23:00

Όπως έχω αποδείξει στην εργασία μου (2016), δεν υπάρχει γενική μέθοδος για την επίλυση της δευτεροβάθμιας εξίσωσης με πραγματικούς συντελεστές στο ℝ. Αυτό, βέβαια, δεν σημαίνει απαραίτητα ότι δεν ισχύει ότι κάθε δευτεροβάθμια εξίσωση με πραγματικούς συντελεστές μπορεί να επιλυθεί στο ℝ από μια ειδική (ανά εξίσωση) μέθοδο. Ωστόσο, θα αποδείξω παρακάτω το πιο ισχυρό αποτέλεσμα (-τουλάχιστον στα συνήθη μαθηματικά), ότι δηλαδή μία συγκεκριμένη δευτεροβάθμια εξίσωση με πραγματικούς συντελεστές δεν είναι δυνατό να επιλυθεί στο ℝ (ούτε από μια ειδική μέθοδο) με την προϋπόθεση βέβαια ότι τα συνήθη μαθηματικά έχουν κάποια γνωστή αξία. Όταν μιλάμε για “συνήθη μαθηματικά” εννοούμε το αξιωματικό σύστημα της θεωρίας των συνόλων ZFC, μιας και δεν υπάρχει κάποια συνήθης μαθηματική θεωρία η οποία δεν μπορεί να προσομοιωθεί από το ZFC – γι’ άλλωστε και το ZFC θεωρείται “θεμέλιο” και η πιο γενική μορφή των μαθηματικών. Όταν λέμε ότι “τα συνήθη μαθηματικά έχουν κάποια γνωστή αξία” εννοούμε ότι είναι συνεπή, δηλαδή δεν αποδεικνύουν κάποιον ισχυρισμό και την άρνησή του, δηλαδή μια αντίφαση. Ένα μαθηματικό σύστημα το οποίο αποδεικνύει μια αντίφαση έχει αποδειχτεί ότι μπορεί να αποδείξει οποιονδήποτε ισχυρισμό, κάτι που είναι γνωστό ως “αρχή της έκρηξης”. Ένα τέτοιο σύστημα δεν έχει κάποια γνωστή αξία.

Μια μηχανή Turing είναι ένα μαθηματικό αντικείμενο το οποίο εισήγαγε ο “πατέρας” – κατά κοινή ομολογία – της επιστήμης των υπολογιστών Alan Turing λίγο πριν τα μέσα του προηγούμενου αιώνα, και είναι ισοδύναμο με ένα πρόγραμμα σε μια σύγχρονη γλώσσα προγραμματισμού. “Ισοδύναμο” σημαίνει ότι για κάθε μηχανή Turing υπάρχει ένα πρόγραμμα σε Γλώσσα ΑΕΠΠ, c, java ή οποιαδήποτε άλλη σύγχρονη γλώσσα προγραμματισμού, το οποίο εκτελεί τον ίδιο υπολογισμό, αλλά και αντίστροφα για κάθε πρόγραμμα σε μια σύγχρονη γλώσσα προγραμματισμού, υπάρχει μια μηχανή Turing η οποία εκτελεί τον ίδιο υπολογισμό. Η διαφορά τους είναι ότι η μηχανή Turing είναι πιο απλό (και ένα από τα απλούστερα) υπολογιστικό μοντέλο, με την έννοια ότι η γενική περιγραφή της λειτουργίας μιας μηχανής Turing είναι σχετικά (πολύ) πιο σύντομη. Κάτι τέτοιο ευνοεί φυσικά την μελέτη των ιδιοτήτων του υπολογισμού.

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

Οι Yedidia & Aaronson (2016) κατασκεύασαν την μηχανή Turing Ζ η οποία δεν τερματίζει αν και μόνο αν το ZFC είναι συνεπές, ή ισοδύναμα τερματίζει αν και μόνο αν το ZFC δεν είναι συνεπές. Θεωρείστε τον πραγματικό αριθμό α ο οποίος ορίζεται ως εξής:

Ακέραιο μέρος της δεκαδικής αναπαράστασής του ίσο με το 0 και το νιοστό ψηφίο της δίνεται από την συνάρτηση f(ν), για ν θετικό ακέραιο:

f

Είναι προφανές ότι:

α = 0 αν και μόνο αν η μηχανή Turing Z δεν τερματίζει (ποτέ)

Ή ισοδύναμα:

α = 0 αν και μόνο αν το ZFC είναι συνεπές (1)

Ή ισοδύναμα:

α ≠ 0 αν και μόνο αν το ZFC είναι ασυνεπές (2)

Θεωρείστε τώρα την ακόλουθη δευτεροβάθμια εξίσωση:

e

Η διακρίνουσα του τριωνύμου είναι:

d

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

in1

Οπότε, από την (2) παίρνουμε ότι το ZFC είναι ασυνεπές, δηλαδή τα συνήθη μαθηματικά είναι άχρηστα.

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

in2

Οπότε, από από την (1) παίρνουμε ότι το ZFC είναι αποδεδειγμένα συνεπές από το ίδιο το ZFC. Το ZFC, όμως, προσομοιώνει, βέβαια, και την “πρωτοβάθμια αριθμητική Peano”, οπότε από το δεύτερο θεώρημα μη-πληρότητας του Gödel παίρνουμε ότι το ZFC είναι ασυνεπές (εφόσον αποδεικνύει το ίδιο την συνέπειά του)!

Με άλλα λόγια, οποιαδήποτε απόδειξη στα συνήθη μαθηματικά, είτε περί της ύπαρξης, είτε περί της μη-ύπαρξης λύσεων στο ℝ της παραπάνω εξίσωσης τα καθιστά άχρηστα. Άρα, αν δεν είναι άχρηστα, δεν υπάρχει απόδειξη εντός αυτών ούτε ότι η εξίσωση αυτή έχει λύσεις στο ℝ, ούτε ότι δεν έχει. Δηλαδή, η εξίσωση αυτή είναι αδύνατο να επιλυθεί στο ℝ με τα συνήθη μαθηματικά (αν τα τελευταία είναι συνεπή).

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

Τελευταία ενημέρωση 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 χρόνια νωρίτερα από τον Σκόλεμ.

Χωρίς “Aν”

Μ’ αυτήν την δημοσίευση θα εγκαινιάσω την κατηγορία “Ασκήσεις ΑΕΠΠ”.

Πρόβλημα:

Χωρίς να χρησιμοποιήσετε τις δομές επιλογής “Αν…Τότε…” και “Επίλεξε…Περίπτωση…”, γράψτε ένα πρόγραμμα το οποίο δέχεται ως είσοδο από το πληκτρολόγιο έναν φυσικό αριθμό (χωρίς έλεγχο εγκυρότητας) και εάν ο αριθμός αυτός είναι άρτιος εμφανίζει στην οθόνη “Άρτιος”, ενώ αν είναι περιττός εμφανίζει “Περιττός”.

Λύση:

ΠΡΟΓΡΑΜΜΑ ΧΩΡΙΣ_ΑΝ_1
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: κ
ΧΑΡΑΚΤΗΡΕΣ: Α[2]
ΑΡΧΗ
Α[1] <- «Άρτιος»
Α[2] <- «Περιττός»
ΓΡΑΨΕ «Δώσε έναν φυσικό αριθμό.»
ΔΙΑΒΑΣΕ κ
ΓΡΑΨΕ Α[κ MOD 2 + 1]
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Σχολιασμός, απόδειξη ορθότητας και ιστορική παρακίνηση

Δηλώνουμε έναν πίνακα χαρακτήρων 2 θέσεων και τον ακέραιο κ. Στην θέση 1 του πίνακα εκχωρούμε την τιμή «Άρτιος» ενώ στην θέση 2 την τιμή «Περιττός». Τότε, η απάντηση του προβλήματος δίνεται από την τιμή Α[κ MOD 2 + 1] , δηλαδή από το “αλφαριθμητικό”* που βρίσκεται στην θέση κ MOD 2 + 1 του πίνακα Α.

Για να αποδείξουμε την ορθότητα του προγράμματος θα πρέπει να αποδείξουμε δύο πράγματα:

1) Αν ο κ είναι άρτιος, τότε το πρόγραμμα εμφανίζει “Άρτιος”.

2) Αν ο κ είναι περιττός, τότε το πρόγραμμα εμφανίζει “Περιττός”.

Απόδειξη:

Αν ο κ είναι άρτιος, τότε κ MOD 2 = 0, άρα κ MOD 2 + 1 = 1. Άρα, το πρόγραμμα θα εμφανίσει το Α[1], το οποίο είναι “Άρτιος”

Αν ο κ είναι περιττός, τότε κ Mod 2 = 1, άρα κ MOD 2 + 1 = 2. Άρα, το πρόγραμμα θα εμφανίσει το Α[2], το οποίο είναι “Περιττός”.

Το 1931 ο μαθηματικός Κουρτ Γκέντελ δημοσίευσε την απόδειξη των περίφημων θεωρημάτων “μη-πληρότητας”. Στην απόδειξη χρησιμοποίησε μία κλάση συναρτήσεων γνωστών ως “μ-Αναδρομικές” (“μ-Recursive”). Αργότερα, αποδείχτηκε ότι οι “μ-Αναδρομικές” συναρτήσεις μπορούν να υπολογίσουν ό,τι υπολογίζει και ένα πρόγραμμα μιας μοντέρνας γλώσσας προγραμματισμού. Ένα υποσύνολο των μ-Αναδρομικών συναρτήσεων είναι οι “πρωτόγονες αναδρομικές” (“primitive recursive”), οι οποίες κατασκευάζονται με ειδική χρήση κάποιων άλλων συναρτήσεων, οι οποίες είναι γνωστές ως “βασικές”. Μια από τις τελευταίες είναι και η “προβολική” συνάρτηση. Η συνάρτηση αυτή, έστω P, ορίζεται ως εξής:

P(n1, n2, … , nk, i) = ni

Η σημασία της είναι η εξής: δοσμένων k (>0) φυσικών αριθμών n1, n2, … , nk και ενός φυσικού αριθμού i τέτοιου ώστε 0 < i ≤ k, η συνάρτηση ουσιαστικά επιλέγει τον αριθμό ni. Η επιλογή στον σύγχρονο προγραμματισμό γίνεται με τις δομές επιλογής “Αν…Τότε…” και “Επίλεξε…Περίπτωση…” ή (λιγότερο συχνά) με την χρήση ενός πίνακα: Η εντολή A[i] ενός πίνακα k θέσεων, όπου 0 < i ≤ k, επιλέγει το στοιχείο του πίνακα που βρίσκεται στην θέση i – και αποτελεί ουσιαστικά μια μορφή “προβολικής” συνάρτησης ή μια μορφή δομής επιλογής (η οποία δεν αναφέρεται συνήθως ως τέτοια).

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

Χωρίς να χρησιμοποιήσετε τις δομές επιλογής “Αν…Τότε…” και “Επίλεξε…Περίπτωση…”, γράψτε ένα πρόγραμμα το οποίο δέχεται ως είσοδο από το πληκτρολόγιο έναν φυσικό αριθμό (χωρίς έλεγχο εγκυρότητας) και εάν ο αριθμός αυτός είναι μεγαλύτερος από το 5 εμφανίζει στην οθόνη “Μεγαλύτερος του 5”, αν είναι μικρότερος του 5 εμφανίζει “Μικρότερος του 5” και εάν είναι ίσος με 5 εμφανίζει “Ίσος με 5”.

*Θεωρώ ότι αυτό που εννοείται με τον όρο “αλφαριθμητικό” του σχολικού βιβλίου είναι αυτό που συνήθως (και πιο σωστά) λέμε “συμβολοσειρά” (“string” είναι ο διεθνής όρος). Συνήθως, ως “αλφαριθμητικό” (“alphanumeric”) αναφέρεται διεθνώς μια ακολουθία από αλφαβητικά σύμβολα και αριθμητικά ψηφία. Η “συμβολοσειρά” είναι κάτι ευρύτερο, μπορεί να περιλαμβάνει όλα τα σύμβολα του πληκτρολογίου (και όλα τα σύμβολα γενικότερα).