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

Ξεκίνησε από ΣΧΟΙΝΑΣ ΚΩΣΤΑΣ, 27 Δεκ 2015, 09:16:35 ΜΜ

« προηγούμενο - επόμενο »

petrosp13

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

theoni

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

din_os

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

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

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

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

pgrontas

Παράθεση από: din_os στις 07 Μαρ 2016, 11:54:17 ΠΜ
Ας μην ξεχνάμε οτι 99% των βιβλίων είναι μεταφράσεις των αγγλικών (π.χ. Knuth*) στα ελληνικά.Ίσως το ένα βιβλίο να θεωρούσε οτι η αύξηση κατα ένα είναι μία πράξη, το άλλο όχι, όταν τα ενώνεις (μια παράγραφο απο ενα βιβλίο μια παράγραφο απο άλλο) και δεν καταλαβαίνεις το περιεχόμενο έχεις ένα μπάχαλο.
Μπινγκο!
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

theoni

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

GB

Παράθεση από: theoni στις 08 Μαρ 2016, 01:40:40 ΜΜ
Χαίρεται έχω διαβάσει με προσόχη όλα τα παραπάνω αλλά δεν μπορώ να καταλάβω που καταλήξαμε τελικά στην για η αύξηση του ι θα μετράει για μια πράξη στην όσο θα μετράει κανονικά για δυο?????

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

Diotima

Παράθεση από: ether στις 05 Μαρ 2016, 04:59:38 ΜΜ
Με την πρώτη ευκαιρία δες και τα βίντεο (με τη σειρά). Αξίζουν.
Είδα τα βίντεο, υπέροχη επιστημονική παρουσίαση από τον Robert Sedgewick, πάρα πολύ αναλυτική και πολύ λεπτομερής για τα θέματα που συζητάμε.
Έκανες πολύ καλά που ανάρτησες τα links, ether.
Είδα και το βιογραφικό του, έκανε το διδακτορικό του με τον Knuth.

anta_113

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

evry

Ο(M*N)

Παράθεση από: anta_113 στις 12 Μαρ 2016, 03:49:50 ΜΜ
Καλησπέρα.
Θα ήθελα να ρωτήσω ποια είναι η σωστή απάντηση στην ερώτηση: Ποια είναι η πολυπλοκότητα του τμήματος αλγορίθμου
Για i από 1 μέχρι n
   Για j από 1 μέχρι m
       διάβασε Α[i,j]
   Τέλος_επανάληψης
Τέλος_επανάληψης
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Πέτρος Κ.

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

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

evry

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

Παράθεση από: Πέτρος Κ. στις 14 Μαρ 2016, 07:57:17 ΜΜ
O(n2) αν θες να αναφέρεις κάποια από τις πολυπλοκότητες του βιβλίου.

Τέτοιο παράδειγμα φυσικά λίγο δύσκολο να ζητηθεί , ωστόσο η πολυπλοκότητα της συγχώνευσης που είναι στο τετράδιο του μαθητή και στις σημειώσεις είναι O(m+n)
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Πέτρος Κ.

Παράθεση από: evry στις 14 Μαρ 2016, 09:55:40 ΜΜ
Δεν είναι σωστό αυτό διότι αν υποθέσουμε ότι m = n2, τότε η πολυπλοκότητα γίνεται O(n3) που δεν είναι O(n2),
ενώ για παράδειγμα το O(n) είναι και O(n2) αν και όπως το γράφω είναι λίγο αδόκιμο αφού μιλάμε για σύνολα συναρτήσεων οπότε οι σχέσεις που έχουμε είναι αυτές του υποσυνόλου.

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

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

pgrontas

Κατά τη γνώμη μου τέτοιες ερωτήσεις που δεν καθορίζεται ρητά η είσοδος θέλουν προσοχή.
Αν υποθέσουμε ότι η είσοδος είναι τα στοιχεία του πίνακα, ναι μεν γίνονται m*n επαναλήψεις, αλλά τόσα είναι τα στοιχεία έτσι κι αλλιώς. Για κάθε στοιχείο γίνεται μόνο δύο πράξεις διάβασμα και προσπέλαση. Άρα ο αλγόριθμος είναι γραμμικός (ως προς το mn όμως)
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

Diotima

Παράθεση από: pgrontas στις 15 Μαρ 2016, 10:51:57 ΠΜ
Κατά τη γνώμη μου τέτοιες ερωτήσεις που δεν καθορίζεται ρητά η είσοδος θέλουν προσοχή.
Αν υποθέσουμε ότι οι είσοδος είναι τα στοιχεία του πίνακα, ναι μεν γίνονται m*n επαναλήψεις, αλλά τόσα είναι τα στοιχεία έτσι κι αλλιώς. Για κάθε στοιχείο γίνεται μόνο δύο πράξεις διάβασμα και προσπέλαση. Άρα ο αλγόριθμος είναι γραμμικός (ως προς το mn όμως)
Συμφωνώ απόλυτα. Θα πρέπει να καθορίζεται από την εκφώνηση το μέγεθος του προβλήματος. Π.χ. σε έναν τετραγωνικό πίνακα nxn μπορείς να θεωρήσεις ως μέγεθος εισόδου τη διάσταση n, οπότε ο παραπάνω αλγόριθμος έχει τάξη Ο(n2), ενώ αν θεωρήσεις ως μέγεθος εισόδου  το πλήθος των στοιχείων του n2, τότε είναι γραμμικός ως προς αυτό. Συνηθίζεται όμως για λόγους κατανόησης και αποφυγής παρεξηγήσεων με μονοδιάστατους πίνακες, να θεωρούμε ως μέγεθος εισόδου στους δισδιάστατους πίνακες τις διαστάσεις τους και όχι το πλήθος των στοιχείων τους. Είναι θέμα επιλογής ανεξάρτητης μεταβλητής ως μέγεθος εισόδου, γι αυτό όταν ζητείται συγκεκριμένη απάντηση αυτό θα πρέπει να καθορίζεται απ' την εκφώνηση.
Όταν δεν καθορίζεται, τότε αυτός που απαντά θα πρέπει να αναφέρει τι θεωρεί μέγεθος εισόδου με το οποίο θα εκφράσει την τάξη του αλγορίθμου.

Παράθεση από: Πέτρος Κ. στις 15 Μαρ 2016, 08:29:58 ΠΜ
Ναι. Σωστά. Εξάλλου, τώρα που το ξανασκέφτομαι, στο  O(n2) δεν φαίνεται καν ότι η πολυπλοκότητα εξαρτάται και από το m.
Σωστά, το μέγεθος του προβλήματος εδώ εξαρτάται από δύο ανεξάρτητες μεταβλητές, θεωρώντας ότι ο αλγόριθμος επιλύει το πρόβλημα γεμίσματος ενός τυχαίου δισδιάστατου πίνακα nxm, οπότε έχει τάξη Ο(n*m).
Το Ο(n2) θα ίσχυε σε ένα υποσύνολο τέτοιων πινάκων όπου θα ξέραμε ότι οι διαστάσεις τους διατηρούν μια γραμμική σχέση μεταξύ τους, π.χ. m=c1*n + c2, όπου c1, c2 κατάλληλοι σταθεροί ακέραιοι (για c1=0, c2>1 θα είχαμε Ο(n)).

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

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

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

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

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

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

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