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

Γενικό Λύκειο => Γ΄ Λυκείου => Δομές δεδομένων => Μήνυμα ξεκίνησε από: xara_pap στις 07 Μαρ 2011, 02:51:39 ΠΜ

Τίτλος: Δυναμική δομή δεδομένων
Αποστολή από: xara_pap στις 07 Μαρ 2011, 02:51:39 ΠΜ
Καλησπέρα κι απο μένα.
Θα ήθελα να ρωτήσω αν τα παιδιά πρέπει να γνωρίζουν κάποια δυναμική δομή δεδομένων μίας και το βιβλίο δεν αναφέρει κάτι.
Ευχαριστώ
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: odysseas στις 07 Μαρ 2011, 09:56:12 ΠΜ
Παράθεση από: xara_pap στις 07 Μαρ 2011, 02:51:39 ΠΜ
Θα ήθελα να ρωτήσω αν τα παιδιά πρέπει να γνωρίζουν κάποια δυναμική δομή δεδομένων μίας και το βιβλίο δεν αναφέρει κάτι.

Αναφέρει τη στοίβα και την ουρά, οι οποίες είναι δυναμικές.
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: P.Tsiotakis στις 07 Μαρ 2011, 11:10:26 ΠΜ
Οι δυναμικές δομές δεδομένων στο σχολικό βιβλίο, αναφέρονται στην παράγραφο 3.9
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: Νίκος Αδαμόπουλος στις 07 Μαρ 2011, 01:12:13 ΜΜ
Παράθεση από: odysseas στις 07 Μαρ 2011, 09:56:12 ΠΜ
Αναφέρει τη στοίβα και την ουρά, οι οποίες είναι δυναμικές.

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

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

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

Από διδακτικής πλευράς τώρα η απορία μου είναι : Πως είναι δυνατόν να εξηγείς σε έναν μαθητή τι είναι στοίβα και τι είναι ουρά με παραδείγματα από την πραγματική ζωή όπου έχουμε μετακίνηση αντικειμένων, δηλαδή εισαγωγή/διαγραφή κόμβων και μετά να του λες ότι είναι στατικές δομές.
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: alkisg στις 07 Μαρ 2011, 03:37:52 ΜΜ
Η στοίβα στις αρχιτεκτονικές επεξεργαστών που ξέρω είναι στατική, π.χ. δεν επιτρέπεται να καλέσεις αναδρομικά μια συνάρτηση περισσότερες από Ν φορές, θα έχεις stack overflow.
Η στοίβα πιάτων επίσης είναι στατική, μέγιστος χώρος είναι το ταβάνι.
Στοίβες και ουρές μπορούν να υλοποιηθούν και με στατικό και με δυναμικό τρόπο.
Νομίζω όμως ότι οι δύο αυτές δομές αποτελούν διαφορετικά διδακτικά αντικείμενα από τους τρόπους δέσμευσης μνήμης, οι οποίοι συμπεριλαμβάνουν κι άλλες δομές από πίσω τους (πίνακες, λίστες κτλ). Για να μιλήσουμε για δυναμικές δομές χρειάζεται κατ' ελάχιστο να αναφέρουμε τι σημαίνει δυναμική δέσμευση μνήμης...
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: xara_pap στις 07 Μαρ 2011, 04:06:04 ΜΜ
Νομίζω οι απαντήσεις ξέφυγαν λίγο. Σχετικά με τη στοίβα και την ουρά μας αναφέρει οτι υλοποιούνται με πίνακα μέσα στην ύλη άρα το παρουσιάζουμε σαν στατική δομή. Τώρα αν εμένα με ρωτήσει κάποιος ποια δυναμική δομή δεδομένων γνωρίζουμε τι πρέπει να απαντήσω?
Εμπλέκεται πουθενά σε όλα αυτά το αρχείο ή η εγγραφή? Γιατί κάτι νομίζω εχει πάρει το μάτι μου σε βοήθημα.
Ευχαριστώ
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: pgrontas στις 07 Μαρ 2011, 05:32:50 ΜΜ
Το γεγονός ότι το συγκεκριμένο θέμα επανέρχεται τόσες φορές, είναι ενδεικτικό του ό,τι στο βιβλίο τα κάνανε σαλάτα. Και πώς να μην γίνει αυτό εφόσον το Κεφ. 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 ΜΜ
Εμπλέκεται πουθενά σε όλα αυτά το αρχείο ή η εγγραφή?
Όχι.
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: odysseas στις 07 Μαρ 2011, 06:16:41 ΜΜ
Δηλαδή αν το βιβλίο δεν ανέφερε τίποτα για την υλοποίηση της στοίβας και της ουράς τότε ίσως να ήταν δυναμικές δομές, ενώ τώρα που αναφέρει συγκεκριμένα για πίνακα (από τους διάφορους πιθανούς τρόπους υλοποίησης) η στοίβα και η ουρά είναι στατικές.

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

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

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

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

Και για να επανέλθω στο αρχικό μήνυμά μου, νομίζω ότι συμφωνούμε τουλάχιστον σε αυτό: "αφού το βιβλίο μιλάει για υλοποίηση με πίνακα, αν δεν αλλάξει αυτό, δεν μπορούμε να λέμε ότι η στοίβα και η ουρά είναι δυναμικές δομές δεδομένων".
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: Νίκος Αδαμόπουλος στις 07 Μαρ 2011, 06:26:49 ΜΜ
Πάντως αν είναι να διορθωθεί το βιβλίο, τότε όποιος το αναλάβει καλό θα ήταν να μην ξεχάσει να διορθώσει και το ότι σε μια στατική δομή το ακριβές μέγεθος καθορίζεται στη φάση του προγραμματισμού...  ;)  :-X  >:D
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: odysseas στις 07 Μαρ 2011, 07:24:38 ΜΜ
Παράθεση από: Νίκος Αδαμόπουλος στις 07 Μαρ 2011, 06:19:04 ΜΜ
Η εξήγηση προς τους μαθητές θα μπορούσε να είναι η εξής: Οι κόμβοι σε μια στοίβα ή και ουρά είναι Ν, ούτε εισάγονται ούτε διαγράφονται κόμβοι... Θα λέγαμε ότι οι λειτουργίες ώθηση, απώθηση (εισαγωγή, εξαγωγή στην ουρά), αντιστοιχούν στην λειτουργία της "προσπέλασης". Μόνο που αυτή θα γίνεται αυστηρά στην κορυφή της στοίβας (ή στο εμπρός και πίσω άκρο της ουράς).

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

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

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

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

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

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

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

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


(btw αν κατάλαβα καλά τον Αφηρημένο Τύπο Δεδομένων που λες, τότε δεν με καλύπτει για τις περιγραφές των δομών δεδομένων, αφού π.χ. η συνάρτηση ΠροσπέλασεΣτοιχείο(10) μου δίνει μόνο το interface για την προσπέλαση του 10ου στοιχείου, ενώ για μια σωστή περιγραφή της δομής εγώ θέλω να ξέρω κι αν αυτό λειτουργεί σε O(1) ή σε Ο(Ν), δηλαδή θέλω να ξέρω και χαρακτηριστικά του implementation)
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: evry στις 07 Μαρ 2011, 10:15:02 ΜΜ
πολύ καλά κατάλαβες. Εγώ θεωρώ ότι δεν πρέπει να ξέρεις την υλοποίηση. Δηλαδή πρέπει να υπάρχει πλήρης ανεξαρτησία μεταξύ interface-implementation. Δηλαδή ναι μεν μπορούμε να πούμε ότι έχουμε υλοποίηση της στοίβας με στατικές ή δυναμικές δομές, αλλά αυτό που εμείς βλέπουμε (το interface) είναι δυναμικό. Σύμφωνα με τη δική σου προσέγγιση εγώ το βλέπω ότι πάντα θα έχει constructor ΔημιούργησεΟυρά().
Κάτι άλλο που θεωρώ σημαντικό είναι ότι τα χαρακτηριστικά αυτών των δομών δεδομένων δηλαδή το ώθησε/απώθησε εισαγωγή/διαγραφή παραπέμπουν καθαρά σε μια δομή που το μέγεθός της αυξομοιώνεται. (εννοώ το ιδεατό μέγεθος).
Επίσης η θεώρηση τέτοιων δομών ως δυναμικές πιστεύω ότι διδακτικά (και όχι μόνο) είναι πολύ κοντά στα αντικείμενα του πραγματικού κόσμου που αυτές μοντελοποιούν.
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: evry στις 07 Μαρ 2011, 10:20:40 ΜΜ
Δηλαδή εγώ λέω ότι δεν πρέπει να ξέρεις τα χαρακτηριστικά του implementation. Ξέρεις ότι σου λέει το interface και τίποτα περισσότερο.

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

Αυτό που είπες για τον χρόνο προσπέλασης, μπορεί να υπάρχει σαν πληροφορία στο interface π.χ. Αλλά δεν πρέπει (κατά τη γνώμη μου) να υπάρχουν στον κώδικά σου στοιχεία που αποκαλύπτουν την υλοποίηση της δομής
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: odysseas στις 07 Μαρ 2011, 10:28:29 ΜΜ
edit: Πόσταρα τα παρακάτω πριν διαβάσω τις απαντήσεις του ευριπίδη. Με βρίσκουν απόλυτα σύμφωνο και πρακτικά λέμε το ίδιο πράγμα.

Αν εγώ αύριο αποφασίσω πως δεν μου αρέσει ο Διερμηνευτής και θέλω να γράψω έναν δικό μου, θα ανοίξω ένα βιβλίο για compilers για να δω πως μπορώ να μετατρέψω infix εκφράσεις σε postfix και πως να τις αποτιμήσω. Ο αλγόριθμος που θα συναντήσω θα χρησιμοποιεί στοίβα και ουρά και πουθενά μα πουθενά δε θα ελέγχει για τυχόν υπερχείλιση ή για εξάντληση της μνήμης. Γιατί εκεί η στοίβα και ουρά είναι αφηρημένοι τύποι δεδομένων, ενώ οι παραπάνω έλεγχοι αφορούν την υλοποίησή τους, η οποία δεν έχει απολύτως καμία σημασία. Μπορεί κανείς να αρνηθεί ότι πρόκειται για δυναμικές δομές δεδομένων; Ο παρακάτω ορισμός του Άλκη προφανώς και βγάζει νόημα και με βρίσκει απόλυτα σύμφωνο, όμως δεν αρμόζει σε αφηρημένους τύπους δεδομένων αλλά σε προγραμματιστικές κατασκευές.

Παράθεση από: alkisg στις 07 Μαρ 2011, 09:37:45 ΜΜ
Στατική δομή = από τη στιγμή που τη δημιουργούμε και μέχρι να την καταστρέψουμε, καταλαμβάνει συγκεκριμένο πλήθος θέσεων μνήμης.
Δυναμική δομή = ο αριθμός θέσεων μνήμης μπορεί να μεταβληθεί κατά τη διάρκεια ζωής της δομής.

Επίσης:

Παράθεση από: alkisg στις 07 Μαρ 2011, 09:37:45 ΜΜ
Αν λοιπόν στη Διαδικασία ΕισαγωγήΣεΟυρά ελέγχουμε ΑΝ ι <= Ν, τότε αυτή είναι στατική δομή.
Αν στη Διαδικασία ΕισαγωγήΣεΟυρά ελέγχαμε ΑΝ (node=malloc()) != NULL τότε είναι δυναμική δομή, δεν κάνουμε αναφορά σε κανένα μέγιστο αριθμό θέσεων Ν.

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

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

Η στοίβα και η ουρά, ως αφηρημένοι τύποι δεδομένων, είναι δυναμικές δομές. Η υλοποίησή τους μπορεί να γίνει είτε με τον ένα είτε με τον άλλον τρόπο και εκεί είναι που μπορεί να εφαρμοστεί ο ορισμός του Άλκη.
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: alkisg στις 08 Μαρ 2011, 12:19:57 ΠΜ
Παράθεση από: evry στις 07 Μαρ 2011, 10:20:40 ΜΜ
Δηλαδή εγώ λέω ότι δεν πρέπει να ξέρεις τα χαρακτηριστικά του implementation. Ξέρεις ότι σου λέει το interface και τίποτα περισσότερο.

Είμαι κάθετα αντίθετος.
Θεωρώ ότι η μελέτη δομών δεδομένων δεν είναι ισοδύναμη με τη μελέτη του interface μιας closed-source βιβλιοθήκης.
Πριν επεκταθώ όμως, να καταθέσω δύο προτάσεις προς σχολιασμό, ώστε να εντοπίσουμε λίγο καλύτερα πού ακριβώς συμφωνούμε και πού διαφωνούμε.


Παράθεση από: evry στις 07 Μαρ 2011, 01:37:53 ΜΜ
Όταν μιλάμε για Στοίβα και Ουρά μιλάμε για Αφηρημένους Τύπους Δεδομένων.

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

Btw, "Τύπο Δεδομένων" δεν λέμε τον ακέραιο, τον πραγματικό κτλ; Μήπως εννοείτε "Αφηρημένη Δομή Δεδομένων" αντί για "Τύπο";
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: xara_pap στις 08 Μαρ 2011, 12:56:45 ΠΜ
Απο ό,τι βλέπω σας έβαλα σε μεγάλη συζήτηση και σε καταιγισμό επίδειξης γνωσεων. Εντάξει αφηρημένος τύπος δεδομένων είναι κι αν θέλουμε το υλοποιούμε είτε με πίνακα είτε με δείκτη. Μιλάμε όμως νομίζς στο φόρουμ για αεππ και εφόσον υλοποιείται με πίνακα είναι στατικές.
Ειχαν βάλει ποτε σε πανελλήνιες είτε επαναληπτικές είτε εσπερινου λυκείου για το αν το αρχείο είναι δυναμική δομή δεδομένων σε Σ-Λ? Το ρωτάω γιατί έχω αυτή την υποψία. Σχετικά με τα υπόλοιπα όλοι έχουμε τα βιβλία μπροστά μας και ξέρουμε τι λένε
Φιλικά
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: Νίκος Αδαμόπουλος στις 08 Μαρ 2011, 01:17:34 ΠΜ
Καταρχάς συμφωνώ με τον Άλκη.

Πέρα όμως από αυτό, οι ορισμοί-χαρακτηριστικά που δίνει το βιβλίο για τη στατική και τη δυναμική δομή δεδομένων έχουν να κάνουν με τη διεπαφή του προγραμματιστή ή με τον τρόπο που υλοποιούνται-λειτουργούν αυτές οι δομές; Η προσέγγιση του σχολικού βιβλίου για τη στοίβα και την ουρά είναι αφηρημένη;

Εμένα προσωπικά δεν με ενδιαφέρει καν κάποιος επίσημος και σωστός ορισμός για το τι είναι στατική ή δυναμική δομή δεδομένων. Αν χρειαστεί να φτιάξω λογισμικό ξέρω να χρησιμοποιώ κάθε φορά αυτό που πρέπει ανάλογα με την περίπτωση χωρίς να με ενδιαφέρει πώς το λένε. Ας το λένε και Μήτσο, αρκεί να ξέρω πώς λειτουργεί και τι επιπτώσεις θα έχει η λειτουργία του στο λογισμικό μου. Σάμπως, έκατσε ποτέ κανείς και όρισε πρώτα τις στατικές και τις δυναμικές δομές και στη συνέχεια έφτιαξε αντίστοιχες δομές; Μάλλον το αντίθετο έγινε! Έτσι, λοιπόν, θεωρώ ότι όλα αυτά είναι απλές συμβάσεις και θέματα ορισμών, τα οποία συνεχώς μεταλλάσσονται-εξελίσσονται παράλληλα με την εξέλιξη της επιστήμης της Πληροφορικής.

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

Πραγματικά είμαι περίεργος να απαντήσετε.

Εγώ πάντως, όπως είπα, προτείνω ότι αφού το βιβλίο περιγράφει την υλοποίηση μέσω πίνακα, τότε η συγκεκριμένη προσέγγιση θεωρεί την ουρά και στοίβα ως στατική δομή (εντάξει τους αναφέρω ότι θα μπορούσε με άλλου είδους υλοποίηση να θεωρούνται δυναμικές δομές), δηλαδή "οι κόμβοι σε μια στοίβα ή και ουρά είναι Ν, ούτε εισάγονται ούτε διαγράφονται κόμβοι... και οι λειτουργίες ώθηση, απώθηση (εισαγωγή, εξαγωγή στην ουρά), αντιστοιχούν στην λειτουργία της "προσπέλασης". Μόνο που αυτή θα γίνεται αυστηρά στην κορυφή της στοίβας (ή στο εμπρός και πίσω άκρο της ουράς)". Έτσι θεωρώ ότι δεν υπάρχει ασυνέπεια, ούτε ότι διαπράττω επιστημονικό σφάλμα!
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: Sergio στις 08 Μαρ 2011, 01:21:14 ΠΜ
Παράθεση από: alkisg στις 08 Μαρ 2011, 12:19:57 ΠΜ
Btw, "Τύπο Δεδομένων" δεν λέμε τον ακέραιο, τον πραγματικό κτλ; Μήπως εννοείτε "Αφηρημένη Δομή Δεδομένων" αντί για "Τύπο";

Υποθέτω ότι απλά αναφέρεται ως κατα λέξη μετάφραση του ADT (Absrtact Data Type)
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: alkisg στις 08 Μαρ 2011, 01:50:34 ΠΜ
Παράθεση από: Sergio στις 08 Μαρ 2011, 01:21:14 ΠΜ
Υποθέτω ότι απλά αναφέρεται ως κατα λέξη μετάφραση του ADT (Absrtact Data Type)

Σωστός, thanks. Βρήκα μια καλή περιγραφή εδώ:
Παράθεση από: http://www-sst.informatik.tu-cottbus.de/~db/doc/People/Broy/Software-Pioneers/Guttag_new.pdf
The notion of an abstract data type is quite simple. It is a set of objects
and the operations on those objects. The specification of those operations
defines an interface between the abstract data type and the rest of the
program. The interface defines the behavior of the operations – what they
do, but not how they do it. The specification thus defines an abstraction
barrier (Figure 1) that isolates the rest of the program from the data
structures, algorithms
, and code involved in providing a realization of the
type abstraction.

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


Παράθεση από: xara_pap στις 08 Μαρ 2011, 12:56:45 ΠΜ
Απο ό,τι βλέπω σας έβαλα σε μεγάλη συζήτηση και σε καταιγισμό επίδειξης γνωσεων.

Αυτό δεν ήταν ευγενικό, δε νομίζω ότι είχε κανείς ως στόχο να κάνει επίδειξη γνώσεων. Σύμφωνοι, εσύ ξεκίνησες το θέμα και αν θεωρείς ότι αυτά που λέμε είναι εκτός θέματος να τα μεταφέρουμε αλλού, γενικά όμως σε ένα φόρουμ οι συζητήσεις είναι δεν είναι πάντα σε μορφή ερώτησης/απάντησης αλλά πολλές φορές δίνουν έναυσμα και σε απορίες/διαφωνίες τρίτων...
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: Νίκος Αδαμόπουλος στις 08 Μαρ 2011, 02:07:54 ΠΜ
Παράθεση από: xara_pap στις 08 Μαρ 2011, 12:56:45 ΠΜ
Ειχαν βάλει ποτε σε πανελλήνιες είτε επαναληπτικές είτε εσπερινου λυκείου για το αν το αρχείο είναι δυναμική δομή δεδομένων σε Σ-Λ?

Δεν νομίζω! Τα πιο σχετικά ΣΛ που βρήκα:
- Σε μια στατική δομή το ακριβές μέγεθος της απαιτούμενης κύριας μνήμης καθορίζεται κατά την εκτέλεση του προγράμματος. (2009 - Ημερησίου)
- Η δυναμική παραχώρηση μνήμης χρησιμοποιείται στις δομές των πινάκων. (2010 - Ημερησίου)

Επίσης, το:

"Να αναφέρετε δύο βασικές λειτουργίες επί των δομών δεδομένων που δεν μπορούν να χρησιμοποιηθούν στους πίνακες. Να αιτιολογήσετε την απάντησή σας." (2007 - Επαν. Ημερησίου)
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: odysseas στις 08 Μαρ 2011, 02:39:46 ΠΜ
Παράθεση από: alkisg στις 08 Μαρ 2011, 01:50:34 ΠΜ
Δηλαδή ένας από τους στόχους των ΑΤΔ είναι να "κρύβουν" τις δομές δεδομένων που χρησιμοποιούν για την υλοποίηση των λειτουργιών τους. Άρα δε νομίζω ότι μας ενδιαφέρουν οι ΑΤΔ όταν ο σκοπός μας είναι ακριβώς να διδάξουμε συγκεκριμένες δομές δεδομένων και αλγορίθμους.

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

Από κει και πέρα το ζήτημα της πολυπλοκότητας που έθεσες είναι πάρα πολύ εύστοχο. Γιατί για να μελετήσει κανείς την πολυπλοκότητα ενός αλγορίθμου που χρησιμοποιεί έναν ΑΤΔ πρέπει όντως συνήθως να γνωρίζει την αναπαράσταση που αυτός χρησιμοποιεί. Κι αυτό γιατί η πολυπλοκότητα των λειτουργιών επηρεάζεται από την αναπαράσταση. Και σκοπίμως δε μιλώ για υλοποίηση αλλά για αναπαράσταση.

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

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

Άντε, καληνύχτα μας.
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: Sergio στις 08 Μαρ 2011, 03:36:30 ΠΜ
Στην ερώτηση του Νίκου (https://alkisg.mysch.gr/steki/index.php?topic=3760.msg38684#msg38684) και συγκεκριμένα:
Παράθεση από: Νίκος Αδαμόπουλος στις 08 Μαρ 2011, 01:17:34 ΠΜ
τι ακριβώς από τα παρακάτω κάνετε-προτείνετε για τις ουρές και στοίβες σε διδακτικό-παιδαγωγικό επίπεδο:
εγώ προτείνω το στ: Άλλο.. και θα εξηγήσω στη συνέχεια ακριβώς ΤΙ, αν και νομίζω ότι ο "ορισμός" του ADT που δίνεται σε επόμενη παράγραφο στο άρθρο που ανέφερε ο Άλκης (http://www-sst.informatik.tu-cottbus.de/~db/doc/People/Broy/Software-Pioneers/Guttag_new.pdf), το περιγράφει επαρκώς:


At most points in the program, one is concerned solely with the behavioral characteristics of the data object. What one can do with them; not with how the various operations on them are implemented. I will use the term "abstract data type" to refer to a class of objects defined by a representation independent specification.



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

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

Επομένως πιστεύω πως ο προβληματισμός μας περί της στατικότητας ή δυναμικότητας των συγκεκριμένων δομών, δεν έχει λόγο να υφίσταται. Αφορά καθαρά στην υλοποίηση και όχι στη συμπεριφορά, που είναι και το ζητούμενο από μία στοίβα (ή ουρά) στο πλαίσιο των στόχων του μαθήματος. Εξάλλου, οποιοδήποτε παράδειγμα υλοποίησης, όπως αυτό με τον πίνακα που έχει το σχολικό βιβλίο, έχει ως σκοπό να βοηθήσει στην κατανόηση της συμπεριφοράς της δομής και όχι (ως έμμεση αναφορά) στην κατάταξή της σε μία από τις δύο κατηγορίες δομών (χαμηλότερου επιπέδου).  Και κάπως έτσι απαντώ και στους μαθητές, όταν εκφράζουν αντίστοιχο προβληματισμό.
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: Sergio στις 08 Μαρ 2011, 09:24:49 ΠΜ
Μήπως το συγκεκριμένο θέμα ανήκει, καλύτερα, στο χώρο της θεωρίας και όχι σε αυτό των μονοδιάστατων πινάκων ;
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: alkisg στις 08 Μαρ 2011, 10:31:42 ΠΜ
Αν έχω καταλάβει καλά, τα ΑΤΔ ανήκουν σε μια "σχολή" σκέψης, ενώ το βιβλίο μας ανήκει σε άλλη "σχολή", που λέει "Δομές δεδομένων + Αλγόριθμοι = προγράμματα" (κεφάλαιο 3.2 του βιβλίου, παραπομπή σε βιβλίο του Wirth).

Να παραθέσω λίγο πάλι το ιστορικό από το pdf:
Παράθεση από: http://www-sst.informatik.tu-cottbus.de/~db/doc/People/Broy/Software-Pioneers/Guttag_new.pdf
So, abstract data types were an indisputably good idea with an impeccable
pedigree. One would have assumed that in the mid-1970s everybody would
have stood up and saluted. Wrong. There was significant resistance in both
academia and industry.
There were other, apparently competing, ideas in the air. There was a
popular (and good) book called Algorithms + Data structures = Programs
[16].

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

Δεν νομίζω ότι είναι στο χέρι μας να διαλέξουμε όποια από τις δύο σχολές θέλουμε να χρησιμοποιήσουμε στη διδασκαλία μας. Μάλλον πρέπει να ακολουθήσουμε το βιβλίο μας, το οποίο πιστεύω ξεκάθαρα σε όλο το κεφάλαιο 3, και στο βιβλίο μαθητή και στο βιβλίο καθηγητή, ακολουθεί τη σχολή "δομές δεδομένων + αλγόριθμοι = προγράμματα".
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: alkisg στις 08 Μαρ 2011, 10:32:34 ΠΜ
Παράθεση από: xara_pap στις 07 Μαρ 2011, 02:51:39 ΠΜ
Θα ήθελα να ρωτήσω αν τα παιδιά πρέπει να γνωρίζουν κάποια δυναμική δομή δεδομένων μίας και το βιβλίο δεν αναφέρει κάτι.

Το βιβλίο κατατάσσει τη στοίβα και την ουρά στις στατικές δομές εφόσον περιγράφει υλοποίησή τους με πίνακες (και στο βιβλίο μαθητή και στο βιβλίο καθηγητή), ενώ σαν δυναμικές αναφέρει τις λίστες, τα δέντρα και τους γράφους:
Παράθεση από: Βιβλίο μαθητή, αρχίζοντας από τη σελίδα 56
...Ωστόσο, εμείς στη συνέχεια θα εξετάσουμε μόνο τις στατικές δομές που είναι ευκολότερες στην κατανόηση και στην υλοποίησή τους
3.3 Πίνακες
3.4 Στοίβα
3.5 Ουρά
...
3.9 Άλλες δομές δεδομένων
Κοινό γνώρισμα των δομών που εξετάστηκαν προηγουμένως είναι ότι οι διαδοχικοί κόμβοι αποθηκεύονται σε συνεχόμενες θέσεις της κύριας μνήμης. Στην παράγραφο αυτή γίνεται μια παρουσίαση τριών πολύ σπουδαίων δομών δεδομένων, στις οποίες οι κόμβοι δεν είναι απαραίτητο να κατέχουν συνεχόμενες θέσεις μνήμης. Πρόκειται για τις λίστες, τα δέντρα και τους γράφους.
...
Οι δομές δεδομένων που χρησιμοποιούν δείκτες, αποκαλούνται δυναμικές (dynamic)...

Άρα, αν θες μπορείς να αναφέρεις αυτές τις 3 ως παραδείγματα δυναμικών δομών, και να πεις βέβαια ότι είναι εκτός ύλης... :)
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: xara_pap στις 08 Μαρ 2011, 10:37:29 ΠΜ
Ευχαριστώ πολύ.
Σχετικά με πριν, ναι ίσως έχετε δίκιο να μην ειναι ευγενικό αλλα συνέχεια αυτό που βλέπω είναι ο ένας να ποσπαθεί να "την πει" στον άλλον και το φόρουμ είναι για να βοηθάει ο ένας τον άλλον. Μερικοι μπορεί να μην ξέρουν τι είναι το ΑΤΔ, είναι όμως και σχεδόν εκτός θέματος γαιτι η θεωρία του αεππ δεν αναφέρει κάτι και το θέμα ειναι να βοηθήσουμε και να μπορέσουμε να απαντήσουμε σύμφωνα με τα δεδομένα και όχι με αυτά που θυμόμαστε.
Φιλικά και συγγνώμη αν προσέβαλα κάποιον.
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: alkisg στις 08 Μαρ 2011, 10:45:16 ΠΜ
Παράθεση από: xara_pap στις 08 Μαρ 2011, 10:37:29 ΠΜ... ο ένας να προσπαθεί να "την πει" στον άλλον και το φόρουμ είναι για να βοηθάει ο ένας τον άλλον...

Όσο γι' αυτό μην ανησυχείς, οι περισσότεροι που συμμετείχαν ειδικά σε αυτό το θέμα είναι καλοί φίλοι μεταξύ τους. :)
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: Σπύρος Δουκάκης στις 08 Μαρ 2011, 11:30:07 ΠΜ
Εδώ είναι όλο το ζουμί!

Παράθεση από: alkisg στις 08 Μαρ 2011, 10:31:42 ΠΜ
Αν έχω καταλάβει καλά, τα ΑΤΔ ανήκουν σε μια "σχολή" σκέψης, ενώ το βιβλίο μας ανήκει σε άλλη "σχολή", που λέει "Δομές δεδομένων + Αλγόριθμοι = προγράμματα" (κεφάλαιο 3.2 του βιβλίου, παραπομπή σε βιβλίο του Wirth).

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

Δεν νομίζω ότι είναι στο χέρι μας να διαλέξουμε όποια από τις δύο σχολές θέλουμε να χρησιμοποιήσουμε στη διδασκαλία μας. Μάλλον πρέπει να ακολουθήσουμε το βιβλίο μας, το οποίο πιστεύω ξεκάθαρα σε όλο το κεφάλαιο 3, και στο βιβλίο μαθητή και στο βιβλίο καθηγητή, ακολουθεί τη σχολή "δομές δεδομένων + αλγόριθμοι = προγράμματα".
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: odysseas στις 08 Μαρ 2011, 12:41:45 ΜΜ
Παράθεση από: xara_pap στις 08 Μαρ 2011, 10:37:29 ΠΜ
Σχετικά με πριν, ναι ίσως έχετε δίκιο να μην ειναι ευγενικό αλλα συνέχεια αυτό που βλέπω είναι ο ένας να ποσπαθεί να "την πει" στον άλλον και το φόρουμ είναι για να βοηθάει ο ένας τον άλλον.

Εγώ θέλω να πω ότι λυπήθηκα ιδιαίτερα όταν διάβασα το παραπάνω γιατί καθόλου δεν ήταν κάτι τέτοιο στα κίνητρά μου και καθόλου δεν ήθελα να δημιουργηθεί τέτοια εντύπωση σε κανέναν. Αντιθέτως βρήκα τη συζήτηση (εντός και εκτός θέματος) πάρα πολύ ενδιαφέρουσα.
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: Σπύρος Δουκάκης στις 08 Μαρ 2011, 06:15:52 ΜΜ
Αντιγράφω από το άρθρο των:
Τσιωτάκης, Π., Στέργου, Σ., Αδαμόπουλος, Ν., & Ψαλτίδου, Α. (2010). Το διδακτικό πακέτο του μαθήματος «Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον». Ασάφειες και επακόλουθα προβλήματα. Στο Δουκάκης Σ. (Επιμ.) Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον, Παρελθόν, Παρόν και Μέλλον, ΕΠΥ, Αθήνα, Εκδόσεις Νέων Τεχνολογιών, 145-175.

Στο βιβλίο μαθητή [Βακάλη κ.α. (2009), σ. 59] αναφέρεται ότι: «Οι πίνακες χρησιμεύουν για την αποθήκευση και διαχείριση δύο σπουδαίων δομών, της στοίβας και της ουράς, που θα εξετασθούν λεπτομερέστερα στη συνέχεια, επειδή χρησιμοποιούνται σε πληθώρα πρακτικών εφαρμογών».

Στην πραγματικότητα, οι δομές αυτές δεν έχουν περιορισμό ως προς τον αριθμό των στοιχείων που μπορούν να δεχτούν [Κοίλιας (2004)]. Έτσι, και οι δύο δομές δεν είναι απαραίτητο ότι θα είναι στατικές, αλλά μπορεί να υλοποιούνται ως δυναμικές. Ωστόσο, η παραπάνω αναφορά αλλά και ο τρόπος υλοποίησης των δομών αυτών στο διδακτικό πακέτο του μαθήματος μάς υποχρεώνει να τις θεωρούμε ως στατικές. Το συμπέρασμα αυτό ενισχύεται αν λάβουμε υπόψη τους αλγορίθμους που παρουσιάζει το διδακτικό πακέτο για την πραγματοποίηση των λειτουργιών κάθε δομής.
Η υλοποίηση των δομών αυτών είναι εκτός ύλης από την πρώτη χρονιά εξέτασης του μαθήματος έως και σήμερα. Αυτό συμβάλλει στην παράκαμψη πρόσθετων ασαφειών που αφορούν στην αλγοριθμική υλοποίηση των δομών αυτών.

Ένα άλλο σημείο ασάφειας είναι το πώς τροποποιούνται οι δείκτες της ουράς κατά την εκτέλεση των λειτουργιών εισαγωγή/εξαγωγή. Πιο συγκεκριμένα, σε κάποια ουρά που περιέχει ένα στοιχείο, τι τιμή θα έχουν οι δείκτες «εμπρός» και «πίσω» αν πραγματοποιηθεί εξαγωγή (και η ουρά είναι πλέον άδεια); Σύμφωνα με τον Κοίλια (2004) «όταν εξέλθει και το τελευταίο στοιχείο της ουράς, ο δείκτης εμπρός γίνεται μεγαλύτερος από τον πίσω κατά 1. Το γεγονός αυτό εκμεταλλεύεται ο αλγόριθμος για να ελέγξει, αν η ουρά είναι άδεια σε επόμενη αίτηση εξαγωγής. Με την ευκαιρία δε αυτή αποδίδονται οι αρχικές τιμές μηδέν και στους δύο δείκτες, μια και η ουρά είναι πλέον άδεια. Με τον τρόπο αυτό αποφεύγεται η συχνή μετατόπιση των στοιχείων για την εύρεση νέων θέσεων». Επίσης, σε κάποια ουρά που περιέχει στοιχεία, τι συμβαίνει αν ο δείκτης «πίσω» φτάσει στο τέλος του πίνακα και οι αρχικές θέσεις της ουράς είναι κενές, λόγω προηγηθέντων εξαγωγών; Στο ερώτημα αυτό ο Κοίλιας (2004) αναφέρει τα ακόλουθα: «Είναι φανερό ότι προοδευτικά ο δείκτης τέλους θα φτάσει τη μέγιστη τιμή του μεγέθους του πίνακα και νέα στοιχεία δεν θα μπορούν να εισαχθούν, ενώ η ουρά μπορεί να διαθέτει ελάχιστα στοιχεία. Για το λόγο αυτό απαιτείται η μετακίνηση όλων των στοιχείων στην αρχή του πίνακα. Αυτή η μετακίνηση μπορεί να γίνεται με υποπρόγραμμα, το οποίο να καλείται αυτόματα όταν διαπιστωθεί ότι δεν υπάρχει χώρος για την εισαγωγή νέου στοιχείου. Έτσι αδυναμία εισαγωγής στοιχείου θα υπάρξει μόνο όταν ο πίνακας είναι πλήρης».

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

και ο Σέργιος εύστοχα θα συμπλήρωνε...

Παράθεση από: Sergio στις 08 Μαρ 2011, 03:36:30 ΠΜ
Με άλλα λόγια, θεωρώ ότι οι δύο δομές για τις οποίες μιλάμε (στοίβα - ουρά) οφείλουν να παρουσιάζονται ως "συμπεριφορές" μάλλον (LIFO, FIFO) παρά ως παράδειγμα κάποιου από τα δύο είδη δομών (στατικές - δυναμικές), κάτι σαν .. δομές δεδομένων υψηλού επιπέδου....
Τίτλος: Απ: Δυναμική δομή δεδομένων
Αποστολή από: thaaanos στις 12 Απρ 2020, 01:17:40 ΠΜ
Στατική δομή = από τη στιγμή που τη δημιουργούμε και μέχρι να την καταστρέψουμε, καταλαμβάνει συγκεκριμένο πλήθος θέσεων μνήμης. δεδομένων
Δυναμική δομή = ο αριθμός θέσεων μνήμης  δεδομένων μπορεί να μεταβληθεί κατά τη διάρκεια ζωής της δομής.