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

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

Το παράδειγμα αυτό σε Fortran:

      PROGRAM TEST
      INTEGER A(10), B(5)

      DO I=1,10
        A(I) = I
      END DO
      DO I=1,5
        B(I) = I**2
      END DO
      CALL PRINT_TABLE(A, 10)
      CALL PRINT_TABLE(B, 5)
      
      END PROGRAM TEST
      
      SUBROUTINE PRINT_TABLE(T, N)
      INTEGER T(N)
      
      DO I=1,N
        PRINT *, T(I)
      END DO
      END SUBROUTINE PRINT_TABLE

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

Αλγόριθμος Μέσος_Όρος
!σελ. 31 τετραδίου μαθητή
S <- 0
Για i από 1 μέχρι 105
  Διάβασε M[i]
  κτλ

και να μην επιτρέπεται το

Αλγόριθμος Μέσος_Όρος
S <- 0
Διάβασε Ν
Για i από 1 μέχρι Ν
  Διάβασε M[i]
  κτλ

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

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

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

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

Έστω ότι μπαίνουν εντός ύλης οι λίστες...
Πως θα εξηγήσουμε σε έναν μαθητή την διαφορά μίας λίστας από έναν πίνακα;

Όταν μπουν η κουβέντα θα πάρει φωτιά ...

Μαλλον γιαυτό δεν έχουν μπει.

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

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

Οπότε Βαγγέλη μην ανησυχείς (αρκεί βέβαια να μην εννοεί ο ʼλκης κάτι διαφορετικό από αυτό που κατάλαβα). Το ερώτημα που θέτεις για διαφορά λίστας και πίνακα, θα χρειαζόταν να απαντηθεί στην περίπτωση που είχαμε περιβάλλον με δυναμικό πίνακα. (Η απάντηση θα στηριζόταν στις επιτρεπόμενες πράξεις πχ στην άμεση προσπέλαση σε πίνακες αλλά όχι λίστες κλπ κλπ αλλά αυτά τώρα είναι εκτός θέματος). 

Κι εγώ συμφωνώ ότι είναι στατική δομή (εννοείται, εξ' ορισμού). Ακόμα κι αν η ψευδογλώσσα υποστήριζε επαναπροσδιορισμό του μεγέθους ενός πίνακα (redim) όπως άλλες γλώσσες, πάλι στατική θα ήταν.
Επίσης στατική δομή θα ήταν αν το μέγεθος του πίνακα οριζόταν στη μέση της εκτέλεσης, π.χ.
Διάβασε Ν
Α[Ν] <- 5 !Εδώ αποφασίσαμε μια και καλή ότι ο πίνακας έχει Ν στοιχεία
Αυτό το υποστηρίζουν αρκετές γλώσσες, δεν είναι κάτι περίεργο. Δηλαδή μπορεί να μπει μεταβλητή για να δηλώσει το μέγεθος ενός πίνακα στη μέση της εκτέλεσης. Ο πίνακας θεωρείται ότι δηλώνεται ακριβώς σε αυτήν τη γραμμή (όχι από την αρχή της εκτέλεσης), και το μέγεθός του δεν μπορεί να αλλάξει στη συνέχεια.

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

Οι λίστες έχουν και pointers (και στο βιβλίο), οπότε αν μπουν στην ύλη θα μπορέσουμε να τα εξηγήσουμε μια χαρά... Το θέμα είναι αν φτάνει ο χρόνος για να διδάξουμε και δείκτες (και records).

ΠαράθεσηΣτη λύση που παρουσιάζει ο Μιχάλης το μέγεθος πρέπει να αλλάζει κατά τη διάρκεια εκτέλεσης και άρα παραβιάζει τη στατικότητα της δομής.

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

Η τεράστια λευκή κόλλα χωράει ένα πολύ μεγάλο αλλά πεπερασμένο πλήθος αριθμών. Ούτε με τη λευκή κόλλα αλλά ούτε με πολλές τέτοιες λύνεται το πρόβλημα στη γενική του περίπτωση. Ο αλγόριθμος δεν είναι μόνο κάτι πρακτικής σημασίας. Έχει και θεωρητικό υπόβαθρο από πίσω του. Σα μαθηματικός νομίζω ότι θα με καταλάβεις.  Θέλω τη γενική λύση του προβλήματος.

Δεν ξέρω αν είναι εύστοχο το παράδειγμα που θα δώσω.

Στα μαθηματικά μπορεί με τη βοήθεια υπολογιστή να ελέγξουμε ότι μια πρόταση ισχύει για ένα τεράστιο πλήθος αριθμών (πχ εικασία Goldbach). Αλλά δε μας αρκεί. Θέλουμε την απόδειξη ότι ισχύει στη γενική περίπτωση. Γι αυτό δαπανήθηκε τόσο κόπος για την απόδειξη του τελευταίου θεωρήματος του Fermat. Καμία εφαρμογή δεν έχει σήμερα το ότι αποδείχτηκε το θεώρημα του Fermat. Αλλά τη θέλαμε την απόδειξη γιατί τότε μόνο θα πούμε ότι λύσαμε το πρόβλημα. Κάπως έτσι…

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

Μιας και είμαστε στο θέμα, να παραθέσω κι ένα παράδειγμα που είναι αποδεκτό σε C:

#include <stdio.h>

int main()
{
  int N;

  scanf("%d", &N); //Διαβάζουμε το μέγεθος του πίνακα από το χρήστη
  {
    int A[N]; //Και έτσι το μέγεθος του πίνακα ορίζεται κατά την εκτέλεση
    
    for (int i = 0; i < N; i++)
      scanf("%d", A[i]); //Διάβασμα των Ν στοιχείων του πίνακα
  }
  return 0;
}

Είναι το παραπάνω αποδεκτό σε ψευδογλώσσα; (προφανώς χωρίς τις δηλώσεις)
Κι αν όχι, γιατί; Ποια είναι η ειδοποιός διαφορά;

Εντωμεταξύ προφανώς το
Αλγόριθμος Δοκιμή
Δεδομένα // table, N //

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

Εγώ νομίζω ότι μπερδεύτηκα λίγο:

Τι διαφορά έχει το

μ<-μ+1
Β[ μ ]<-βαθμός
ΟΝ[ μ ]<-όνομα

από το

Διάβασε Ν
Α[Ν] <- 5 !Εδώ αποφασίσαμε μια και καλή ότι ο πίνακας έχει Ν στοιχεία

Θα μπορούσε δηλαδή και στην αρχική εκδοχή του Μιχάλη σε κάθε επανάληψη να ξαναδημιουργείται ο πίνακας με μέγεθος το καινούριο μ. Δηλαδή στατική δομή,  αλλά με νέο μέγεθος σε κάθε επανάληψη (όπως το redim preserve της VB - δεν ξέρω πώς υλοποιείται αλλά δίνει αίσθηση στατικής δομής).
Γιατί η ερμηνεία του ότι το μέγεθος του πίνακα προσδιορίζεται από την μέγιστη τιμή του πλήθους είναι ασύμβατη με αυτό;

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

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

Πάντως στο βιβλίο αναφέρεται ότι :

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

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


Το παράδειγμα σε C επιτρέπεται σε compilers που υλοποποιούν το πρότυπο C99 δηλαδή εμφανίστηκε μετά το 1999. Φαντάζομαι πάντως πως αν και το μέγεθος καθορίζεται κατά τη διάρκεια της εκτέλεσης,αυτό δεν σημαίνει ότι μπορεί και να αλλάξει. Δεν μπορείς δηλαδή να πεις Α[Ν+1]=1.

edit: http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=215
http://publib.boulder.ibm.com/infocenter/pseries/v5r3/index.jsp?topic=/com.ibm.xlcpp8a.doc/language/ref/variable_length_arrays.htm

Η διαφορά με την ψευδογλώσσα είναι ότι δεν δηλώνεις το μέγεθος του πίνακα. Οπότε το

Διάβασε μ
Α[μ]=1;
Α[μ+1]=2;

Όχι μόνο καθορίζει το μέγεθος του πίνακα κατά τη διάρκεια της εκτέλεσης αλλά και το αλλάζει ταυτόχρονα.

Νομίζω ότι έχουμε 3 περιπτώσεις:

• Το μέγεθος του πίνακα πρέπει να καθοριστεί την στιγμή της μεταγλώτισης
• Το μέγεθος του πίνακα μπορεί να καθοριστεί κατά την διάρκεια της εκτέλεσης αλλά δεν μπορεί να αλλάξει
• Το μέγεθος του πίνακα μπορεί να καθοριστεί και να αλλάξει κατά την διάρκεια της εκτέλεσης

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

ΠαράθεσηΔηλαδή στατική δομή,  αλλά με νέο μέγεθος σε κάθε επανάληψη.

Νομίζω πως το νόημα της στατικής δομής είναι ακριβώς το αντίθετο. Ότι δηλαδή δεν αλλάζει. Εάν άλλαζε τότε τι σόι στατική δομή είναι (!!).

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

ΠαράθεσηΝομίζω πως το νόημα της στατικής δομής είναι ακριβώς το αντίθετο. Ότι δηλαδή δεν αλλάζει. Εάν άλλαζε τότε τι σόι στατική δομή είναι (!!).

Μάλλον δεν εξέφρασα σωστά αυτό που σκεφτόμουν (μου συμβαίνει συχνά)
Το μέγεθος δεν αλλάζει μέσα στην επανάληψη. Στο επόμενο loop θα χρησιμοποιηθεί μία ΚΑΙΝΟΥΡΙΑ δομή με μέγεθος +1 και σταθερό μέγεθος για όλη την διάρκεια ζωής της κόκ.

Είναι λίγο δύσκολο να εκφράσουμε με παραδείγματα όλες τις διαφορετικές περιπτώσεις.

Το
Διάβασε μ
Α[μ] <- κάτι
δε σημαίνει απαραίτητα ότι αποφάσισα ότι ο πίνακας Α έχει μ στοιχεία, μπορεί να αποφάσισα ότι έχει 2*μ στοιχεία και να χρησιμοποιώ τα υπόλοιπα παρακάτω.

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

Αλγόριθμος ΔιαβάζωΈνανΠίνακαΚαιΕπιστρέφωΤηΔιασπορά
Δεδομένα // Ν //
Για ι από 1 μέχρι Ν
  Διάβασε Α[ι]
  υπολόγισε τη διασπορά κτλ
Αποτελέσματα // διασπορά //
Τέλος ΔιαβάζωΈνανΠίνακαΚαιΕπιστρέφωΤηΔιασπορά

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

Αλγόριθμος ΒρεςΚάμποσεςΔιασπορές
Διάβασε Ν
διασπορά1 <- ΔιαβάζωΈνανΠίνακαΚαιΕπιστρέφωΤηΔιασπορά(Ν)
!Δημιουργείται (και καταστρέφεται στο τέλος της κλήσης) πίνακας Ν στοιχείων
διασπορά2 <- ΔιαβάζωΈνανΠίνακαΚαιΕπιστρέφωΤηΔιασπορά(2*Ν)
!Δημιουργείται (και καταστρέφεται στο τέλος της κλήσης) πίνακας 2*Ν στοιχείων
Τέλος ΒρεςΚάμποσεςΔιασπορές

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


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

Παράθεση από: sstergou στις 25 Ιαν 2008, 04:42:40 ΜΜ
Ελπίζω στο επόμενο βιβλίο να εφεύρουν μια γλώσσα που να μπορεί να εκτελεστεί έτσι όπως την περιγράφουν.

Αμήν!