Ύλη 2015 2016

Ξεκίνησε από GB, 07 Ιουν 2015, 09:07:35 ΠΜ

« προηγούμενο - επόμενο »

Diotima

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

evry

Δεν είναι δυνατόν να μπει στις πανελλήνιες θέμα που να ζητάει έτσι αόριστα τον βέλτιστο αλγόριθμο για δυο λόγους κατά τη γνώμη μου.
1ον γιατί θα πρέπει να αποδείξεις ότι είναι ο βέλτιστος, άρα η πολυπλοκότητά του είναι κοντά στην πολυπλοκότητα του προβλήματος. Για παράδειγμα έχει αποδειχθεί ότι η ταξινόμηση δεν μπορεί να γίνει Καλύτερα από O(nlogn).
http://www.bowdoin.edu/~ltoma/teaching/cs231/fall07/Lectures/sortLB.pdf
2ον ζητώντας τον βέλτιστο αλγόριθμο γενικά και αόριστα μπορείς να πάρεις πολλές μη αναμενόμενες απαντήσεις κάτι το οποίο είναι καταστροφικό για την βαθμολόγηση των γραπτών και την ίση αντιμετώπιση των υποψηφίων.

Κατά τη γνώμη μου ο παρακάτω τύπος άσκησης θα μπορούσε να μπει (εφόσον ο συμβολισμός big-O είναι μέσα στην ύλη)
1) Να γράψετε αλγόριθμο αναζήτησης σε ταξινομημένο πίνακα με πολυπλοκότητα O(logn)
2) Τα στοιχεία ενός πίνακα Ν θέσεων μπορεί να είναι 1 ή 2 ή 3. Να σχεδιάσετε αλγορίθμο ταξινόμησης πολυπλοκότητας O(n)

Επίσης ένα ερώτημα που κατά τη γνώμη μου έχει ενδιαφέρον.
Πέφτει το θέμα:
Ο αλγόριθμος της γρήγορης ταξινόμησης (quicksort) έχει πολυπλοκότητα
α. O(nlogn)
β. O(n2)
γ. O(nn)
δ. O(en)
Ποια ή ποιες από τις παραπάνω συνιστούν σωστές απαντήσεις;

Το παραπάνω θέμα αναδεικνύει και ένα σοβαρό πρόβλημα του συμβολισμού Ο (big-O) ο οποίος δεν ενδείκνυται για πανελλήνιες εξετάσεις
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

petrosp13

Παράθεση από: evry στις 19 Ιουν 2015, 11:26:40 ΜΜ

Κατά τη γνώμη μου ο παρακάτω τύπος άσκησης θα μπορούσε να μπει (εφόσον ο συμβολισμός big-O είναι μέσα στην ύλη)
1) Να γράψετε αλγόριθμο αναζήτησης σε ταξινομημένο πίνακα με πολυπλοκότητα O(logn)
2) Τα στοιχεία ενός πίνακα Ν θέσεων μπορεί να είναι 1 ή 2 ή 3. Να σχεδιάσετε αλγορίθμο ταξινόμησης πολυπλοκότητας O(n)


Ευρυπίδη, για ποιους μαθητές μιλάμε;
...
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

evry

Για τους μαθητές που ξέρουν ότι η πολυπλοκότητα της δυαδικής αναζήτησης που είναι εντός ύλης είναι O(nlogn)
Όπως είπα και πριν αυτά που είπα ισχύουν εφόσον ο συμβολισμός Big-O είναι εντός ύλης, αλλιώς δεν έχει νόημα.

Πάντως το 2ο θέμα είναι ουσιαστικά το προπέρσινο θέμα Β με τις λογικές τιμές. Για όσους θυμούνται είναι ο αλγόριθμος ταξινόμησης που τελικά δεν ήταν... αλγόριθμος ταξινόμησης
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

petrosp13

Απλά θεωρώ ότι είναι too much το να ζητήσεις μέσα σε 3ωρη εξέταση από μαθητή την υλοποίηση αλγορίθμου με συγκεκριμένη πολυπλοκότητα
Μέχρι συγκεκριμένη πολυπλοκότητα να το καταλάβω, αλλά και πάλι πάμε μακριά
Πόσοι φοιτητές πληροφορικής μπορούν να ανταπεξέλθουν στο ερώτημα;
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

Νίκος Αδαμόπουλος

Παράθεση από: pgrontas στις 17 Ιουν 2015, 03:13:16 ΜΜ
Η πολυπλοκότητα αλγορίθμων θα διδαχθεί θεωρητικά με παραδείγματα και σε σύνδεση με την επίδοση χωρίς οι μαθητές να εμπλακούν σε ασκήσεις υπολογισμού της τάξης Ο ενός αλγορίθμου.

evry

Ακριβώς, για αυτό ανέφερα ότι αυτά παίζουν μόνο αν επιτραπεί ο συμβολισμός big-O , ο υπολογισμός της πολυπλοκότητας κλπ.
Το οποίο λογικά κάποια στιγμή θα γίνει γιατί δεν είναι δυνατόν η συγκεκριμένη παράγραφος να είναι μέσα μόνο θεωρητικά
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

ether

Παράθεση από: evry στις 19 Ιουν 2015, 11:26:40 ΜΜ
Επίσης ένα ερώτημα που κατά τη γνώμη μου έχει ενδιαφέρον.
Πέφτει το θέμα:
Ο αλγόριθμος της γρήγορης ταξινόμησης (quicksort) έχει πολυπλοκότητα
α. O(nlogn)
β. O(n2)
γ. O(nn)
δ. O(en)
Ποια ή ποιες από τις παραπάνω συνιστούν σωστές απαντήσεις;

Το παραπάνω θέμα αναδεικνύει και ένα σοβαρό πρόβλημα του συμβολισμού Ο (big-O) ο οποίος δεν ενδείκνυται για πανελλήνιες εξετάσεις
Αν ο αλγόριθμος είχε παρουσιαστεί και αναλυθεί σωστά στο βιβλίο, οπότε θα αναφερόταν και η πολυπλοκότητά του (χειρότερης (worst) και μέσης (average/expected) περίπτωσης) για τη συγκεκριμένη υλοποίηση και το ερώτημα είχε τεθεί σαφώς (δηλαδή διευκρίνιζε ότι αφορά στη συγκεκριμένη υλοποίηση που θα είχε παρουσιαστεί στο βιβλίο και ξεκαθάριζε ρητά αν ζητούσε πολυπλοκότητα χειρότερης ή μέσης περίπτωσης), τι πρόβλημα θα υπήρχε με το συμβολισμό big-O;

evry

Συνήθως όταν χρησιμοποιούμε τον συμβολισμό big-O χωρίς να διευκρινίζουμε τι είναι εννοούμε την πολυπλοκότητα χειρότερης περίπτωσης.
Το πρόβλημα με τον συμβολισμό big-O είναι ότι στο παράδειγμα που δίνω τα β, γ, δ είναι και τα τρία σωστά διότι όταν γράφουμε f(n)=O(g(n)) εννοούμε ότι η g(n) είναι ένα άνω όριο για την f(n) και όχι το ελάχιστο άνω όριο, δηλαδή το supremum του συνόλου. (Λέω σύνολο γιατί το = το χρησιμοποιούμε καταχρηστικά, κανονικά εκεί ήθελε το σύμβολο του ανήκει).

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

δες π.χ. πως στο επόμενο έγγραφο αποδεικνύει πως ένα πολυώνυμο δευτέρου βαθμού είναι O(n3)
http://www.math.uvic.ca/faculty/gmacgill/guide/big-O.pdf
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

ether

Παράθεση από: evry στις 20 Ιουν 2015, 03:26:12 ΜΜ
Συνήθως όταν χρησιμοποιούμε τον συμβολισμό big-O χωρίς να διευκρινίζουμε τι είναι εννοούμε την πολυπλοκότητα χειρότερης περίπτωσης.
Το πρόβλημα με τον συμβολισμό big-O είναι ότι στο παράδειγμα που δίνω τα β, γ, δ είναι και τα τρία σωστά διότι όταν γράφουμε f(n)=O(g(n)) εννοούμε ότι η g(n) είναι ένα άνω όριο για την f(n) και όχι το ελάχιστο άνω όριο, δηλαδή το supremum του συνόλου. (Λέω σύνολο γιατί το = το χρησιμοποιούμε καταχρηστικά, κανονικά εκεί ήθελε το σύμβολο του ανήκει).

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

δες π.χ. πως στο επόμενο έγγραφο αποδεικνύει πως ένα πολυώνυμο δευτέρου βαθμού είναι O(n3)
http://www.math.uvic.ca/faculty/gmacgill/guide/big-O.pdf
Στην περίπτωση πιθανοτικών αλγορίθμων, συνήθως ξεκαθαρίζουμε αν αναφερόμαστε σε worst case ή average/expected. Άρα, αν μιλάμε για πιθανοτική Quicksort, θα έπρεπε να ξεκαθαρίζει το ερώτημα για τι μιλάει.

Έχεις δίκιο σ' αυτό που λες, ότι ισχύουν και τα τρία β, γ, δ (θα μπορούσε να ισχύει και το α, για expected κάποιας πιθανοτικής ή για worst κάποιας συγκεκριμένης ντετερμινιστικής υλοποίησης της Quicksort), αφού ο συμβολισμός big-O αφορά σε άνω φράγμα και όχι σε ελάχιστο άνω φράγμα. Ουσιαστικά το ερώτημα τσεκάρει και τη γνώση για την πολυπλοκότητα της Quicksort και την κατανόηση του συμβολισμού big-O.

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

Εξαρτάται λοιπόν τι θέλει κανείς να ελέγξει με το ερώτημα.

AEPP2106

Καλησπέρα σε όλους!
Επειδή αύριο ξεκινούν τα φροντιστήρια για πολλούς από εμάς, μπορείτε να προτείνετε έναν "μπούσουλα" σχετικά με την ύλη που πρέπει να ακολουθηθεί; Ας πούμε πόσο χρόνο να αφιερώσουμε σε αλγορίθμους; κλπ. κλπ. Και με αυτό το 5ο κεφάλαιο τι πρέπει να γίνει????? Οι παράγραφοι 5.3.1 και 5.3.2 είναι εντός ύλης??
Ευχαριστώ :)

ako

Καλησπέρα. Ένας μπούσουλας που κατέληξα για τον τρόπο που θα διδάξω την ύλη (τουλάχιστον στην αρχή) για το φροντιστήριο: ξεκινώ κανονικά με δομή ακολουθίας κάνοντας ένα-δυο παραδείγματα αλγορίθμων (ίσως και 2-3 ασκήσεις) μόνο και μόνο για και για να μπορέσω να πω την αντίστοιχη θεωρία του 2ου κεφαλαίου (αλγόριθμοι  και δομή ακολουθίας μόνο).  Επίσης θα κάνω και ένα διάγραμμα ροής και τέλος. Στην συνέχεια θα το γυρίσω σε ΓΛΩΣΣΑ και θα συνεχίσω με την θεωρία του 7ου κεφαλαίου. Από ασκήσεις εξαιρώντας τις 2-3 παραπάνω  που σκοπεύω να τις ζητήσω σε αλγόριθμο (μη δίνοντας και μεγάλη σημασία σε λάθη) ΟΛΕΣ οι υπόλοιπες θα πάνε με πρόγραμμα.

Κάτι άλλο: νομίζω ότι το μάθημα θέλει πια 3 ώρες στο φροντιστήριο και πιθανώς περισσότερες στο σχολείο (αφού εκεί τα τμήματα έχουν πολύ περισσότερους μαθητές):
(α) είναι πια πολύ χαμηλό το επίπεδο των μαθητών (σε σχέση με πέρυσι) και πρέπει να κάνουμε περισσότερες ασκήσεις σε κάθε ενότητα ώστε να μπορούν να εξοικειωθούν,
(β) βγάλανε μια θεωρία ανύπαρκτη (1ο)  και μπήκε το 5ο που θες περισσότερο χρόνο να εξηγήσεις γράφοντας και παραδείγματα στον πίνακα
(γ) ήδη ήμασταν μέχρι φέτος  στο όριο με την ύλη: αφού αυτά που πριν από 5-10 χρόνια διδάσκονταν «επιφανειακά», τον τελευταίο καιρό ήμασταν αναγκασμένοι με τα θέματα που έμπαιναν να εμβαθύνουμε και να τρώμε απίστευτα πολλές εργατοώρες  μην τύχει και μπει το άπιαστο  θέμα και δεν το έχουμε διδάξει.  Πόσο μάλλον τώρα που μπαίνει αναζήτηση,  ταξινόμηση, ουρές και στοίβες.
(δ) για κάθε άσκηση που λύνουμε στον πίνακα θέλουμε και κάποιο χρόνο να γράφουμε (και κυρίως να εξηγούμε) τις μεταβλητές.

Δημήτρης Αρ.

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

tsak

Παράθεση από: ako στις 21 Ιουν 2015, 08:05:58 ΜΜ
Καλησπέρα. Ένας μπούσουλας που κατέληξα για τον τρόπο που θα διδάξω την ύλη (τουλάχιστον στην αρχή) για το φροντιστήριο: ξεκινώ κανονικά με δομή ακολουθίας κάνοντας ένα-δυο παραδείγματα αλγορίθμων (ίσως και 2-3 ασκήσεις) μόνο και μόνο για και για να μπορέσω να πω την αντίστοιχη θεωρία του 2ου κεφαλαίου (αλγόριθμοι  και δομή ακολουθίας μόνο).  Επίσης θα κάνω και ένα διάγραμμα ροής και τέλος. Στην συνέχεια θα το γυρίσω σε ΓΛΩΣΣΑ και θα συνεχίσω με την θεωρία του 7ου κεφαλαίου. Από ασκήσεις εξαιρώντας τις 2-3 παραπάνω  που σκοπεύω να τις ζητήσω σε αλγόριθμο (μη δίνοντας και μεγάλη σημασία σε λάθη) ΟΛΕΣ οι υπόλοιπες θα πάνε με πρόγραμμα.

Κάτι άλλο: νομίζω ότι το μάθημα θέλει πια 3 ώρες στο φροντιστήριο και πιθανώς περισσότερες στο σχολείο (αφού εκεί τα τμήματα έχουν πολύ περισσότερους μαθητές):
(α) είναι πια πολύ χαμηλό το επίπεδο των μαθητών (σε σχέση με πέρυσι) και πρέπει να κάνουμε περισσότερες ασκήσεις σε κάθε ενότητα ώστε να μπορούν να εξοικειωθούν,
(β) βγάλανε μια θεωρία ανύπαρκτη (1ο)  και μπήκε το 5ο που θες περισσότερο χρόνο να εξηγήσεις γράφοντας και παραδείγματα στον πίνακα
(γ) ήδη ήμασταν μέχρι φέτος  στο όριο με την ύλη: αφού αυτά που πριν από 5-10 χρόνια διδάσκονταν «επιφανειακά», τον τελευταίο καιρό ήμασταν αναγκασμένοι με τα θέματα που έμπαιναν να εμβαθύνουμε και να τρώμε απίστευτα πολλές εργατοώρες  μην τύχει και μπει το άπιαστο  θέμα και δεν το έχουμε διδάξει.  Πόσο μάλλον τώρα που μπαίνει αναζήτηση,  ταξινόμηση, ουρές και στοίβες.
(δ) για κάθε άσκηση που λύνουμε στον πίνακα θέλουμε και κάποιο χρόνο να γράφουμε (και κυρίως να εξηγούμε) τις μεταβλητές.


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

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

petrosp13

Παράθεση από: tsak στις 21 Ιουν 2015, 09:55:35 ΜΜ
Αύριο όμως  πολλοί ξεκινάμε και κάποιοι θέλουν να δώσουν ολοκληρωμένα τις σημειώσεις τους (όπως κι εγώ). Αλλά φέτος πρέπει να γίνουν αρκετές άλλες αναθεωρήσεις στο υλικό που θα δώσουμε και επειδή θα προκύψουν φαντάζομαι διευκρινίσεις στην πορεία από το Υπουργείο, σκέφτηκα ότι μια λύση είναι τα καινούρια κομμάτια της ύλης να τα καλύψω στο τέλος και αφού έχω ολοκληρώσει αυτά που έκανα κάθε χρόνο. Απλά θα δώσω στο τελειώματα της ύλης (αν δεν προλάβω μέχρι Αύγουστο) ένα συμπληρωματικό φυλλάδιο με ασκήσεις και σχόλια στα καινούρια της ύλης.

Ή μπορείς να δώσεις τα πρώτα κομμάτια της ύλης που είναι βέβαια και να δώσεις ολόκληρο το πακέτο των σημειώσεων τον Αύγουστο, οπότε ΕΛΠΙΖΟΥΜΕ ότι θα έχουν δοθεί κάποιες παραπάνω διευκρινίσεις (αλγόριθμοι αναζήτησης-ταξινόμησης, ασκήσεις ουράς-στοίβας, πολυπλοκότητα)
Αν αυτό δεν γίνει μέχρι τον Αύγουστο, τότε θα έχουμε πραγματικά πρόβλημα με τις σημειώσεις
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής