Ισοδυναμία ψευδογλώσσας και διαγράμματος ροής

[vtsakan]

Πρόταση 1: Ένα διάγραμμα ροής ισοδυναμεί με έναν αλγόριθμο σε ψευδογλώσσα.
Πρόταση 2: Ένας αλγόριθμος σε ψευδογλώσσα αντιστοιχεί σε ένα διάγραμμα ροής.

ΣΩΣΤΟ Η ΛΑΘΟΣ;

Η πρόταση 1 είναι λάθος, και έχω βρεί αρκετά αντιπαραδείγματα.
Η πρόταση 2 πιστεύω πως είναι λάθος, αλλά δεν έχω βρει ακόμα αντιπαράδειγμα.

Καμιά ιδέα;

[gpapargi]

Επιτρέπεται η goto;

[vtsakan]

Όχι. Στον δομημένο προγραμματισμό...

[gpapargi]

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

[vtsakan]

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

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

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

Πρόταση 2: Ένας αλγόριθμος σε ψευδογλώσσα αντιστοιχεί σε ένα διάγραμμα ροής.

Μια εντολή Αρχή_επανάληψης... μέχρις_ότου σε ψευδογλώσσα, δεν θα μπορούσε να απεικονιστεί με 2 διαφορετικά διαγράμματα ροής;

[gpapargi]

Φαίνεται να καταλάβαμε με διαφορετικό τρόπο τα 2 ΣΛ. Όταν λέμε ότι ένα ΔΡ ισοδυναμεί με έναν ψευδοκώδικα εννοούμε ακριβώς έναν (και όχι δεύτερο) ή τουλάχιστον έναν δηλαδή ότι υπάρχει κάποιος ισοδύναμος ψευδοκώδικας.

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

[vtsakan]

Έχετε δίκιο.
Ας το δουμε λίγο πιο αναλυτικά.

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

Ας περιγράψω ένα παράδειγμα για την πρόταση 1 για να γίνω πιο κατανοητός:
Έστω το διάγραμμα ροής του attached αρχείου.
Τότε μπορώ να φτιάξω 2 αλγορίθμους που αντιστοιχούν στο ίδιο διάγραμμα ροής.

Αλγόριθμος 1:

ΑΛΓΟΡΙΘΜΟΣ ΔΙΑΓΡΑΜΜΑ1

  ΔΙΑΒΑΣΕ α
  ΑΝ (α > 0) ΤΟΤΕ
    ΓΡΑΨΕ α
  ΑΛΛΙΩΣ_ΑΝ (α < 0) ΤΟΤΕ
    ΓΡΑΨΕ -α
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ ΔΙΑΓΡΑΜΜΑ1         

Αλγόριθμος 2:

ΑΛΓΟΡΙΘΜΟΣ ΔΙΑΓΡΑΜΜΑ1

  ΔΙΑΒΑΣΕ α
  ΑΝ (α > 0) ΤΟΤΕ
    ΓΡΑΨΕ α
  ΑΛΛΙΩΣ
      ΑΝ (α < 0) ΤΟΤΕ
          ΓΡΑΨΕ -α
     ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ ΔΙΑΓΡΑΜΜΑ1         

Συνεπώς η πρόταση 1 είναι Λάθος.

Τι γίνεται με την αντίστροφη πρόταση, δηλαδή την πρόταση 2;

Ελπίζω να εξήγησα καλύτερα τον προβληματισμό μου.

[vtsakan]

Μια εντολή Αρχή_επανάληψης... μέχρις_ότου σε ψευδογλώσσα, δεν θα μπορούσε να απεικονιστεί με 2 διαφορετικά διαγράμματα ροής;

Πώς; Αλλάζοντας την συνθήκη με την συζυγή της;

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

Πώς; Αλλάζοντας την συνθήκη με την συζυγή της;

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

Το παρακάτω:

Αρχή_επανάληψης
   <εντολές>
Μέχρις_ότου <συνθήκη>

... ξέρουμε πώς απεικονίζεται (συνήθως) σε διάγραμμα ροής! (αυτός ας πούμε είναι ο 1ος τρόπος!)

Όμως δεν ισοδυναμεί με το εξής;

<εντολές>
Όσο όχι <συνθήκη> επανάλαβε
   <εντολές>
Τέλος_επανάληψης

... το οποίο, επίσης, ξέρουμε πώς απεικονίζεται (συνήθως) σε διάγραμμα ροής! (αυτός ας πούμε είναι ο 2ος τρόπος!)
Όσο για τη συνθήκη, για να μη χρειαστεί να την "πειράξουμε", δεν θα μπορούσαμε να την αφήσουμε όπως ήταν αρχικά, και να αντιστρέψουμε τα Αληθής - Ψευδής στις δύο εξόδους της συνθήκης (ρόμβου) της Όσο... ;;

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

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

Φαίνεται να καταλάβαμε με διαφορετικό τρόπο τα 2 ΣΛ. Όταν λέμε ότι ένα ΔΡ ισοδυναμεί με έναν ψευδοκώδικα εννοούμε ακριβώς έναν (και όχι δεύτερο) ή τουλάχιστον έναν δηλαδή ότι υπάρχει κάποιος ισοδύναμος ψευδοκώδικας.

Όντως δεν είναι σαφές τι από τα δύο εννοεί, αν και εγώ υπέθεσα τελικά την 1η εκδοχή...!

[gpapargi]

Το παρακάτω:

Αρχή_επανάληψης
   <εντολές>
Μέχρις_ότου <συνθήκη>

... ξέρουμε πώς απεικονίζεται (συνήθως) σε διάγραμμα ροής! (αυτός ας πούμε είναι ο 1ος τρόπος!)

Όμως δεν ισοδυναμεί με το εξής;

<εντολές>
Όσο όχι <συνθήκη> επανάλαβε
   <εντολές>
Τέλος_επανάληψης

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

Αυτοί οι 2 είναι τελικά διαφορετικοί κώδικες και άρα λογικά αντιστοιχούν σε διαφορετικά ΔΡ. Δε μας χαλάει κάτι.

Όσο για τη συνθήκη, για να μη χρειαστεί να την "πειράξουμε", δεν θα μπορούσαμε να την αφήσουμε όπως ήταν αρχικά, και να αντιστρέψουμε τα Αληθής - Ψευδής στις δύο εξόδους της συνθήκης (ρόμβου) της Όσο... ;;

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

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

[gpapargi]

Έχετε δίκιο.
Ας το δουμε λίγο πιο αναλυτικά.

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

Ας περιγράψω ένα παράδειγμα για την πρόταση 1 για να γίνω πιο κατανοητός:
Έστω το διάγραμμα ροής του attached αρχείου.
Τότε μπορώ να φτιάξω 2 αλγορίθμους που αντιστοιχούν στο ίδιο διάγραμμα ροής.

Αλγόριθμος 1:

ΑΛΓΟΡΙΘΜΟΣ ΔΙΑΓΡΑΜΜΑ1

  ΔΙΑΒΑΣΕ α
  ΑΝ (α > 0) ΤΟΤΕ
    ΓΡΑΨΕ α
  ΑΛΛΙΩΣ_ΑΝ (α < 0) ΤΟΤΕ
    ΓΡΑΨΕ -α
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ ΔΙΑΓΡΑΜΜΑ1         

Αλγόριθμος 2:

ΑΛΓΟΡΙΘΜΟΣ ΔΙΑΓΡΑΜΜΑ1

  ΔΙΑΒΑΣΕ α
  ΑΝ (α > 0) ΤΟΤΕ
    ΓΡΑΨΕ α
  ΑΛΛΙΩΣ
      ΑΝ (α < 0) ΤΟΤΕ
          ΓΡΑΨΕ -α
     ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ ΔΙΑΓΡΑΜΜΑ1         

Συνεπώς η πρόταση 1 είναι Λάθος.

Τι γίνεται με την αντίστροφη πρόταση, δηλαδή την πρόταση 2;

Ελπίζω να εξήγησα καλύτερα τον προβληματισμό μου.

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

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

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

Εγώ εδώ διαφωνώ! Το ΔΡ θεωρώ ότι είναι τελείως διαφορετικός τρόπος απεικόνισης του αλγορίθμου, χωρίς να υπάρχει λόγος για σχέση 1 προς 1 με την ψευδογλώσσα του βιβλίου. Άλλωστε το ΔΡ προϋπήρχε της ψευδογλώσσας αυτής. Επίσης υπάρχουν γλώσσες χωρίς πολλαπλή Αν, όπως η pascal και η C, όπου οι πολλαπλές Αν στην πραγματικότητα είναι εμφωλευμένες... Για αυτό άλλωστε πρότεινα παραπάνω τους 2 διαφορετικούς τρόπους μετατροπής της Αρχής_επανάληψης... μέχρις_ότου σε ΔΡ. Μάλιστα στους μαθητές προτείνω να θεωρούν ότι το ΔΡ είναι φτιαγμένο από λάστιχο και άρα μπορούν να το τραβούν και  να το τεντώνουν από όποια μεριά θέλουν, αρκεί να μην κοπούν οι συνδέσεις!

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

[gpapargi]

Υποχρεωτικό σίγουρα δεν μπορεί να είναι αφού υπάρχει και η σελίδα 38 του βιβλίου.
Γενικά όμως έχω να πω το εξής:
Ο βασικός λόγος που το ΔΡ θεωρείται ξεπερασμένο είναι το ότι μπορεί να δώσει διάγραμμα που δεν μπορεί να γίνει στη συνέχεια κώδικας. Πχ αν τραβήξεις μια γραμμή τυχαία μπορεί να δίνει μια βολική λύση στο ΔΡ, αλλά όταν πας να το κάνεις κώδικα θα πρέπει να χρησιμοποιήσεις goto. Αφού η goto θεωρείται μαύρο πρόβατο, υπάρχει πρόβλημα και με το διάγραμμα.
Η γνώμη μου είναι ότι όσο περισσότερο απομακρύνεται το ΔΡ από τον ψευδοκώδικα, τόσο το χειρότερο για το ΔΡ... θα πέφτει όλο και σε μεγαλύτερη δυσμένεια.
Για μένα είναι εντελώς ατυχές το ότι το χρησιμοποιούμε. Οφείλεται στο ότι παλιά όταν ξεκίνησε το μάθημα οι θεματοδότες δεν κατάλαβαν αυτό που λένε τα βιβλία μαθητή και καθηγητή ότι το ΔΡ είναι ξεπερασμένο, αναφέρεται για ιστορικούς λόγους και ότι πρέπει να μη στεκόμαστε αλλά να αναφέρουμε απλώς τα βασικά. Δεν το κατάλαβαν και το έβαλαν στις εξετάσεις. Η συνέχεια είναι γνωστή: όσοι διδάσκουν ΣΟΣ του έδιναν έμφαση και όσοι εξετάζουν ΣΟΣ το προτιμούσαν στις εξετάσεις. Έτσι ένα πεθαμένο θέμα ζωντάνεψε κακώς.
Προσωπικά θεωρώ λάθος το να σκέφτεται κανείς απευθείας σε ΔΡ. Άντε να κάνουμε καμιά μετατροπή επειδή πέφτει στις εξετάσεις. Αλλά μέχρι εκεί. Και σε αυτές προσπαθώ να μετριάσω τη ζημιά προτιμώντας απεικονίσεις που έρχονται σε ένα προς ένα σχέση με τον ψευδοκώδικα. Μακάρι να μην υπήρχε καθόλου.