Σχετικά με το θέμα Α2 της Πληροφορικής των Πανελλαδικών

(Διευκρίνιση: το σχόλιό μου δεν αφορά την περίπτωση απάντησης «και οι 4 κόμβοι σε ένα δέντρο» – αυτό δεν συμφωνεί με την δεδομένη εκφώνηση)

Το επιστημονικό-διδακτικό πλαίσιο αναφορικά με κάθε επιστήμη επιβάλλει μία σαφή θεωρητική προσέγγιση ως βάση για την επίλυση μιας άσκησης/θέματος. Δεν είναι δυνατόν κάποια ενδεικτική λύση να μετατρέπεται σε θεωρητική δικαιολόγηση και τελικά σε μοναδικό τρόπο λύσης. Στην σελίδα 51 του βιβλίου Πληροφορική-Συμπληρωματικό Εκπαιδευτικό Υλικό υπάρχει μία άσκηση παρόμοια με αυτήν του εν λόγω θέματος:

Το βιβλίο δεν αναφέρει πουθενά κάποιον συγκεκριμένο αλγόριθμο τοποθέτησης-προσθήκης κόμβου σε δυαδικό δέντρο αναζήτησης. Συνεπώς, το επιστημονικά συνεπές συμπέρασμα είναι ότι ο κόμβος μπορεί να τοποθετηθεί οπουδήποτε, αρκεί το αποτέλεσμα που θα προκύψει να συνιστά δυαδικό δέντρο αναζήτησης. Και αυτό το συμπέρασμα δεν μπορεί να αλλάξει μετά την παρουσίαση μιας οποιασδήποτε ενδεικτικής λύσης (εξ’ ου και ενδεικτική).

Στης σελίδα 28, στο Βιβλίο Μαθητή-Πληροφορική-Συμπληρωματικό Εκπαιδευτικό Υλικό – Ενδεικτικές Λύσεις Ασκήσεων παρουσιάζεται κάποιος συγκεκριμένος αλγόριθμος προσθήκης κόμβου. Αν αυτός είναι ο ενδεδειγμένος και απαιτούμενος τρόπος για την προσθήκη ενός κόμβου σε δυαδικό δέντρο αναζήτησης θα έπρεπε να αναφέρεται στο βιβλίο Πληροφορική-Συμπληρωματικό Εκπαιδευτικό Υλικό και όχι στις Ενδεικτικές Λύσεις των ασκήσεων. Επόμενως, ξεκάθαρα, για το θέμα Α2 των Πανελλαδικών οποιαδήποτε λύση έχει ως αποτέλεσμα ένα δυαδικό δέντρο αναζήτησης (για κάθε μία από τις 4 περιπτώσεις) θα πρέπει να πάρει την μέγιστη βαθμολογία.

Επιπλέον, θα πρέπει να τονιστεί ότι το παραπάνω αναφερόμενο βιβλίο Βιβλίο Μαθητή-Πληροφορική-Συμπληρωματικό Εκπαιδευτικό Υλικό – Ενδεικτικές Λύσεις Ασκήσεων δεν περιλαμβάνεται στην εξεταστέα ύλη των Πανελλαδικών, έτσι όπως η τελευταία ορίζεται στο παρακάτω ΦΕΚ:

https://www.e-nomothesia.gr/kat-ekpaideuse/deuterobathmia-ekpaideuse/upourgike-apophase-83871-d2-2021.html?fbclid=IwAR0YjEsh45XKvKbWaYWXre31RS2Gr862Ib3SQKBppWFuHv6WBvhac3RVr9s

Γιώργος Μπουγιούκας, πληροφορικός, βιοπληροφορικός (MSc)

“Ελληνική PISA”, PISA και “εφαρμοσμένες επιστήμες”

Ο σκοπός μιας εκπαιδευτικής διαδικασίας δεν είναι να μας μάθει μόνο ότι 1+1=2, αλλά και την πρακτική-εφαρμοστική γενίκευση: 1 πορτοκάλι και 1 πορτοκάλι κάνουν δύο πορτοκάλια. Πρόσφατα, έχει ανακοινωθεί η πρόθεση του Υπουργείου Παιδείας για ίδρυση ή μετατροπή τμημάτων τριτοβάθμιας εκπαίδευσης σε τμήματα “εφαρμοσμένων” επιστημών με χαμηλότερη ΕΒΕ και μη δυνατότητα ανάληψης διδακτορικού από τους απόφοιτούς τους. Ξεκάθαρα, εδώ υπάρχει μία ιδεολογία: το “εφαρμοσμένο” είναι κατώτερο από το “θεωρητικό”.

Ωστόσο, η επιστημονική πραγματικότητα είναι ακριβώς αντίθετη, διότι, για να εφαρμόσεις μία επιστήμη πρέπει να την κατέχεις πρώτα θεωρητικά: ο “εφαρμοσμένος” τομέας αποτελεί έκφραση της ολότητας θεωρία-πράξη. Είναι κατώτερο το Τμήμα Εφαρμοσμένων Μαθηματικών του ΕΜΠ από το Τμήμα Μαθηματικών του ΕΚΠΑ; Θα αφαιρεθεί από τους αποφοίτους του πρώτου η δυνατότητα ανάληψης διδακτορικού;

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

Κάπως έτσι γεννήθηκε η ιδέα των εξετάσεων PISA: εκφράζουν μία ριζοσπαστική υπέρβαση του υφιστάμενου εκπαιδευτικού καθεστώτος με έμφαση στην ανάπτυξη της ικανότητας εφαρμοστικής γενίκευσης των θεωρητικών σημασιών (και όχι την σκοτεινή μεθόδευση ενός ιερατείου που συνωμοτεί πίσω από κλειστές κουρτίνες).

Ας δούμε ένα χαρακτηριστικό παράδειγμα από τα ενδεικτικά θέματα Μαθηματικών Γυμνασίου στην ιστοσελίδα της PISA:

https://pisa2022-maths.oecd.org/ca/index.html#Examples

For, IF, THEN, ELSE. Πρόκειται για τις αλγοριθμικές δομές της Πληροφορικής (“δομή επανάληψης” και “δομή επιλογής”). Τι πιο λογικό, στο επιστημονικό πλαίσιο της εποχής μας, τα Μαθηματικά να πλαισιώνονται/γενικεύονται από την Πληροφορική. Η Πληροφορική είναι αυτή που ανεβάζει τα Μαθηματικά σε πραγματικά άλλο επίπεδο στις μέρες μας.

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

http://iep.edu.gr/images/eedx/themata/DIM_CLAST_%CE%9C%CE%91%CE%A4%CE%97_SUBJECT_1_79.pdf

Καμία απολύτως σχέση με την λογική της PISA. Εδώ έχουμε εξετάσεις στα απολύτως καθιερωμένα, χωρίς ίχνος υπέρβασης. Επομένως, ο χαρακτηρισμός “ελληνική PISA” είναι τουλάχιστον ατυχής, όπως και ο χαρακτηρισμός “εφαρμοσμένες επιστήμες” για τμήματα με χαμηλότερη ΕΒΕ και μη-δυνατότητα λήψης διδακτορικού από τους απόφοιτούς τους. Αλλά, τι να περιμένει κανείς από ένα εκπαιδευτικό σύστημα το οποίο δεν δίνει την δυνατότητα εισαγωγής στα Τμήματα Μαθηματικών και Μηχανικών Υπολογιστών στους μόνους υποψήφιους που εξετάζονται τόσο στην Πληροφορική όσο και στα Μαθηματικά στις Πανελλαδικές, δηλαδή τους υποψήφιους του Επιστημονικού Πεδίου Οικονομίας και Πληροφορικής, τους καλύτερα προετοιμασμένους υποψήφιους για ένα Τμήμα Μαθηματικών και για ένα Τμήμα Μηχανικών Υπολογιστών.

Γιώργος Μπουγιούκας, πληροφορικός-βιοπληροφορικός (MSc)

Συντελεστές βαρύτητας ΓΕΛ: άνοδος για Πληροφορική και Γλώσσα, πτώση για Μαθηματικά, Αρχαία και Βιολογία

Με βάση τα στοιχεία που δημοσεύτηκαν στην σελίδα του Υπουργείου Παιδείας ( https://www.minedu.gov.gr/news/50746-18-11-21-oi-syntelestes-varytitas-panelladika-eksetazomenon-mathimaton )

Για τις προηγούμενες Πανελλαδικές, του 2021, ίσχυσαν «οριζόντιοι» συντελεστές βαρύτητας στα 4 επιστημονικά πεδία με δύο μαθήματα σε κάθε πεδίο να έχουν συντελεστές 33% και 27% αντίστοιχα, και τα υπόλοιπα δύο από 20% το καθένα (σύνολο 100%). Αυτή είναι η % αναγωγή των συντελεστών του 2021 για να μπορέσει να γίνει η σύγκριση, μιας και συνήθως οι δύο υψηλότεροι συντελεστές (33% και 27%) αναφέρονταν ως «1.3 και 0.7» αντίστοιχα, ενώ οι χαμηλότεροι (20%) αναφέρονταν ως «χωρίς συντελεστή», αναφορικά με κάποιον τύπο υπολογισμού μορίων. Ποτέ μου δεν κατάλαβα γιατί δεν αναφέρονταν με την % αναγωγή (33%, 27%, 20%, 20%) η οποία δίνει μια σαφή εικόνα για την βαρύτητα των βαθμολογιών. Με την % αναγωγή είναι ξεκάθαρο, για παράδειγμα, ότι το μάθημα της Πληροφορικής είχε οριζόντιο συντελεστή 20% για όλες τις σχολές, ενώ η περιγραφή «χωρίς συντελεστή» δεν λέει και πολλά πράγματα.

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

Η μεγαλύτερη πτώση παρατηρείται στο πεδίο των Ανθρωπιστικών, Νομικών και Κοινωνικών Επιστημών στα Αρχαία, ο συντελεστής των οποίων μειώνεται κατά 9.63 ποσοστιαίες μονάδες κατά μέσο όρο και ακολουθεί το 4ο πεδίο των Επιστημών Οικονομίας και Πληροφορικής με τα Μαθηματικά, ο συντελεστής των οποίων μειώνεται κατά 7.07 ποσοστιαίες μονάδες. Στο 3ο πεδίο των Επιστημών Υγείας και Ζωής η Βιολογία παρουσιάζει πτώση κατά 6.28 ποσοστιαίες μονάδες.

Η μεγαλύτερη άνοδος αφορά επίσης το 1ο επιστημονικό πεδίο, με την Νεοελληνική Γλώσσα και Λογοτεχνία να αυξάνεται κατά 8.51 ποσοστιαίες μονάδες. Ακολουθεί, το 4ο πεδίο με την Πληροφορική να αυξάνεται κατά 4.79 ποσοστιαίες μονάδες.

Αξίζει να σημειωθεί, ακόμη, ότι η Νεοελληνική Γλώσσα και Λογοτεχνία αυξάνεται και στα τέσσερα πεδία, ενώ τα Μαθηματικά ελαττώνονται και στα δύο πεδία που συμμετέχουν, στο 2ο και στο 4ο.

Τελος, παρατηρείται μικρή πτώση για την Οικονομία στο 4ο πεδίο κατά 2.33 ποσοστιαίες μονάδες, ενώ η αύξηση της Χημείας στο 2ο πεδίο αντισταθμίζεται εν μέρει από την πτώση της στο 3ο πεδίο.

Συντελεστές βαρύτητας μαθημάτων για τα 4 νέα τμήματα της Σχολής Ικάρων

(Με βάση το σχετικό ΦΕΚ)

Πανελλαδικές: αλλάζουν οι συντελεστές βαρύτητας από το 2022

Σύμφωνα με το νομοσχέδιο του Υπουργείου Παιδείας 4777/2021 (ΦΕΚ 25/Α/17-2-2021) από τις πανελλαδικές εξετάσεις του 2022 παύουν οι ενιαίοι συντελεστές βαρύτητας ανά επιστημονικό πεδίο και κάθε τμήμα της τριτοβάθμιας εκπαίδευσης επιλέγει το ίδιο τους επιθυμητούς ανά επιστημονικό πεδίο συντελεστές βαρύτητας για κάθε μάθημα. Αξίζει να σημειωθεί ότι σύμφωνα με το παραπάνω νομοσχέδιο οι συντελεστές βαρύτητας αναφέρονται με την οικεία % ποσόστωση (όπου το άθροισμα ισούται με 100) και όχι με τον τρόπο που εμφανίζονταν μέχρι τώρα. Απορίας άξιον είναι γιατί οι τρέχουσες ενιαίες ανά πεδίο ποσοστώσεις οι οποίες είναι 33%, 27%, 20% και 20% αναφέρονται ως εξής: συντελεστής “1.3” (αντιστοιχεί στο 33%), συντελεστής “0.7” (αντιστοιχεί στο 27%) και “χωρίς συντελεστή” (αντιστοιχεί στο 20%).

Η αρχή έγινε ήδη με τους συντελεστές βαρύτητας για τις Στρατιωτικές και Αστυνομικές Σχολές, τις Σχολές Πυροσβεστικής και Λιμενικού και την ΑΣΤΕ οι οποίοι ανακοινώθηκαν πρόσφατα. Ας δούμε ένα χαρακτηριστικό παράδειγμα από τις Στρατιωτικές Σχολές, την Σχολή Ικάρων (ΣΙ) Έρευνας Πληροφορικής η οποία είναι προσβάσιμη τόσο από το 2ο, όσο και από το 4ο επιστημονικό πεδίο, με τους εξής συντελεστές ανά πεδίο:

(ΕΦΗΜΕΡΙΔΑ ΤΗΣ ΚΥΒΕΡΝΗΣΕΩΣ (esos.gr))

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

Τεχνητή Νοημοσύνη και Επιστημονική Μέθοδος

Υπολογίζοντας το εμβαδό κάτω από την καμπύλη με την Πληροφορική των Πανελλαδικών

Στο μάθημα των Μαθηματικών Προσανατολισμού… Γ’ Λυκείου ο υπολογισμός του εμβαδού ανάμεσα σε μια καμπύλη και τον άξονα των x από μία τιμή α μέχρι μία τιμή β γίνεται κλασικά μέσω του υπολογισμού της έκφρασης του αόριστου ολοκληρώματος: αν αυτή η έκφραση είναι G(x), τότε το ζητούμενο εμβαδό είναι G(β)-G(α). Όμως, ο υπολογισμός της έκφρασης του αόριστου ολοκληρώματος δεν είναι πάντα εύκολη υπόθεση! Δοκιμάστε για παράδειγμα την ολοκλήρωση της παρακάτω συνάρτησης:

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

Το παραπάνω πρόγραμμα βασίζεται άμεσα στον ορισμό του ορισμένου ολοκληρώματος, ως το όριο του αθροίσματος των εμβαδών των ορθογωνίων στα οποία μπορεί να χωριστεί η επιφάνεια κάτω από την καμπύλη, καθώς το πλήθος αυτών των ορθογωνίων τείνει στο άπειρο (ισοδύναμα καθώς η ποσότητα δχ τείνει στο 0) – βλ. ενότητα 3.4, “Ορισμένο ολοκλήρωμα”, Μαθηματικά Γ’ Τάξης ΓΕΛ Ομάδας Προσανατολισμού... Από αυτόν τον ορισμό συνεπάγεται ότι μπορούμε να πετύχουμε όσο καλή προσέγγιση του εμβαδού θέλουμε επιλέγοντας μια ανάλογα μεγάλη τιμή του πλήθους των ορθογωνίων.

Το τελευταίο πλήθος εκφράζεται από την μεταβλητή ν στο παραπάνω πρόγραμμα, ενώ το εμβαδό του ι-οστού ορθογωνίου από την έκφραση f(α+ι*δχ)*δχ, όπου δχ είναι η μία διάσταση του ορθογωνίου και f(α+ι*δχ) η άλλη, όπου f είναι μία συνάρτηση με δεδομένο αναλυτικό τύπο, της οποίας κάποιο ορισμένο ολοκλήρωμα ζητείται– τέτοιες συναρτήσεις μπορούν εύκολα να κωδικοποιηθούν στην ΓλώσσαΗ μεταβλητή Σ κρατάει το άθροισμα των εμβαδών των ορθογωνίων.

Η μεταβλητή δχ είναι αντιστρόφως ανάλογη της μεταβλητής ν: όσο μεγαλύτερη η μία, τόσο μικρότερη η άλλη. Για την παραπάνω εμφανιζόμενη τιμή δχ=0.001 το πρόγραμμα δίνει ικανοποιητική επίλυση σε διάφορες περιπτώσεις, αλλά ανάλογα με το εύρος του διαστήματος [α, β] και την απαιτούμενη τιμή δχ, ο αριθμός ν μπορεί να υπερβαίνει το φράγμα 105. Η συγκεκριμένη τιμή επιλέχτηκε λόγω του ότι η υπολογιστική της αντιμετώπιση είναι εφικτή στους περισσότερους Η/Υ που κυκλοφορούν εκεί έξω. Φυσικά, μπορείτε να θέσετε μεγαλύτερη τιμή, ανάλογα και με τις δυνατότητες του υπολογιστή σας.

Ας δούμε το πρόγραμμά μας στην πράξη. Θα υπολογίσουμε το παρακάτω ολοκλήρωμα (το οποίο δεν μπορεί να υπολογιστεί με την μεθοδολογία που περιγράφεται στα Μαθηματικά Προσανατολισμού… της Γ’ ΓΕΛ ):

Κωδικοποιούμε την συνάρτηση f (και φυσικά θέτουμε α=0 και β=10):

Η εκτέλεση του προγράμματος στον Διερμηνευτή της Γλώσσας δίνει 0.88672693.  Δοκιμάζουμε μια μικρότερη τιμή για το δχ, 0.0001 και παίρνουμε 0.88627693. Παρατηρείστε ότι ο αριθμός αριστερά από την υποδιαστολή και τα τρία πρώτα δεκαδικά ψηφία δεν άλλαξαν, γεγονός που συνιστά μια ένδειξη (όχι όμως  και απόδειξη) ότι ο αριθμός αριστερά από την υποδιαστολή και τα τρία πρώτα δεκαδικά του αποτελέσματος είναι αυτά ακριβώς! Ας τσεκάρουμε το αποτέλεσμά μας με ένα καταξιωμένο λογισμικό όπως το Wolfram|Alpha, το οποίο δίνει 0.886227

(https://www.wolframalpha.com/input/?i=integrate+e%5E%28-x%5E2%29+from+0+to+10)

Ας δούμε ένα άλλο ολοκλήρωμα, το οποίο επίσης δεν φαίνεται και πολύ εύκολο:

Κωδικοποιούμε την συνάρτηση στην Γλώσσα:

Η εκτέλεση του προγράμματος για δχ=0.001 δίνει 3052491665.01952. Δοκιμάζουμε για μικρότερο δχ, 0.0001, και παίρνουμε 3056988940.38689. Παρατηρούμε ότι τα τρία πρώτα ψηφία αριστερά από την υποδιαστολή δεν άλλαξαν. Το Wolfram|Alpha δίνει 3057488912.86528.

(https://www.wolframalpha.com/input/?i=integrate+%CF%87%5E%CF%87+from+0+to+10)

Η ποσοστιαία απόκλιση της δεύτερης τιμής που έδωσε το πρόγραμμά μας από την τιμή του Wolfram|Alpha είναι 0.016%.

Μια άλλη (κάπως πιο εύκολη για τα Μαθηματικά) περίπτωση:

Η επίλυση του αόριστου ολοκληρώματος που δίνει το Wolfram|Alpha μοιάζει κάπως έτσι:

https://www.wolframalpha.com/input/?i=integrate+1%2F%28%28x-3%29%5E4%2B1%2F2%29

Διαμορφώνουμε την f στο πρόγραμμά μας:

Οπότε, με την εκτέλεση για δχ=0.001 παίρνουμε 3.72272538. Δοκιμάζουμε για δχ=0.0001 και παίρνουμε 3.72272005. Παρατηρούμε ότι η τιμή αριστερά από την υποδιαστολή και τα πέντε πρώτα δεκαδικά ψηφία δεν άλλαξαν. To Wolfram|Alpha δίνει 3.72272

(https://www.wolframalpha.com/input/?i=integrate+1%2F%28%28x-3%29%5E4%2B1%2F2%29+from+0+to+10 )

Ας δούμε, τέλος, και μια εύκολη (για τα Μαθηματικά) περίπτωση:

Κωδικοποιούμε την συνάρτηση:

Για δχ=0.001 παίρνουμε 333.283335. Για δχ=0.0001 παίρνουμε 333.32833335.  Από την γνωστή παράγουσα της συνάρτησης παίρνουμε 10^3/3 =333.3333…

Αξίζει να σημειώσουμε ότι ο κλάδος της Πληροφορικής που μελετάει τα προβλήματα της Ανάλυσης από καθαρά υπολογιστική σκοπιά – η οποία έχει και ιδιαίτερη σημασία για την επιστημονική μοντελοποίηση και έρευνα – ονομάζεται Αριθμητική Ανάλυση.

*Οι εικόνες του κώδικα του προγράμματος είναι screenshots από τον Διερμηνευτή της Γλώσσας

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

Κωδικοποίηση γράφων στην Γλώσσα της Πληροφορικής των Πανελλαδικών

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

Ας δούμε ένα παράδειγμα μη-κατευθυνόμενου γράφου, αρχικά. Η φιλία στο μέσο κοινωνικής δικτύωσης facebook μπορεί να αναπαρασταθεί με έναν μη-κατευθυνόμενο γράφο – αφού η φιλία στο fb είναι αμφίδρομη. Ας θωρήσουμε πέντε χρήστες του fb, την Μαρία, τον Θανάση, την Σοφία, την Τζένη και τον Αποστόλη. Οι χρήστες αυτοί θα είναι οι κορυφές του γράφου. Η ύπαρξη ακμής μεταξύ δύο κορυφών σηματοδοτεί την ύπαρξη φιλίας μεταξύ των αντίστοιχων χρηστών. Ο γράφος μας έχει την μορφή:

Προκειμένου να κωδικοποιήσουμε τον παραπάνω γράφο στην Γλώσσα με πίνακα γειτνίασης χρειαζόμαστε έναν δισδιάστατο τετραγωνικό πίνακα 5x5 ακέραιου τύπου. Οι διαστάσεις του πίνακα είναι και οι δύο ίσες με 5, όσο και το πλήθος των κορυφών του γράφου. Μετά κάνουμε μια αντιστοιχία ονομάτων και αριθμών από το 1 ως το 5, για παράδειγμα, Μαρία (1), Σοφία (2), Θανάσης (3), Αποστόλης (4), Τζένη (5).

Όπως, ίσως, ήδη παρατηρήσατε, μια τιμή 1 σε κάποια θέση του πίνακα σημαίνει ότι τα ονόματα που αντιστοιχούν στην αντίστοιχη γραμμή και στήλη του πίνακα είναι φίλοι, ενώ μια τιμή 0 σημαίνει ότι δεν είναι φίλοι. Αυτός είναι ένας συνήθης τρόπος κωδικοποίησης, χωρίς όμως να αποκλείεται οποιοσδήποτε άλλος συμβολισμός. Για παράδειγμα, η ύπαρξη φιλίας θα μπορούσε να συμβολιστεί με το 15 και η μη-ύπαρξη φιλίας με το 25 (ok, αυτό δεν συνηθίζεται!). Ή ακόμα, ο τύπος του πίνακα θα μπορούσε να ήταν λογικός με την τιμή Αληθής να σηματοδοτεί την ύπαρξη φιλίας και την τιμή Ψευδής την μη-ύπαρξη. Ή ο τύπος του πίνακα θα μπορούσε να ήταν και χαρακτήρας, π.χ. με την τιμή ‘φίλοι’ να σηματοδοτείται η φιλία και με την τιμή ‘όχι φίλοι’ η μη-ύπαρξη φιλίας. Θα μπορούσε, ακόμα, να χρησιμοποιηθεί ο “μισός” πίνακας, είτε από την κύρια διαγώνιο και πάνω, είτε από την κύρια διαγώνιο και κάτω, μιας και όταν ο γράφος είναι μη-κατευθυνόμενος οι τιμές στις θέσεις [ι, κ] και [κ,ι] είναι ίσες (για κάθε ι, για κάθε κ). Ένας τέτοιος πίνακας, μάλιστα, λέγεται συμμετρικός.

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

Θα εξετάσουμε το παράδειγμα του κεντρικού δόγματος της μοριακής βιολογίας. Πρόκειται για το θεμελιώδες μοντέλο της λειτουργίας του κυττάρου στην σύγχρονη βιολογία, το οποίο αναπαριστά την ροή της πληροφορίας μέσα στο κύτταρο. Το σύνηθες μονοπάτι του μοντέλου, το οποίο είναι και το πιο γνωστό, περιλαμβάνει την «μεταγραφή» του DNA σε (m)RNA, το οποίο τελικά αποτελεί το «πρόγραμμα» (αν θέλετε βγάλτε τα εισαγωγικά) με βάση το οποίο λαμβάνει χώρα η παραγωγή πρωτεϊνών μέσα στο κύτταρο! Αξίζει να σημειωθεί ότι το βασικό μοντέλο του DNA (primary structure) είναι ένα δεδομένο τύπου χαρακτήρων συμβολοσειρά (string) όπως είναι ευρύτερα γνωστός αυτός ο τύπος στην επιστήμη της πληροφορικής), το οποίο κτίζεται με ένα αλφάβητο από τέσσερα σύμβολα, A (για την νουκλεοβάση Adenine), G (για την νουκλεοβάση Guanine), C (για την νουκλεοβάση Cytosine) και T (για την νουκλεοβάση Thymine). Όχι τυχαία, η σύζευξη των επιστημών της βιολογίας και της πληροφορικής έχει δώσει ώθηση στην ανάπτυξη του κλάδου της βιοπληροφορικής!

Θεωρούμε την αντιστοιχία DNA (1), RNA (2) και ΠΡΩΤΕΪΝΗ (3) και έναν πίνακα 3×3:

Κάποιες παρατηρήσεις:

Ο κόμβος ΠΡΩΤΕΪΝΗ δεν αποτελεί αφετηρία για καμία ακμή, γεγονός που σηματοδοτείται από την ύπαρξη μόνο της τιμής 0 στην αντίστοιχη γραμμή.

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

Υπάρχουν τιμές ίσες με 1 στην κύρια διαγώνιο, γεγονός που σηματοδοτεί ότι κάποιοι κόμβοι συνδέονται με τον εαυτό τους.

Ας δούμε και μια περίπτωση γράφου με “βάρηστις ακμές. Πολλές φορές οι ακμές ενός γράφου συσχετίζονται με κάποιες τιμές δεδομένων. Για παράδειγμα, στις επαναληπτικές πανελλαδικές εξετάσεις του 2018, στο θέμα Δ, ο πίνακας ΑΠ[15,15] κωδικοποιεί έναν γράφο με κορυφές 15 νησιά και βάρη τις αποστάσεις μεταξύ τους. Για χάρη απλοποίησης, στο παρακάτω σχήμα απεικονίζεται ένας γράφος με 5 νησιά (Ν1, Ν2, Ν3, Ν4, Ν5). Παρατηρείστε τις τιμές (βάρη) στις ακμές (με κόκκινο χρώμα), οι οποίες στην δεδομένη περίπτωση είναι οι αποστάσεις μεταξύ δύο νησιών.

Σ’ αυτήν την περίπτωση στον τετραγωνικό πίνακα ΑΠ[15,15] οι τιμές εκφράζουν τα βάρη. Για το συγκεκριμένο θέμα των Πανελλαδικών δεν υπήρχαν δύο νησιά που δεν σχετίζονταν με ακμή. Αν υπήρχαν, θα μπορούσε να καταχωρηθεί μια αρνητική τιμή (π.χ. -1) για αυτές τις περιπτώσεις στο πίνακα. Αξίζει να σημειωθεί, ακόμη, ότι στο συγκεκριμένο θέμα ζητήθηκε να χρησιμοποιηθεί το τμήμα του πίνακα πάνω από την κύρια διαγώνιο (αφού ο γράφος που κωδικοποιείται στην ουσία είναι μη-κατευθυνόμενος). Ο πίνακας γειτνίασης για το  παραπάνω παράδειγμα με τα 5 νησιά, με βάση την κωδικοποίηση του θέματος των επαναληπτικών Πανελλαδικών του 2018 (με χρήση μόνο των στοιχείων του πίνακα που βρίσκονται πάνω από την κύρια διαγώνιο) είναι:

*Η οπτική απεικόνιση των γράφων έγινε με την βοήθεια του πακέτου Graphviz και της Python.

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