Θέμα Β

Ξεκίνησε από gpapargi, 29 Μαΐου 2013, 10:19:38 ΠΜ

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

itt

Ναι συμφώνω μαζί σου,δεν ορίζεται διάταξη μεταξύ των λογικών μεταβλητών,τουλάχιστον στο ΑΕΠΠ.

evry

Ωστόσο μπορείς να χρησιμοποιήσεις τον αλγόριθμο ταξινόμησης της φυσαλίδας για να διατάξεις τις λογικές τιμές έτσι ώστε να είναι οι Αληθείς πριν από τις Ψευδείς.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

P.Tsiotakis

πιθανώς εννοείς μόνο με τη χρήση = και <>, δεκτό
κάτι που δεν αναιρεί το νόημα του παρακάτω (το οποίο άλλαξα ελαφρά στο πρωτότυπο)

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


itt

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

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

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

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

Παράθεση από: evry στις 31 Μαΐου 2013, 11:20:00 ΠΜ
Δεν το λέω έτσι. Στην εξέταση των ΦΑ είχαμε το εξής πρόβλημα: Πολλοί θεώρησαν ότι  ο πίνακας έχει 50 αληθείς και 50 ψευδείς.

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

itt

Παράθεση από: Νίκος Αδαμόπουλος στις 31 Μαΐου 2013, 08:07:53 ΜΜ
Αυτό το υπέθεσε και ένας γνωστός μου (μέτριος προς κακός) μαθητής και το υλοποίησε με 2 εντολές Για. Άραγε τι πιάνει;

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

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

Παράθεση από: alkisg στις 31 Μαΐου 2013, 03:55:13 ΜΜ
Ο ορισμός της ταξινόμησης στη σελίδα 66 του σχολικού βιβλίου (αλλά και γενικότερα) αναφέρει ότι δεν συγκρίνουμε τις τιμές "ak" του πίνακα,
αλλά τις τιμές μια συνάρτησης "f(ak)",
η οποία για την περίπτωση των λογικών μεταβλητών θα μπορούσε να οριστεί ως f(Ψευδής)=0 και f(Αληθής)=1.

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

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

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

Παράθεση από: gpapargi στις 31 Μαΐου 2013, 04:21:58 ΜΜ
Έτσι είναι. Για να υπάρχει ταξινόμηση πρέπει να υπάρχει διάταξη. Διάταξη όχι στο σύνολο των στοιχείων που ταξινομούμε, αλλά στο σύνολο των εικόνων των στοιχείων που ταξινομούμε μέσω της 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

Παράθεση από: aperdos στις 31 Μαΐου 2013, 10:26:33 ΜΜ
Είναι αλγόριθμος ταξινόμησης ή όχι; Και αν όχι γιατί; Εγώ πάντως δεν μπορώ να απαντήσω.

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

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

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


Οπότε συνοψίζοντας,

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

gpapargi

Για να μην τσαντίσουμε τον Παναγιώτη, διατυπώνω κάπως διαφορετικά. Το σύνολο {Αληθής, Ψευδής} δεν είναι διατεταγμένο και άρα δεν μπορεί να γίνει σύγκριση μεταξύ του Αληθής και του ψευδής Με τελεστές < και >. Για αυτό μεταφερόμαστε σε άλλο συνολο που υπάρχει η διάταξη. Στέλνεις το Αληθής στο 0 και το Ψευδής στο 1 και συγκρίνεις όχι πια τα 0 Αληθής και Ψευδής αλλά τα 0 και 1 δηλαδή τις εικόνες τους μέσω της συνάρτησης f η οποία υλοποιεί απλώς αυτή την αντιστοιχία. Η f δηλαδή ορίζεται με πεδίο ορισμού το {Αληθής, Ψευδής} και απεικονίζει αυτό το σύνολο στο {0,1} όπου υπάρχει η διάταξη και άρα οι τελεστές < και > παίζουν κανονικά.

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

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

alkisg

#84
Γιώργο νομίζω έχεις στο νου σου τους "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:
Παράθεση από: gpapargi στις 01 Ιουν 2013, 09:55:04 ΠΜ
Για να μην τσαντίσουμε τον Παναγιώτη, διατυπώνω κάπως διαφορετικά.
...εντάξει μωρέ στο επόμενο συνέδριο τον κερνάμε 2-3 τσίπουρα παραπάνω και θα μας συγχωρήσει!  :D

itt

Παράθεση από: alkisg στις 01 Ιουν 2013, 07:17:05 ΠΜ
Εφόσον ικανοποιεί τον ορισμό της ταξινόμησης, δηλαδή κάνει τον πίνακα να είναι τελικά διατεταγμένος με βάση κάποια συνάρτηση (ή τελεστή) σύγκρισης, ναι, είναι ταξινόμηση.

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

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


Οπότε συνοψίζοντας,

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

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

alkisg

Παράθεση από: itt στις 01 Ιουν 2013, 11:28:56 ΠΜ
Άμα αυτό που ζητούσε η ερώτηση εἰναι ταξινόμηση τότε δεν έχει νόημα.Αφού με τη λογική αυτή όποιον αλγόριθμο και να χρησιμοποιούσες θα έπρεπε να θεωρηθεί αλγόριθμος ταξινόμησης καθώς θα ταξινομούσε τα στοιχεία με βάση κάποια total order.

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

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

cets89

Παραθέτω μια "κομψή" λύση που δώσαμε για το Β2 ως εξεταστές Φ.Α.
j <- 0
Για i από 1 μέχρι 100
     Αν Π[ i ] = ΑΛΗΘΗΣ τότε
          j <- j+1
          Αντιμετάθεσε Π[ i ], Π[ j ]
     Τέλος_αν
Τέλος_επανάληψης
As soon as an Analytical Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will then arise--
By what course of calculation can these results be arrived at by the machine in the shortest time?
--CHARLES BABBAGE (1864)

gpapargi

Παράθεση από: alkisg στις 01 Ιουν 2013, 11:49:06 ΠΜ
Από την άλλη, αν η εκφώνηση μπορούσε να πει "απαγορεύετε να χρησιμοποιήσετε εμφωλευμένη επανάληψη", δεν θα υπήρχε τίποτα αμφιλεγόμενο.
Σκέψου όμως ότι θα μπορούσε να υλοποιήσει φυσσαλίδα με μονό βρόχο   :D

alkisg

Χεχε, το είχα σκεφτεί ένα λεπτό αφότου είχα γράψει το μήνυμα, αλλά είπα να μην το χοντρύνω! Σύμφωνοι, η O(n (+k για το πλήθος του πεδίου τιμών)) πολυπλοκότητα θα ήταν η καλύτερη εκφώνηση!
...αλλά από την άλλη, αν κάποιος κατάφερνε ταξινόμηση φυσαλίδας με μονό loop, εγώ θα του έβαζα 100 χωρίς να κοιτάξω καν τις άλλες απαντήσεις του!  >:D