Αναζήτηση στοιχείων σε μονοδιάστατο πίνακα

Πληροφορική (Γενικό Λύκειο)

Αναζήτηση στοιχείων σε μονοδιάστατο πίνακα

3 ώρες

Γενική περιγραφή περιεχομένου

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

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

Εκπαιδευτικό Πρόβλημα

Το πρόβλημα της αναζήτησης (searching) στοιχείου(ων) σε πίνακα είναι ιδιαίτερα ενδιαφέρον λόγω της χρησιμότητάς του σε πλήθος εφαρμογών. Υπάρχουν αρκετοί αλγόριθμοι αναζήτησης σε πίνακα που εξαρτώνται κυρίως από το αν ο πίνακας είναι ταξινομημένος ή όχι. Μια άλλη παράμετρος είναι αν ο πίνακας περιέχει στοιχεία που είναι όλα διάφορα μεταξύ τους ή όχι. Ο εκπαιδευτικός -στο πλαίσιο του μαθήματος- καλείται να προσεγγίσει τις παραπάνω περιπτώσεις επιχειρώντας ταυτόχρονα να βοηθήσει τους μαθητές ώστε να αποκτήσουν την ικανότητα να επιλέγουν τον καταλληλότερο αλγόριθμο αναζήτησης ανάλογα με το πρόβλημα.

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

at 50/100 Δύσκολο

Εκπαιδευτική Βαθμίδα που απευθύνεται το σενάριο

Γενικό Λύκειο

Θεματική Ταξινομία

Πληροφορική > Προγραμματισμός υπολογιστών > Αλγόριθμος >

Τύπος Διαδραστικότητας

Συνδυασμός παθητικής και ενεργητικής μάθησης

Επίπεδο Διαδραστικότητας

υψηλό

Προτεινόμενη ηλικιακή ομάδα:

-6

6-9

9-12

12-15

15-18

18-25

25+

Φάσεις Ψηφιακού Σεναρίου:

Εισαγωγικές δραστηριότητες

25λεπτά

Χώρος Υλοποίησης

Σχολικό Εργαστήριο Πληροφορικής & Εφαρμογών Η/Υ (ΣΕΠΕΗΥ)

Αλγόριθμος σειριακής αναζήτησης ύπαρξης και θέσης

20λεπτά

Χώρος Υλοποίησης

Σχολικό Εργαστήριο Πληροφορικής & Εφαρμογών Η/Υ (ΣΕΠΕΗΥ)

Αλγόριθμοι σειριακής αναζήτησης (παραλλαγές)

40λεπτά

Χώρος Υλοποίησης

Σχολικό Εργαστήριο Πληροφορικής & Εφαρμογών Η/Υ (ΣΕΠΕΗΥ)

Αλγόριθμος δυαδικής αναζήτησης

40λεπτά

Χώρος Υλοποίησης

Σχολικό Εργαστήριο Πληροφορικής & Εφαρμογών Η/Υ (ΣΕΠΕΗΥ)

Διδακτικοί Στόχοι

Να διακρίνουν τις μεθόδους αναζήτησης.

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

Να αποφασίζουν αν μπορούν να χρησιμοποιήσουν την δυαδική αναζήτηση.

Λέξεις κλειδιά που χαρακτηρίζουν τη θεματική του σεναρίου

Πίνακας, Αναζήτηση, Σειριακή, Δυαδική,

Υλικοτεχνική υποδομή

Σχολικό εργαστήριο πληροφορικής και εφαρμογών ηλεκτρονικών υπολογιστών, Διερμηνευτής της Γλώσσας

Πνευματικά δικαιώματα ή άλλοι αντίστοιχοι περιορισμοί

Δεν υπάρχουν πνευματικά δικαιώματα

Δημιουργός Σεναρίου: ΠΑΝΑΓΙΩΤΑ ΓΙΑΝΝΟΠΟΥΛΟΥ (Εκπαιδευτικός)

ΑΝΑΓΝΩΡΙΣΤΙΚΟ (τι είναι;)

Αesop - 22579

Το σενάριο «Αναζήτηση στοιχείων σε μονοδιάστατο πίνακα» έχει χαρακτηριστεί ως Επαρκές (βαθμολογία 50 μονάδων μέχρι 69.5) ύστερα από αξιολόγηση που πραγματοποιήθηκε από δύο αξιολογητές βάσει κριτηρίων που ορίστηκαν από το ΔΣ του ΙΕΠ.

Ταξινόμηση στοιχείων μονοδιάστατου πίνακα

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

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

Δοθέντων των στοιχείων a1, a2, …, an η ταξινόμηση συνίσταται στη μετάθεση της θέσης των στοιχείων ώστε να τοποθετούνται σε μια σειρά ak1, ak2, …, akn, προκειμένου δοθείσης μιας συνάρτησης διάταξης f, να ισχύει: f(ak1) ≤ f(ak2) ≤ … ≤ f(akn). Ο ορισμός αφορά την ταξινόμηση των στοιχείων σε αύξουσα τάξη. Για φθίνουσα ταξινόμηση των στοιχείων η συνάρτηση διάταξης τροποποιείται ως εξής: f(ak1) ≥ f(ak2) ≥ …≥ f(akn).

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

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

Το ψηφιακό σενάριο θα υλοποιηθεί εξ ολοκλήρου στο σχολικό εργαστήριο πληροφορικής και εφαρμογών ηλεκτρονικών υπολογιστών (ΣΕΠΕΗΥ). Οι μαθητές θα εργαστούν σε ομάδες των δύο ατόμων (ζεύγη), όπου κάθε ζεύγος θα χρησιμοποιεί έναν υπολογιστή, ώστε να ευνοηθεί η αλληλεπίδραση μεταξύ των μαθητών. Το σενάριο λαμβάνει υπόψη του τις πραγματικές συνθήκες διεξαγωγής του μαθήματος ώστε να είναι ρεαλιστικά πραγματοποιήσιμο στον προβλεπόμενο χρόνο.

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

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

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

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