Μετατροπή δομών επανάληψης

[gpapargi]

Η Όσο γίνεται πάντα σε μέχρις_ότου λόγω του ότι μια λογική παράσταση παίρνει μόνο 2 τιμές: Αληθής και Ψευδής. Ελέγχοντας αν ισχύει η συνθήκη σ ταυτόχρονα ελέγχεις και την όχι (σ). Είναι το ίδιο. Στη μετατροπή Όσο σε μέχρις_ότου και ανάποδα αντιστρέφοντας τη συνθήκη κάνεις τον ίδιο έλεγχο.

Όταν όμως αλλάζεις τον τελεστή ο έλεγχος είναι διαφορετικός. Δες για παράδειγμα το θέμα
https://alkisg.mysch.gr/steki/index.php?topic=1157.0

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

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

[ntzios kostas]

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

[gpapargi]

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

Αν μιλήσουμε για ίδια έξοδο και ίδια πολυπλοκότητα τότε πάμε σε άλλο ορισμό με ενδεχόμενο να έχουμε άλλα side effects.

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

[ntzios kostas]

Γιώργο το κοίταξα το Link και πράγματι δώσατε μεγάλη μάχη για να λύσετε μία άσκηση που μάλλον δεν προοριζόταν για μαθητές από καθηγητές. Δεν ξέρω πιο είναι το λάθος το για μαθητές ή το από καθηγητές .
Πράγματι η άσκηση έπρεπε να λέει για ακέραιους αριθμούς.

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

[gpapargi]

Πάντως για μένα αν θέλουμε να μιλάμε για μετατροπές μεταξύ δομών, είναι επιτακτική ανάγκη να δοθεί αυστηρός ορισμός.

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

Ούτε στην πολυπλοκότητα μπορούμε να στηριχτούμε. Πχ μπορούμε σε πίνακα 2 διαστάσεων να βρούμε το άθροισμα κάθε στήλης σαρώνοντας είτε κατά στήλη είτε κατά γραμμή (πχ σχολικό βιβλίο σελίδα 58). Οι αλγόριθμοι είναι τελείως διαφορετικοί αλλά καταλήγουν στο ίδιο αποτέλεσμα.

Για μένα η μόνη λύση που μπορεί να περπατήσει είναι ο τελείως περιοριστικός ορισμός «οι 2 κωδικοποιήσεις να κάνουν ακριβώς τα ίδια πράγματα και με ακριβώς την ίδια σειρά». Ουσιαστικά δηλαδή δε μιλάμε για μετατροπή αλγορίθμου (αφού αλγόριθμος είναι τα βήματα που κάνουμε) αλλά για μετατροπή κωδικοποίησης. Αν κάτσεις και εκτελέσεις τον αλγόριθμο με το χέρι θα κάνεις τις ίδιες ακριβώς ενέργειες. Αυτές τις ίδιες ενέργειες (που αποτελούν τον αλγόριθμο) θα πρέπει να μπορείς να τις εκφράσεις σε ψευδογλώσσα είτε με Όσο είτε με μέχρις_ότου. Δηλαδή διαχωρίζω σαφώς σαν έννοιες τον αλγόριθμο από την κωδικοποίηση του σε ψευδογλώσσα.

Αν το καλοσκεφτούμε… τι ακριβώς θα θέλαμε νε δούμε με τέτοιες ασκήσεις; Προφανώς το ότι μπορεί κάποιος να κάνει χρήση και άλλης εντολής αλλά τα πράγματα που γίνονται να είναι τα ίδια.

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

[ntzios kostas]

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

δηλαδή:

χ<- 100
όσο χ<100 επανάλαβε
γράψε χ
χ<-χ+1
τέλος_επανάληψης

και

χ<-100
αρχή_επανάληψης
   γράψε χ
   χ<-χ+1
μέχρις_ότου χ>=100

να μην τα θεωρήσουμε ισοδύναμα γιατί άμα τα εκτελέσω με το χέρι στο πρώτο κάνω πρώτα την σύγκριση και στο δεύτερο εμφανίζω το χ. ΄

Ούτε στην πολυπλοκότητα μπορούμε να στηριχτούμε. Πχ μπορούμε σε πίνακα 2 διαστάσεων να βρούμε το άθροισμα κάθε στήλης σαρώνοντας είτε κατά στήλη είτε κατά γραμμή (πχ σχολικό βιβλίο σελίδα 58). Οι αλγόριθμοι είναι τελείως διαφορετικοί αλλά καταλήγουν στο ίδιο αποτέλεσμα.

Προσωπικά τους δύο αλγόριθμους τους θεωρώ ισοδύναμους.

   

[gpapargi]

Στο πρώτο κομμάτι δε θα εκτελεστεί καμία φορά ο βρόχος. Στο δεύτερο θα εκτελεστεί 1 φορά. Προφανώς δεν είναι ισοδύναμα.

Αν αρχικοποιήσεις το χ με 1 αντί για 100 τότε όντως προκύπτει θέμα. (Ίσως αυτό να ήθελες να πεις και ξέφυγε.).

Σε αυτή την περίπτωση με βάση τον ορισμό μου οι 2 ψευδοκώδικες δεν είναι ισοδύναμοι γιατί ο ένας κάνει μια σύγκριση που δεν την κάνει ο άλλος. Για να είναι ισοδύναμοι θα πρέπει η μέχρις)ότου να μπει σε μια Αν χ<100. Τότε θα γίνονται τα ίδια πράγματα.

Δες την εξής άσκηση:
Να γραφτεί ο παρακάτω ψευδοκώδικας χρησιμοποιώντας την Όσο έτσι ώστε για κάθε είσοδο να παράγεται η ίδια έξοδος.

Διαβασε κ
ι ← 1
Αρχή_επανάληψης
  Εμφάνισε ι
  ι  ← ι+1
Μέχρις_ότου ι>κ

Θα δεις τι ακριβώς εννοώ.

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

[ntzios kostas]

X<-1 εννούσα (Με την πίεση του κουδουνιού την πάτησα  )

Μπορεί να είναι το σωστό αυτό που λες, βάζοντας το άν χ<=100 στην αρχή και προκύπτει μάλιστα από το γενικό σκεπτικό που έδωσα σε κάποιοα post  παραπάνω:

όσο συνθήκη επανάλαβε
     ομάδα εντολών
τέλος_επανάληψης

αυτό είναι ισοδύναμο με

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

αν συνθήκη τότε (που τη βγάλαμε εκτός επανάληψης)
  αρχή_επανάληψης
    οε
  μέχρις_ότου όχι(συνθήκη)
τέλος_αν

με αυτό δίνεται απάντηση και στο παράδειγμα που έδωσες.
Δεν μπορώ όμως να θεωρήσω ότι χαλάει η ισοδυναμία αν δεν βάλουμε την σύγκριση αν χ<=100 αν η συνθήκη της είναι σίγουρα αληθής.

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

Εννοείται δεν είναι θέμα προσωπικό, και βέβαια πρέπει όσο γίνεται όλα τα θέματα να είναι ξεκάθαρα από το βιβλίο. Αυτή η κουβέντα γίνεται, γιατί ελπίζω βοηθάει και τους δύο και όποιον άλλον τη διαβάζει, αφού το βιβλίο δεν έχει ορισμό του. Όμως αυτή τη στιγμή μετά από τόσα θέματα εξετάσεων που έχουν μπει στις πανελλήνιες και αφού τέτοιες μετατροπές και χειρότερες τις έχουμε δει ως θέματά τους, ως ισοδύναμα τμήματα έχω στο μυαλό μου αυτά που δίνουν το ίδιο αποτέλεσμα και έχουν την ίδια ή περίπου την ίδια πολυπλοκότητα . Μπορούμε όμως λίγο να αλλάξουμε την εκφώνηση του προβλήματος, βγάζοντας την λέξη ισοδύναμα ως εξής:
Να μετατραπεί το παρακάτω πρόγραμμα ώστε να χρησιμοποιεί την δομή επανάληψης για παράδειγμα την για αντί της όσο, ώστε να βγάζει τα ίδια αποτελέσματα για κάθε τιμή για παράδειγμα εισόδου. Την πολυπλοκότητα την βγάζουμε στην άκρη αφού δεν μας νοιάζει ο αριθμός των επαναλήψεων.
Ή να δοθεί η εκφώνηση:
Να μετατραπεί το παρακάτω πρόγραμμα ώστε να χρησιμοποιεί την δομή επανάληψης για παράδειγμα την για αντί της όσο, ώστε να βγάζει τα ίδια αποτελέσματα με τον ίδιο αριθμό επανάληψεων για κάθε τιμή για παράδειγμα εισόδου. Βάζουμε και λίγο την πολυπλοκότητα.

[gpapargi]

Μπορούμε όμως λίγο να αλλάξουμε την εκφώνηση του προβλήματος, βγάζοντας την λέξη ισοδύναμα ως εξής:
Να μετατραπεί το παρακάτω πρόγραμμα ώστε να χρησιμοποιεί την δομή επανάληψης για παράδειγμα την για αντί της όσο, ώστε να βγάζει τα ίδια αποτελέσματα για κάθε τιμή για παράδειγμα εισόδου. Την πολυπλοκότητα την βγάζουμε στην άκρη αφού δεν μας νοιάζει ο αριθμός των επαναλήψεων.
Ή να δοθεί η εκφώνηση:
Να μετατραπεί το παρακάτω πρόγραμμα ώστε να χρησιμοποιεί την δομή επανάληψης για παράδειγμα την για αντί της όσο, ώστε να βγάζει τα ίδια αποτελέσματα με τον ίδιο αριθμό επανάληψεων για κάθε τιμή για παράδειγμα εισόδου. Βάζουμε και λίγο την πολυπλοκότητα.

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

Οι παρακάτω 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 έχουν ίδια έξοδο, ίδια πολυπλοκότητα, ίδιο αριθμό βημάτων και ίδιο αποτέλεσμα. Όλα ίδια σε «μακροσκοπικό επίπεδο».
Άρα ένας ορισμός βασισμένος σε τέτοιες έννοιες (που δεν κατεβαίνει σε επίπεδο μεμονωμένης εντολής) θα  τους έδινε ισοδύναμους… πράγμα προφανώς λάθος.

Γι αυτό εγώ πιστεύω ότι πρέπει αναγκαστικά να μιλήσουμε για ίδιες ενέργειες και με την ίδια σειρά.

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

[ntzios kostas]

Πολύ καλό παράδειγμα.

Εσύ τι πιστεύεις ότι θα έκανες αν σου έκανε ένας μαθητής μία τέτοια μετατροπή; Πόσο θα έβαζες στα 10;

Πάντως αν η ερώτηση της άσκησης ήταν διατυπωμένη όπως σου είπα παραπάνω δεν νομίζω ότι υπάρχει κανένα πρόβλημα.

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

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

[Laertis]

Για το συγκεκριμένο θέμα 1Δ των επαναληπτικών του 2001 η εκφώνηση ήταν :

Δ. Δίνεται το παρακάτω τμήμα αλγορίθμου :

   Χ <-- Α
   Αρχή_επανάληψης
      Χ <-- Χ + 2
      Τύπωσε το Χ
   Μέχρις_ότου Χ>=Μ
   
α. Να δώσετε τη δομή επανάληψης «Για … από … μέχρι… βήμα» η οποία τυπώνει ακριβώς τις ίδιες τιμές με το πιο πάνω τμήμα αλγορίθμου

Στις επαναληπτικές τους 2008 το 1Ε ζητούσε ισοδύναμο αλγόριθμο απο Για σε Όσο και Μέχρις_ότου. Προφανώς η ισοδυναμία που ζητείται, αναφέρεται στην ίδια έξοδο όταν δοθούν τα ίδια δεδομένα πράγμα που μπορεί να υλοποιηθεί με διαφορετικούς τρόπους.
Ειλικρινά δε ξέρω αν αυτό υπόκειται -πάντα- σε κανόνες κι αν πρέπει να ψάξουμε να τους βρούμε (αν υπάρχουν) ...

[P.Tsiotakis]

Όπως γνωρίζουμε οι δομές Όσο και Μέχρις_ότου χρησιμοποιούνται για βρόχους που εκτελούνται για άγνωστο αριθμό επαναλήψεων. Όλοι οι βρόχοι μπορούν να υλοποιηθούν με κάποια απο τις δομές αυτές.
Συνεπώς, πάντα μπορεί κάποιος βρόχος να μετατραπεί απο τη μια στην άλλη.
Είναι προφανές οτι λόγω των διαφορετικών ιδιοτήτων τους η κωδικοποίηση δε θα είναι η ίδια.
Ομοίως για τα ζευγάρια Όσο-Για και Μέχρις_ότου-Για.

Το μόνο σίγουρο για αξιολόγηση (=βαθμολόγηση) τέτοιων μετατροπών είναι η ίδια έξοδος των δυο βρόχων (για ίδια είσοδο). Σίγουρο από την άποψη οτι είναι μετρήσιμο και μπορεί να αξιολογηθεί ακόμη και για διαφορετικές κωδικοποιήσεις...
Άλλωστε και στη ΔΤ4 στη σελίδα 79 του τετραδίου μαθητή η διατύπωση είναι όπως το θέμα 1Ε του 2008, που προανέφερε ο σοφός Λαέρτης.

[alkisg]

Για ισοδύναμο κώδικα, εξαρτάται σε τι επίπεδο μιλάμε.
Π.χ. οι εντολές
α <- "Κειμενάκι"
β <- 1

και οι αντιστραμμένες εντολές
β <- 1
α <- "Κειμενάκι"

σε επίπεδο άγριου optimization (π.χ. διαδικασίες assembly που καλούνται χιλιάδες φορές σε κάποιο πρόγραμμα) δεν θεωρούνται ισοδύναμες. Αυτοί που γράφουν τέτοιο κώδικα assembly μετράνε μέχρι και το cache line του επεξεργαστή για να δουν πώς θα γλυτώσουν 1-2 κύκλους CPU.

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

Εγώ στον "ορισμό" για ισοδύναμους αλγορίθμους θα πρόσθετα τουλάχιστον τον περιορισμό να έχουν την ίδια πολυπλοκότητα (δηλαδή αν ο ένας κώδικας κάνει N επαναλήψεις, ο άλλος να μην κάνει Ν^2), αλλά είναι λίγο δύσκολο θέμα με την τρέχουσα ύλη που δεν περιλαμβάνει το κεφάλαιο με την πολυπλοκότητα...

[gpapargi]

Θα προσπαθήσω να εξηγήσω πως τα έχω στο κεφάλι μου.

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

Ξαναλέω: για μένα άλλο αλγόριθμος και άλλο κωδικοποίηση σε ψευδογλώσσα.

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

Εδώ όμως μιλάμε για κωδικοποίηση και όχι για αλγόριθμο. Θέλουμε δηλαδή τον ίδιο ακριβώς αλγόριθμο (δηλαδή τις ίδιες ακριβώς ενέργειες) να τις κωδικοποιήσουμε  άλλη εντολή πχ με Μέχρις_ότου αντί για Όσο. Για σκεφτείτε λίγο… τι ακριβώς θέλουν να ελέγξουν οι ασκήσεις αυτού του είδους;

Για μένα λοιπόν δεν έχει νόημα να συζητάμε για ισοδυναμίες αλγορίθμων γιατί ξεφεύγουμε.

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

Για μένα το ουσιώδες θέμα είναι το να αποσαφηνιστεί αν μιλάμε για «ισοδυναμίες» αλγορίθμων ή κωδικοποιήσεων. Εγώ λέω το καθαρά δεύτερο: ίδιος αλγόριθμος, άλλη εντολή. 

edit: ʼλκη νομίζω πως δεν πρέπει να μας απασχολήσει το θέμα της υλοποίησης σε χαμηλό επίπεδο. Μπορεί η Όσο και Μέχρις_ότου μέσα σε Αν να δίνουν διαφορετικό δυαδικό κώδικα τελικά αλλά σαν ενέργειες που κάνει αυτός που εκτελεί τον αλγόριθμο είναι το ίδιο (έλεγχος - εντολές βρόχου - έλεγχος κλπ)   

[Vangelis]

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

Βαγγέλης