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

[aroniotis]

Να πω και γω την άποψη μου για τις απαντήσεις. Η 17 τελικά δεν ήταν θέμα για πληροφορικούς αλλά για μαθηματικούς. Μπέρδεψε και τους πιο σχετικούς με το "άθλημα" αφού οι πληροφορικοί έχουμε μάθει να ταυτίζουμε την έννοια του Ο, Θ , Ω κτλ με πολυπλοκότητα. Τελικά η άσκηση δεν ζητούσε πολυπλοκότητα αλλά ζητούσε να ασχοληθούμε με συναρτήσεις "στεγνές". Πως δε μας βάλανε και κάνα ολοκλήρωμα έτσι για το γαμώτο (καλύτερα να μας βάζανε, τουλάχιστον τότε θα ξέραμε τι ζητούσε η ερώτηση)

Ας πούμε ότι την βάζουμε στην άκρη την 17. Εμένα οι ενστάσεις μου είναι στην 32 και στην 54.

Στην 32 σωστή απάντηση είναι η β. Το λόγο τον έχω αναφέρει αλλά ας τον ξαναπώ. Η ερώτηση λέει ότι μας ενδιαφέρει η σειρά εκτέλεσης των διεργασιών ("εξαρτάται από τη σειρά εκτέλεσης τους"). Όταν έχουμε race conditions ΔΕΝ ξέρουμε με ποια σειρά θα εκτελεστούν οι διεργασίες, κοινώς η κατάσταση είναι όποιος προλάβει. Ενώ όταν έχουμε συγχρονισμό μπορούμε να καθορίσουμε εμείς ποια διεργασία θα εκτελεστεί πρώτη, ποια δεύτερη κτλ.

Στην 54 έχουμε πάλι αναφερθεί σε αυτό το φόρουμ. Τα αρχεία php είναι cgi scripts (τουλάχιστον μπορούν να χρησιμοποιηθούν ως cgi scripts, στο συγκεκριμένο παράδειγμα ΣΙΓΟΥΡΑ είναι cgi scripts). Οπότε γιατί είναι το β? Επειδή λέει στο συγκεκριμένο κώδικα HTML? Μα και γω για το συγκεκριμένο κώδικα μιλάω. Εγώ επιμένω στο γ πάντως. Ακούω τις απόψεις σας.

Όποιος έχει ενστάσεις ξέρει τι να κάνει: http://www.alfavita.gr/anakoinoseis/ank12_2_9_112.php

[PDE ads]

[thymiaras]

θυμιάρα:-)αν δεν δεις το όνομά σου γραμμένο σε ένσταση να μή σε ξαναπούν Θυμιάρα:-!

Με τρώει το δίκιο μου φίλε GOODmorning !!! Μήπως να στείλω κανά fax στον ΑΣΕΠ ? Εσείς τι απαντήσατε στις συγκεκριμένες ερωτήσεις ?

[GOODmorning]

:-)Εγώ πάντως θα σε συμπεριλάβω στην ένστασή μου:-))

[GOODmorning]

Γνωρίζετε συνονόματοι και μή, πότε τελειώνει η περίοδος των ενστάσεων;

[PDE ads]

[nastytweety]

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

Εσεις που λετε οτι ειναι αυτο το θεμα εντος υλης θα διαμαρτυρηθειτε αραγε στον επομενο ΑΣΕΠ που θα σας βαλουν διαφορικες εξισωσεις και τριπλα ολοκληρωματα?Οσο οι διαφορικες εξισωσεις ειναι εντος υλης αλλο τοσο ειναι και αυτο το θεμα.Παντως οπως ειπα βλεπω πολλες ενστασεις πανω στην ερωτηση και οσο πιο πολλες γινουν τοσο πιο καλα για μας.....

[thymiaras]

:-)Εγώ πάντως θα σε συμπεριλάβω στην ένστασή μου:-))

Αν σκοπεύεις πραγματικά να στείλεις ένσταση στείλε pm να ετοιμάσουμε μαζί την υπερασπιστική μας γραμμή !!!

[GOODmorning]

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

[si@]

Παιδιά έχω φάει άνα κόλλημα σε σχέση με μια ερώτηση

8.
Έστω ότι έχετε τρεις διαφορετικούς αλγορίθμους, Α, Β και Γ, που επιλύουν το ίδιο πρόβλημα. Η πολυπλοκότητα του Α είναι O(n^6), του Β είναι Ο(2^n) και του Γ είναι O(n!). Ποιον από τους τρεις θα προτιμούσατε;
α) Τον Α.
β) Τον Β.
γ) Τον Γ.
δ) Οποιονδήποτε από τους Β ή Γ, δεν έχουν διαφορά.

Η σωστή κατά ΑΣΕΠ είναι η α. Είναι σωστό αυτό ή εγώ είμαι άσχετη;

[skarag1]

Παιδιά έχω φάει άνα κόλλημα σε σχέση με μια ερώτηση

8.
Έστω ότι έχετε τρεις διαφορετικούς αλγορίθμους, Α, Β και Γ, που επιλύουν το ίδιο πρόβλημα. Η πολυπλοκότητα του Α είναι O(n^6), του Β είναι Ο(2^n) και του Γ είναι O(n!). Ποιον από τους τρεις θα προτιμούσατε;
α) Τον Α.
β) Τον Β.
γ) Τον Γ.
δ) Οποιονδήποτε από τους Β ή Γ, δεν έχουν διαφορά.

Η σωστή κατά ΑΣΕΠ είναι η α. Είναι σωστό αυτό ή εγώ είμαι άσχετη;

Σωστό το ΑΣΕΠ. Πάντα θα εξετάζεις για πολύ μεγάλο n.

[si@]

OK ας μου δώσει καποιος μια εξήγηση τουλάχιστον να καταλάβω...

[nobody]

OK ας μου δώσει καποιος μια εξήγηση τουλάχιστον να καταλάβω...

Βάλε όπου n 100 και θα καταλάβεις.

[aroniotis]

OK ας μου δώσει καποιος μια εξήγηση τουλάχιστον να καταλάβω...

Αν διάβαζες τις απαντήσεις που είχα δώσει θα καταλαβαινες. Άντε, ας το ξαναπω. Αν βάλεις n=1.000.000 μπορείς να δεις αμέσως πιο είναι μεγαλύτερο. Για να μην κάθεσαι να το ψάχνεις, σου λέω εγώ οτι το n^6 είναι 10^36 δηλαδή ένας αριθμός με 36 ψηφία (μεγάλος). Αν κάνεις το 2^n θα δεις έναν αριθμό με χιλιάδες ψηφία (το έκανα για περιέργεια στο Mathematica και ήταν μια σελίδα ψηφία). Αμέσως φαίνεται ότι το 2^n είναι τεράστιο για μεγάλα n.

Βέβαια και με απλή λογική βγαίνει, αφού το ένα είναι εκθετικό

[si@]

Kαλά το εκθετικό δε με νοιάζει. Εντάξει ευχαριστώ ρε παιδιά! Είχα φάει κόλλημα χοντρό! Πω πω ρεζίλι...Απάντησα σωστά άλλα κι άλλα κι αυτό...Τεσπα δεν πειράζει. Ευχαριστώ!

[rory]

Δεν κατάλαβα γιατί δεν το περίμενες? Αφού χωρίζεις τα n σε k ομάδες , άρα κάθε ομάδα έχει n/k και επειδή η συνάρτηση hash σε ρίχνει σε μια τέτοια ομάδα τότε αρκεί να ψάξεις μόνο τα στοιχεία της ομάδας. Αυτό δεν είναι το σκεπτικό ή κάνω λάθος?

Αυτό που δεν περίμενα από το ΑΣΕΠ (κρίνοντας το από κραυγαλέα λάθη του παρελθόντος) ήταν η απάντηση γ που έδωσε - πολύ σωστά - στην ερώτηση 41.

Στο hashing μπορεί μια κακή είσοδος να δώσει και τα n στοιχεία στην ίδια θέση του πίνακα κατακερματισμού. Σε αυτή την περίπτωση η πολυπλοκότητα είναι O(n). Εδώ είναι, θεωρώ, κάπως ελλιπής η εκφώνηση αν και ζητάει την απλοϊκή απάντηση O(n/k) όπως φαίνεται από τις απαντήσεις του ΑΣΕΠ.

Η 17 γνώμη μου είναι δεν έπρεπε να σας μπερδέψει τόσο. Είναι νομίζω τραβηγμένο να θεωρήσει κανείς ότι ζητείται η πολυπλοκότητα του αλγορίθμου αθροίσματος. Τα αριστερά μέλη αποτελούν συναρτήσεις πολυπλοκότητας με βάση το n, όπως σε όλα τα βιβλία αλγορίθμων. Έπρεπε μεν το ΑΣΕΠ να διατυπώσει το θέμα ως "θεωρήστε το αριστερό μέλος ως συνάρτηση πολυπλοκότητας του n" αλλά ενας αλγόριθμος δεν ισούται με κάτι, ενώ μια συνάρτηση πολυπλοκότητας "ισούται" με έναν ασυμπτωτικό συμβολισμό.

Στο 40 να σχολιάσω μια απορία κ συγγνώμη αν έχει ξανασχολιαστεί. Το δυαδικό ισοζυγισμένο δέντρο υλοποιεί όλες τις πράξεις σε χρόνο   Ο(logn). H ταξινομημένη λίστα παρότι είναι ταξινομημένη δεν μπορεί να υποστηρίξει καμία πράξη σε λιγότερο του O(n) γιατί δεν μπορεί να πραγματοποιηθεί αποδοτικά η αναζήτηση στοιχείου. Κάθε πράξη προσθήκης ή διαγραφής απαιτεί την αναζήτηση της κατάλληλης θέσης στην οποία θα γίνει η προσθήκη/διαγραφή το οποίο στη λίστα γίνεται από τα άκρα της και στοιχείο-στοιχείο.

Καλά αποτελέσματα!