Θέμα: Επίδοση και Πολυπλοκότητα - Ερώτηση 2η

[gthal]

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

Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?

[apoldem]

Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?

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

[gthal]

Μα πώς θα ήταν η πολυπλοκότητα ΝΧΜ, αφού δεν υπάρχει τέτοιος συμβολισμός? Μπορούμε να πούμε ότι είναι Ο(ΝΧΜ) ? ? ?

[apoldem]

Και βέβαια μπορούμε. Το μέγεθος της εισόδου μπορεί να περιγραφεί από περισσότερες μεταβλητές, ανεξάρτητες μεταξύ τους. Για παράδειγμα στα δίκτυα (ή γράφοι) είναι πολύ συνηθισμένο να μετράμε το μέγεθος τους με το πλήθος των κόμβων (n) και το πλήθος των συνδέσεων (m). Π.χ. ο διάσημος αλγόριθμος Dijkstra για τις συντομότερες διαδρομές έχει (χοντρικά) πολυπλοκότητα Ο(n+m).

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

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

[pgrontas]

Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?

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

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

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

[itt]

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

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

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

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

[gpapargi]

Κατά η δική μου κατανόηση, η πολυπλοκότητα είναι μια συνάρτηση και θα πρέπει να ξεκαθαρίσεις ποια είναι ανεξάρτητη μεταβλητή σου. Δηλαδή να αποφασίσεις η πολυπλοκότητα συνάρτηση ποιου πράγματος είναι.
Τυπικά (δηλαδή με βάση τον ορισμό των μηχανώνΤuring) η πολυπλοκότητα είναι με βάση το χαρακτήρων που δίνεις να είσοδο. Γι αυτό θα δεις ότι ο έλεγχος για το αν ένας αριθμός είναι πρώτος, υπολογίζεται όχι με βάση τον αριθμό που ελέγχουμε αν είναι πρώτος, αλλά με βάση το πλήθος των ψηφίων του αριθμού. Πχ το επίτευγμα το αλγορίθμου AKS είναι ότι έλυσε το πρόβλημα σε πολυωνυμικό χρόνο από εκθετικός που ήταν πριν. Αν μετράγαμε με βάση τον αριθμό που ελέγχουμε (και όχι το πλήθος των ψηφίων του) θα ήταν εξαρχής πολυωνυμική η λύση.
Στην πράξη όμως το να πας τυπικά με το πλήθος των χαρακτήρων εισόδου είναι άβολο και πάμε με κάτι πιο βολικό/πρακτικό. Ότι μεταβλητή όμως και να χρησιμοποιήσουμε, μπορούμε να πάμε και σε άλλη μέσω σύνθεσης συναρτήσεων.
Πχ στον αλγόριθμο του τετραδίου με τον νΧν δισδιάστατο πίνακα, αν έχω μεταβλητή το ν τότε ναι πάω για τετραγωνική πολυπλοκότητα  (του ν). Αν έχω το πλήθος των στοιχείων (ν^2=π) τότε έχω γραμμική συνάρτηση του π (πλήθος). Συμφωνώ ότι είναι άκομψο το να διαλέξεις σα μεταβλητή το ν και όχι το πλήθος των στοιχείων. Γι αυτό ανέφερα και το παράδειγμα με τους πρώτους πιο πριν, για να δείξω το ρόλο της μεταβλητής που επιλέγω. Τελικά πιστεύω ότι είναι μαθηματικό παιχνίδι επιλογής της ανεξάρτητης μεταβλητής και κατασκευής συνάρτησης πάνω σε αυτή. Καλό είναι να διαλέγουμε μεταβλητή που να ταιριάζει με τη διαίσθησή μας.

[pgrontas]

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

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

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

itt (έστω και με καθυστέρηση): Οι φωτιές αναφέρονταν στο να μην ξεκινήσει η συζήτηση περι των ασαφειων της εντολής δεδομένα.

[gpapargi]

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

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

[pgrontas]

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

[petrosp13]

Ένα αρκετά πολύπλοκο κεφάλαιο που προστέθηκε στην ύλη ελαφρά τη καρδιά και χωρίς διευκρινίσεις με την μισή χρονιά πίσω μας πλέον

[gpapargi]

Κατάλαβα τι λες Παναγιώτη και συμφωνώ για το Δεδομένα //ν//. Πχ στους αραιούς δίνει το ν και ο πίνακας έχει μέγεθος 3ν.
Νομίζω όπως ότι η συζήτηση μοιραία θα περιστραφεί και γύρω από την είσοδο. Πχ δες ένα παράδειγμα:
Να γραφτεί αλγόριθμος που θα διαβάζει έναν ακέραιο αριθμό και θα εκτυπώνει τους ακέραιους από το 1 μέχρι αυτόν.
Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης

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

[ether]

Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.

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

[pgrontas]

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

Συμφωνούμε 100%

[itt]

Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.

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

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