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

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

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

lsourtzo

Παράθεση από: andreas_p στις 05 Απρ 2016, 10:56:57 ΠΜ
O(n*m)

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

Vangelis

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


Παράθεση από: NiColas1957 στις 15 Μαρ 2016, 06:33:16 ΜΜ

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



Παράθεση από: lsourtzo στις 04 Απρ 2016, 01:35:36 ΜΜ
τελικά θα απαντήσει κανείς σε αυτό ???


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

twisted

Καλησπέρα στην κοινότητα....

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

theoni

Βαση των συζητήσεων που έχουν γίνει  είναι 4πράξεις μια το <> μια το και  μια το >= και μια το +

twisted

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

nikolasmer

Αν δε γίνεται πλήρης αποτίμηση λογικών τελεστών; Τι κάνουμε; Με το σύνολο των πράξεων εννοώ .
Μερεντίτης Νικόλαος
Πληροφορικός

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

Δεν αναφέρεται πουθενά η μερική αποτίμηση των λογικών εκφράσεων.
Η αποτίμηση των λογικών εκφράσεων είναι πάντα πλήρης.

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

Πάλι στα πλαίσια της συζήτησης και με την προυπόθεση ότι θα ακολουθηθούν οι οδηγίες, ρωτάω το εξής

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

Diotima

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

evry

Αν μιλάμε για την ΔΣ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) είναι επιστημονικό λάθος.

evry

Την απάντηση στο βιβλίο του καθηγητή δεν είχα χρόνο να τη δω. Έτσι όπως το διατυπώνουν έχεις δίκιο, είναι λάθος.
Άρα από την απάντηση που δίνουν μάλλον έχουν ξεχάσει τις εντολές όπως είπες.

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

Diotima

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

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

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

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

Οπότε ο/η συγγραφέας των ασκήσεων (και των απαντήσεων) ακολουθούν αυτή την
πρόταση που μπορούμε να χρησιμοποιήσουμε για να υπολογίσουμε "γρήγορα και βρώμικα"
μια πολυπλοκότητα αλλά στη συγκεκριμένη περίπτωση (ΔΣ1) τη χρησιμοποιούν λάθος.
Επίσης δεν καταλαβαίνω γιατί στην απάντηση του ΔΤ2 (σελ 139) χρησιμοποιούν πίνακα με
30 θέσεις.
Επειδή όμως διαβάζουν και μαθητές να διευκρινίσουμε ότι ο υπολογισμός της τάξης ενός αλγορίθμου είναι
εκτός ύλης