0 μέλη και 5 επισκέπτες διαβάζουν αυτό το θέμα.
Παράθεση από: kostas_xania στις Φεβρουάριος 07, 2009, 03:02:51 πμστην 29 τελικα εναι το Α ή το Γ ? http://en.wikipedia.org/wiki/Device_driverΑναρωτιέμαι, μετά από τις πρόσφατες ανακοινώσεις αποτελεσμάτων των φροντιστηρίων υπάρχει άραγε κόσμος που θα συνεχίσει να απευθύνεται σε αυτά για την προετοιμασία του σε διαγωνισμούς ΑΣΕΠ;
στην 29 τελικα εναι το Α ή το Γ ?
Αν υπάρχει λέει, και ξέρω και ποιοι είναι όλοι αυτοί που πιστεύουν ακόμα ότι Σ{k} = O(n) !!!!αφού και από ότι φαίνεται κάποια φροντιστήρια πιστεύουν το ίδιο!!! Φανταστείτε τι άτομα διδάσκουν εκεί.
Β. Κανόνες (όπου f(n) η δοθείσα συνάρτηση):α) Αν f(c*n) -> O(n) , δηλαδή παράλειψη της σταθεράς c.β) Αν f(n+n^2) -> O(n^2) , δηλαδή άθροισμα όρων διαφορετικής τάξης -> καθορισμός φράγματος από το μεγαλύτερο όρογ) Αν f(n+2n) -> Ο(n) , δηλαδή άθροισμα όρων ίδιας τάξης -> O(n) και όχι O(n^2).
Batman είσαι απλά άσχετος επί του θέματος.
Πληροφοριακά να σου πω ότι ρώτησα 4 καθηγητές στο Α.Τ.Ε.Ι. που εργάζομαι και όλοι συμφώνησαν με τον συλλογισμό μου.
Τώρα αν θες να τους βγάλεις όλους ανίδεους ε τότε τι να σου πω.
Ελπίζω να βγουν γρήγορα οι απαντήσεις για να μην έχεις πλέον τα μούτρα να μιλάς στο forum.
Παράθεση από: thymiaras στις Φεβρουάριος 09, 2009, 05:28:41 μμBatman είσαι απλά άσχετος επί του θέματος. Ευχαριστώ πολύ, άλλο ένα φοβερό επιχείρημα για το αληθές της πρότασής σου. Πάντως επιμένεις βλέπω. Δύσκολο να το παραδεχτείς. Καλά δε βλέπεις ότι τόσοι άλλοι που είναι στο φόρουμ έχουν αντίθετη άποψη? Γιατί δεν το παραδέχεσαι ότι ακόμα και μεγάλοι επιστήμονες σαν και σένα κάνουν που και που κανένα λάθος.ΠαράθεσηΠληροφοριακά να σου πω ότι ρώτησα 4 καθηγητές στο Α.Τ.Ε.Ι. που εργάζομαι και όλοι συμφώνησαν με τον συλλογισμό μου. Ε άμα είναι και καθητήτες στο ΑΤΕΙ τι να λέμε τώρα, τύφλα να έχουν τα ΑΕΙ, η wikipedia και εκατοντάδες βιβλία σχετικά με την θεωρία πολυπλοκότητας. Μιλάμε για ΑΤΕΙ, όχι απλό ΤΕΙ. Το Α τι σημαίνει ? Advanced???ΠαράθεσηΤώρα αν θες να τους βγάλεις όλους ανίδεους ε τότε τι να σου πω. Δεν ξέρω αν το κατάλαβες αλλά οι όλοι είναι εσύ, γιατί στο φόρουμ όλοι οι άλλοι έχουν την αντίθετη άποψη, οπότε μάλλον εσύ τους βγάζεις όλους άσχετους, ενώ εγώ βγάζω άσχετο μόνο εσένα.Παράθεση Ελπίζω να βγουν γρήγορα οι απαντήσεις για να μην έχεις πλέον τα μούτρα να μιλάς στο forum.Περιμένω να βγουν για να γελάσουμε όλοι μαζί. Αλήθεια έχω μια ερώτηση για σένα. Με τι κριτήρια σε προσέλαβαν στο ΑΤΕΙ ? είχες πολλούς γνωστούς ή έχεις κάποια αντικειμενικά προσόντα? δηλαδή υψηλό βαθμό πτυχίου, μεταπτυχιακό δημοσιεύσεις?
Παράθεση από: spk στις Φεβρουάριος 09, 2009, 03:51:10 μμΒ. Κανόνες (όπου f(n) η δοθείσα συνάρτηση):α) Αν f(c*n) -> O(n) , δηλαδή παράλειψη της σταθεράς c.β) Αν f(n+n^2) -> O(n^2) , δηλαδή άθροισμα όρων διαφορετικής τάξης -> καθορισμός φράγματος από το μεγαλύτερο όρογ) Αν f(n+2n) -> Ο(n) , δηλαδή άθροισμα όρων ίδιας τάξης -> O(n) και όχι O(n^2).Αν και το έχω ξαναγράψει σε προηγούμενο post πήγαινε στο σχολικό βιβλίο Ανάπτυξη Εφαρμογών σε προγραμματιστικό περιβάλλον κεφ.5 σελ 107. Έχει μια περίπτωση σχεδόν ίδια και την δίνει Ο(n2)http://pi-schools.sch.gr/download/lessons/computers/lykeio/books/anaptyxh.htmlΣτα παραδείγματα του βιβλίου οι συναρτήσεις αυτές δεν είναι ο ίδιος ο αλγόριθμος. Είναι συναρτήσεις που δίνουν τον αριθμό των βασικών πράξεων που εκτελεί ο αλγόριθμος σε σχέση με το μέγεθος εισόδου n. Προσωπικά θεωρώ απίθανο να δώσει απάντηση ο ΑΣΕΠ που έρχεται σε αντίθεση με παράδειγμα του σχολικού βιβλίου και μάλιστα του πανελλαδικώς εξεταζόμενου μαθήματος.
Το παράδειγμα του βιβλίου που αναφέρεις μιλάει για ταξινόμηση ευθείας ανταλλαγής (straight exchange sort). Ο συγκεκριμένος αλγόριθμος ταξινόμησης υλοποιείται με εμφώλευση βρόχων. Από τη στιγμή που κάθε βρόχος εκτελείται έως (άνω φράγμα) n φορές τότε προφανώς n*n = n^2 operations. Το βιβλίο δεν είναι αναλυτικό/σαφές σε αυτό το σημείο. Από το ΑΣΕΠ και το ΥΠΕΠΘ δεν αποκλείω τίποτα. Μην ξεχνάς ότι στο σύνδεσμο που παρέθεσες υπάρχει ειδικό αρχείο με διορθώσεις για το συγκεκριμένο βιβλίο.Ο αλγόριθμος sigma που παρέθεσα δεν είναι σχεδόν ίδια περίπτωση με αυτή του βιβλίου. Υλοποιείται με έναν απλό βρόχο, χωρίς εμφώλευση. Συνεπώς πρόκειται για τελείως διαφορετικούς αλγορίθμους όσον αφορά την πολυπλοκότητα τους.
Στο ερώτημα 17 είμαι από αυτούς που υποστηρίζουν πως υπάρχει ένα απλό μαθηματικό άθροισμα Σ και ότι δεν περιγράφεται ένας συγκεκριμένος αλγόριθμος.Αντίθετα πολλοί υποστηρίζουν ότι πρόκειται για τον αλγόριθμο αθροίσματος n όρων. Δεν νομίζω όμως ότι ισχύει κάτι τέτοιο.
Καταλήγουμε τελικά στο ότι υπάρχουν δύο οπτικές γωνίες από τις οποίες μπορεί κανείς να δει τη συγκεκριμένη ερώτηση.
Και οι δύο είναι ορθές και επιστημονικά τεκμηριωμένες.
Όταν οι μισοί υποψήφιοι και καθηγητές πληροφορικής σε οποιαδήποτε βαθμίδα εκπαίδευσης "νομίζουμε" και "υποστηρίζουμε" τεκμηριωμένα διαφορετική απάντηση από τους άλλους μισούς θεωρώ ότι το σωστό από πλευράς ΑΣΕΠ είναι να λάβει υπόψη του και τους μεν και τους δε.
Όταν δίνει το σύμβολο του αθροίσματος Σ και ζητάει να πούμε αν είναι Ο(n) ή Ο(n^2) φυσικά και δεν ζητάει συγκεκριμένο αλγόριθμο υλοποίησης απλά μας λέει να βασιστούμε στον ορισμό του αθροίσματος τον οποίο υποθέτει ότι όλοι μας τον ξέρουμε. Γιατί ο ορισμός του αθροίσματος αποτελεί από μόνος του αλγόριθμο υπολογισμού του αθροίσματος. Το δ είναι ΛΑΘΟΣ γιατί το n(n-1)/2 στο οποίο βασίζονται όσοι επιλέγουν το Δ ΔΕΝ μας δίνει πολυπλοκότητα, μας δίνει το αποτέλεσμα (με τι ισούται δηλαδή το αριστερό μέρος της ισότητας). Δηλαδή αν π.χ. μας δίναν ότι το n=10 τότε ο παραπάνω τύπος θα μας έδινε: Σk για k=1 μέχρι 10 =45, OXI ME O(45). Αν δεν μπορείτε να το καταλάβετε αυτό με γεια σας με χαρά σας.