ALGORITHMOS
  • Αρχικη
  • Υλικο ΑΕΠΠ
    • Η υλη του μαθηματος
    • Βασικα σημεια θεωριας
    • Θεωρια - Μεθοδολογια >
      • Βασικες γνωσεις
      • Δομη Ακολουθιας
      • Δομη Επιλογης
      • Δομη επαναληψης
      • Μονοδιαστατοι Πινακες
      • Δισδιαστατοι Πίνακες
    • Ασκησεις >
      • Δομη Ακολουθιας >
        • Δομη Ακολουθιας - Λυσεις Ασκησεων
      • Δομη Επιλογης >
        • Δομη Επιλογης - Λυσεις Ασκησεων
      • Δομη Επαναληψης >
        • Δομη Επαναληψης - Λυσεις Ασκησεων
      • Μονοδιάστατοι Πίνακες >
        • Μονοδιαστατοι Πινακες - Λυσεις Ασκησεων
      • Δισδιάστατοι Πίνακες >
        • Δισδιάστατοι Πίνακες - Λυσεις Ασκησεων
      • Υποπρογράμματα
    • Θεματα πανελλαδικων εξετασεων
    • Γλωσσομάθεια
  • Άρθρα
  • Online Test
    • Online Test - Γενικά
    • Online Test - Πανελληνιων
  • Επικοινωνια
Giakoumoglou Vagelis

Κεφάλαιο 5 Ανάλυση Αλγορίθμων

5.1 Επίδοση (Performance) ή αποδοτικότητα (Efficiency) των αλγορίθμων.

Για να μπορέσουμε να κατανοήσουμε τι ακριβώς σημαίνει ο όρος επίδοση ενός αλγορίθμου θα πρέπει πρώτα να απαντήσουμε μερικά ερωτήματα όπως :
  • Πώς υπολογίζεται ο χρόνος εκτέλεσης ενός αλγορίθμου.
  • Πως μπορούν να συγκριθούν μεταξύ τους οι διάφοροι αλγόριθμοι.
  • Πως μπορεί να γνωρίζει κανείς αν ένας αλγόριθμος είναι «βέλτιστος»
Για να απαντήσουμε αυτά τα ερωτήματα θα πρέπει πρώτα να γίνει καταγραφή των ουσιωδών πληροφοριών για το πρόβλημα οι οποίες είναι οι εξής :
  • Αναγνώριση της «χειρότερης» περίπτωσης του αλγορίθμου, και
  • Την αποτύπωση του μεγέθους του προβλήματος  με βάση το πλήθος των δεδομένων .

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

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

5.1.3 Χρόνος εκτέλεσης ενός αλγορίθμου

Έστω ότι έχουμε τον παρακάτω αλγόριθμο:

Αλγόριθμος Παρ_1
S<--0
Για i από 1 μέχρι 400
                Αν i mod 8 = 0 τότε
                                S<--S+i
                Τέλος_αν
Τέλος_επανάληψης
Εμφάνισε ‘ το άθροισμα είναι:’,S
Τέλος Παρ_1
 
Με δεδομένο ότι ο βρόχος του προγράμματος θα πραγματοποιηθεί 400 φορές έχουμε:

Εντολή Αλγορίθμου           Αριθμός πράξεων
Ανάθεση τιμής στο s                       1
Αρχική τιμή i                                     1
Έλεγχος i (στην επανάληψη)        400
Έλεγχος i (στην επιλογή)              400
Αύξηση s                                            50
Αύξηση i (βήμα)                               400
Εμφάνιση αποτελέσματος               1
Σύνολο                                           1253

 
 
 
Ας δούμε και μια διαφορετική λύση για το ίδιο πρόβλημα:
Αλγόριθμος Παρ_2
S<--0
Για i από 8 μέχρι  400 με_βήμα 8
                S<--S+i
Τέλος_επανάληψης
Εμφάνισε ‘το άθροισμα είναι:’,S
Τέλος παρ_2
 
Η ανάλυση εδώ θα έχει ως εξής :
Εντολή Αλγορίθμου                           Αριθμοί πράξεων
Ανάθεση τιμής στο s                                        1
Αρχική τιμή i                                                      1
Έλεγχος i (στην επανάληψη)                          50
Αύξηση s                                                            50
Αύξηση i (βήμα)                                                50
Εμφάνιση αποτελέσματος                               1
Σύνολο                                                            153

 
Βλέπουμε ξεκάθαρα πλέον τι σημαίνει αποδοτικότερος αλγόριθμος και πως ο αριθμός των βρόχων επηρεάζει το χρόνο εκτέλεσης.
Μπορείτε να κατεβάσετε τα παρακάτω αρχεία και να «τρέξετε» τα προγράμματα στη γλωσσομάθεια για να δείτε τη διαφορά στους χρόνους εκτέλεσης.

ΠΑΡ_1.psc
File Size: 0 kb
File Type: psc
Download File

ΠΑΡ_2.psc
File Size: 0 kb
File Type: psc
Download File

5.1.4 Αποδοτικότητα αλγορίθμων
Όταν συγκρίνονται δυο αλγόριθμοι, θα πρέπει  να συγκρίνονται με χρήση των ίδιων δεδομένων και κάτω από τις ίδιες συνθήκες.  
Γενικά, ο χρόνος εκτέλεσης κάθε αλγορίθμου εξαρτάται από ένα σύνολο παραγόντων που μπορούν να συνοψισθούν στους εξής:
  • Τύπος του ηλεκτρονικού υπολογιστή που θα εκτελέσει το πρόγραμμα του αλγορίθμου,
  • Γλώσσα προγραμματισμού που θα χρησιμοποιηθεί,
  • Δομή προγράμματος και δομές δεδομένων που θα χρησιμοποιηθούν,
  • Χρόνος για πρόσβαση στο δίσκο και στις ενέργειες εισόδου εξόδου,
  • Είδος συστήματος , ενός χρήστη ή πολλών χρηστών
Για να έχει έννοια κάθε σύγκριση μεταξύ δυο προγραμμάτων αλγόριθμων , θα πρέπει να ικανοποιούνται οι παρακάτω προϋποθέσεις:
  • Και τα δυο προγράμματα να έχουν συνταχθεί στην ίδια γλώσσα προγραμματισμού,
  • Να έχει χρησιμοποιηθεί ο ίδιος μεταφραστής της γλώσσας προγραμματισμού,
  • Να χρησιμοποιείται η ίδια υπολογιστική πλατφόρμα,
  • Ακριβώς τα ίδια δεδομένα να αποτελούν είσοδο κατά τον έλεγχο των δύο αλγορίθμων.

Ασκήσεις στο κεφάλαιο 5
Κατεβάστε το αρχείο:

Κεφ5_Ασκήσεις.pdf
File Size: 295 kb
File Type: pdf
Download File

Ποιοί είμαστε.
Σχετικά με τη σελίδα
Επικοινωνία
Το υλικό που υπάρχει στη παρούσα ιστοσελίδα , είναι προϊόν προσωπικής εργασίας με στόχο να χρησιμοποιηθεί στην εκπαίδευση και βελτίωση μαθητών στο μάθημα της Ανάπτυξης Εφαρμογών σε Προγραμματιστικό Περιβάλλον.
Θα εκτιμούσα ιδιαίτερα αν επικοινωνήσετε μαζί μου για όποια λάθη βρείτε ή προτάσεις βελτίωσης της σελίδας, στο email που αναφέρεται στη σελίδα επικοινωνίας.
​
              Με εκτίμηση,
         Γιακουμόγλου Βαγγέλης


                                                                                                                         
  • Αρχικη
  • Υλικο ΑΕΠΠ
    • Η υλη του μαθηματος
    • Βασικα σημεια θεωριας
    • Θεωρια - Μεθοδολογια >
      • Βασικες γνωσεις
      • Δομη Ακολουθιας
      • Δομη Επιλογης
      • Δομη επαναληψης
      • Μονοδιαστατοι Πινακες
      • Δισδιαστατοι Πίνακες
    • Ασκησεις >
      • Δομη Ακολουθιας >
        • Δομη Ακολουθιας - Λυσεις Ασκησεων
      • Δομη Επιλογης >
        • Δομη Επιλογης - Λυσεις Ασκησεων
      • Δομη Επαναληψης >
        • Δομη Επαναληψης - Λυσεις Ασκησεων
      • Μονοδιάστατοι Πίνακες >
        • Μονοδιαστατοι Πινακες - Λυσεις Ασκησεων
      • Δισδιάστατοι Πίνακες >
        • Δισδιάστατοι Πίνακες - Λυσεις Ασκησεων
      • Υποπρογράμματα
    • Θεματα πανελλαδικων εξετασεων
    • Γλωσσομάθεια
  • Άρθρα
  • Online Test
    • Online Test - Γενικά
    • Online Test - Πανελληνιων
  • Επικοινωνια