Αποστολέας Θέμα: Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς  (Αναγνώστηκε 4497 φορές)

Επισκέπτης

  • Επισκέπτης
Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς
« στις: 15 Μάρ 2006, 10:09:33 μμ »
Το λάθος της Υπερ/υπο-χείλισης αναφέρεται στο βιβλίο μόνο για τη στοίβα.

Το ίδιο δε μπορεί να συμβεί και σε ουρά; (εισαγωγή σε γεμάτη / εξαγωγή από άδεια);;  Γιατί να το περιορίσουμε στη στοίβα;


Λάμπρος Μπουκουβάλας

  • Η παιδεία είναι: στους φτωχούς, ΠΛΟΥΤΟΣ. Στους πλούσιους, ΣΤΟΛΙΔΙ. Στους νέους, ΚΑΙ ΤΑ ΔΥΟ (Διογένης) !
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 1226
    • Το μπλογκάκι μου
Απ: Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς
« Απάντηση #1 στις: 16 Μάρ 2006, 10:44:53 πμ »
η υπερχείλιση αναφέρεται στο βιβλίο σε συνδυασμό με την λειτουργία της μνήμης του υπολογιστή ως στοίβας. έχεις δει σε υπολογιστή το μήνυμα λάθους stack overflow, αλλά δεν έχεις δει το μήνυμα out of queue. Μήπως κάτι σημαίνει αυτό?
Λάμπρος Μπουκουβάλας
MSc - MRes

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται…

filippos

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 139
Απ: Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς
« Απάντηση #2 στις: 16 Μάρ 2006, 12:02:02 μμ »
Η εισαγωγή σε γεμάτη ουρά είναι εξίσου λάθος με την ώθηση σε γεμάτη στοίβα.

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

Γι' αυτό το λόγο γενικά οι αλγόριθμοι που υλοποιούν αυτές τις 4 λειτουργίες οφείλουν να ελέγχουν γι' αυτές τις καταστάσεις.

Έχω όμως την αίσθηση ότι οι όροι υπερχείλιση (overflow) και υποχείλιση (underflow) χρησιμοποιούνται μόνο σε στοίβα και όχι σε ουρά.  Δεν είμαι όμως και απόλυτα σίγουρος.

Οι υπόλοιποι τι λέτε;

Θα μπορούσε να τεθεί ερώτηση Σωστό/Λάθος με τη μορφή:
1. η εξαγωγή από κενή ουρά προκαλεί υποχείλιση
ή / και
2. η εισαγωγή σε γεμάτη ουρά προκαλεί υπερχείλιση

Τι πρέπει να απαντήσουν οι μαθητές

andreas_p

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 1014
Απ: Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς
« Απάντηση #3 στις: 16 Μάρ 2006, 12:06:19 μμ »
Δε νομίζω να πέσει τέτοια ερώτηση. Αν πέσει  θα πρέπει να λάβουμε κάθε απάντηση ως Σωστή.

Λάμπρος Μπουκουβάλας

  • Η παιδεία είναι: στους φτωχούς, ΠΛΟΥΤΟΣ. Στους πλούσιους, ΣΤΟΛΙΔΙ. Στους νέους, ΚΑΙ ΤΑ ΔΥΟ (Διογένης) !
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 1226
    • Το μπλογκάκι μου
Απ: Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς
« Απάντηση #4 στις: 16 Μάρ 2006, 12:59:59 μμ »
o filippos έχει δίκιο. οι έννοιες υπερχείλιση και υποχείλιση ισχύουν μόνο για στοίβα. κατά τη γνώμη μου η απάντηση στην ερώτησή σου είναι ΛΑΘΟΣ. δεν αναφέρει το βιβλίο τις αντίστοιχες λειτουργίες της ουράς.
Λάμπρος Μπουκουβάλας
MSc - MRes

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται…

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς
« Απάντηση #5 στις: 16 Μάρ 2006, 04:29:26 μμ »

   Το ότι δεν αναφέρει το βιβλίο τo underflow/overflow ουράς δε σημαίνει ότι δεν υπάρχει. Αφού μιλάμε για έναν πίνακα με περιορισμένο αριθμό θέσεων είναι προφανές ότι στις οριακές περιπτώσεις συμβαίνει ότι και στη στοίβα.
    Ο λόγος που το βιβλίο αναφέρει μόνο τη στοίβα είναι ότι η δομή αυτή χρησιμοποιείται αρκετά από τα λειτουργικα συστήματα και από τις γλώσσες προγραμματισμού όπως για παράδειγμα στη μεταβίβαση παραμέτρων όπου το σχολικό βιβλίο αφιερώνει μια σελίδα στη στοίβα.
     Μπορείτε να ρίξετε μια ματιά σε οποιοδήποτε σοβαρό βιβλίο για δομές δεδομένων ή ακόμα και στη σχετική σελίδα της wikipedia
http://en.wikipedia.org/wiki/Queue
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Επισκέπτης

  • Επισκέπτης
Απ: Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς
« Απάντηση #6 στις: 16 Μάρ 2006, 04:53:41 μμ »
@Evry: Το θέμα δεν είναι κατά πόσον είναι λάθος η εισαγωγή σε γεμάτη ουρά ή η εξαγωγή από άδεια.  Σε αυτό νομίζω συμφωνούμε όλοι. 

Το θέμα είναι κατά πόσον είναι δόκιμος ο όρος υπερ/υπο-χείλιση (οver/under-flow) στις ουρές.  Το βιβλίο αναφέρει τους όρους μόνο στη στοίβα, και η δική μου αίσθηση είναι επίσης ότι το πρόβλημα περιγράφεται μεν ως stack overflow error στις στοίβες αλλά ως queue full error στις ουρές. 

Αν λοιπόν θυμάμαι καλά, ο υπο συζήτηση όρος αφορά μόνο τη στοίβα

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς
« Απάντηση #7 στις: 16 Μάρ 2006, 06:14:24 μμ »
Πάντως για να λέει το παρακάτω στο wikipedia (όχι ότι το θεωρώ και ευαγγέλιο) κάτι θα ξέρει

A practical implementation of a queue of course does have some capacity limit, that depends on the concrete situation it is used in. For a data structure the executing computer will eventually run out of memory, thus limiting the queue size. Queue overflow results from trying to add an element onto a full queue and queue underflow happens when trying to remove an element from an empty queue

Επίσης αν βάλεις "queue overflow in data structures" στο google θα βγουν αρκετές σελίδες του μαθήματος δομών δεδομένων σε πολλά πανεπιστήμια. Οπότε ο όρος χρησιμοποιείται από αρκετούς. Ίσως κάποιοι να προτιμουν κάποιον άλλο όρο για την ουρά για να μην γίνεται σύγχυση με τη στοίβα αλλά το queue overflow δε νομίζω ότι είναι λάθος.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

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

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3174
  • I love you 3000
    • Panagiotis Tsiotakis
Απ: Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς
« Απάντηση #8 στις: 17 Μάρ 2006, 10:34:56 πμ »

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

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

Με εκτίμηση,