Λύσεις — Κεφάλαιο 1 · Από το Πρόβλημα στην Ανάπτυξη Αλγόριθμου (σελ. 17, 20) – ΑΡΧΕΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ ΥΠΟΛΟΓΙΣΤΩΝ

Λύσεις — Κεφάλαιο 1 · Από το Πρόβλημα στην Ανάπτυξη Αλγόριθμου (σελ. 17, 20)

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

Ερ.1 — Τι είναι πρόβλημα

Ερώτηση: Τι είναι ένα πρόβλημα;

Απάντηση:

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

Σύνοψη: (ενδεικτική) Κατάσταση που απαιτεί λύση, η οποία δεν είναι γνωστή/προφανής (αν λύνεται με Η/Υ → υπολογιστικό).

Κριτήρια αξιολόγησης:

• Κριτήριο: «απαιτεί λύση» + «η λύση δεν είναι γνωστή/προφανής».

Ερ.2 — Βήματα επίλυσης προβλήματος

Ερώτηση: Ποια είναι τα βασικά βήματα για την επίλυση ενός προβλήματος;

Απάντηση:

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

Σύνοψη: (ενδεικτική) Κατανόηση/αφαίρεση → ανάλυση σε υποπροβλήματα → αναγνώριση προτύπων → κατασκευή αλγόριθμου → αξιολόγηση → γενίκευση.

Κριτήρια αξιολόγησης:

• Κριτήριο: ≥4 στάδια με λογική σειρά (κατανόηση→αλγόριθμος→αξιολόγηση).

Ερ.3 — Η αξία της αφαίρεσης

Ερώτηση: Μπορείτε να περιγράψετε με ένα δικό σας παράδειγμα την αξία της αφαίρεσης;

Απάντηση:

• Αφαίρεση = εντοπισμός των βασικών χαρακτηριστικών, αγνοώντας τα περιττά.
• Παράδειγμα: για να δρομολογήσω μια διαδρομή σε χάρτη, κρατώ τις αποστάσεις/δρόμους και αγνοώ το χρώμα των κτιρίων ή τον καιρό.
• (Άλλο: ένα Formula 1 και ένα τζιπ είναι και τα δύο αυτοκίνητα — αφαιρώ τις διαφορές τους.)

Σύνοψη: (ενδεικτική) Αφαίρεση = κράτημα των βασικών χαρακτηριστικών. Π.χ. στη δρομολόγηση διαδρομής κρατώ αποστάσεις/δρόμους, αγνοώ άσχετες λεπτομέρειες.

Κριτήρια αξιολόγησης:

• ΕΝΔΕΙΚΤΙΚΗ: κάθε λογικό προσωπικό παράδειγμα δεκτό. Κριτήριο: δείχνει «κρατώ βασικά, αγνοώ περιττά».

Ερ.4 — Τρόποι αναπαράστασης αλγόριθμου

Ερώτηση: Με ποιους τρόπους μπορούμε να αναπαραστήσουμε έναν αλγόριθμο;

Απάντηση:

• Φυσική γλώσσα (με απλά λόγια και ελεύθερες εκφράσεις — αυξημένη πιθανότητα λάθους ή ασάφειας).
• Διαγραμματικές τεχνικές — η πιο γνωστή είναι το διάγραμμα ροής (γραφικός τρόπος).
• Κωδικοποίηση: πρόγραμμα γραμμένο σε ψευδογλώσσα ή σε γλώσσα προγραμματισμού, που όταν εκτελεσθεί δίνει τα ίδια αποτελέσματα με τον αλγόριθμο.
• Ψευδογλώσσα/ψευδοκώδικας (υποθετική δομημένη γλώσσα με λίγες εντολές και απλοποιημένη σύνταξη).

Σύνοψη: (ενδεικτική) Φυσική γλώσσα, διαγραμματικές τεχνικές (διάγραμμα ροής), κωδικοποίηση (πρόγραμμα), ψευδογλώσσα/ψευδοκώδικας.

Κριτήρια αξιολόγησης:

• Κριτήριο: ≥3 τρόποι (ιδανικά και οι 4).

Δραστηριότητα 1 (Πρόβλημα 1) — Εύρεση των κάλπικων νομισμάτων με μια ζύγιση

Ερώτηση: Υπάρχουν δέκα σακιά που περιέχουν 100 νομίσματα το καθένα. Το κάθε νόμισμα ζυγίζει 10 γραμμάρια. Το ένα από τα δέκα σακιά έχει μέσα μόνο κάλπικα νομίσματα τα οποία ζυγίζουν 9 γραμμάρια το καθένα. Πώς μπορούμε, με μία μόνο ζύγιση σε μια ηλεκτρονική ζυγαριά ακριβείας, να βρούμε ποιο σακί περιέχει τα κάλπικα νομίσματα;

Απάντηση:

• Ιδέα: αριθμούμε τα σακιά 1..10 και παίρνουμε διαφορετικό πλήθος νομισμάτων από το καθένα: 1 από το σακί 1, 2 από το σακί 2, …, 10 από το σακί 10.
• Συνολικά ζυγίζουμε \(1+2+\dots+10=55\) νομίσματα. Αν όλα ήταν γνήσια, το βάρος θα ήταν \(55\times10=550\) g.
• Κάθε κάλπικο νόμισμα «λείπει» 1 g. Αν το κάλπικο είναι το σακί \(k\), πήραμε \(k\) κάλπικα → έλλειμμα \(k\) g.
• Άρα: αριθμός κάλπικου σακιού \(= 550 - (\text{μέτρηση})\). Π.χ. μέτρηση 547 g → έλλειμμα 3 → σακί 3.

Σύνοψη: Παίρνουμε 1,2,…,10 νομίσματα από τα σακιά 1..10 (σύνολο 55). Κάλπικο σακί = 550 − ζυγισμένο βάρος (το έλλειμμα σε g δίνει τον αριθμό).

Κριτήρια αξιολόγησης:

• Έλεγχος: για κάθε \(k=1,\dots,10\) η μέτρηση είναι \(550-k\) g, δηλαδή διαφορετική για κάθε σακί. Το «κλειδί» είναι η μοναδική ταυτότητα κάθε σακιού μέσω διαφορετικού πλήθους νομισμάτων.
• Ανάδειξη εννοιών: αφαίρεση (κρατάμε το βάρος-ταυτότητα) και αναγνώριση προτύπου.

Δραστηριότητα 1 (Πρόβλημα 2) — Το πρόβλημα της Χειραψίας

Ερώτηση: Ας υποθέσουμε ότι είκοσι άνθρωποι βρίσκονται μαζί με έναν μαθητή σε ένα δωμάτιο και πρέπει ο μαθητής να ανταλλάξει χειραψία με κάθε έναν από αυτούς. Με πόσους ανθρώπους τελικά, θα ανταλλάξει χειραψία; Εάν υπάρχουν Ν (Ν>0) άνθρωποι μαζί με το μαθητή στο δωμάτιο, με πόσους τελικά θα έρθει αυτός σε επαφή;

Απάντηση:

• Κατανόηση: γνωστό είναι το πλήθος των ανθρώπων που βρίσκονται μαζί με τον μαθητή (20, και στη γενική περίπτωση Ν). Ζητούμενο είναι με πόσους θα ανταλλάξει χειραψία ο μαθητής. Συνθήκη: χειραψία ανταλλάσσει μόνο ο μαθητής, με κάθε έναν από τους υπόλοιπους.
• Πλάνο: ο μαθητής πηγαίνει διαδοχικά σε κάθε άνθρωπο του δωματίου· κάθε άνθρωπος προσθέτει ακριβώς μία χειραψία.
• Υλοποίηση: με 20 ανθρώπους ο μαθητής ανταλλάσσει 20 χειραψίες (τον εαυτό του δεν τον μετράμε).
• Γενίκευση: με Ν ανθρώπους μαζί του (Ν>0), ο μαθητής έρχεται σε επαφή με Ν ανθρώπους.

Σύνοψη: Με 20 ανθρώπους ανταλλάσσει 20 χειραψίες· γενικά, με Ν ανθρώπους έρχεται σε επαφή με Ν.

Κριτήρια αξιολόγησης:

• ΠΑΓΙΔΑ: το πρόβλημα ζητά τις χειραψίες μόνο του μαθητή, όχι όλων με όλους· γι' αυτό η απάντηση είναι απλώς Ν και όχι κάποιος πιο σύνθετος τύπος.
• Ο μαθητής δεν μετράει τον εαυτό του στους ανθρώπους του δωματίου.