ΠΕ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.

[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. Ο θεός βοηθός τώρα για το ποια απάντηση θα δώσει σωστή ο ΑΣΕΠ