Μια "αιρετική" αναζήτηση

Ξεκίνησε από gthal, 20 Ιαν 2011, 01:15:30 ΜΜ

« προηγούμενο - επόμενο »

Νίκος Αδαμόπουλος

Παράθεση από: nobody6 στις 14 Φεβ 2014, 11:10:31 ΜΜ
3. Η χρήση λογικής μεταβλητής είναι άστοχη εδώ,(Νομίζω είναι και η πρώτη φορά που χρησιμοποιείται στο βιβλίο)εφ' όσον η αναζήτηση
    σταματάει με την εύρεση. Αν θέλεις να διδάξεις τη χρήση λογικής μεταβλητής θα ήταν εύστοχο να το κάνεις με χρήση Για.

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

Παράθεση από: nobody6 στις 14 Φεβ 2014, 11:10:31 ΜΜ
4. Αποδοτικότερος αλγόριθμος (εκτός ύλης, αλλά νομίζω πρέπει να αναφέρεται).

Δεν είναι πιο αποδοτικός...

Κανένας

Δεν θεωρώ άστοχη τη λογική μεταβλητή αλλά τη χρήση της (εκμάθησή της) στη σειριακή αναζήτηση του βιβλίου.
Τη λογική μεταβλητή τη διδάσκω με το εξής πρόβλημα (χωρίς χρήση πίνακα):
"Γράψτε αλγόριθμο που διαβάζει 100 αριθμούς,  τυπώνει το άθροισμά τους  και μας πληροφορεί  αν διάβασε τον αριθμό 17".

Αν ο αλγόριθμος σταμάταγε με το διάβασμα του 17 η χρήση της λογικής μεταβλητής θα ήταν περιττή (άστοχη χρήση) γιατί την πληροφορία (αν δόθηκε το 17) θα την έπαιρνα απ' την τιμή της μεταβλητής με την οποία διαβάζω τους αριθμούς (α=17).
Στην πρώτη περίπτωση αντίθετα, η 100η (τελευταία) τιμή που δόθηκε στην μεταβλητή α δεν μου εξασφαλίζει  αν δόθηκε το 17,κι έτσι η λογική μεταβλητή μπορεί και γίνεται χρήσιμη.
Ανάλογα τα πράγματα αν τα παραπάνω γίνουν  με χρήση πίνακα.
Τώρα σχετικά με την απόδοση:
Σ' ένα πίνακα με 1 εκατομμύριο στοιχεία και το αναζητούμενο στοιχείο στην τελευταία θέση, ο αλγόριθμος του βιβλίου θα έκανε 1 εκατομμύριο συγκρίσεις
περισσότερες απ' τον προτεινόμενο. (Η πολυπλοκότητα φυσικά είναι ίδια Ο(Ν). και οι δύο έχουν μια απλή επανάληψη).
Νικηφόρος Μανδηλαράς
ΓΕΛ Νάξου "Μανώλης Γλέζος"
https://blogs.sch.gr/nobody/

apoldem

Έχεις δίκιο nobody6 για την απόδοση. Άλλο πολυπλοκότητα άλλο απόδοση. Για ίδια πολυπλοκότητα ένας αλγόριθμος μπορεί να είναι πιο αποδοτικός από κάποιον άλλον. Η πολυπλοκότητα είναι εκτός ύλης αλλά η απόδοση; Αν δεν ενδιαφέρει καθόλου η απόδοση σε εκμάθηση αλγορίθμων τότε καλώς καταργείται το μάθημα. Μην τα θέλουμε όλα δικά μας.
Ο αλγόριθμος αναζήτησης του βιβλίου είναι πράγματι απαράδεκτος. Αυτό που προτείνεις όμως χάνει την τελευταία θέση (αν αυτό που ψάχνουμε είναι στην τελευταία θέση). Γιατί να μην γίνει με Όσο, που είναι και η κλασική σειριακή αναζήτηση:
θ <- 1
Όσο θ<Ν και Α[θ]<>Query επανάλαβε
  θ<-θ+1
Τέλος_επανάληψης
βρέθηκε <- θ<=Ν

nikolasmer

Παράθεση από: apoldem στις 16 Φεβ 2014, 10:08:31 ΠΜ
θ <- 1
Όσο θ<Ν και Α[θ]<>Query επανάλαβε
  θ<-θ+1
Τέλος_επανάληψης
βρέθηκε <- θ<=Ν

Έχω την εντύπωση πως και αυτός ο κώδικας δεν ελέγχει την τελευταία θέση.
Μερεντίτης Νικόλαος
Πληροφορικός

Κανένας

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

Αν Α[θ]=Query τότε
  !χρησιμοποιούμε την τιμή του θ αν είναι τμήμα κώδικα
  position<-θ            ! αν είναι συνάρτηση επιστρέφει position
  done<-ΑΛΗΘΗΣ      ! αν είναι διαδικασία επιστρέφει position και done
αλλιώς
  position<-0            ! αν είναι συνάρτηση επιστρέφει position

  done<-ΨΕΥΔΗΣ      ! αν είναι διαδικασία επιστρέφει position και done
Τέλος_Αν
Νικηφόρος Μανδηλαράς
ΓΕΛ Νάξου "Μανώλης Γλέζος"
https://blogs.sch.gr/nobody/

apoldem

Σωστά nikolasmer! Ξέχασα ένα '='. Η συνθήκη στο Όσο είναι

Όσο θ<=Ν και Α[θ]<>Query επανάλαβε

μ' αρέσει που ξανάγραψα ολόκληρο τον αλγόριθμο για να ξανακάνει το ίδιο λάθος ;D

Κανένας

#21
Τώρα είναι λάθος!
Είναι πιθανό ο συγγραφέας της σειριακής του βιβλίου να κατέφυγε στη χρήση της λογικής μεταβλητής
θέλοντας να διορθώσει αυτό το λάθος.
Βγάζει τη συνθήκη Α[θ]<>Query (που δημιουργεί το λάθος) απ' το Όσο και τη βάζει μέσα στην επανάληψη
με τη μορφή του Αν και στη θέση της βάζει τη λογική μεταβλητή που παίρνει τιμή τερματισμού μέσα στο Αν.
Φυσικά είναι απλούστερο να διορθωθεί αν αντί θ<=Ν μπει θ<Ν.
Την τελευταία θέση την ελέγχει το εξωτερικό Αν το οποίο είναι έτσι κι αλλιώς απαραίτητο.

Επισυνάπτω σχετικό φύλλο εργασίας.
Νικηφόρος Μανδηλαράς
ΓΕΛ Νάξου "Μανώλης Γλέζος"
https://blogs.sch.gr/nobody/

nikolasmer

Παράθεση από: apoldem στις 16 Φεβ 2014, 11:39:51 ΠΜ
Σωστά nikolasmer! Ξέχασα ένα '='. Η συνθήκη στο Όσο είναι

Όσο θ<=Ν και Α[θ]<>Query επανάλαβε

μ' αρέσει που ξανάγραψα ολόκληρο τον αλγόριθμο για να ξανακάνει το ίδιο λάθος ;D
Νομίζω ότι βγαίνει εκτός ορίων του πίνακα οταν και εφόσον γίνεται πλήρης αποσαφήνιση των λογικών τελεστών.
Μερεντίτης Νικόλαος
Πληροφορικός

apoldem

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

Νίκος Αδαμόπουλος

Παράθεση από: apoldem στις 16 Φεβ 2014, 01:13:07 ΜΜ
Εννοείται ότι δεν κάνουμε πλήρη αποτίμηση λογικών εκφράσεων. Δεν νομίζω να υπάρχει καμία δέσμευση από την πλευρά του βιβλίου, εκτός αν υπάρχει οδηγία από το υπουργείο και την αγνοώ.

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

P.Tsiotakis

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

η μερική αποτίμηση δεν είναι σκέψη αλλά προγραμματιστικά τρικ, όπως τα άλματα στον κώδικα, το σπάσιμο της δομής Για και αρκετά άλλα

φιλικά, Π.

apoldem

@Νίκος Αδαμόπουλος
Αυτή η συντηρητική προσέγγιση κατάντησε να διδάσκουμε προγραμματισμό δεκαετίας 90 στα παιδιά. Η σύντομη αποτίμηση δεν είναι συμβατή με καμιά σημερινή γλώσσα (εκτός της Visual Basic, που και αυτή είναι παραγκωνισμένη έως ανύπαρκτη αυτή την στιγμή)

@Παναγιώτης Τσιωτάκης
Η σύντομη αποτίμηση εμποδίζει τα παιδιά να σκέφτονται; Προγραμματιστικό τρικ είναι επίσης όλος ο αντικειμενοστραφής προγραμματισμός. Να ξεχάσουμε όλες τις εξελίξεις στον προγραμματισμό τα 20 τελευταία χρόνια και να γυρίσουμε στην pascal και την basic.

Το βιβλίο μυρίζει μούχλα και ναφθαλίνη (γραμμένο στα τέλη της δεκαετίας του 90). Ας μην το κάνουμε χειρότερο απ' ότι είναι. Ο σημερινός προγραμματισμός δεν έχει καμία σχέση με αυτά που μαθαίνουν τα παιδιά. Η σύντομη αποτίμηση είναι στάνταρντ παντού. Η εντολή Για δεν υπάρχει πουθενά με την μορφή που την διδάσκουμε. Όλες οι γλώσσες υποστηρίζουν με τον έναν ή τον άλλον τρόπο ForEach για μια συλλογή δεδομένων. Κάποιες έχουν τελεστή hasNext για να ελέγχεις αν υπάρχει επόμενο στοιχείο στην συλλογή. Προγραμματισμός με δείκτη i που τρέχει τα στοιχεία ενός πίνακα είναι μακρινό παρελθόν. Ακόμη και οι πίνακες με το περιβόητο i, χρησιμοποιούνται πολύ λίγο πλέον και μόνο για συγκεκριμένες δουλειές. Και ναι, παρόλα αυτά, οι σημερινοί προγραμματιστές συνεχίζουν να σκέφτονται και να εκφράζουν την σκέψη τους μέσα από κώδικα και μάλιστα με πολύ μεγαλύτερη σαφήνεια απ' ότι πριν 20 χρόνια.

itt

Παράθεση από: Κανένας στις 16 Φεβ 2014, 02:13:01 ΠΜ
Τώρα σχετικά με την απόδοση:
Σ' ένα πίνακα με 1 εκατομμύριο στοιχεία και το αναζητούμενο στοιχείο στην τελευταία θέση, ο αλγόριθμος του βιβλίου θα έκανε 1 εκατομμύριο συγκρίσεις
περισσότερες απ' τον προτεινόμενο. (Η πολυπλοκότητα φυσικά είναι ίδια Ο(Ν). και οι δύο έχουν μια απλή επανάληψη).

Aυτό δεν έχει νόημα σαν συζήτηση. Δεν μπορείς να ξέρεις την απόδοση του αλγόριθμου άμα δεν κάνεις profile το runtime του. Αν υπάρχει ας πούμε μερική διάταξη στα δεδομένα του πίνακα ( και σε πραγματικά δεδομένα δεν θα ήταν καθόλου περίεργο) τότε ο branch predictor θα βελτιώσει τον χρόνο εκτέλεσης.

Παράθεση από: apoldem στις 16 Φεβ 2014, 10:08:31 ΠΜ
Έχεις δίκιο nobody6 για την απόδοση. Άλλο πολυπλοκότητα άλλο απόδοση. Για ίδια πολυπλοκότητα ένας αλγόριθμος μπορεί να είναι πιο αποδοτικός από κάποιον άλλον. Η πολυπλοκότητα είναι εκτός ύλης αλλά η απόδοση; Αν δεν ενδιαφέρει καθόλου η απόδοση σε εκμάθηση αλγορίθμων τότε καλώς καταργείται το μάθημα. Μην τα θέλουμε όλα δικά μας.

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

pgrontas

H μερική αποτίμηση (δηλ. (Αληθης ή _ ) = Αληθής, (Ψευδής και _ ) = Ψευδής, (Ψευδής ή _ ) = _, (Αληθής και _) = _) δεν είναι προγραμματιστικό τρικ. Είναι άμεση συνέπεια του ορισμού των λογικών πράξεων και υπάρχει διδακτική αξία στο να το επισημάνεις στους μαθητές.

Αν στα μαθηματικά είχαμε πολλαπλασιασμό μιας παράστασης με το μηδέν θα καθόμασταν ποτέ να υπολογίσουμε την παράσταση;
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

Νίκος Αδαμόπουλος

Παράθεση από: apoldem στις 18 Φεβ 2014, 01:52:03 ΠΜ
@Νίκος Αδαμόπουλος
Αυτή η συντηρητική προσέγγιση κατάντησε να διδάσκουμε προγραμματισμό δεκαετίας 90 στα παιδιά. Η σύντομη αποτίμηση δεν είναι συμβατή με καμιά σημερινή γλώσσα (εκτός της Visual Basic, που και αυτή είναι παραγκωνισμένη έως ανύπαρκτη αυτή την στιγμή)

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

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

Υ.Γ.

Σχετικά με την δημοτικότητα των γλωσσών προγραμματισμού:
http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html

(Δες το υπότιτλο του άρθρου... Πολλές φορές τα πράγματα δεν είναι όπως τα νομίζουμε!)