Δυναμική δομή δεδομένων

Ξεκίνησε από xara_pap, 07 Μαρ 2011, 02:51:39 ΠΜ

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

xara_pap

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

odysseas

Παράθεση από: xara_pap στις 07 Μαρ 2011, 02:51:39 ΠΜ
Θα ήθελα να ρωτήσω αν τα παιδιά πρέπει να γνωρίζουν κάποια δυναμική δομή δεδομένων μίας και το βιβλίο δεν αναφέρει κάτι.

Αναφέρει τη στοίβα και την ουρά, οι οποίες είναι δυναμικές.

P.Tsiotakis

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

Νίκος Αδαμόπουλος

Παράθεση από: odysseas στις 07 Μαρ 2011, 09:56:12 ΠΜ
Αναφέρει τη στοίβα και την ουρά, οι οποίες είναι δυναμικές.

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

evry

#4
Νομίζω ότι δεν μπορούμε να ξεχάσουμε τα λίγα που μάθαμε στο πανεπιστήμιο επειδή το βιβλίο αφήνει κάπου να εννοηθεί πως η στοίβα και η ουρά είναι στατικές δομές. Αν το αναφέρει αυτό τότε το βιβλίο είναι λάθος και πρέπει να διορθωθεί.
Όταν μιλάμε για Στοίβα και Ουρά μιλάμε για Αφηρημένους Τύπους Δεδομένων. Δηλαδή δεν μας ενδιαφέρει πως υλοποιούνται από πίσω. Εμείς απλά χρησιμοποιούμε την διεπαφή Ώθηση/Απώθηση. Δεν γνωρίζουμε αν από πίσω υπάρχει πίνακας ή λίστα.
Από τη στιγμή που έχουμε μια δομή στην οποία αφαιρούμε/προσθέτουμε κόμβους τότε προφανώς μιλάμε για δυναμική δομή.
(Εφόσον ο ορισμός της δυναμικής δομής είναι η δομή στην οποία μπορούμε να προσθέτουμε και να αφαιρούμε αντικείμενα)

Αν πάλι παρουσιάζουμε στα παιδιά έναν πίνακα και τους λέμε ότι αυτό είναι στοίβα φοβάμαι ότι δεν μπορούμε να απαντήσουμε στην ερώτηση του μαθητή "Γιατί τότε να μην χρησιμοποιώ κατευθείαν τον πίνακα όπως θέλω εγώ, η ώθηση και η απώθηση με μπερδεύουν". Εκεί φυσικά απαντάμε "εε ξέρεις η υλοποίηση είναι εκτός ύλης, αυτά είναι μόνο στη θεωρία", δηλαδή με λίγα λόγια η υλοποίηση της θεωρίας είναι εκτός ύλης αλλά η θεωρία της υλοποίησης είναι εντός!!!.

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

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

alkisg

Η στοίβα στις αρχιτεκτονικές επεξεργαστών που ξέρω είναι στατική, π.χ. δεν επιτρέπεται να καλέσεις αναδρομικά μια συνάρτηση περισσότερες από Ν φορές, θα έχεις stack overflow.
Η στοίβα πιάτων επίσης είναι στατική, μέγιστος χώρος είναι το ταβάνι.
Στοίβες και ουρές μπορούν να υλοποιηθούν και με στατικό και με δυναμικό τρόπο.
Νομίζω όμως ότι οι δύο αυτές δομές αποτελούν διαφορετικά διδακτικά αντικείμενα από τους τρόπους δέσμευσης μνήμης, οι οποίοι συμπεριλαμβάνουν κι άλλες δομές από πίσω τους (πίνακες, λίστες κτλ). Για να μιλήσουμε για δυναμικές δομές χρειάζεται κατ' ελάχιστο να αναφέρουμε τι σημαίνει δυναμική δέσμευση μνήμης...

xara_pap

Νομίζω οι απαντήσεις ξέφυγαν λίγο. Σχετικά με τη στοίβα και την ουρά μας αναφέρει οτι υλοποιούνται με πίνακα μέσα στην ύλη άρα το παρουσιάζουμε σαν στατική δομή. Τώρα αν εμένα με ρωτήσει κάποιος ποια δυναμική δομή δεδομένων γνωρίζουμε τι πρέπει να απαντήσω?
Εμπλέκεται πουθενά σε όλα αυτά το αρχείο ή η εγγραφή? Γιατί κάτι νομίζω εχει πάρει το μάτι μου σε βοήθημα.
Ευχαριστώ

pgrontas

#7
Το γεγονός ότι το συγκεκριμένο θέμα επανέρχεται τόσες φορές, είναι ενδεικτικό του ό,τι στο βιβλίο τα κάνανε σαλάτα. Και πώς να μην γίνει αυτό εφόσον το Κεφ. 3 είναι σε πολλά σημεία, copy - paste από το αντίστοιχο βιβλίο Δομών Δεδομένων του Μανωλόπουλου (ένα ροζ για να σας θυμήσω και τα χρόνια σας στο πανεπιστήμιο - όσοι το κάνατε). Αποδεικνύεται λοιπόν ότι δεν υπάρχει συνοχή (πόσο μάλλον παιδαγωγικός σχεδιασμός) και κατά συνέπεια δεν πρέπει να το εκλαμβάνουμε ως ευαγγέλιο.
Τέλος πάντων, η θέση που έχω καταλήξει μετά από πολλή σκέψη εκφράζεται καλύτερα από το:
Παράθεση από: evry στις 07 Μαρ 2011, 01:37:53 ΜΜ
Όταν μιλάμε για Στοίβα και Ουρά μιλάμε για Αφηρημένους Τύπους Δεδομένων. Δηλαδή δεν μας ενδιαφέρει πως υλοποιούνται από πίσω. Εμείς απλά χρησιμοποιούμε την διεπαφή Ώθηση/Απώθηση. Δεν γνωρίζουμε αν από πίσω υπάρχει πίνακας ή λίστα.
και το:
Παράθεση από: alkisg στις 07 Μαρ 2011, 03:37:52 ΜΜ
Στοίβες και ουρές μπορούν να υλοποιηθούν και με στατικό και με δυναμικό τρόπο.
Νομίζω όμως ότι οι δύο αυτές δομές αποτελούν διαφορετικά διδακτικά αντικείμενα από τους τρόπους δέσμευσης μνήμης, οι οποίοι συμπεριλαμβάνουν κι άλλες δομές από πίσω τους (πίνακες, λίστες κτλ).

Επειδή υπάρχει πίνακας από πίσω έχουμε προδεσμεύσει Ν θέσεις. Άρα η υλοποίηση είναι στατική. Αυτό δεν μπορώ να το παραβλέψω.
Από την άλλη έχουμε πρόσβαση μόνο σε ένα στοιχείο τη φορά (αυτό της κορυφής) και όχι σε όλα. Άρα δεν υπάρχει ισοδυναμία με τους πίνακες (ΑΤΔ). Όμως μπορώ να παραβλέψω ότι η ώθηση και η απώθηση φαίνεται να προσθέτουν/αφαιρούν στοιχεία ως εξής: Αρχικά τα στοιχεία δεν είναι ανύπαρκτα, αλλά εχουν μια προκαθορισμένη τιμή πχ. μηδέν. Με την πρώτη ώθηση αντικαθιστάς το μηδενικό της κορυφής με την τιμή που μπαίνει. Στην απώθηση απλά μετακινείς την κορυφή προς τα κάτω, ώστε με την επόμενη ώθηση να αντικαταστήσεις την παλιά τιμή.
Αυτή την εξήγηση δίνω, η οποία μου φαίνεται κάπως συνεπής.

Παράθεση από: xara_pap στις 07 Μαρ 2011, 04:06:04 ΜΜ
Τώρα αν εμένα με ρωτήσει κάποιος ποια δυναμική δομή δεδομένων γνωρίζουμε τι πρέπει να απαντήσω?
Νομίζω ότι πρέπει να τον ρωτήσεις αν εννοεί δομή δεδομένων με δυναμική υλοποίηση.

Παράθεση από: xara_pap στις 07 Μαρ 2011, 04:06:04 ΜΜ
Εμπλέκεται πουθενά σε όλα αυτά το αρχείο ή η εγγραφή?
Όχι.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

odysseas

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

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

Παράθεση από: xara_pap στις 07 Μαρ 2011, 04:06:04 ΜΜ
Εμπλέκεται πουθενά σε όλα αυτά το αρχείο ή η εγγραφή? Γιατί κάτι νομίζω εχει πάρει το μάτι μου σε βοήθημα.

Τα αρχεία αναφέρονται στη σελ. 67 του σχολικού βιβλίου. Είναι δυναμικές δομές δευτερεύουσας μνήμης αλλά επειδή μπορεί δημιουργώντας ένα αρχείο να δεσμεύσεις όλο το δίσκο με κενές εγγραφές και να τις γεμίζεις εκ των υστέρων κατά βούληση τότε ίσως να είναι και στατικές, ξέρω γω...

Νίκος Αδαμόπουλος

Νομίζω ότι το βιβλίο εξηγεί και την υλοποίηση: για την ώθηση αυξάνει το top κατά ένα και στην θέση αυτή μπαίνει το νέο στοιχείο, κλπ... Εντάξει, δεν είμαι και πλήρως ικανοποιημένος με την προσέγγιση του βιβλίου, αφού αφήνει κενά, όπως π.χ. τι γίνεται αν το rear φτάσει στην τελευταία θέση του πίνακα αλλά όμως υπάρχουν ελεύθερες θέσεις από την άλλη μεριά του πίνακα, κλπ. Όμως δεν νομίζω ότι χρειάζεται να δραματοποιούμε τα πράγματα...!

Επίσης, το ότι χρησιμοποιούνται οι όροι ώθηση - απώθηση (και αντίστοιχα εισαγωγή - εξαγωγή στην ουρά) δεν σημαίνει ότι έχουμε εισαγωγή ή διαγραφή νέων κόμβων, με την έννοια τουλάχιστον που δίνεται στην περιγραφή των 8 λειτουργιών επί των δομών δεδομένων. Η "συνωνυμία" όντως δημιουργεί παρερμηνίες... Η εξήγηση προς τους μαθητές θα μπορούσε να είναι η εξής: Οι κόμβοι σε μια στοίβα ή και ουρά είναι Ν, ούτε εισάγονται ούτε διαγράφονται κόμβοι... Θα λέγαμε ότι οι λειτουργίες ώθηση, απώθηση (εισαγωγή, εξαγωγή στην ουρά), αντιστοιχούν στην λειτουργία της "προσπέλασης". Μόνο που αυτή θα γίνεται αυστηρά στην κορυφή της στοίβας (ή στο εμπρός και πίσω άκρο της ουράς).

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

Νίκος Αδαμόπουλος

Πάντως αν είναι να διορθωθεί το βιβλίο, τότε όποιος το αναλάβει καλό θα ήταν να μην ξεχάσει να διορθώσει και το ότι σε μια στατική δομή το ακριβές μέγεθος καθορίζεται στη φάση του προγραμματισμού...  ;)  :-X  >:D

odysseas

Παράθεση από: Νίκος Αδαμόπουλος στις 07 Μαρ 2011, 06:19:04 ΜΜ
Η εξήγηση προς τους μαθητές θα μπορούσε να είναι η εξής: Οι κόμβοι σε μια στοίβα ή και ουρά είναι Ν, ούτε εισάγονται ούτε διαγράφονται κόμβοι... Θα λέγαμε ότι οι λειτουργίες ώθηση, απώθηση (εισαγωγή, εξαγωγή στην ουρά), αντιστοιχούν στην λειτουργία της "προσπέλασης". Μόνο που αυτή θα γίνεται αυστηρά στην κορυφή της στοίβας (ή στο εμπρός και πίσω άκρο της ουράς).

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

Όχι, προσωπικά διαφωνώ κάθετα και στα δύο παραπάνω.

evry

Άλκη το σκεπτικό το οποίο αναφέρεις μπορεί να ισχύσει για οποιαδήποτε δομή. Δηλαδή ακόμα και στην δυναμική εκχώρηση μνήμης είναι πιθανόν η κλήση να αποτύχει διότι η μνήμη του υπολογιστή είναι πεπερασμένη. Άρα με το σκεπτικό αυτό όλες οι δομές είναι στατικές αφού έχουν τέτοιους περιορισμούς.
  Πράγματι πρέπει να ορίσουμε τι εννοούμε επακριβώς όταν λέμε δυναμική δομή δεδομένων και δυναμική εκχώρηση μνήμης όμως κατά τη γνώμη μου δεν πρέπει να σκεφτόμαστε με όρους υλοποίησης. Όταν μιλάμε για μια δομή πρέπει να έχουμε στο μυαλό μας τον ΑΤΔ αυτής της δομής. για παράδειγμα ο ΑΤΔ του πίνακα είναι στατικός. Δεν προσθέτεις ούτε διαγράφεις τίποτα. Στην στοίβα και στην ουρά όμως τα πράγματα είναι διαφορετικά. Αυτός που χρησιμοποιεί μια στοίβα δεν ξέρει τι κρύβεται από πίσω. Βλέπει μόνο τους κόμβους που προσθέτει και αφαιρεί. Το αν είναι πίνακας ή όχι δεν έχει σημασία. Για παράδειγμα θα μπορούσα να υλοποιήσω μια στοίβα με πίνακα και μόλις γεμίσει να δεσμεύσω έναν πίνακα με το διπλάσιο μέγεθος (έχω την εντύπωση ότι αυτή τη στρατηγική ακολουθεί η Java).  Αυτό θα μπορούσε να θεωρηθεί δυναμικό?
  Επίσης είναι και το άλλο θέμα κατά τη γνώμη μου, η ασυνέπεια που παρουσιάζεται όταν το εξηγούμε στους μαθητές. π.χ. φαντάσου μια στοίβα με 2 στοιχεία. Προσθέτουμε 3. Ρωτάμε τον μαθητή "πόσα στοιχεία έχει τώρα?" μας λέει "5". Αφαιρούμε 4. Πόσα έχει τώρα? "1". Και μετά του λέμε ότι πρόκειται για στατική δομή. Δεν είναι ανακόλουθο, ή τουλάχιστον δεν φαίνεται ασυνεπές προς τον μαθητή?
   
   Επίσης όσον αφορά το παράδειγμα με τα πιάτα και το ταβάνι, φαντάσου ότι είσαι στην ύπαιθρο ;)

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

alkisg

Παράθεση από: evry στις 07 Μαρ 2011, 09:05:28 ΜΜ
Άλκη το σκεπτικό το οποίο αναφέρεις μπορεί να ισχύσει για οποιαδήποτε δομή. Δηλαδή ακόμα και στην δυναμική εκχώρηση μνήμης είναι πιθανόν η κλήση να αποτύχει διότι η μνήμη του υπολογιστή είναι πεπερασμένη. Άρα με το σκεπτικό αυτό όλες οι δομές είναι στατικές αφού έχουν τέτοιους περιορισμούς.

Πιστεύω ότι η διαφορά της στατικής δομής από τη δυναμική δομή είναι ξεκάθαρη:

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

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

Δηλαδή όταν κάνουμε array A = malloc(N θέσεις), δημιουργούμε στατική δομή αφού για όλη τη διάρκεια της ζωής της θα έχει σταθερά Ν θέσεις.
Ενώ αντίθετα οι πίνακες της Javascript είναι δυναμικές δομές αφού το πλήθος θέσεων μνήμης που καταλαμβάνουν μεταβάλλεται κατά τη διάρκεια της ζωής τους.

Αν λοιπόν στη Διαδικασία ΕισαγωγήΣεΟυρά ελέγχουμε ΑΝ ι <= Ν, τότε αυτή είναι στατική δομή.
Αν στη Διαδικασία ΕισαγωγήΣεΟυρά ελέγχαμε ΑΝ (node=malloc()) != NULL τότε είναι δυναμική δομή, δεν κάνουμε αναφορά σε κανένα μέγιστο αριθμό θέσεων Ν.
Φυσικά η ελεύθερη μνήμη του συστήματος είναι ένας περιορισμός, ποτέ κανένα άπειρο δεν χωράει σε υπολογιστή, αλλά το (μεταβλητό) όριο που θέτει η ελεύθερη μνήμη δεν έχει σχέση με το αν η δομή είναι στατική ή δυναμική.

alkisg

Με άλλα λόγια.
Αν στο ΑΤΔ σου βάλεις:
  constructor ΔημιούργησεΟυρά(Ν)
τότε η ουρά σου είναι στατική δομή,
ενώ αν βάλεις
  constructor ΔημιούργησεΟυρά()
τότε είναι δυναμική.


(btw αν κατάλαβα καλά τον Αφηρημένο Τύπο Δεδομένων που λες, τότε δεν με καλύπτει για τις περιγραφές των δομών δεδομένων, αφού π.χ. η συνάρτηση ΠροσπέλασεΣτοιχείο(10) μου δίνει μόνο το interface για την προσπέλαση του 10ου στοιχείου, ενώ για μια σωστή περιγραφή της δομής εγώ θέλω να ξέρω κι αν αυτό λειτουργεί σε O(1) ή σε Ο(Ν), δηλαδή θέλω να ξέρω και χαρακτηριστικά του implementation)