Αποστολέας Θέμα: Υλοποίηση ουράς  (Αναγνώστηκε 532 φορές)

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2466
  • I 'm not young enough to know everything
Υλοποίηση ουράς
« στις: 21 Απρ 2021, 11:36:06 πμ »
Έχω μεγάλο πρόβλημα στο πως να διδάξω την υλοποίηση της ουράς. Αυτό που έχει μέσα το βιβλίο είναι προφανώς λάθος αφού τα στοιχεία είναι μονής χρήσεως σε κάποιες περιπτώσεις. Θα ήταν πολύ καλύτερη μια κυκλική υλοποίηση με mod ή και με "Αν" έστω και αν έφτιαχνα ένα υποπρόγραμμα που έπαιρνε την τρέχουσα τιμή του δείκτη και μου γύριζε την επόμενη (και μέσα έκρυβα το πως βρίσκω την επόμενη τιμή).
Το θέμα είναι τι διδάσκω. Δυσκολεύομαι να διδάξω κάτι που ξέρω ότι είναι λάθος. Από την άλλη φοβάμαι να διδάξω και το σωστό γιατί υπάρχουν και οι πανελλήνιες. Έχει κανείς απάντηση;

andreas_p

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 1085
Απ: Υλοποίηση ουράς
« Απάντηση #1 στις: 21 Απρ 2021, 12:56:48 μμ »
Διδάσκουμε την ουρά  , ΟΧΙ κυκλικά , αλλά σειριακά. (Σε περίπτωση ολίσθησης)

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2466
  • I 'm not young enough to know everything
Απ: Υλοποίηση ουράς
« Απάντηση #2 στις: 21 Απρ 2021, 01:27:47 μμ »
Από ότι είδα η ουρά με ολίσθηση χρησιμοποιείται στο συμπληρωματικό υλικό. Είναι μια λύση με κακή ποπλυπλοκότητα (αλλοιώνει την αλγοριθμική τάξη), αλλά όχι λάθος. Η υλοποίηση ουράς μονής χρήσεως είναι λάθος. Προτιμώ την ολίσθηση (με βαριά καρδιά). Καλύτερα ορθός και κακός παρά λανθασμένος. Σαν να κάνει εύρεση μεγίστου με πλήρη ταξινόμηση. Ε ρε που μπλέξαμε...  :-\

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6011
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Υλοποίηση ουράς
« Απάντηση #3 στις: 21 Απρ 2021, 05:32:00 μμ »
Τα ίδια παράπονα είχα κάνει κι εγώ σε παλιότερο θέμα: https://alkisg.mysch.gr/steki/index.php?topic=8149.0

Εντωμεταξύ, τα τετράδια μαθητή, ενδεικτικές λύσεις ασκήσεων κλπ, ΔΕΝ θεωρούνται ως εξεταστέα ύλη, σωστά; Η ολίσθηση υπάρχει μόνο στην λύση της άσκησης με το ταχυδρομείο, δεν αναφέρεται αλλού.

Νομίζω ότι το καλύτερο θα είναι:
  • Η επιτροπή να μην βάλει φέτος άσκηση με ολίσθηση.
  • Για του χρόνου, η ενδεικτική λύση της άσκησης με το ταχυδρομείο να αλλάξει ώστε να γίνει επιστημονικά σωστή, Εισαγωγή = Ο(1). Είτε ΑΝ είτε mod, όχι ΓΙΑ. Για ποιο λόγο να κάνει κανείς επανάληψη όταν δεν χρειάζεται?!
  • Προς το παρόν για τους διδάσκοντες και τους μαθητές, μάλλον ισχύει η λογική του στρατού... "εκτελώ τη διαταγή αλλά υποβάλλω αναφορά με τις αντιρρήσεις μου". Λέμε στους μαθητές τι γράφει το διδακτικό πακέτο, κι ας παραπονιόμαστε γι' αυτό.
  • Αν τώρα γίνει η στραβή και μπει τέτοιο θέμα, θα πρέπει οι βαθμολογητές να δεχτούν οπωσδήποτε ως σωστή μια κυκλική λύση, προστατεύοντας τους "υπερβολικά καλούς" μαθητές.

ApoAntonis

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 156
Απ: Υλοποίηση ουράς
« Απάντηση #4 στις: 21 Απρ 2021, 09:20:01 μμ »
Εντωμεταξύ, τα τετράδια μαθητή, ενδεικτικές λύσεις ασκήσεων κλπ, ΔΕΝ θεωρούνται ως εξεταστέα ύλη, σωστά;

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

Η ολίσθηση υπάρχει μόνο στην λύση της άσκησης με το ταχυδρομείο, δεν αναφέρεται αλλού.

ΠΙΑΣΤΟ ΤΟ ΑΒΓΟ ΚΑΙ ΚΟΥΡΕΥΤΟ:
(από τις οδηγίες)

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


Τι σημαίνει "να παρουσιαστεί"; Εγώ το καταλαβαίνω ότι ανήκει στην διδακτέα.

George Eco

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 468
Απ: Υλοποίηση ουράς
« Απάντηση #5 στις: 22 Απρ 2021, 01:51:39 μμ »
Αν τώρα γίνει η στραβή και μπει τέτοιο θέμα, θα πρέπει οι βαθμολογητές να δεχτούν οπωσδήποτε ως σωστή μια κυκλική λύση, προστατεύοντας τους "υπερβολικά καλούς" μαθητές
Συμφωνώ απόλυτα.
Αλλά αυτό ΔΕ συνέβη το 2018. Θέλω να πω το 2018 αν στο Β2 έλεγες πως είναι αδύνατο να υλοποιηθεί τμήμα προγράμματος σε ΓΛΩΣΣΑ που να εκτελεί ακριβώς την ίδια ακολουθία εντολών (βημάτων) με το αδόμητο διάγραμμα ροής, θα υπήρχαν εξεταστές που θα μηδένιζαν το θέμα αντί να δώσουν άριστα. Κι όμως, ένα παιδί που θα έλεγε αυτό και θα επεξηγούσε την απαίτηση να υπάρχει GOTO, αλλά λόγω απουσίας της στη ΓΛΩΣΣΑ δε γίνεται το αδόμητο να υλοποιηθεί ΑΚΡΙΒΩΣ, καταλήγουμε σε μεγάλη αδικία.

Ας αποφύγουν επίμαχα σημεία.


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



thaaanos

  • Βετεράνος
  • ****
  • Μηνύματα: 52
Απ: Υλοποίηση ουράς
« Απάντηση #6 στις: 11 Μαΐ 2021, 02:03:34 μμ »
Ύστερα από αρκετή σκέψη κατέληξα οτι η ολίσθηση δεν είναι και "τόσο κακή" αρκεί να γίνεται μόνο όποτε χρειάζεται όταν πχ ο δείκτης rear φτάσει στο max και ο front>1 και όχι σε κάθε απώθηση που αλλοιώνει την πολυπλοκότητα.
Δεν είναι εξάλλου λίγες οι δομές που αναδιάτασουν τα δεδομένα τους η προβαίνουν σε εργασίες "συντήρησης" όποτε χρειαστεί.
Θα μπορούσε κάποιος να πεί οτι είναι ένα είδος garbage collection.

Για μένα η μέγαλύτερη χαζομάρα είναι η
Α) Η αρχικοποιηση στο (f,r)=(0,0) με αποτέλεσμα την ανάγκη έξτρα συνθήκης στην μετάβαση από και πρός κενη ουρά, αν αρχικοποιουνταν οι δείκτες στο  (f,r)=(1,0) θα ήταν πίο απλός ο αλγόριθμος εισαγωγής και εξαγωγής.

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

Η κύκλική ουρά όσες φορές και αν την έδειξα μάλλον μάταιος κόπος.

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6011
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Υλοποίηση ουράς
« Απάντηση #7 στις: 11 Μαΐ 2021, 02:57:35 μμ »
Ύστερα από αρκετή σκέψη κατέληξα οτι η ολίσθηση δεν είναι και "τόσο κακή" αρκεί να γίνεται μόνο όποτε χρειάζεται όταν πχ ο δείκτης rear φτάσει στο max και ο front>1 και όχι σε κάθε απώθηση που αλλοιώνει την πολυπλοκότητα.

Η εισαγωγή από Ο(1) γίνεται Ο(Ν). Συνήθως μετράμε το worst case complexity, όχι το average:

...one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity,...

Για την κυκλική, δεν είναι απαραίτητο να χρησιμοποιηθεί mod, γίνεται και με ΑΝ, π.χ. "Αν δείκτης < Ν, τότε δείκτης <- Ν+1, αλλιώς δείκτης <- 1`. Δηλαδή καταλαβαίνουν την ευκλείδεια διαίρεση και όχι μια τέτοια ΑΝ;

thaaanos

  • Βετεράνος
  • ****
  • Μηνύματα: 52
Απ: Υλοποίηση ουράς
« Απάντηση #8 στις: 11 Μαΐ 2021, 03:10:56 μμ »
Η εισαγωγή από Ο(1) γίνεται Ο(Ν). Συνήθως μετράμε το worst case complexity, όχι το average:

Για την κυκλική, δεν είναι απαραίτητο να χρησιμοποιηθεί mod, γίνεται και με ΑΝ, π.χ. "Αν δείκτης < Ν, τότε δείκτης <- Ν+1, αλλιώς δείκτης <- 1`. Δηλαδή καταλαβαίνουν την ευκλείδεια διαίρεση και όχι μια τέτοια ΑΝ;
Η εισαγωγή από Ο(1) γίνεται Ο(Ν). Συνήθως μετράμε το worst case complexity, όχι το average:
Νομίζω οτι στις πράξεις των δομών πάμε με amortized ανάλυση