Καλύτερη υλοποίηση ουράς

Ξεκίνησε από alkisg, 14 Φεβ 2020, 11:55:38 ΠΜ

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

bugman

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

akalest0s

Παράθεση από: fof στις 18 Φεβ 2020, 04:32:28 ΜΜ
υπάρχουν αρκετοί τρόποι επίλυσης για ολίσθηση σε ουρά, γιατί να συγκεκριμενοποιησουμε εναν μονο!.
Ποιος είπε να συγκεκριμενοποιήσουμε έναν μόνο τρόπο;
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

fof


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

akalest0s

#18
Παράθεση από: fof στις 18 Φεβ 2020, 11:29:17 ΜΜ
Η συζήτηση  αφορά αλλαγές στην παρούσα υλοποιηση της ουράς και της ολίσθησης (όπου δεν αναφέρεται  ως θεωρία στο βιβλίο) . Γιατί; Δεν έχω εντοπίσει το πρόβλημα ακριβώς; Μια χαρά θέμα είναι.
- Χαζή υλοποίηση σε περίπτωση γεμίσματος ουράς (που όμως δεν έχει γεμίσει.. σοβαρά τώρα;)
- Κυκλικός πίνακας ή ολίσθηση: καλό είναι να ξεκαθαρίσει τη θέση του και γιατί όχι, να τα συμπεριλάβει, με μια καλή υλοποίηση. Αν τα θέλει εντός, να τα περιγράψει με ικανό τρόπο. Αν τα θέλει εκτός, να μην τα πετάει στην λύση άσκησης που δεν τα ζητάει, αλλά μόνο αν περιγράφεται με ικανό τρόπο στην εκφώνηση.

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

- "Για r=10, θεωρούμε ότι η ουρά έχει γεμίσει"
- "Μα κύριε, αν έχουν γίνει εξαγωγές;"
- "Ναι, ξέρετε.. όντως δεν είναι πραγματικά γεμάτη, αλλά εμείς έτσι θα λέμε!"
- "..."

διάλογος-ομορφιά #2:
- "Αν f=0 και r=0 τότε η ουρά είναι άδεια"
- "Κύριε, γιατί χρειαζόμαστε να τσεκάρουμε και το f και το r, δεν είναι περιττό;"
- "Είναι όντως.."
- "Μα δεν έχετε πει ότι πρέπει να αποφεύγουμε περιττούς ελέγχους στις Αν;"
- "Εεε,..."


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

Μια χαρά είναι η άσκηση που έβαλες προ ημερών σε ουρές (για την οποία, παρεμπιπτόντως, σε ευχαριστώ). Οι ασκήσεις στο σχολικό σου φαίνονται οκ, με 20 γραμμές εκφώνηση που αποτυχαίνει να ορίσει τι ακριβώς θέλει να πει, με ασάφειες ή και flat out λάθη;
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

alkisg

@fof, το ερώτημα είναι "έχω μια ουρά με Ν θέσεις, βάζω Ν στοιχεία, βγάζω Ν στοιχεία, άρα η ουρά τώρα είναι άδεια, μπορώ λοιπόν να προσθέσω άλλα";

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

Η διόρθωση των λύσεων είναι απλή, χρειάζεται να χρησιμοποιηθεί η πράξη "mod N" και γίνονται όλα ΟΚ.

Μια εναλλακτική προσέγγιση θα ήταν να χρησιμοποιηθεί ολίσθηση των στοιχείων προς τα αριστερά όταν rear=N, αλλά εγώ είμαι εντελώς αντίθετος σε αυτή τη λύση, είναι δυσνόητη (χρησιμοποιεί ΓΙΑ χωρίς να χρειάζεται), αντιεπιστημονική (κάνει την ουρά Ο(Ν) αντί για Ο(1)), και αντιπαιδαγωγική (παρομοιάζει τις ουρές στους υπολογιστές με κινούμενα αυτοκίνητα ή ανθρώπους, το οποίο δεν αντιστοιχεί αφού στις ουρές υπολογιστών δεν χρειάζεται ολίσθηση/κίνηση των κόμβων).
Συνήθως στο δίκτυο την ολίσθηση την βλέπουμε με την υποσημείωση "πως να ΜΗΝ υλοποιούμε τις ουρές", και ακολουθεί η λύση με το mod N.

fof

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

akalest0s

Παράθεση από: fof στις 20 Φεβ 2020, 09:57:17 ΜΜ
για παράδειγμα θα μπορουσε να χρησιμοποιηθεί στην αναγνωριση μιας συμβολοσειράς η στην εύρεση στοιχείων κατά πλατος ενός γράφου .
..με το οποίο δεν διαφωνώ καθόλου.
Και εδώ είναι ένα από τα μεγαλύτερα, αν όχι το μεγαλύτερο, κατά τη γνώμη μου, πρόβλημα, όχι μόνο της πληροφορικής, αλλά και όλων των διδακτικών προσεγγίσεων, σε όλη την υπάρχουσα εκπαίδευση. Ελλιπές ή ανύπαρκτο εμπειρικό πλαίσιο. Η μόνη σύνδεση που επιχειρεί το βιβλίο, του κώδικα με την εμπειρία των μαθητών στη θεωρία, είναι με το αρχικό παράδειγμα με τους φοιτητές και το καράβι. Στο οποίο παράδειγμα δεν έχει νόημα αυτό το "r=M, η ουρά γέμισε". (Ή, αν θεωρήσουμε, με λίγη καλή θέληση, ότι έχει νόημα, τότε αργότερα όταν δημιουργηθεί η προφανής απορία στα παιδιά σε άλλο σημείο, με ποιον τρόπο τους απαντάς;)
Δεν είναι του θέματος, και δεν θα επεκταθώ, αλλά είναι χαρακτηριστικό πως πέφτουμε σε θεωρητικολογίες και απροσδιοριστίες, όταν δεν έχει εμπειρικό αντίκρισμα αυτό που λέμε στα παιδιά. Οι ασκήσεις γίνονται αδιάφορες, και η θεωρία απρόσληπτη.
(Για να μην πω ότι πολλές φορές ούτε εμείς οι καθηγητές δεν έχουμε εμπειρία των όσων διδάσκουμε..)
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

fof

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

akalest0s

Παράθεση από: P. TsiotakisΤο κεφάλαιο αυτό πρέπει να αφαιρεθεί από την τρέχουσα μορφή του μαθήματος της Πληροφορικής.
Αυτό να πεις.

Γενικότερα, για να πάρω μια θέση για το αρχικό ζήτημα: ως προς την υλοποίηση που συζητάμε, είτε μια από τις απλουστευμένες μορφές που προτάθηκαν, με την ολίσθηση να είναι απλά ένα δύσκολο θέμα, εκτός βασικής θεωρίας (όπως δηλ. είναι η δυαδική αναζήτηση αυτή τη στιγμή), είτε αυτό που πρότεινε ο Άλκης, με δεδομένο ότι όλος ο κώδικας αυτός μπορεί να θεωρηθεί το πιο δύσκολο σημείο του μαθήματος. Μέσα από ασκήσεις πάντως, μπορεί να εμπεδωθεί.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

Vangelis

Η παρουσίαση της λειτουργίας της ουράς έχει πολλά προβλήματα όπως έχει εισαχθεί.
Στον φυσικό κόσμο οι ουρές δουλεύουν με ολίσθηση άρα παιδαγωγικά και επειδή προσπαθούμε τα προβλήματα που βάζουμε να είναι πραγματικά θα έπρεπε να διδάσκεται έτσι. Δεν μπορώ να φανταστώ πρόβλημα στον πραγματικό κόσμου που να υλοποιείται με κυκλική ουρά.   Φυσικά στο τέλος του αντίστοιχου κεφαλαίου θα έπρεπε να υπάρχει η λειτουργία της κυκλικής ουράς με το mod N και να αναφέρεται η μικρότερη πολυπλοκότητα του αλγορίθμου.
Λόγω όλων αυτών των προβλημάτων υποθέτω ότι η ουρά αποτελεί απαγορευμένο θέμα για τις πανελλαδικές για  θέμα 3 ή 4.

alkisg

Παράθεση από: Vangelis στις 23 Φεβ 2020, 04:08:16 ΜΜ
Δεν μπορώ να φανταστώ πρόβλημα στον πραγματικό κόσμου που να υλοποιείται με κυκλική ουρά.

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

Παράθεση από: Vangelis στις 23 Φεβ 2020, 04:08:16 ΜΜ
Στον φυσικό κόσμο οι ουρές δουλεύουν με ολίσθηση άρα παιδαγωγικά και επειδή προσπαθούμε τα προβλήματα που βάζουμε να είναι πραγματικά θα έπρεπε να διδάσκεται έτσι.

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

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

ΓΙΑ ι ΑΠΟ Ν ΜΕΧΡΙ 1 ΜΕ_ΒΗΜΑ -1
  Α[ι] <- άνθρωπος
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Αυτή είναι η "ολίσθηση" που γίνεται στον φυσικό κόσμο, ενώ εμείς την αναφέρουμε ως:
  Α[1] <- άνθρωπος
...σαν αυτός να μη διέσχισε το διάδρομο αλλά να τηλεμεταφέρθηκε στη θέση 1.

Εννοείται όμως ότι ΔΕΝ θέλουμε τέτοια μοντελοποίηση. Όπως δεν θέλουμε να αναφέρουμε τη "διάσχιση του 1ου ανθρώπου", έτσι δεν θέλουμε να αναφέρουμε και την "διάσχιση=ολίσθηση των επόμενων που μπήκαν λίγη ώρα αργότερα".

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

Τέλος, μπορούμε να κάνουμε όσα αυθεντικά παραδείγματα θέλουμε, αλλά αν είναι Ο(Ν), δεν μπορούμε να τα χρησιμοποιήσουμε για να διδάξουμε ουρές. Η εισαγωγή και εξαγωγή στις ουρές είναι Ο(1), δεν πρέπει να χαθεί η ορθότητα για χάρη του παραδείγματος.
Αντίστοιχα, αν βρούμε κάποιο αυθεντικό παράδειγμα ταξινόμησης σε Ο(Ν^3), δεν μπορούμε να πούμε ότι είναι bubblesort, αφού αυτός είναι Ο(Ν^2).
Ή στα μαθηματικά, αν δεν βρούμε φυσικό λόγο να διδάξουμε πενταπλό επικαμπύλιο ολοκλήρωμα, δεν σημαίνει ότι θα πρέπει να διδάξουμε κάτι άλλο και να το βαφτίσουμε όπως θέλουμε.

bagelis

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

Διαισθάνομαι ότι δεν υπάρχει μία άποψη...

alkisg

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

Η αποφυγή αυτή επίσης σημαίνει ότι όλα είναι καλά, δεν χρειάζεται ούτε mod Ν ούτε ολίσθηση, και οι ουρές είναι Ο(1).
Για παράδειγμα, στην άσκηση ΤΡΑΠΕΖΑ του συμπληρωματικού τεύχους δίνει τον περιορισμό ότι η τράπεζα θα εξυπηρετήσει το πολύ μέχρι 1000 πελάτες και άρα δεν θα φτάσει το δεξί άκρο του πίνακα.

Όμως, στην ενδεικτική λύση της άσκησης ΤΑΧΥΔΡΟΜΕΙΟ στη σελίδα 18 του συμπληρωματικού τεύχους αναφέρεται σε αυτό το ζήτημα και το λύνει κάνοντας ολίσθηση των στοιχείων.
Αυτό είναι προβληματικό, αφού πλέον η ουρά γίνεται Ο(Ν) και έτσι ακυρώνεται το βιβλίο μαθητή που στη σελίδα 98 λέει ότι οι ουρές είναι Ο(1).

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

ApoAntonis

Παράθεση από: alkisg στις 27 Φεβ 2020, 07:39:05 ΠΜ
Για παράδειγμα, στην άσκηση ΤΡΑΠΕΖΑ του συμπληρωματικού τεύχους δίνει τον περιορισμό ότι η τράπεζα θα εξυπηρετήσει το πολύ μέχρι 1000 πελάτες και άρα δεν θα φτάσει το δεξί άκρο του πίνακα.

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

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

Vangelis

Παράθεση από: alkisg στις 17 Φεβ 2020, 08:41:02 ΠΜ
Οι βέλτιστες αρχικές τιμές είναι rear=0 και front=1. Εξηγώ γιατί:

  • Μετά την πρώτη εισαγωγή, θέλουμε να δείχνουν και οι δύο δείκτες το πρώτο στοιχείο, rear=1 και front=1.
  • Στις εισαγωγές, θέλουμε να μεταβάλλουμε μόνο τον δείκτη rear. Δεν έχει νόημα να μεταβάλλουμε και τον front. Έτσι και γλυτώνουμε μια ΑΝ και κάνουμε τον κώδικα απλούστατο, μόνο 3 γραμμές.
  • Από τα δύο προηγούμενα bullets συνεπάγεται ότι οι καλύτερες αρχικές τιμές και από πλευράς υλοποίησης και από πλευράς διδασκαλίας είναι rear=0 και front=1.
Αντίστοιχα στις εξαγωγές εννοείται ότι θέλουμε να μεταβάλλουμε μόνο τον δείκτη front.
Συμφωνώ με τον Άλκη η βέλτιστη λύση είναι rear=0 και  front=1. Αυτό λύνει πολλά προβλήματα και έτσι υλοποιούνται οι ουρές στις "πραγματικές γλώσσες προγραμματισμού.