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

[thymiaras]

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

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

[PDE ads]

[spk]

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

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

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

Το '=' χρησιμοποιείται για να δηλώσει ότι το αριστερό μέλος της ισότητας ισούται με το δεξί και αντίστροφα. Στη συγκεκριμένη περίπτωση είναι αδόκιμο. Κι αυτό διότι αν ισχύει f(n) is O(n^2), δεν ισχύει O(n^2) is f(n). Το όλο πρόβλημα ανάγεται στην προσπάθεια των μαθηματικών να μετατρέψουν την περιγραφική/λεκτική διατύπωση του 'is' σε ένα μαθηματικό σύμβολο. Η γνωστή αναντιστοιχία φραστικής διατύπωσης - μαθηματικού συμβολισμού είναι λεπτομέρεια φυσικά μπροστά σε άλλα σημαντικότερα λάθη του ΑΣΕΠ.

[nobody]

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

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

[banned]

Τελευταίο μου post επί του θέματος.

1) Όταν πρόκειται για λεπτά ζητήματα δεν διαβάζουμε wikipedia. To '=' όντως χρησιμοποιείτε καταχρηστικά αντί του 'ε' (ανήκει) γιατί το Ο ορίζει σύνολο συναρτήσεων, αλλά η 'κατάχρηση' αναφέρεται στον ορισμό.

2) Μάθημα Θεωρία Αλγορίθμων ή Αλγόριθμοι και Πολυπλοκότητα θα (πρέπει να) κάνατε όλοι σίγουρα άρα είναι εντός ύλης.

3) Το να ξέρεις ένα σύμβολο τι σημαίνει, δεν σημαίνει ότι πρέπει να σημαίνει το ίδιο παντού. Π.χ.  το w στα Αγγλικά είναι συνήθως 'γου', ενώ στα γερμανικά 'βου'... ΑΣΧΕΤΟ.

4) Όλη η πληροφορική έγινε αρχικά από μαθηματικούς

5) Όταν κάτι είναι '=' είναι και '<='

6) Το ΑΣΕΠ μπορώ να το κατηγορήσω για 10⁶ λόγους, αλλά να το κάνουμε κάπου που έχουμε άδικο απλώς χάνουμε το δίκιο μας γενικά.

[PDE ads]

[GOODmorning]

Καλημέρα!! Επιτέλους διαβάζω για το πόσο αμφιλεγόμενο είναι το ίσον= σε αυτή την ερώτηση. Συμφωνώ-Πιστεύω ότι όποιος σκέφτηκε καθαρά Μαθηματικά δεν απάντησε το δ αλλά το παραπάνω, ακριβώς γιατί για το δ δεν ισχύει η ισότητα,κατά την γνώμη μου,αλλά προσεγγίζεται η f από την Ο. Αν ίσχυε η ισότητα τότε δεν θα έπρεπε να ξαναμιλήσουμε για Ο(n^2) αλλά για το ίσον του f(..). Bέβαια με την ίδια λογική θα μου πείτε ότι αν ισχύει το γ τότε ισχύει το ίδιο με πριν ότι αντί του Ο(n^2) να χρησιμοποιούμε την f(..) που πάλι δεν ισχύει. Ωστόσο με βάση την ακρίβεια που κανονικά θα έπρεπε να υποδηλλώνεται με το ίσον περισσότερη ακρίβεια και όχι προσσεγγιστικότητα ισχύει στο γ παρά στο δ, τουλάχιστον όσον αφορά την ισότητα από αριστερά προς τα δεξιά  "=>"  . Και εφόσον το "από δεξιά προς τα αριστερά" , δεν μπορεί να ισχύει με τη μορφή της ισότητας (τουλάχιστον με βάση αυτα που ανέφερα παραπάνω) καταλήγω και εγώ προσσεγγιστικά,όπως οι κύριοι του ΑΣΕΠ, στο γ Τί άλλο να πώ βρε συνάδελφοι!!!!δουλείες δεν υπάρχουν και ασχολούμαστε με το γ ή δ!!!!!Μακάρι να βγάλουν σωστό το Δ!!!!! παρόλο που έχω βάλει το γ, μόνο και μόνο για να τους δείξω ότι τουλάχιστον εγώ λυπάμαι που μπήκα στη διαδικασία να ασχοληθώ με αυτούς, έστω έμμεσα στέλνοντας την άποψή μου, ενώ έχω και άλλες "δουλειές"!!!!!!

[skarag1]

Τελευταίο μου post επί του θέματος.

1) Όταν πρόκειται για λεπτά ζητήματα δεν διαβάζουμε wikipedia. To '=' όντως χρησιμοποιείτε καταχρηστικά αντί του 'ε' (ανήκει) γιατί το Ο ορίζει σύνολο συναρτήσεων, αλλά η 'κατάχρηση' αναφέρεται στον ορισμό.

2) Μάθημα Θεωρία Αλγορίθμων ή Αλγόριθμοι και Πολυπλοκότητα θα (πρέπει να) κάνατε όλοι σίγουρα άρα είναι εντός ύλης.

3) Το να ξέρεις ένα σύμβολο τι σημαίνει, δεν σημαίνει ότι πρέπει να σημαίνει το ίδιο παντού. Π.χ.  το w στα Αγγλικά είναι συνήθως 'γου', ενώ στα γερμανικά 'βου'... ΑΣΧΕΤΟ.

4) Όλη η πληροφορική έγινε αρχικά από μαθηματικούς

5) Όταν κάτι είναι '=' είναι και '<='

6) Το ΑΣΕΠ μπορώ να το κατηγορήσω για 10⁶ λόγους, αλλά να το κάνουμε κάπου που έχουμε άδικο απλώς χάνουμε το δίκιο μας γενικά.

Συμφωνώ με spk.
Αντί = θα μπορούσαν να χρησιμοποιοήσουν τη λέξη είναι (is) ή ανήκει ή υποσύνολο αν θέλουμε σωστά μαθηματικά.
Η Wikipedia είναι πάντα in.
H πληροφορική δεν έγινε από μαθηματικούς όπως επίσης ούτε η φυσική. Απλώς πληροφορική και φυσική χρησιμοποίησαν γνωστικά πεδία των μαθηματικών ως υπόβαθρο για την ανάπτυξή τους,

[batman]

Oraio forum o kathe enas leei oti thelei kai to paizei eidimon kai epistimonas
oste i pliroforiki den egine apo mathimatikous e?
na sou po re file
oi parakato ti einai? logotexnes?
knuth
dijkstra
turing
church
shannon
von neumann
george bool
edgar codd
godel

des kai edo kai ante anoikse kanena vivlio
http://en.wikipedia.org/wiki/List_of_computer_scientists
ektos fisika an den tous exeis akouse pote opote ok.

kai ase min asxoleisai me tin fisiki, einai gnosto oti palia oloi itan taytoxrona kai fisikoi kai mathimatikoi kati to opoio agnoeis
newton, gauss, kopernikos, keppler
ti itan aytoi filologoi?

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

[aroniotis]

Batman, εδωσες wiki! Δεν είναι επιστημονικά τεκμηριωμένη η απάντηση σου! Στη πυρά! 

[skarag1]

Ένα μπράβο στον thymiaras που παραδέχτηκε το λάθος του. Δείχνει το (υψηλό) επίπεδό του.

[spk]

Τελικά παιδιά έχετε και σεις τα δίκια σας ! Είδα τον ορισμό του Ο σε κάτι ξεχασμένες σημειώσεις του Μανωλόπουλου από τη σχολή και είχε πραγματικά το ζητούμενο άθροισμα ίσο με Ο(n^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) κτλ ...

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

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

Για όλους αυτούς τους λόγους και για πολλούς άλλους, προτιμώ τα ξενόγλωσσα κείμενα, αυτούσια. Το ΑΣΕΠ όμως εσκεμμένα δεν μας λέει πουθενά ποια βιβλία προτιμάει ως ύλη. Αν προτιμήσει 2 ξένα θα ξεσηκωθούν όλοι οι Ελληνες καθηγητές (βλέπε κέρδη από εκδόσεις). Αν προτιμήσει 2 ελληνικά θα ξεσηκωθούν οι υπόλοιποι Ελληνες καθηγητές που θα μείνουν εκτός. Οπότε προκειμένου να μη δημιουργήσει θέμα, νίπτει τας χείρας του...πετώντας το μπαλάκι στους υποψηφίους που δε φταίνε σε τίποτα. Ή μήπως φταίνε, γιατί με τη συμπεριφορά τους συμβάλλουν στη διαιώνιση της κατάστασης; Τελικά, καθόμαστε και ασχολούμαστε με ένα πρόβλημα το οποίο δεν δημιουργήσαμε εμείς. Εμείς όμως συμβάλλαμε με την ανοχή μας στο να υπάρχουν οι προϋποθέσεις για να υφίσταται σήμερα το πρόβλημα. Φυσικά, όταν ένα χέρι πονάει (ΑΣΕΠ) η λύση δεν είναι να το κόψουμε. Η λύση βρίσκεται στη θεραπεία (βελτίωση) του. Κάποιοι μάχονται ποικιλοτρόπως για το κόψιμο του χεριού, γιατί δεν τους βολεύει, αλλά δεν θα τους περάσει.

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

Θέλετε κι άλλο παράδειγμα; Υπάρχουν καθηγητές με πτυχία αποκλειστικά μαθηματικών που διδάσκουν πληροφορική σε τριτοβάθμια ιδρύματα. Αυτοί ή θα έπρεπε να απορροφηθούν από τα τμήματα μαθηματικών ή να μετεκπαιδευτούν στην πληροφορική ή να αλλάξουν αντικείμενο εγκαταλείποντας τα αμφιθέατρα. Το πρώτο δεν είναι εφικτό, το δεύτερο έχει πολιτικό κόστος και το τρίτο απαγορεύεται από το Σύνταγμα καθώς οι καθηγητές ΑΕΙ είναι ισόβιοι.

[GOODmorning]

Μία παράκληση προς όλους σας από μεριάς μου:Μιας και υπάρχουν πολλές επισκέψεις'  Κλείνετε τα μηνύματά σας με το ΠΛΗΡΩΣ ΑΥΤΟΝΟΗΤΟ και ΚΟΙΝΩΣ ΠΑΡΑΔΕΚΤΟ ΜΉΝΥΜΑ ΣΤΟ ΟΠΟΙΟ ΣΥΜΦΩΝΟΥΜΕ ΟΛΟΙ:
 ΑΠΑΙΤΩ ΝΑ

[petrosp_13]

Επανέρχομαι στην πολύκροτη παράσταση Σ=1+2+3...+Ν
Το σχολικό βιβλίο της Ανάπτυξης Εφαρμογών που αναφέρθηκαν πολλοί για να υποστηρίξουν ότι είναι πολυπλοκότητας ν^2, δεν αναφέρεται στην πολυπλοκότητα υπολογισμού αυτής της παράστασης στην παράγραφο 5.3.1.
Μιλάει για τον αλγόριθμο φυσαλίδας, όπου γίνονται συγκρίσεις, των οποίων ο αριθμός εξαρτάται από το μέγεθος του πίνακα (ν)
Όταν το μέγεθος του πίνακα είναι ν, απαιτούνται 1+2+3+...+ν-1 ΣΥΓΚΡΙΣΕΙΣ, δηλαδή ΕΝΤΟΛΕΣ
Οπότε μιλάμε για ν*(ν-1)/2 ΕΝΤΟΛΕΣ, δηλαδή είναι πολυπλοκότητας ν^2

Η παράσταση που μας δόθηκε στον διαγωνισμό ήθελε να υπολογίσουμε το άθροισμα 1+2+3+...+ν για το οποίο αρκούν ν ΕΠΑΝΑΛΗΨΕΙΣ, ν ΕΝΤΟΛΕΣ και όχι ν*(ν+1)/2.
Άρα, θεωρώ ότι η ερώτηση είναι ή κακοδιατυπωμένη, ή η μόνη σωστή απάντηση είναι η Ο(ν)

Ας βγάλουν τις όποιες απαντήσεις τους να ξέρουμε τουλάχιστον τι θεωρούν αυτοί σωστό

[nobody]

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

Για όλους αυτούς τους λόγους και για πολλούς άλλους, προτιμώ τα ξενόγλωσσα κείμενα, αυτούσια. Το ΑΣΕΠ όμως εσκεμμένα δεν μας λέει πουθενά ποια βιβλία προτιμάει ως ύλη. Αν προτιμήσει 2 ξένα θα ξεσηκωθούν όλοι οι Ελληνες καθηγητές (βλέπε κέρδη από εκδόσεις). Αν προτιμήσει 2 ελληνικά θα ξεσηκωθούν οι υπόλοιποι Ελληνες καθηγητές που θα μείνουν εκτός. Οπότε προκειμένου να μη δημιουργήσει θέμα, νίπτει τας χείρας του...πετώντας το μπαλάκι στους υποψηφίους που δε φταίνε σε τίποτα. Ή μήπως φταίνε, γιατί με τη συμπεριφορά τους συμβάλλουν στη διαιώνιση της κατάστασης; Τελικά, καθόμαστε και ασχολούμαστε με ένα πρόβλημα το οποίο δεν δημιουργήσαμε εμείς. Εμείς όμως συμβάλλαμε με την ανοχή μας στο να υπάρχουν οι προϋποθέσεις για να υφίσταται σήμερα το πρόβλημα. Φυσικά, όταν ένα χέρι πονάει (ΑΣΕΠ) η λύση δεν είναι να το κόψουμε. Η λύση βρίσκεται στη θεραπεία (βελτίωση) του. Κάποιοι μάχονται ποικιλοτρόπως για το κόψιμο του χεριού, γιατί δεν τους βολεύει, αλλά δεν θα τους περάσει.

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

Θέλετε κι άλλο παράδειγμα; Υπάρχουν καθηγητές με πτυχία αποκλειστικά μαθηματικών που διδάσκουν πληροφορική σε τριτοβάθμια ιδρύματα. Αυτοί ή θα έπρεπε να απορροφηθούν από τα τμήματα μαθηματικών ή να μετεκπαιδευτούν στην πληροφορική ή να αλλάξουν αντικείμενο εγκαταλείποντας τα αμφιθέατρα. Το πρώτο δεν είναι εφικτό, το δεύτερο έχει πολιτικό κόστος και το τρίτο απαγορεύεται από το Σύνταγμα καθώς οι καθηγητές ΑΕΙ είναι ισόβιοι.

Δηλαδή στα πανεπιστήμια του εξωτερικού, όλοι οι καθηγητές που διδάσκουν σε τμήματα Πληροφορικής είναι απόφοιτοι τμημάτων Πληφορικής; Κριτήριο για την πρόσληψη ενός καθηγητή σε Πανεπιστήμια σε όλο τον κόσμο είναι (τυπικά τουλάχιστον)  οι δημοσιεύσεις σε μια συγκεκριμένη ερευνητική περιοχή και όχι το πτυχίο του.

[nobody]

Η παράσταση που μας δόθηκε στον διαγωνισμό ήθελε να υπολογίσουμε το άθροισμα 1+2+3+...+ν για το οποίο αρκούν ν ΕΠΑΝΑΛΗΨΕΙΣ, ν ΕΝΤΟΛΕΣ και όχι ν*(ν+1)/2.
Άρα, θεωρώ ότι η ερώτηση είναι ή κακοδιατυπωμένη, ή η μόνη σωστή απάντηση είναι η Ο(ν)
Ας βγάλουν τις όποιες απαντήσεις τους να ξέρουμε τουλάχιστον τι θεωρούν αυτοί σωστό

Η σχέση υπάρχει αυτούσια σε βιβλία Θεωρίας Αλγορίθμων και Δομών Δεδομένων τα οποία είναι εντός ύλης όπως εδώ. Ή ξέρεις τη σχέση ή δεν την ξέρεις(αν και η απόδειξη είναι απλή) και δεν υπάρχει θέμα κακοδιατυπωμένης ερώτησης (τουλάχιστον εδώ).