Παραβίαση Αλγοριθμικών Κριτηρίων

Ξεκίνησε από redhata, 01 Νοε 2004, 11:29:46 ΜΜ

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

redhata

Όσον αφορά την παραβίαση των κριτηρίων καθοριστικότητας και περατότητας τα έχουμε δει ως θέματα σε πανελλαδικές.
Ο παρακάτω αλγόριθμος:

Αλγόριθμος noexit
 Διάβασε a,b
 c<-a+b
Τέλος noexit

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

P.Tsiotakis

Συμφωνώ μα την παραπάνω τοποθέτηση, μάλιστα πιστεύω οτι πρέπει συνεχώς να υπενθυμίζουμε στα παιδιά τα 5 κριτήρια και την ικανοποίησή τους
 
Το κριτήριο της αποτελεσματικότητας θέλει καθε 1 εντολή να είναι απλή, χρησιμοποιώ το παρακάτω αλγόριθμο και τους ζητώ να τον εκτελέσουν
 
Αλγόριθμος noexit  
 Διάβασε a, b  
 c <- a @ b  
 Εμφάνισε c
Τέλος noexit  
 
Τα παιδιά δεν ξέρουν καμία πράξη που να ορίζεται με το σύμβολο @
 
Άλλο παράδειγμα που χρησιμοποιώ είναι η εντολή εκχώρησης:
 
c <- ρίζα ((c * (a+b)) ^a / ((b-c)^a)) + ((c-a)^b)^(1/c) - c*b
 
Η οποία είναι εκτελέσιμη (αν και μπορεί να παραβιάζει το κριτήριο της καθοριστικότητας) αλλά μάλλον πρέπει να "σπάσει" σε πιο απλά τμήματα, γιατί η ζωή πρέπει να είναι απλή, το ίδιο και οι εντολές ενός αλγορίθμου
 
Με εκτίμηση,

redhata

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

Αλγόριθμος noinput
 c <- a+b
 Εμφάνισε c
Τέλος noinput

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

rEdHaTa

P.Tsiotakis


Απο τη στιγμή που δεν υπάρχει είσοδος και παραβιάζεται το -βασικό- κριτήριο της
εισόδου για ποιον αλγόριθμο συζητάμε?


xaidi

(συγνώμη για την παρέμβαση).....c <- a @ b  έχω την αίσθηση ότι αυτή η εντολή δεν είναι ορθό παράδειγμα για το κριτήριο της αποτελεσματικότητας διότι αυτό παραπέμπει σε τελεστή που δεν υπάρχει δηλαδή σε λάθος χρησιμοποίηση.
Μια σκέψη μου όμως και ερώτηση είναι η εξής, μια που το θίξατε! το κριτήριο αυτό παραπέμπει σε σπάσιμο των εντολών όπως και το παράδειγμα που έγραψε ο Παναγιώτης. Ο αλγόριθμος όμως πρέπει να είναι όσο το δυνατό δεμένος και μικρός γρήγορος με όχι περιττές μεταβλητές και κλπ άρα αν σπάσω σε τόσες εντολές τη σχέση με επιπλέον μεταβλητές μήπως τελικά χάνω αλλού το νόημα του "προγραμματίζω"?
Ευχαριστώ,

gpapargi

Καλημέρα

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

Το θέμα είναι τι εννοεί εδώ ο συγγραφέας.

Με βάση τον «ορισμό» που δίνει και τα παραδείγματα που γράφει καταλαβαίνω ότι θέλει να πει τα εξής: Οι εντολές πρέπει να είναι εκτελέσιμες δηλαδή να αντιστοιχούν σε εντολές που εκτελούνται. Πχ αν έχεις ένα πίνακα αριθμών δεν μπορείς να πεις σε ένα αλγοριθμο
«Βρες ποια στοιχεία του πίνακα είναι ίσα με 5»
γιατί δεν υπάρχει τέτοια εντολή στη ΓΛΩΣΣΑ.
Επίσης δεν μπορείς να πεις «Βρες τον μεγαλύτερο από τα στοιχεία του πίνακα» ή «βρες το μέσο όρο».
Σε όλα αυτά τα παραδείγματα δεν υπάρχουν αντίστοιχες (μια καθε φορά) εντολές από πίσω. Αυτό είναι που λέμε ότι πρέπει να είναι «απλες» οι εντολές και «εκτελέσιμες». Πρέπει δηλαδή όταν μεταφερθούν σε κάποια γλώσσα να τρέχουν όπως είναι. Σε κάθε ένα από τα παραπάνω παραδείγματα θέλει σύνολο από εντολές και όχι μόνο μία.

Βέβαια αν γράφεις σε sql οι παραπάνω εντολές είναι απλές και εκτελέσιμες λόγω του ανώτερου επιπέδου της γλώσσας sql. Σε αυτή την περίπτωση είναι νόμιμη  εντολή το «βρες το μεγαλύτερο» γιατί μπορείς να γράψεις
Select max(στήλη) from πίνακας

Αν αυτά που λέω είναι σωστά τότε τα παραπάνω που αναφέρω είναι κλασσικά παραδείγματα.

Η αλήθεια είναι ότι σχολιάζω μια λίγο διαφορετική έννοια της «αποτελεσματικότητας» από αυτή που σχολιάζει ο Παναγιώτης. Το @ θα οδηγήσει σε συντακτικό λάθος και άρα έχουμε επίσης μη εκτελέσιμο κώδικα.
Εγω εκτός από το «εκτελέσιμο» στάθηκα λίγο και στο «απλό».

Τώρα στο θέμα της εισόδου τα πράγματα έχουν φοβάμαι και άλλες πτυχές.
Προσέξτε ένα πρόγραμμα που έφτιαξα κάποτε:
Είχαμε μια εφαρμογή που την αποτελούσαν πολλά processes, ας πούμε πολλά προγράμματα. Αν κάποιο από αυτά έπαυε να τρέχει η εφαρμογή δε λειτουργούσε. Οπότε έκανα το εξής: Έφτιαξα ένα πρόγραμμα που έλεγχε κάθε 5 λεπτά αν τρέχουν τα συγκεκριμένα προγράμματα. Αν έτρεχαν δεν έκανε τίποτα. Αν κάποιο έλειπε το επανεκκινούσε. Το πρόγραμμά μου δεν έδινε τίποτα στο χρήστη ούτε έπαιρνε κάποια είσοδο. Έκανε απλώς μια δουλειά. Ξεκίναγε αυτόματα από το crontab  του Unix.
Εδώ το πρόγραμμα δεν έπαιρνε κάποια είσοδο από το χρήστη. Καλούσε μια εντολή για να δει τι τρέχει στο συγκεκριμένο υπολογιστή και έπαιρνε την έξοδό της. Αυτό ας πούμε ότι είναι μια είσοδος. Το πρόγραμμα όμως δεν έβγαζε κάποια έξοδο. Αυτό που έκανε ήταν μερικές φορές (όχι πάντα) να ξεκινάει ένα πρόγραμμα.
Νομίζω ότι αυτό που θέλει να πει το βιβλίο είναι ότι ο αλγόριθμος πρέπει να επικοινωνεί με το περιβάλλον και προς τις 2 κατευθύνσεις. Δηλαδή και να δίνει και να παίρνει από αυτό.

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

pfan

#6
Γεια χαρά σε όλους
Θα ήθελα να προσθέσω και εγώ κάποιες σκέψεις για το θέμα της εισόδου.

Στον αλγόριθμο

Αλγόριθμος noinput
 c <- a+b
 Εμφάνισε c
Τέλος noinput
 
το βασικό πρόβλημά του είναι η εντολή ανάθεσης c<-a+b που έχει στο δεξί μέρος της μια αριθμητική έκφραση και οι μεταβλητές που μετέχουν σε αυτή θα πρέπει να είναι ορισμένες (βιβλίο μαθητή σελ 154 πάνω). Βέβαια στις περισσότερες γλώσσες προγραμματισμού οι μεταβλητές α και b θα έχουν την τιμή 0 και το πρόγραμμα θα εκτελεστεί μια χαρά.

Έστω ότι έχουμε τον παρακάτω αλγόριθμο:
Αλγόριθμος no_external_input
 a<- 3
 b<- 4
 c <- a+b
 Εμφάνισε c
Τέλος no_external_input

Τώρα ο παραπάνω αλγόριθμος παραβιάζει το κριτήριο της εισόδου; Για μένα όχι γιατί στο σχολικό βιβλίο αναφέρετε ότι ένας αλγόριθμος μπορεί να έχει και καμία είσοδο (σελ 25 κάτω) (Εκεί επίσης αναφέρει και για τις γεννήτριες ψευδοτυχαίων αριθμών. Ένα φιλοσοφικό ερώτημα: Άραγε ο μαθητής πόσα μαθήματα αργότερα θα μπορέσει να καταλάβει αυτές τις γραμμές του βιβλίου)

επίσης ο αλγόριθμος:
Αλγόριθμος hello
Εμφάνισε 'hello word'
Τέλος hello

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

P.Tsiotakis

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

Στα μαθηματικά έχω την δυνατότητα να ορίζω τελεστές. Ορίζω λοιπόν οτι a @ b = ο μικρότερος τέλειος αριθμός μεταξύ των αριθμών a και b υψωμένος εις την a

Στον αλγόριθμο δεν μπορώ να χρησιμοποιήσω αυτήν την πράξη.
Στον αλγόριθμο πολλαπλασιασμός αλα ρωσικά πάντως, χρησιμοποιείται (κυριολεκτικά στο άσχετο) ο τελεστής [] αντί του div. Μπορεί ο καθένας να ορίσει νέο τελεστή στα πλαίσια ενός αλγορίθμου?

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

Μπορώ να χρησιμοποιήσω 500 μεταβλητές
Μπορώ να χρησιμποιήσω 500 περιττές εντολές
Τι σημαίνει γρήγορος στο χαρτί?
Τι σημαίνει προγραμματίζω στην Γ Λυκείου - Τεχνολογική Κατεύθυνση

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

Για την εύρεση των δεκάδων σε έναν τετραψήφιο αριθμό, υπάρχει κανείς καθηγητής που προτείνει τον τρόπο:

δεκάδες <- ((αριθμός mod 1000) mod 100) div 10      (Ελπίζω να το έγραψα σωστά...)

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

Με εκτίμηση,

gpapargi

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

Στο προηγούμενο post μου έδωσα και ένα παράδειγμα προγράμματος που δεν έχει έξοδο. Θέλω να πω ότι τα κριτήρια εισόδου-εξόδου δεν είναι και πολύ καλά ορισμένα. Ειλικρινά δεν ξέρω αν έχει νόημα η κουβέντα.
 ???

P.Tsiotakis

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

Προσωπικά δεν έχω κατάλάβει τι νόημα έχει η συζήτηση για Unix processes, startup scripts, hello world κ.λ.π. στο συγκεκριμένο forum, στο συγκεκριμένο θέμα

Ο αλγόριθμος :

Αλγόριθμος hello
μήνυμα <-  "hello word"
Εμφάνισε  μήνυμα
Τέλος hello

Έχει είσοδο, έτσι δεν είναι;

Με εκτίμηση

xaidi

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

gpapargi

Καλημέρα

Παναγιώτη η συζήτηση για Unix processes και startup scripts έχει το νόημα του να δώσει ένα παράδειγμα αλγορίθμου που δεν έχει είσοδο ή έξοδο. Θέλω να πω ότι αυτά που λέει το βιβλίο δεν είναι αυστηρά (με τη μαθηματική έννοια). Δηλαδή λέει ότι ο αλγόριθμος έχει πάντα έξοδο αλλά εγώ δίνω παράδειγμα αλγορίθμου που δεν έχει έξοδο.
Ουσιαστικά κάνουμε και μια κριτική στο βιβλίο εδώ πέρα. Η κουβέντα αυτή είναι μεταξύ καθηγητών και δεν είναι ανάγκη να είναι κατανοητή στους μαθητές. Δεν μπορώ να δώσω παράδειγμα αλγορίθμου που να μην έχει έξοδο το οποίο να είναι κατανοητό στο μαθητή. Ποτέ όμως δε θα με ακούσει μαθητής να λέω για start up scripts και processes. Όταν μιλάμε πρέπει κάθε στιγμή να έχουμε κατά νου και το που απευθυνόμαστε. Εγώ απευθύνομαι σε καθηγητές στο παρόν θέμα.

Χάιντι τι δε σου αρέσει στη λέξη προγραμματισμός;
Η «ανάπτυξη εφαρμογών» και ο «προγραμματισμός» είναι συνώνυμα. Στην πιάτσα οι προγραμματιστές λέγονται και «application developers». Δηλαδή το αντικείμενο του μαθήματος η ανάπτυξη εφαρμογών ή αλλιώς ο προγραμματισμός (έστω και σε πολύ πρώιμο στάδιο).
Ο Wirth είπε τη φράση
 «Αλγόριθμοι + Δομές δεδομένων = προγράμματα»
Το βιβλίο περιλαμβάνει και τους αλγορίμους και τις δομές δεδομένων σαν κεφάλαια. Άρα περιλαμβάνει και την έννοια του προγραμματισμού.

Θέτω το εξής ερώτημα (σε μας που διδάσκουμε):

Υπάρχουν προγράμματα που ανάλογα με το τι μέρα είνει εκτελούν και άλλη διαδικασία:
 Πχ κάθε Δευτέρα παίρνουν backup κάποια αρχεία.
Κάθε Τρίτη τα στέλνουν σε κάποιο άλλο υπολογιστή
Κλπ
Τέτοιου είδους προγράμματα είναι γεμάτα από if then else (αν. . .  τότε . . .αλλιώς για να μιλήσω στη γλώσσα του βιβλίου). Δηλαδή έχουν αρκετές εντολές από αυτές που περιέχει το βιβλίο στο κεφάλαιο των αλγορίθμων. Αλλά δεν παράγουν κάποια έξοδο. Απλά καλούν το κατάλληλο πρόγραμμα που κάνει τη δουλειά.
Τελικά είναι ή δεν είναι αλγόριθμος αυτός που χρησιμοποιείται;
Αν είναι, τότε το βιβλίο δε λέει σωστά ότι ο αλγόριθμος έχει πάντα έξοδο.
Αν δεν είναι, τότε τι είναι οι εντολές επιλογής και επανάληψης που περιέχει;

Με εκτίμηση

redhata

#12
pfan
------
Ο αλγόριθμος no_external_input παράγει με εντολές εκχώρησης κάποιες βασικές τιμές, οπότε δεν βρίσκω παραβίαση κριτηρίου εισόδου.
Για τον  αλγόριθμο hello, η σταθερά 'hello world' μπορεί να θεωρηθεί σαν βασική τιμή που παράγεται εσωτερικά στον αλγόριθμο οπότε πάλι δεν υπάρχει παραβίαση του κριτηρίου εισόδου. Παραβίαση θα υπήρχε αν στην εντολή Εμφάνισε υπήρχε μια μεταβλητή(και όχι σταθερά), χωρίς να προηγείται Διάβασε ή εκχώρηση.
Το κριτήριο εισόδου λέει μηδέν, μία ή περισσότερες τιμές εισόδου και για μηδέν εισόδους απαιτεί κάποιες πρωτογενείς τιμές που παράγονται κάπως... Οι σταθερές για μένα είναι μια χαρά πρωτογενείς τιμές.

  ::)
rEdHaTa

redhata

#13
gpapargi
-----------
Κάθε script οποιουδήποτε shell του unix μετά τον τερματισμό του, επιστρέφει πάντα σε μια μεταβλητή του shell(πχ. στη status για το C shell)  έναν κωδικό(έξοδος   ;)), που είναι 0, αν έχει τελειώσει κανονικά και διάφορος του μηδενός, σε διαφορετική περίπτωση.
rEdHaTa

P.Tsiotakis


Αγαπητοί,

ο αλγόριθμος είναι το θεωρητικό υπόβαθρο

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