Θεμα Γ χρηση πινακων απολυτα σωστη !!!

Ξεκίνησε από Mathitis14, 08 Ιουν 2014, 12:48:46 ΜΜ

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

Αθανάσιος Πέρδος

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

Παράθεση από: evry
link=topic=5804.msg65837#msg65837 date=1402419642

ναι βρε Νάσο, αυτή ήταν η πρώτη λύση με πολυπλοκότητα Ο(n), αυτό λέω
όλοι όσοι πήραν πίνακες, επέλεξαν αυτό τον δρόμο για να κάνουν ταξινόμηση, άρα O(n^2)
Αυτοί που έκαναν την έξυπνη σκέψη που λες δεν χρειάστηκε να πάρουν πίνακες.



itt

Παράθεση από: evry στις 10 Ιουν 2014, 04:37:16 ΜΜ
Τι εννοείς?
η λύση με πίνακες είχε πολυπλοκότητα Ο(n^2) ενώ χωρίς πίνακες είχε Ο(n).
Χρησιμοποιείς σε τέτοιες περιπτώσεις πίνακα όταν έχεις καλύτερη πολυπλοκότητα όχι για να τα κάνεις χειρότερα.

Υπάρχει και το overhead του ΙΟ ( στην πραγματική ζωή τουλάχιστον).


Παράθεση από: evry στις 10 Ιουν 2014, 04:37:16 ΜΜ
εγώ είπα ότι η ψευδογλώσσα του βιβλίου δεν είναι η γνωστή, ψευδογλώσσα. Εσύ πως έβγαλες το παρακάτω συμπέρασμα, από αυτό?Εννοούσα ότι είναι μια ψευδογλώσσα κοντά στην ΓΛΩΣΣΑ αφού έχει περιορισμούς, π.χ. δεν μπορείς να πειράξεις το μετρητή του Για. Αυτό είναι δυνατόν να συμβαίνει σε ψευδογλώσσα? επίσης όπως έχω πει άπειρες φορές στην ψευδογλώσσα του σχολικού οι δυναμικοί πίνακες είναι εκτός ύλης, τι να κάνουμε τώρα.
Αυτό που λέω λοιπόν είναι ότι η ψευδογλώσσα του βιβλίου είναι ουσιαστικά μια ΓΛΩΣΣΑ με πιο χαλαρή σύνταξη στην οποία δεν έχουμε δήλωση μεταβλητών.

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

Παράθεση από: evry στις 10 Ιουν 2014, 04:37:16 ΜΜ
Επίσης αυτό που λες με το Interface δε συμφωνώ καθόλου. Όταν χρησιμοποιείς ένα interface αυτό έχει καποια specifications. Αν ανάλογα με την υλοποίηση αλλάζουν τα specifications (γεμίζει ο πίνακας και κρεμάει) τότε κάτι δεν πάει καλά.

Δεν αλλάζει κανένα specification. Θα το πω πολύ απλά. Άμα έχεις μια συνάρτηση/μέθοδο που για ένα index τύπου T σου επιστρέφει το περιεχόμενο σε αυτή τη θέση (έστω τύπου U),  τότε για τον δυναμικό όταν θα κάνεις access θέση μεγαλύτερη από το μέγεθος του πίνακα μπορεί να σου επιστρέχει την default τιμή για έναν τύπο U, ενώ ο στατικός θα σου επιστρέψει το bottom για το type system σου.
Στην Java πχ, θα ρίξεις ένα exception. Οπότε κανένα invariant του spefication του interface σου δεν παραβιάζεται.

ολγα

Παράθεση από: evry στις 10 Ιουν 2014, 04:50:55 ΜΜ


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


Συμφωνώ! Από εκεί ξεκινάει το πρόβλημα. Κάποιοι δεν ξέρουν τι θα πει θεωρητική πληροφορική, ασχολούνται με "υλοποιήσεις" και διυλυζουμε τον κώνωπα τόσα χρόνια.
Οι αγορές μου θεωρητικά θα μπορούσαν να ξεπεράσουν τα όρια της μνήμης της μηχανής, όμως ο αλγόριθμος πρέπει να δουλεύει και σε αυτή την περίπτωση. Μήπως εκεί θα αποτύγχαναν τόσο οι στατικοί όσο και οι δυναμικοί πίνακες; Δεν υπάρχει λύση με πίνακες για αυτλο το θέμα.
Όσο για την αναζήτηση με ΓΙΑ εξηγήστε μου γιατί δεν καταλαβαίνω! Μια αναζήτηση διδάσκουμε: τη σειριακή (που όσοι πήγαμε πανεπιστήμιο τη μάθαμε με ΟΣΟ-εμένα έτσι μου τη μάθανε πολλά χρόνια πριν). Δε μπορούμε έτσι να τη διδάξουμε και στους μαθητές μας;
Γιατί να αφήνουμε περιθώρια για ελευθερίες του στυλ αφού δουλεύει και με ΓΙΑ ας το δεχτούμε! ΔΕΝ ΕΙΝΑΙ ΑΥΤΟ ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ.
Μια αναζήτηση μαθαίνουν τα παιδιά. Ας τη μάθουν όπως πρέπει.

... και συγνώμη για το ύφος.

petrosp13

Να προσθέσω ότι αν όλες οι ασκήσεις μπορούν να λυθούν με πίνακες, τότε μπορούν να λυθούν και με Για, "σπάζοντας" την επανάληψη
Νομίζω ότι σε αυτό έχουμε συμφωνήσει ότι απαγορεύεται
Σωστά;
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

Άρης Κεσογλίδης

Παράθεση από: petrosp13 στις 12 Ιουν 2014, 10:30:43 ΜΜ
Να προσθέσω ότι αν όλες οι ασκήσεις μπορούν να λυθούν με πίνακες, τότε μπορούν να λυθούν και με Για, "σπάζοντας" την επανάληψη
Νομίζω ότι σε αυτό έχουμε συμφωνήσει ότι απαγορεύεται
Σωστά;
Σε αυτό συμφωνήσαμε, επειδή στο Τετράδιο του μαθητή στη σελ. 78 λέει:

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

...όπως επίσης και βασιζόμενοι σε ανάλογη οδηγία του Παιδαγωγικού Ινστιτούτου.

Παράθεση από: ολγα στις 12 Ιουν 2014, 10:25:58 ΜΜ
Όσο για την αναζήτηση με ΓΙΑ εξηγήστε μου γιατί δεν καταλαβαίνω! Μια αναζήτηση διδάσκουμε: τη σειριακή (που όσοι πήγαμε πανεπιστήμιο τη μάθαμε με ΟΣΟ-εμένα έτσι μου τη μάθανε πολλά χρόνια πριν). Δε μπορούμε έτσι να τη διδάξουμε και στους μαθητές μας;
Γιατί να αφήνουμε περιθώρια για ελευθερίες του στυλ αφού δουλεύει και με ΓΙΑ ας το δεχτούμε! ΔΕΝ ΕΙΝΑΙ ΑΥΤΟ ΣΕΙΡΙΑΚΗ ΑΝΑΖΗΤΗΣΗ.
Μια αναζήτηση μαθαίνουν τα παιδιά. Ας τη μάθουν όπως πρέπει.
"Σειριακή" λέγεται η αναζήτηση όχι επειδή είναι με ΟΣΟ, αλλά επειδή προσπελαύνει τα στοιχεία σειριακά, ή ακολουθιακά, δηλαδή με τη σειρά ένα-ένα. Και με ΓΙΑ να γίνει, αφού τα ψάχνει με τη σειρά, είναι ΣΕΙΡΙΑΚΗ αναζήτηση, απλά δεν σταματάει αμέσως.

Να δοθεί μια οδηγία και για εδώ και να λέει ότι όποτε κι αν χρειαστεί να γίνει αναζήτηση, να σταματάει αμέσως μόλις βρεθεί το ζητούμενο στοιχείο, ή να αληθεύει η συνθήκη που θέλουμε (είτε με ΟΣΟ, είτε με ΜΕΧΡΙΣ_ΟΤΟΥ).
Άρης Κεσογλίδης
Μαθηματικός
Μεταπτυχιακό στη "Θεωρητική Πληροφορική και Θεωρία Συστημάτων και Ελέγχου"

evry

Παράθεση από: Άρης Κεσογλίδης στις 12 Ιουν 2014, 11:07:08 ΜΜ
Σε αυτό συμφωνήσαμε, επειδή στο Τετράδιο του μαθητή στη σελ. 78 λέει:

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

Κώδικας: Pascal
i<-1
Όσο i<=10 Επανάλαβε
    Διάβασε όνομα
    Αν όνομα = "ΤΕΛΟΣ" 
            Τότε i <- 666
   αλλιώς 
           ι <- ι + 1
Τέλος_Επανάληψης


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

What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

ολγα

#81
Η σειριακή αναζήτηση σταματάει όταν βρεθεί το στοιχείο. Αν συνεχίζει να ψάχνει ενώ έχει βρεθεί, τότε αυτό δεν είναι σειριακή αναζήτηση. Είναι κάτι άλλο, αλλά όχι σειριακή αναζήτηση. Έτσι περιγράφεται στο βιβλίο της ΑΕΠΠ αλλά και σε οποιοδήποτε βιβλίο αλγορίθμων. Όπως και εδώ:

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

For each item in the list:
     if that item has the desired value,
         stop the search and return the item's location.
Return Λ.

Όπως πρέπει να το διδάσκονται και οι μαθητές μας.

Άρης Κεσογλίδης

@ Evry
Παραλογισμοί υπάρχουν δεκάδες στο σχολικό βιβλίο... :)

Παράθεση από: ολγα στις 13 Ιουν 2014, 12:19:15 ΠΜ
Η σειριακή αναζήτηση σταματάει όταν βρεθεί το στοιχείο. Αν συνεχίζει να ψάχνει ενώ έχει βρεθεί, τότε αυτό δεν είναι σειριακή αναζήτηση. Είναι κάτι άλλο, αλλά όχι σειριακή αναζήτηση.

Όλγα, σύμφωνα με αυτά που λες, και η "έξυπνη φυσαλίδα" δεν είναι φυσαλίδα, διότι η μία κάνει ν-1 σειρές συγκρίσεων, ενώ η άλλη μπορεί να σταματήσει πιο νωρίς... ( ; )  ???

Σειριακή αναζήτηση λέγεται επειδή ψάχνει με τη σειρά τα στοιχεία ένα-ένα. Απλά έχει επικρατήσει με τον όρο "σειριακή αναζήτηση" να εννοούμε αυτή που σταματάει γιατί είναι πιο αποδοτική.

Δεν ξέρω αν διαφωνεί και κανένας άλλος από τόσους συναδέλφους, ειδικά στο θέμα που έχει τεθεί, με τίτλο:
"Σειριακή Αναζήτηση με τη δομή Για...από...μέχρι"
https://alkisg.mysch.gr/steki/index.php?topic=1702.0

Ίσως θα έπρεπε να λέμε την αναζήτηση που σταματάει "έξυπνη σειριακή αναζήτηση".  :)
Άρης Κεσογλίδης
Μαθηματικός
Μεταπτυχιακό στη "Θεωρητική Πληροφορική και Θεωρία Συστημάτων και Ελέγχου"