Αποστολέας Θέμα: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η  (Αναγνώστηκε 6804 φορές)

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 887
Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« στις: 12 Νοέ 2015, 11:28:52 μμ »
Έστω πίνακας Α 100 ακεραίων και θέλουμε να εμφανίσουμε το άθροισμα των στοιχείων του ανά δεκάδα, δηλαδή
Α[1]+Α[2]+Α[3]+ ... +Α[9]+Α[10] = ?
Α[11]+Α[12]+Α[13]+ ... +Α[19]+Α[20] = ?
...
Α[91]+Α[92]+Α[93]+ ... +Α[99]+Α[100] = ?

Δίνονται δύο αλγόριθμοι που επιλύουν το παραπάνω πρόβλημα

Αλγόριθμος λύση_1
Δεδομένα // A //
Για i από 0 μέχρι 9
  S <- 0
  Για j από 1 μέχρι 10
    S <- S +A[i*10+j]
  Τέλος_επανάληψης
  Εμφάνισε S
Τέλος_επανάληψης
Τέλος λύση_1
                         Αλγόριθμος λύση_2
Δεδομένα // A //
S <- 0
Για i από 1 μέχρι 100
  S <- S + A[ i ]
  Αν i mod 10 = 0 τότε
    Εμφάνισε S
    S <- 0
  Τέλος_αν
Τέλος_επανάληψης
Τέλος λύση_2

Θεωρώ ότι χοντρικά και οι δύο κάνουν το ίδιο πλήθος πράξεων (ο 1ος καθυστερεί για τον υπολογισμό του δείκτη, ο δεύτερος καθυστερεί για τον έλεγχο της συνθήκης της Αν)
Ισχύει ότι ο πρώτος είναι O(n2)  και ο δεύτερος O(n)  ?
και τότε τι σημαίνει αυτό για τον δεύτερο? ότι είναι καλύτερος?
Φιλικά,
Γιώργος Θαλασσινός

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #1 στις: 13 Νοέ 2015, 02:05:48 μμ »
Αν υποθέσουμε ότι τα δεδομένα είναι Μ = Ν2
τότε και οι δυο αλγόριθμοι έχουν πολυπλοκότητα στη χειρότερη περίπτωση
O(M) = O(N*N) = O(N2)

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

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2213
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #2 στις: 13 Νοέ 2015, 02:13:37 μμ »
Αν δεν ζητηθεί πλήθος πράξεων στις εξετάσεις, τότε τι θα ζητηθεί, εφόσον στην φετινή ύλη ορίζεται ότι δεν θα ζητηθεί από τους μαθητές να προσδιορίσουν την τάξη του αλγορίθμου;;;
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #3 στις: 13 Νοέ 2015, 05:23:00 μμ »
Η γνώμη μου είναι πως αν δεν μπορεί να ζητηθεί η τάξη ενός αλγορίθμου δεν μπορεί να ζητηθεί τίποτα άλλο, πόσο μάλλον ο επακριβής υπολογισμός των πράξεων που γίνονται.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #4 στις: 13 Νοέ 2015, 07:07:35 μμ »
Οι δύο αλγόριθμοι που παρουσιάζεις έχουν ακριβώς την ίδια πολυπλοκότητα, Ο(n). (Ακόμη πιο σωστά, θα έπρεπε να πούμε ότι έχουν πολυπλοκότητα Θ(n), αφού στο παράδειγμά σου δεν υπάρχει καλύτερη και χειρότερη περίπτωση. Οι αλγόριθμοι θα κάνουν ακριβώς τον ίδιο χρόνο με ότι δεδομένα και να τους τρέξουμε.)
Ο πρώτος αλγόριθμος, σε καμιά περίπτωση δεν είναι Ο(n^2). Δεν αρκεί να έχεις φωλιασμένους βρόγχους για να γίνει η πολυπλοκότητα τετραγωνική.
Ο δεύτερος αλγόριθμος είναι πολύ χειρότερος από τον πρώτο. Αυτό δεν οφείλεται στην Αν (η οποία και αυτή έχει κόστος) αλλά στην διαίρεση που κάνεις στην συνθήκη της Αν.

Αν δύο αλγόριθμοι έχουν την ίδια πολυπλοκότητα (χρόνου εκτέλεσης) δεν σημαίνει ότι έχουν και την ίδια απόδοση (τον ίδιο χρόνο εκτέλεσης). Η πολυπλοκότητα μετράει την συμπεριφορά του αλγόριθμου καθώς αυξάνεται γραμμικά το μέγεθος των δεδομένων. Δηλαδή, αν για για n δεδομένα ο αλγόριθμος χρειάζεται χρόνο 1, τότε τι χρόνο χρειάζεται για 2n, 3n, 4n, ... μέγεθος δεδομένων; Ο αλγόριθμος συγκρίνεται με τον εαυτό του καθώς αυξάνει το μέγεθος των δεδομένων, δεν συγκρίνεται με άλλους αλγόριθμους.

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 887
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #5 στις: 14 Νοέ 2015, 02:34:21 μμ »
Ευχαριστώ για τις απαντήσεις σας!

Ο πρώτος αλγόριθμος, σε καμιά περίπτωση δεν είναι Ο(n^2).
Διαισθητικά συμφωνώ μαζί σου apoldem, αφού υπάρχει ισοδύναμος γραμμικός αλγόριθμος, θα πρέπει κι αυτός να θεωρείται O(n).
Όμως κι ο evry παραπάνω με είχε πείσει ότι έχουν την ίδια πολυπλοκότητα n2 με την έννοια ότι:
σ' αυτό το στιγμιότυπο του προβλήματος έχουμε 10 δεκάδες, σ' ένα άλλο 100 εκατοντάδες και γενικά σε κάποιο άλλο Ν Ν-άδες
Άρα ο ένας αλγόριθμος θα το λύσει με 2 εμφωλευμένες δομές που θα κάνουν Ν επαναλήψεις η καθεμιά - άρα Ν*Ν
ενώ ο άλλος θα το λύσει γραμμικά με μία δομή που θα κάνει Μ επαναλήψεις, όπου Μ=Ν*Ν
Οπότε είναι και οι δύο Ο(Ν2)
Έτσι, δεν ξέρω με ποια εξήγηση να πάω....

Δεν αρκεί να έχεις φωλιασμένους βρόγχους για να γίνει η πολυπλοκότητα τετραγωνική.
Σωστό μου ακούγεται και αναρωτιέμαι.... αλήθεια, τι αρκεί ??  (χάριν της θεωρητικής τεκμηρίωσης)

Ακόμα, αν καταλαβαίνω σωστά τη λογική που περιγράφεις και τη χρησιμοποιήσω παρακάτω, μπορώ να αποδείξω ότι η φυσαλίδα είναι Ο(Ν) !!!
Ας πάρω την "έκδοση" της φυσαλίδας που δίνει το τετράδιο του μαθητή στο παράδειγμα 3, σελ 49 (που είναι "λίγο χειρότερη" από τη γνωστή φυσαλίδα):
Για i από 1 μέχρι N-1
  Για j από 1 από N-1
    ...

      που γράφεται ισοδύναμα:     
Για k από 1 μέχρι (Ν-1)^2
  i ← (k-1) div (Ν-1) +1
  j ← (k-1) mod (Ν-1) +1
  ...

Άρα με βάση τα προηγούμενα, δεν αρκεί το ότι η φυσαλίδα γίνεται με φωλιασμένες επαναλήψεις. Αφού μπορεί να γίνει και γραμμικά, είναι Ο(Ν)
(αλλά, βέβαια με ένα Ν που είναι ... της τάξης Ν2   :laugh: )

Οπότε... πού καταλήγουμε ?
Φιλικά,
Γιώργος Θαλασσινός

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #6 στις: 14 Νοέ 2015, 06:22:16 μμ »
Η πολυπλοκότητα υπολογίζεται συγκρίνοντας τον χρόνο εκτέλεσης του αλγόριθμου καθώς μεγαλώνει το μέγεθος των δεδομένων.

Ερ. Ο πρώτος αλγόριθμος, πως θα συμπεριφερθεί αν του δώσουμε τα διπλάσια δεδομένα (πίνακα 200 θέσεων);
Απ. Θα κάνει τον διπλάσιο χρόνο.

Συνεπώς η πολυπλοκότητα είναι γραμμική Ο(n).

Δεν έχει σημασία το αρχικό μέγεθος των δεδομένων. Αρκεί να δεις πως αυξάνεται ο χρόνος εκτέλεσης καθώς αυξάνεις γραμμικά τα δεδομένα (2n, 3n, ...). Ο ένας αλγόριθμος έχει δύο φωλιασμένους βρόγχους από 0 έως sqrt(n) ο καθένας, σύνολο n επαναλήψεις. Ο άλλος έχει έναν βρόγχο, n επαναλήψεων από την αρχή.

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1316
  • There are always possibilities...
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #7 στις: 14 Νοέ 2015, 06:37:50 μμ »
Σε κάθε περίπτωση η πολυπλοκότητα είναι ευθέως ανάλογη του πλήθους των δεδομένων, δηλαδή γραμμική.
O evry και o apoldem λένε το ίδιο πράγμα και έχουν φυσικά δίκιο.

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

A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 887
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #8 στις: 15 Νοέ 2015, 02:12:41 πμ »
Ερ. Ο πρώτος αλγόριθμος, πως θα συμπεριφερθεί αν του δώσουμε τα διπλάσια δεδομένα (πίνακα 200 θέσεων);
Απ. Θα κάνει τον διπλάσιο χρόνο.
Α, αυτό το κάνει ξεκάθαρο! Ευχαριστώ!

Γιώργο, αυτό που σε μπερδεύει είναι ότι πας να υπολογίσεις την πολυπλοκότητα με βάση τον εμφωλευμένο βρόχο, ο οποίος όμως αφορά τις δεκάδες (ν-αδες) στις οποίες διαιρείς τα δεδομένα και όχι με βάση το μέγεθος της εισόδου
Κατάλαβα τι λες Παναγιώτη. Ευχαριστώ!
Φιλικά,
Γιώργος Θαλασσινός

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 887
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #9 στις: 16 Νοέ 2015, 12:52:10 μμ »
Παναγιώτη επανέρχομαι στο σημείο που τόνισες γιατί δαβάζοντας το παράδειγμα 2 σελ 48 του τετραδίου του μαθητή μπερδεύτηκα πάλι...

Έστω 1600 στοιχεία που θέλω να επεξεργαστώ.
Μπορώ να τα αποθηκεύσω σαν μονοδιάστατο 1600 στοιχείων ή δισδιάτατο 40Χ40 ή 16Χ100 ή 160Χ10 κλπ κλπ κλπ
Και πάλι, ενώ τα στοιχεία είναι 1600, μπορώ να τα "διαιρέσω" σε 40-άδες, 100-άδες, 10-άδες κοκ
οπότε για την πολυπλοκότητα δεν θα έπρεπε να παίζει ρόλο αυτό αλλά το μέγεθος της εισόδου, το 1600
Στο παράδειγμα 2 όμως που αναφέρω κάνει το ίδιο πράγμα σε έναν πίνακα ΝΧΝ και καταλήγει ότι ο αλγόριθμος είναι τετραγωνικός!

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

Άρα η επεξεργασία δισδιάστατου πίνακα μου μοιάζει να μην είναι απαραίτητα Ν^2 έτσι?
Όμως η φυσαλίδα απαραίτητα είναι.
Ή το πρόβλημα της αναζήτησης κάθε στοιχείου ενός πίνακα Α, Ν στοιχείων σε έναν πίνακα Β, Μ στοιχείων? Μου φαίνεται ότι τετραγωνικής πολ/κότητας - δεν ξέρω γιατί... εδώ ποιο είναι το μέγεθος? Ν ή Μ? ή και τα δύο ? ή ΝΧΜ ? και αν 2πλασιάσω το μέγεθος, πώς αυξάνει η πολυπλοκότητα?
Φιλικά,
Γιώργος Θαλασσινός

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #10 στις: 16 Νοέ 2015, 01:59:22 μμ »
Παρά το ότι απευθύνεσαι στον Παναγιώτη, πήρα το θάρος να επέμβω. Κατέβασα και διάβασα το παράδειγμα 2 του Βιβλίου Μαθητή και έφριξα! Τώρα καταλαβαίνω γιατί προσθέτεις όλες τις πράξεις. Υπάρχουν τέτοια παραδείγματα στο βιβλίο. Δύο παραδείγματα διάβασα και μου πέσαν τα μαλλιά. Από το παράδειγμα 2, αυτολεξή:

"Να υπολογισθεί ο χρόνος εκτέλεσης του αλγορίθμου αυτού και να σχολιασθεί η βαρύτητα των
πράξεων επανάληψης σε σχέση με την απόφαση για την πολυπλοκότητα των αλγορίθμων."

Πως μπορεί να υπολογιστεί ο "χρόνος εκτέλεσης"; Ποια είναι η "βαρύτητα των πράξεων"; Τι σημαίνει "απόφαση για την πολυπλοκότητα";

Anyway, το παράδειγμα 2 της σελ. 48 είναι λυμένο λάθος. Η πολυπλοκότητα του αλγόριθμου είναι γραμμική, όχι τετραγωνική.

Το μέγεθος του πίνακα είναι το πλήθος των στοιχείων του (άλλο είναι οι διαστάσεις του πίνακα). Η πολυπλοκότητα ενδιαφέρεται για ΜΕΓΕΘΟΣ, όχι τις διαστάσεις. Αν θέλω να εκτυπώσω όλα τα στοιχεία ενός πίνακα και τα πάρω με την σειρά και τα τυπώσω, τότε έχω γραμμική πολυπλοκότητα. Για έναν διπλάσιο πίνακα, θα κάνω διπλάσιο χρόνο. Οι διαστάσεις των πινάκων μπορεί να είναι 2, 3, 7..., αλλά αυτό δεν με ενδιαφέρει. Οι διαστάσεις του πίνακα δεν αυξάνουν τον όγκο των δεδομένων (τα megabyte)

Διπλάσιο πίνακας είναι αυτός που έχει διπλάσια δεδομένα. Όπως ένα διπλάσιο σπίτι έχει διπλάσια τετραγωνικά μέτρα και ένα διπλάσιο χωράφι έχει τα διπλάσια στρέματα.

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1316
  • There are always possibilities...
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #11 στις: 16 Νοέ 2015, 02:51:36 μμ »
Κατ'αρχή συμφωνώ με τον apoldem ότι το παράδειγμα 2 σελ. 46 (νομίζω ή έχει αλλάξει η σελιδοποίηση;) είναι για τα μπάζα - και με τα υπόλοιπα. Απλά τα ξαναγράφω με δικά μου λόγια.   ;)

Το n που χρησιμοποιει συμβολίζει το πλήθος στοιχείων στη μία διάσταση του πίνακα. Στο παράδειγμα σου με τα 1600 δεδομένα το n είναι 40. Εννοεί λοιπόν ότι είναι τετραγωνικός ως προς αυτό.

Φυσικά δεν έχει νόημα η πολυπλοκότητα ως προς την διάσταση του πίνακα, αλλά ως προς συνολικό  πλήθος των στοιχείων του, αφού αυτά θα επεξεργαστεί ο αλγόριθμος.

A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

dpa2006

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 618
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #12 στις: 16 Νοέ 2015, 03:11:33 μμ »
Πανελλαδικώς εξεταζόμενο το θέμα και η παράγραφος...
Λέτε να δούμε τέτοιο θέμα;
Στην αρχική έκδοση και παλαιότερες εκδόσεις του βιβλίου δεν το θυμάμαι... ???
Computer science (abbreviated CS or CompSci) is the scientific and practical approach to computation and its applications. It is the systematic study of the feasibility, structure, expression, and mechanization of the methodical processes (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information, whether such information is encoded in bits and bytes in a computer memory or transcribed engines and protein structures in a human cell.source:http://en.wikipedia.org/wiki/Computer_science

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #13 στις: 16 Νοέ 2015, 08:11:33 μμ »
Ξαναδιάβασα το παράδειγμα 2, της ενότητας 5.2, από το τετράδιο μαθητή (στο σπίτι αυτή την φορά, συντροφιά με φραπεδάκι).

Έτσι όπως το σκέφτηκαν οι συγγραφείς, μπορεί να θεωρηθεί σωστό (με πολύ καλή θέληση). Το σκεπτικό τους είναι ότι σου δίνεται η διάσταση του τετραγωνικού πίνακα και ο αλγόριθμος πρέπει να ζητήσει ένα-ένα τα στοιχεία και να τα τυπώσει. Είσοδος για τον αλγόριθμο είναι η διάσταση. Τα υπόλοιπα θεωρούνται "επεξεργασία" των δεδομένων! Για να αποφύγουν να δώσουν τον ίδιο τον πίνακα ως είσοδο, βάζουν το διάβασμα και την εκτύπωση των στοιχείων του πίνακα μέσα στην επεξεργασία.

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

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

Υ.Γ. Το συντακτικό και τα ρήματα που χρησιμοποιούνται στο κεφάλαιο αυτό σπάει κόκαλα. Από το παράδειγμα 3 αυτολεξή:

"Να παρακολουθήσετε την πορεία του αλγορίθμου με καταγραφή της επίδοσής του που θα
εκφράζεται από τον αριθμό των πράξεων που πρέπει να εκτελεσθούν."

Δεν έχει σημασία ποιος είναι ο αλγόριθμος. Αυτό ζητείται από τον μαθητή! Χρειάζεται επιτροπή φιλολόγων για να κάνει συντακτική ανάλυση σ' αυτή την πρόταση. Να σκεφτεί κανείς ότι ο κεντρικός πυρήνας του μαθήματος είναι η σαφήνεια. Τόση σαφήνεια ώστε αυτό που λέμε να μπορεί να το καταλάβει μια μηχανή.
« Τελευταία τροποποίηση: 16 Νοέ 2015, 08:44:59 μμ από apoldem »

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 887
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #14 στις: 17 Νοέ 2015, 08:52:59 πμ »
Παρά το ότι απευθύνεσαι στον Παναγιώτη, πήρα το θάρος να επέμβω.
Καλά έκανες, εννοείται φίλε μου ! (μακάρι να ήξερα και το μικρό σου όνομα, να μη σε λέω με το username σου...)
και σ' ευχαριστώ για το χρόνο που διέθεσες  :)

Το συντακτικό και τα ρήματα που χρησιμοποιούνται στο κεφάλαιο αυτό σπάει κόκαλα.
Πράγματι, και οι δύο εκφωνήσεις που παραθέτεις είναι τραγικές
Φιλικά,
Γιώργος Θαλασσινός

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 887
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #15 στις: 17 Νοέ 2015, 08:55:55 πμ »
Το n που χρησιμοποιει συμβολίζει το πλήθος στοιχείων στη μία διάσταση του πίνακα. Στο παράδειγμα σου με τα 1600 δεδομένα το n είναι 40. Εννοεί λοιπόν ότι είναι τετραγωνικός ως προς αυτό.
Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?
Φιλικά,
Γιώργος Θαλασσινός

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #16 στις: 17 Νοέ 2015, 05:27:47 μμ »
Παράθεση
Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?

Το μέγεθος της εισόδου μπορεί να περιγράφεται από δύο ή περισσότερες παραμέτρους. Αν ακολουθήσουμε το σκεπτικό του παραδείγματος 2 και το εφαρμόσουμε σε πίνακα ΝΧΜ, τότε το μέγεθος της εισόδου είναι οι αριθμοί Ν και Μ και η πολυπλοκότητα προκύπτει ΝΧΜ.

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 887
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #17 στις: 17 Νοέ 2015, 05:46:10 μμ »
Μα πώς θα ήταν η πολυπλοκότητα ΝΧΜ, αφού δεν υπάρχει τέτοιος συμβολισμός? Μπορούμε να πούμε ότι είναι Ο(ΝΧΜ) ? ? ?
Φιλικά,
Γιώργος Θαλασσινός

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #18 στις: 17 Νοέ 2015, 07:11:31 μμ »
Και βέβαια μπορούμε. Το μέγεθος της εισόδου μπορεί να περιγραφεί από περισσότερες μεταβλητές, ανεξάρτητες μεταξύ τους. Για παράδειγμα στα δίκτυα (ή γράφοι) είναι πολύ συνηθισμένο να μετράμε το μέγεθος τους με το πλήθος των κόμβων (n) και το πλήθος των συνδέσεων (m). Π.χ. ο διάσημος αλγόριθμος Dijkstra για τις συντομότερες διαδρομές έχει (χοντρικά) πολυπλοκότητα Ο(n+m).

Πιο γήινο παραδείγματα: Έχουμε δύο πίνακες ακεραίων Α[N] και Β[M]. Θέλουμε να βρούμε όλα τα ζευγάρια στοιχείων, που το ένα στοιχείο να ανήκει στον Α και το άλλο στον Β, και το άθροισμά τους να είναι 100.
Θα πρέπει να τσεκάρουμε όλα τα ζευγάρια στοιχείων μεταξύ Α και Β. Πολυπλοκότητα Ο(N*M).

Άλλο παράδειγμα: Έχουμε πάλι τους πίνακες Α[Ν] και Β[Μ]. Θέλουμε να βρούμε αν υπάρχει περίπτωση επιλέγοντας ένα οποιοδήποτε στοιχείο του Α και δύο οποιαδήποτε στοιχεία του Β να βρούμε άθροισμα 100. Εδώ τώρα επειδή διαλέγουμε 2 στοιχεία από το Β η πολυπλοκότητα θα βγει Ο(Ν*Μ2).

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1316
  • There are always possibilities...
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #19 στις: 17 Νοέ 2015, 08:16:24 μμ »
Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?

Μια παρατήρηση που ίσως διευκολύνει, ίσως και αναψει φωτιες.
Το n δεν είναι η είσοδος του αλγορίθμου.
Τα στοιχεία του πίνακα είναι η είσοδος.

Το n απλά ειναι κατι που πρέπει να έχει οριστεί πριν τρέξει ο αλγόριθμος.

Δηλ. δεν σημαίνει ότι οτιδήποτε υπάρχει στα δεδομένα θα επηρεάσει την πολυπλοκότητα.
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 428
  • Real stupidity beats ΑΙ any time
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #20 στις: 18 Νοέ 2015, 09:47:12 πμ »
Μια παρατήρηση που ίσως διευκολύνει, ίσως και αναψει φωτιες.
Το n δεν είναι η είσοδος του αλγορίθμου.
Τα στοιχεία του πίνακα είναι η είσοδος.

Το n απλά ειναι κατι που πρέπει να έχει οριστεί πριν τρέξει ο αλγόριθμος.

Δηλ. δεν σημαίνει ότι οτιδήποτε υπάρχει στα δεδομένα θα επηρεάσει την πολυπλοκότητα.

Δεν καταλαβαίνω τι εννοείς. Η πολυπλοκότητα περιγράφει πώς αντιδρά ο αλγόριθμος (χωρικά|χρονικά) σε αλλαγές στο μέγεθος του input. Τι φωτιά ανάβει το ότι δεν έχει σχέση με τα δεδομένα per se;

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #21 στις: 07 Δεκ 2015, 01:15:21 μμ »
Κατά η δική μου κατανόηση, η πολυπλοκότητα είναι μια συνάρτηση και θα πρέπει να ξεκαθαρίσεις ποια είναι ανεξάρτητη μεταβλητή σου. Δηλαδή να αποφασίσεις η πολυπλοκότητα συνάρτηση ποιου πράγματος είναι.
Τυπικά (δηλαδή με βάση τον ορισμό των μηχανώνΤuring) η πολυπλοκότητα είναι με βάση το χαρακτήρων που δίνεις να είσοδο. Γι αυτό θα δεις ότι ο έλεγχος για το αν ένας αριθμός είναι πρώτος, υπολογίζεται όχι με βάση τον αριθμό που ελέγχουμε αν είναι πρώτος, αλλά με βάση το πλήθος των ψηφίων του αριθμού. Πχ το επίτευγμα το αλγορίθμου AKS είναι ότι έλυσε το πρόβλημα σε πολυωνυμικό χρόνο από εκθετικός που ήταν πριν. Αν μετράγαμε με βάση τον αριθμό που ελέγχουμε (και όχι το πλήθος των ψηφίων του) θα ήταν εξαρχής πολυωνυμική η λύση.
Στην πράξη όμως το να πας τυπικά με το πλήθος των χαρακτήρων εισόδου είναι άβολο και πάμε με κάτι πιο βολικό/πρακτικό. Ότι μεταβλητή όμως και να χρησιμοποιήσουμε, μπορούμε να πάμε και σε άλλη μέσω σύνθεσης συναρτήσεων.
Πχ στον αλγόριθμο του τετραδίου με τον νΧν δισδιάστατο πίνακα, αν έχω μεταβλητή το ν τότε ναι πάω για τετραγωνική πολυπλοκότητα  (του ν). Αν έχω το πλήθος των στοιχείων (ν^2=π) τότε έχω γραμμική συνάρτηση του π (πλήθος). Συμφωνώ ότι είναι άκομψο το να διαλέξεις σα μεταβλητή το ν και όχι το πλήθος των στοιχείων. Γι αυτό ανέφερα και το παράδειγμα με τους πρώτους πιο πριν, για να δείξω το ρόλο της μεταβλητής που επιλέγω. Τελικά πιστεύω ότι είναι μαθηματικό παιχνίδι επιλογής της ανεξάρτητης μεταβλητής και κατασκευής συνάρτησης πάνω σε αυτή. Καλό είναι να διαλέγουμε μεταβλητή που να ταιριάζει με τη διαίσθησή μας.

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1316
  • There are always possibilities...
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #22 στις: 07 Δεκ 2015, 04:29:37 μμ »
Γιώργο συμφωνώ μαζί σου. Όμως ο αλγόριθμος έχει και μία σημασιολογία η οποία μας οδηγεί στο να επιλέξουμε την ανεξάρτητη μεταβλητή, όπως λες.
Δεν είναι λοιπόν όλες οι επιλογές ισοδύναμες.

Στο συγκεκριμένο παράδειγμα λοιπόν η επεξεργασία αφορά τα εισαγόμενα στοιχεία τα οποία απλά δείχνουμε (άρα αυτό αφορά την πολυπλοκότητα και είναι γραμμική).

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

itt (έστω και με καθυστέρηση): Οι φωτιές αναφέρονταν στο να μην ξεκινήσει η συζήτηση περι των ασαφειων της εντολής δεδομένα.
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #23 στις: 07 Δεκ 2015, 04:49:06 μμ »
Έχω μια μικρή επιφύλαξη στο αν πρέπει να στηριχτούμε στη σημασιολογία ή αν έχουμε το δικαίωμα να το δούμε τελείως  ψυχρά μαθηματικά το θέμα χωρίς φυσική σημασία: το ότι στον έλεγχο πρώτου η ανεξάρτητη μεταβλητή μας είναι το πλήθος των ψηφίων του αριθμού που ελέγχουμε και όχι ο αριθμός. Αν πηγαίναμε σημασιολογικά θα έπρεπε να είναι ο αριθμός. Η διαίσθηση αυτό λέει.

Δηλαδή στο παράδειγμα του βιβλίου, αν το δούμε διαισθητικά/σημασιολογικά η λογική επιλογή είναι το ν^2 σαν ανεξάρτητη μεταβλητή. Αν το δούμε σαν παιχνίδι επιλογής μεταβλητής μπορείς (έστω και αν είναι άκομψο) να έχεις ανεξάρτητη μεταβλητή το ν. Το παράδειγμα των πρώτων είναι που ανακατεύει το πράγμα.

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1316
  • There are always possibilities...
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #24 στις: 07 Δεκ 2015, 10:41:01 μμ »
Μάλλον δεν το εξέφρασα καλά.
Και στις δύο περιπτώσεις (πρώτοι και παράδειγμα) μας απασχολεί το μέγεθος της εισόδου. Στους πρώτους είναι τo μέγεθος της αναπαράστασης του αριθμού σε bits, ενώ στο παράδειγμα το πλήθος των αριθμών. Από  τη μία προσθέτοντας ένα bit διπλασιάζεται η δουλειά, από την άλλη προσθέτοντας έναν αριθμό η δουλειά απλά αυξάνεται κατά ένα.
Απλά στο παράδειγμα πρέπει να ανακαλύψουμε ποια είναι η είσοδος από τον αλγόριθμο και όχι να πάρουμε στα τυφλά ότι λέει η εντολή δεδομένα (η οποία δεν έχει πάντα σχέση με την είσοδο για την πολυπλοκότητα). Αυτό εννοώ με το σημασιολογία.
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2213
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #25 στις: 08 Δεκ 2015, 12:08:12 πμ »
Ένα αρκετά πολύπλοκο κεφάλαιο που προστέθηκε στην ύλη ελαφρά τη καρδιά και χωρίς διευκρινίσεις με την μισή χρονιά πίσω μας πλέον
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #26 στις: 08 Δεκ 2015, 05:20:51 μμ »
Κατάλαβα τι λες Παναγιώτη και συμφωνώ για το Δεδομένα //ν//. Πχ στους αραιούς δίνει το ν και ο πίνακας έχει μέγεθος 3ν.
Νομίζω όπως ότι η συζήτηση μοιραία θα περιστραφεί και γύρω από την είσοδο. Πχ δες ένα παράδειγμα:
Να γραφτεί αλγόριθμος που θα διαβάζει έναν ακέραιο αριθμό και θα εκτυπώνει τους ακέραιους από το 1 μέχρι αυτόν.
Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης

Ποια είναι η είσοδος και ποια είναι η ανεξάρτητη μεταβλητή συναρτήσει της οποίας θα υπολογίσουμε την πολυπλοκότητα;
Είναι το πλήθος των ψηφίων του αριθμού ή ο αριθμός; Αν είναι το πρώτο, η πολυπλοκότητα είναι συνάρτηση του πλήθους των ψηφίων και  είναι εκθετική. Αν είναι το δεύτερο η πολυπλοκότητα είναι συνάρτηση του αριθμού ν και είναι γραμμική.
Η συζήτηση για την ανεξάρτητη μεταβλητή συναρτήσει της οποίας βγάζουμε την πολυπλοκότητα μοιραία επαναφέρει και το "στοιχειωμένο" ζήτημα της εισόδου.  Εγώ είμαι υπέρ της πρώτης απάντησης.
« Τελευταία τροποποίηση: 08 Δεκ 2015, 05:35:38 μμ από gpapargi »

ether

  • Επισκέπτης
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #27 στις: 08 Δεκ 2015, 06:21:46 μμ »
Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.

Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης
« Τελευταία τροποποίηση: 08 Δεκ 2015, 06:33:21 μμ από ether »

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1316
  • There are always possibilities...
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #28 στις: 08 Δεκ 2015, 07:59:33 μμ »
Η συζήτηση για την ανεξάρτητη μεταβλητή συναρτήσει της οποίας βγάζουμε την πολυπλοκότητα μοιραία επαναφέρει και το "στοιχειωμένο" ζήτημα της εισόδου. 
Συμφωνούμε 100%
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 428
  • Real stupidity beats ΑΙ any time
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #29 στις: 09 Δεκ 2015, 11:38:10 πμ »
Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.

Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης

Οπότε λοιπόν εαν κάποιος κάνει την εύλογη ερώτηση με τον αλγόριθμο που έγραψες, τι του απαντάμε; Υπάρχει για μας η ψευδο-πολυωνυμική πολυπλοκότητα; Εγώ ειλικρινά δεν καταλαβαίνω γιατί αυτό το κεφαλαίο μπήκε στην ύλη.

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #30 στις: 09 Δεκ 2015, 02:58:03 μμ »
Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.

Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης


ether συμφωνούμε σε όλα.
Το ερώτημα για μένα που πρέπει να συζητήσουμε είναι το πότε επιτρέπεται να κάνουμε αλλαγή ανεξάρτητης μεταβλητής και να μην βρίσκουμε την πολυπλοκότητα συναρτήσει των bits εισόδου, αλλά συναρτήσει κάποια άλλης μεταβλητής.
Κατά τη γνώμη μου επιτρέπεται  όταν απλά πολλαπλασιάζεις την είσοδο με μια σταθερά πχ αντί για bits μετράς χαρακτήρες. Δεν πρόκειται αυτά να αλλάξει την τάξη του αλγορίθμου. Δεν επιτρέπεται όταν αλλάζεις την τάξη από πολυωνυμική σε εκθετική και ανάποδα. Το ερώτημα είναι: επιτρέπεται το να αλλάξεις από πολυωνυμική κάποιου βαθμού σε πολυωνυμική άλλου βαθμού (όπως κάνει το τετράδιο μαθητή στο παράδειγμα το ν σε ν^2); Ποια είναι τα όρια ανοχής;

Επίσης μια ερώτηση προς ether για να δούμε με ποια άποψη συμφωνείς ως προς την είσοδο: Ο παρακάτω αλγόριθμος έχει είσοδο;
Για ι από 1 ως 100
Γράψε ι
Τέλος_επανάληψης
Δηλαδή δεν έχω διάβασε. Έχει είσοδο ή όχι;
« Τελευταία τροποποίηση: 09 Δεκ 2015, 04:32:49 μμ από gpapargi »

ether

  • Επισκέπτης
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #31 στις: 09 Δεκ 2015, 05:47:01 μμ »
Οπότε λοιπόν εαν κάποιος κάνει την εύλογη ερώτηση με τον αλγόριθμο που έγραψες, τι του απαντάμε; Υπάρχει για μας η ψευδο-πολυωνυμική πολυπλοκότητα; Εγώ ειλικρινά δεν καταλαβαίνω γιατί αυτό το κεφαλαίο μπήκε στην ύλη.
Θα μπορούσαμε να δώσουμε διαφορετική απάντηση από αυτή που αναφέρεται στη σχετική βιβλιογραφία;
Όταν λες αν υπάρχει για εμάς η ψευδοπολυωνυμική πολυπλοκότητα, που ουσιαστικά είναι εκθετική ως προς το μέγεθος της εισόδου, τι εννοείς, στα πλαίσια της ΑΕΠΠ; Θεωρώ ότι είναι κάτι που δεν πρέπει να απασχολεί εμάς και τους μαθητές στα πλαίσια της ΑΕΠΠ και ούτε κι εγώ καταλαβαίνω γιατί μπήκε στην ύλη το συγκεκριμένο κεφάλαιο. Είναι κακογραμμένο, αλλά ακόμα και καλογραμμένο να ήταν θεωρώ ότι δε θα έπρεπε να αποτελεί αντικείμενο εξέτασης.
« Τελευταία τροποποίηση: 09 Δεκ 2015, 05:58:27 μμ από ether »

ether

  • Επισκέπτης
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #32 στις: 09 Δεκ 2015, 05:50:36 μμ »
ether συμφωνούμε σε όλα.
Το ερώτημα για μένα που πρέπει να συζητήσουμε είναι το πότε επιτρέπεται να κάνουμε αλλαγή ανεξάρτητης μεταβλητής και να μην βρίσκουμε την πολυπλοκότητα συναρτήσει των bits εισόδου, αλλά συναρτήσει κάποια άλλης μεταβλητής.
Κατά τη γνώμη μου επιτρέπεται  όταν απλά πολλαπλασιάζεις την είσοδο με μια σταθερά πχ αντί για bits μετράς χαρακτήρες. Δεν πρόκειται αυτά να αλλάξει την τάξη του αλγορίθμου. Δεν επιτρέπεται όταν αλλάζεις την τάξη από πολυωνυμική σε εκθετική και ανάποδα. Το ερώτημα είναι: επιτρέπεται το να αλλάξεις από πολυωνυμική κάποιου βαθμού σε πολυωνυμική άλλου βαθμού (όπως κάνει το τετράδιο μαθητή στο παράδειγμα το ν σε ν^2); Ποια είναι τα όρια ανοχής;

Επίσης μια ερώτηση προς ether για να δούμε με ποια άποψη συμφωνείς ως προς την είσοδο: Ο παρακάτω αλγόριθμος έχει είσοδο;
Για ι από 1 ως 100
Γράψε ι
Τέλος_επανάληψης
Δηλαδή δεν έχω διάβασε. Έχει είσοδο ή όχι;
Στο CLRS (3rd edition, p. 25) αναφέρει:
The best notion for input size depends on the problem being studied. For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the number of items in the input—for example, the array size n for sorting. For many other problems, such as multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation. Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph. We shall indicate which input size measure is being used with each problem we study

Ο αλγόριθμος που έδωσες παραπάνω, αν κάθε φορά τον τρέχεις έτσι όπως είναι, χωρίς να αλλάξεις τις τιμές ΑΠΟ ΜΕΧΡΙ, έχει πολυπλοκότητα Ο(1) ως προς οποιαδήποτε είσοδο, γιατί οποιαδήποτε είσοδο κι αν του δώσεις την αγνοεί και εκτελεί πάντοτε τον συγκεκριμένο αριθμό εντολών.

Σχετικά με το παράδειγμα 2 του κεφ. 5 του τετραδίου μαθητή, προφανώς ως προς το πλήθος των στοιχείων του πίνακα (n^2) η πολυπλοκότητα του αλγορίθμου είναι γραμμική.
Αν υποθέσουμε όμως ότι ο πίνακας αυτός είναι ο πίνακας γειτνίασης ενός γράφου n κόμβων, τότε ενδεχομένως θα μας ενδιέφερε να μετρήσουμε την πολυπλοκότητα συναρτήσει του πλήθους των κόμβων n και να πούμε π.χ. ότι με το συγκεκριμένο τρόπο αναπαράστασης (πίνακας γειτνίασης), η πολυπλοκότητα εμφάνισης όλων των ακμών είναι O(n^2). Όπως λέει λοιπόν και το CLRS, η έννοια του μεγέθους εισόδου εξαρτάται από το πρόβλημα και θα πρέπει να αναφέρεται.

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #33 στις: 09 Δεκ 2015, 07:52:05 μμ »
Μια μικρή παρένθεση ως προς το αν έπρεπε να μπει ή όχι το κεφάλαιο 5 στην ύλη:
Πιο παλιά, έβλεπες εύρεση μεγίστου σε πίνακα με πλήρη ταξινόμηση. Σε κανέναν δεν άρεσε, αλλά κανείς δεν μπορούσε να κάνει τίποτα. Σου έλεγαν «μετράει μόνο το σωστό αποτέλεσμα» και «η πολυπλοκότητα είναι εκτός ύλης». Έπρεπε να βρεθεί ένα πλαίσιο για να μη δεχόμαστε σαν σωστούς εντελώς απαράδεκτους αλγορίθμους. Το κεφάλαιο 5 δίνει ένα τέτοιο πλαίσιο. Θα συζητήσουμε και θα ξεδιαλύνουμε τις λεπτομέρειες, δεν είναι η πρώτη φορά που γίνεται αυτό. Ίσα ίσα που το στέκι δείχνει να ξαναβρίσκει τον παλιό καλό του εαυτό που οι επιστημονικές  παιδαγωγικές συζητήσεις ήταν καθημερινότητα.   

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #34 στις: 10 Δεκ 2015, 11:42:39 πμ »
Στο CLRS (3rd edition, p. 25) αναφέρει:
The best notion for input size depends on the problem being studied. For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the number of items in the input—for example, the array size n for sorting. For many other problems, such as multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation. Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph. We shall indicate which input size measure is being used with each problem we study

Ο αλγόριθμος που έδωσες παραπάνω, αν κάθε φορά τον τρέχεις έτσι όπως είναι, χωρίς να αλλάξεις τις τιμές ΑΠΟ ΜΕΧΡΙ, έχει πολυπλοκότητα Ο(1) ως προς οποιαδήποτε είσοδο, γιατί οποιαδήποτε είσοδο κι αν του δώσεις την αγνοεί και εκτελεί πάντοτε τον συγκεκριμένο αριθμό εντολών.

Σχετικά με το παράδειγμα 2 του κεφ. 5 του τετραδίου μαθητή, προφανώς ως προς το πλήθος των στοιχείων του πίνακα (n^2) η πολυπλοκότητα του αλγορίθμου είναι γραμμική.
Αν υποθέσουμε όμως ότι ο πίνακας αυτός είναι ο πίνακας γειτνίασης ενός γράφου n κόμβων, τότε ενδεχομένως θα μας ενδιέφερε να μετρήσουμε την πολυπλοκότητα συναρτήσει του πλήθους των κόμβων n και να πούμε π.χ. ότι με το συγκεκριμένο τρόπο αναπαράστασης (πίνακας γειτνίασης), η πολυπλοκότητα εμφάνισης όλων των ακμών είναι O(n^2). Όπως λέει λοιπόν και το CLRS, η έννοια του μεγέθους εισόδου εξαρτάται από το πρόβλημα και θα πρέπει να αναφέρεται.

Σύμφωνα με την άποψη που διατυπώνεις ether (διόρθωσέ με αν κατάλαβα λάθος) και πηγάζει από το CLR, το να δεις τον κώδικα (χωρίς εκφώνηση) στο παράδειγμα του τετραδίου μαθητή, δε σημαίνει τίποτα για την επιλογή της μεταβλητής ως προς την οποία θα υπολογίσουμε την πολυπλοκότητα. Τη μεταβλητή την επιλέγουμε με βάση τη φυσική σημασία του κώδικα και προέρχεται από την εκφώνηση. Έχουμε το δικαίωμα να επιλέξουμε ανεξάρτητη μεταβλητή και να φτιάξουμε τη συνάρτηση.
Γενικά δηλαδή ο κώδικας δεν καθορίζει τη μεταβλητή. Η εκφώνηση (=φυσική σημασία) την καθορίζει.

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #35 στις: 10 Δεκ 2015, 01:18:09 μμ »
Γράφω ένα σχόλιο στην παραπάνω άποψη. Αν έχεις πίνακα γειτνίασης γράφου, η αύξηση των κόμβων κατά 1 σημαίνει  αύξηση των κελιών κατά 2ν+1=(ν+1)^2 - ν^2. Δε γίνεται να αυξήσεις τα κελιά του πίνακα κατά 1, αλλά μόνο κατά 2ν+1. Πάλι γραμμική είναι η πολυπλοκότητα ως προς το μέγεθος εισόδου. Το θέμα είναι αν μπορείς να ονομάσεις μέγεθος εισόδου το πλήθος των κόμβων τη στιγμή που κάθε νέος κόμβος σημαίνει αύξηση κατά μεταβλητό (2ν+1)πλήθος κελιών κάθε φορά. Αν θέλεις την πολυπλοκότητα συναρτήσει του ν φυσικά γίνεται. 

ether

  • Επισκέπτης
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #36 στις: 10 Δεκ 2015, 03:16:49 μμ »
Σύμφωνα με την άποψη που διατυπώνεις ether (διόρθωσέ με αν κατάλαβα λάθος) και πηγάζει από το CLR, το να δεις τον κώδικα (χωρίς εκφώνηση) στο παράδειγμα του τετραδίου μαθητή, δε σημαίνει τίποτα για την επιλογή της μεταβλητής ως προς την οποία θα υπολογίσουμε την πολυπλοκότητα. Τη μεταβλητή την επιλέγουμε με βάση τη φυσική σημασία του κώδικα και προέρχεται από την εκφώνηση. Έχουμε το δικαίωμα να επιλέξουμε ανεξάρτητη μεταβλητή και να φτιάξουμε τη συνάρτηση.
Γενικά δηλαδή ο κώδικας δεν καθορίζει τη μεταβλητή. Η εκφώνηση (=φυσική σημασία) την καθορίζει.
Ο προφανής αλγόριθμος που υπολογίζει το άθροισμα δυο τετραγωνικών πινάκων ΝxN έχει τετραγωνική πολυπλοκότητα ως προς το Ν.
Ο αλγόριθμος της φυσσαλίδας για την ταξινόμηση ενός πίνακα Ν στοιχείων έχει επίσης τετραγωνική πολυπλοκότητα ως προς το Ν.
Και οι δύο έχουν διπλό εμφωλευμένο βρόχο (ίδιας τάξης πολυπλοκότητας).
Ο πρώτος έχει γραμμική πολυπλοκότητα ως προς το μέγεθος εισόδου και είναι βέλτιστος για το συγκεκριμένο πρόβλημα.
Ο δεύτερος έχει τετραγωνική πολυπλοκότητα ως προς το μέγεθος εισόδου και δεν είναι βέλτιστος για το συγκεκριμένο πρόβλημα.

Ο προφανής αλγόριθμος που υπολογίζει το άθροισμα των στοιχείων ενός πίνακα ΝxΜ έχει πολυπλοκότητα Ο(NM).
Ο κλασσικός αλγόριθμος δυναμικού προγραμματισμού για το 0/1 knapsack για N αντικείμενα με μέγιστο βάρος M έχει πολυπλοκότητα επίσης Ο(NM).
Και οι δύο έχουν διπλό εμφωλευμένο βρόχο (ίδιας τάξης πολυπλοκότητας).
Ο πρώτος έχει γραμμική πολυπλοκότητα ως προς το μέγεθος εισόδου και είναι βέλτιστος για το συγκεκριμένο πρόβλημα.
Ο δεύτερος έχει εκθετική πολυπλοκότητα ως προς το μέγεθος εισόδου (αν είχε γραμμική θα σήμαινε ότι P=NP οπότε θα ήμασταν (; ) όλοι χαρούμενοι) και δεν ξέρουμε αν είναι βέλτιστος για το συγκεκριμένο πρόβλημα (είναι πολύ πιθανό να είναι, παρόλο που ευχόμαστε (; ) να μην είναι)
« Τελευταία τροποποίηση: 10 Δεκ 2015, 03:30:11 μμ από ether »

ether

  • Επισκέπτης
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #37 στις: 10 Δεκ 2015, 03:26:26 μμ »
Γράφω ένα σχόλιο στην παραπάνω άποψη. Αν έχεις πίνακα γειτνίασης γράφου, η αύξηση των κόμβων κατά 1 σημαίνει  αύξηση των κελιών κατά 2ν+1=(ν+1)^2 - ν^2. Δε γίνεται να αυξήσεις τα κελιά του πίνακα κατά 1, αλλά μόνο κατά 2ν+1. Πάλι γραμμική είναι η πολυπλοκότητα ως προς το μέγεθος εισόδου. Το θέμα είναι αν μπορείς να ονομάσεις μέγεθος εισόδου το πλήθος των κόμβων τη στιγμή που κάθε νέος κόμβος σημαίνει αύξηση κατά μεταβλητό (2ν+1)πλήθος κελιών κάθε φορά. Αν θέλεις την πολυπλοκότητα συναρτήσει του ν φυσικά γίνεται.
Πάντως εγώ στο παραπάνω σχόλιό μου ανέφερα για το συγκεκριμένο θέμα ότι ενδεχομένως να μας ενδιέφερε ότι έχει τετραγωνική πολυπλοκότητα ως προς το πλήθος των κόμβων (αφού αν χρησιμοποιούσαμε ως αναπαράσταση του γραφήματος λίστες γειτνίασης ο αντίστοιχος αλγόριθμος θα είχε πολυπλοκότητα γραμμική ως προς το μέγεθος εισόδου, άρα μάλλον προτιμότερη σε σχέση με την τετραγωνική ως προς το πλήθος των κόμβων του αλγόριθμου με αναπαράσταση πίνακα γειτνίασης), δεν είπα κάτι για το μέγεθος εισόδου, ούτε και θεώρησα ως μέγεθος εισόδου το πλήθος των κόμβων.

Προφανώς και δεν μπορείς να ονομάσεις ως μέγεθος εισόδου του αλγορίθμου το πλήθος των κόμβων. Το μέγεθος εισόδου σε έναν αλγόριθμο επεξεργασίας γραφήματος με N κόμβους και M ακμές συνήθως μας βολεύει να το θεωρούμε Ν+Μ.
Επομένως, γραμμικοί θεωρούνται οι αλγόριθμοι επεξεργασίας γραφημάτων με πολυπλοκότητα Ο(Ν+Μ).
Συνήθως είσοδος στους αλγορίθμους αυτούς δεν είναι ο πίνακας γειτνίασης αλλά οι κόμβοι και οι ακμές.
Αν λοιπόν από τους Ν κόμβους πάω στους Ν+1, οπότε ο πίνακας γειτνίασης θα αυξηθεί όσο ανέφερες, δε σημαίνει ότι και η είσοδος θα έχει αυξηθεί τόσο. Αν π.χ. ο κόμβος που πρόσθεσα δεν έχει καμία ακμή, τότε το μέγεθος της εισόδου αυξήθηκε απλά κατά ένα.
« Τελευταία τροποποίηση: 10 Δεκ 2015, 04:19:39 μμ από ether »

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #38 στις: 11 Δεκ 2015, 12:04:49 μμ »
Εντάξει συμφωνώ σε αυτά. Εμένα το πρόβλημα που με απασχολεί είναι το εξής:
Το μέγεθος της εισόδου τυπικά μετριέται στο πλήθος των bits εισόδου. Μπορώ επίσης να χρησιμοποιήσω κάποια άλλη μεταβλητή που να συνδέεται με το πλήθος των bits με κάποια πολλαπλασιαστική σταθερά πχ πλήθος χαρακτήρων. Το ερώτημα είναι: μπορώ να χρησιμοποιήσω κάποια άλλη μεταβλητή επειδή θέλω ή επειδή με βολεύει; Μπορώ πχ να πω ότι στον αλγόριθμο
Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης
χρησιμοποιώ σαν μεταβλητή τον αριθμό εισόδου ν και έχω πολυπλοκότητα γραμμική ως προς ν ή είμαι παράτυπος;
Μπορώ πχ να εξηγήσω γιατί αν ταξινομώ πίνακες με αριθμούς χρησιμοποιώντας το πλήθος των αριθμών και όχι τα ψηφία τους έχω μεταβλητή πολλαπλασιασμένη με το πλήθος των bits εισόδου, αλλά τι γίνεται με το παράδειγμα που δίνω; Έχω δικαίωμα να εκφράσω πολυπλοκότητα ως προς ν αλλάζοντας την τάξη από εκθετική ως προς τα bits σε πολυωνυμική ως προς ν ή όχι;

ether

  • Επισκέπτης
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #39 στις: 11 Δεκ 2015, 03:00:33 μμ »
Εντάξει συμφωνώ σε αυτά. Εμένα το πρόβλημα που με απασχολεί είναι το εξής:
Το μέγεθος της εισόδου τυπικά μετριέται στο πλήθος των bits εισόδου. Μπορώ επίσης να χρησιμοποιήσω κάποια άλλη μεταβλητή που να συνδέεται με το πλήθος των bits με κάποια πολλαπλασιαστική σταθερά πχ πλήθος χαρακτήρων. Το ερώτημα είναι: μπορώ να χρησιμοποιήσω κάποια άλλη μεταβλητή επειδή θέλω ή επειδή με βολεύει; Μπορώ πχ να πω ότι στον αλγόριθμο
Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης
χρησιμοποιώ σαν μεταβλητή τον αριθμό εισόδου ν και έχω πολυπλοκότητα γραμμική ως προς ν ή είμαι παράτυπος;
Μπορώ πχ να εξηγήσω γιατί αν ταξινομώ πίνακες με αριθμούς χρησιμοποιώντας το πλήθος των αριθμών και όχι τα ψηφία τους έχω μεταβλητή πολλαπλασιασμένη με το πλήθος των bits εισόδου, αλλά τι γίνεται με το παράδειγμα που δίνω; Έχω δικαίωμα να εκφράσω πολυπλοκότητα ως προς ν αλλάζοντας την τάξη από εκθετική ως προς τα bits σε πολυωνυμική ως προς ν ή όχι;
Έχουμε λοιπόν έναν αλγόριθμο που δέχεται ως είσοδο έναν ακέραιο ν κι εμφανίζει όλους τους ακέραιους από το 1 μέχρι το ν.

Έχουμε κάθε δικαίωμα να πούμε ότι ο αλγόριθμός μας έχει πολυπλοκότητα Ο(ν). Δεν έχουμε όμως δικαίωμα να πούμε ότι ο αλγόριθμός μας είναι πολυωνυμικού χρόνου, αφού αυτό θα σήμαινε ότι είναι πολυωνυμικού χρόνου ως προς το μέγεθος της εισόδου (αφού ως προς το μέγεθος της εισόδου μετράμε την πολυπλοκότητα για να χαρακτηρίσουμε τον αλγόριθμο ως πολυωνυμικού, εκθετικού κτλ χρόνου), από τη στιγμή που το μέγεθος της εισόδου είναι lgν κι ο αλγόριθμός μας είναι Ο(2^lgν).

Και για τον αλγόριθμο δυναμικού προγραμματισμού για το knapsack, αναφέρουμε την πολυπλοκότητά του ως Ο(nW). Κανένας όμως αυτό δεν το ερμηνεύει ως πολυωνυμικού χρόνου, αφού στο συγκεκριμένο πρόβλημα το W δεν αντιστοιχεί σε πλήθος δεδομένων αλλά είναι απλά μια αριθμητική τιμή, άρα ουσιαστικά ο αλγόριθμος είναι εκθετικός, Ο(n*2^lgW), ως προς το μέγεθος της εισόδου.


gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η
« Απάντηση #40 στις: 11 Δεκ 2015, 04:09:06 μμ »
Με βάση αυτά, στο παράδειγμα του τετραδίου μπορώ να πω ότι ο αλγόριθμος έχει τετραγωνική πολυπλοκότητα Ο(ν^2) αν και φυσικά δεν μπορώ να πω ότι είναι τετραγωνικός ως προς το χρόνος εκτέλεσης. Φοβάμαι πως θα δημιουργηθούν μπερδέματα.