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

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

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

alkisg

Παράθεση από: xara_pap στις 08 Μαρ 2011, 10:37:29 ΠΜ... ο ένας να προσπαθεί να "την πει" στον άλλον και το φόρουμ είναι για να βοηθάει ο ένας τον άλλον...

Όσο γι' αυτό μην ανησυχείς, οι περισσότεροι που συμμετείχαν ειδικά σε αυτό το θέμα είναι καλοί φίλοι μεταξύ τους. :)

Σπύρος Δουκάκης

Εδώ είναι όλο το ζουμί!

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

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

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

odysseas

Παράθεση από: xara_pap στις 08 Μαρ 2011, 10:37:29 ΠΜ
Σχετικά με πριν, ναι ίσως έχετε δίκιο να μην ειναι ευγενικό αλλα συνέχεια αυτό που βλέπω είναι ο ένας να ποσπαθεί να "την πει" στον άλλον και το φόρουμ είναι για να βοηθάει ο ένας τον άλλον.

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

Σπύρος Δουκάκης

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

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

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

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

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

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

Παράθεση από: Sergio στις 08 Μαρ 2011, 03:36:30 ΠΜ
Με άλλα λόγια, θεωρώ ότι οι δύο δομές για τις οποίες μιλάμε (στοίβα - ουρά) οφείλουν να παρουσιάζονται ως "συμπεριφορές" μάλλον (LIFO, FIFO) παρά ως παράδειγμα κάποιου από τα δύο είδη δομών (στατικές - δυναμικές), κάτι σαν .. δομές δεδομένων υψηλού επιπέδου....

thaaanos

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