ΟΥΡΑ-ΣΤΟΙΒΑ

Ξεκίνησε από tkon, 04 Μαρ 2008, 01:23:12 ΜΜ

« προηγούμενο - επόμενο »

tkon

ΘΑ ΗΘΕΛΑ ΝΑ ΔΩΣΕΙ ΚΑΠΟΙΟΣ ΜΙΑ ΣΩΣΤΗ ΑΠΑΝΤΗΣΗ ΣΤΙΣ ΠΑΡΑΚΑΤΩ ΕΡΩΤΗΣΕΙΣ:
1) Η ΣΤΟΙΒΑ ΚΑΙ Η ΟΥΡΑ ΤΕΛΙΚΑ ΕΙΝΑΙ ΣΤΑΤΙΚΗ Ή ΔΥΝΑΜΙΚΗ ΔΟΜΗ ΔΕΔΟΜΕΝΩΝ;
2) Η ΣΥΝΤΑΞΗ ΤΟΥ ΠΑΡΑΚΑΤΩ ΤΜΗΜΑΤΟΣ ΣΤΟ ΠΡΟΓΡΑΜΜΑΤΟΣ ΕΙΝΑΙ ΣΩΣΤΗ;
ΠΡΟΓΡΑΜΜΑ Α1
ΜΕΤΑΒΛΗΤΕΣ
   ΑΚΕΡΑΙΕΣ:Χ,Π[20]
   ΠΡΑΓΜΑΤΙΚΕΣ:
   ΛΟΓΙΚΕΣ:ΒΡΕΘΗΚΕ
   ΧΑΡΑΚΤΗΡΕΣ:Χ[20]

ΑΝ ΔΗΛΑΔΗ ΔΕΝ ΕΧΩ  ΠΡΑΓΜΑΤΙΚΕΣ ΜΕΤΑΒΛΗΤΕΣ, ΑΛΛΑ ΤΙΣ ΔΗΛΩΣΩ ΣΤΟ ΠΡΟΓΡΑΜΜΑ ΟΠΩΣ ΠΑΡΑΠΑΝΩ ΕΙΝΑΙ ΣΩΣΤΟ;

3) ΥΠΑΡΧΕΙ ΠΕΡΙΠΤΩΣΗ ΝΑ ΠΕΣΕΙ ΣΕ ΑΣΚΗΣΗ ΣΕΙΡΙΑΚΗ ΣΕ ΤΑΞΙΜΟΜΗΜΕΝΟ ΠΙΝΑΚΑ;
ΠΕΡΙΜΕΝΩ ΑΠΑΝΤΗΣΗ
ΕΥΧΑΡΙΣΤΩ

P.Tsiotakis

1. Η στοίβα και η ουρά, όπως υλοποιούνται στο διδακτικό μας πακέτο είναι ΣΤΑΤΙΚΕΣ δομές δεδομένων. Αλλιώς τι νόημα έχει η υπερχείλιση;  ::)

2. Δεν μπορεί να υπάρχει πίνακας και μεταβλητή με το ίδιο όνομα (αυτό δεν εννοούσες;). Το να υπάρχει η δήλωση ΠΡΑΓΜΑΤΙΚΕΣ και καμία μεταβλητή να ακολουθεί, δεν θα το χαρακτήριζα λάθος, αλλά μάλλον δεν θα υπάρχει σε γραπτό μαθητή. (Τυπογραφικό)

3. ΜΑΚΑΡΙ. Το τέλειο ερώτημα κρίσεως: περιγράφεται στο βιβλίο αλλά δεν παρουσιάζεται ο αλγόριθμος. Όχι σε άσκηση (που μπορείς να γράψει την κλασική σειριακή, αλλά σαν θεωρία)

alkisg

Το (2) εγώ θα το χαρακτήριζα συντακτικό λάθος. Σε ΓΛΩΣΣΑ είμαστε, υπάρχουν αυστηροί κανόνες.
Τώρα αν δεν αναφέρεται ρητώς στο βιβλίο... ε, τι να κάνουμε, δεν είναι το μόνο.

andreas_p

Καλημέρα σας.

1)   Στατικές

2)  Λάθος

3)  Το περιμένουμε ... χρόνια τώρα  (θέμα  θεϊκό)


Ανδρέας

bagelis

1) Διφορούμενο, ΔΕΝ ΠΡΕΠΕΙ ΝΑ ΜΠΕΙ ΣΕ ΕΞΕΤΑΣΕΙΣ
Παλιότερα είχε γίνει μια ολόκληρη κουβέντα για αυτό!!!!

2) Λάθος, λόγω του Χ

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

Stavros

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

Για το 3 αν και δεν έχει γίνει εμένα προσοπικά δεν θα με πείραζε να υπήρχε μία τέτοια άσκηση
Stavros
3ετής φοιτητής πληροφορικής


Το νέο φοιτητικό site
www.universitas.gr
www.csforces.gr/forums
All about computers!!!
Join us!!!!

evry


   Δεν κατάλαβα γιατί θεωρούμε τη στοίβα στατική δομή. Αν υποθέσουμε ότι έχουμε σε μια στοίβα 3 στοιχεία, το μέγεθός της είναι 3 και όχι το μέγεθος του πίνακα στον οποίο αποθηκεύεται. Η στοίβα και η ουρά είναι δομές στις οποίες μπορούμε να προσθέτουμε και να αφαιρούμε στοιχεία, άρα είναι δυναμικές και όχι στατικές.
   Τώρα το αν υλοποιούνται με πίνακα ή με συνδεδεμένη λίστα δεν μας ενδιαφέρει. Αυτή άλλωστε είναι και η ιδέα των αφηρημένων δομών δεδομένων, δεν πρέπει να βλέπουμε την υλοποίηση αλλά μόνο τη διεπαφή (interface). Δηλαδή δε μπορούμε να διαχωρίζουμε τη στοίβα που υλοποιείται με πίνακα και αυτή που υλοποιείται με συνδεδεμένη λίστα. Αυτό που πρέπει να βλέπουμε είναι μόνο τη δομή και τις βασικές λειτουργίες της, άσε που η υλοποίηση είναι εκτός ύλης. Αλλά όπως και να έχει ακόμα και με πίνακες πάλι μπορείς να υλοποίησεις μια δυναμική δομή. Οι δομές δεδομένων στην STL της C++ και στην Java έχω την εντύπωση ότι υλοποιούνται με πίνακες απλά όταν δεν υπάρχει άλλη διαθέσιμη θέση στον πίνακα, τότε ο πίνακας επεκτείνεται κατά κάποιες θέσεις (βλέπε dynamic arrays)
  Τώρα σχετικά με την υπερχείλιση που είπε ο Παναγιώτης (η οποία κατά τη γνώμη μου κακώς είναι στην ύλη αφού η υλοποίηση της στοίβας είναι εκτός) αυτή μπορεί να συμβεί και όταν υλοποιήσεις τη στοίβα με συνδεδεμένη λίστα και δεν υπάρχει αρκετή μνήμη. Και τότε υπερχείλιση έχεις, αλλά δεν πρόκειται για στατική δομή. Ακόμα και η συνδεδεμένη λίστα είναι περιορισμένη από την μνήμη του υπολογιστή η οποία μπορεί να θεωρηθεί σαν ένας τεράστιος πίνακας.
    Η γνώμη μου είναι πως όταν αναφερόμαστε σε τέτοιες δομές δεδομένων δεν πρέπει να σκεφτόμαστε την υλοποίηση αλλά μόνο τις βασικές λειτουργίες τους και να τις βλέπουμε σαν Αφηρημένες Δομές (ή Τύπους) Δεδομένων.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

P.Tsiotakis

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

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

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


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

evry

Κατά τη γνώμη μου θα πρέπει να εξετάζουμε τις αφηρημένες λειτουργίες των δομών και όχι το πως υλοποιούνται, αυτό είναι το πνεύμα των δομών δεδομένων και της έννοιας του Αφηρημένου Τύπου Δεδομένων (ΑΔΤ), σαν μην βλέπουμε την υλοποίηση. Επίσης κάτι άλλο, τα δέντρα και οι γράφοι είναι στατικές ή δυναμικές δομές δεδομένων? Ας πούμε ότι υλοποιούνται με πίνακες. Μπορείς να αφαιρέσεις κάλλιστα μια ακμή θέτοντας 0 στο αντίστοιχο κελί. Αυτό δε σημαίνει ότι είναι δυναμική δομή; (αφού μπορείς σε χρόνο εκτέλεσης να αλλάξεις τη δομή του γράφου, δηλαδή να αλλάξεις τη δομή δυναμικά άρα μιλάμε για δυναμική δομή).
   Αυτό στο οποίο θέλω να καταλήξω είναι όπως είπα και πριν ότι πρέπει να εξετάζουμε μόνο τις βασικές λειτουργίες των δομών και να τις βλέπουμε σαν Αφηρημένους Τύπους Δεδομένων. Η υλοποίηση δεν παίζει ρόλο για το αν αναφέρομαστε σε στατικές ή δυναμικές δομές δεδομένων.
    Αν δεχτούμε ότι οι δομές που υλοποιούνται με πίνακα είναι στατικές τότε θα πρέπει να δεχτούμε ότι αφού η μνήμη του υπολογιστή είναι πεπερασμένη, και πρόκειται ουσιαστικά για έναν μονοδιάστατο πίνακα όλες οι δομές δεδομένων είναι στατικές, αφού όλες χρησιμοποιούν τμήματα αυτού του μονοδιάστατου πίνακα. Επίσης δεν εξετάζω τόσο πολύ το πνεύμα του βιβλίου γιατί σε πολλές περιπτώσεις αυτό έχει αποδειχθεί ότι δεν είναι αξιόπιστο (βλέπε αποτελεσματικότητα). Επειδή πάντως δε νομίζω ότι θα συμφωνήσουμε με τον Παναγιώτη (μάλλον είμαστε στα δυο άκρα :-)) μήπως να το βάλουμε σε ψηφοφορία? Έχει κανείς καμιά άλλη άποψη?
    Πιστεύω ότι η συγκεκριμένη συζήτηση και η διαφωνία μας έχει σημασία από την πλευρά ότι πολλοί μαθητές είναι επίσης δύσπιστοι για το αν οι δομές αυτές είναι στατικές ή δυναμικές, οπότε θα πρέπει να βρούμε καλά επιχειρήματα για να τους πείσουμε για το δίκιο της μιας ή της άλλης άποψης.

  Επίσης οι δυναμικές δομές δεδομένων δε νομίζω ότι είναι εκτός ύλης, αφού στο κεφάλαιο 3 οι διαφορές στατικών και δυναμικών δομών δεδομένων είναι εντός ύλης. Οι δυναμικές δομές δεδομένων γενικά είναι στην ύλη και μπορεί να πέσει στις πανελλήνιες ερώτηση θεωρίας για το τι είναι ή ποιες είναι οι διαφορές τους από τις στατικές δομές. Το πως υλοποιούνται οι δυναμικές δομές είναι εκτός ύλης (αυτό φαντάζομαι ότι εννοείς Παναγιώτη) αλλά η έννοια της δυναμικής δομής δεδομένων είναι μέσα στην ύλη. Και αν θέλεις να εξηγήσεις στα παιδιά με ένα παράδειγμα τι σημαίνει δυναμική δομή δεδομένων, το μόνο εργαλείο που έχεις στα χέρια σου είναι η στοίβα και η ουρά.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

P.Tsiotakis

Όταν η εκφώνηση ξεκινάει με τη διατύπωση: "έστω μια στοίβα 10 θέσεων...", τότε δεν μπορεί να αναφέρεται σε δυναμική δομή δεδομένων.

Η τεχνική της δυναμικής παραχώρησης μνήμης είναι η αύξηση του δείκτη top κατά 1 στη στοίβα;

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

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

evry

#10
Η ιδέα του Αφηρημένου Τύπου Δεδομένων είναι η ανεξαρτησία από την υλοποίηση. Ο αφηρημένος τύπος Στοίβα/Ουρά σε αφηρημένο επίπεδο είναι ή στατικός ή δυναμικός, όχι και τα δυο, και σίγουρα όχι με βάση την υλοποίηση. Η εκφώνηση "έστω μια στοίβα 10 θέσεων" ουσιαστικά σου αποκαλύπτει την υλοποίηση της στοίβας η οποία αν δεν κάνω λάθος είναι και εκτός ύλης.

   Φυσικά και στο μάθημά μας δεν υπάρχει παρουσίαση δυναμικής δομής δεδομένων, εδώ συμφωνούμε απόλυτα. Το ερώτημα είναι πως από την στιγμή που δεν υπάρχει μια δυναμική δεδομένων να επικαλεστείς σαν παράδειγμα πως θα εξηγήσεις στα παιδιά τις διαφορές μεταξύ δυναμικών και στατικών δομών οι οποίες είναι εντός ύλης;
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

P.Tsiotakis

Η εκφώνηση "Σε ΅ία ουρά 10 θέσεων έχουν τοποθετηθεί..."
αφορά το θέμα 1Β των εξετάσεων εσπερινών λυκείων 2004
(http://users.kor.sch.gr/ptsiotakis/aepp/aepp_panel_esp_2004.htm ).

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

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

potato

   evry, για το αν θα χαρακτηρίσεις έναν ΑΤΔ δυναμικό ή στατικό εξαρτάται από την υλοποιήση. Λέμε ότι ένας ADT είναι ανεξάρτητος της implementation και των specifications της γλώσσας που υλοποιείται, εξαιτίας του χειρισμού του που γίνεται από το interface του και μόνο(η λειτουργία παραμένει ίδια). Αλλά ερώτηση που αφορά χαρακτηριστικά όπως δυναμική ή όχι είναι θέμα υλοποιήσης. Είναι σαν να ρωτάς αν ένας κώδικας είναι ασφαλής ή όχι, είναι και αυτό θέμα υλοιποιήσης ανεξάρτητα από το αν 2 ΑΤΔ έχουν τις ίδιες πράξεις.

  Επομένως, δεν υπάρχει μία απάντηση. Οι μαθητές του Λυκείου μπορούν να απαντήσουν μόνο στατική. Γενικότερα.. απλά εξαρτάται..
Be open source. Knowledge belongs to the world.

evry


Οι πίνακες είναι στατική δομή δεδομένων? 

What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

papaluk

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