Αποστολέας Θέμα: Μια "αιρετική" αναζήτηση  (Αναγνώστηκε 9353 φορές)

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2784
  • Πύργος Ηλείας
    • ΚΕΠΛΗΝΕΤ Ηλείας
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #15 στις: 16 Φεβ 2014, 12:01:08 πμ »
3. Η χρήση λογικής μεταβλητής είναι άστοχη εδώ,(Νομίζω είναι και η πρώτη φορά που χρησιμοποιείται στο βιβλίο)εφ' όσον η αναζήτηση
    σταματάει με την εύρεση. Αν θέλεις να διδάξεις τη χρήση λογικής μεταβλητής θα ήταν εύστοχο να το κάνεις με χρήση Για.

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

4. Αποδοτικότερος αλγόριθμος (εκτός ύλης, αλλά νομίζω πρέπει να αναφέρεται).

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

Κανένας

  • Βετεράνος
  • ****
  • Μηνύματα: 52
Μια "στρωτή" αναζήτηση
« Απάντηση #16 στις: 16 Φεβ 2014, 02:13:01 πμ »
Δεν θεωρώ άστοχη τη λογική μεταβλητή αλλά τη χρήση της (εκμάθησή της) στη σειριακή αναζήτηση του βιβλίου.
Τη λογική μεταβλητή τη διδάσκω με το εξής πρόβλημα (χωρίς χρήση πίνακα):
"Γράψτε αλγόριθμο που διαβάζει 100 αριθμούς,  τυπώνει το άθροισμά τους  και μας πληροφορεί  αν διάβασε τον αριθμό 17".

Αν ο αλγόριθμος σταμάταγε με το διάβασμα του 17 η χρήση της λογικής μεταβλητής θα ήταν περιττή (άστοχη χρήση) γιατί την πληροφορία (αν δόθηκε το 17) θα την έπαιρνα απ' την τιμή της μεταβλητής με την οποία διαβάζω τους αριθμούς (α=17).
Στην πρώτη περίπτωση αντίθετα, η 100η (τελευταία) τιμή που δόθηκε στην μεταβλητή α δεν μου εξασφαλίζει  αν δόθηκε το 17,κι έτσι η λογική μεταβλητή μπορεί και γίνεται χρήσιμη.
Ανάλογα τα πράγματα αν τα παραπάνω γίνουν  με χρήση πίνακα.
Τώρα σχετικά με την απόδοση:
Σ' ένα πίνακα με 1 εκατομμύριο στοιχεία και το αναζητούμενο στοιχείο στην τελευταία θέση, ο αλγόριθμος του βιβλίου θα έκανε 1 εκατομμύριο συγκρίσεις
περισσότερες απ' τον προτεινόμενο. (Η πολυπλοκότητα φυσικά είναι ίδια Ο(Ν). και οι δύο έχουν μια απλή επανάληψη).
ΝΙΚΗΦΟΡΟΣ ΜΑΝΔΗΛΑΡΑΣ
ΓΕΛ ΝΑΞΟΥ

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #17 στις: 16 Φεβ 2014, 10:08:31 πμ »
Έχεις δίκιο nobody6 για την απόδοση. Άλλο πολυπλοκότητα άλλο απόδοση. Για ίδια πολυπλοκότητα ένας αλγόριθμος μπορεί να είναι πιο αποδοτικός από κάποιον άλλον. Η πολυπλοκότητα είναι εκτός ύλης αλλά η απόδοση; Αν δεν ενδιαφέρει καθόλου η απόδοση σε εκμάθηση αλγορίθμων τότε καλώς καταργείται το μάθημα. Μην τα θέλουμε όλα δικά μας.
Ο αλγόριθμος αναζήτησης του βιβλίου είναι πράγματι απαράδεκτος. Αυτό που προτείνεις όμως χάνει την τελευταία θέση (αν αυτό που ψάχνουμε είναι στην τελευταία θέση). Γιατί να μην γίνει με Όσο, που είναι και η κλασική σειριακή αναζήτηση:
θ <- 1
Όσο θ<Ν και Α[θ]<>Query επανάλαβε
  θ<-θ+1
Τέλος_επανάληψης
βρέθηκε <- θ<=Ν

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 543
  • There can be only one...may it be AEPP.
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #18 στις: 16 Φεβ 2014, 10:30:31 πμ »
θ <- 1
Όσο θ<Ν και Α[θ]<>Query επανάλαβε
  θ<-θ+1
Τέλος_επανάληψης
βρέθηκε <- θ<=Ν

Έχω την εντύπωση πως και αυτός ο κώδικας δεν ελέγχει την τελευταία θέση.
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

Κανένας

  • Βετεράνος
  • ****
  • Μηνύματα: 52
Απ: Μια "στρωτή" αναζήτηση
« Απάντηση #19 στις: 16 Φεβ 2014, 10:56:29 πμ »
Μετά το τέλος της επανάληψης μπαίνει ένα Αν έτσι κι αλλιώς, για να ελέγξουμε αν βρέθηκε το στοιχείο (εκεί γίνεται ο έλεγχος εύρεσης).
Με το Αν αυτό κανονίζουμε και τι θα επιστρέφει σαν αποτέλεσμα (ανάλογα αν η σειριακή είναι: τμήμα κώδικα, συνάρτηση, διαδικασία)

Αν Α[θ]=Query τότε
  !χρησιμοποιούμε την τιμή του θ αν είναι τμήμα κώδικα
  position<-θ            ! αν είναι συνάρτηση επιστρέφει position
  done<-ΑΛΗΘΗΣ      ! αν είναι διαδικασία επιστρέφει position και done
αλλιώς
  position<-0            ! αν είναι συνάρτηση επιστρέφει position
 
  done<-ΨΕΥΔΗΣ      ! αν είναι διαδικασία επιστρέφει position και done
Τέλος_Αν
« Τελευταία τροποποίηση: 16 Φεβ 2014, 12:37:29 μμ από Κανένας »
ΝΙΚΗΦΟΡΟΣ ΜΑΝΔΗΛΑΡΑΣ
ΓΕΛ ΝΑΞΟΥ

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #20 στις: 16 Φεβ 2014, 11:39:51 πμ »
Σωστά nikolasmer! Ξέχασα ένα '='. Η συνθήκη στο Όσο είναι

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

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

Κανένας

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

Επισυνάπτω σχετικό φύλλο εργασίας.
« Τελευταία τροποποίηση: 16 Φεβ 2014, 01:03:21 μμ από Κανένας »
ΝΙΚΗΦΟΡΟΣ ΜΑΝΔΗΛΑΡΑΣ
ΓΕΛ ΝΑΞΟΥ

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 543
  • There can be only one...may it be AEPP.
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #22 στις: 16 Φεβ 2014, 12:15:13 μμ »
Σωστά nikolasmer! Ξέχασα ένα '='. Η συνθήκη στο Όσο είναι

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

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

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #23 στις: 16 Φεβ 2014, 01:13:07 μμ »
Εννοείται ότι δεν κάνουμε πλήρη αποτίμηση λογικών εκφράσεων. Δεν νομίζω να υπάρχει καμία δέσμευση από την πλευρά του βιβλίου, εκτός αν υπάρχει οδηγία από το υπουργείο και την αγνοώ.

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2784
  • Πύργος Ηλείας
    • ΚΕΠΛΗΝΕΤ Ηλείας
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #24 στις: 17 Φεβ 2014, 01:45:47 πμ »
Εννοείται ότι δεν κάνουμε πλήρη αποτίμηση λογικών εκφράσεων. Δεν νομίζω να υπάρχει καμία δέσμευση από την πλευρά του βιβλίου, εκτός αν υπάρχει οδηγία από το υπουργείο και την αγνοώ.

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

Παναγιώτης Τσιωτάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3218
  • I love you 3000
    • Panagiotis Tsiotakis
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #25 στις: 17 Φεβ 2014, 10:54:27 μμ »
βασικός στόχος του μαθήματος δεν είναι οι μαθητές να μάθουν να σκέφτονται και να διατυπώνουν σωστά και ολοκληρωμένα τη σκέψη τους;;

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

φιλικά, Π.

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #26 στις: 18 Φεβ 2014, 01:52:03 πμ »
@Νίκος Αδαμόπουλος
Αυτή η συντηρητική προσέγγιση κατάντησε να διδάσκουμε προγραμματισμό δεκαετίας 90 στα παιδιά. Η σύντομη αποτίμηση δεν είναι συμβατή με καμιά σημερινή γλώσσα (εκτός της Visual Basic, που και αυτή είναι παραγκωνισμένη έως ανύπαρκτη αυτή την στιγμή)

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

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

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 428
  • Real stupidity beats ΑΙ any time
Απ: Μια "στρωτή" αναζήτηση
« Απάντηση #27 στις: 18 Φεβ 2014, 01:55:47 πμ »
Τώρα σχετικά με την απόδοση:
Σ' ένα πίνακα με 1 εκατομμύριο στοιχεία και το αναζητούμενο στοιχείο στην τελευταία θέση, ο αλγόριθμος του βιβλίου θα έκανε 1 εκατομμύριο συγκρίσεις
περισσότερες απ' τον προτεινόμενο. (Η πολυπλοκότητα φυσικά είναι ίδια Ο(Ν). και οι δύο έχουν μια απλή επανάληψη).

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

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

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

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1322
  • There are always possibilities...
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #28 στις: 18 Φεβ 2014, 08:23:05 πμ »
H μερική αποτίμηση (δηλ. (Αληθης ή _ ) = Αληθής, (Ψευδής και _ ) = Ψευδής, (Ψευδής ή _ ) = _, (Αληθής και _) = _) δεν είναι προγραμματιστικό τρικ. Είναι άμεση συνέπεια του ορισμού των λογικών πράξεων και υπάρχει διδακτική αξία στο να το επισημάνεις στους μαθητές.

Αν στα μαθηματικά είχαμε πολλαπλασιασμό μιας παράστασης με το μηδέν θα καθόμασταν ποτέ να υπολογίσουμε την παράσταση;
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2784
  • Πύργος Ηλείας
    • ΚΕΠΛΗΝΕΤ Ηλείας
Απ: Μια "αιρετική" αναζήτηση
« Απάντηση #29 στις: 18 Φεβ 2014, 09:23:14 πμ »
@Νίκος Αδαμόπουλος
Αυτή η συντηρητική προσέγγιση κατάντησε να διδάσκουμε προγραμματισμό δεκαετίας 90 στα παιδιά. Η σύντομη αποτίμηση δεν είναι συμβατή με καμιά σημερινή γλώσσα (εκτός της Visual Basic, που και αυτή είναι παραγκωνισμένη έως ανύπαρκτη αυτή την στιγμή)

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

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

Υ.Γ.

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

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