ΠΕ19-ΠΕ20 - ασεπ 2009-γνωστικο

[banned]

re thymiara pragmatika eisai theos!!!!!
ti algorithmara einai ayti pou petakses?
"sum=n;
sum=sum*(n-1);
sum=sum/2;"
to  sum:=n*(n-1)/2 se xalage na to grapseis monokomato?!?!

Pes oti kaneis plaka giati thaxoume mazikes aytoktonies sto forum. Toulaxiston ksexname to agxos ton apotelesmaton. Pes mou pantos apo periergeia apo poio tmima pires to ptyxio sou? (gm to Elliniko Kratos gm)

[PDE ads]

[thymiaras]

re thymiara pragmatika eisai theos!!!!!
ti algorithmara einai ayti pou petakses?
"sum=n;
sum=sum*(n-1);
sum=sum/2;"
to  sum:=n*(n-1)/2 se xalage na to grapseis monokomato?!?!

Pes oti kaneis plaka giati thaxoume mazikes aytoktonies sto forum. Toulaxiston ksexname to agxos ton apotelesmaton. Pes mou pantos apo periergeia apo poio tmima pires to ptyxio sou? (gm to Elliniko Kratos gm)

Banned το έκανα επίτηδες έτσι "λιανά" γιατί αν παρατηρήσεις την συζήτηση στο συγκεκριμένο θέμα θα δεις ότι τίποτα δεν θεωρείται αυτονόητο ακόμα και τα πιο απλά πράγματα. Απλά ξεχώρισα τις πράξεις για να φανεί ότι η πολυπλοκότητα είναι σταθερή και ίση με O(3) (αν θεωρήσουμε όλες τις πράξεις καθώς και την ανάθεση τιμής ισοδύναμες). Αρκεί απλά να φανταστείς ότι κάποιοι πιστεύουν ότι ο συγκεκριμένος αλγόριθμος έχει πολυπλοκότητα O(n^2).

[NEF]

Συγγνώμη που παρεμβαίνω αλλά νομίζω ότι κάνετε όλοι λάθος. Αν τρέξετε το παρακάτω τμήμα κώδικα θα καταλάβετε ποια είναι η πολυπλοκότητα.. το λέει καθαρά 

 int main()
{
  printf ("%s \n", "O(n^3)");
  return 0;
}

[aroniotis]

Συγγνώμη που παρεμβαίνω αλλά νομίζω ότι κάνετε όλοι λάθος. Αν τρέξετε το παρακάτω τμήμα κώδικα θα καταλάβετε ποια είναι η πολυπλοκότητα.. το λέει καθαρά 

 int main()
{
  printf ("%s \n", "O(n^3)");
  return 0;
}

Συμφωνω με NEF! Το έτρεξα καί όντως βγάζει n^3! Την πατήσαμε όλοι μας!

[PDE ads]

[NEF]

Διαβάστε λίγο καλύτερα τη 17 ερώτηση γιατί νομίζω ότι μαλώνετε άδικα:

[thymiaras]

Εγώ και πάλι το γ διαλέγω   

[banned]

  xaxaxa θαυμάζω την όρεξή σου ρε NEF.

thymiara αγόρι μου άκου και μη νομίζεις ότι είναι προσωπικό.

Το μυστικό είναι στο ΟΡΙΣΜΟ του Ο(), που λέει ότι:

το f(n) = O(g(n)) σημαίνει ότι υπάρχουν θετικοί αριθμοί c και k, τέτοια ώστε  0 ≤ f(n) ≤ c*g(n) για κάθεl n ≥ k.
Με άλλα λόγια αυτό σημαίνει ότι η συνάρτηση g() από την τιμή k και μετά αρχίζει και αυξάνεται με γρηγορότερο (ή ίδιο) ρυθμό από την συνάρτηση f(). ΔΕΝ ΛΕΕΙ ΠΟΥΘΕΝΑ ΓΙΑ ΑΛΓΟΡΙΘΜΟΥΣ. ΞΕΧΝΑ ΤΟΥΣ. ΜΟΝΟ ΣΥΝΑΡΤΗΣΕΙΣ.

Τώρα, αυτοί σου λένε ότι το Σ_{1}^{n} k είναι ΣΥΝΑΡΤΗΣΗ του n, άρα f(n)=Σ_{1}^{n} k=n*(n-1)/2. Ποια συνάρτηση τώρα πάει τουλάχιστον τόσο γρήγορα όσο η f??? H g(n)=n^2.

Πουθενα δεν υπάρχει αλγόριθμος. Σκέτα Μαθηματικά. Γι' αυτό μπερδεύεσαι.
...
Και είναι λίγο εκνευριστικό που δεν το ξέρεις γιατί θα'πρεπε να το έχεις κάνει από το 1ο -2ο έτος.
 

[nobody]

Εγώ και πάλι το γ διαλέγω   

Ακόμα και μετά το link που παρέθεσα διαλέγεις το γ;

[batman]

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

Εγώ και πάλι το γ διαλέγω   

Ακόμα και μετά το link που παρέθεσα διαλέγεις το γ;

[thymiaras]

Τελικά παιδιά έχετε και σεις τα δίκια σας ! Είδα τον ορισμό του Ο σε κάτι ξεχασμένες σημειώσεις του Μανωλόπουλου από τη σχολή και είχε πραγματικά το ζητούμενο άθροισμα ίσο με Ο(n^2). Ακόμα και τώρα όμως δε μπορώ να το συλλάβω διαισθητικά. Πάντως εφόσον υπάρχει τρόπος υπολογισμού του αθροίσματος με Ο(n) (με τον πολύ απλό αλγόριθμο μονής επανάληψης που έχω δώσει σε προηγούμενο ποστ) στην ουσία το Ο(n) ισχύει και είναι μια"σφικτότερη" πολυπλοκότητα από το O(n^2). Οπότε και τα 2 είναι σωστά. Παραθέτω και ένα κομμάτι των σημειώσεων για να καταλάβετε τι εννοώ :

" Οι συμβολισμοί Ο, Ω και Θ μπορεί να είναι περισσότερο ή λιγότερο περιοριστικοί ή σφικτοί (tight). Για παράδειγμα είναι ευνόητο ότι ισχύει τόσο 2n^2 = O(n^2) όσο και 2n = O(2n^2), όπου όμως η δεύτερη έκφραση είναι λιγότερο περιοριστική. Χρειαζόμαστε λοιπόν περισσότερο σφικτούς συμβολισμούς."
και στη συνέχεια δίνει τον ορισμό του ο .

Δηλαδή αν ισχύει f(n) = O(n^2) τότε για την ίδια f(n) ισχύει και f(n) = O(n^3) , f(n) = O(n^4) κτλ ...

[skarag1]

Για το επίμαχο θέμα βρήκα αυτό. Σελίδα 3, παράδειγμα 4. Είναι η λύση που θέλουμε.
http://www.cs.utsa.edu/~bylander/cs3233/big-oh.pdf

[spk]

το f(n) = O(g(n)) σημαίνει ότι υπάρχουν θετικοί αριθμοί c και k, τέτοια ώστε  0 ≤ f(n) ≤ c*g(n) για κάθεl n ≥ k.
Με άλλα λόγια αυτό σημαίνει ότι η συνάρτηση g() από την τιμή k και μετά αρχίζει και αυξάνεται με γρηγορότερο (ή ίδιο) ρυθμό από την συνάρτηση f(). ΔΕΝ ΛΕΕΙ ΠΟΥΘΕΝΑ ΓΙΑ ΑΛΓΟΡΙΘΜΟΥΣ. ΞΕΧΝΑ ΤΟΥΣ. ΜΟΝΟ ΣΥΝΑΡΤΗΣΕΙΣ.

Τώρα, αυτοί σου λένε ότι το Σ_{1}^{n} k είναι ΣΥΝΑΡΤΗΣΗ του n, άρα f(n)=Σ_{1}^{n} k=n*(n-1)/2. Ποια συνάρτηση τώρα πάει τουλάχιστον τόσο γρήγορα όσο η f??? H g(n)=n^2.

Πουθενα δεν υπάρχει αλγόριθμος. Σκέτα Μαθηματικά. Γι' αυτό μπερδεύεσαι.
...
Και είναι λίγο εκνευριστικό που δεν το ξέρεις γιατί θα'πρεπε να το έχεις κάνει από το 1ο -2ο έτος.

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

Το ζήτημα είναι ότι ΠΟΥΘΕΝΑ στην ύλη που ανακοίνωσε το ΑΣΕΠ δεν αναφέρει κάτι σχετικό με 'σκέτα μαθηματικά' ή 'συναρτήσεις' ή 'διακριτά μαθηματικά' ή έστω κάτι παρεμφερές για τους ΠΕ19/ΠΕ20. Βάσει αυτού του γεγονότος και γνωρίζοντας ότι ο περιβόητος συμβολισμός Big-O υιοθετήθηκε τον τελευταίο αιώνα πρώτα από τους μαθηματικούς και μεταγενέστερα από τους πληροφορικούς...φτάνοντας σήμερα στο σημείο να χρησιμοποιείται και από τους δύο...απάντησα ως ΠΕ Πληροφορικής, όχι ως ΠΕ Μαθηματικός. Να μη μας διαφεύγει επίσης ότι υπάρχουν αυτή τη στιγμή άνθρωποι που κατέχουν και τα δύο πτυχία (μαθηματικών, πληροφορικής) έχοντας δώσει κατατακτήριες για τη μετάβαση από το ένα τμήμα στο άλλο.

Αντιγράφω λοιπόν από τη Wikipedia:

Although developed as a part of pure mathematics, it is now frequently also used in computational complexity theory to describe an algorithm's usage of computational resources (usually running time or memory) with respect to the size of the input data. It is also used in many other fields to provide similar estimates.

The statement "f(x) is O(g(x))" as defined above is usually written as f(x) = O(g(x)). This is a slight abuse of notation; equality of two functions is not asserted, and it cannot be since the property of being O(g(x)) is not symmetric:
O(x)=O(x^2) but O(x^2) != O(x)

Επίσης, ενώ η ισότητα είναι ένα σύμβολο που χρησιμοποιείται κατά κόρον από τους μαθηματικούς, ορισμένοι επιστήμονες της πληροφορικής αποφεύγουν να χρησιμοποιούν το σύμβολο '=' μεταξύ f και O. Αυτοί, επιλέγουν ως περισσότερο ακριβή τη διατύπωση 'f is O' αντί 'f = Ο' (για τον λόγο που αναφέρει και η wikipedia). Στα πανεπιστήμια βέβαια (και όχι μόνο) υπάρχουν πολλών κατηγοριών καθηγητές: οι σκέτοι μαθηματικοί, οι σκέτοι πληροφορικοί και οι πρώην μαθηματικοί που εξελίχθηκαν σε πληροφορικούς...

Για παράδειγμα, το National Institute of Standards and Technology των ΗΠΑ (το δημοφιλέστερο site παγκοσμίως στην υποκατηγορία: Science >  Reference >  Standards) φιλοξενεί το Dictionary of Algorithms and Data Structures, όπου μεταξύ άλλων αναφέρει για την περιβόητη Big-O:

Note: As an example, n² + 3n + 4 is O(n²), since n² + 3n + 4 < 2n² for all n > 10. Strictly speaking, 3n + 4 is O(n²), too, but big-O notation is often misused to mean equal to rather than less than. The notion of "equal to" is expressed by Θ(n).

Προφανώς, αν n² + 3n + 4 = O(n²) και 3n + 4 = O(n²) -> n² + 3n + 4 = 3n + 4. Το Big-O όμως εκφράζει άνω φράγμα, το οποίο ακριβέστερα ισοδυναμεί με '<=' όχι με '=' όπως καταχρηστικά χρησιμοποιείται.

Τονίζω και πάλι ότι από μαθηματικής πλευράς οι συλλογισμοί που παρατίθενται στο τρέχον νήμα είναι σωστοί. Από πληροφορικής όμως το Big-O εκφράζει time/space complexity. Η πρώτη εκδοχή είναι εκτός ύλης, ενώ η δεύτερη εντός. Ακρίβεια διατύπωσης; Εξεταστέα ύλη; Ψιλά γράμματα για το ΑΣΕΠ θα μου πείτε και θα έχετε δίκιο...είδαμε τι έγινε με την επίσημη ανακοίνωση αποτελεσμάτων για βιολόγους/φυσικούς/χημικούς.

[batman]

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

Για το επίμαχο θέμα βρήκα αυτό. Σελίδα 3, παράδειγμα 4. Είναι η λύση που θέλουμε.
http://www.cs.utsa.edu/~bylander/cs3233/big-oh.pdf

@spk
Αυτό το οποίο επικαλείσαι είναι αντιεπιστημονικό. Δηλαδή πες ότι σου έδιναν έναν αλγόριθμο και σου έλεγαν να υπολογίσεις την τάξη της πολυπλοκότητάς του. Τι θα έλεγες? θα έφτανες μέχρι ένα σημείο και μετά θα έγραφες ότι από εδώ και πέρα είναι δουλειά μαθηματικού?
Το θέμα όπως δόθηκε απλά δεν ήταν κατανοητό από μεγάλη μερίδα αποφοίτων πληροφορικής που δεν έχει διδαχθεί την αντίστοιχη θεωρία, για αυτό έχει γίνει όλος αυτός ο χαμός.

Επίσης τα τελευταία που γράφεις είναι όλα λάθος.
όταν γράφεις f(n) = O(n²) σημαίνει ότι υπάρχει C τέτοιο ώστε f(n) <= C n²
δεν έχει νόημα ανισότητα με big-O notation

[thymiaras]

Τονίζω και πάλι ότι από μαθηματικής πλευράς οι συλλογισμοί που παρατίθενται στο τρέχον νήμα είναι σωστοί. Από πληροφορικής όμως το Big-O εκφράζει time/space complexity. Η πρώτη εκδοχή είναι εκτός ύλης, ενώ η δεύτερη εντός. Ακρίβεια διατύπωσης; Εξεταστέα ύλη; Ψιλά γράμματα για το ΑΣΕΠ θα μου πείτε και θα έχετε δίκιο...είδαμε τι έγινε με την επίσημη ανακοίνωση αποτελεσμάτων για βιολόγους/φυσικούς/χημικούς.

Για αυτό ακριβώς και έβγαζα τους συλλογισμούς των "άλλων" λανθασμένους. Γιατί εγώ μετρούσα time/space complexity και μου φαίνονταν αδιανόητα τα όσα υποστήριζαν οι άλλοι. Αλλά τελικά it was a matter of perspective. Ο θεός βοηθός τώρα για το ποια απάντηση θα δώσει σωστή ο ΑΣΕΠ