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

Ως γνωστόν, με βάση το άρθρο 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 (το οποίο διατυπώθηκε παραπάνω) είναι αρκετά αργός (“εκθετικός”) για να είναι χρήσιμος-αποδοτικός. Υπάρχει ένας αρκετά γρήγορος (“πολυωνυμικός”) αλγόριθμος, ώστε να είναι χρήσιμος-αποδοτικός;

Επίλογος

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

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

Τελευταία ενημέρωση 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”) αναφέρεται διεθνώς μια ακολουθία από αλφαβητικά σύμβολα και αριθμητικά ψηφία. Η “συμβολοσειρά” είναι κάτι ευρύτερο, μπορεί να περιλαμβάνει όλα τα σύμβολα του πληκτρολογίου (και όλα τα σύμβολα γενικότερα).