Αποστολέας Θέμα: Θέμα Β  (Αναγνώστηκε 27218 φορές)

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 428
  • Real stupidity beats ΑΙ any time
Απ: Θέμα Β
« Απάντηση #75 στις: 31 Μάι 2013, 05:02:16 μμ »
Ναι συμφώνω μαζί σου,δεν ορίζεται διάταξη μεταξύ των λογικών μεταβλητών,τουλάχιστον στο ΑΕΠΠ.

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: Θέμα Β
« Απάντηση #76 στις: 31 Μάι 2013, 05:16:38 μμ »
Ωστόσο μπορείς να χρησιμοποιήσεις τον αλγόριθμο ταξινόμησης της φυσαλίδας για να διατάξεις τις λογικές τιμές έτσι ώστε να είναι οι Αληθείς πριν από τις Ψευδείς.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

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

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3174
  • I love you 3000
    • Panagiotis Tsiotakis
Απ: Θέμα Β
« Απάντηση #77 στις: 31 Μάι 2013, 05:21:12 μμ »
πιθανώς εννοείς μόνο με τη χρήση = και <>, δεκτό
κάτι που δεν αναιρεί το νόημα του παρακάτω (το οποίο άλλαξα ελαφρά στο πρωτότυπο)

ΔΕΝ θεωρώ οτι ο αποκλεισμός των "αλγορίθμων ταξινόμησης" είναι για την πολυπλοκότητα. Η επιτροπή προσπάθησε πιθανόν να αποτρέψει όλους μας να λύσουμε ΛΑΝΘΑΣΜΕΝΑ με φυσαλίδα την άσκηση, μιας και ΔΕΝ ΜΠΟΡΟΥΜΕ ΝΑ ΤΑΞΙΝΟΜΗΣΟΥΜΕ λογικές τιμές αφού δεν μπορούμε να κάνουμε ερωτήσεις > και < σε αυτές.
Διαφορετικά, θα συζητούσαμε ακόμη σήμερα (edit:) τη σχετική αναφορά στη σελίδα 166 του σχολικού βιβλίου μαθητή  και θα διυλίζαμε τον κώνωπα όπως το 2010.
Ευτυχώς, ο καλός Θεούλης μας προστάτεψε από αυτήν την εξέλιξη.


itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 428
  • Real stupidity beats ΑΙ any time
Απ: Θέμα Β
« Απάντηση #78 στις: 31 Μάι 2013, 06:13:44 μμ »
Παράθεση
Μερικοί μπορείτε να πείτε ότι το παραπάνω επιχείρημα είναι εξυπναδίστικο και ότι παίζω με τις λέξεις.
Δεν το λέω έτσι. Στην εξέταση των ΦΑ είχαμε το εξής πρόβλημα: Πολλοί θεώρησαν ότι  ο πίνακας έχει 50 αληθείς και 50 ψευδείς. Πιστεύω ότι η συγκεκριμένη διατύπωση τους δημιούργησε την παρανόηση μιας ιδιότυπης συμμετρίας, δηλαδή έχω δύο άκρα, ισοβαρή κλπ. Επίσης μπορεί κάποιοι να αναρωτήθηκαν οκ στις πρώτες έχει αυτά και στις τελευταίες αυτά, στις μεσαίες τι έχει?

Νομίζω ( απλά για την ιστορία ) ότι η διατύπωση θα έπρεπε να ήταν "Να τοποθετεί τα στοιχεία του πίνακα έτσι ώστε όλες οι Αληθείς να είναι πριν από τις Ψευδείς"

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

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2779
  • Πύργος Ηλείας
    • ΚΕΠΛΗΝΕΤ Ηλείας
Απ: Θέμα Β
« Απάντηση #79 στις: 31 Μάι 2013, 08:07:53 μμ »
Δεν το λέω έτσι. Στην εξέταση των ΦΑ είχαμε το εξής πρόβλημα: Πολλοί θεώρησαν ότι  ο πίνακας έχει 50 αληθείς και 50 ψευδείς.

Αυτό το υπέθεσε και ένας γνωστός μου (μέτριος προς κακός) μαθητής και το υλοποίησε με 2 εντολές Για. Άραγε τι πιάνει;

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 428
  • Real stupidity beats ΑΙ any time
Απ: Θέμα Β
« Απάντηση #80 στις: 31 Μάι 2013, 10:07:31 μμ »
Αυτό το υπέθεσε και ένας γνωστός μου (μέτριος προς κακός) μαθητής και το υλοποίησε με 2 εντολές Για. Άραγε τι πιάνει;

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

Αθανάσιος Πέρδος

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 288
Απ: Θέμα Β
« Απάντηση #81 στις: 31 Μάι 2013, 10:26:33 μμ »
Ο ορισμός της ταξινόμησης στη σελίδα 66 του σχολικού βιβλίου (αλλά και γενικότερα) αναφέρει ότι δεν συγκρίνουμε τις τιμές "ak" του πίνακα,
αλλά τις τιμές μια συνάρτησης "f(ak)",
η οποία για την περίπτωση των λογικών μεταβλητών θα μπορούσε να οριστεί ως f(Ψευδής)=0 και f(Αληθής)=1.

Δηλαδή φυσικά και μπορεί να οριστεί ταξινόμηση πινάκων λογικών μεταβλητών.

Στην υλοποίηση της φυσαλίδας στη σελίδα 68, εάν θέλαμε να βάλουμε τη συνάρτηση f(), ώστε να "πιάσουμε" και τους πίνακες λογικών μεταβλητών, θα αλλάζαμε μόνο την εντολή Αν:
Αν f(table[j-1]) > f(table[j]) τότε
...

Αν δεν ίσχυε ο παραπάνω ορισμός, τότε δεν θα μπορούσαμε να μιλάμε ούτε καν για ταξινομημένους τηλεφωνικούς καταλόγους, αφού δεν ορίζεται η σύγκριση μεταξύ εγγραφών (structs). Αλλά και σ' εκείνη την περίπτωση ορίζουμε έμμεσα μια συνάρτηση f(struct) η οποία μας επιστρέφει μόνο το ονοματεπώνυμο και όχι το τηλέφωνο, οπότε και χρησιμοποιούμε αυτό για τη σύγκριση των εγγραφών.

Έτσι είναι. Για να υπάρχει ταξινόμηση πρέπει να υπάρχει διάταξη. Διάταξη όχι στο σύνολο των στοιχείων που ταξινομούμε, αλλά στο σύνολο των εικόνων των στοιχείων που ταξινομούμε μέσω της ordering function.
Στην κλασσική αύξουσα ταξινόμηση ordering function έχεις την ταυτοτική f(x)=x, στην αύξουσα την f(x)=-x. Προφανώς το σύνολο των 2 τιμών {Αληθής, Ψευδής} δεν είναι διατεταγμένο, αλλά μπορείς να ορίσεις μια ordering function πχ f(Αληθής)=0 και f(Ψευδής)=1 και να συνεχίσεις. Αν ορίσεις f(x)=x στις λογικές τότε προφανώς δε γίνεται ταξινόμηση γιατί δεν υπάρχει διάταξη στις λογικές τιμές. Αυτά όμως παρακάμπτονται εύκολα.
Κι εγώ αν ήθελα formal διατύπωση του θέματος χωρίς περιορισμό από τη σχολική ύλη θα μίλαγα για Ο(ν) αντί για Ο(ν^2).


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

μ<-- 0
Για κ από 1 μέχρι 100
      Αν Π[κ] = Αληθής τότε (ή Π[κ] < 0 ή Π[κ]mod2 = 0 για παράδειγμα)
           μ <-- μ + 1
           Αντιμετάθεσε Π[κ], Π[μ]
      τέλος_αν
τελος_επανάληψης

με βάση τα παραπάνω καταφέρνει να ταξινομήσει διατεταγμένο σύνολο.

Είναι αλγόριθμος ταξινόμησης ή όχι; Και αν όχι γιατί; Εγώ πάντως δεν μπορώ να απαντήσω.

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Θέμα Β
« Απάντηση #82 στις: 01 Ιούν 2013, 07:17:05 πμ »
Είναι αλγόριθμος ταξινόμησης ή όχι; Και αν όχι γιατί; Εγώ πάντως δεν μπορώ να απαντήσω.

Εφόσον ικανοποιεί τον ορισμό της ταξινόμησης, δηλαδή κάνει τον πίνακα να είναι τελικά διατεταγμένος με βάση κάποια συνάρτηση (ή τελεστή) σύγκρισης, ναι, είναι ταξινόμηση.

Βυθίζεται ο Τιτανικός! Να σωθούν πρώτα τα γυναικόπαιδα!
=> έχουμε έναν πίνακα (σειρά ανθρώπων) ο οποίος περιέχει λογικές μεταβλητές (γυναικόπαιδο ή όχι)
=> η επεξεργασία που θέλουμε να του κάνουμε είναι ταξινόμηση πίνακα λογικών μεταβλητών, το ίδιο με το θέμα Β´

Τώρα αν θα το κάνουμε με τελεστή σύγκρισης, Αν γυναικόπαιδο = Αληθής,
ή με συνάρτηση σύγκρισης, f(γυναικόπαιδο) = 1 ή 0,
αυτό είναι λεπτομέρεια, ο τελεστής είναι απλά μια υποπερίπτωση της συνάρτησης.


Οπότε συνοψίζοντας,
  • αυτό που ζητούσε το ερώτημα είναι ταξινόμηση,
  • δεν ορίζονται οι τελεστές > και < μεταξύ λογικών μεταβλητών στην ΑΕΠΠ,
  • μπορεί να οριστεί διάταξη μεταξύ των δύο λογικών τιμών στην ΑΕΠΠ, είτε με συγκριτικό τελεστή (= Ψευδής, <> Αληθής...) είτε με συνάρτηση,
  • άρα ορίζεται ταξινόμηση πίνακα λογικών μεταβλητών στα πλαίσια της ΑΕΠΠ,
  • και αν δεν υπήρχαν οι περιορισμοί της εκφώνησης, το ερώτημα θα μπορούσε να λυθεί (μπακαλίστικα) με ταξινόμηση φυσαλίδας και συγκριτικούς τελεστές.

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Θέμα Β
« Απάντηση #83 στις: 01 Ιούν 2013, 09:55:04 πμ »
Για να μην τσαντίσουμε τον Παναγιώτη, διατυπώνω κάπως διαφορετικά. Το σύνολο {Αληθής, Ψευδής} δεν είναι διατεταγμένο και άρα δεν μπορεί να γίνει σύγκριση μεταξύ του Αληθής και του ψευδής Με τελεστές < και >. Για αυτό μεταφερόμαστε σε άλλο συνολο που υπάρχει η διάταξη. Στέλνεις το Αληθής στο 0 και το Ψευδής στο 1 και συγκρίνεις όχι πια τα 0 Αληθής και Ψευδής αλλά τα 0 και 1 δηλαδή τις εικόνες τους μέσω της συνάρτησης f η οποία υλοποιεί απλώς αυτή την αντιστοιχία. Η f δηλαδή ορίζεται με πεδίο ορισμού το {Αληθής, Ψευδής} και απεικονίζει αυτό το σύνολο στο {0,1} όπου υπάρχει η διάταξη και άρα οι τελεστές < και > παίζουν κανονικά.

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Θέμα Β
« Απάντηση #84 στις: 01 Ιούν 2013, 11:10:17 πμ »
Γιώργο νομίζω έχεις στο νου σου τους "comparison sort" αλγορίθμους, που δουλεύουν με οποιοδήποτε σύνολο εισόδου, έχουν αποδεδειγμένο κάτω όριο Ω(n*logn) κλπ.
Οι περισσότεροι "non comparison sorts" έχουν συγκεκριμένες απαιτήσεις από το σύνολο εισόδου, δεν δεσμεύονται από το Ω(n*logn), και παρόλα αυτά στην βιβλιογραφία αναφέρονται ως sorting algorithms...

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
...εκεί έχει έναν πίνακα με τους "comparison sorts", και αμέσως μετά έναν με τους "non comparison sorts" στους οποίους αναφέρομαι.

edit:
Για να μην τσαντίσουμε τον Παναγιώτη, διατυπώνω κάπως διαφορετικά.
...εντάξει μωρέ στο επόμενο συνέδριο τον κερνάμε 2-3 τσίπουρα παραπάνω και θα μας συγχωρήσει!  :D

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 428
  • Real stupidity beats ΑΙ any time
Απ: Θέμα Β
« Απάντηση #85 στις: 01 Ιούν 2013, 11:28:56 πμ »
Εφόσον ικανοποιεί τον ορισμό της ταξινόμησης, δηλαδή κάνει τον πίνακα να είναι τελικά διατεταγμένος με βάση κάποια συνάρτηση (ή τελεστή) σύγκρισης, ναι, είναι ταξινόμηση.

Βυθίζεται ο Τιτανικός! Να σωθούν πρώτα τα γυναικόπαιδα!
=> έχουμε έναν πίνακα (σειρά ανθρώπων) ο οποίος περιέχει λογικές μεταβλητές (γυναικόπαιδο ή όχι)
=> η επεξεργασία που θέλουμε να του κάνουμε είναι ταξινόμηση πίνακα λογικών μεταβλητών, το ίδιο με το θέμα Β´

Τώρα αν θα το κάνουμε με τελεστή σύγκρισης, Αν γυναικόπαιδο = Αληθής,
ή με συνάρτηση σύγκρισης, f(γυναικόπαιδο) = 1 ή 0,
αυτό είναι λεπτομέρεια, ο τελεστής είναι απλά μια υποπερίπτωση της συνάρτησης.


Οπότε συνοψίζοντας,
  • αυτό που ζητούσε το ερώτημα είναι ταξινόμηση,
  • δεν ορίζονται οι τελεστές > και < μεταξύ λογικών μεταβλητών στην ΑΕΠΠ,
  • μπορεί να οριστεί διάταξη μεταξύ των δύο λογικών τιμών στην ΑΕΠΠ, είτε με συγκριτικό τελεστή (= Ψευδής, <> Αληθής...) είτε με συνάρτηση,
  • άρα ορίζεται ταξινόμηση πίνακα λογικών μεταβλητών στα πλαίσια της ΑΕΠΠ,
  • και αν δεν υπήρχαν οι περιορισμοί της εκφώνησης, το ερώτημα θα μπορούσε να λυθεί (μπακαλίστικα) με ταξινόμηση φυσαλίδας και συγκριτικούς τελεστές.

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Θέμα Β
« Απάντηση #86 στις: 01 Ιούν 2013, 11:49:06 πμ »
Άμα αυτό που ζητούσε η ερώτηση εἰναι ταξινόμηση τότε δεν έχει νόημα.Αφού με τη λογική αυτή όποιον αλγόριθμο και να χρησιμοποιούσες θα έπρεπε να θεωρηθεί αλγόριθμος ταξινόμησης καθώς θα ταξινομούσε τα στοιχεία με βάση κάποια total order.

Yup, πιστεύω πώς οι περισσότεροι συμφωνούμε ότι αν και το θέμα ήταν ωραίο, η εκφώνησή του ήταν λίγο αμφιλεγόμενη.
Π.χ. νομίζω ότι οι πιο αποδεκτές υλοποιήσεις που προτάθηκαν, εφαρμόζουν την εκφυλισμένη περίπτωση του counting sort για k=2 (όπου δεν χρειάζεται πίνακας k μετρητών, αλλά μόνο ένας ή δύο μετρητές), και παίρνουν όλα τα μόρια...
...ενώ πιο αμφιλεγόμενο στη βαθμολόγηση θα είναι αν κάποιος έχει υλοποιήσει σωστά το bubble sort, με τους τελεστές = ή <>.

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

cets89

  • Βαθμολογικά 2016
  • *
  • Μηνύματα: 42
  • Μηδέν άγαν!
Απ: Θέμα Β
« Απάντηση #87 στις: 01 Ιούν 2013, 04:24:16 μμ »
Παραθέτω μια "κομψή" λύση που δώσαμε για το Β2 ως εξεταστές Φ.Α.
j <- 0
Για i από 1 μέχρι 100
     Αν Π[ i ] = ΑΛΗΘΗΣ τότε
          j <- j+1
          Αντιμετάθεσε Π[ i ], Π[ j ]
     Τέλος_αν
Τέλος_επανάληψης
Κωνσταντίνος Τσουκάρας
Διπλωματούχος Μηχανικός Η/Υ και Πληροφορικής Πανεπιστημίου Πατρών

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Θέμα Β
« Απάντηση #88 στις: 01 Ιούν 2013, 04:37:57 μμ »
Από την άλλη, αν η εκφώνηση μπορούσε να πει "απαγορεύετε να χρησιμοποιήσετε εμφωλευμένη επανάληψη", δεν θα υπήρχε τίποτα αμφιλεγόμενο.
Σκέψου όμως ότι θα μπορούσε να υλοποιήσει φυσσαλίδα με μονό βρόχο   :D

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Θέμα Β
« Απάντηση #89 στις: 01 Ιούν 2013, 06:27:27 μμ »
Χεχε, το είχα σκεφτεί ένα λεπτό αφότου είχα γράψει το μήνυμα, αλλά είπα να μην το χοντρύνω! Σύμφωνοι, η O(n (+k για το πλήθος του πεδίου τιμών)) πολυπλοκότητα θα ήταν η καλύτερη εκφώνηση!
...αλλά από την άλλη, αν κάποιος κατάφερνε ταξινόμηση φυσαλίδας με μονό loop, εγώ θα του έβαζα 100 χωρίς να κοιτάξω καν τις άλλες απαντήσεις του!  >:D