Eνημέρωση από Σχολικό Σύμβουλο Πληροφορικής για Α.Ε.Π.Π. 2016

Σύμφωνα με τις οδηγίες του Υπ.Π.Ε.Θ. για τη διδασκαλία του μαθήματος «Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον» της Γ΄ τάξης Ημερήσιου Γενικού Λυκείου για το σχολ. έτος 2015 – 2016 (υπ’ αρ. 199465 /Δ2/08-12-2015) «Στο κεφάλαιο 5 να διδαχθούν οι ενότητες 5.1 (επίδοση αλγορίθμων) και 5.3 (πολυπλοκότητα αλγορίθμων). Η έννοια της επίδοσης να εξεταστεί με αναφορά στους αλγορίθμους αναζήτησης και ταξινόμησης. Η πολυπλοκότητα αλγορίθμων να διδαχθεί θεωρητικά με παραδείγματα και σε σύνδεση με την επίδοση, χωρίς οι μαθητές να εμπλακούν σε ασκήσεις υπολογισμού της τάξης Ο ενός αλγορίθμου.»

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

ανάθεση τιμής

σύγκριση 2 μεταβλητών

αριθμητική πράξη μεταξύ 2 μεταβλητών»

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

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

Πρόσβαση στην τιμή ενός συγκεκριμένου κελιού ενός πίνακα

Αύξηση (ή μείωση) της τιμής μιας μεταβλητής

Η τελευταία αναφερόμενη πράξη συνάγεται από το παράδειγμα στην παράγραφο 5.1.3, όπου η θεωρητική έκφραση i <-i +1 υπολογίζεται ως μια πράξη. Συνεπώς, η αύξηση (ή μείωση) της τιμής οποιασδήποτε μεταβλητής (π.χ x <- x+1) υπολογίζεται ως μια πράξη, ενώ αν εμπλέκονται και άλλες μεταβλητές (x <- y+1), υπολογίζεται ως δύο.

Ως αιτιολόγηση των ανωτέρω μπορούν να χρησιμοποιηθούν τα παρακάτω: Στην αρχή του βιβλίου (παράγραφος 1.6) αναφέρεται σε επίπεδο αρχιτεκτονικής «Όσο και αν τυχόν ξαφνιάζει, ο υπολογιστής δεν μπορεί να εκτελεί παρά μόνο τρεις λειτουργίες: πρόσθεση, ….. σύγκριση,…. μεταφορά δεδομένων, …..».

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

Οι υπολογισμοί του πίνακα 5.2 για τον αλγόριθμο της παραγράφου 5.1.3 ισχύουν αν υποτεθεί ότι η εντολή «Για» εκτελείται Ν-φορές και κάθε βασική πράξη θέλει 1 μs.

Για τις εντολές που εκτελούνται μόνο μια φορά (εκτός επανάληψης)

  1. x <-123,
  2. y <- 234,
  3. εκτύπωσε x,
  4. εκτύπωσε y,
  5. εκτύπωσε z .

Είναι συνολικά 5 πράξεις (5 μs)

Οι εντολές μέσα στο βρόχο «Για…» εκτελούνται:

Αρχική τιμή i : 1 πράξη

Έλεγχος i : Ν+1 πράξεις

Αύξηση : Ν πράξεις

Εκτύπωση : Ν πράξεις

Υπολογισμός (z <- x*y) : 2N πράξεις

Άρα, συνολικές πράξεις : 5+1+Ν+1+Ν+Ν+2Ν= 5Ν+7

Ο ανωτέρω τύπος για Ν=5 δίνει 32μs, για Ν=10 δίνει 57μs και Ν=1.000.000 βγάζει (περίπου 5.000.000 πράξεις δηλαδή 5.000.000 μs = 5 sec (1 sec = 1.000.000 μs).

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

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

Γενικότερα, «η πολυπλοκότητα ενός αλγορίθμου δίνει ένα μέτρο της χρονικής καθυστέρησης του αλγορίθμου για την επίλυση ενός προβλήματος» ή ισοδύναμα » ένα μέτρο της ταχύτητας εκτέλεσης του αλγορίθμου».

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

Αριθμός συγκρίσεων στη δυαδική αναζήτηση

Στοιχεία Ν Συγκρίσεις
10 4
100 7
1.000 10
10.000 14
100.000 17
1.000.000 20
10.000.000 24
100.000.000 27
1.000.000.000 30

Για τον συμβολισμό Ο της πολυπλοκότητας δεν πρέπει να αναλυθεί τι ακριβώς εκφράζει και πως υπολογίζεται σ’ έναν αλγόριθμο. Προτείνεται ο εκπαιδευτικός να δείξει τον πίνακα 2.2 και την εικόνα 2.10 από τη σελίδα 24 του βιβλίου της Β’ ΓΕΛ, καθώς και τον πίνακα 5.4 του βιβλίου της Γ΄ τάξης και να συζητήσει με τους μαθητές, για την αύξηση του χρόνου ολοκλήρωσης που απαιτεί ένας αλγόριθμος, καθώς αυξάνεται η πολυπλοκότητά του.

Τέλος, μπορεί να αναφερθεί ότι πρακτικά τα απλά προγράμματα μπορούν να αναλυθούν μετρώντας τους εμφωλευμένους βρόχους, που υπάρχουν στο πρόγραμμα. Ένας απλός βρόχος, που διασχίζει Ν στοιχεία, δίνει πολυπλοκότητα n, ένας βρόχος μέσα σ᾽ έναν βρόχο δίνει n^2, ένας βρόχος μέσα σ᾽ έναν βρόχο άλλου βρόχου δίνει n^3 κ.ο.κ.

Ο Σχολικός Σύμβουλος Πληροφορικής Ιονίων Νήσων

Γεράσιμος Πολυμέρης

Print Friendly, PDF & Email
Share
Share