Σκεπτικό του σεναρίου / Αιτιολόγηση των επιλογών

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

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

Λόγω της δυναμικής του φύσης, οι αλγόριθμοι ταξινόμησης πινάκων είναι δύσκολο να μελετηθούν και να παρουσιαστούν με παραδοσιακά μέσα (πίνακας, βιβλίο). Φαίνεται ότι η αξιοποίηση ψηφιακών πόρων οπτικοποίησης/προσομοίωσης, σε συνδυασμό με την υλοποίηση διερευνητικών και συνεργατικών μαθησιακών δραστηριοτήτων, συμβάλουν στην οικοδόμηση ολοκληρωμένων αναπαραστάσεων και νοητικών μοντέλων για βασικούς αλγορίθμους πινάκων.

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

Παιδαγωγική προσέγγιση και στρατηγικές

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

Στοχευόμενο κοινό (ομάδα-στόχος ή σε ποιους απευθύνεται) Βαθμίδα Εκπαίδευσης

γενικό λύκειο

Τάξη

Γ' Λυκείου

Ηλικιακή ομάδα

Από 17   Έως 18

Γλώσσα στοχευόμενου κοινού

ελληνικά

Εκτιμώμενος χρόνος υλοποίησης σεναρίου (διάρκεια)

μικρή διάρκεια: έως 3 ώρες

2 διδακτικές ώρες

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

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

α) Εκπαιδευτικά βίντεο στο YouTube για τους αλγόριθμους ταξινόμησης

Ταξινόμηση ευθείας ανταλλαγής: https://youtu.be/NiyEqLZmngY?t=13

Ταξινόμηση με επιλογή: https://youtu.be/EdUWyka7kpI

β) Μαθησιακά Αντικείμενα του Φωτόδεντρου που αφορούν αλγορίθμους ταξινόμησης σε πίνακες

Ταξινόμηση ευθείας ανταλλαγής: http://photodentro.edu.gr/lor/r/8521/10460

Ταξινόμηση εισαγωγής δεδομένων: http://photodentro.edu.gr/lor/r/8521/10526

Ταξινόμηση με επιλογή: http://photodentro.edu.gr/lor/r/8521/10557

γ) Περιβάλλον προγραμματισμού (π.χ. Ψευδογλώσσα, Python, JavaScript).

Ενορχήστρωση τάξης Οργάνωση τάξης / διδασκαλίας

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

Παρακολουθούν, αναλύουν και σχολιάζουν σχετικά βίντεο YouTube για τους αλγόριθμους ταξινόμησης. Διακρίνουν και συζητούν για τα σημαντικά τμήματα κάθε αλγορίθμου. Ακολούθως, χειρίζονται και διερευνούν ΜΑ του Φωτόδεντρου που θα τους δοθούν. Αναλύουν τη δομή του αλγορίθμου και τη μετατρέπουν σε αλγοριθμικές εντολές Ψευδογλώσσας. Τέλος, υλοποιούν τον αλγόριθμο ταξινόμησης ευθείας ανταλλαγής σε περιβάλλον γλώσσας προγραμματισμού.

Ρόλοι μαθητών & εκπαιδευτικών

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

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

Απαιτήσεις εφαρμογής σεναρίου Προαπαιτούμενες γνώσεις των μαθητών

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

Απαιτούμενη προετοιμασία

Σε τεχνικό-οργανωτικό επίπεδο: Πόροι και εργαλεία που θα χρησιμοποιηθούν για την απρόσκοπτη υλοποίηση του εκπαιδευτικού σεναρίου.

Σε παιδαγωγικό επίπεδο:

• Χρονοπρογραμματισμός και οργάνωση του τρόπου εργασίας των μαθητών.
• Ετοιμότητα του εκπαιδευτικού για τις αναμενόμενες δυσκολίες των μαθητών και τους αποτελεσματικούς τρόπους αντιμετώπισης
• Σχεδιασμός της μαθησιακής καθοδήγησης και υποστήριξης των μαθητών (scaffolding).

Προσδοκώμενα μαθησιακά αποτελέσματα

Μετά την ολοκλήρωση του εκπαιδευτικού σεναρίου οι μαθητές να είναι ικανοί

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

Παιδαγωγική προσέγγιση και στρατηγικές

Το εκπαιδευτικό σενάριο υιοθετεί την προσέγγιση της συνεργατικής μάθησης και βασίζεται:

α) στη διερεύνηση των λογικών δομών του αλγορίθμου ταξινόμησης

β) στη συζήτηση και διαμοίραση ιδεών στην ομάδα

γ) στον πειραματισμό με την προσομοίωση του αλγορίθμου ταξινόμησης μέσω ΜΑ του Φωτόδεντρου

δ) στην μετατροπή του αλγορίθμου σε κώδικα από τους μαθητές.

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

Ροή εφαρμογής – Πορεία διδασκαλίας

Εισαγωγή-προσανατολισμός

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

Στη συνέχεια, παρουσιάζει στη τάξη ή ζητά από τους μαθητές να παρακολουθήσουν τα παρακάτω βίντεο:

Αλγόριθμος ταξινόμησης με επιλογή: https://youtu.be/EdUWyka7kpI

Ταξινόμηση με εισαγωγή: https://youtu.be/OGzPmgsI-pQ

Αλγόριθμος ταξινόμησης ευθείας ανταλλαγής (φυσαλίδας): https://youtu.be/NiyEqLZmngY?t=13

 

Καθοδηγούμενη διερεύνηση

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

 

Ταξινόμηση ευθείας ανταλλαγής

Οι μαθητές επιλέγουν τον σχετικό σύνδεσμο (http://photodentro.edu.gr/lor/r/8521/10460) και χειρίζονται το Μαθησιακό Αντικείμενο που θα χρησιμοποιήσουν στη συνέχεια του εκπαιδευτικού σεναρίου. Η επιλογή του βασίζεται στο ότι η προσομοίωση της εκτέλεσης του αλγορίθμου αναδεικνύει με δυναμικό τρόπο τα στοιχεία του πίνακα, τους δείκτες θέσης ανά εντολή, την προσπέλαση και σύγκριση των διαδοχικών στοιχείων, καθώς και την αντιμετάθεση τιμών όταν η συνθήκη είναι αληθής.

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

 

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

Όπως φαίνεται στις παρακάτω οθόνες, κατά τη σύγκριση δύο στοιχείων του πίνακα (π.χ. του 9ου και 8ου στοιχείου) ξεχωρίζουν με διαφορετικό χρώμα, τόσο τα στοιχεία που συγκρίνονται,  όσο και οι εντολές ελέγχου και αντιμετάθεσης. Στη συνέχεια δείχνεται δυναμικά η αντιμετάθεση των στοιχείων με τιμές 3 και 55.  

 

Η διαδικασία συνεχίζεται μέχρι το στοιχείο με τιμή 3 να τοποθετηθεί στην πρώτη θέση του πίνακα.

 

 

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

 

 

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

 

Αναστοχασμός και συζήτηση στην τάξη

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

 

Εφαρμογή, υλοποίηση

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

 

Επέκταση σεναρίου

Ο εκπαιδευτικός αναθέτει στους μαθητές τη διερεύνηση του ΜΑ  προσομοίωσης του αλγορίθμου ταξινόμησης με εισαγωγή (http://photodentro.edu.gr/lor/r/8521/10526). Οι μαθητές έχουν τη δυνατότητα να αναπτύξουν περαιτέρω τις προγραμματιστικές τους ικανότητες σχεδιάζοντας και υλοποιώντας τον αλγόριθμο ταξινόμησης με εισαγωγή σε πραγματικό προγραμματιστικό περιβάλλον.

Φάσεις, Βήματα ή Δραστηριότητες

Περιγράφεται/αναλύεται η ροή υλοποίησης των διδακτικών ενεργειών και των μαθητικών δραστηριοτήτων των μαθητών

Διαμορφωτική αξιολόγηση στην τάξη

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

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

 

Επέκταση σεναρίου

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

Ταξινόμηση με επιλογή: http://photodentro.edu.gr/lor/r/8521/10557

Merge Sort: https://youtu.be/HsZ-YRQM8sE

Gnome Sort: https://youtu.be/43noNfrbEnQ

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

Insertion Sort vs Bubble Sort + Some analysis: https://youtu.be/TZRWRjq2CAg

Merge Sort vs Quick Sort: https://youtu.be/es2T6KY45cA

Βιβλιογραφία

Dale, N. B. (2006). Most difficult topics in CS1: results of an online survey of educators. SIGCSE Bulletin. 38(2), 49-53.

Qian, Y., & Lehman, J. (2017). Students’ misconceptions and other difficulties in introductory programming: a literature review. ACM Transactions on Computing Education, 18(1), Art. 1.

Vrachnos, E., & Jimoyiannis, A. (2017). Secondary education students’ difficulties in algorithmic problems with arrays: An analysis using the SOLO taxonomy. Themes in Science and Technology Education, 10(1), 31-52.

Βραχνός, Ε., & Τζιμογιάννης, Α. (2009). Εκπαιδευτικά περιβάλλοντα οπτικοποίησης αλγορίθμων: Μια επισκόπηση των τεχνικών και παιδαγωγικών χαρακτηριστικών. Θέματα Επιστημών και Τεχνολογίας στην Εκπαίδευση, 2(3), 215-245.

Βραχνός, Ε., & Τζιμογιάννης, Α. (2014). Αναπαραστάσεις μαθητών και φοιτητών για τον αλγόριθμο ταξινόμησης ευθείας ανταλλαγής: Μια ανάλυση βασισμένη στην ταξινομία SOLO. Πρακτικά 7ου Πανελλήνιου Συνεδρίου ‘’Διδακτική της Πληροφορικής’’ (σ. 72-81). Ρέθυμνο: ΕΤΠΕ.

Βραχνός, Ε., & Τζιμογιάννης, Α. (2016). Προϋπάρχουσες γνώσεις των μαθητών στους αλγόριθμους ταξινόμησης. Ποιον αλγόριθμο επινοούν; Πρακτικά 8ου Πανελλήνιου Συνεδρίου ‘’Διδακτική της Πληροφορικής’’ (σ. 61-68). Ιωάννινα: ΕΤΠΕ.

Βραχνός, Ε., & Τζιμογιάννης, Α. (2018). Προϋπάρχουσες γνώσεις των μαθητών Γυμνασίου και Λυκείου στους αλγόριθμους ταξινόμησης. Μια συγκριτική ανάλυση. Πρακτικά 9ου Πανελλήνιου Συνεδρίου “Διδακτική της Πληροφορικής” (σ. 110-117). Θεσσαλονίκη: ΕΤΠΕ.

Κόμης, Β., & Τζιμογιάννης, Α. (2006). Ο Προγραμματισμός ως μαθησιακή δραστηριότητα: από τις εμπειρικές προσεγγίσεις στη γνώση παιδαγωγικού περιεχομένου. Θέματα στην Εκπαίδευση, 7(3), 229-255.

 

Επιπλέον ψηφιακό περιεχόμενο και εργαλεία

Merge Sort: https://youtu.be/HsZ-YRQM8sE

Gnome Sort: https://youtu.be/43noNfrbEnQ

Insertion Sort vs Bubble Sort + Some analysis: https://youtu.be/TZRWRjq2CAg

Merge Sort vs Quick Sort: https://youtu.be/es2T6KY45cA