Αποστολέας Θέμα: ΔΟΜΗ ΕΠΙΛΟΓΗΣ ΠΕΡΙΟΡΙΣΜΟΙ  (Αναγνώστηκε 8209 φορές)

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

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3176
  • I love you 3000
    • Panagiotis Tsiotakis
Re: ΔΟΜΗ ΕΠΙΛΟΓΗΣ ΠΕΡΙΟΡΙΣΜΟΙ
« Απάντηση #15 στις: 15 Νοέ 2004, 10:16:44 μμ »
[smiley=cwm39.gif]        8)





Παρακαλώ συνεχίστε...

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Re: ΔΟΜΗ ΕΠΙΛΟΓΗΣ ΠΕΡΙΟΡΙΣΜΟΙ
« Απάντηση #16 στις: 15 Νοέ 2004, 11:28:02 μμ »
«Το γένος του redhata είναι δηλωμένο μια χαρά»
Αλίμονο. . . δεν παίζουμε με αυτά. Ακούς Χάιντι;

Τώρα κατάλαβα τι εννοείς λέγοντας «εξέταση». Νόμιζα ότι ο χαρακηρισμός «εξέταση» πήγαινε στη σπαζοκεφαλιά που έθεσα (να βρεθεί παράδειγμα που μας βολεύει ο αλγόριθμος 2 για λόγους ταχύτητας). Κατάλαβα στραβά, αναγνωρίζω το λάθος μου. Πάντως προς αποφυγή παρεξηγήσεων δήλωσα εξαρχής ότι μέσα στην αίθουσα κανένας φοιτητής δεν πήρε χαμπάρι το λάθος. Ο χρόνος που μας είχε δώσει ο καθηγητής ήταν λίγος αλλά βέβαια δεν περίμενα να διαθέσει κανείς από το στέκι περισσότερο. Αν το βλέπεις σαν εξέταση τότε δήλωσα από την αρχή ότι κόπηκα και εγώ.

Η αλήθεια είναι ότι ο αλγόριθμος 2 δεν είναι τόσο ευάλωτος σε τέτοιες παγίδες. Είναι πιο ξεκάθαρος. Πάντως δεν μεροληπτώ υπέρ του. Επειδή φάνηκε ο αλγ 1 να κερδίζει τις εντυπώσεις και θεωρώ σωστό για την κουβέντα να ακούγονται όλες οι απόψεις εξίσου, τον αβαντάρισα λίγο (σαν αποκατάσταση της ισοροπίας). Στην κριτκή που σκοπεύω να γράψω θα είμαι 100% αντικειμενικός. Κάθε αλγόριθμος έχει πλεονεκτήματα και μειονεκτήματα και άρα δικό του πεδίο εφαρμογής.

ΥΓ Παναγιώτη χωρατατζής όπως πάντα  ;D

George

  • Θαμώνας
  • ***
  • Μηνύματα: 41
  • Γράψτε το προσωπικό σας σλόγκαν!
Re: ΔΟΜΗ ΕΠΙΛΟΓΗΣ ΠΕΡΙΟΡΙΣΜΟΙ
« Απάντηση #17 στις: 16 Νοέ 2004, 12:17:15 πμ »
Καλησπέρα
Άναψαν λίγο τα αίματα και ζωντάνεψε η κουβέντα. Χρειάζεται που και που! Μόνο που ο Παναγιώτης πήρε όλα τα Ποπκορν και δεν μας είπε από πού για να πάρουμε και εμείς!
Στην κουβέντα μας τώρα για τους δύο αλγορίθμους. Εγώ συμπαθώ και τους δύο για διαφορετικούς λόγους. Ο πρώτος δεν κάνει περιττούς ελέγχους και είναι ποιο λιτός και ''κομψός'' (αν και δεν πρόκειται να τον στείλουμε στα καλλιστεία!!!). Ο δεύτερος θεωρώ ότι είναι ποιο ξεκάθαρος και ''λογικός'' για τους περισσότερους  μαθητές και τον μαθαίνουν ευκολότερα. Όσο για τον έλεγχο περιττών συνθηκών  πιστεύω ότι δεν πρέπει να θεωρείτε λάθος στους Αλγορίθμους.  
Ο Αλγ2 μιας και δεν επηρεάζεται από την αλλαγή στη σειρά των συνθηκών  θα μπορούσε να είναι ταχύτερος στην περίπτωση που ελέγχουμε πρώτα την περιοχή τιμών που βρίσκεται η πλειοψηφία των μαθητών.
Με εκτίμηση,

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Re: ΔΟΜΗ ΕΠΙΛΟΓΗΣ ΠΕΡΙΟΡΙΣΜΟΙ
« Απάντηση #18 στις: 16 Νοέ 2004, 08:47:43 πμ »
Λοιπόν, ξεκινώ τη σύγκριση των 2 αλγορίθμων από το θέμα της αποδοτικότητας που φαίνεται να συζητήθηκε περισσότερο.

Ο αλγόριθμος 2 διπλασιάζει τους ελέγχους και σε πρώτη φάση είναι πιο αργός. Αλλά ο τρόπος που τους αυξάνει (ο διπλασιασμός) δεν είναι τόσο κακός. Δηλαδή δεν αλλάζει την τάξη του αλγορίθμου. Ν ήταν και Ν παραμένει. Αν θυμάστε είχα ασκήσει βέτο στο θέμα της εύρεσης των 2 πρώτων από μια λίστα αριθμών επικαλούμενος την αύξηση των συγκρίσεων και άρα την έλλειψη αποδοτικότητας. Αλλά τότε άλλαζε η τάξη του αλγορίθμου από Ν σε Ν^2. Αυτό είναι κάτι πολύ διαφορετικό. Ο διπλασιασμός γίνεται πιο ανώδυνος αν λάβουμε υπόψην ότι σε ένα σχολικό πρόβλημα δε θα υπάρχουν και πολλές συνθήκες. Και 20 να είναι δε βλέπω μεγάλη διαφορά. Ενώ ένας αλγόριθμος εύρεσης 2 μεγαλύτερων έχει ακριβώς την ίδια μορφή ακόμα κι αν πρέπει να ψάξει 1000000 αριθμούς.

Υπάρχουν όμως και περιπτώσεις που ο αλγόριθμος 2 μπορεί να γίνει πιο γρήγορος από τον αλγ1. Ο αλγόριθμος 2 έχει ένα πλεονέκτημα: μπορεί να αλλάξει τη σειρά των ελέγχων. Αν έχουμε την πληροφορία ότι σε κάποιο διάστημα κάπου στη μέση είναι η μεγάλη πλειοψηφία των δειγμάτων μας τότε βολευει να βάλουμε τα συχνά διαστήματα στην αρχή έτσι ώστε η πολλαπλή επιλογή να αποφασίζει με λίγους ελέγχους. Για παράδειγμα ας υποθέσουμε ότι πρέπει να ελέγξουμε το iq μιας ολόκληρης χώρας που παίρνει τιμές από 0 ως 160 και να το κατατάξουμε σε κατηγορίας (διαστήματα πλάτους 5). Έχουμε 32 διαστήματα. Έχουμε επίσης την πληροφορία ότι οι τιμές συσσωρεύονται γύρω από το 80 (κατανομή Gauss με μέση τιμή 80). Έτσι μας βολεύει να βάλουμε τα διαστήματα γύρω από το 80 ψηλά στην πολαπλή επιλογή και όσο κατεβαίνουμε να απομακρυνόμαστε από το 80. Οι τελευταίοι έλεγχοι θα είναι για τα σπάνια διαστήματα [0,5] και [155, 160].
Εδώ ο αλγ 2 αποκτάει σημαντικό πλεονέκτημα στην ταχύτητα.

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

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

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

Στη δυνατότητα χρήσης σε πολύπλοκα προγράμματα τα πράγματα είναι μπερδεμένα. Σε καταστάσεις που τα διαστήματα είναι διατεταγμένα μπορεί ο αλγ 1 να δώσει πιο συμπαγη κώδικα. Κλασσικό περίπτωση είναι στο κεφάλαιο 8 του τετραδίου το παράδειγμα 1 (με τους ρύπους). Για να το λύσεις αυτό με σαφή άκρα πρέπει να κατατάξεις μια κατάσταση ανάλογα με το ρύπο που οδηγεί στο χειρότερο στάδιο.
Πχ για στάδιο λήψης μέτρων Α βαθμίδας η συνθήκη είναι
Αν (ΝΟ2 >500 και ΝΟ2<700 και Ο3 <500) ή (Ο3>300 και Ο3<500 και ΝΟ2<700)
Μπέρδεμα! Αλλά από την άλλη μεριά αν ξέρεις να δίνεις σαφή άκρα παίζοντας με τις συνθήκες μπορείς να λύσεις τα πάντα.

Νομίζω ότι κάθε τεχνική έχει δικό της πεδίο εφαρμογής. Σαν κανόνα όμως θα έλεγα ότι στο χαμηλό επίπεδο του μαθήματος ψηφίζω τον αλγόριθμο 2 γιατί δίνει πιο ευανάγνωστο κώδικα και μικραίνει την πιθανότητα λάθους θυσιάζοντας σε ανεκτό σημείο την ταχύτητα (δεν αλλάζει την τάξη). Νομίζω ότι απαντώ και στο ιδιαίτερα εύστοχο ερώτημα του συνωνόματου George που ρώτησε «πόσο λάθος είναι ο έλεγχος περιττών συνθηκών σε ένα αλγόριθμο». Η απάντηση μου είναι: κυρίως αν δεν αλλάζει η τάξη του αλγορίθμου και δευτερευόντως αν τα δεδομένα δεν είναι πολλά (πχ 20 το πολύ έλεγχοι στο σχολικο μάθημα) επιλέγουμε ευκολία στην εκμάθηση.

Σε πιο προχωρημένο επίπεδο νομιζω ότι διαλέγουμε το πιο γρήγορο, που σημαίνει διαδική αναζήτηση (αν γίνεται), συνυπολογισμό της πιθανότητας να είσαι σε κάποιο διάστημα κλπ

Νομίζω μίλησα αντικειμενικά. Μπορούμε να κουβεντιάσουμε οτιδήποτε.

Φιλικά

xaidi

  • Ομάδα διαγωνισμάτων 2009
  • *
  • Μηνύματα: 111
  • who is WHO!!!!!!
Re: ΔΟΜΗ ΕΠΙΛΟΓΗΣ ΠΕΡΙΟΡΙΣΜΟΙ
« Απάντηση #19 στις: 16 Νοέ 2004, 12:29:33 μμ »
συγνώμη για το λάθος μου για το γένος του gpapargi.  :whip:
Ευχαριστώ,

redhata

  • Θαμώνας
  • ***
  • Μηνύματα: 24
Re: ΔΟΜΗ ΕΠΙΛΟΓΗΣ ΠΕΡΙΟΡΙΣΜΟΙ
« Απάντηση #20 στις: 16 Νοέ 2004, 04:20:27 μμ »
gpapargi
------------
ok, σε συγκεκριμένες εφαρμογές όπου υπάρχει συγκέντρωση τιμών μακριά από τα τελευταία διαστήματα του αλγ1, το πλεονέκτημα του αλγ2 σχετικά με τη δυνατότητα αλλαγής της σειράς των συνθηκών ισχύει.
Εγώ πάντως προτιμώ τον αλγ1, μιας και οι προτινόμενες απαντήσεις στα θέματα των πανελλαδικών είναι στο στιλ του αλγ1. Ειδικά όταν μιλάμε για αλγόριθμο όπου η επιλογή δεν είναι μέσα σε loop ώστε να εκτελείται πολλές φορές και να χρειαστεί να κάνουμε ανάλυση δεδομένων(το γνωστό ΘΕΜΑ3), αναγκαστικά γίνομαι εξετασιοκεντρικός.

xaidi
------
KAI τον gpapargi έκανες female?  ;D

psiotakis
-----------
sorry but the show is over here....   ;)
« Τελευταία τροποποίηση: 16 Νοέ 2004, 10:51:29 μμ από redhata »
rEdHaTa

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

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3176
  • I love you 3000
    • Panagiotis Tsiotakis
Re: ΔΟΜΗ ΕΠΙΛΟΓΗΣ ΠΕΡΙΟΡΙΣΜΟΙ
« Απάντηση #21 στις: 16 Νοέ 2004, 11:40:59 μμ »

Σελίδα 172: Συχνό λάθος που παρατηρείται στα προγράμματα είναι ο έλεγχος περιττών συνθηκών

Κατά τα άλλα πουλάω pop corn με κλιμακωτή χρέωση

Με εκτίμηση,

George

  • Θαμώνας
  • ***
  • Μηνύματα: 41
  • Γράψτε το προσωπικό σας σλόγκαν!
Re: ΔΟΜΗ ΕΠΙΛΟΓΗΣ ΠΕΡΙΟΡΙΣΜΟΙ
« Απάντηση #22 στις: 18 Νοέ 2004, 01:16:45 μμ »
Σελίδα 172: Συχνό λάθος που παρατηρείται στα προγράμματα είναι ο έλεγχος περιττών συνθηκών

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Re: ΔΟΜΗ ΕΠΙΛΟΓΗΣ ΠΕΡΙΟΡΙΣΜΟΙ
« Απάντηση #23 στις: 19 Νοέ 2004, 11:41:08 πμ »
Καλημέρα

Παναγιώτη το βιβλίο συγκρίνει τους 2 αλγορίθμους επιφανειακά. Αυτό που γράφει το αναφέρω στο κείμενό μου μαζί με αρκετά ακόμα πράγματα. Νομίζω ότι μια πλήρη ανάλυση του θέματος περιλαμβάνει τουλάχιστο αυτά που γράφω και ενδεχομένως άλλα που δε σκέφτηκα.

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

Τώρα στο αν πρέπει να κοπούν βαθμοί θα πω τα εξής: Πριν από λίγες μέρες είχαμε κουβεντιάσει το θέμα της εύρεσης των 2 μεγαλύτερων. Σχεδόν όλοι υποστήριξαν την άποψη ότι ο μαθητής μπορεί να λύσει το πρόβλημα με πλήρη ταξινόμηση (αλλαγή τάξης από ν σε ν^2) παρά το ότι υπάρχει τρόπος να λυθεί η άσκηση με 2 σαρώσεις (η γνώση αυτή υπάρχει μέσα στην ύλη του βιβλίου). Είναι δυνατό να κοπούν βαθμοί όταν απλά διπλασιάζεις τους ελέγχους και η τάξη του αλγορίθμου δεν αλλάζει;
Μόνο με διαφορετικά μέτρα και σταθμά γίνεται αυτό!

Πάντως θεωρώ πρόγραμμα και αλγόριθμο το ίδιο όσον αφορά τη φιλοσοφία προγραμματισμού.