Καλησπέρα,
Θα ήθελα τη γνώμη σας για μια προσέγγιση που αφορά στη μετατροπή από Όσο σε Αρχή_επανάληψης και το αντίθετο. Θα ήταν λάθος να δώσουμε την εξής μετατροπή σαν γενική μέθοδο; Μπορεί να έχει ξαναπαρουσιαστεί αλλά δεν το έχω παρακολουθήσει.
Από Αρχή_επανάληψης σε Όσο (για γνωστό αριθμό επαναλήψεων αρχικοποίηση με μετρητή).
μτ<-ατ
Αρχή_επανάληψης
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Μέχρις_ότου <μτ τελεστής ττιμή>
μτ<-ατ
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Όσο ΟΧΙ <μτ τελεστής ττιμή> επανάλαβε
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Τέλος_επανάληψης
Από Όσο σε Αρχή_επανάληψης (για γνωστό αριθμό επαναλήψεων αρχικοποίηση με μετρητή).
μτ<-ατ
Όσο <μτ τελεστής ττιμή> επανάλαβε
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Τέλος_επανάληψης
μτ<-ατ
Αρχή_επανάληψης
Αν <μτ τελεστής ττιμή>
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Τέλος_αν
Μέχρις_ότου ΟΧΙ<μτ τελεστής ττιμή>
Ευχαριστώ,
Ελένη
Στο τελευταίο, εγώ την Αν θα την έβγαζα απ' έξω, για να μην επιβαρύνεται η επανάληψη:
μτ<-ατ
Αν <μτ τελεστής ττιμή> τότε
Αρχή_επανάληψης
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Μέχρις_ότου ΟΧΙ<μτ τελεστής ττιμή>
Τέλος_αν
Κατά τα άλλα καλό μου φαίνεται.
μπράβο Ελένη
μένουν 2 κατηορίες:
1. για <-> όσο
2. για <-> μέχρις_ότου
Υ.Γ. μπορείς να το εκφράσεις γενικά με οποιαδήποτε συνθήκη, χωρίς να στηρίζεσαι σε μετρητή ή συγκεκριμένο αριθμό επαναλήψεων:
Εντολές_1
Όσο Συνθήκη_1 επανάλαβε
Εντολές_2
Τέλος_επανάληψης
Χμμμμμ το θέμα αυτό με είχε απασχολήσει πολύ στο παρελθόν. Είχα αναπτύξει μια μέθοδο που παρέχει απόδειξη για όλες τις πιθανές μετατροπές (και όχι απλή μετατροπή). Η ίδια μέθοδος φωτογραφίζει αν μια άσκηση λύνεται καλύτερα με Όσο ή με Μέχρις_ότου και με αυτή κάνω την επιλογή.
Αν θυμάμαι καλά (δεν είμαι σίγουρος που είχα καταλήξει τότε) νομίζω ότι η Όσο με τελεστή < ή > και η μέχρις_ότου με τελεστή =< ή >= δεν μετατρέπεται πάντα σε Για ενώ τα άλλα γίνονται (ακόμα και η μεχρις_ότου με μετρητή στη μέση σε Για) . Εννοείται πως μιλάμε για Όσο και Μέχρις_ότου με συνθήκη πάνω στο μετρητή.
Είναι μια συζήτηση που πρέπει να την κάνουμε κάποια στιγμή για να δούμε και τι ακριβώς εννούμε όταν ζητάμε ισοδύναμο αλγόριθμο.
Θέλω να βρω λίγο χρόνο να τα γράψω γιατί είναι αρκετά. :-\
Ας ορίσουμε πρώτα τη ΓΙΑ και μετά πάμε και σε ισοδυναμίες! >:D
Π.χ.
ΓΙΑ α ΑΠΟ 1 ΜΕΧΡΙ α+1
ΓΡΑΨΕ α
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Σταματάει αυτό ποτέ στη ΓΛΩΣΣΑ; Γιατί σε Pascal και Basic σταματάει μια χαρά, τα άκρα και το βήμα αποτιμούνται μόνο μία φορά... Κι αν πούμε ότι όντως συμβαίνει αυτό και στη ΓΛΩΣΣΑ, τότε καλύτερα να ξεχάσουμε τις μετατροπές από ΓΙΑ σε ΟΣΟ ή ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ, είναι υπερβολικά εξεζητημένες.
https://alkisg.mysch.gr/steki/index.php?topic=1118.msg7185#msg7185
Με τις ισοδυναμίες συμφωνώ και εγώ ότι υπάρχουν μερικά μικροπροβληματάκια στον ορισμό. Ωστόσο στις γλώσσες C, C++, Java όπου η ΓΙΑ έχει τη μορφή
for (i=1; i<=10; i=i+1) { ...... }
έχουμε πλήρη ισοδυναμία μεταξύ ΓΙΑ και ΟΣΟ, δεν είναι αυτός ο τρόπος καλύτερος; δηλαδή δεν θα μπορούσαμε να είχαμε στη ΓΛΩΣΣΑ κάτι στο στυλ;
ΕΠΑΝΑΛΑΒΕ ΓΙΑ (i=1; i<=10; i=i+1) { ...... }
Παράθεση από: alkisg στις 23 Νοε 2007, 11:51:27 ΜΜ
Ας ορίσουμε πρώτα τη ΓΙΑ και μετά πάμε και σε ισοδυναμίες! >:D
Π.χ.
ΓΙΑ α ΑΠΟ 1 ΜΕΧΡΙ α+1
ΓΡΑΨΕ α
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Σταματάει αυτό ποτέ στη ΓΛΩΣΣΑ; Γιατί σε Pascal και Basic σταματάει μια χαρά, τα άκρα και το βήμα αποτιμούνται μόνο μία φορά... Κι αν πούμε ότι όντως συμβαίνει αυτό και στη ΓΛΩΣΣΑ, τότε καλύτερα να ξεχάσουμε τις μετατροπές από ΓΙΑ σε ΟΣΟ ή ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ, είναι υπερβολικά εξεζητημένες.
https://alkisg.mysch.gr/steki/index.php?topic=1118.msg7185#msg7185
ΕΛΠΙΖΩ ΝΑ ΚΑΛΥΠΤΕΙ ΤΙΣ ΜΕΤΑΤΡΟΠΕΣ ΤΗΣ ΓΙΑ ΣΤΙΣ ΑΛΛΕΣ ΔΥΟ ΔΟΜΕΣ ΕΠΑΝΑΛΗΨΗΣ
ΓΕΝΙΚΗ ΜΟΡΦΗ ΓΙΑ
ΓΙΑ ΜΤ ΑΠΟ ΑΤ ΜΕΧΡΙ ΤΤ ΜΕ_ΒΗΜΑ ΒΜ
ΕΝΤΟΛΕΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Όπου ΜΤ ο μετρητής, ΑΤ η αρχική τιμή, ΤΤ η τελική τιμή και ΒΜ το βήμα
ΓΙΑ ΣΕ ΟΣΟ
ΜΤ <- ΑΤ
ΑΝ ΒΜ >= 0 ΤΟΤΕ
ΟΣΟ ΜΤ <= ΤΤ ΕΠΑΝΑΛΑΒΕ
ΕΝΤΟΛΕΣ
ΜΤ <- ΜΤ + ΒΜ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΛΛΙΩΣ
ΟΣΟ ΜΤ >= ΤΤ ΕΠΑΝΑΛΑΒΕ
ΕΝΤΟΛΕΣ
ΜΤ <- ΜΤ + ΒΜ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΑΝ
ΓΙΑ ΣΕ ΜΕΧΡΙΣ_ΟΤΟΥ (με μετατροπή σε ΟΣΟ πρώτα)
ΜΤ <- ΑΤ
ΑΝ ΒΜ >= 0 ΤΟΤΕ
ΑΝ ΜΤ <= ΤΤ ΤΟΤΕ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΕΝΤΟΛΕΣ
ΜΤ <- ΜΤ + ΒΜ
ΜΕΧΡΙΣ_ΟΤΟΥ ΜΤ > ΤΤ
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ
ΑΝ ΜΤ >= ΤΤ ΤΟΤΕ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΕΝΤΟΛΕΣ
ΜΤ <- ΜΤ + ΒΜ
ΜΕΧΡΙΣ_ΟΤΟΥ ΜΤ < ΤΤ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ
ΔΙΟΝΥΣΗΣ
Καλησπέρα. Θα ήθελα τη βοήθεια σας στα παρακάτω θέματα:
1) Όταν έχουμε να μετατρέψουμε μία δομή Όσο σε Μέχρις_ότου θα πρέπει να προσθέσουμε μία δομή επιλογής για να ελέγχει αν θα εκτελεστούν οι εντολές του βρόχου αφού ο αλγόριθμος με τη χρήση της δομής Μέχρις_ότου εκτελείται τουλάχιστον μία φορά;
2)Όταν έχουμε να μετατρέψουμε μία δομή Μέχρις_ότου σε Όσο θα πρέπει να εκτελεστεί ένα σετ εντολών (μία επανάληψη) πριν από τη δομή επανάληψης για να εξασφαλιστεί ότι ο αλγόριθμος θα εκτελεστεί τουλάχιστον μία φορά;
Ή μήπως αυτοί οι έλεγχοι είναι περιττοί;
Γεια σου φίλε, ελπίζω να είσαι καλά,
Αν έχεις νούμερα (αρχικές τιμές, όρια διαστημάτων κτλ) τότε βλέπεις αν γίνεται μια μόνο ή καμία επανάληψη και συνεπώς όλα είναι απλά (φυσικά δε θα ζητηθεί τέτοια μετατροπή).
Αν όμως δεν είναι προφανές αλλά υπάρχουν περιπτώσεις τότε πρέπει να ελέγξεις. Κι αυτό γιατί τα δυο τμήματα αλγορίθμων πρέπει να έχουν την ΙΔΙΑ ΕΞΟΔΟ για την ΙΔΙΑ ΕΙΣΟΔΟ (τιμές μεταβλητών). Κι αυτό θα γίνει σωστά, μόνο αν διερευνήσεις όλες τις περιπτώσεις
http://users.kor.sch.gr/ptsiotakis/aepp/aepp_ask23_3.htm
Από όσο --> μέχρις_ότου
αν εκτελέσουμε βήμα βήμα την όσο και πούμε ότι είναι μία επαναλαμβανόμενη αν έχουμε
όσο συνθήκη επανάλαβε
ομάδα εντολών
τέλος_επανάληψης
αυτό είναι εισοδύναμο με
αν συνθήκη τότε
οε
αν συνθήκη τότε
οε
αν συνθήκη τότε
.....
εδώ βλέπουμε ότι επαναλαμβανεται η
αν συνθκη τότε
οε
κάποιος άλλος όμως μπορεί την πρώτη συνθήκη να τη βγάλει απέξω από την επανάληψη και να πει ότι επαναλαμβάνονται οι εντολές
οε
αν συνθήκη τότε
που είναι η μέχρις_ότου αφού η συνθήκη βρίσκεται στο τέλος της επανάληψης. Άρα η μετατροπή έχει:
αν συνθήκη τότε (που τη βγάλαμε εκτός επανάληψης)
αρχή_επανάληψης
οε
μέχρις_ότου όχι(συνθήκη)
τέλος_αν
από μέχρις_ότου σε για
Αν γίνεται η επανάληψη την μετατρέπουμε πρώτα σε όσο και στη συνέχεια σε για.
η γενική μετατροπή αφού πρώτα την έκανα σε όσο είναι:
μτ<-ατ
αρχή_επανάληψης
οε
μτ<-μτ+β
μέχρις_ότου μτ ΤΣ τιμή
και σε για γίνεται:
μτ<-ατ
οε
μτ<-μτ +β
για μτ από ατ+β μέχρι ττ με_βήμα β
οε
τέλος_επανάληψης
όπου ττ πρέπει να αναζητηθεί με βάση την μτ ΤΣ τιμή (για παράδειγμα αν έλεγε μτ >=100) θα έπρεπε να ήταν μέχρι 99
Καλημέρα
Η μετατροπή από τη μια δομή επανάληψης στην άλλη είναι μεγάλο θέμα και έχει ενδιαφέρον μια που πέφτει και στις εξετάσεις. Φοβάμαι πως τα πράγματα έχουν πάρει λάθος τροπή γενικότερα.
Να θέσω ένα ερώτημα πάνω στο οποίο στηρίζονται όλα:
Τι εννοούμε όταν λέμε ότι θέλουμε "ισοδύναμο αλγόριθμο" ή "μετατροπή" από τη μια δομή στην άλλη; Ποιος είναι ο ορισμός του ισοδύναμου αλγόριθμου (ή της κωδικοποίησης) έτσι ώστε να ελέγξουμε αν μια μετατροπή είναι ισοδύναμη; Τι θέλουμε να ελέγξουμε σε αυτές τις ασκήσεις;
Ζητάμε απλώς να έχουν την ίδια έξοδο όταν υπάρχει η ίδια είσοδος ή εννοούμε ότι πρέπει οι 2 δομές να κάνουν ακριβώς τα ίδια πράγματα με ακριβώς την ίδια σειρά;
Εγώ προσωπικά θεωρώ σωστό το δεύτερο και ουσιαστικά αυτό που ζητάμε σε αυτές τις ασκήσεις είναι η μετατροπή του ίδιου αλγορίθμου σε ισοδύναμη κωδικοποίηση που περιέχει την άλλη δομή επανάληψης. Δηλάδή αλλάζει η κωδικοποίηση αλλά όχι ο αλγόριθμος.
Αν ξεκαθαρίσουμε αυτό τότε όλα τα άλλα προκύπτουν εύκολα.
Καλημέρα και από εμένα.
ΠαράθεσηΖητάμε απλώς να έχουν την ίδια έξοδο όταν υπάρχει η ίδια είσοδος ή εννοούμε ότι πρέπει οι 2 δομές να κάνουν ακριβώς τα ίδια πράγματα με ακριβώς την ίδια σειρά;
Νομίζω ότι ζητάμε το δεύτερο. Για παράδειγμα ας υποθέσουμε είχαμε την δομή:
χ<-1
όσο χ<=10 επανάλαβε
γράψε χ
χ<-χ+1
τέλος_επανάληψης
και κάποιος την μετέτρεπε σε
για ως εξής
για χ από 5 μέχρι 10000
αν χ<=104 τότε
γράψε χ-4
τέλος_αν
τέλος_επανάληψης
Ο μαθητής αυτός θα έπρεπε να πάρει άριστα; Δεν νομίζω.
Τώρα όσο αφορά την μετατροπή από
όσο σε
μέχρις_ότου συνηθίζετε να βάζουμε την συνθήκη του
αν μέσα στην δομή
μέχρις_ότου. Αν και η μετατροπή αυτή δεν είναι η αντίστοιχη της όσο αφού στην όσο σε κάθε επανάληψη γίνεται μία σύγκριση, ενώ στη μετατροπή της σε μέχρις_ότου γίνονται 2, την απάντηση αυτή τη λαμβάνουμε σωστή. Μήπως εδώ κάνουμε λάθος και δεν πρέπει να την λαμβάνουμε σωστή;
Αν όντως εννοούμε το δεύτερο (και εγώ είμαι έντονα υπερ αυτής της άποψης) τότε τα πράγματα για μένα είναι ξεκάθαρα.
Προφανώς και δεν είναι πρέπει να ισοδύναμη κωδικοποίηση το να βάζουμε την Αν μέσα στην Μέχρις_ότου κατά τη μετατροπή από Όσο σε μέχρις_ότου γιατί στη μια περίπτωση η Αν εκτελείται μια φορά και στην άλλη σε κάθε επανάληψη.
Επίσης είναι λάθος να ζητάμε μετατροπή της Όσο και της Μέχρις_ότου με τελεστή < ή > σε Για αφού τελικά στη συνθήκη της Για γίνεται έλεγχος με τελεστή <= ή >=.
Επίσης είναι λάθος να ζητάμε μετατροπή από Όσο ή μέχρις_ότου με αλλαγή μετρητή στη μέση σε Για, αφού αλλάζουμε τη σχετική σειρά των εντολών.
Να προσθέσω επίσης ότι δεν πρέπει να αρκούμαστε σε ίδια έξοδο, αφού σκεφτείτε ότι μπορεί κάποιος να δώσει σειριακή αναζήτηση με Όσο και σαν ισοδύναμο να θεωρήσουμε δυαδική αναζήτηση με μέχρις_ότου. Σίγουρα δε μπορεί να ζητάμε κάτι τέτοιο.
Πολλά πράγματα μπαίνουν στη θέση τους αν ξεκαθαρίσουμε τι ακριβώς ζητάμε.
ΠαράθεσηΕπίσης είναι λάθος να ζητάμε μετατροπή της Όσο και της Μέχρις_ότου με τελεστή < ή > σε Για αφού τελικά στη συνθήκη της Για γίνεται έλεγχος με τελεστή <= ή >=.
Για το συγκεκριμένο δεν συμφωνώ απόλυτα γιατί τότε μπορεί να υποστηρίξει κάποιος ότι ούτε η όσο σε μέχρις_ότου γίνεται αφού αλλάζει η συνθήκη. Και δεν μπορώ να δεχτώ ότι αν βάλουμε τελεστή < σε μία όσο να λέμε τότε ότι αυτή δεν μετατρέπεται σε ισοδύναμη δομή για.
ΠαράθεσηΕπίσης είναι λάθος να ζητάμε μετατροπή από Όσο ή μέχρις_ότου με αλλαγή μετρητή στη μέση σε Για, αφού αλλάζουμε τη σχετική σειρά των εντολών.
έστω τα τμήματα:
όσο χ<=100 επανάλαβε
γράψε χ
χ<-χ+1
κ<-κ+χ
τέλος_επανάληψης
και
όσο χ<=100 επανάλαβε
γράψε χ
κ<-κ+(χ+1)
χ<-χ+1
τέλος_επανάληψης
Να χαρακτηρίσετε αν τα παραπάνω τμήματα είναι ισοδύναμα.
Τι θα απαντούσαμε; Αν λέγαμε ναι τότε έχει νόημα η μετατροπή του πρώτου τμήματος σε για.
Η Όσο γίνεται πάντα σε μέχρις_ότου λόγω του ότι μια λογική παράσταση παίρνει μόνο 2 τιμές: Αληθής και Ψευδής. Ελέγχοντας αν ισχύει η συνθήκη σ ταυτόχρονα ελέγχεις και την όχι (σ). Είναι το ίδιο. Στη μετατροπή Όσο σε μέχρις_ότου και ανάποδα αντιστρέφοντας τη συνθήκη κάνεις τον ίδιο έλεγχο.
Όταν όμως αλλάζεις τον τελεστή ο έλεγχος είναι διαφορετικός. Δες για παράδειγμα το θέμα
https://alkisg.mysch.gr/steki/index.php?topic=1157.0
Για το δεύτερο έχω να πω ότι ένας ορισμός από κάποιο σημείο και μετά είναι θέμα επιλογής. Αν δώσεις ορισμό απλά βλέπεις αν ισχύει ή όχι. Αν δώσουμε ένα ορισμό σαν αυτό που έδωσα τότε αυτά τα 2 δεν είναι ισοδύναμα αφού δεν κάνουν τα ίδια ακριβώς πράγματα με την ίδια σειρά.
Αν αυτός ο ορισμός δίνει συμπεράσματα που δε μας αρέσουν πιθανόν να μην έχουμε κάνει καλή επιλογή ορισμού λόγω του ότι έχει άσχημες συνέπειες. Ποιος είναι όμως ο ορισμός; Αν μιλήσουμε απλά για ίδια είσοδο έξοδο προκύπτουν τα προβλήματα που εντοπίσαμε παραπάνω.
Προσωπικά αισθάνομαι ικανοποιημένος από τον ορισμό που προσπάθησα να δώσω και δεν έχω πρόβλημα στο να θεωρήσω διαφορετικούς τους 2 κώδικες που δίνεις. Δεν κάνουν πανομοιότυπα πράγματα. Αλλάζει η σειρά απλά δίνουν ίδια έξοδο.
Γιώργο οι δύο κώδικες που δίνω είναι διαφορετικοί αλλά είναι ισοδύναμοι αφού βγάζουν το ίδιο αποτέλεσμα και έχουν την ίδια πολυπλοκότητα. Με αυτόν τον ορισμό που δίνεις ως ισοδυναμία αλγορίθμων νομίζω ότι μιλάμε πλέον για ίδιους αλγόριθμους.
Κώστα με βάση τον ορισμό που δίνω (που ενδεχομένως να μην είναι και η καλύτερη επιλογή) - έτσι όπως τον εννοώ τουλάχιστο - ο ένας αλλάζει πρώτα το χ και μετά το κ ενώ ο δεύτερος τα κάνει ανάποδα. Έχει αλλάξει η σχετική σειρά των εντολών οπότε οι 2 κώδικες δεν κάνουν ακριβώς τα ίδια και με την ίδια σειρά.
Αν μιλήσουμε για ίδια έξοδο και ίδια πολυπλοκότητα τότε πάμε σε άλλο ορισμό με ενδεχόμενο να έχουμε άλλα side effects.
Μπορεί να είναι λίγο σπαστικό αλλά το έχουν αυτό οι ορισμοί :) . Ρίξε μια ματιά στο link που σου έστειλα (το οποίο είμαι βέβαιος ότι είναι λάθος από μέρους της επιτροπής εξετάσεων) για να δεις τι προβλήματα μπορεί να προκύψουν αν έχουμε ασαφείς ορισμούς. Και οι τόσες κουβέντες που έχουμε ανοίξει για τις κατηγοριοποιήσεις προβλημάτων (επιλύσιμα-άλυτα, δομημένα αδόμητα) είναι αποτέλεσμα ασαφών ορισμών.
Γιώργο το κοίταξα το Link και πράγματι δώσατε μεγάλη μάχη για να λύσετε μία άσκηση που μάλλον δεν προοριζόταν για μαθητές από καθηγητές. Δεν ξέρω πιο είναι το λάθος το για μαθητές ή το από καθηγητές :o.
Πράγματι η άσκηση έπρεπε να λέει για ακέραιους αριθμούς.
Τέλος πάντων εμένα μου αρέσουν αυτές οι κουβέντες, γιατί πάντα κάτι καλό βγαίνει. Απλά τους μαθητές να μην βάζουν κάποιοι σε τέτοια παιχνίδια, γιατί την πληρώνουν οι επόμενες γενιές μαθητών που πρέπει να τους κάνουμε και την κουφή περίπτωση που κάποιοι βάλανε απρόσεκτα στις εξετάσεις.
Πάντως για μένα αν θέλουμε να μιλάμε για μετατροπές μεταξύ δομών, είναι επιτακτική ανάγκη να δοθεί αυστηρός ορισμός.
Ένας ορισμός που στηρίζεται στην μόνο έξοδο δεν μπορεί να σταθεί αφού πχ μπορούμε να φτιάξουμε αλγορίθμους που κάνουν τελείως διαφορετικά πράγματα και δε βγάζουν έξοδο εντός του βρόχου ή βγάζουν την ίδια έξοδο. Αλλά έχουν και μη κοινές εντολές.
Ούτε στην πολυπλοκότητα μπορούμε να στηριχτούμε. Πχ μπορούμε σε πίνακα 2 διαστάσεων να βρούμε το άθροισμα κάθε στήλης σαρώνοντας είτε κατά στήλη είτε κατά γραμμή (πχ σχολικό βιβλίο σελίδα 58). Οι αλγόριθμοι είναι τελείως διαφορετικοί αλλά καταλήγουν στο ίδιο αποτέλεσμα.
Για μένα η μόνη λύση που μπορεί να περπατήσει είναι ο τελείως περιοριστικός ορισμός «οι 2 κωδικοποιήσεις να κάνουν ακριβώς τα ίδια πράγματα και με ακριβώς την ίδια σειρά». Ουσιαστικά δηλαδή δε μιλάμε για μετατροπή αλγορίθμου (αφού αλγόριθμος είναι τα βήματα που κάνουμε) αλλά για μετατροπή κωδικοποίησης. Αν κάτσεις και εκτελέσεις τον αλγόριθμο με το χέρι θα κάνεις τις ίδιες ακριβώς ενέργειες. Αυτές τις ίδιες ενέργειες (που αποτελούν τον αλγόριθμο) θα πρέπει να μπορείς να τις εκφράσεις σε ψευδογλώσσα είτε με Όσο είτε με μέχρις_ότου. Δηλαδή διαχωρίζω σαφώς σαν έννοιες τον αλγόριθμο από την κωδικοποίηση του σε ψευδογλώσσα.
Αν το καλοσκεφτούμε
τι ακριβώς θα θέλαμε νε δούμε με τέτοιες ασκήσεις; Προφανώς το ότι μπορεί κάποιος να κάνει χρήση και άλλης εντολής αλλά τα πράγματα που γίνονται να είναι τα ίδια.
Για μένα η προχειρότητα με την οποία αντιμετωπίστηκε το μάθημα στις εξετάσεις τα πρώτα χρόνια δημιούργησε ένα κακό προηγούμενο και τώρα καθόμαστε όλοι και μιλάμε για μετατροπές χωρίς να έχουμε καθορίσει ένα συνεπές πλαίσιο. Το ζήτημα για μένα είναι αν μπορούμε αυτή τη στιγμή να κάνουμε κάτι για αυτό. Δηλαδή να βρούμε κάτι που να στέκει και στη συνέχεια να το επιβάλουμε στις εξεταζόμενες ασκήσεις.
Παράθεση. Αν κάτσεις και εκτελέσεις τον αλγόριθμο με το χέρι θα κάνεις τις ίδιες ακριβώς ενέργειες. Αυτές τις ίδιες ενέργειες (που αποτελούν τον αλγόριθμο) θα πρέπει να μπορείς να τις εκφράσεις σε ψευδογλώσσα είτε με Όσο είτε με μέχρις_ότου. Δηλαδή διαχωρίζω σαφώς σαν έννοιες τον αλγόριθμο από την κωδικοποίηση του σε ψευδογλώσσα.
δηλαδή:
χ<- 100
όσο χ<100 επανάλαβε
γράψε χ
χ<-χ+1
τέλος_επανάληψης
και
χ<-100
αρχή_επανάληψης
γράψε χ
χ<-χ+1
μέχρις_ότου χ>=100
να μην τα θεωρήσουμε ισοδύναμα γιατί άμα τα εκτελέσω με το χέρι στο πρώτο κάνω πρώτα την σύγκριση και στο δεύτερο εμφανίζω το χ. ΄
ΠαράθεσηΟύτε στην πολυπλοκότητα μπορούμε να στηριχτούμε. Πχ μπορούμε σε πίνακα 2 διαστάσεων να βρούμε το άθροισμα κάθε στήλης σαρώνοντας είτε κατά στήλη είτε κατά γραμμή (πχ σχολικό βιβλίο σελίδα 58). Οι αλγόριθμοι είναι τελείως διαφορετικοί αλλά καταλήγουν στο ίδιο αποτέλεσμα.
Προσωπικά τους δύο αλγόριθμους τους θεωρώ ισοδύναμους.
Στο πρώτο κομμάτι δε θα εκτελεστεί καμία φορά ο βρόχος. Στο δεύτερο θα εκτελεστεί 1 φορά. Προφανώς δεν είναι ισοδύναμα.
Αν αρχικοποιήσεις το χ με 1 αντί για 100 τότε όντως προκύπτει θέμα. (Ίσως αυτό να ήθελες να πεις και ξέφυγε.).
Σε αυτή την περίπτωση με βάση τον ορισμό μου οι 2 ψευδοκώδικες δεν είναι ισοδύναμοι γιατί ο ένας κάνει μια σύγκριση που δεν την κάνει ο άλλος. Για να είναι ισοδύναμοι θα πρέπει η μέχρις)ότου να μπει σε μια Αν χ<100. Τότε θα γίνονται τα ίδια πράγματα.
Δες την εξής άσκηση:
Να γραφτεί ο παρακάτω ψευδοκώδικας χρησιμοποιώντας την Όσο έτσι ώστε για κάθε είσοδο να παράγεται η ίδια έξοδος.
Διαβασε κ
ι ← 1
Αρχή_επανάληψης
Εμφάνισε ι
ι ← ι+1
Μέχρις_ότου ι>κ
Θα δεις τι ακριβώς εννοώ.
Αυτό που θέλω να τονίσω είναι ότι δεν είναι σωστό να θεωρούμε προσωπικό ζήτημα του Κώστα ή του Γιώργου το αν 2 ψευδοκώδικες είναι ισοδύναμοι. Πρέπει να υπάρχουν ενιαίοι κανόνες. Θέλουμε δηλαδή έναν ορισμό και με βάση αυτόν να μπορούμε να αποφανθούμε για την ισοδυναμία. Προσπάθησε να δώσεις έναν ορισμό για να δεις τι ακριβώς προβλήματα προκύπτουν. Ανάφερα μερικά παραπάνω (στο θέμα της πολυπλοκότητας και της εξόδου). Δεν είναι εύκολη υπόθεση να δοθεί ορισμός χωρίς ασυνέπειες. Ούτε όμως είναι σωστό να στηριζόμαστε στην υποκειμενική διαίσθησή μας και το γούστο. Αυτά μπορεί να διαφέρουν από άνθρωπο σε άνθρωπο.
X<-1 εννούσα (Με την πίεση του κουδουνιού την πάτησα :o)
Μπορεί να είναι το σωστό αυτό που λες, βάζοντας το άν χ<=100 στην αρχή και προκύπτει μάλιστα από το γενικό σκεπτικό που έδωσα σε κάποιοα post παραπάνω:
Παράθεσηόσο συνθήκη επανάλαβε
ομάδα εντολών
τέλος_επανάληψης
αυτό είναι ισοδύναμο με
αν συνθήκη τότε
οε
αν συνθήκη τότε
οε
αν συνθήκη τότε
.....
εδώ βλέπουμε ότι επαναλαμβανεται η
αν συνθκη τότε
οε
κάποιος άλλος όμως μπορεί την πρώτη συνθήκη να τη βγάλει απέξω από την επανάληψη και να πει ότι επαναλαμβάνονται οι εντολές
οε
αν συνθήκη τότε
που είναι η μέχρις_ότου αφού η συνθήκη βρίσκεται στο τέλος της επανάληψης. Άρα η μετατροπή έχει:
αν συνθήκη τότε (που τη βγάλαμε εκτός επανάληψης)
αρχή_επανάληψης
οε
μέχρις_ότου όχι(συνθήκη)
τέλος_αν
με αυτό δίνεται απάντηση και στο παράδειγμα που έδωσες.
Δεν μπορώ όμως να θεωρήσω ότι χαλάει η ισοδυναμία αν δεν βάλουμε την σύγκριση
αν χ<=100 αν η συνθήκη της είναι σίγουρα αληθής.
ΠαράθεσηΑυτό που θέλω να τονίσω είναι ότι δεν είναι σωστό να θεωρούμε προσωπικό ζήτημα του Κώστα ή του Γιώργου το αν 2 ψευδοκώδικες είναι ισοδύναμοι. Πρέπει να υπάρχουν ενιαίοι κανόνες. Θέλουμε δηλαδή έναν ορισμό και με βάση αυτόν να μπορούμε να αποφανθούμε για την ισοδυναμία. Προσπάθησε να δώσεις έναν ορισμό για να δεις τι ακριβώς προβλήματα προκύπτουν. Ανάφερα μερικά παραπάνω (στο θέμα της πολυπλοκότητας και της εξόδου). Δεν είναι εύκολη υπόθεση να δοθεί ορισμός χωρίς ασυνέπειες. Ούτε όμως είναι σωστό να στηριζόμαστε στην υποκειμενική διαίσθησή μας και το γούστο. Αυτά μπορεί να διαφέρουν από άνθρωπο σε άνθρωπο.
Εννοείται δεν είναι θέμα προσωπικό, και βέβαια πρέπει όσο γίνεται όλα τα θέματα να είναι ξεκάθαρα από το βιβλίο. Αυτή η κουβέντα γίνεται, γιατί ελπίζω βοηθάει και τους δύο και όποιον άλλον τη διαβάζει, αφού το βιβλίο δεν έχει ορισμό του. Όμως αυτή τη στιγμή μετά από τόσα θέματα εξετάσεων που έχουν μπει στις πανελλήνιες και αφού τέτοιες μετατροπές και χειρότερες τις έχουμε δει ως θέματά τους, ως ισοδύναμα τμήματα έχω στο μυαλό μου αυτά που δίνουν το ίδιο αποτέλεσμα και έχουν την ίδια ή περίπου την ίδια πολυπλοκότητα . Μπορούμε όμως λίγο να αλλάξουμε την εκφώνηση του προβλήματος, βγάζοντας την λέξη ισοδύναμα ως εξής:
Να μετατραπεί το παρακάτω πρόγραμμα ώστε να χρησιμοποιεί την δομή επανάληψης
για παράδειγμα την για αντί της όσο, ώστε να βγάζει τα ίδια αποτελέσματα για κάθε τιμή
για παράδειγμα εισόδου. Την πολυπλοκότητα την βγάζουμε στην άκρη αφού δεν μας νοιάζει ο αριθμός των επαναλήψεων.
Ή να δοθεί η εκφώνηση:
Να μετατραπεί το παρακάτω πρόγραμμα ώστε να χρησιμοποιεί την δομή επανάληψης
για παράδειγμα την για αντί της όσο, ώστε να βγάζει τα ίδια αποτελέσματα
με τον ίδιο αριθμό επανάληψεων για κάθε τιμή
για παράδειγμα εισόδου. Βάζουμε και λίγο την πολυπλοκότητα.
Παράθεση από: ntzios kostas στις 25 Σεπ 2008, 12:44:21 ΜΜ
Μπορούμε όμως λίγο να αλλάξουμε την εκφώνηση του προβλήματος, βγάζοντας την λέξη ισοδύναμα ως εξής:
Να μετατραπεί το παρακάτω πρόγραμμα ώστε να χρησιμοποιεί την δομή επανάληψης για παράδειγμα την για αντί της όσο, ώστε να βγάζει τα ίδια αποτελέσματα για κάθε τιμή για παράδειγμα εισόδου. Την πολυπλοκότητα την βγάζουμε στην άκρη αφού δεν μας νοιάζει ο αριθμός των επαναλήψεων.
Ή να δοθεί η εκφώνηση:
Να μετατραπεί το παρακάτω πρόγραμμα ώστε να χρησιμοποιεί την δομή επανάληψης για παράδειγμα την για αντί της όσο, ώστε να βγάζει τα ίδια αποτελέσματα με τον ίδιο αριθμό επανάληψεων για κάθε τιμή για παράδειγμα εισόδου. Βάζουμε και λίγο την πολυπλοκότητα.
Κοίτα να δεις γιατί αν μπλέξεις με έξοδο, αποτελέσματα, πολυπλοκότητα, αριθμό επαναλήψεων και οτιδήποτε άλλο έχει την ίδια έννοια χωρίς να μπεις σε επίπεδο συγκεκριμένης εντολής, πάντα θα υπάρχει πρόβλημα.
Οι παρακάτω 2 κώδικες βρίσκουν το άθροισμα κάθε στήλης πίνακα 2 διαστάσεων. Έχει προηγηθεί αρχικοποίηση του πίνακα sum
Κώδικας 1
Για j από 1 μέχρι 10
Για i από 1 μέχρι 10
Sum[j]<-sum[j] + α[i,j]
Τέλος_επανάληψης
Τέλος_επανάληψης
Κώδικας 2
Για i από 1 μέχρι 10
Για j από 1 μέχρι 10
Sum[j]<-sum[j] + α[i,j]
Τέλος_επανάληψης
Τέλος_επανάληψης
Οι 2 κώδικες έχουν ίδια έξοδο (είναι σε παρακάτω εντολή και δεν τη βάζω) έχουν το ίδιο αποτέλεσμα (αποθηκεύουν στον πίνακα sum το άθροισμα των στηλών), κάνουν τις ίδιες επαναλήψεις και έχουν την ίδια πολυπλοκότητα.
Φαντάσου λοιπόν ότι σου δίνουν τον πρώτο και ζητάνε μετατροπή σε Όσο. Και κάποιος γράφει σαν απάντηση τον δεύτερο με χρήση Όσο. Είναι σωστή η μετατροπή;
Εγώ λέω όχι αφού ο κάθε κώδικας κάνει τελείως διαφορετική σάρωση. Ο ένας σαρώνει κατά στήλη και ο άλλος κατά γραμμή. Είναι διαφορετικοί αλγόριθμοι (δε μιλάω μόνο για κωδικοποίηση).
Παρόλα αυτά και οι 2 έχουν ίδια έξοδο, ίδια πολυπλοκότητα, ίδιο αριθμό βημάτων και ίδιο αποτέλεσμα. Όλα ίδια σε «μακροσκοπικό επίπεδο».
Άρα ένας ορισμός βασισμένος σε τέτοιες έννοιες (που δεν κατεβαίνει σε επίπεδο μεμονωμένης εντολής) θα τους έδινε ισοδύναμους
πράγμα προφανώς λάθος.
Γι αυτό εγώ πιστεύω ότι πρέπει αναγκαστικά να μιλήσουμε για ίδιες ενέργειες και με την ίδια σειρά.
Φυσικά τώρα τα πράγματα έχουν πάρει κάποιο δρόμο, έχουν πέσει θέματα σε εξετάσεις και δεν μπορώ να φανταστώ τι θα μπορούσε να γίνει. Τουλάχιστο θα ήταν χρήσιμο να βρίσκαμε με την κουβέντα ποιο είναι το σωστό.
Πολύ καλό παράδειγμα.
Εσύ τι πιστεύεις ότι θα έκανες αν σου έκανε ένας μαθητής μία τέτοια μετατροπή; Πόσο θα έβαζες στα 10;
Πάντως αν η ερώτηση της άσκησης ήταν διατυπωμένη όπως σου είπα παραπάνω δεν νομίζω ότι υπάρχει κανένα πρόβλημα.
Αν όμως μου έλεγε ισοδύναμο τμήμα με την δομή όσο τότε πρέπει οπωσδήποτε να δοθεί ορισμός από την επιτροπή για το ισοδύναμο. Κανονικά με βάση τα θέματα (και την βαθμολόγησή τους) των προηγούμενων ετών δεν μπορεί να δώσει τον ορισμό που δίνεις.
Εψαξα λίγο στο διαδίκτυο να βρω κάτι για ισοδύναμους αλγόριθμους αλλά δεν τα κατάφερα. Πάντως τώρα που το σκέφτομαι μπορούμε να βρούμε έναν ορισμό με βάση τη λέξη ισοδύναμος. Δηλαδή δύο αλγόριθμοι να λέγονται ισοδύναμοι αν πάμε από τον έναν στον άλλον με διαδοχικές ισοδυναμίες. Πώς σου φαίνεται;
Για το συγκεκριμένο θέμα 1Δ των επαναληπτικών του 2001 η εκφώνηση ήταν :
Δ. Δίνεται το παρακάτω τμήμα αλγορίθμου :
Χ <-- Α
Αρχή_επανάληψης
Χ <-- Χ + 2
Τύπωσε το Χ
Μέχρις_ότου Χ>=Μ
α. Να δώσετε τη δομή επανάληψης «Για
από
μέχρι
βήμα» η οποία τυπώνει ακριβώς τις ίδιες τιμές με το πιο πάνω τμήμα αλγορίθμου
Στις επαναληπτικές τους 2008 το 1Ε ζητούσε ισοδύναμο αλγόριθμο απο Για σε Όσο και Μέχρις_ότου. Προφανώς η ισοδυναμία που ζητείται, αναφέρεται στην ίδια έξοδο όταν δοθούν τα ίδια δεδομένα πράγμα που μπορεί να υλοποιηθεί με διαφορετικούς τρόπους.
Ειλικρινά δε ξέρω αν αυτό υπόκειται -πάντα- σε κανόνες κι αν πρέπει να ψάξουμε να τους βρούμε (αν υπάρχουν) ...
Όπως γνωρίζουμε οι δομές Όσο και Μέχρις_ότου χρησιμοποιούνται για βρόχους που εκτελούνται για άγνωστο αριθμό επαναλήψεων. Όλοι οι βρόχοι μπορούν να υλοποιηθούν με κάποια απο τις δομές αυτές.
Συνεπώς, πάντα μπορεί κάποιος βρόχος να μετατραπεί απο τη μια στην άλλη.
Είναι προφανές οτι λόγω των διαφορετικών ιδιοτήτων τους η κωδικοποίηση δε θα είναι η ίδια.
Ομοίως για τα ζευγάρια Όσο-Για και Μέχρις_ότου-Για.
Το μόνο σίγουρο για αξιολόγηση (=βαθμολόγηση) τέτοιων μετατροπών είναι η ίδια έξοδος των δυο βρόχων (για ίδια είσοδο). Σίγουρο από την άποψη οτι είναι μετρήσιμο και μπορεί να αξιολογηθεί ακόμη και για διαφορετικές κωδικοποιήσεις...
Άλλωστε και στη ΔΤ4 στη σελίδα 79 του τετραδίου μαθητή η διατύπωση είναι όπως το θέμα 1Ε του 2008, που προανέφερε ο σοφός Λαέρτης.
Για ισοδύναμο κώδικα, εξαρτάται σε τι επίπεδο μιλάμε.
Π.χ. οι εντολές
α <- "Κειμενάκι"
β <- 1
και οι αντιστραμμένες εντολές
β <- 1
α <- "Κειμενάκι"
σε επίπεδο άγριου optimization (π.χ. διαδικασίες assembly που καλούνται χιλιάδες φορές σε κάποιο πρόγραμμα) δεν θεωρούνται ισοδύναμες. Αυτοί που γράφουν τέτοιο κώδικα assembly μετράνε μέχρι και το cache line του επεξεργαστή για να δουν πώς θα γλυτώσουν 1-2 κύκλους CPU.
Σε επίπεδο κατασκευής αλγορίθμων χωρίς να μας ενδιαφέρουν οι επιδόσεις και η πολυπλοκότητα, θα μπορούσαμε να πούμε "αρκεί να δίνουν το ίδιο αποτέλεσμα για όλες τις δυνατές εισόδους".
Αλλά έτσι, για το πρόβλημα "εύρεση μεγίστου σε έναν πίνακα", θα θεωρούσαμε ισοδύναμο κώδικα και το "τον ταξινομώ και εκτυπώνω τον πρώτο". :(
Εγώ στον "ορισμό" για ισοδύναμους αλγορίθμους θα πρόσθετα τουλάχιστον τον περιορισμό να έχουν την ίδια πολυπλοκότητα (δηλαδή αν ο ένας κώδικας κάνει N επαναλήψεις, ο άλλος να μην κάνει Ν^2), αλλά είναι λίγο δύσκολο θέμα με την τρέχουσα ύλη που δεν περιλαμβάνει το κεφάλαιο με την πολυπλοκότητα...
Θα προσπαθήσω να εξηγήσω πως τα έχω στο κεφάλι μου.
Στην παρούσα κουβέντα υπάρχουν 2 διαφορετικά πράγματα. Το ένα είναι ο αλγόριθμος δηλαδή οι συγκεκριμένες ενέργειες που κάνει αυτός που τον εκτελεί.
Το άλλο είναι η κωδικοποίηση σε ψευδογλώσσα δηλαδή οι λεκτικές περιγραφές των εντολών (πχ Όσο, μέχρις_ότου) με τις οποίες αναπαριστούμε τον αλγόριθμο.
Ξαναλέω: για μένα άλλο αλγόριθμος και άλλο κωδικοποίηση σε ψευδογλώσσα.
Στο συγκεκριμένο θέμα δεν έχει νόημα να μιλάμε για ισοδυναμία αλγορίθμων. Αυτό ακόμα και βιβλιογραφικά φαίνεται πως δεν ορίζεται με κάποιο κοινά αποδεκτό τρόπο. Ισοδύναμοι αλγόριθμοι μπορεί να είναι αυτοί που δίνουν ίδια έξοδο αν έχουν την ίδια είσοδο και εδώ μπορούμε ενδεχομένως να βάλουμε στο παιχνίδι και την πολυπλοκότητα.
Εδώ όμως μιλάμε για κωδικοποίηση και όχι για αλγόριθμο. Θέλουμε δηλαδή τον ίδιο ακριβώς αλγόριθμο (δηλαδή τις ίδιες ακριβώς ενέργειες) να τις κωδικοποιήσουμε άλλη εντολή πχ με Μέχρις_ότου αντί για Όσο. Για σκεφτείτε λίγο
τι ακριβώς θέλουν να ελέγξουν οι ασκήσεις αυτού του είδους;
Για μένα λοιπόν δεν έχει νόημα να συζητάμε για ισοδυναμίες αλγορίθμων γιατί ξεφεύγουμε.
Και βέβαια (Κώστα) στο παράδειγμα που έδωσα στο προηγούμενο μήνυμά μου ο μαθητής αλλάζει τον αλγόριθμο. Δεν του ζήτησα αυτό. Εγώ θέλω τα ίδια πράγματα να τα κάνει με ίδια εντολή. Αυτός κάνει άλλα πράγματα με άλλη εντολή. Άλλο βέβαια αν δείχνει ότι ξέρει.
Για μένα το ουσιώδες θέμα είναι το να αποσαφηνιστεί αν μιλάμε για «ισοδυναμίες» αλγορίθμων ή κωδικοποιήσεων. Εγώ λέω το καθαρά δεύτερο: ίδιος αλγόριθμος, άλλη εντολή.
edit: ʼλκη νομίζω πως δεν πρέπει να μας απασχολήσει το θέμα της υλοποίησης σε χαμηλό επίπεδο. Μπορεί η Όσο και Μέχρις_ότου μέσα σε Αν να δίνουν διαφορετικό δυαδικό κώδικα τελικά αλλά σαν ενέργειες που κάνει αυτός που εκτελεί τον αλγόριθμο είναι το ίδιο (έλεγχος - εντολές βρόχου - έλεγχος κλπ)
Συναδελφοι αρχικά καλή χρονιά (μια και γράφω για πρώτη φορά εφέτος)
νομίζω ότι την απάντηση πρέπει να την σώσουμε στα πλαίσια του μαθήματος μας και όχι θεωρητικά.
Στους διαγωνισμούς πληροφορικής (π.χ Ολυμπιάδα) δεν εξετάζουν τον κώδικα που έγραψε ο καθένας εξετάζουν μόνο τα αποτελέσματα σε μια δεδομένη είσοδο και μερικές φορές την ταχύτητα εμφανισης αυτών των αποτελεσμάτων. Στην περίπτωση αυτή είναι φανερό ότι ισοδύναμος αλγόριθμος ή πρόγραμμα είναι αυτό που βγάζει τα ίδια αποτελέσματα και πιθανά στον ίδιο (περίπου) χρόνο. Υπευθυμίζω άπο τα μαθηματικά ότι ισοδύναμες ονομάζονται δύο εξισώσεις όταν έχεουν τις ίδιες λύσεις (άσχετα που εγώ είχα απαντήσει ότι είναι αυτές που έχουν τις ίδιες δυνάμεις - και γέλαγε ο μαθηματικός στο Γυμνάσιο για ένα μήνα).
Στο σχολείο δεν κάνουμε αυτό άρα ισοδύναμοι είνια δύο αλγόριθμοι όχι όταν απλά βγάζουν το ίδιο αποτέλεσμα αλλά και με τον ίδιο τρόπο. Συνεπώς στις εξετάσεις κοιτάμε και τη μέθοδο και το αποτέλεσμα.
Βαγγέλης