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

andreas_p

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 1087

lsourtzo

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 131
O(n*m)

Μα αφού στις οδηγίες λένε ότι οι μαθητές ΔΕΝ πρέπει να ασχοληθούν με τον υπολογισμό της Πολυπλοκότητας Ο
Γιατί να το ρωτήσουν αυτό ?

Vangelis

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



Μα αφού στις οδηγίες λένε ότι οι μαθητές ΔΕΝ πρέπει να ασχοληθούν με τον υπολογισμό της Πολυπλοκότητας Ο
Γιατί να το ρωτήσουν αυτό ?    ???



τελικά θα απαντήσει κανείς σε αυτό ???


Φυσικά και δεν θα το ρωτήσουν
(το ρωτάμε εμείς για να γίνεται συζήτηση, το κακό είναι ότι μπορεί αν τα διαβάζουν και μαθητές και να τρελαίνονται)
 

twisted

  • Θαμώνας
  • ***
  • Μηνύματα: 43
Καλησπέρα στην κοινότητα....

Να κάνω και εγώ μια ερώτηση. Αν έχουμε τη συνθήκη: x <> y ΚΑΙ x >= w + 10 πόσες πράξεις είναι;;;

theoni

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 125
Βαση των συζητήσεων που έχουν γίνει  είναι 4πράξεις μια το <> μια το και  μια το >= και μια το +

twisted

  • Θαμώνας
  • ***
  • Μηνύματα: 43
Μάλιστα, το λογικό λοιπόν.... απλά έλεγα μήπως πρέπει να θεωρήσουμε κάτι διαφορετικό για το >=.... :-\

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 571
  • There can be only one...may it be AEPP.
Αν δε γίνεται πλήρης αποτίμηση λογικών τελεστών; Τι κάνουμε; Με το σύνολο των πράξεων εννοώ .
Μερεντίτης Νικόλαος
Πληροφορικός

Λάμπρος Παπαδόπουλος

  • Βετεράνος
  • ****
  • Μηνύματα: 63
Δεν αναφέρεται πουθενά η μερική αποτίμηση των λογικών εκφράσεων.
Η αποτίμηση των λογικών εκφράσεων είναι πάντα πλήρης.

Γιάννης Αναγνωστάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 846
Πάλι στα πλαίσια της συζήτησης και με την προυπόθεση ότι θα ακολουθηθούν οι οδηγίες, ρωτάω το εξής

Στο http://ebooks.edu.gr/new/classcoursespdf.php?classcode=DSGL-C υπάρχει το διδακτικό πακέτο της ΑΕΠΠ
Μέσα σε αυτό υπάρχει το βιβλίο καθηγητή λπν, που για την ΔΣ1/Σελ. 52/1η άσκηση δίνει ως απάντηση ότι η πολυπλοκότητα ειναι Ο(n)....
Αυτό δεν είναι εντελώς λάθος επιστημονικά; (Δεν αναφέρομαι στο οτι λείπει η αρχική τιμή του i και η εντολή για το βήμα, αλλά στο πως αντιμετωπίζουμε την τάξη πολυπλοκότητας του)

Diotima

  • Επισκέπτης
Φυσικά και είναι λάθος η απάντηση. Η πολυπλοκότητα του αλγορίθμου είναι της τάξης Ο(1) και όχι Ο(n).

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3615
  • to Iterate is human to Recurse divine
Αν μιλάμε για την ΔΣ1 , σελ. 52 , το 1, κατά τη γνώμη μου οι παρακάτω πιθανές απαντήσεις έχουν νόημα:

1) Δεν ορίζεται πολυπλοκότητα διότι δεν είναι αλγόριθμος αφού περιέχει ατέρμων βρόχο.

2) Είναι O( N ) , όπου Ν είναι το πλήθος των επαναλήψεων, το οποίο όμως τείνει στο άπειρο.
Η λογική εδώ είναι ότι αν διπλασιάσουμε το Ν θα διπλασιαστεί και η απόδοση άρα είναι γραμμική η σχέση της απόδοσης με το Ν

Λογικά στο βιβλίο καθηγητή έδωσαν τη 2η απάντηση.

Ο(1) δεν είναι σε καμία περίπτωση αφού δεν μπορούμε να βρούμε σταθερά C στον ορισμό την οποία να θέσουμε ίση με άπειρο, κάτι που είναι μαθηματικά λάθος.

Σε τέτοιες περιπτώσεις που είναι "ακραίες" , ο ορισμός μπορεί να μας βοηθήσει να βγάλουμε άκρη.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Diotima

  • Επισκέπτης
Γράφω τον αλγόριθμο που δίνει η άσκηση:

Όσο i<100 επανάλαβε
  a ← 2*i
Τέλος_επανάληψης

Στην απάντηση στο βιβλίο του καθηγητή (σελ. 140) γράφει:

"Το κομμάτι του αλγορίθμου είναι ένας απλός βρόχος η = 100 επαναλήψεων.
Άρα, η πολυπλοκότητα είναι γραμμική O(n)."

Οπότε υποθέτω ότι έχει ξεχάσει την αύξηση του i, i<-- i+1 μέσα στο βρόχο, όπως και την αρχική τιμή του i.

Με βάση λοιπόν τον ορισμό του βιβλίου για την Ο(1) (σελ.96):

"Ο(1). Κάθε εντολή του προγράμματος εκτελείται μία φορά ή το πολύ μερικές μόνο φορές. Στην περίπτωση αυτή λέγεται ότι ο αλγόριθμος είναι σταθερής πολυπλοκότητας."

και τα παραπάνω ο αλγόριθμος έχει τάξη Ο(1).

Αν παραβλέψουμε την απάντηση στο βιβλίο του καθηγητή, δηλαδή ότι εκτελεί 100 επαναλήψεις και κρίνουμε τον αλγόριθμο όπως δίνεται, τότε θα κάνει είτε καμία είτε άπειρες επαναλήψεις και συμφωνώ με την απάντηση 1) που δίνεις.

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

Η απάντηση όμως που έδωσαν, το να γράφουν ότι ο αλγόριθμος κάνει 100 επαναλήψεις, άρα έχει πολυπλοκότητα Ο(n) είναι επιστημονικό λάθος.
« Τελευταία τροποποίηση: 08 Μαΐ 2016, 02:01:25 μμ από Diotima »

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3615
  • to Iterate is human to Recurse divine
Την απάντηση στο βιβλίο του καθηγητή δεν είχα χρόνο να τη δω. Έτσι όπως το διατυπώνουν έχεις δίκιο, είναι λάθος.
Άρα από την απάντηση που δίνουν μάλλον έχουν ξεχάσει τις εντολές όπως είπες.

Πάντως όταν έλεγα για ορισμό δεν εννοούσα αυτούς του βιβλίου. Εννοώ τον αυστηρό μαθηματικό ορισμό του Ο. Με αυτό δεν υπάρχουν περιθώρια για παρερμηνείες.
Επίσης η απόδοση πολυπλοκότητας σε έναν βρόχο που δεν τερματίζει ποτέ έχει ενδιαφέρον από θεωρητικής πλευράς. Εδώ θα πρέπει να δούμε τον ορισμό.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Diotima

  • Επισκέπτης
Το κατάλαβα ότι αναφέρεσαι στο μαθηματικό ορισμό του Ο που φυσικά δε δίνει περιθώριο για παρερμηνείες. Αποφεύγω τις αναφορές σε αυτόν γιατί είναι εκτός ύλης για τους μαθητές, προσπαθώ να τα εξηγώ με τα εντός ύλης.

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

Λάμπρος Παπαδόπουλος

  • Βετεράνος
  • ****
  • Μηνύματα: 63
Στην ΔΤ1  στο βιβλίο του καθηγητή (σελ 138) γράφει :
"Γενικά, ισχύει ότι κάθε απλός βρόχος έχει γραμμική πολυπλοκότητα,
κάθε διπλός βρόχος έχει τετραγωνική πολυπλοκότητα κοκ."

Οπότε ο/η συγγραφέας των ασκήσεων (και των απαντήσεων) ακολουθούν αυτή την
πρόταση που μπορούμε να χρησιμοποιήσουμε για να υπολογίσουμε "γρήγορα και βρώμικα"
μια πολυπλοκότητα αλλά στη συγκεκριμένη περίπτωση (ΔΣ1) τη χρησιμοποιούν λάθος.
Επίσης δεν καταλαβαίνω γιατί στην απάντηση του ΔΤ2 (σελ 139) χρησιμοποιούν πίνακα με
30 θέσεις.
Επειδή όμως διαβάζουν και μαθητές να διευκρινίσουμε ότι ο υπολογισμός της τάξης ενός αλγορίθμου είναι
εκτός ύλης
« Τελευταία τροποποίηση: 10 Μαΐ 2016, 02:13:32 πμ από Λάμπρος Παπαδόπουλος »