Πρόσληψη δακτυλογράφου(Άσκηση με κλήση πολλών υποπρογραμμάτων)

[nikolasmer]

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

[nikolasmer]

Δηλαδή:

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

[gthal]

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

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

[gthal]

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

[nikolasmer]

"ποιο είναι το αποτέλεσμα του παραπάνω αλγορίθμου" ή "τι πετυχαίνει ο παραπάνω αλγόριθμος;"

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

[nikolasmer]

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

[nikolasmer]

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

Ένα επαναληπτικό διαγώνισμα σε όλη την ύλη.

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

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

[itt]

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

Η λύση που παρέθεσες πιο κάτω έχει 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²),καθώς μας ενδιαφέρει μόνο ο μεγιστοβάθμιος όρος του πολυωνύμου στην ασυμπτωτική ανάλυση.

[nikolasmer]

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