Αποστολέας Θέμα: Δυναμική δομή δεδομένων  (Αναγνώστηκε 11141 φορές)

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3606
  • to Iterate is human to Recurse divine
Απ: Δυναμική δομή δεδομένων
« Απάντηση #15 στις: 07 Μαρ 2011, 10:15:02 μμ »
πολύ καλά κατάλαβες. Εγώ θεωρώ ότι δεν πρέπει να ξέρεις την υλοποίηση. Δηλαδή πρέπει να υπάρχει πλήρης ανεξαρτησία μεταξύ interface-implementation. Δηλαδή ναι μεν μπορούμε να πούμε ότι έχουμε υλοποίηση της στοίβας με στατικές ή δυναμικές δομές, αλλά αυτό που εμείς βλέπουμε (το interface) είναι δυναμικό. Σύμφωνα με τη δική σου προσέγγιση εγώ το βλέπω ότι πάντα θα έχει constructor ΔημιούργησεΟυρά().
Κάτι άλλο που θεωρώ σημαντικό είναι ότι τα χαρακτηριστικά αυτών των δομών δεδομένων δηλαδή το ώθησε/απώθησε εισαγωγή/διαγραφή παραπέμπουν καθαρά σε μια δομή που το μέγεθός της αυξομοιώνεται. (εννοώ το ιδεατό μέγεθος).
Επίσης η θεώρηση τέτοιων δομών ως δυναμικές πιστεύω ότι διδακτικά (και όχι μόνο) είναι πολύ κοντά στα αντικείμενα του πραγματικού κόσμου που αυτές μοντελοποιούν.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3606
  • to Iterate is human to Recurse divine
Απ: Δυναμική δομή δεδομένων
« Απάντηση #16 στις: 07 Μαρ 2011, 10:20:40 μμ »
Δηλαδή εγώ λέω ότι δεν πρέπει να ξέρεις τα χαρακτηριστικά του implementation. Ξέρεις ότι σου λέει το interface και τίποτα περισσότερο.

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

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

odysseas

  • Ομάδα διαγωνισμάτων 2011
  • *
  • Μηνύματα: 842
Απ: Δυναμική δομή δεδομένων
« Απάντηση #17 στις: 07 Μαρ 2011, 10:28:29 μμ »
edit: Πόσταρα τα παρακάτω πριν διαβάσω τις απαντήσεις του ευριπίδη. Με βρίσκουν απόλυτα σύμφωνο και πρακτικά λέμε το ίδιο πράγμα.

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

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

Επίσης:

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

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

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

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5963
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Δυναμική δομή δεδομένων
« Απάντηση #18 στις: 08 Μαρ 2011, 12:19:57 πμ »
Δηλαδή εγώ λέω ότι δεν πρέπει να ξέρεις τα χαρακτηριστικά του implementation. Ξέρεις ότι σου λέει το interface και τίποτα περισσότερο.

Είμαι κάθετα αντίθετος.
Θεωρώ ότι η μελέτη δομών δεδομένων δεν είναι ισοδύναμη με τη μελέτη του interface μιας closed-source βιβλιοθήκης.
Πριν επεκταθώ όμως, να καταθέσω δύο προτάσεις προς σχολιασμό, ώστε να εντοπίσουμε λίγο καλύτερα πού ακριβώς συμφωνούμε και πού διαφωνούμε.
  • Αναπόσπαστο κομμάτι της περιγραφής μιας δομής είναι ο καθορισμός της πολυπλοκότητας και των απαιτήσεων μνήμης της, για όλες τις λειτουργίες της π.χ. Προσπέλαση, Εισαγωγή, Διαγραφή, Αναζήτηση, Ταξινόμηση, Αντιγραφή, Συγχώνευση, Διαχωρισμός κτλ (βλ. σελίδα 54 του βιβλίου).
    Δηλαδή δεν αρκεί να δώσω μόνο το prototype "Συνάρτηση ΠροσπέλασηΣτοιχείου(index)". Θα πρέπει οπωσδήποτε να αναφέρω αν αυτό γίνεται σε Ο(1) ή σε Ο(Ν) κτλ. Αν δεν το αναφέρω, τότε δεν έχω περιγράψει σωστά τη δομή, και αυτός που τη χρησιμοποιεί δεν θα μπορεί να υπολογίσει την πολυπλοκότητα των δικών του αλγορίθμων.
  • Ένας πίνακας, μια ουρά, μια στοίβα κτλ μπορούν να υλοποιηθούν με διαφορετικούς τρόπους, ώστε ορισμένες λειτουργίες τους να έχουν διαφορετική πολυπλοκότητα. Για παράδειγμα, η ΠροσπέλασηΣτοιχείου() σε πίνακες της Javascript δεν γίνεται σε Ο(1) επειδή χρησιμοποιούν κατακερματισμό, και επομένως δεν μπορώ να τους θεωρήσω ως την ίδια δομή με τους πίνακες της Pascal που είναι σε συνεχόμενες θέσεις μνήμης.


Όταν μιλάμε για Στοίβα και Ουρά μιλάμε για Αφηρημένους Τύπους Δεδομένων.

Επίσης να ρωτήσω και κάποια πράγματα σχετικά με το πώς ορίζετε τον "Αφηρημένο Τύπο Δεδομένων", για να δω κατά πόσο συμπίπτει με την "Περιγραφή της δομής δεδομένων" που λέω παραπάνω.
  • Ο ΑΤΔ περιλαμβάνει τον καθορισμό της πολυπλοκότητας και των απαιτήσεων μνήμης των λειτουργιών; Ή μόνο το interface, δηλαδή τα prototypes των συναρτήσεων;
  • Ο ΑΤΔ περιλαμβάνει και τους αλγορίθμους των λειτουργιών; (δηλαδή το implementation, το τι ενέργειες πρέπει να γίνουν για να αναζητηθεί ένα στοιχείο της δομής κτλ)
  • Αν δύο δομές έχουν ακριβώς το ίδιο interface αλλά εντελώς τυχαία ΚΑΙ την ίδια πολυπλοκότητα σε όλες τις λειτουργίες τους, τότε θεωρείται ότι πρόκειται για τον ίδιο ΑΤΔ;

Btw, "Τύπο Δεδομένων" δεν λέμε τον ακέραιο, τον πραγματικό κτλ; Μήπως εννοείτε "Αφηρημένη Δομή Δεδομένων" αντί για "Τύπο";

xara_pap

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 127
Απ: Δυναμική δομή δεδομένων
« Απάντηση #19 στις: 08 Μαρ 2011, 12:56:45 πμ »
Απο ό,τι βλέπω σας έβαλα σε μεγάλη συζήτηση και σε καταιγισμό επίδειξης γνωσεων. Εντάξει αφηρημένος τύπος δεδομένων είναι κι αν θέλουμε το υλοποιούμε είτε με πίνακα είτε με δείκτη. Μιλάμε όμως νομίζς στο φόρουμ για αεππ και εφόσον υλοποιείται με πίνακα είναι στατικές.
Ειχαν βάλει ποτε σε πανελλήνιες είτε επαναληπτικές είτε εσπερινου λυκείου για το αν το αρχείο είναι δυναμική δομή δεδομένων σε Σ-Λ? Το ρωτάω γιατί έχω αυτή την υποψία. Σχετικά με τα υπόλοιπα όλοι έχουμε τα βιβλία μπροστά μας και ξέρουμε τι λένε
Φιλικά

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2837
  • Πύργος Ηλείας
Απ: Δυναμική δομή δεδομένων
« Απάντηση #20 στις: 08 Μαρ 2011, 01:17:34 πμ »
Καταρχάς συμφωνώ με τον Άλκη.

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

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

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

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

Εγώ πάντως, όπως είπα, προτείνω ότι αφού το βιβλίο περιγράφει την υλοποίηση μέσω πίνακα, τότε η συγκεκριμένη προσέγγιση θεωρεί την ουρά και στοίβα ως στατική δομή (εντάξει τους αναφέρω ότι θα μπορούσε με άλλου είδους υλοποίηση να θεωρούνται δυναμικές δομές), δηλαδή "οι κόμβοι σε μια στοίβα ή και ουρά είναι Ν, ούτε εισάγονται ούτε διαγράφονται κόμβοι... και οι λειτουργίες ώθηση, απώθηση (εισαγωγή, εξαγωγή στην ουρά), αντιστοιχούν στην λειτουργία της "προσπέλασης". Μόνο που αυτή θα γίνεται αυστηρά στην κορυφή της στοίβας (ή στο εμπρός και πίσω άκρο της ουράς)". Έτσι θεωρώ ότι δεν υπάρχει ασυνέπεια, ούτε ότι διαπράττω επιστημονικό σφάλμα!
« Τελευταία τροποποίηση: 08 Μαρ 2011, 01:53:25 πμ από Νίκος Αδαμόπουλος »

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 810
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Δυναμική δομή δεδομένων
« Απάντηση #21 στις: 08 Μαρ 2011, 01:21:14 πμ »
Btw, "Τύπο Δεδομένων" δεν λέμε τον ακέραιο, τον πραγματικό κτλ; Μήπως εννοείτε "Αφηρημένη Δομή Δεδομένων" αντί για "Τύπο";

Υποθέτω ότι απλά αναφέρεται ως κατα λέξη μετάφραση του ADT (Absrtact Data Type)
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5963
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Δυναμική δομή δεδομένων
« Απάντηση #22 στις: 08 Μαρ 2011, 01:50:34 πμ »
Υποθέτω ότι απλά αναφέρεται ως κατα λέξη μετάφραση του ADT (Absrtact Data Type)

Σωστός, thanks. Βρήκα μια καλή περιγραφή εδώ:
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.

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


Απο ό,τι βλέπω σας έβαλα σε μεγάλη συζήτηση και σε καταιγισμό επίδειξης γνωσεων.

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

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2837
  • Πύργος Ηλείας
Απ: Δυναμική δομή δεδομένων
« Απάντηση #23 στις: 08 Μαρ 2011, 02:07:54 πμ »
Ειχαν βάλει ποτε σε πανελλήνιες είτε επαναληπτικές είτε εσπερινου λυκείου για το αν το αρχείο είναι δυναμική δομή δεδομένων σε Σ-Λ?

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

Επίσης, το:

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

odysseas

  • Ομάδα διαγωνισμάτων 2011
  • *
  • Μηνύματα: 842
Απ: Δυναμική δομή δεδομένων
« Απάντηση #24 στις: 08 Μαρ 2011, 02:39:46 πμ »
Δηλαδή ένας από τους στόχους των ΑΤΔ είναι να "κρύβουν" τις δομές δεδομένων που χρησιμοποιούν για την υλοποίηση των λειτουργιών τους. Άρα δε νομίζω ότι μας ενδιαφέρουν οι ΑΤΔ όταν ο σκοπός μας είναι ακριβώς να διδάξουμε συγκεκριμένες δομές δεδομένων και αλγορίθμους.

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

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

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

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

Άντε, καληνύχτα μας.

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 810
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Δυναμική δομή δεδομένων
« Απάντηση #25 στις: 08 Μαρ 2011, 03:36:30 πμ »
Στην ερώτηση του Νίκου και συγκεκριμένα:
τι ακριβώς από τα παρακάτω κάνετε-προτείνετε για τις ουρές και στοίβες σε διδακτικό-παιδαγωγικό επίπεδο:
εγώ προτείνω το στ: Άλλο.. και θα εξηγήσω στη συνέχεια ακριβώς ΤΙ, αν και νομίζω ότι ο ”ορισμός” του ADT που δίνεται σε επόμενη παράγραφο στο άρθρο που ανέφερε ο Άλκης, το περιγράφει επαρκώς:


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) παρά ως παράδειγμα κάποιου από τα δύο είδη δομών (στατικές - δυναμικές), κάτι σαν .. δομές δεδομένων υψηλού επιπέδου.  Εξάλλου, οι μόνες λειτουργίες που μας απασχολούν για τις συγκεκριμένες δομές είναι η είσοδος και η έξοδος στοιχείου, δύο λειτουργίες που προσδιορίζουν και την ουσιαστική διαφορά ανάμεσά τους, αν θεωρήσουμε πως αυτές (οι δομές) ορίζονται ως:
Στοίβα είναι μία δομή δεδομένων στην οποία τα στοιχεία εξέρχονται με σειρά αντίστροφη από αυτή που εισέρχονται.
Ουρά   είναι μία δομή δεδομένων στην οποία τα στοιχεία εξέρχονται με σειρά την ίδια με αυτή που εισέρχονται.
Δηλαδή ορισμούς που αποδίδουν τη συμπεριφορά χωρίς να ασχολούνται με το θέμα της στατικότητας (ή μη) των δομών.

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

Επομένως πιστεύω πως ο προβληματισμός μας περί της στατικότητας ή δυναμικότητας των συγκεκριμένων δομών, δεν έχει λόγο να υφίσταται. Αφορά καθαρά στην υλοποίηση και όχι στη συμπεριφορά, που είναι και το ζητούμενο από μία στοίβα (ή ουρά) στο πλαίσιο των στόχων του μαθήματος. Εξάλλου, οποιοδήποτε παράδειγμα υλοποίησης, όπως αυτό με τον πίνακα που έχει το σχολικό βιβλίο, έχει ως σκοπό να βοηθήσει στην κατανόηση της συμπεριφοράς της δομής και όχι (ως έμμεση αναφορά) στην κατάταξή της σε μία από τις δύο κατηγορίες δομών (χαμηλότερου επιπέδου).  Και κάπως έτσι απαντώ και στους μαθητές, όταν εκφράζουν αντίστοιχο προβληματισμό.
« Τελευταία τροποποίηση: 08 Μαρ 2011, 09:15:17 πμ από Sergio »
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 810
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Δυναμική δομή δεδομένων
« Απάντηση #26 στις: 08 Μαρ 2011, 09:24:49 πμ »
Μήπως το συγκεκριμένο θέμα ανήκει, καλύτερα, στο χώρο της θεωρίας και όχι σε αυτό των μονοδιάστατων πινάκων ;
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5963
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Δυναμική δομή δεδομένων
« Απάντηση #27 στις: 08 Μαρ 2011, 10:31:42 πμ »
Αν έχω καταλάβει καλά, τα ΑΤΔ ανήκουν σε μια "σχολή" σκέψης, ενώ το βιβλίο μας ανήκει σε άλλη "σχολή", που λέει "Δομές δεδομένων + Αλγόριθμοι = προγράμματα" (κεφάλαιο 3.2 του βιβλίου, παραπομπή σε βιβλίο του Wirth).

Να παραθέσω λίγο πάλι το ιστορικό από το 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

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5963
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Δυναμική δομή δεδομένων
« Απάντηση #28 στις: 08 Μαρ 2011, 10:32:34 πμ »
Θα ήθελα να ρωτήσω αν τα παιδιά πρέπει να γνωρίζουν κάποια δυναμική δομή δεδομένων μίας και το βιβλίο δεν αναφέρει κάτι.

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

Άρα, αν θες μπορείς να αναφέρεις αυτές τις 3 ως παραδείγματα δυναμικών δομών, και να πεις βέβαια ότι είναι εκτός ύλης... :)

xara_pap

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 127
Απ: Δυναμική δομή δεδομένων
« Απάντηση #29 στις: 08 Μαρ 2011, 10:37:29 πμ »
Ευχαριστώ πολύ.
Σχετικά με πριν, ναι ίσως έχετε δίκιο να μην ειναι ευγενικό αλλα συνέχεια αυτό που βλέπω είναι ο ένας να ποσπαθεί να "την πει" στον άλλον και το φόρουμ είναι για να βοηθάει ο ένας τον άλλον. Μερικοι μπορεί να μην ξέρουν τι είναι το ΑΤΔ, είναι όμως και σχεδόν εκτός θέματος γαιτι η θεωρία του αεππ δεν αναφέρει κάτι και το θέμα ειναι να βοηθήσουμε και να μπορέσουμε να απαντήσουμε σύμφωνα με τα δεδομένα και όχι με αυτά που θυμόμαστε.
Φιλικά και συγγνώμη αν προσέβαλα κάποιον.