Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Γ΄ Λυκείου => Δομές δεδομένων => Μήνυμα ξεκίνησε από: gpapargi στις 21 Απρ 2021, 11:36:06 πμ

Τίτλος: Υλοποίηση ουράς
Αποστολή από: gpapargi στις 21 Απρ 2021, 11:36:06 πμ
Έχω μεγάλο πρόβλημα στο πως να διδάξω την υλοποίηση της ουράς. Αυτό που έχει μέσα το βιβλίο είναι προφανώς λάθος αφού τα στοιχεία είναι μονής χρήσεως σε κάποιες περιπτώσεις. Θα ήταν πολύ καλύτερη μια κυκλική υλοποίηση με mod ή και με "Αν" έστω και αν έφτιαχνα ένα υποπρόγραμμα που έπαιρνε την τρέχουσα τιμή του δείκτη και μου γύριζε την επόμενη (και μέσα έκρυβα το πως βρίσκω την επόμενη τιμή).
Το θέμα είναι τι διδάσκω. Δυσκολεύομαι να διδάξω κάτι που ξέρω ότι είναι λάθος. Από την άλλη φοβάμαι να διδάξω και το σωστό γιατί υπάρχουν και οι πανελλήνιες. Έχει κανείς απάντηση;
Τίτλος: Απ: Υλοποίηση ουράς
Αποστολή από: andreas_p στις 21 Απρ 2021, 12:56:48 μμ
Διδάσκουμε την ουρά  , ΟΧΙ κυκλικά , αλλά σειριακά. (Σε περίπτωση ολίσθησης)
Τίτλος: Απ: Υλοποίηση ουράς
Αποστολή από: gpapargi στις 21 Απρ 2021, 01:27:47 μμ
Από ότι είδα η ουρά με ολίσθηση χρησιμοποιείται στο συμπληρωματικό υλικό. Είναι μια λύση με κακή ποπλυπλοκότητα (αλλοιώνει την αλγοριθμική τάξη), αλλά όχι λάθος. Η υλοποίηση ουράς μονής χρήσεως είναι λάθος. Προτιμώ την ολίσθηση (με βαριά καρδιά). Καλύτερα ορθός και κακός παρά λανθασμένος. Σαν να κάνει εύρεση μεγίστου με πλήρη ταξινόμηση. Ε ρε που μπλέξαμε...  :-\
Τίτλος: Απ: Υλοποίηση ουράς
Αποστολή από: alkisg στις 21 Απρ 2021, 05:32:00 μμ
Τα ίδια παράπονα είχα κάνει κι εγώ σε παλιότερο θέμα: https://alkisg.mysch.gr/steki/index.php?topic=8149.0

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

Νομίζω ότι το καλύτερο θα είναι:
Τίτλος: Απ: Υλοποίηση ουράς
Αποστολή από: ApoAntonis στις 21 Απρ 2021, 09:20:01 μμ
Εντωμεταξύ, τα τετράδια μαθητή, ενδεικτικές λύσεις ασκήσεων κλπ, ΔΕΝ θεωρούνται ως εξεταστέα ύλη, σωστά;

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

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

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

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


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

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


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


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

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

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

Η κύκλική ουρά όσες φορές και αν την έδειξα μάλλον μάταιος κόπος.
Τίτλος: Απ: Υλοποίηση ουράς
Αποστολή από: alkisg στις 11 Μαΐ 2021, 02:57:35 μμ
Ύστερα από αρκετή σκέψη κατέληξα οτι η ολίσθηση δεν είναι και "τόσο κακή" αρκεί να γίνεται μόνο όποτε χρειάζεται όταν πχ ο δείκτης rear φτάσει στο max και ο front>1 και όχι σε κάθε απώθηση που αλλοιώνει την πολυπλοκότητα.

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

Παράθεση από: https://en.wikipedia.org/wiki/Time_complexity
...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 στις 11 Μαΐ 2021, 03:10:56 μμ
Η εισαγωγή από Ο(1) γίνεται Ο(Ν). Συνήθως μετράμε το worst case complexity, όχι το average:

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