Aτέρμων βρόχος

[johnny_xp]

Γεια σας. Θα ήθελα να θέσω μια ερώτηση σχετικά με την έννοια του ατέρμων βρόχου.
Συγκεκριμένα, θεωρούμε τις επόμενες δυο περιπτώσεις:

ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
     ΔΙΑΒΑΣΕ x
ΜΕΧΡΙΣ_ΟΤΟΥ x>0

ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10 ΜΕ_ΒΗΜΑ 0
     ΔΙΑΒΑΣΕ x
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Η ερώτηση είναι πολύ απλή: ποιος από τους δυο παραπάνω βρόχους είναι ατέρμων;

[petrosp13]

Η πρώτη επανάληψη θα τερματίσει όταν δοθεί ως είσοδος τιμή <=0

Η δεύτερη επανάληψη, αν μετατραπεί σε δομή "Όσο" θα γίνει κάπως έτσι:
ι<--1
ΟΣΟ (ι<=10) ΕΠΑΝΑΛΑΒΕ
      ΔΙΑΒΑΣΕ χ
      ι<--ι+0
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Οπότε, η μεταβλητή ι δεν αλλάζει τιμή μέσα στην επανάληψη και ο βρόγχος δεν τερματίζεται

Υ.Γ. Έχω κάποιους ενδοιασμούς για το κατά πόσο σωστή είναι η συνθήκη του "Όσο", αφού αυτή εξαρτάται από το αν το βήμα είναι θετικό ή αρνητικό

[P.Tsiotakis]

Ο πρώτος βρόχος (Μέχρις_ότου) δεν είναι ατέρμων αφού η μεταβλητή που συμμετέχει στη συνθήκη (x) ΤΡΟΠΟΠΟΙΕΙΤΑΙ εντός του βρόχου

Ο δεύτερος είναι ατέρμων αφού η μεταβλητή που συμμετέχει στη συνθήκη (i) ΔΕΝ ΤΡΟΠΟΠΟΙΕΙΤΑΙ εντός του βρόχου (καλό το σχόλιο για το πρόσημο του βήματος  )



Με εκτίμηση,

Τσιωτάκης Παναγιώτης

[alkisg]

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

Εννοείται ότι με βάση το βιβλίο δεν έχει καθοριστεί κάτι τέτοιο, ούτε καν έχει καθοριστεί το πώς (και αν) μεταφράζεται σε Όσο...

[novulus]

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

χ<--1
Αρχή_επανάληψης
     χ <-- χ+2
Μέχρις_ότου(χ=10)

Το χ μεταβάλλεται εντός του βρόχου αλλα δεν παίρνει ποτέ την τιμή 10...

[P.Tsiotakis]

Σαφώς, καμμία αντίρρηση για το τελευταίο  novulus

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

Θα μπορούσες πιο απλά να γράψεις:
χ<--1
Αρχή_επανάληψης
     χ <-- χ +2
Μέχρις_ότου (χ <= 1)

[johnny_xp]

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

for(;;){}

είναι ατέρμων, αλλά είναι έγκυρος.

Προφανώς ο βρόχος ΓΙΑ που έδωσα είναι ατέρμων. Στον βρόχο ΜΕΧΡΙΣ_ΟΤΟΥ αν επάπειρων δίνω ένα x<=0 τότε πότε θα τερματισθεί;

[alkisg]

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

Π.χ. ο g77 της fortran βγάζει τέτοιο μήνυμα (Iterative DO loop step count known to be 0 (zero) at (^)):

io@~/public_html/tosteki #cat for.f
        integer i
        do i=1,10,0
          print *, 'i='
        enddo
        end
io@~/public_html/tosteki #g77 for.f
for.f: In program `MAIN__':
for.f:2:
           do i=1,10,0
                     ^
Iterative DO loop step count known to be 0 (zero) at (^)

Επίσης η kidbasic τρέχει μία μόνο φορά το loop (δηλαδή δε μεταφράζει την ΓΙΑ σε ΟΣΟ, αλλά σε ΜΕΧΡΙΣ_ΟΤΟΥ).

Δεν είναι το θέμα τι κάνουν οι διάφορες γλώσσες, το θέμα είναι ότι δεν έχει νόημα να υποθέτουμε (όλα γίνονται ), αλλά να βγάζουμε συμπεράσματα με βάση το βιβλίο...

[johnny_xp]

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

• 
  Η υλοποίηση της Lahey επιτρέπει τη χρήση μηδενικού βήματος (http://www.lahey.com/docs/lfenthelp/hh_start.htm)
  
• 
  Στην υλοποίηση της Intel δεν επιτρέπεται η χρήση μηδενικού βήματος (ftp://download.intel.com/support/performancetools/fortran/windows/v9/ifort_doc.zip).
  
• 
  Στην υλοποίηηση της NAGWare f95 ο compiler επιτρέπει ή όχι τη χρήση μηδενικού βήματος, ανάλογα με τις ρυθμισεις που έχουν επιβληθεί (http://www.nag.co.uk/nagware/np/r51_doc/f95.html)
  

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

[petrosp13]

Προφανώς ο βρόχος ΓΙΑ που έδωσα είναι ατέρμων. Στον βρόχο ΜΕΧΡΙΣ_ΟΤΟΥ αν επάπειρων δίνω ένα x<=0 τότε πότε θα τερματισθεί;

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

Δίνω το παράδειγμα ενός server που χρησιμοποιεί μια δομή

while (true)
{...}

για να δέχεται συνεχώς κλήσεις TCP/IP από clients, το οποίο προφανώς είναι ατέρμων βρόχος, αλλά προγραμματιστικά είναι ορθός, αφού σχεδιάστηκε ορθά να μην ολοκληρώνεται ποτέ

[johnny_xp]

petrosp_13, είσαι στη σωστή, κατά την άποψη μου, κατεύθυνση. Ήδη αυτό που λες είναι η μισή απάντηση και φυσικά συμφωνώ μαζί σου.

[gpapargi]

Δεν είμαι σίγουρος ότι έχω καταλάβει ποιο ακριβώς είναι το ερώτημα. Ζητάμε κάποιον αυστηρό ορισμό του ατέρμων βρόχου; Ή ζητάμε αν το να μην τερματίζει κάτι είναι μια περίπτωση κατ’ ανάγκη προβληματική;

Στο δεύτερο θα έλεγα ότι υπάρχουν οι mail servers και άλλες εφαρμογές που δεν τερματίζουν ποτέ και είναι σε listening mode. Αλλοίμονο αν τερμάτιζαν. Επίσημα η τήρηση του κριτηρίου της περατότητας είναι η διαφορά μεταξύ αλγορίθμου και προγράμματος.

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

Αν δεχτούμε ότι η «Για» μετατρέπεται σε «Όσο» (αν και είναι κάπως αυθαίρετο) προκύπτει το ζήτημα του πως θα γίνει η συνθήκη της «Όσο» στην περίπτωση που το βήμα είναι 0. Θα έλεγα πιο «λογικό» είναι το να γίνει ι<> 10 αφού σε άλλη περίπτωση θα έδειχνε κάποια προτίμηση προς κάποια κατεύθυνση.

[johnny_xp]

Σε προγραμματιστικό επίπεδο ένας ατέρμων βρόχος είναι εργαλείο στα χέρια του προγραμματιστή και μπορεί να το χρησιμοποιήσει για να αντιμετωπίσει συγκεκριμένες καταστάσεις, όπως αυτές που ανέφεραν οι φίλοι, παραπάνω. Άλλωστε ο βρόχος μηνυμάτων των Windows είναι κατά συνθήκη ατέρμων ή όχι. Πράγματι, αν ο χρήστης δεν κλήσει ποτέ ένα παράθυρο των Windows ο βρόχος μηνυμάτων θα εκτελείτα επ΄ άπειρων.

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

ʼποψη μου είναι ότι υπάρχουν βρόχοι οι οποίοι είναι a priori ατέρμωνοι (προφανώς λόγο εσφαλμένου προγραμματισμού). Θεωρητικά, ένας τέτοιος βρόχος είναι ο ΓΙΑ που έδωσα στην αρχή της συζήτησης. Υπάχρουν όμως και βρόχοι οι οποίο μπορεί κατά περίπτωση να είναι ή όχι ατέρμωνοι. Μια τέτοια περίπτωση είναι ο βρόχος ΜΕΧΡΙΣ_ΟΤΟΥ που έδωσα.

Ένα από τα πολλά ερωτήματα που μπορούν να προκύψουν από αυτή τη συζήτηση είναι και το εξής: αν δωθεί ένας τέτοιος βρόχος, όπως ο ΜΕΧΡΙΣ_ΟΤΟΥ που έδωσα, στις Εξετάσεις και τεθεί το ερώτημα αν παριστάνει αλγόριθμο, ποιά είναι η απάντηση; Σημειώνω δε, ότι διδάσκουμε τους μαθητές να χρησιμοποιούν τέτοιους βρόχους σε περιπτώσεις ελέγχου δεδομένων εισόδου.

[P.Tsiotakis]

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

Ο πρώτος βρόχος (Μέχρις_ότου) δεν είναι ατέρμων αφού η μεταβλητή που συμμετέχει στη συνθήκη (x) ΤΡΟΠΟΠΟΙΕΙΤΑΙ εντός του βρόχου

[alkisg]

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

Μια διαδικασία που δεν τελειώνει μετά από συγκεκριμένο αριθμό βημάτων δεν αποτελεί αλγόριθμο, αλλά λέγεται απλά υπολογιστική διαδικασία (computational procedure).

Με βάση τα παραπάνω, ο έλεγχος δεδομένων από το χρήστη δεν είναι αλγόριθμος! 
Και δεν το συζητάμε καν για web servers και ατέρμονες βρόχους...
Δε λέω ότι μου αρέσουν αυτοί οι ορισμοί, αλλά μπορούμε να υποστηρίξουμε κάτι διαφορετικό στα πλαίσια της ύλης;

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

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

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