Αποστολέας Θέμα: Σχολιασμός θεμάτων ΟΕΦΕ 2016?  (Αναγνώστηκε 9463 φορές)

dpa2006

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 684
Απ: Σχολιασμός θεμάτων ΟΕΦΕ 2016?
« Απάντηση #30 στις: 15 Μάι 2016, 03:27:58 πμ »
Τα θέματα και οι απαντήσεις ΟΕΦΕ 2016 είναι διαθέσιμα online:
http://www.oefe.gr/el/static/refresher-exam-topics_el.aspx
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

dpa2006

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 684
Απ: Σχολιασμός θεμάτων ΟΕΦΕ 2016?
« Απάντηση #31 στις: 17 Μάι 2016, 05:59:38 μμ »
Καλησπέρα,
θα ήθελα να αναφέρω το θέμα Α3 (ζήτημα 1) της ΟΕΦΕ
Έχει νόημα να θέτει ως απάντηση O(2n)...;
Δεν είναι λάθος ως διατύπωση...;
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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3502
  • to Iterate is human to Recurse divine
Απ: Σχολιασμός θεμάτων ΟΕΦΕ 2016?
« Απάντηση #32 στις: 17 Μάι 2016, 11:51:30 μμ »
Έχεις δίκιο, η διατύπωση έχει σοβαρό πρόβλημα, για να το πω ευγενικά  >:D.
αφού ισχύει O(n) = O(2n)
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

SuperTz

  • Βετεράνος
  • ****
  • Μηνύματα: 56
Απ: Σχολιασμός θεμάτων ΟΕΦΕ 2016?
« Απάντηση #33 στις: 26 Μάι 2016, 12:26:08 μμ »
Θα διαφωνήσω.
Ακριβώς αυτό το 2 είναι που κάνει λάθος την επιλογή. Αφού δεν λαμβάνουμε υπόψη το συντελεστή του πολυωνύμου δεν μπορεί να είναι απάντηση το Ο(2η)

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3502
  • to Iterate is human to Recurse divine
Απ: Σχολιασμός θεμάτων ΟΕΦΕ 2016?
« Απάντηση #34 στις: 26 Μάι 2016, 01:23:24 μμ »
Το 2 δεν κάνει καθόλου λάθος την επιλογή διότι πολύ απλά, αν πάρεις το πηλίκο 2n/n με το όριο στο +άπειρο θα δεις ότι το όριο είναι σταθερός αριθμός άρα και τα δυο αυξάνονται κατά τον ίδιο ρυθμό.
Τα πράγματα είναι ξεκάθαρα διότι υπάρχει αυστηρός μαθηματικός ορισμός και η ερμηνεία δεν εναπόκειται στο τι πιστεύει ο καθένας.
Το θέμα είναι λάθος!

Παράθεση
Αφού δεν λαμβάνουμε υπόψη το συντελεστή του πολυωνύμου δεν μπορεί να είναι απάντηση το Ο(2η)
Πολύ σωστά!!! Δεν λαμβάνουμε υπόψη το συντελεστή του πολυωνύμου άρα O(2n) = O(n) = O(100n).
Για αυτό δεν τον λαμβάνουμε. Αυτό δε σημαίνει ότι αν βάλουμε έναν συντελεστή μπροστά αλλάζει η πολυπλοκότητα.
Για παράδειγμα:
T(N) = 2*N + 1 = O(2N) = O(N)
T(N) = N + 1 = O(N)
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

dpa2006

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 684
Απ: Σχολιασμός θεμάτων ΟΕΦΕ 2016?
« Απάντηση #35 στις: 28 Μάι 2016, 11:23:25 πμ »
Έχεις δίκιο, η διατύπωση έχει σοβαρό πρόβλημα, για να το πω ευγενικά  >:D.
αφού ισχύει O(n) = O(2n)
Ακριβώς...!!!
Αν έψαχνε εναλλακτική λαθεμένη απάντηση ας έβαζε κάτι άλλο....!!! :)
Με αυτή τη λογική δύο απαντήσεις του ταυτίζονται.
Δεν έχει δηλαδή τέσσερις πιθανές απαντήσεις αλλά τρεις...

και μια μικρή βιβλιογραφία(ας επαναληφθεί)
http://www.cs.cornell.edu/courses/cs211/2005sp/lectures/l14-bigo/l14-15-complexity.4up.pdf
http://web.engr.oregonstate.edu/~sinisa/courses/OSU/CS261/CS261_Textbook/Chapter04.pdf
http://infolab.stanford.edu/~ullman/focs/ch03.pdf
http://www.spatial.cs.umn.edu/Courses/Spring12/1902/notes/Chapter04-EffeciencyOfAlgorithms.pdf

και το βιβλίο του Μανωλόπουλου
http://www.politeianet.gr/books/9789603120742-manolopoulos-ioannis-art-of-text-domes-dedomenon-protos-tomos-58671
http://okeanos.lib.unipi.gr/Record/P00000011528/Details
Οι Δομές αρχείων πρέπει να έχουν εξαντληθεί από καιρό,ίσως και οι δομές δεδομένων

« Τελευταία τροποποίηση: 28 Μάι 2016, 01:05:12 μμ από dpa2006 »
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

SuperTz

  • Βετεράνος
  • ****
  • Μηνύματα: 56
Απ: Σχολιασμός θεμάτων ΟΕΦΕ 2016?
« Απάντηση #36 στις: 30 Μάι 2016, 07:36:42 μμ »
Θα ήθελα να μου κάνετε μια πρόταση για το πως θα μπορούσε να τεθεί μια πιθανή απάντηση για να διακρίνει αν ο μαθητής έχει καταλάβει την απαλοιφή των συντελεστών από το πολυώνυμο π.χ.

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3502
  • to Iterate is human to Recurse divine
Απ: Σχολιασμός θεμάτων ΟΕΦΕ 2016?
« Απάντηση #37 στις: 30 Μάι 2016, 08:04:00 μμ »
Κοίτα, καταρχήν να ξεκαθαρίσουμε ότι με βάση τις οδηγίες αυτό είναι εκτός ύλης.

Δίνω μια πρόχειρη άσκηση που μου έρχεται στο μυαλό, αλλά θέλει δουλειά στη διατύπωση:

Παρακάτω δίνονται οι χρόνοι υπολογισμού σε συνάρτηση με το μέγεθος εισόδου Ν, για διάφορους αλγορίθμους.
Ποιοι από τους παρακάτω αλγορίθμους έχουν την ίδια πολυπλοκότητα, και ποια είναι αυτή;
Τ1(Ν) = Ν4+496
Τ1(Ν) = Ν + 2Ν
Τ2(Ν) = 6 Ν2+29
Τ3(Ν) = 3 logΝ + 78
Τ4(Ν) = 100 Ν+18
Τ5(Ν) = 0.5 Ν2+4
Τ6(Ν) = 0.5 Ν+100
Τ7(Ν) = Ν2+28
Τ8(Ν) = Ν3+496
Τ9(Ν) = 100 logΝ + 1
Τ10(Ν) = 0.5 Ν+4
Τ11(Ν) = 28 Ν4+28

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

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

  • Βετεράνος
  • ****
  • Μηνύματα: 63
Απ: Σχολιασμός θεμάτων ΟΕΦΕ 2016?
« Απάντηση #38 στις: 31 Μάι 2016, 02:48:15 πμ »
Θα ήθελα να μου κάνετε μια πρόταση για το πως θα μπορούσε να τεθεί μια πιθανή απάντηση για να διακρίνει αν ο μαθητής έχει καταλάβει την απαλοιφή των συντελεστών από το πολυώνυμο π.χ.

SuperTz δεν τίθεται θέμα τέτοιας άσκησης γιατί όπως λέει και ο evry πιό πάνω είναι εκτός ύλης. Θα συμφωνήσω όμως μαζί σου ότι την απάντηση Ο(2n) δεν πρέπει να την επιλέξει κάποιος ως σωστή.

Ο λόγος είναι ο εξής:
 Εφαρμόζουμε τον μαθηματικό ορισμό για να βρούμε την τάξη του αλγορίθμου αλλά εκτός από αυτόν τηρούμε και κάποιους περιορισμούς γιατί αν τον εφαρμόσουμε ως έχει μπορούμε να γράψουμε ότι η τάξη ενός αλγορίθμου Ο(n2) είναι Ο(n3), γιατί ικανοποιεί τον ορισμό, αλλά δεν τον χρησιμοποιούμε έτσι. Όταν γράφουμε λοιπόν ότι η τάξη του αλγορίθμου είναι Ο(g(n)) ζητάμε η g(n) να αποτελεί ένα "σφιχτό όριο" της Τ(n) και να είναι απλή. Για εφαρμογή του τελευταίου περιορισμού δεν γράφουμε ότι ένας αλγόριθμος έχει χρονική πολυπλοκότητα τάξης Ο(cn) αλλά θέτουμε c=1. Επομένως δεν πρέπει να γράψουμε ότι η πολυπλοκότητα ενός αλγορίθμου είναι Ο(2n) αλλά Ο(n)
Είτε γράψουμε ότι η πολυπλοκότητα είναι Ο(2n) είτε Ο(n) μαθηματικά λέμε το ίδιο πράγμα αλλά δεν χρησιμοποιούμε τον συμβολισμό Ο(2n). Αυτό που πιστεύω ότι ζητάει το θέμα είναι η αντιστοίχιση αλγορίθμων με τους χρησιμοποιούμενους , για την πολυπλοκότητα τους, συμβολισμούς big-O.