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

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Διορθώνω τώρα και τα ορθογραφικά μου. Περιμένω σαν απάντηση "την ταξινόμηση του πίνακα". Βέβαια πριν λίγο καιρό δε γνώριζα πως ο αλγόριθμος αυτός είχε όνομα(Ταξινόμηση με επιλογή). :-[
Θα βγάλω εντελώς το MAX  και θα το διορθώσω αφήνωντας μόνο τη θέση.
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Δηλαδή:
Κώδικας: [Επιλογή]
  ΓΙΑ Κ ΑΠΟ 1 ΜΕΧΡΙ 5
                                                                   ! ΜΑΧ <- Π[Κ]
    Θ <- Κ
    ΓΙΑ I ΑΠΟ Κ + 1 ΜΕΧΡΙ 5
      ΑΝ Π[I] > Π[Θ] ΤΟΤΕ
                                                                    !ΜΑΧ <- Π[I]
        Θ <- I
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    Χ <- Π[Θ]
    Π[Θ] <- Π[Κ]
    Π[Κ] <- Χ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

gthal

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

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

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 946
Νομίζω ότι θα πρέπει να ρετουσάρεις λίγο και τα μεγάλα σου θέματα (3 και 4)
Τα είδα λίγο βιαστικά - σόρυ δεν έχω χρόνο για περισσότερη λεπτομέρεια - και μπορώ να πω ότι ζαλίστηκα ...  :laugh:  ;)
(ίσως βέβαια φταίει και το ότι βιάζομαι)
Φιλικά,
Γιώργος Θαλασσινός

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
"ποιο είναι το αποτέλεσμα του παραπάνω αλγορίθμου" ή "τι πετυχαίνει ο παραπάνω αλγόριθμος;"
Έτσι θα το ήθελα από την αρχή.
Θα το αλλάξω τώρα.
Σας ευχαριστώ πάρα πολύ! :)
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Όσο για το 4ο θέμα το ξαναείδα και καταλαβαίνω πως δεν είναι και τόσο βατό.
Θα βάλω μια άλλη άσκηση που επεξεργάστηκα.
Και πάλι οποιεσδήποτε διορθώσεις/παρατηρήσεις θα μου ήταν απαραίτητες.
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Για κάθε ενδιαφερόμενο
Ένα επαναληπτικό διαγώνισμα σε όλη την ύλη.
Επισυνάπτω τις ενδεικτικές λύσεις του παραπάνω μέχρι το Θέμα 3.

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

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 429
  • Real stupidity beats ΑΙ any time
Άλλο ενα Θέμα Δ για επαναληπτικό διαγώνισμα.
Μήπως θα μπορούσε κάποιος να μου απαντήσει τί Πολυπλοκότητας είναι το πρόγραμμα που δημιουργείται ή γενικότερα πώς υπολογίζω την πολυπλοκότητα ενός αλγορίθμου γιατί είμαι εντελώς ανίδεος;! :-[

Η λύση που παρέθεσες πιο κάτω έχει 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] ,ἐστω tj το αντίστοιχο πλήθος εκτελέσεων του ελέγχου του βρόχου Όσο στη γραμμή 5.
Οπότε λοιπόν

      Κόστος      Επαναλήψεις
1      c1                n
2      c2                n-1
3      0                 n-1
4      c4                n-1
5      c5               Σnj=2 tj
6      c6               Σnj=2 (tj-1)
7      c7               Σnj=2 (tj-1)
8      c8                n-1

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

Τ(n) =  c1n + c2n-1 + c4n-1+c5Σnj=2 tj + c6Σnj=2 (tj-1) + c7Σnj=2 (tj-1) + c8 n-1   

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

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

Σnj=2 tj = 1/2 * n(n+1) -1

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

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

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Φοβερή η ανάλυσή σου itt.  :D  Θα την κοιτάξω πιο εξονυχιστικά προσεχώς. Σε ευχαριστώ πάρα πολύ.
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής