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

petrosp13

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

theoni

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

din_os

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

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

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

* Οι πηγές επίσης είναι παλιές (ο ίδιος ο Knuth έχει αναφέρει οτι θέλει να ξαναγράψει το 1ο βιβλίο).
« Τελευταία τροποποίηση: 07 Μάρ 2016, 12:18:27 μμ από din_os »

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1317
  • There are always possibilities...
Ας μην ξεχνάμε οτι 99% των βιβλίων είναι μεταφράσεις των αγγλικών (π.χ. Knuth*) στα ελληνικά.Ίσως το ένα βιβλίο να θεωρούσε οτι η αύξηση κατα ένα είναι μία πράξη, το άλλο όχι, όταν τα ενώνεις (μια παράγραφο απο ενα βιβλίο μια παράγραφο απο άλλο) και δεν καταλαβαίνεις το περιεχόμενο έχεις ένα μπάχαλο.
Μπινγκο!
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

theoni

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

GB

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

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

Diotima

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

anta_113

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3147
  • to Iterate is human to Recurse divine
Ο(M*N)

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

Πέτρος Κ.

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

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3147
  • to Iterate is human to Recurse divine
Δεν είναι σωστό αυτό διότι αν υποθέσουμε ότι m = n2, τότε η πολυπλοκότητα γίνεται O(n3) που δεν είναι O(n2),
ενώ για παράδειγμα το O(n) είναι και O(n2) αν και όπως το γράφω είναι λίγο αδόκιμο αφού μιλάμε για σύνολα συναρτήσεων οπότε οι σχέσεις που έχουμε είναι αυτές του υποσυνόλου.

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

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

Πέτρος Κ.

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

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

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

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1317
  • There are always possibilities...
Κατά τη γνώμη μου τέτοιες ερωτήσεις που δεν καθορίζεται ρητά η είσοδος θέλουν προσοχή.
Αν υποθέσουμε ότι η είσοδος είναι τα στοιχεία του πίνακα, ναι μεν γίνονται m*n επαναλήψεις, αλλά τόσα είναι τα στοιχεία έτσι κι αλλιώς. Για κάθε στοιχείο γίνεται μόνο δύο πράξεις διάβασμα και προσπέλαση. Άρα ο αλγόριθμος είναι γραμμικός (ως προς το mn όμως)
« Τελευταία τροποποίηση: 15 Μάρ 2016, 11:18:21 πμ από pgrontas »
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

Diotima

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

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

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

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 655
Καλημερα σε όλους

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

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

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

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

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