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

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

ΠΡΟΣΛΑΜΒΑΝΕΤΑΙ <- ΟΝ[ΣΥΝ3(ΓΙΝΟΜΕΝΟ)]
(κλήση συνάρτησης ως δείκτης σε πίνακα, φυσικά με ακέραιο αποτέλεσμα)

Τρέχει!

Μια ενδεικτική λύση της παραπάνω άσκησης.

Προσπάθησα να εκτελέσω το αντίθετο

ΟΝ[ΣΥΝ3(ΓΙΝΟΜΕΝΟ)] <- ΠΡΟΣΛΑΜΒΑΝΕΤΑΙ
αλλά δεν γίνεται. Εφόσον το αποτέλεσμα της κλήσης της συνάρτησης είναι ακέραιος, γιατί μου βγάζει :
Δεν μπορείτε να χρησιμοποιήσετε το όνομα της συνάρτησης «Σ» στην αρχή μιας εντολής, παρά μόνο μέσα σε εκφράσεις.
ο διερμηνευτής;
???
Δεν είχα ιδέα οτι αυτό δεν εκτελείται!!

Θέλησα να δημιουργήσω συνάρτηση η οποία να δέχεται ενα πίνακα 5χ5 και τον αριθμό μιας γραμμής και να μου επιστρέφει τη θέση του μέγιστου στοιχείου της γραμμής του πίνακα. Στη συνέχεια σε πρόγραμμα να ταξινομώ κατα αύξουσα σειρά τα μέγιστα στοιχεία κάθε γραμμής του πίνακα, με τη βοήθεια της συνάρτησης. Εφόσον λόγω του παραπάνω μου βγάζει συντακτικό λάθος ο διερμηνευτής της γλώσσας,κατα την αντιμετάθεση των στοιχείων, τροποποιώντας τον κώδικα και χρησιμοποιώντας τις βοηθητικές μεταβλητές Κ και Λ τρέχει. Αλλά τα αποτελέσματα δεν είναι τα αναμενόμενα. Νομίζω πως το πρόβλημα είναι να ξαναεισάγω τις καινούριες τιμές του Κ και Λ στις θέσεις των μέγιστων. Δηλάδή μετά το Τέλος_αν μέσα στην Ταξινόμηση να έχω εντολές του στυλ
ΒΑΘ[J - 1, Σ(ΒΑΘ, J - 1)] <- Κ
ΒΑΘ[J, Σ(ΒΑΘ, J)] <- Λ
πράγμα που προφανώς δε γίνεται και δεν έχω ιδέα το τι μπορώ να κάνω.
Αν μπορεί κάποιος ας βοηθήσει γιατί σκάω :(.

Ο κώδικας:

ΠΡΟΓΡΑΜΜΑ Α2
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: I, J, ΒΑΘ[5, 5], TEMP, Κ, Λ
ΑΡΧΗ
  ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ 5
    ΓΙΑ J ΑΠΟ 1 ΜΕΧΡΙ 5
      ΔΙΑΒΑΣΕ ΒΑΘ[I, J]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΙΑ I ΑΠΟ 2 ΜΕΧΡΙ 5
    ΓΙΑ J ΑΠΟ 5 ΜΕΧΡΙ I ΜΕ_ΒΗΜΑ -1
      Κ <- ΒΑΘ[J - 1, Σ(ΒΑΘ, J - 1)]
      Λ <- ΒΑΘ[J, Σ(ΒΑΘ, J)]
      ΑΝ Κ > Λ ΤΟΤΕ
        TEMP <- Κ
        Κ <- Λ
        Λ <- TEMP
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ 5
    ΓΡΑΨΕ ΒΑΘ[I, Σ(ΒΑΘ, I)]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΣΥΝΑΡΤΗΣΗ Σ(Π, ΓΡ): ΑΚΕΡΑΙΑ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ΜΑΧ, Π[5, 5], Θ, J, ΓΡ
ΑΡΧΗ
  ΜΑΧ <- Π[ΓΡ, 1]
  Θ <- 1
  ΓΙΑ J ΑΠΟ 2 ΜΕΧΡΙ 5
    ΑΝ Π[ΓΡ, J] > ΜΑΧ ΤΟΤΕ
      ΜΑΧ <- Π[ΓΡ, J]
      Θ <- J
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  Σ <- Θ
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ    

Παράθεση από: nikolasmer στις 30 Μαρ 2013, 11:07:39 ΠΜ
Προσπάθησα να εκτελέσω το αντίθετο

Κώδικας [Επιλογή] Expand


ΟΝ[ΣΥΝ3(ΓΙΝΟΜΕΝΟ)] <- ΠΡΟΣΛΑΜΒΑΝΕΤΑΙ
αλλά δεν γίνεται. Εφόσον το αποτέλεσμα της κλήσης της συνάρτησης είναι ακέραιος, γιατί μου βγάζει :
Δεν μπορείτε να χρησιμοποιήσετε το όνομα της συνάρτησης «Σ» στην αρχή μιας εντολής, παρά μόνο μέσα σε εκφράσεις.
ο διερμηνευτής;
???
Δεν είχα ιδέα οτι αυτό δεν εκτελείται!!

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

Άλλο ενα Θέμα Δ για επαναληπτικό διαγώνισμα.
Μήπως θα μπορούσε κάποιος να μου απαντήσει τί Πολυπλοκότητας είναι το πρόγραμμα που δημιουργείται ή γενικότερα πώς υπολογίζω την πολυπλοκότητα ενός αλγορίθμου γιατί είμαι εντελώς ανίδεος;! :-[

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

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

Θα έλεγα να μην αγγίξεις το θέμα δτων διαφορών διαδικασιών-συναρτήσεων, μια και δεν προσδιορίζεται στο βιβλίο με σαφήνεια

Να το σβήσω και να αφήσω τα άλλα 2 θέματα θεωρίας ή να την αλλάξω εντελώς; Έχω ξεμείνει από ιδέες.

Καλημέρα σε όλους.
Ήθελα να ρωτήσω αν το παρακάτω παίζει και κάνει αυτό που πρέπει να κάνει.

ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 10
ΚΑΛΕΣΕ ΔΙΑΔ(Χ, Ψ[Ι],Ζ[Ι])
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


όπου Χ πίνακας ως είσοδο και Ψ  και Ζ στοιχεία άλλων πινάκων ως έξοδο.

Παράθεση από: nikolasmer στις 08 Απρ 2013, 12:28:53 ΠΜ
Ένα επαναληπτικό διαγώνισμα σε όλη την ύλη.
Οι παρατηρήσεις σας για τυχόν ασάφειες ή παραλήψεις και γενικότερα αστοχίες είναι πολύ σημαντικές για μένα.
Θα ήθελα ενα σχολιασμό πάνω στο Θέμα.

Στο Α4 και οι δυο για πρέπει να φτάνουν ως το 5. Αλλιώς βγαίνεις εκτός πίνακα...

Παράθεση από: panastros στις 16 Απρ 2013, 10:49:15 ΠΜ
Στο Α4 και οι δυο για πρέπει να φτάνουν ως το 5. Αλλιώς βγαίνεις εκτός πίνακα...

Έχεις δίκαιο. Στο διερμηνευτή το είχα κάνει για πίνακα 10 θέσεων και αργότερα αποφάσισα να μη βάλω τους μαθητές να ταλαιπωρούνται τόσο. Δε θα το παρατηρούσα.Χίλια ευχαριστώ panastros.

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

Διορθώνω τώρα και τα ορθογραφικά μου. Περιμένω σαν απάντηση "την ταξινόμηση του πίνακα". Βέβαια πριν λίγο καιρό δε γνώριζα πως ο αλγόριθμος αυτός είχε όνομα(Ταξινόμηση με επιλογή). :-[
Θα βγάλω εντελώς το MAX  και θα το διορθώσω αφήνωντας μόνο τη θέση.

Δηλαδή:

  ΓΙΑ Κ ΑΠΟ 1 ΜΕΧΡΙ 5
                                                                   ! ΜΑΧ <- Π[Κ]
    Θ <- Κ
    ΓΙΑ I ΑΠΟ Κ + 1 ΜΕΧΡΙ 5
      ΑΝ Π[I] > Π[Θ] ΤΟΤΕ
                                                                    !ΜΑΧ <- Π[I]
        Θ <- I
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    Χ <- Π[Θ]
    Π[Θ] <- Π[Κ]
    Π[Κ] <- Χ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

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

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

Νομίζω ότι θα πρέπει να ρετουσάρεις λίγο και τα μεγάλα σου θέματα (3 και 4)
Τα είδα λίγο βιαστικά - σόρυ δεν έχω χρόνο για περισσότερη λεπτομέρεια - και μπορώ να πω ότι ζαλίστηκα ...  :laugh:  ;)
(ίσως βέβαια φταίει και το ότι βιάζομαι)

Παράθεση από: gthal στις 16 Απρ 2013, 12:24:40 ΜΜ
"ποιο είναι το αποτέλεσμα του παραπάνω αλγορίθμου" ή "τι πετυχαίνει ο παραπάνω αλγόριθμος;"

Έτσι θα το ήθελα από την αρχή.
Θα το αλλάξω τώρα.
Σας ευχαριστώ πάρα πολύ! :)

Όσο για το 4ο θέμα το ξαναείδα και καταλαβαίνω πως δεν είναι και τόσο βατό.
Θα βάλω μια άλλη άσκηση που επεξεργάστηκα.
Και πάλι οποιεσδήποτε διορθώσεις/παρατηρήσεις θα μου ήταν απαραίτητες.

Για κάθε ενδιαφερόμενο

Παράθεση από: nikolasmer στις 08 Απρ 2013, 12:28:53 ΠΜ
Ένα επαναληπτικό διαγώνισμα σε όλη την ύλη.

Επισυνάπτω τις ενδεικτικές λύσεις του παραπάνω μέχρι το Θέμα 3.

Το θέμα 4 άλλαξε και στη θέση του μπήκε το προηγούμενο θέμα με τον τίτλο "ΠΑΝΕΠΙΣΤΗΜΙΟ - ΣΤΑΤΙΣΤΙΚΑ" για το οποίο επισυνάπτω μια ενδεικτική λύση.

Παράθεση από: nikolasmer στις 04 Απρ 2013, 11:23:31 ΠΜ
Άλλο ενα Θέμα Δ για επαναληπτικό διαγώνισμα.
Μήπως θα μπορούσε κάποιος να μου απαντήσει τί Πολυπλοκότητας είναι το πρόγραμμα που δημιουργείται ή γενικότερα πώς υπολογίζω την πολυπλοκότητα ενός αλγορίθμου γιατί είμαι εντελώς ανίδεος;! :-[

Η λύση που παρέθεσες πιο κάτω έχει worst case πολυπλοκότητα O(n x m).


Τώρα για το πώς υπολογίζεις την πολυπλοκότητα :

Ο χρόνος εκτέλεσης ενός αλγορίθμου είναι το πλήθος των στοιχειωδών πράξεων που εκτελούνται.Ας κάνουμε την ολίγον naive παραδοχή πώς ο χρόνος εκτέλεσης κάθε γραμμής του ψευδοκώδικα είναι σταθερός.Θα αναλύσουμε τον αλγόριθμο του insertion sort με βάση αυτή την παραδοχή :


ΙnsertionSort(A)
                                                                                                     
1  Για j <- 2 έως μήκος [A]                                                         
2                 κλειδί <-A[j]
3                   Ενθέτεις το Α[j] στην ταξινομημένη
                             ακολουθία Α[1...j-1]
4                    i <-j-1
5                   Όσο i>0 και A[i] > κλειδί
6                            Α[i+1] <- A[i]
7                             i<-j-1
8                A[i+1] <-κλειδί


Για κάθε  j = 2,3,...,n , όπου n = μήκος[A] ,ἐστω t_j το αντίστοιχο πλήθος εκτελέσεων του ελέγχου του βρόχου Όσο στη γραμμή 5.
Οπότε λοιπόν

      Κόστος      Επαναλήψεις
1      c₁                n
2      c₂                n-1
3      0                 n-1
4      c₄                n-1
5      c₅               Σⁿ_j=2 t_j
6      c₆               Σⁿ_j=2 (t_j-1)
7      c₇               Σⁿ_j=2 (t_j-1)
8      c₈                n-1

Ο χρόνος εκτέλεσης του αλγορίθμου είναι το άθροισμα των χρόνων εκτέλεσης όλων των εντολών που εκτελούνται.Μια εντολή που απαιτεί c_i βήματα και εκτελείται n φορἐς,συνεισφέρει στον ολικό χρόνο εκτέλεσης c_in.
Για να υπολογίσουμε τον Τ(n),τον ολικό χρόνο εκτέλεσης,της Insertion Sort,πολ/σιάζουμε το κάθε στοιχείο της στήλης κόστος με το αντίστοιχο της στήλης επαναλήψεις και αθροίζουμε τα επιμέρους γινόμενα :

Τ(n) =  c₁n + c₂n-1 + c₄n-1+c₅Σⁿ_j=2 t_j + c₆Σⁿ_j=2 (t_j-1) + c₇Σⁿ_j=2 (t_j-1) + c₈ n-1   

Η πολυπλοκότητα worst case στην insertion sort είναι όταν το input είναι ταξινομημένο σε φθίνουσα σειρά.

Για τα αθροίσματα προκύπτει ότι

Σⁿ_j=2 t_j = 1/2 * n(n+1) -1

Σⁿ_j=2 (t_j-1) = 1/2* n(n-1)
Με βάση αυτά βγαίνει ένας αρκετά δύστροπος τύπος για το T(n) του worst case που εν τέλει γράφεται με απλοποιήσεις σε μορφή an²+bn+c.

Oπότε και προκύπτει το O(n²),καθώς μας ενδιαφέρει μόνο ο μεγιστοβάθμιος όρος του πολυωνύμου στην ασυμπτωτική ανάλυση.

Φοβερή η ανάλυσή σου itt.  :D  Θα την κοιτάξω πιο εξονυχιστικά προσεχώς. Σε ευχαριστώ πάρα πολύ.