Θέμα: Υπολογισμός χρόνου εκτέλεσης (υπολογισμός αριθμού πράξεων των εντολών)

[petrosp13]

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

[theoni]

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

[din_os]

Μια εντολή σε assembly δεν είναι απαραίτητα μια πράξη. Θα δεχόμουν ώς μια πράξη την ολίσθηση (χ <- χ * 2, χ <- χ div 2) αλλά για το +-1 πολύ πιθανό να χρησιμοποιεί βοηθητική θέση μνήμης για την πρόσθεση. Καλές οι διατυπώσεις όμως του συναδέλφου και βοηθούν σε περαιτέρω συζήτηση.

Το θέμα βέβαια δεν ειναι πόσο ακριβής είναι ο υπολογισμός του παραδείγματος του βιβλίου. Ας μην ξεχνάμε οτι 99% των βιβλίων είναι μεταφράσεις των αγγλικών (π.χ. Knuth*) στα ελληνικά. Ίσως το ένα βιβλίο να θεωρούσε οτι η αύξηση κατα ένα είναι μία πράξη, το άλλο όχι, όταν τα ενώνεις (μια παράγραφο απο ενα βιβλίο μια παράγραφο απο άλλο) και δεν καταλαβαίνεις το περιεχόμενο έχεις ένα μπάχαλο.

Δυστυχώς κατα τη γνώμη μου, αν πέσει η ίδια ακριβώς άσκηση ο μαθητής πρέπει να βρει σύνολο 32 ενώ για άλλα παραδείγματα πρέπει να κάνει χρήση των τριών βασικών κανόνων στην αρχή του 5.1.1, όπου και θα έβρισκε π.χ. σύνολο 37.  . Θέλω να πιστεύω όμως, όπως προαναφέρθηκε, οτι στις πανελλήνιες αν πέσει τέτοιου είδους άσκηση θα υπάρχει διευκρίνιση στην εκφώνηση.

* Οι πηγές επίσης είναι παλιές (ο ίδιος ο Knuth έχει αναφέρει οτι θέλει να ξαναγράψει το 1ο βιβλίο).

[pgrontas]

Ας μην ξεχνάμε οτι 99% των βιβλίων είναι μεταφράσεις των αγγλικών (π.χ. Knuth*) στα ελληνικά.Ίσως το ένα βιβλίο να θεωρούσε οτι η αύξηση κατα ένα είναι μία πράξη, το άλλο όχι, όταν τα ενώνεις (μια παράγραφο απο ενα βιβλίο μια παράγραφο απο άλλο) και δεν καταλαβαίνεις το περιεχόμενο έχεις ένα μπάχαλο.

Μπινγκο!

[theoni]

Χαίρεται έχω διαβάσει με προσόχη όλα τα παραπάνω αλλά δεν μπορώ να καταλάβω που καταλήξαμε τελικά στην για η αύξηση του ι θα μετράει για μια πράξη στην όσο θα μετράει κανονικά για δυο??

[GB]

Χαίρεται έχω διαβάσει με προσόχη όλα τα παραπάνω αλλά δεν μπορώ να καταλάβω που καταλήξαμε τελικά στην για η αύξηση του ι θα μετράει για μια πράξη στην όσο θα μετράει κανονικά για δυο??

Ναι με βάση το βιβλίο 1 πράξη είναι η αύξηση του μετρητή της ΓΙΑ, και 2 πράξεις το Ι<--Ι+1

[Diotima]

Με την πρώτη ευκαιρία δες και τα βίντεο (με τη σειρά). Αξίζουν.

Είδα τα βίντεο, υπέροχη επιστημονική παρουσίαση από τον Robert Sedgewick, πάρα πολύ αναλυτική και πολύ λεπτομερής για τα θέματα που συζητάμε.
Έκανες πολύ καλά που ανάρτησες τα links, ether.
Είδα και το βιογραφικό του, έκανε το διδακτορικό του με τον Knuth.

[anta_113]

Καλησπέρα.
Θα ήθελα να ρωτήσω ποια είναι η σωστή απάντηση στην ερώτηση: Ποια είναι η πολυπλοκότητα του τμήματος αλγορίθμου
Για i από 1 μέχρι n
   Για j από 1 μέχρι m
       διάβασε Α[i,j]
   Τέλος_επανάληψης
Τέλος_επανάληψης

[evry]

Ο(M*N)

Καλησπέρα.
Θα ήθελα να ρωτήσω ποια είναι η σωστή απάντηση στην ερώτηση: Ποια είναι η πολυπλοκότητα του τμήματος αλγορίθμου
Για i από 1 μέχρι n
   Για j από 1 μέχρι m
       διάβασε Α[i,j]
   Τέλος_επανάληψης
Τέλος_επανάληψης

[Πέτρος Κ.]

Καλησπέρα.
Θα ήθελα να ρωτήσω ποια είναι η σωστή απάντηση στην ερώτηση: Ποια είναι η πολυπλοκότητα του τμήματος αλγορίθμου
Για i από 1 μέχρι n
   Για j από 1 μέχρι m
       διάβασε Α[i,j]
   Τέλος_επανάληψης
Τέλος_επανάληψης

O(n²) αν θες να αναφέρεις κάποια από τις πολυπλοκότητες του βιβλίου.

[evry]

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

O(n²) αν θες να αναφέρεις κάποια από τις πολυπλοκότητες του βιβλίου.

Τέτοιο παράδειγμα φυσικά λίγο δύσκολο να ζητηθεί , ωστόσο η πολυπλοκότητα της συγχώνευσης που είναι στο τετράδιο του μαθητή και στις σημειώσεις είναι O(m+n)

[Πέτρος Κ.]

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

Τέτοιο παράδειγμα φυσικά λίγο δύσκολο να ζητηθεί , ωστόσο η πολυπλοκότητα της συγχώνευσης που είναι στο τετράδιο του μαθητή και στις σημειώσεις είναι O(m+n)

Ναι. Σωστά. Εξάλλου, τώρα που το ξανασκέφτομαι, στο  O(n²) δεν φαίνεται καν ότι η πολυπλοκότητα εξαρτάται και από το m.

[pgrontas]

Κατά τη γνώμη μου τέτοιες ερωτήσεις που δεν καθορίζεται ρητά η είσοδος θέλουν προσοχή.
Αν υποθέσουμε ότι η είσοδος είναι τα στοιχεία του πίνακα, ναι μεν γίνονται m*n επαναλήψεις, αλλά τόσα είναι τα στοιχεία έτσι κι αλλιώς. Για κάθε στοιχείο γίνεται μόνο δύο πράξεις διάβασμα και προσπέλαση. Άρα ο αλγόριθμος είναι γραμμικός (ως προς το mn όμως)

[Diotima]

Κατά τη γνώμη μου τέτοιες ερωτήσεις που δεν καθορίζεται ρητά η είσοδος θέλουν προσοχή.
Αν υποθέσουμε ότι οι είσοδος είναι τα στοιχεία του πίνακα, ναι μεν γίνονται m*n επαναλήψεις, αλλά τόσα είναι τα στοιχεία έτσι κι αλλιώς. Για κάθε στοιχείο γίνεται μόνο δύο πράξεις διάβασμα και προσπέλαση. Άρα ο αλγόριθμος είναι γραμμικός (ως προς το mn όμως)

Συμφωνώ απόλυτα. Θα πρέπει να καθορίζεται από την εκφώνηση το μέγεθος του προβλήματος. Π.χ. σε έναν τετραγωνικό πίνακα nxn μπορείς να θεωρήσεις ως μέγεθος εισόδου τη διάσταση n, οπότε ο παραπάνω αλγόριθμος έχει τάξη Ο(n²), ενώ αν θεωρήσεις ως μέγεθος εισόδου  το πλήθος των στοιχείων του n², τότε είναι γραμμικός ως προς αυτό. Συνηθίζεται όμως για λόγους κατανόησης και αποφυγής παρεξηγήσεων με μονοδιάστατους πίνακες, να θεωρούμε ως μέγεθος εισόδου στους δισδιάστατους πίνακες τις διαστάσεις τους και όχι το πλήθος των στοιχείων τους. Είναι θέμα επιλογής ανεξάρτητης μεταβλητής ως μέγεθος εισόδου, γι αυτό όταν ζητείται συγκεκριμένη απάντηση αυτό θα πρέπει να καθορίζεται απ' την εκφώνηση.
Όταν δεν καθορίζεται, τότε αυτός που απαντά θα πρέπει να αναφέρει τι θεωρεί μέγεθος εισόδου με το οποίο θα εκφράσει την τάξη του αλγορίθμου.

Ναι. Σωστά. Εξάλλου, τώρα που το ξανασκέφτομαι, στο  O(n²) δεν φαίνεται καν ότι η πολυπλοκότητα εξαρτάται και από το m.

Σωστά, το μέγεθος του προβλήματος εδώ εξαρτάται από δύο ανεξάρτητες μεταβλητές, θεωρώντας ότι ο αλγόριθμος επιλύει το πρόβλημα γεμίσματος ενός τυχαίου δισδιάστατου πίνακα nxm, οπότε έχει τάξη Ο(n*m).
Το Ο(n²) θα ίσχυε σε ένα υποσύνολο τέτοιων πινάκων όπου θα ξέραμε ότι οι διαστάσεις τους διατηρούν μια γραμμική σχέση μεταξύ τους, π.χ. m=c1*n + c2, όπου c1, c2 κατάλληλοι σταθεροί ακέραιοι (για c1=0, c2>1 θα είχαμε Ο(n)).

[Λαμπράκης Μανώλης]

Καλημερα σε όλους

σήμερα θα κάνω μία προσπάθεια να διδάξω το κεφάλαιο 5 (και ο Θεός βοηθός) και να ολοκληρώσω την ύλη  ... για να μην ανοίξω άλλο θέμα ρωτάω εδώ, μήπως έχει καταλάβει κάποιος κάτι

1) τελικά η παράγραφος 5.3 είναι μέχρι τον ορισμό της πολυπλοκότητας ?? δηλαδή τις σελίδες 105 κάτω από τον ορισμό μέχρι  την 108 δεν θα τη διδάξουμε ??   αν δεν τα διδάξουμε, το παράδειγμα 2 σελίδα 48 του ΤΜ που προτείνεται από τις οδηγίες αναφέρει την τετραγωνική πολυπλοκότητα αν δεν κάνω λάθος, που έρχεται σε αντίθεση με αυτό 

2)  """ Για τον συμβολισμό Ο της πολυπλοκότητας, δεν πρέπει να αναλυθεί τι ακριβώς εκφράζει και πως υπολογίζεται σε ένα αλγόριθμο.  """ ... ξανά το παραπάνω παράδειγμα του ΤΜ σε αυτό δεν αναφέρεται ??

3) και ένα τρίτο από άλλο κεφάλαιο, αναφέρεται κάπου στις οδηγίες πως η συνάρτηση δεν μπορεί να καλέσει διαδικασία ?? λίγο που έψαξα δεν το βρήκα

πάντως εγώ θεωρώ πως από το κεφάλαιο 5 θα μπεί κάποια θεωρία μέσα από το βιβλίο ή ένας πίνακας υπολογισμός πράξεων ίδιος με αυτόν του βιβλίου