Ενότητα 08 – Δραστηριότητες – Σελίδα 93-96 – ΠΛΗΡΟΦΟΡΙΚΗ Α΄ ΓΥΜΝΑΣΙΟΥ – Απαντήσεις – Λύσεις

(Πηγή: Βιβλίο Μαθητή, Πληροφορική Α΄ Γυμνασίου, Κεφάλαιο 8 «Αλγοριθμική», σελ. 93-96. Το §8.5 "Ερωτήσεις - Ασκήσεις" του κεφαλαίου έχει ήδη το δικό του πλήρες lyseis ζεύγος (kefalaio-8.5_lyseis.json/.md) και ΔΕΝ επαναλαμβάνεται εδώ. Οι 6 «Δραστηριότητα 1-6» παρακάτω είναι τοπικά αριθμημένα κουτιά ενσωματωμένα μέσα στη θεωρία των §8.2 και §8.3 (καμία δεν βρέθηκε στα §8.1 και §8.4). Οι εκφωνήσεις είναι αυτούσιες από το σχολικό βιβλίο.)

Δραστηριότητες Κεφαλαίου 8

Δραστηριότητα 1 (σελ. 93)

Μετρήστε ακριβώς 6 λίτρα αν έχετε στη διάθεσή σας ένα δοχείο των 5 λίτρων, ένα των 7 λίτρων και μια πηγή με άφθονο νερό. Μπορείτε μόνο να γεμίζετε μέχρι πάνω και να αδειάζετε εντελώς τα δοχεία όσες φορές θέλετε.

Σκέψη / Μεθοδολογία: Ίδιος τύπος προβλήματος με το λυμένο Παράδειγμα 2 της §8.2 (εκεί: δοχεία 5 & 3 λίτρων, στόχος 1 λίτρο), με το ίδιο σύνολο εντολών {Γέμισε(Ν), Άδειασε(Ν), Μετακίνησε(Μ,Ν)}. Μοντελοποιήσαμε το πρόβλημα ως χώρο καταστάσεων (a, b) = (λίτρα στο δοχείο 5, λίτρα στο δοχείο 7) και βρήκαμε τη συντομότερη λύση με αλγόριθμο BFS σε πραγματικό κώδικα Python.

Λύση:

Κατάσταση (a, b) = (λίτρα στο δοχείο 5L, λίτρα στο δοχείο 7L). Αρχική κατάσταση: (0, 0).

Η λύση επαληθεύτηκε υπολογιστικά με αλγόριθμο BFS πάνω σε όλο τον χώρο καταστάσεων {0..5}×{0..7}: 10 είναι ο ελάχιστος δυνατός αριθμός βημάτων.

Απάντηση: Μετά από 10 βήματα, το δοχείο των 7 λίτρων καταλήγει με ακριβώς 6 λίτρα νερού.

Πρόσεξε:

• Υπάρχουν και άλλες ισοδύναμες ακολουθίες 10 βημάτων με το ίδιο αποτέλεσμα (π.χ. ξεκινώντας από Γέμισε(5))· γι' αυτό η λύση σημειώνεται ενδεικτική.
• Τα 6 λίτρα δεν μπορούν ποτέ να βρεθούν στο δοχείο των 5 λίτρων (χωρητικότητα 5 < 6) — μόνο στο δοχείο των 7.
• Ο γρίφος λύνεται επειδή ΜΚΔ(5,7)=1: με δύο δοχεία πρώτων μεταξύ τους χωρητικοτήτων μπορούμε να πετύχουμε οποιαδήποτε ακέραια ποσότητα από 0 έως 7 λίτρα.

Δραστηριότητα 2 (σελ. 93)

Έχετε τρεις κανάτες, μία των 10 λίτρων, μία των 7 λίτρων και μία των 3 λίτρων. Αυτή που χωράει 10 λίτρα είναι γεμάτη και οι άλλες δύο άδειες. Πώς μπορείτε να βάλετε σε μία από τις κανάτες ακριβώς 5 λίτρα νερό, χωρίς ζυγαριά, κάνοντας μόνο μεταφορές νερού από τη μία στην άλλη;

Σκέψη / Μεθοδολογία: Σε αντίθεση με τη Δραστηριότητα 1, εδώ η συνολική ποσότητα νερού είναι σταθερή (10 λίτρα, μοιρασμένα στις τρεις κανάτες) — επιτρέπονται μόνο μεταφορές μεταξύ κανατών. Μοντελοποιήσαμε την κατάσταση ως (x, y, z) = (10L, 7L, 3L κανάτα) με x+y+z=10, και βρήκαμε τη συντομότερη λύση με BFS.

Λύση:

Κατάσταση (x, y, z) = (λίτρα στην κανάτα 10L, 7L, 3L). Αρχική κατάσταση: (10, 0, 0).

Η λύση επαληθεύτηκε υπολογιστικά με BFS πάνω σε όλο τον χώρο καταστάσεων (x+y+z=10, 0≤x≤10, 0≤y≤7, 0≤z≤3): 8 είναι ο ελάχιστος αριθμός μεταφορών.

Απάντηση: Μετά από 8 μεταφορές, η κανάτα των 7 λίτρων καταλήγει με ακριβώς 5 λίτρα νερό.

Πρόσεξε:

• Υπάρχουν διαφορετικές αλλά εξίσου σωστές ακολουθίες 8 μεταφορών (π.χ. συμμετρικές παραλλαγές) — η λύση σημειώνεται ενδεικτική.
• Σε κάθε μεταφορά μετακινείται πάντα το ελάχιστο ανάμεσα σε «όσο έχει η πηγή» και «όσο χώρο έχει ο προορισμός» — ποτέ δεν επιλέγουμε εμείς ενδιάμεση ποσότητα.
• Το άθροισμα των τριών κανατών παραμένει πάντα 10 λίτρα — χρήσιμος έλεγχος ορθότητας σε κάθε βήμα.

Δραστηριότητα 3 (σελ. 94)

Να καταγράψετε τα βήματα του αλγορίθμου της πρόσθεσης αναλυτικά.

Σκέψη / Μεθοδολογία: Το βιβλίο δίνει ακριβώς πριν τη Δραστηριότητα το λυμένο παράδειγμα κάθετης πρόσθεσης 1999 + 39 = 2038 «με κρατούμενα». Μετατρέπουμε τη γνωστή διαδικασία σε ρητά, εκτελέσιμα βήματα αλγορίθμου και επαληθεύουμε πάνω στο ίδιο παράδειγμα του βιβλίου.

Λύση:

1. Δεδομένα εισόδου: δύο ακέραιοι Α και Β, ευθυγραμμισμένοι από τα δεξιά (μονάδες κάτω από μονάδες κ.ο.κ.), με μηδενικά συμπλήρωσης όπου χρειάζεται.
2. Αρχικοποίηση: κρατούμενο = 0, ξεκινάμε από τη στήλη των μονάδων.
3. Επανάληψη (για κάθε στήλη, από δεξιά προς αριστερά): πρόσθεσε τα δύο ψηφία της στήλης και το τρέχον κρατούμενο.
4. Αν το άθροισμα ≥ 10: γράψε το τελευταίο ψηφίο (άθροισμα mod 10), νέο κρατούμενο = 1. Αλλιώς: γράψε όλο το άθροισμα, νέο κρατούμενο = 0.
5. Προχώρα στην επόμενη στήλη αριστερά, επανέλαβε 3-4 μέχρι να εξαντληθούν τα ψηφία.
6. Αν απομείνει κρατούμενο 1 μετά την τελευταία στήλη, πρόσθεσέ το ως νέο τελευταίο (αριστερότερο) ψηφίο.
7. Έξοδος: το αποτέλεσμα είναι η ακολουθία ψηφίων που γράφτηκαν, από αριστερά προς δεξιά.

Επαλήθευση πάνω στο 1999 + 39: μονάδες 9+9=18 → γράψε 8, κρατ.1 · δεκάδες 9+3+1=13 → γράψε 3, κρατ.1 · εκατοντάδες 9+0+1=10 → γράψε 0, κρατ.1 · χιλιάδες 1+0+1=2 → γράψε 2. Αποτέλεσμα: 2038 — ταυτίζεται με το παράδειγμα του βιβλίου.

Απάντηση: Ο αλγόριθμος περιγράφεται στα 7 βήματα παραπάνω· εφαρμοσμένος στο 1999+39 δίνει σωστά 2038.

Πρόσεξε:

• Αποδεκτή κάθε ισοδύναμη διατύπωση των ίδιων βημάτων — σημειώνεται ενδεικτική.
• Το κρατούμενο είναι το κρισιμότερο σημείο που δεν πρέπει να παραλειφθεί.

Δραστηριότητα 4 (σελ. 94)

Να βάλετε στη σειρά τα βήματα εκτέλεσης μιας απλής συνταγής για μακαρόνια με σάλτσα.

Σκέψη / Μεθοδολογία: Δίνονται 10 βήματα σε τυχαία σειρά. Παρατηρήσαμε ότι δύο από αυτά («Αφού στραγγίσετε τα μακαρόνια, τα βάζετε πίσω στην κατσαρόλα με λάδι και βούτυρο και ανακατεύετε» και «Στραγγίστε τα μακαρόνια και στη συνέχεια σερβίρετε στα πιάτα») περιγράφουν εναλλακτικά, αλληλοαποκλειόμενα τελειώματα της ίδιας συνταγής (επιβεβαιώθηκε λέξη προς λέξη στο ίδιο το PDF — δεν είναι λάθος μεταγραφής). Επιλέξαμε την πληρέστερη εκδοχή ως κύρια αλυσίδα.

Λύση (σωστή σειρά):

1. Τοποθετήστε την κατσαρόλα στο μάτι της κουζίνας.
2. Γεμίστε την κατσαρόλα με νερό από τη βρύση.
3. Ανοίξτε το μάτι της κουζίνας.
4. Περιμένετε μέχρι να βράσει το νερό.
5. Βάλτε τα μακαρόνια στην κατσαρόλα.
6. Βράζετε τα μακαρόνια για 8 λεπτά.
7. Κλείστε το μάτι της κουζίνας.
8. Αφού στραγγίσετε τα μακαρόνια, τα βάζετε πίσω στην κατσαρόλα με λάδι και βούτυρο και ανακατεύετε.
9. Σερβίρετε τα μακαρόνια με σάλτσα ντομάτας και από πάνω ρίχνετε πιπέρι.

Η δέκατη πρόταση («Στραγγίστε τα μακαρόνια και στη συνέχεια σερβίρετε στα πιάτα») περιγράφει συνοπτικά ακριβώς τα ίδια βήματα 8-9 και δεν προστίθεται ξεχωριστά, αφού θα σήμαινε διπλό στράγγισμα/σερβίρισμα του ίδιου φαγητού.

Απάντηση: Τοποθέτησε την κατσαρόλα → γέμισέ την με νερό → άναψε το μάτι → περίμενε το βράσιμο → βάλε τα μακαρόνια → βράσε 8 λεπτά → σβήσε το μάτι → στράγγισε, βάλε πίσω με λάδι/βούτυρο, ανακάτεψε → σερβίρισε με σάλτσα και πιπέρι.

Πρόσεξε:

• Επαληθεύτηκε λέξη προς λέξη με pdftotext στη σελ. 95 του PDF ότι η λίστα ταιριάζει ακριβώς με το JSON.
• Οι δύο εναλλακτικές διατυπώσεις στράγγισης/σερβιρίσματος είναι πιθανή ατέλεια/επικάλυψη της ίδιας της άσκησης στο βιβλίο, όχι λάθος μεταγραφής μας — σημειώνεται ρητά, η απάντηση παραμένει μη ενδεικτική ως προς τη γενική σειρά.

Δραστηριότητα 5. Κρυπτανάλυση (σελ. 96)

Χωριστείτε σε ομάδες των 3-4 ατόμων στην τάξη. Επιλέξτε το μυστικό κλειδί της κρυπτογράφησης και κρυπτογραφήστε με αυτό μια φράση. Στη συνέχεια, να γράψετε στον πίνακα το κρυπτογραφημένο μήνυμα. Ο στόχος είναι να βρείτε τα κλειδιά των άλλων ομάδων και να αποκρυπτογραφήσετε τα μηνύματά τους. Να καταγράψετε αναλυτικά τη στρατηγική που θα ακολουθήσετε κατά την κρυπτογράφηση του δικού σας μηνύματος, αλλά και κατά τη διαδικασία της κρυπτανάλυσης των μηνυμάτων των άλλων ομάδων. Πόσο χρόνο πιστεύετε ότι χρειάζεται ένας απλός υπολογιστής για να «σπάσει» τον κώδικα του Καίσαρα; Υπάρχει τρόπος να τον δυσκολέψετε;

Σκέψη / Μεθοδολογία: Ομαδική/βιωματική δραστηριότητα χωρίς μοναδική «σωστή» φράση/κλειδί. Δίνουμε δειγματική στρατηγική, μαζί με την τεκμηριωμένη (μη ενδεικτική στην ουσία) απάντηση για τον χρόνο εξαντλητικής αναζήτησης: το ελληνικό αλφάβητο έχει 24 γράμματα, άρα μόνο 23 μη-τετριμμένα πιθανά κλειδιά ολίσθησης.

Λύση:

• Κρυπτογράφηση: επιλογή μυστικού κλειδιού k (1-23), επιλογή φράσης, ολίσθηση κάθε γράμματος κατά k θέσεις στο 24γράμματο αλφάβητο (με αναδίπλωση), γράφουμε στον πίνακα μόνο το κρυπτόγραμμα.
• Κρυπτανάλυση των άλλων ομάδων: εξαντλητική αναζήτηση (brute force) — δοκιμάζουμε διαδοχικά όλα τα 23 πιθανά κλειδιά και ελέγχουμε ποιο δίνει νόημα στα ελληνικά.
• Χρόνος εξαντλητικής αναζήτησης: με μόλις 23 πιθανά κλειδιά, ένας υπολογιστής δοκιμάζει όλα σε χρόνο πρακτικά μηδενικό (< 1 χιλιοστό του δευτερολέπτου), ανεξάρτητα από το μήκος του μηνύματος.
• Πώς δυσκολεύουμε την κρυπτανάλυση: αντί για απλή ολίσθηση, γενική αντικατάσταση όπου κάθε γράμμα αντιστοιχίζεται ελεύθερα σε οποιοδήποτε άλλο — τότε ο χώρος κλειδιών γίνεται 24! (πάνω από 6×10²³ πιθανά αλφάβητα), πρακτικά αδύνατο για εξαντλητική αναζήτηση, αν και ευάλωτο σε στατιστική ανάλυση συχνοτήτων.

Απάντηση (ενδεικτική): Η απλή κρυπτογράφηση Καίσαρα έχει μόνο 23 πιθανά κλειδιά — «σπάει» σχεδόν ακαριαία από υπολογιστή. Δυσκολεύει σημαντικά με γενική αντικατάσταση αλφαβήτου (24! κλειδιά).

Πρόσεξε:

• Το ερώτημα του χρόνου έχει συγκεκριμένη, τεκμηριωμένη απάντηση — δεν πρέπει να συγχέεται με το ανοιχτό/ομαδικό μέρος (επιλογή φράσης/κλειδιού).
• Η γενική αντικατάσταση παραμένει ευάλωτη σε ανάλυση συχνοτήτων γραμμάτων, δεν είναι «απόλυτα ασφαλής».

Δραστηριότητα 6. Έξοδος από Λαβύρινθο (σελ. 96)

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

Σκέψη / Μεθοδολογία: Το βιβλίο περιγράφει ήδη σε πεζό λόγο τη λύση (κανόνας δεξιού χεριού / wall follower). Η δραστηριότητα ζητά τη μετατροπή της σε ρητά, εκτελέσιμα βήματα αλγορίθμου — γενικά, ανεξάρτητα από τη συγκεκριμένη εικόνα λαβυρίνθου, αφού ο ίδιος αλγόριθμος λειτουργεί σε κάθε λαβύρινθο χωρίς νησίδες τοίχων.

Λύση:

1. Είσοδος: θέση εισόδου (κόκκινο βέλος) και αρχικός προσανατολισμός με το δεξί χέρι πάνω σε τοίχο.
2. Τοποθέτησε το δεξί σου χέρι σε έναν τοίχο, στην είσοδο, και μην το αποκολλήσεις ποτέ.
3. Επανάληψη (όσο δεν έχεις φτάσει στην έξοδο):
   • Αν υπάρχει πέρασμα ΔΕΞΙΑ → στρίψε δεξιά, προχώρα ένα βήμα.
   • Αλλιώς αν υπάρχει πέρασμα ΜΠΡΟΣΤΑ → προχώρα ευθεία.
   • Αλλιώς αν υπάρχει πέρασμα ΑΡΙΣΤΕΡΑ → στρίψε αριστερά, προχώρα.
   • Αλλιώς (αδιέξοδο) → κάνε μεταβολή 180° και προχώρα.
4. Επανέλαβε μέχρι να φτάσεις στην έξοδο (πράσινο βέλος).
5. Έξοδος του αλγορίθμου: η ακολουθία κινήσεων από την είσοδο μέχρι την έξοδο.

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

Απάντηση: Αλγόριθμος wall follower όπως περιγράφεται στα 5 βήματα παραπάνω· τερματίζει πάντα επιτυχώς σε λαβύρινθο χωρίς κενά/νησίδες στους τοίχους.

Πρόσεξε:

• Δεν χρειάζεται η εικόνα του συγκεκριμένου λαβυρίνθου για τον γενικό αλγόριθμο — μόνο μια πλήρης ιχνηλάτηση πάνω στη συγκεκριμένη εικόνα θα την απαιτούσε.
• Ο κανόνας δεξιού χεριού δεν εγγυάται τη συντομότερη διαδρομή, μόνο ότι θα βρει κάποια — άλλες λύσεις (π.χ. BFS/DFS σε γράφο) είναι εξίσου αποδεκτές, γι' αυτό η απάντηση σημειώνεται ενδεικτική.