Αποστολέας Θέμα: Μέγεθος πίνακα στην ψευδογλώσσα  (Αναγνώστηκε 37498 φορές)

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1463
  • There are always possibilities...
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #45 στις: 05 Φεβ 2008, 03:55:37 μμ »
Εμένα αυτό που δεν μου αρέσει είναι το εξής:
Λέμε ότι το

Κώδικας: [Επιλογή]
Όσο όνομα<>"τέλος" επανάλαβε
    Διάβασε βαθμός
    μ<-μ+1
    Β[ μ ]<-βαθμός
    ΟΝ[ μ ]<-όνομα
    Διάβασε όνομα
  Τέλος_επανάληψης

δεν είναι σωστό γιατί δεν υπάρχει άνω όριο στοιχείων στον πίνακα.
Δεν θα μπορούσαμε να πούμε όμως ότι δεν μπορεί να αποτελέσει και αλγόριθμο γιατί υπάρχει περίπτωση αν δεν δωθεί τέλος να μην τερματίσει ποτέ;
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 988
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #46 στις: 05 Φεβ 2008, 04:19:50 μμ »
Αυτό δεν έχει σχέση με τη δομή και τον τρόπο χρησιμοποίησης. Το ίδιο θα μπορούσε να συμβεί με

....
Κώδικας: Ψευδογλώσσα
  1. Όσο όνομα<>"τέλος" επανάλαβε
  2.     Διάβασε βαθμός
  3.     Σ <- Σ + βαθμός
  4.     Μ <- Μ + 1
  5.     Διάβασε όνομα
  6. Τέλος_επανάληψης
....

edit:Είχα ξεχάσει το Διάβασε όνομα  :-X

 O Κnuth στον ορισμό της περατότητας αναφέρει ως παράδειγμα της υπολογιστικής διαδικασίας (computational process) την "διαδραστική διαδικασία" (reactive process) ως μια διαδικασία η οποία επικοινωνεί με το περιβάλλον της. Αυτό μας καλύπτει;

Αν κάποιος έχει να προτείνει καλύτερο όρο.. .
« Τελευταία τροποποίηση: 05 Φεβ 2008, 08:08:20 μμ από sstergou »

Michael

  • Βετεράνος
  • ****
  • Μηνύματα: 79
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #47 στις: 05 Φεβ 2008, 11:53:24 μμ »
Πραγματικά... ακόμη κι αν θεωρήσουμε μια σωστή λύση της άσκησης, πώς εξασφαλίζεται η περατότητα του αλγορίθμου ????

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

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

Αν από την άλλη η εκφώνηση δεν επιτρέπει στο χρήστη την εισαγωγή δεδομένων απείρου πλήθους (και καλό θα ήταν η εκφώνηση να το κάνει αυτό και να μην περιμένει από το λύτη να το θεωρήσει προφανές), τότε, δεν είναι απαραίτητη η θεώρηση απειρο-πινάκων από τη μεριά του λύτη. Οι πίνακες που θα χρησιμοποιήσει θα είναι εξ' ορισμού πεπερασμένου μεγέθους, ακόμη κι αν η εκφώνηση δεν θέτει ένα ακριβές άνω όριο στην εισαγωγή δεδομένων από το χρήστη (κάτι που θα μπορούσε να γίνει π.χ. με μια φράση όπως: "ο κατάσκοπος έχει μόνο ένα λεπτό στη διάθεσή του για να εισάγει όσα δεδομένα προλαβαίνει"). Πόσα δεδομένα? Δεν ξέρουμε, σίγουρα όμως θα είναι πεπερασμένα. Ποιο είναι το ακριβές πλήθος των θέσεων που θα έχει ο πίνακάς μας? Δεν ξέρουμε, όμως ούτε τον εξεταστή τον ενδιαφέρει. Διότι αν τον ενδιέφερε, θα μπορούσε πολύ εύκολα να μας αναγκάσει να δηλώσουμε εξ’ αρχής το πλήθος των θέσεων μνήμης που θα δεσμεύσουμε, ζητώντας μας πρόγραμμα σε ΓΛΩΣΣΑ. Υποθέτω ότι το τμήμα δηλώσεων της ΓΛΩΣΣΑΣ δεν βρίσκεται εκεί για διακόσμηση.

Συγνώμη για το μακροσκελές post, η βασική μου ερώτηση είναι η πρώτη: "Ακόμη κι αν θεωρήσουμε μια σωστή λύση της άσκησης, πώς εξασφαλίζεται η περατότητα του αλγορίθμου?"

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

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1463
  • There are always possibilities...
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #48 στις: 06 Φεβ 2008, 09:27:56 πμ »
Μιχάλη με κάλυψες πλήρως δεν θα μπορούσα να το είχα πει καλύτερα.
Να προσθέσω και το εξής:
Εφόσον με την ψευδογλώσσα μπορούμε να περιγράψουμε υπολογιστικές διαδικασίες - αλγορίθμους που δεν τερματίζουν ποτέ, σύμφωνα με το βιβλίο - και εφόσον δεν πρόκειται να εκτελεστούν σε κάποιον υπολογιστή οπότε δεν έχουμε φυσικούς περιορισμούς όπως η μνήμη, γιατί να μην θεωρήσουμε πίνακες με άπειρο μέγεθος. Προφανώς αυτοί οι πίνακες δεν θα είναι οι γνωστές μας περιορισμένες δομές των γλωσσών προγραμματισμού.
Επίσης προσυπογράφω και το παρακάτω:
Παράθεση
Το αρνητικό είναι πως η μεγάλη ελευθερία που παρέχει παρεξηγείται.
Νομίζω πως γι' αυτό ακριβώς συζητάμε κατά βάθος. Ποια είναι τα ακριβή όρια (και ακόμη πιο συγκεκριμένα, τα βαθμολογικά όρια) αυτής της ελευθερίας.
Η ουσία της συζήτησης αυτής είναι τι μπορούμε και τι δεν μπορούμε να κάνουμε στην ψευδογλώσσα.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2468
  • I 'm not young enough to know everything
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #49 στις: 06 Φεβ 2008, 10:41:44 πμ »
Είναι σίγουρα πολύ ενδιαφέρουσες όλες αυτές οι θεωρητικές συζητήσεις. Και είναι ακόμα πιο ωραίο ότι επιτέλους συμμετέχουν και άλλοι εκτός από τους γνωστούς 2-3.

Για μένα θα πρέπει να ξεκαθαρίσουμε κάτι:
Σε καμία περίπτωση δεν πρέπει τα διάφορα μαθηματικά και φιλοσοφικά έξυπνα τεχνάσματα να μας οδηγήσουν σε αδιέξοδο. Υπήρξαν άνθρωποι που θεώρησαν ότι πάμε σε τέλμα λόγω του παραδόξων του Ζήνωνα. Σήμερα ξέρουμε ότι ο Ζήνωνας απλά δεν είχε στη διάθεσή του τη θεωρία για εύρεση αθροίσματος απείρων όρων γεωμετρική προόδου με λ<1.

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

Αν τελικά προκύψει ότι στην ψευδογλώσσα έχει ασάφειες και αφήνει ανοικτό το ενδεχόμενο χρήσης άπειρων πινάκων, τότε το μόνο που θα πετύχουμε είναι να καταργηθεί η ψευδογλώσσα και να ασχοληθούμε μόνο με ΓΛΩΣΣΑ. Πίνακες άπειρου μεγέθους δεν πρόκειται να γίνουν αποδεκτοί διότι θα οδηγήσουμε τη σκέψη των μαθητών πολύ μακριά από την πραγματικότητα  και άρα θα τους κάνουμε κακό.
Ο στόχος είναι να διδάξουμε αλγοριθμική σκέψη στα παιδιά που να έχει συνέχεια στο μέλλον. Η ψευδογλώσσα είναι το μέσο (η λεπτομέρεια) για να το πετύχουμε αυτό.

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

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

Για μένα λοιπόν αν θέλουμε να χρησιμοποιούμε την ψευδογλώσσα σαν εργαλείο εκμάθησης σκέψης και να αποφύγουμε τις τεχνικές λεπτομέρειες κάποιας γλώσσας (πχ ΓΛΩΣΣΑ) θα πρέπει να ξεκαθαρίσουμε με τι πνεύμα τη χρησιμοποιούμε. Δηλαδή θα πρέπει να επιβάλουμε τους περιορισμούς της ΓΛΩΣΣΑΣ στο μέγεθος και τη στατικότητα των δομών. Αντίθετα δε θα δηλώσουμε τις μεταβλητές μια που θέλουμε να γλιτώσουμε τις λεπτομέρειες του περιβάλλοντος. Έτσι θα κρατήσουμε μόνο τις διευκολύνσεις της ψευδογλώσσας και θα αποφύγουμε επιμελώς τα κακά της.

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

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 988
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #50 στις: 06 Φεβ 2008, 04:10:57 μμ »
Κανείς δεν πιστεύω ότι μπορεί να θέλει την χρήση πινάκων απείρου μεγέθους. Μια τέτοια συζήτηση μου φαίνεται περισσότερο φιλοσοφική και όχι πρακτική και προσωπικά δεν με απασχολεί τόσο πολύ.

Μιλάμε για πραγματικά προβλήματα. Στα πραγματικά προβλήματα δεν ξέρεις πάντα κατά την διάρκεια της μεταγλώττισης το ακριβές μέγεθος του πίνακα που πρέπει να χρησιμοποιήσεις. Οπότε έχεις 3 λύσεις
  • Χρησιμοποιείς πίνακες των οποίων το μέγεθος είναι σταθερό ορίζοντας ένα μέγιστο αριθμό θέσεων που καταλαμβάνουν
  • Δηλώνεις μεταβλητό μέγεθος πίνακα όπως το παράδειγμα του 'Αλκη στη C
  • Κάθε φορά που χρειάζεσαι μνήμη την ζητάς και εφόσον υπάρχει διαθέσιμη την παίρνεις. Όταν δεν την χρειάζεσαι την αποδεσμεύεις ή την αποδεσμεύει για σένα ο garbage collector

Ποια είναι η περισσότερο αποδοτική λύση; Ποια λύση "περιορίζει τις δυνατότητες του προγράμματος"; Ποια είναι πιο ρεαλιστική;
Οι πίνακες στην ψευδογλώσσα, από τη στιγμή που δεν δηλώνεις το μέγεθός τους, αναγκαστικά ανήκουν στην τρίτη κατηγορία, όπως ανήκουν και οι πίνακες στην php, την perl και άλλες γλώσσες.

Η δυναμική παραχώρηση μνήμης έχει χρησιμοποιηθεί στους πίνακες χωρίς ο προγραμματιστής να χρειάζεται να ασχοληθεί με pointers, malloc και τα λοιπά.

Είναι δηλαδή καλύτερα να δεσμεύουμε 100000 θέσεις μνήμης για να χρησιμοποιήσουμε μόνο 10;

Στο πρόβλημα : "Να διαβαστούν Ν αριθμοί και να εμφανιστεί το πόσοι είναι μεγαλύτεροι και μικρότεροι από τον μέσο όρο τους " Ποια θα πρέπει να είναι η λύση; Πως θα το λύνατε σε ΓΛΩΣΣΑ; Δεν βλέπω την ψευδογλώσσα σαν το κουτσό αδερφάκι της ΓΛΩΣΣΑΣ. Μάλλον το αντίθετο βλέπω ότι συμβαίνει. Αν μία άσκηση λύνεται και με τα δύο, ποια θα επιλέγατε; Το μόνο που σώνει τη ΓΛΩΣΣΑ είναι τα υποπρογράμματα.


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

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

Πιστεύω ότι αυτό είναι μέσα στο πνεύμα της ψευδογλώσσας και της πληροφορικής γενικότερα. Όταν βγήκε ο πρώτος compiler σε fortran, κάποιοι δεν ήθελαν να τον χρησιμοποιήσουν γιατί παρήγαγε χειρότερο κώδικα assembly από τον αντίστοιχο άνθρωπο assembler. Προφανώς είχαν δίκιο.


« Τελευταία τροποποίηση: 08 Φεβ 2008, 04:39:00 μμ από sstergou »

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1463
  • There are always possibilities...
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #51 στις: 06 Φεβ 2008, 04:40:28 μμ »
Όπως έχω προαναφέρει για την χρήση πίνακα το κριτήριο (για μένα τουλάχιστον) πρέπει να είναι με πόσα δεδομένα ταυτόχρονα ασχολείται ο αλγόριθμος. Ούτε όρια, ούτε τζάμπα μνήμη, ούτε τίποτα. Αν ασχολείται με τα δεδομένα ένα ένα όπως κάνει πχ. σε κάποιο άθροισμα τότε δεν χρειάζεται πίνακα.
Κατά συνέπεια για μένα δεν τίθεται βαθμολογικό θέμα.

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

Για μένα, αφού κάποιος άνθρωπος μπορεί να εκτελεί επ'άπειρον το κόσκινο του Ερατοσθένη και να σημειώνει κάθε πρώτο, δεν βλέπω γιατί να μην μπορούμε να περιγράψουμε την διαδικασία στην ψευδογλώσσα, τοποθετώντας κάθε πρώτο που βρίσκουμε σε έναν πίνακα.

Διευκρίνηση: Δεν συσχετίζω την ψευδογλώσσα με καμία μηχανή ούτε με κάποιο περιβάλλον εκτέλεσης. Την  θεωρώ ως ένα συστηματικό τρόπο συγγραφής οδηγιών.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6150
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #52 στις: 06 Φεβ 2008, 08:24:37 μμ »
Άσχετο αλλά σχετικό:
Τους αλγόριθμους Εισαγωγή_σε_Ουρά και Εξαγωγή_από_Ουρά στη σελίδα 87 του βιβλίου καθηγητή τους έχετε δει;
Με τις ωθήσεις / εξωθήσεις οι δείκτες πηγαίνουν πάντα προς τα δεξιά, δεν γίνεται κύκλος. Έτσι αν βάζουμε/βγάζουμε ένα στοιχείο τη φορά, και κάνουμε πολλές επαναλήψεις, θέλουμε άπειρο πίνακα, ακόμα κι αν στην ουρά βρίσκεται ένα μόνο δεδομένο.

Είναι λάθος του βιβλίου ή όντως στην ψευδογλώσσα αδιαφορούμε για το μέγεθος και λέμε "οκ, κάθε φορά που θέλω να βάλω/βγάλω κάτι μπορώ να ζητήσω μια ακόμα θέση στον πίνακά μου, δε με νοιάζει καθόλου η μνήμη, θεωρώ ότι είναι άπειρη" ;;;

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

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

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 988
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #53 στις: 06 Φεβ 2008, 08:49:14 μμ »
 :D
Τα queue και stack απλά φυτρώνουν εκεί μέσα. Οι εκφωνήσεις πάντως προσπαθούν να μαζέψουν τα ασυμάζευτα. "Η στοίβα αντιπροσωπεύεται από έναν πίνακα μέχρι 100 θέσεων".
Έτσι απλά επειδή το λέει η εκφώνηση ο αλγόριθμος υποχρεούται να το τηρήσει χωρίς εντολές, από μόνος του!!!!

edit:Λες και γράφτηκε πρώτα η λύση και μετά η εκφώνηση.

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6150
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #54 στις: 06 Φεβ 2008, 11:41:28 μμ »
Το κακό είναι ότι και στη θεωρία δεν αναφέρεται το γεγονός ότι οι ουρές πρέπει υποχρεωτικά να είναι κυκλικές, δεν είναι μόνο η λύση προβληματική... Γενικά υπάρχει μια τάση για άπειρους πίνακες!!! :)

Αλεξόπουλος Ανδρέας

  • Θαμώνας
  • ***
  • Μηνύματα: 44
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #55 στις: 06 Φεβ 2008, 11:57:37 μμ »
Το κακό είναι ότι και στη θεωρία δεν αναφέρεται το γεγονός ότι οι ουρές πρέπει υποχρεωτικά να είναι κυκλικές, δεν είναι μόνο η λύση προβληματική... Γενικά υπάρχει μια τάση για άπειρους πίνακες!!! :)

Βέβαια, αν το δεις λίγο καλύτερα, στην υλοποίηση που έχουν για την ουρά δεν χρησιμοποιούν άπειρους πίνακες. Αυτό φαίνεται απλά από τον έλεγχο που λέει ότι πρέπει να κάνουμε για το αν ο δείκτης rear έχει φτάσει στο τέλος του πίνακα και αν έχει φτάσει η εισαγωγή αποτυγχάνει. Αν θεωρήσουμε ότι έχουμε έναν πίνακα άπειρου μεγέθους τότε απλά ο έλεγχος αυτός δεν χρειάζεται καθόλου!
Από όποια πλευρά κι αν το δούμε πάντως ο αλγόριθμος της ουράς όπως παρουσιάζεται και στο βιβλίο τους μαθητή και στο βιβλίο του καθηγητή είναι λάθος. Δηλαδή:
α) αν θεωρήσουμε ότι έχουμε άπειρο πίνακα τότε τα λάθη είναι δυο. Πρώτον δεν υπάρχει πίνακας άπειρου μεγέθους και δεύτερον αν υπήρχε γιατί να κάνουμε τον έλεγχο για το αν έχει γεμίσει;
β) αν θεωρήσουμε ότι ο πίνακας είναι πεπερασμένου μεγέθους (όπως αναφέρει και το βιβλίο του καθηγητή στο παράδειγμα), τότε απλά πρέπει να υλοποιήσουμε την ουρά με κυκλικό πίνακα, γιατί αν δεν κάνω λάθος δεν υπάρχει πουθενά στην θεωρία των δομών δεδομένων υλοποίηση της ουράς με πίνακα συγκεκριμένου μεγέθους ο οποίος δεν είναι κυκλικός.

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

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 6150
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #56 στις: 07 Φεβ 2008, 09:01:49 πμ »
Yeap, Αντρέα έχεις απόλυτο δίκιο, το είχα σημειώσει για τις προτεινόμενες διορθώσεις του βιβλίου αλλά δεν το ξανακοίταξα τώρα και δεν το θυμόμουν καλά.
Παρεπιπτόντως, το size δεν δηλώνεται καν στα δεδομένα του αλγόριθμου...

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2468
  • I 'm not young enough to know everything
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #57 στις: 07 Φεβ 2008, 10:22:20 πμ »
Μιλάμε για πραγματικά προβλήματα. Στα πραγματικά προβλήματα δεν ξέρεις πάντα κατά την διάρκεια της μεταγλώττισης το ακριβές μέγεθος του πίνακα που πρέπει να χρησιμοποιήσεις. Οπότε έχεις δύο λύσεις
  • Χρησιμοποιείς πίνακες των οποίων το μέγεθος είναι σταθερό ορίζοντας ένα μέγιστο αριθμό θέσεων που καταλαμβάνουν
  • Δηλώνεις μεταβλητό μέγεθος πίνακα όπως το παράδειγμα του 'Αλκη στη C
  • Κάθε φορά που χρειάζεσαι μνήμη την ζητάς και εφόσον υπάρχει διαθέσιμη την παίρνεις. Όταν δεν την χρειάζεσαι την αποδεσμεύεις ή την αποδεσμεύει για σένα ο garbage collector

Ποια είναι η περισσότερο αποδοτική λύση; Ποια λύση "περιορίζει τις δυνατότητες του προγράμματος"; Ποια είναι πιο ρεαλιστική;
Οι πίνακες στην ψευδογλώσσα, από τη στιγμή που δεν δηλώνεις το μέγεθός τους, αναγκαστικά ανήκουν στην τρίτη κατηγορία, όπως ανήκουν και οι πίνακες στην php, την perl και άλλες γλώσσες.

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

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

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

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 988
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #58 στις: 07 Φεβ 2008, 02:39:57 μμ »
Δεν είναι δυνατόν να έχεις άλλα πράγματα να ισχύουν στην ψευδογλώσσα και άλλα πράγματα στη ΓΛΩΣΣΑ. Αυτό θα μπερδέψει τους μαθητές.
Συμφωνώ.   :)

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

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

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

π.χ. Θέμα 3 ημερήσια 2005 : "∆ίνεται πίνακας Α[Ν] ακέραιων και θετικών αριθμών..." ,πως θα το λύσω αυτό σε ΓΛΩΣΣΑ;
Αν και αμφιβάλλω αν αυτό μπορεί να γίνει από τη στιγμή που δεν δηλώνεις μέγεθος.

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

Επίσης δε μας ενδιαφέρει το αν κάποια από τις 3 λύσεις είναι πιο αποδοτική από τις άλλες γιατί αυτές οι λύσεις αφορούν τεχνικές λεπτομέρειες και όχι αλγόριθμο (που είναι ο σκοπός του μαθήματος).
Εδώ και αν συμφωνώ... Πρέπει να διδάξουμε αλγοριθμική σκέψη και όχι στατικές-δυναμικές δομές, η java είναι για applets, η lisp για τεχνητή νοημοσύνη. Ο βασικός κορμός του μαθήματος για μένα πρέπει να είναι : πρόβλημα-ανάλυση-αλγόριθμος (σωστός αλγόριθμος, με ότι αυτό συνεπάγεται). Τελικά δεν μπορώ να καταλάβω γιατί πρέπει οι μαθητές να διδάσκονται Ψευδογλώσσα, ΓΛΩΣΣΑ, διαγράμματα ροής, και να έχει το βιβλίο παραδείγματα από BASIC και PASCAL. Λες και πια και είμαστε τόσο χαζοί που πρέπει να να δούμε το ίδιο πράγμα 10 φορές για να το καταλάβουμε. Και κάθε χρόνο οι ίδιες οδηγίες "Οι μαθητές μπορούν να εκφράσουν τη λύση....".

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


edit :
Δηλαδή στο αν θα υιοθετήσουμε δυναμική ή στατική υλοποίηση πίνακα στην ψευδογλώσσα δεν πρέπει να μας ενδιαφέρει ποια είναι πιο αποδοτική υλοποίηση, αλλά ποια μοιάζει στη ΓΛΩΣΣΑ

Γιατί πρέπει σώνει και καλά να μοιάσει η ψευδογλώσσα στην ΓΛΩΣΣΑ και όχι το αντίθετο;
Μήπως γιατί πρέπει να διορθωθούν λιγότερα πράγματα ή γιατί η ΓΛΩΣΣΑ είναι μια γλώσσα "πρότυπο" για τη διδασκαλία αλγορίθμων;
« Τελευταία τροποποίηση: 07 Φεβ 2008, 02:51:07 μμ από sstergou »

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3636
  • to Iterate is human to Recurse divine
Απ: Μέγεθος πίνακα στην ψευδογλώσσα
« Απάντηση #59 στις: 07 Φεβ 2008, 09:23:51 μμ »

  Θα μπορούσες να θεωρήσεις ότι όταν έχεις δεδομένα και αποτελέσματα υλοποιείς υποπρόγραμμα και τα τοποθετείς στις παραμέτρους εισόδου και εξόδου. Το Ν το ορίζεις σαν σταθερά και είσαι οκ.

π.χ. Θέμα 3 ημερήσια 2005 : "∆ίνεται πίνακας Α[Ν] ακέραιων και θετικών αριθμών..." ,πως θα το λύσω αυτό σε ΓΛΩΣΣΑ;
Αν και αμφιβάλλω αν αυτό μπορεί να γίνει από τη στιγμή που δεν δηλώνεις μέγεθος.

Υπερασπίζομαι το παραπάνω θέμα γιατί νομίζω ότι είναι ίσως το καλύτερο που έχει μπει ποτέ σε αυτό το μάθημα.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr