Έλεγχος εισαγωγής ακεραίου/Ταξινόμηση ευθείας ανταλλαγής

[metestaki]

Καλησπέρα! 
Δυο ερωτήματα:

1.Έλεγχος εισαγωγής ακεραίου
Όταν μια άσκηση λέει "Να διαβάζει ένα ακέραιο αριθμό" πρέπει ο λύτης να μπει στη διαδικασία ελέγχου εγκυρότητας δεδομένων, όσον αφορά τον έλεγχο για το αν δόθηκε ακέραιος αριθμός, ως εξής:
Αρχή_ επανάληψης
Διάβασε χ
μέχρις_ότου χ=Α_Μ(χ)


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


Ευχαριστώ!!!

[petrosp13]

Εννοεί αν τα στοιχεία του είναι ίδια
Προφανώς είναι λάθος γιατί ο αλγόριθμος θα κάνει πάρα πολλές περιττές επαναλήψεις

[gthal]

Καλημέρα.
Όσο για το πρώτο ερώτημα

1.Έλεγχος εισαγωγής ακεραίου
Όταν μια άσκηση λέει "Να διαβάζει ένα ακέραιο αριθμό" πρέπει ο λύτης να μπει στη διαδικασία ελέγχου εγκυρότητας δεδομένων, όσον αφορά τον έλεγχο για το αν δόθηκε ακέραιος αριθμός ...

κι εδώ η απάντηση είναι αρνητική. Όταν η άσκηση θέλει έλεγχο εκγυρότητας το ζητάει ρητά. Σε κάθε άλλη περίπτωση, η σχετική δήλωση της εκφώνησης πρέπει να ληφθεί ως πληροφορία για το τι είδους δεδομένα θα λάβουμε (πχ εδώ ακεραίους, σε άλλες ασκήσεις "το 0 ή το 1" ή "βαθμός από 0 ως 20"  κλπ) γιατί προφανώς θα τη χρειαστούμε (αυτή την πληροφορία) κατά την επεξεργασία τους. Φυσικά, αν ο λύτης κάνει έλεγχο εκγυρότητας, δε φαντάζομαι ότι κανείς θα του το θεωρήσει λάθος - απλά δε χρειάζεται.
Καλό το ερώτημα. Είναι πολλοί οι μαθητές που για μεγάλο διάστημα δυσκολεύονται να κάνουν τη διάκριση μεταξύ των δύο ερμηνειών.

[evry]

Ένα λεπτό, άλλο αποτελεσματική και άλλο αποδοτική.
Αποτελεσματική σημαίνει ότι έχει σωστό αποτέλεσμα, δηλαδή εδώ μας ενδιαφέρει η ορθότητα του αλγορίθμου.
Οπότε θα πρέπει αν κάποιος θέλει να μιλήσει για αποτελεσματικότητα να κάτσει και να αποδείξει ότι ο αλγόριθμος είναι αποτελεσματικός και σε αυτή την περίπτωση.
Είναι προφανές ότι στην περίπτωση των ίσων στοιχείων του πίνακα ο αλγόριθμος είναι αποτελεσματικός όπως άλλωστε και κάθε άλλος αλγόριθμος ταξινόμησης.
Ποιο όμως το νόημα της ερώτησης τότε?
Καταρχήν να πω εδώ ότι κατά τη γνώμη μου η ερώτηση είναι ούτως ή άλλως άκυρη.
Η μελέτη αλγορίθμου στην περίπτωση των ίσων κλειδιών έχει νόημα για να εξετάσουμε αυτό που λέμε stability του αλγορίθμου, ευστάθεια μου φαίνεται η καλύτερη μετάφραση
Τι ονομάζουμε ευσταθή αλγόριθμο ταξινόμησης?
Τον αλγόριθμο ο οποίος δεν αλλάζει τη σχετική σειρά των ίσων στοιχείων. Ο αλγόριθμος ευθείας ανταλλαγής είναι ευσταθής διότι δεν έχει <= ή >= αλλά < ή > .
Περισσότερα μπορείτε να διαβάσετε στους παρακάτω συνδέσμους
http://www.algorithmist.com/index.php/Stable_Sort
http://stackoverflow.com/questions/808617/what-is-the-benefit-for-a-sort-algorithm-to-be-stable

Για να καταλάβετε καλύτερα την έννοια της ευστάθειας προσπαθήστε να κάνετε ταξινόμηση με <= σε δύο παράλληλους πίνακες με ονόματα και βαθμούς μαθητών όπου κάποιοι μαθητές έχουν τον ίδιο βαθμό. Θα πρέπει μετά το πέρας της ταξινόμησης να μην αλλάξει η σειρά τους. Δηλαδή αν για παράδειγμα υπάρχουν 10 μαθητές που έχουν 18 και είναι εξαρχής σε αλφαβητική σειρά θα πρέπει και μετά την ταξινόμηση να παραμείνουν σε αλφαβητική σειρά.
Αυτά όσον αφορά τα ίσα κλειδιά

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

[gthal]

Ο αλγόριθμος ευθείας ανταλλαγής είναι ευσταθής διότι δεν έχει < ή > αλλά <= .

... μάλλον το αντίστροφο ήθελες να γράψεις εδώ ... ? (δεν έχει <= αλλά < πχ)

[evry]

Γιώργο ευχαριστώ, το άλλαξα παραπάνω για να μην μπερδευτεί κάποιος που θα διαβάσει το post

... μάλλον το αντίστροφο ήθελες να γράψεις εδώ ... ? (δεν έχει <= αλλά < πχ)

[metestaki]

Επομένως:
1.Έλεγχος εισαγωγής ακεραίου
Όταν μια άσκηση λέει "Να διαβάζει ένα ακέραιο αριθμό" πρέπει ο λύτης να μπει στη διαδικασία ελέγχου εγκυρότητας δεδομένων, όσον αφορά τον έλεγχο για το αν δόθηκε ακέραιος αριθμός, ως εξής:
Αρχή_ επανάληψης
Διάβασε χ
μέχρις_ότου χ=Α_Μ(χ)
μόνο αν ζητείται από την εκφώνηση να ελέγχεται αν δόθηκε ακέραιος αριθμός.

2.Ταξινόμηση ευθείας ανταλλαγής
Η ταξινόμηση ευθείας ανταλλαγής είναι πολύ αποτελεσματική αν ο πίνακας περιέχει ίσα κλειδιά.
Η παραπάνω πρόταση είναι λανθασμένη γιατί δεν τίθεται θέμα αποτελεσματικότητας;
Στο πακέτο ασκήσεων που τη συνάντησα αναφέρεται λύση ως "Σωστή".
Μήπως μπορεί να θεωρηθεί σωστή λόγω του ότι στη σύγκριση χρησιμοποιείται το "<" ή ">" χωρίς το "=" επομένως δεν θα γίνει καμμία αντιμετάθεση σε πίνακα που περιέχει ίσα κλειδιά;

[evry]

Δεν καταλαβαίνω τι σημαίνει το πολύ αποτελεσματική. Δηλαδή υπάρχει και λίγο αποτελεσματική? Πως ορίζεται το αποτελεσματική? Υπάρχει πουθενά στο βιβλίο μια εξήγηση του τι σημαίνει "αποτελεσματικός" αλγόριθμος?
(ή μήπως να έχει σχέση με το κριτήριο της αποτελεσματικότητας  )
Αν δεν υπάρχει δεν νομίζω ότι μπορούμε να το χρησιμοποιούμε έτσι.
Η ουσία είναι ότι πρόκειται για μια ερώτηση την οποία δεν μπορείς να βάλεις σε μαθητές γιατί δεν μπορείς να δικαιολογήσεις τη σωστή απάντηση οποία και να είναι και επειδή δεν είναι υποχρεωμένοι να ξέρουν τι είναι "αποτελεσματικός" αλγόριθμος.

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

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

[metestaki]

Ok.Ευχαριστώ!

[Σπύρος Δουκάκης]

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

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

π.χ. θα μπορούσε η πρόταση να ήταν η ακόλουθη:

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

Δεν καταλαβαίνω τι σημαίνει το πολύ αποτελεσματική. Δηλαδή υπάρχει και λίγο αποτελεσματική? Πως ορίζεται το αποτελεσματική? Υπάρχει πουθενά στο βιβλίο μια εξήγηση του τι σημαίνει "αποτελεσματικός" αλγόριθμος?
(ή μήπως να έχει σχέση με το κριτήριο της αποτελεσματικότητας  )
Αν δεν υπάρχει δεν νομίζω ότι μπορούμε να το χρησιμοποιούμε έτσι.
Η ουσία είναι ότι πρόκειται για μια ερώτηση την οποία δεν μπορείς να βάλεις σε μαθητές γιατί δεν μπορείς να δικαιολογήσεις τη σωστή απάντηση οποία και να είναι και επειδή δεν είναι υποχρεωμένοι να ξέρουν τι είναι "αποτελεσματικός" αλγόριθμος.

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

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

[gthal]

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

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

[evry]

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

Η σειριακή αναζήτηση είναι η πιο απλή, αλλά και η λιγότερη αποτελεσματική μέθοδος

(τουλάχιστον στο παλιό βιβλίο που έχω εγώ. Δεν ξέρω αν το έχουν αλλάξει )

Τι εννοεί ο ποιητής? προφανώς εννοεί αποδοτική και όχι αποτελεσματική. Μάλλον έγινε λάθος στη μετάφραση του efficient. Λογικά το ίδιο συμβαίνει και στην ερώτηση του βιβλίου καθηγητή.
Άρα εννοούν αποδοτική και όχι αποτελεσματική. Τώρα ίσως έχει κάποιο νόημα αλλά φυσικά είναι εκτός ύλης.
Άσε που για να απαντήσεις σε αυτό θα πρέπει να το αποδείξεις κιόλας.

Σπύρο στην ερώτηση που έδωσες τα στοιχεία του πίνακα είναι όλα ίσα. Στην αρχική ερώτηση δεν λέει ότι είναι όλα ίσα αλλά ότι ο πίνακας περιέχει ίσα κλειδιά.
Εγώ καταλαβαίνω ότι περιέχει κάποια κλειδιά που είναι ίσα μεταξύ τους αλλά όχι ότι όλα είναι ίσα μεταξύ τους. Όταν την πρωτοδιάβασα αυτό κατάλαβα. Τώρα που το ξανακοιτάω δεν είμαι σίγουρος πάντως τι από τα 2 εννοεί.
  Θέλω να πω ότι αν ήταν όλα ίσα θα έλεγε "όλα ίσα μεταξύ τους" και όχι απλά "περιέχει ίσα κλειδιά". τες πα μάλλον δεν έχει σημασία πλέον