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

[aroniotis]

Τα πράγματα είναι πολύ απλά σε σχέση με την περιβόητη ερώτηση 17. Το θέμα δεν είναι ποια απάντηση είναι επιστημονικά ορθή γιατί πολύ απλά είναι κακοδιατυπωμένη η ερώτηση. Ε

Εγώ πάντως δεν θεωρώ πως η συγκεκριμένη είναι κακοδιατυπωμένη. Θεωρώ ότι είναι απόλυτα ακριβής. Υπάρχουν άλλες που είναι κακοδιατυπωμένες, αλλά όχι αυτή

[PDE ads]

[elia]

Σχετικά με την ερώτηση 29 : τα βιβλία του Γυμνασίου (και το παλιό και το καινούριο) χρησιμοποιούν τον όρο οδηγός συσκευής και για λογισμικό αλλά και για υλικό. Στη σελίδα 19 του καινούριου βιβλίου αναφέρει "Οι δισκέτες και οι ψηφιακοί δίσκοι τύπου CD και DVD χρειάζονται ειδικές συσκευές, τους οδηγούς ή τις μονάδες, για να μπορέσουμε να διαβάσουμε ή να γράψουμε δεδομένα σε αυτές". Άρα θεωρώ ότι το ΑΣΕΠ θα πρέπει να θεωρήσει την απάντηση γ ως σωστή.

[Alexhs_27]

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

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

[spk]

Και καθόμαστε όλοι εδώ και προσπαθούμε να πείσουμε για τα αυτονόητα.

Αυτονόητα;

41. Πόσο χρόνο απαιτεί η αναζήτηση ενός στοιχείου, βάσει του κλειδιού του, σε πίνακα κατακερματισμού (hash table) k θέσεων που περιέχει n στοιχεία;
α) O(n)
β) O(logn)
γ) O(n/k)
δ) O(nlogk)

http://en.wikipedia.org/wiki/Hash_table

hash tables provide constant-time O(1) lookup on average, regardless of the number of items in the table. While theoretically the worst-case lookup time can be as bad as O(n), this is, for practical purposes, statistically unlikely unless the hash function is poorly designed or unless the set of keys is maliciously chosen with the given hash function in mind. These corner cases are addressed in mathematical analysis with the Simple Uniform Hashing Assumption.

http://en.wikipedia.org/wiki/SUHA

Under the assumption of uniform hashing, the average time (in big-O notation) to successfully find an element in a hash table using chaining is Ο(1).

http://en.wikipedia.org/wiki/Cuckoo_hashing

Lookup requires inspection of just two locations in the hash table, which takes constant time in the worst case (see Big O notation). This is in contrast to many other hash table algorithms, which may not have a constant worst-case bound on the time to do a lookup.

A study by Zukowski et al.[3] has shown that cuckoo hashing is much faster than chained hashing for small, cache-resident hash tables on modern processors. Kenneth Ross[4] has shown bucketized versions of cuckoo hashing (variants that use buckets that contain more than one key) to be faster than conventional methods also for large hash tables, when space utilization is high. However as of 2007 cuckoo hashing remains largely unknown outside the research community.

Ευτυχώς στην 41 δεν υπήρχαν ως πιθανές απαντήσες οι Ο(1) και Ο(n). Γιατί τότε:
α) worst case uniform hashing -> O(n)
β) worst case cuckoo hashing -> O(1)

Αυτονόητα δεν είναι ούτε η χρησιμοποιούμενη τεχνική κατακερματισμού ούτε πολλά άλλα στις ερωτήσεις του ΑΣΕΠ όπως είναι διατυπωμένες. Στη συγκεκριμένη περίπτωση η βιβλιογραφία αναφέρει διαφορετικά Big-O για average/worst. Τέλος, το γεγονός ότι πολλοί σήμερα δε γνωρίζουν την cuckoo hashing, δε σημαίνει κάτι. Υπάρχει, και δίνει O(1) στη χειρότερη περίπτωση.

Αυτονόητο δεν είναι επίσης ότι ορθή είναι η απάντηση που πηγάζει από το τρέχον σχολικό βιβλίο Πληροφορικής. Ένα τέτοιο βιβλίο μπορεί να έχει γραφεί πριν από 5-10 χρόνια, να κυκλοφορεί ως 5-10η έκδοση στα σχολεία και να αναφέρει το δίσκο DVD ως το πλέον σύγχρονο μέσο για την αποθήκευση βίντεο, ενώ όλοι γνωρίζουμε σήμερα για την ύπαρξη των δίσκων Blue-ray. Όταν το ΑΣΕΠ ανακοινώνει ύλη θα πρέπει να είναι πιο συγκεκριμένο παραθέτοντας σχετική βιβλιογραφία (είτε σχολική είτε ακαδημαϊκή είτε οποιαδήποτε άλλη).

Αυτό με το οποίο διαφωνώ είναι η τακτική του ΑΣΕΠ να ζητά από τους υποψηφίους να προβούν σε "αυτονόητες" παραδοχές αντί να διευκρινίζει με ορισμένες λέξεις-κλειδιά σε τι ακριβώς αναφέρεται. Θεωρώ πλέον ότι η στρατηγική αυτή αποτελεί συνειδητή επιλογή. Το πρόβλημα που δημιουργεί αυτή η τακτική δεν αφορά τόσο τους υποψηφίους (συμπεριλαμβανομένου και του υποφαινόμενου) που έχουν ήδη 45/53 σωστές απαντήσεις και αναμένουν να δουν τις υπόλοιπες. Αφορά κυρίως αυτούς που βρίσκονται στο όριο της βαθμολογικής βάσης. Εν ολίγοις νομίζω ότι η κακή διατύπωση των θεμάτων αποσκοπεί κυρίως στην αύξηση των αποτυχόντων.

[PDE ads]

[thymiaras]

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

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

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

[elia]

Αυτονόητο δεν είναι επίσης ότι ορθή είναι η απάντηση που πηγάζει από το τρέχον σχολικό βιβλίο Πληροφορικής. Ένα τέτοιο βιβλίο μπορεί να έχει γραφεί πριν από 5-10 χρόνια, να κυκλοφορεί ως 5-10η έκδοση στα σχολεία και να αναφέρει το δίσκο DVD ως το πλέον σύγχρονο μέσο για την αποθήκευση βίντεο, ενώ όλοι γνωρίζουμε σήμερα για την ύπαρξη των δίσκων Blue-ray. Όταν το ΑΣΕΠ ανακοινώνει ύλη θα πρέπει να είναι πιο συγκεκριμένο παραθέτοντας σχετική βιβλιογραφία (είτε σχολική είτε ακαδημαϊκή είτε οποιαδήποτε άλλη).

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

[nobody]

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

Αναφέρει η ερώτηση ότι πρόκειται για αλγόριθμο του αθροίσματος; Ούτε καν τον αλγόριθμο δεν δίνει. Αντίθετα η σχέση που ζητά υπάρχει στα περισσότερα βιβλία αλγορίθμων και Δομών Δεδομένων αυτούσια, ως έχει (οπότε ναι, είναι εντός ύλης). Για παράδειγμα, ένα από τα καλύτερα βιβλία που υπάρχουν στον τομέα αυτό, το Introduction to Algorithms, Second Edition  Thomas H. Cormen  Charles E. Leiserson  Ronald L. Rivest  Clifford Stein The MIT Press,  στη σελίδα 1059 έχει ακριβώς αυτή τη σχέση. Μπορείτε να τη δείτε και όσοι δεν έχετε το βιβλίο από τη σελίδα αυτή. Υπάρχει ακόμα κανένας που πιστεύει ότι η πολυπλοκότητα είναι Ο(n);

[anastasi21]

Συγνώμη παιδιά που θα σας "την σπάσω" για ακόμη μια φορά αλλά πάλι κάνετε λάθος. Καλά για τα παραδείγματα του βιβλίου που αναφέρονται δε θα μπω στη διαδικασία να τα περιγράψω γιατί όλοι καταλαβαίνουν ότι είναι άσχετα με τη συγκεκριμένη ερώτηση. Ας δώσω κάποια σχόλια για τη συγκεκριμένη ερώτηση.
Όταν δίνει το σύμβολο του αθροίσματος Σ και ζητάει να πούμε αν είναι Ο(n) ή Ο(n^2) φυσικά και δεν ζητάει συγκεκριμένο αλγόριθμο υλοποίησης απλά μας λέει να βασιστούμε στον ορισμό του αθροίσματος τον οποίο υποθέτει ότι όλοι μας τον ξέρουμε. Γιατί ο ορισμός του αθροίσματος αποτελεί από μόνος του αλγόριθμο υπολογισμού του αθροίσματος.
Το δ είναι ΛΑΘΟΣ γιατί το n(n-1)/2 στο οποίο βασίζονται όσοι επιλέγουν το Δ ΔΕΝ μας δίνει πολυπλοκότητα, μας δίνει το αποτέλεσμα (με τι ισούται δηλαδή το αριστερό μέρος της ισότητας). Δηλαδή αν π.χ. μας δίναν ότι το n=10 τότε ο παραπάνω τύπος θα μας έδινε: Σk για k=1 μέχρι 10 =45, OXI ME O(45). Αν δεν μπορείτε να το καταλάβετε αυτό με γεια σας με χαρά σας.

Είσαι πολύ λάθος και επιμένεις χωρίς λόγο. Μπορείς να μας δώσεις έναν αλγόριθμο σε οποιαδήποτε γλώσσα που να υπολογίζει το άθροισμα n όρων αριθμητικής προόδου, το οποίο είναι και ζητούμενο στην περιβόητη ερώτηση 17, με πολυπλοκότητα Ο(n); Εγώ προκαταβολικά θα σου πω ότι δεν υπάρχει για τον πολύ απλό λόγο ότι κάτι τέτοιο θα ίσχυε μόνο αν επρόκειτο για άθροισμα n ίδιων αριθμών (π.χ. c+c+...+c=c*n=O(n)). Εδώ όμως έχουμε διαφορετικούς αριθμούς και για να υπολογίσουμε το άθροισμά τους πρέπει να εφαρμόσουμε διπλή επανάληψη στον αλγόριθμο. Παραθέτω κι ένα παράδειγμα σε C που υπολογίζει το άθροισμα αυτό:

for (k=1; k <=n; k++) {
   for (j=1; j <= k; j++)
   sum=sum+j;
}

Η πολυπλοκότητά του είναι: n επαναλήψεις από το πρώτο for loop και n+1 προσθέσεις σε κάθε επανάληψη (n για τον υπολογισμό του όρου j που θα προστεθεί στο μερικό άθροισμα sum και 1 για τον υπολογισμό του νέου μερικού αθροίσματος. Οπότε συνολικά n*(n+1) πράξεις και άρα O(n²). Περιμένω τη δική σου υλοποίηση με πολυπλοκότητα O(n).

[aroniotis]

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

Αναφέρει η ερώτηση ότι πρόκειται για αλγόριθμο του αθροίσματος; Ούτε καν τον αλγόριθμο δεν δίνει. Αντίθετα η σχέση που ζητά υπάρχει στα περισσότερα βιβλία αλγορίθμων και Δομών Δεδομένων αυτούσια, ως έχει (οπότε ναι, είναι εντός ύλης). Για παράδειγμα, ένα από τα καλύτερα βιβλία που υπάρχουν στον τομέα αυτό, το Introduction to Algorithms, Second Edition  Thomas H. Cormen  Charles E. Leiserson  Ronald L. Rivest  Clifford Stein The MIT Press,  στη σελίδα 1059 έχει ακριβώς αυτή τη σχέση. Μπορείτε να τη δείτε και όσοι δεν έχετε το βιβλίο από τη σελίδα αυτή. Υπάρχει ακόμα κανένας που πιστεύει ότι η πολυπλοκότητα είναι Ο(n);

ΡΕ παίδες, όσοι επιμένετε δείτε αυτό που έδωσε ο nobody και σταματήστε πια! Κουραστικό κατάντησε! Άντε πια με αυτό το θέμα...

[Alexhs_27]

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

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

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

Φίλε μου η ερώτηση δεν μιλάει για κανένα συγκεκριμένο αλγόριθμο, μιλάει για συγκεκριμένη συνάρτηση. Ξαναδιάβασε την ερώτηση και πες μου που βλέπεις τη λέξη αλγόριθμο.

17. Στις παρακάτω ισότητες θεωρήστε το αριστερό μέλος ως συνάρτηση του n. Ποιά από τις ισότητες ισχύει;

ΥΓ: Λοιπόν,επειδή το έχουμε κουράσει το θέμα και επαναλαμβανόμαστε ας τ' αφήσουμε εδώ. Δε βγάζουμε άκρη... Αύριο, θα δώσει ο ΑΣΕΠ τις απαντήσεις και θα ξέρουμε στα σίγουρα.

[kripintiris]

Αυτό με το οποίο διαφωνώ είναι η τακτική του ΑΣΕΠ να ζητά από τους υποψηφίους να προβούν σε "αυτονόητες" παραδοχές αντί να διευκρινίζει με ορισμένες λέξεις-κλειδιά σε τι ακριβώς αναφέρεται. Θεωρώ πλέον ότι η στρατηγική αυτή αποτελεί συνειδητή επιλογή.

Συμφωνώ απόλυτα με τα παραπάνω λόγια του spk. Θεωρώ ότι προς αυτή την κατεύθυνση τους ωθούν και οι οδηγίες του ΥΠΕΠΘ, τουλάχιστον για τη δική μας ειδικότητα. Αφού οι 1050 (ΑΕΙ + ΤΕΙ) θέσεις του διαγωνισμού το 2005 έγιναν 120 φέτος θεωρούν ενδεδειγμένη αυτή την τακτική.
Όσον αφορά το 2003 τα θέματα του ΑΣΕΠ για ΠΕ19-ΠΕ20 ήταν πάρα πολύ πιο εύκολα. Ρίχνοντάς τους μια ματιά πριν από το φετινό διαγωνισμό έβαλα τα γέλια με μερικά ζητήματα, όπως στο "Ποιος από τους παρακάτω δεν είναι γνωστός επιστήμονας της Πληροφορικής", ή το "τι σημαίνει LAN" ή αν το WWW σημαίνει world wide web ή wide world wire...
Τουλάχιστον είχε πλέον κατοχυρωθεί να διορίζονται ως καθηγητές Πληροφορικής άνθρωποι με πτυχίο Πληροφορικής και όχι όποιοι είχαν σεμινάριο στο Office ...
Σημειώνω εδώ ότι έχω διαβάσει/μάθει ότι το 40% των καθηγητών Πληροφορικής στη Δευτεροβάθμια Εκπαίδευση δεν προέρχονται από σχολές Πληροφορικής, αλλά είναι Μαθηματικοί, Φυσικοί, Φιλόλογοι, Θεολόγοι, Κομμωτικής και ό,τι μπορεί να κατεβάσει ο νους σας...
Και ρωτάω δεν μπορεί το ΥΠΕΠΘ να μεριμνήσει γι αυτόν τον κλάδο; Δεν μπορεί να στείλει όλους αυτούς να διδάξουν μαθήματα πάνω στο γνωστικό τους αντικείμενο; Προφανώς και δεν πρόκειται να κάνει τίποτα το ΥΠΕΠΘ αφού δεν ασχολείται κανείς με εμάς...
Θα υπάρχουν σταδιακά όλο και λιγότερες θέσεις και σε τρεις διαγωνισμούς θα κυριαρχούν θέματα Ρομποτικής και Νευρωνικών Δικτύων για το διορισμό 10 πληροφορικάριων (όπως μας αποκαλούν στα σχολεία) για την 5ετία 2015 έως 2020...
Ας καθήσουμε λοιπόν να τσακωνόμαστε για την τάξη της πολυπλοκότητας της διοφαντικής εξίσωσης, περιμένοντας να μπει μια ώρα Πληροφορικής σε κάθε τάξη του Δημοτικού ώστε να δημιουργηθούν αυτόματα 2000 με 3000 θέσεις...

[thymiaras]

Είσαι πολύ λάθος και επιμένεις χωρίς λόγο. Μπορείς να μας δώσεις έναν αλγόριθμο σε οποιαδήποτε γλώσσα που να υπολογίζει το άθροισμα n όρων αριθμητικής προόδου, το οποίο είναι και ζητούμενο στην περιβόητη ερώτηση 17, με πολυπλοκότητα Ο(n); Εγώ προκαταβολικά θα σου πω ότι δεν υπάρχει για τον πολύ απλό λόγο ότι κάτι τέτοιο θα ίσχυε μόνο αν επρόκειτο για άθροισμα n ίδιων αριθμών (π.χ. c+c+...+c=c*n=O(n)). Εδώ όμως έχουμε διαφορετικούς αριθμούς και για να υπολογίσουμε το άθροισμά τους πρέπει να εφαρμόσουμε διπλή επανάληψη στον αλγόριθμο. Παραθέτω κι ένα παράδειγμα σε C που υπολογίζει το άθροισμα αυτό:

for (k=1; k <=n; k++) {
   for (j=1; j <= k; j++)
   sum=sum+j;
}

Η πολυπλοκότητά του είναι: n επαναλήψεις από το πρώτο for loop και n+1 προσθέσεις σε κάθε επανάληψη (n για τον υπολογισμό του όρου j που θα προστεθεί στο μερικό άθροισμα sum και 1 για τον υπολογισμό του νέου μερικού αθροίσματος. Οπότε συνολικά n*(n+1) πράξεις και άρα O(n²). Περιμένω τη δική σου υλοποίηση με πολυπλοκότητα O(n).

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

sum=0;
for(i=1;i<=n;i++)
     sum=sum + i;

Αυτό είναι όλο και όλο. Απλά κάποιοι δεν ξέρουν πραγματικά τι πάει να πει το Σ.
Υ.Γ. Περιμένω ακόμα διαφορετικό αλγόριθμο υπολογισμού του αθροίσματος (σωστό αυτή τη φορά)

[aroniotis]

Είσαι πολύ λάθος και επιμένεις χωρίς λόγο. Μπορείς να μας δώσεις έναν αλγόριθμο σε οποιαδήποτε γλώσσα που να υπολογίζει το άθροισμα n όρων αριθμητικής προόδου, το οποίο είναι και ζητούμενο στην περιβόητη ερώτηση 17, με πολυπλοκότητα Ο(n); Εγώ προκαταβολικά θα σου πω ότι δεν υπάρχει για τον πολύ απλό λόγο ότι κάτι τέτοιο θα ίσχυε μόνο αν επρόκειτο για άθροισμα n ίδιων αριθμών (π.χ. c+c+...+c=c*n=O(n)). Εδώ όμως έχουμε διαφορετικούς αριθμούς και για να υπολογίσουμε το άθροισμά τους πρέπει να εφαρμόσουμε διπλή επανάληψη στον αλγόριθμο. Παραθέτω κι ένα παράδειγμα σε C που υπολογίζει το άθροισμα αυτό:

for (k=1; k <=n; k++) {
   for (j=1; j <= k; j++)
   sum=sum+j;
}

Η πολυπλοκότητά του είναι: n επαναλήψεις από το πρώτο for loop και n+1 προσθέσεις σε κάθε επανάληψη (n για τον υπολογισμό του όρου j που θα προστεθεί στο μερικό άθροισμα sum και 1 για τον υπολογισμό του νέου μερικού αθροίσματος. Οπότε συνολικά n*(n+1) πράξεις και άρα O(n²). Περιμένω τη δική σου υλοποίηση με πολυπλοκότητα O(n).

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

sum=0;
for(i=1;i<=n;i++)
     sum=sum + i;

Αυτό είναι όλο και όλο. Απλά κάποιοι δεν ξέρουν πραγματικά τι πάει να πει το Σ.
Υ.Γ. Περιμένω ακόμα διαφορετικό αλγόριθμο υπολογισμού του αθροίσματος (σωστό αυτή τη φορά)

Δεν είπε ότι υπολογίζει το άθροισμα, αλλά ότι ο αλγόριθμος έχει πολυπλοκότητα όσο το άθροισμα. Καλά, δεν διαβάζεις τίποτα, απλά βιάζεσαι να απαντήσεις; thymiaras ειλικρινά, πες μου ότι είσαι κανένας φιλόλογος κι ότι έχεις μπει εδώ μέσα για να μας σπάσεις τα νεύρα...

[thymiaras]

Είσαι πολύ λάθος και επιμένεις χωρίς λόγο. Μπορείς να μας δώσεις έναν αλγόριθμο σε οποιαδήποτε γλώσσα που να υπολογίζει το άθροισμα n όρων αριθμητικής προόδου, το οποίο είναι και ζητούμενο στην περιβόητη ερώτηση 17, με πολυπλοκότητα Ο(n); Εγώ προκαταβολικά θα σου πω ότι δεν υπάρχει για τον πολύ απλό λόγο ότι κάτι τέτοιο θα ίσχυε μόνο αν επρόκειτο για άθροισμα n ίδιων αριθμών (π.χ. c+c+...+c=c*n=O(n)). Εδώ όμως έχουμε διαφορετικούς αριθμούς και για να υπολογίσουμε το άθροισμά τους πρέπει να εφαρμόσουμε διπλή επανάληψη στον αλγόριθμο. Παραθέτω κι ένα παράδειγμα σε C που υπολογίζει το άθροισμα αυτό:

for (k=1; k <=n; k++) {
   for (j=1; j <= k; j++)
   sum=sum+j;
}

Η πολυπλοκότητά του είναι: n επαναλήψεις από το πρώτο for loop και n+1 προσθέσεις σε κάθε επανάληψη (n για τον υπολογισμό του όρου j που θα προστεθεί στο μερικό άθροισμα sum και 1 για τον υπολογισμό του νέου μερικού αθροίσματος. Οπότε συνολικά n*(n+1) πράξεις και άρα O(n²). Περιμένω τη δική σου υλοποίηση με πολυπλοκότητα O(n).

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

sum=0;
for(i=1;i<=n;i++)
     sum=sum + i;

Αυτό είναι όλο και όλο. Απλά κάποιοι δεν ξέρουν πραγματικά τι πάει να πει το Σ.
Υ.Γ. Περιμένω ακόμα διαφορετικό αλγόριθμο υπολογισμού του αθροίσματος (σωστό αυτή τη φορά)

Δεν είπε ότι υπολογίζει το άθροισμα, αλλά ότι ο αλγόριθμος έχει πολυπλοκότητα όσο το άθροισμα. Καλά, δεν διαβάζεις τίποτα, απλά βιάζεσαι να απαντήσεις; thymiaras ειλικρινά, πες μου ότι είσαι κανένας φιλόλογος κι ότι έχεις μπει εδώ μέσα για να μας σπάσεις τα νεύρα...

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

Εδώ όμως έχουμε διαφορετικούς αριθμούς και για να υπολογίσουμε το άθροισμά τους πρέπει να εφαρμόσουμε διπλή επανάληψη στον αλγόριθμο. Παραθέτω κι ένα παράδειγμα σε C που υπολογίζει το άθροισμα αυτό:

Τις καληνύχτες μου παιδιά. Συνεχίζουμε το μάθημα αύριο με καινούρια πλούσια παραδείγματα