ΑΕΠΠ 2018 – Ενδεικτικές απαντήσεις πανελλαδικών θεμάτων

Advertisements

Γενίκευση συνέπειας του θεωρήματος Bolzano

Αν δύο συναρτήσεις f, g είναι συνεχείς σε κάποιο διάστημα Δ και f(x)g(x) για κάθε x∈Δ, τότε ή f(x)>g(x) για κάθε x∈Δ ή f(x)<g(x) για κάθε x∈Δ, δηλαδή θα λέγαμε ότι η γραφική παράσταση κάποιας από τις δύο συναρτήσεις “διατηρείται πάνω” από την γραφική παράσταση της άλλης στο Δ.

Διαίσθηση απόδειξης

Θεωρούμε την συνέπεια του θεωρήματος Bolzano (σ. 74 του σχολικού βιβλίου, οι χρωματικές επισημάνσεις δικές μου):

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

Η τελευταία πρόταση μπορεί να διατυπωθεί ισοδύναμα ως εξής (τα ισοδύναμα τμήματα επισημαίνονται με το ίδιο χρώμα):

Έστω η συνάρτηση g για την οποία ισχύει g(x)=0 για κάθε xΔ. Αν μια συνάρτηση f είναι συνεχής στο Δ και f(x)≠g(x) για κάθε x∈Δ, τότε ή f(x)>g(x) για κάθε x∈Δ ή f(x)<g(x) για κάθε x∈Δ, δηλαδή η γραφική παράσταση κάποιας από τις δύο συναρτήσεις “διατηρείται πάνω” από την γραφική παράσταση της άλλης στο Δ.

gg1

Οπότε, δημιουργείται η διαίσθηση της γενίκευσης της παραπάνω συνέπειας του θεωρήματος Bolzano, θεωρώντας στην θέση της g μια οποιαδήποτε συνεχή στο Δ συνάρτηση, δηλαδή θεωρώντας το θεώρημα στην αρχή αυτής της δημοσίευσης.

Απόδειξη:

Θεωρούμε την συνάρτηση h ορισμένη στο Δ με h(x) = f(x) – g(x).

Για κάθε xΔ έχουμε:

f(x)≠g(x) ⇔ f(x) – g(x) ≠ 0 ⇔ h(x) ≠ 0 (1)

Ακόμη:

η h είναι συνεχής στο Δ, αφού προκύπτει από συνήθεις πράξεις μεταξύ συνεχών στο Δ συναρτήσεων (2)

Από την συνέπεια του θεωρήματος Bolzano (σχόλιο σελ. 74 σχολικού βιβλίου) λόγω των (1), (2), παίρνουμε ότι η h “διατηρεί πρόσημο” στο Δ, οπότε:

ή h(x) >0 για κάθε x∈Δ ή h(x) <0 για κάθε x∈Δ ⇔

ή f(x) – g(x) >0 για κάθε x∈Δ ή f(x) – g(x) <0 για κάθε x∈Δ⇔

ή f(x) > g(x) για κάθε x∈Δ ή f(x) < g(x) για κάθε x∈Δ ∎

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

Σημειώσεις πάνω στο θεώρημα 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))

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

Μια παρατήρηση περί Μαθηματικής Λογικής σε άσκηση του βιβλίου Μαθηματικών της Β’ Γυμνασίου

Στην σελίδα 43 του σχολικού βιβλίου Μαθηματικών της Β’ Γυμνασίου υπάρχει η εξής άσκηση:

Καταρχάς, υποθέτουμε ότι η εκφώνηση εννοεί “Για κάθε θετικό αριθμό x, στις παρακάτω προτάσεις επιλέξτε τη σωστή απάντηση”. Πολλές φορές στα Μαθηματικά χρειάζεται να υποθέσουμε αυτό το “για κάθε” το οποίο δεν λέγεται ρητά. Αυτό ίσως δεν είναι πρόβλημα για κάποιον που έχει κάποια εξοικείωση με τα Μαθηματικά, ωστόσο θεωρώ δεν ενδείκνυται κατά την διδασκαλία των Μαθηματικών σε αρχάριους. Η έννοια μιας ιδιότητας η οποία αφορά όλα τα στοιχεία ενός συνόλου, η οποία ισχύει για κάθε στοιχείο ενός συνόλου, είναι απλή στην κατανόηση όσο και στοιχειώδης για τα Μαθηματικά. Δεν βλέπω κάποιον λόγο για να υπονοείται χωρίς να λέγεται ρητά, ειδικά σε τέτοιες περιπτώσεις. Και είναι κάτι που συμβαίνει ακόμα και σε θέματα Πανελλαδικών εξετάσεων, για παράδειγμα στο θέμα Α1 των Πανελλαδικών του 2017:

Φυσικά, αυτό που εννοείται είναι “Για κάθε συνάρτηση f η οποία είναι συνεχής σε ένα διάστημα Δ, αν f'(x)>0 …”.

Ας υποθέσουμε όμως ότι κάτι τέτοιο δεν δημιουργεί πρόβλημα εδώ – έχουμε κατανοήσει καλά τη σημασία του “για κάθε” – και ας εστιάσουμε στο ερώτημα 3 της άσκησης. Καλούμαστε, λοιπόν, δεδομένης της “υπόθεσης” (), να βρούμε το “συμπέρασμα” (ένα (;) από τα Α, Β, Γ, Δ, Ε) σ’ έναν “τύπο” της μορφής (έτσι ώστε ο τελευταίος να είναι αληθής):

Αν “ΥΠΟΘΕΣΗ”, ΤΟΤΕ “ΣΥΜΠΕΡΑΣΜΑ”

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

Το θέμα εδώ είναι ότι η υπόθεση  είναι ψευδής για κάθε θετικό αριθμό x, γεγονός το οποίο μας επιτρέπει να επιλέξουμε ως σωστές όλες (!) τις πιθανές απαντήσεις, δηλαδή την Α, την Β, την Γ, την Δ και την Ε.  Αυτό συμβαίνει διότι στα Μαθηματικά ένας τύπος της μορφής Αν “ΥΠΟΘΕΣΗ”, ΤΟΤΕ “ΣΥΜΠΕΡΑΣΜΑ” είναι αληθής ανεξάρτητα από το συμπέρασμα, αν η υπόθεση είναι ψευδής. Κάτι τέτοιο είναι σύμφωνο με την κοινή λογική, και τα Μαθηματικά διέπονται από την κοινή λογική.

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

Αν βρέχει, τότε έχει συννεφιά (Π1)

Διάλεξα το παραπάνω παράδειγμα επίτηδες, για να δείξω ότι το μαθηματικό/λογικό σχήμα “υπόθεση-συμπέρασμα” δεν πρέπει να συγχέεται με το «φυσικό» σχήμα “αίτιο-αποτέλεσμα” – η βροχή, προφανώς, δεν είναι το φυσικό αίτιο της συννεφιάς!

Καταρχάς, η Π1 δεν μας δίνει καμία πληροφορία, ούτε για το αν βρέχει, ούτε για το αν έχει συννεφιά, με άλλα λόγια δεν μας δίνει καμία πληροφορία ούτε για την υπόθεση την ίδια, ούτε για το συμπέρασμα το ίδιο (αντίστροφα, όμως, άραγε η ισχύς ή μη της υπόθεσης της ίδιας, ή η ισχύς ή μη του συμπεράσματος του ίδιου, μας δίνουν κάποια πληροφορία για την ισχύ της Π1 ; Θα το δούμε παρακάτω). Μας δίνει όμως την πληροφορία ότι στην περίπτωση που ισχύει η υπόθεση, τότε (υποχρεωτικά) ισχύει και το συμπέρασμα. Με άλλα λόγια, αρκεί να ισχύει η υπόθεση για να ισχύει το συμπέρασμα. Ή η ισχύς της υπόθεσης είναι ικανή συνθήκη ώστε να ισχύει το συμπέρασμα.

Ας θεωρήσουμε τώρα ότι η υπόθεση δεν ισχύει. Μεταβάλλει αυτό την ισχύ της πρότασης Π1; Δηλαδή, όταν δεν βρέχει, αλλάζει κάτι όσον αφορά την ισχύ της πρότασης “Αν βρέχει, τότε έχει συννεφιά”; Φυσικά και  δεν αλλάζει,  επομένως η μη ισχύς της υπόθεσης δεν επηρεάζει την ισχύ μιας πρότασης της μορφής της Π1.

Για να δούμε τι γίνεται όταν η υπόθεση ισχύει. Δύο περιπτώσεις έχουμε εδώ: είτε ισχύει το συμπέρασμα, είτε δεν ισχύει. Το να ισχύει το συμπέρασμα με βάση τα παραπάνω καθιστά την Π1 αληθή: απολύτως λογικό, βρέχει και έχει συννεφιά, η Π1 ισχύει. Αν όμως δεν ισχύει το συμπέρασμα, δηλαδή αν βρέχει και δεν έχει συννεφιά, τότε η αλήθεια της Π1 καταρρέει. Με άλλα λόγια η αλήθεια της Π1 καταρρέει μόνο αν βρέχει και δεν έχει συννεφιά. Σ’ όλες τις άλλες περιπτώσεις η Π1 παραμένει αληθής.

Αυτή είναι κοινή-καθημερινή λογική και στα Μαθηματικά αποκρυσταλλώνεται στον παρακάτω “πίνακα αλήθειας”, όπου παρουσιάζονται όλες οι δυνατές τιμές αλήθειας της υπόθεσης και του συμπεράσματος μαζί με την αντίστοιχη λογική αποτίμηση της συνεπαγωγής, δηλαδή του τύπου της μορφής ΑΝ “ΥΠΟΘΕΣΗ”, ΤΟΤΕ “ΣΥΜΠΕΡΑΣΜΑ”:

Παρατηρείστε ότι όταν η υπόθεση είναι ψευδής δεν χρειάζεται να γνωρίζουμε το συμπέρασμα για να αποφασίσουμε την ισχύ της συνεπαγωγής, ανεξάρτητα από το συμπέρασμα η συνεπαγωγή είναι αληθής. Με άλλα λόγια, από μια ψευδή υπόθεση, μπορούμε να βγάλουμε οποιοδήποτε συμπέρασμα. Επομένως, στο 3ο ερώτημα της δεδομένης άσκησης όπου για κάθε θετικό αριθμό x η υπόθεση είναι ψευδής, μπορούμε να βγάλουμε οποιοδήποτε συμπέρασμα, για κάθε θετικό αριθμό x. Άρα, όλες οι δεδομένες απαντήσεις είναι σωστές (Α, Β, Γ, Δ και Ε).

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

Γιατί δεν υπάρχει πρόσβαση στα τμήματα Μαθηματικών από το πεδίο Επιστημών Οικονομίας και Πληροφορικής;

Ο μαθηματικός Κουρτ Γκέντελ. Απέδειξε ότι οι πρωτόγονες αναδρομικές συναρτήσεις είναι αναπαραστάσιμες στην πρωτοβάθμια αριθμητική Peano.

Οι υποψήφιοι/ες του πεδίου Επιστημών Οικονομίας και Πληροφορικής εξετάζονται στα ίδια ακριβώς θέματα με τους υποψήφιους/ες του πεδίου Θετικών και Τεχνολογικών Επιστημών για το μάθημα των Μαθηματικών, ενώ εξετάζονται και στο μάθημα της Ανάπτυξης Εφαρμογών σε Προγραμματιστικό Περιβάλλον, το οποίο έχει ισχυρή δομική συνάφεια με επιπλέον τρία (!) μαθηματικά αντικείμενα:

  1. Αλγόριθμοι και γενικότερα υπολογιστικές διαδικασίες (αναπαριστάνονται στην πρωτοβάθμια αριθμητική Peano)
  2. Δίτιμη Άλγεβρα Boole («λογικές εφράσεις» της Γλώσσας της ΑΕΠΠ )
  3.  Προτασιακή Λογική (η συνάφεια με την  δίτιμη άλγεβρα Boole είναι προφανής)

Επομένως, οι υποψήφιοι/ες του πεδίου Επιστημών Οικονομίας και Πληροφορικής εξετάζονται πρακτικά σε συνάφεια με τέσσερα (!) μαθηματικά αντικείμενα, και όχι μόνο στην Ανάλυση, όπως συμβαίνει με τους υποψήφιους/ες του πεδίου Θετικών και Τεχνολογικών Επιστημών. Παρόλ’ αυτά, οι υποψήφιοι/ες του πεδίου Επιστημών Οικονομίας και Πληροφορικής δεν έχουν πρόσβαση στα τμήματα Μαθηματικών;

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

 

Εισαγωγή στην ΑΕΠΠ – Η έννοια του αλγορίθμου

Το θέμα Γ των πανελλαδικών της ΑΕΠΠ και η ταξινόμηση φυσαλίδας (bubble sort)

Το πιο “δύσκολο” σημείο του θέματος Γ των φετινών πανελλαδικών (2017) ήταν κατά κοινή ομολογία η ιδιαίτερη μορφή ταξινόμησης η οποία ζητήθηκε στο υποερώτημα Γ3. Τέτοιου είδους προβλήματα (ταξινόμησης) γίνονται πολύ εύκολα αν θεωρήσουμε τον ακόλουθο γενικό ορισμό της ταξινόμησης:

α) Θεωρείστε έναν μονοδιάστατο πίνακα Α[μ] τύπου Τ.

β) Θεωρείστε μια συνάρτηση Διάταξη(χ1, χ2, …) λογικού τύπου με τουλάχιστον δύο τυπικές παραμέτρους (οι δύο πρώτες τύπου Τ), η οποία ορίζεται στην γλώσσα της ΑΕΠΠ για κάθε τιμή των παραμέτρων χ1, χ2, οι οποίες παίρνουν τιμές αποκλειστικά από τα στοιχεία του πίνακα Α. Θεωρείστε ότι για την συνάρτηση αυτή ισχύει, για κάποιες παραμέτρους π1, π2, π3:

i) Αν ισχύει Διάταξη(π1,π2,…) = Αληθής και Διάταξη(π2,π1,…) = Αληθής, τότε ισχύει π1=π2

ii) Αν ισχύει Διάταξη(π1,π2,…) = Αληθής και Διάταξη(π2, π3,…) = Αληθής, τότε ισχύει Διάταξη(π1,π3,…) = Αληθής

Σημειώνεται ότι η σημασία της έκφρασης Αν…, τότε … στα i) και ii) αμέσως παραπάνω δεν έχει καμία σχέση με την “δομή επιλογής” της Γλώσσας της ΑΕΠΠ, αλλά είναι η “λογική συνεπαγωγή” (γνωστή ίσως και από τα Μαθηματικά), η οποία συμβολίζεται συνήθως με “. Για κάθε ζεύγος προτάσεων (λογικών εκφράσεων) Α, Β ο πίνακας τιμών της λογικής συνεπαγωγής είναι:

Παρατηρούμε, δηλαδή, ότι η λογική συνεπαγωγή Α → Β είναι Ψευδής μόνο όταν η Α είναι Αληθής και η Β είναι Ψευδής.

Οπότε, η συνάρτηση Συνεπάγεται(Α,Β) μπορεί να κατασκευαστεί στην Γλώσσα της ΑΕΠΠ:

Μ’ αυτόν τον τρόπο, θεωρώντας τις λογικές μεταβλητές Α, Β, Γ και Δ οι παραπάνω δύο προϋποθέσεις i), ii) γράφονται (και απαιτείται να είναι Αληθείς) στην Γλώσσα της ΑΕΠΠ:

i) Συνεπάγεται(Α, Β), όπου:

Α <- Διάταξη(π1,π2,…) KAI Διάταξη(π2,π1,…) και

Β <- π1 = π2

ii) Συνεπάγεται(Γ, Δ), όπου

Γ <- Διάταξη(π1,π2,…) ΚΑΙ Διάταξη(π2, π3,…) και

Δ<- Διάταξη(π1,π3,…)

 

Ορισμός: ο πίνακας Α[μ] είναι ταξινομημένος σύμφωνα με την συνάρτηση Διάταξη(π1,π2,…) όταν για κάθε ζευγάρι διαδοχικών στοιχείων του πίνακα με δείκτες i και i -1, με 2i≤μ, ισχύει Διάταξη(Α[i-1], Α[i],…) = Αληθής.

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

Συνεπάγεται από τον παραπάνω ορισμό ότι:

Ο πίνακας Α[μ] δεν είναι ταξινομημένος σύμφωνα με την συνάρτηση Διάταξη(π1,π2,…) όταν υπάρχει (τουλάχιστον ένα) ζευγάρι διαδοχικών στοιχείων του πίνακα με δείκτες i και i -1, με 2≤i≤μ, τέτοιο ώστε Διάταξη(Α[i-1], Α[i],…) = Ψευδής.

Θεώρημα: Ο πίνακας Α μπορεί να ταξινομηθεί σύμφωνα με την συνάρτηση Διάταξη(π1,π2,…) με τον παρακάτω αλγόριθμο, τον οποίο θα ονομάζαμε “γενικό αλγόριθμο ταξινόμησης φυσαλίδας”:

Όπου η διαδικασία ΑΝΤΙΜΕΤΑΘΕΣΕ ορίζεται ως εξής, για κάθε τύπο Τ δεδομένων της Γλώσσας:

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

Ας δούμε τώρα όμως την περίπτωση του υποερωτήματος Γ3. Εύκολα μπορούμε να διαπιστώσουμε ότι η συνάρτηση Διάταξη(χ1,χ2,…) η οποία αντιστοιχεί στην συγκεκριμένη περίπτωση είναι:

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

Ένα επιπλέον παράδειγμα:

Δίνεται πίνακας χαρακτήρων Π[100] με κάθε στοιχείο να παίρνει μία από τις ακόλουθες τρεις δυνατές τιμές: “Πρώτος”, “Δεύτερος”, “Τρίτος”. Να κατασκευάσετε τμήμα προγράμματος, το οποίο να αναδιατάσσει τον πίνακα Π έτσι ώστε όλα τα στοιχεία με την τιμή “Πρώτος” να βρίσκονται στην αρχή του πίνακα, να ακολουθούν όλα τα στοιχεία με την τιμή “Δεύτερος” και στο τέλος όλα τα στοιχεία με την τιμή “Τρίτος”.

Θεωρούμε την παρακάτω συνάρτηση Διάταξη(χ1,χ2):

Και την χρησιμοποιούμε στον “γενικό αλγόριθμο ταξινόμησης φυσαλίδας”:

Φυσικά, όπως σε κάθε περίπτωση, μπορούμε να μην εμφανίσουμε “ρητά” την συνάρτηση Διάταξη:

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

Σχετικά με το θέμα Α1 των πανελλαδικών της ΑΕΠΠ του 2017

Στο φετινό θέμα Α1 των πανελλαδικών της ΑΕΠΠ το πρώτο  υποερώτημα αφορούσε την ισχύ της ισοδυναμίας δύο λογικών εκφράσεων:

Η έκφραση ΟΧΙ(Κ=10 ΚΑΙ Χ>7) είναι ισοδύναμη με την έκφραση (Κ<>10 Ή Χ<=7)” (Σωστό ή Λάθος)

Η παραπάνω ισοδυναμία συνεπάγεται από τον έναν από τους δύο γνωστούς στην Πληροφορική “νόμους De Morgan”, για κάθε λογική έκφραση Α, για κάθε λογική έκφραση Β:

(ΟΧΙ (Α ΚΑΙ Β)) ↔ ((ΟΧΙ Α) Ή (ΟΧΙ Β))

(ΟΧΙ (Α Ή Β)) ↔ ((ΟΧΙ Α) ΚΑΙ (ΟΧΙ Β))

Θυμίζει λίγο την γνωστή “επιμεριστική” ιδιότητα, με τον τελεστή ΟΧΙ να εφαρμόζεται σε κάθε έναν από τους τελεστέους των τελεστών ΚΑΙ/Ή στο πρώτο μέλος της ισοδυναμίας, και με τον τελεστή ΚΑΙ να μετατρέπεται σε Ή, ενώ τον Ή να μετατρέπεται σε ΚΑΙ στο δεύτερο μέλος.

Αν και ο τελεστής της λογικής ισοδυναμίας “↔”  δεν ορίζεται ως λογικός τελεστής στην Γλώσσα της ΑΕΠΠ,  τον ρόλο αυτού του τελεστή στην τελευταία αναλαμβάνει ο γνωστός λογικός τελεστής της ισότητας “=”, όπως θα δούμε παρακάτω. Οπότε, οι νόμοι De Morgan στην Γλώσσα της ΑΕΠΠ γράφονται (και είναι Αληθείς), για κάθε λογική έκφραση Α, για κάθε λογική έκφραση Β:

(ΟΧΙ (Α ΚΑΙ Β)) = ((ΟΧΙ Α) Ή (ΟΧΙ Β))

(ΟΧΙ (Α Ή Β)) = ((ΟΧΙ Α) ΚΑΙ (ΟΧΙ Β))

Αντικαθιστώντας την λογική έκφραση Α με την λογική έκφραση Κ=10, την Β με την Χ>7 (αφού οι παραπάνω νόμοι ισχύουν για κάθε ζεύγος λογικών εκφράσεων Α, Β) και εφαρμόζοντας τον πρώτο νόμο De Morgan παραπάνω, παίρνουμε:

(ΟΧΙ(Κ=10 ΚΑΙ Χ>7)) = ((ΟΧΙ Κ=10) Ή (ΟΧΙ Χ>7)) →

((ΟΧΙ Κ=10) Ή (ΟΧΙ Χ>7)) = (Κ <> 10 Ή Χ <= 7)

Ωστόσο, οι νόμοι De Morgan δεν διδάσκονται στην δευτεροβάθμια εκπαίδευση, οπότε το πρόβλημα μπορεί να αντιμετωπιστεί με τη χρήση πίνακα παρόμοιου με αυτόν ο οποίος δίνεται στην σελ. 43 του σχολικού βιβλίου της ΑΕΠΠ, για κάθε διάταξη τιμών (“αποτίμηση”) των λογικών εκφράσεων (ή “προτάσεων”) Α, Β.

Πίνακας τιμών για τις λογικές πράξεις Ή, ΚΑΙ και ΟΧΙ, σελ. 43 σχολικού βιβλίου ΑΕΠΠ (η σκίαση με μπλε και κόκκινο χρώμα δική μου)

Ένας τέτοιος πίνακας λοιπόν μπορεί να κατασκευαστεί όχι μόνο για τις λογικές εκφράσεις “Α Ή Β”, “Α ΚΑΙ Β” και “ΌΧΙ Α”, αλλά…για κάθε λογική έκφραση!

Πριν κατασκευάσουμε όμως έναν τέτοιο πίνακα για τις δύο λογικές εκφράσεις του παραπάνω υποερωτήματος των πανελλαδικών του 2017, ας δούμε την έννοια της λογικής ισοδυναμίας. Η λογική ισοδυναμία (ή απλά «ισοδυναμία») ορίζεται ως εξής: δύο προτάσεις (ή λογικές εκφράσεις) είναι ισοδύναμες όταν είναι και οι δύο Αληθείς ή όταν είναι και οι δύο Ψευδείς. Με άλλα λόγια δύο προτάσεις είναι λογικά ισοδύναμες όταν είναι…λογικά ίσες! Επομένως, στην Γλώσσα της ΑΕΠΠ η λογική ισοδυναμία μεταξύ δύο λογικών εκφράσεων εκφράζεται με τον τελεστή της ισότητας “=”! Δίνεται παρακάτω ο πίνακας τιμών της λογικής ισοδυναμίας:

Πίνακας τιμών της λογικής ισοδυναμίας

Ας δούμε τώρα όμως τον πίνακα τιμών για τις λογικές εκφράσεις του θέματος Α1.

Πίνακας τιμών των λογικών εκφράσεων του πρώτου υποερωτήματος του θέματος Α1 των πανελλαδικών της ΑΕΠΠ του 2017

Παρατηρούμε ότι για κάθε αποτίμηση των λογικών εκφράσεων Κ=10” και “Χ>7”, οι τιμές των λογικών εκφράσεων “ΟΧΙ (Κ=10 ΚΑΙ Χ>7)” και “Κ<>10 Ή Χ <= 7” είναι ίσες, άρα οι λογικές αυτές εκφράσεις είναι ισοδύναμες.

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

Ενδεικτικές απαντήσεις πανελληνίων θεμάτων ΑΕΠΠ 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 δεν έχει αποδειχτεί, ούτε καταρριφθεί) και γιατί;

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

– Περατότητα

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

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