Λύσεις — Κεφάλαιο 12: Εισαγωγή στην Υπολογιστική Σκέψη (σελ. 232-233) – ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ ΥΠΟΛΟΓΙΣΤΩΝ Γ΄ ΕΠΑΛ

Λύσεις — Κεφάλαιο 12: Εισαγωγή στην Υπολογιστική Σκέψη (σελ. 232-233)

Λύσεις της Δραστηριότητας 1 (τρία προβλήματα: κάλπικα νομίσματα, χειραψία, ρέστα-βελτιστοποίηση), της Δραστηριότητας 2 (αυτοκίνητα — γενίκευση σε συνάρτηση), της Δραστηριότητας 3 (πύργοι του Ανόι) και των 4 Ερωτήσεων του κεφαλαίου 12.

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

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

Απάντηση:

• Κατανόηση του προβλήματος. Γνωστά: 10 σακιά × 100 νομίσματα· γνήσιο νόμισμα 10 g, κάλπικο 9 g· ένα σακί έχει μόνο κάλπικα· διαθέτουμε ηλεκτρονική ζυγαριά ακριβείας (δείχνει το ακριβές βάρος σε γραμμάρια). Άγνωστο: ποιο από τα 10 σακιά είναι το κάλπικο. Ζητούμενο: να εντοπιστεί το σακί. Συνθήκες: μία μόνο ζύγιση· επιτρέπεται να βγάλουμε νομίσματα από τα σακιά και να ζυγίσουμε ό,τι θέλουμε μαζί.
• Πλάνο — η ιδέα (αφαίρεση): αν ζυγίζαμε ένα σακί τη φορά θα χρειαζόμασταν έως 9 ζυγίσεις. Με μία ζύγιση πρέπει η μία μέτρηση να «κωδικοποιεί» την ταυτότητα του σακιού. Παίρνουμε διαφορετικό πλήθος νομισμάτων από κάθε σακί: 1 νόμισμα από το σακί 1, 2 από το σακί 2, …, 10 από το σακί 10 — συνολικά 1+2+…+10 = 55 νομίσματα — και τα ζυγίζουμε όλα μαζί.
• Υλοποίηση της λύσης: αν όλα ήταν γνήσια, το βάρος θα ήταν 55 × 10 = 550 g. Κάθε κάλπικο νόμισμα «λείπει» 1 g· από το σακί k πήραμε k κάλπικα, άρα το βάρος είναι 550 − k. Επομένως k = 550 − (μετρούμενο βάρος). Παράδειγμα: η ζυγαριά δείχνει 547 g → 550 − 547 = 3 → το κάλπικο είναι το σακί 3. Ως αλγόριθμος: elleimma = 550 - varos; print 'Κάλπικο το σακί', elleimma.
• Ανακεφαλαίωση/συζήτηση: η λύση λειτουργεί επειδή κάθε σακί συνεισφέρει μοναδικό αριθμό νομισμάτων, οπότε το έλλειμμα βάρους (1 έως 10 g) αντιστοιχεί μονοσήμαντα σε ένα σακί — λογική οργάνωση δεδομένων και αναγνώριση προτύπου. Γενίκευση: για N σακιά παίρνουμε 1, 2, …, N νομίσματα (χρειάζονται ≥ N νομίσματα στο σακί N)· με διαφορετική διαφορά βάρους d το σακί είναι (αναμενόμενο − μετρούμενο)/d· αν το κάλπικο σακί μπορεί και να μην υπάρχει, έλλειμμα 0 σημαίνει «όλα γνήσια»· αν τα κάλπικα σακιά μπορεί να είναι περισσότερα, χρειάζονται δυνάμεις του 2 (1, 2, 4, 8, …) ώστε κάθε υποσύνολο να δίνει διαφορετικό έλλειμμα. Επαληθεύτηκε αριθμητικά.

Σύνοψη: Παίρνουμε 1 νόμισμα από το σακί 1, 2 από το 2, …, 10 από το 10 (55 νομίσματα, αναμενόμενο βάρος 550 g) και ζυγίζουμε μία φορά· το σακί με τα κάλπικα είναι το k = 550 − βάρος (π.χ. 547 g → σακί 3). Γενίκευση: N σακιά → 1…N νομίσματα.

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

• Πλήρης δομή (κατανόηση, πλάνο, υλοποίηση, ανακεφαλαίωση) + σωστός τύπος 550 − βάρος.

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

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

Απάντηση:

• Κατανόηση. Γνωστά: στο δωμάτιο είναι ο μαθητής και 20 άλλοι άνθρωποι· ο μαθητής κάνει χειραψία με καθέναν από αυτούς. Άγνωστο/ζητούμενο: το πλήθος των ανθρώπων με τους οποίους θα κάνει χειραψία — και μετά γενίκευση για Ν ανθρώπους. Συνθήκες: κάθε χειραψία γίνεται μία φορά με κάθε άτομο· ο μαθητής δεν κάνει χειραψία με τον εαυτό του.
• Πλάνο/σχεδίαση: το πρόβλημα, απαλλαγμένο από περιττές λεπτομέρειες (αφαίρεση), είναι μια απλή καταμέτρηση: ένα άτομο = μία χειραψία. Μπορούμε να το επαληθεύσουμε σε μικρή κλίμακα (διάσπαση): 1 άνθρωπος → 1 χειραψία, 2 → 2, 3 → 3 … (αναγνώριση προτύπου).
• Υλοποίηση: με 20 ανθρώπους ο μαθητής θα ανταλλάξει χειραψία με 20 ανθρώπους (20 χειραψίες). Γενίκευση: με Ν ανθρώπους (Ν > 0) θα έρθει σε επαφή με Ν ανθρώπους — η λύση είναι η συνάρτηση f(N) = N. Αλγοριθμικά: N = input('Άνθρωποι στο δωμάτιο: '); print 'Ο μαθητής θα κάνει', N, 'χειραψίες'.
• Ανακεφαλαίωση/συζήτηση: η προσοχή στη διατύπωση είναι το κλειδί — η αρχική διατύπωση παρασύρει σε πιο πολύπλοκο πρόβλημα. Παραλλαγή (επέκταση): αν όλοι οι παρόντες (Ν + 1 άτομα, μαζί με τον μαθητή) ανταλλάξουν χειραψία μεταξύ τους ανά δύο, οι χειραψίες είναι (Ν+1)·Ν/2 — για 21 άτομα 21·20/2 = 210 (κάθε ζεύγος μετριέται μία φορά· καθένας κάνει Ν χειραψίες, αλλά κάθε χειραψία ανήκει σε δύο άτομα). Το βιβλίο (σελ. 229) τονίζει ότι πολλά προβλήματα λύνονται με περισσότερους τρόπους αν αναδιατυπώσουμε το ερώτημα.

Σύνοψη: Με 20 ανθρώπους → 20 χειραψίες· με Ν ανθρώπους → Ν (f(N) = N). Παραλλαγή «όλοι με όλους» (Ν+1 άτομα): (Ν+1)·Ν/2 — για 21 άτομα 210.

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

• Απάντηση 20 / Ν με δομή κατανόησης-πλάνου· η παραλλαγή είναι προαιρετική επέκταση.

Δραστηριότητα 1 — Πρόβλημα 3: Βελτιστοποίηση — ρέστα αυτόματου μηχανήματος εισιτηρίων

Ερώτηση: Να μελετηθεί το πρόβλημα που θα υπολογίζει τα ρέστα που πρέπει να δώσει ένα αυτόματο μηχάνημα έκδοσης εισιτηρίων. Τα εισιτήρια κοστίζουν 0.95€. Ο αλγόριθμος θα δέχεται το ποσό που πληρώνει ο πελάτης και θα επιστρέφει τον αριθμό των κερμάτων με αξία 2€, 1€, 0.50€, 0.20€, 0.10€. Ο αλγόριθμος πρέπει να λειτουργεί με τέτοιο τρόπο, ώστε τα ρέστα να δίνονται με το μικρότερο δυνατό (βελτιστοποίηση) αριθμό νομισμάτων.

Απάντηση:

• Κατανόηση. Γνωστά: τιμή εισιτηρίου 0,95 €· διαθέσιμα κέρματα ρέστων 2, 1, 0,50, 0,20, 0,10 €· το ποσό που πληρώνει ο πελάτης (είσοδος). Άγνωστο: πόσα κέρματα από κάθε είδος. Ζητούμενο: τα ρέστα (ποσό − 0,95) με το ελάχιστο πλήθος κερμάτων. Συνθήκες: το ποσό ≥ 0,95· ρέστα = ποσό − 0,95· τα κέρματα του μηχανήματος δεν περιλαμβάνουν 0,05 €, οπότε ό,τι υπόλοιπο μικρότερο από 0,10 € δεν μπορεί να δοθεί (το επισημαίνουμε).
• Πλάνο — «άπληστος» (greedy) αλγόριθμος: για ελάχιστο πλήθος κερμάτων δίνουμε κάθε φορά όσο το δυνατόν περισσότερα από το μεγαλύτερο κέρμα που χωράει στο υπόλοιπο, και συνεχίζουμε με το επόμενο μικρότερο — όπως στο παράδειγμα «Ρέστα» του κεφ. 8 (σελ. 135). Για τα νομίσματα του ευρώ (κάθε κέρμα είναι πολλαπλάσιο ή «καλύπτεται» από τα μικρότερα) ο άπληστος αλγόριθμος δίνει πάντα τη βέλτιστη λύση. Αφαίρεση/οργάνωση δεδομένων: δουλεύουμε σε λεπτά (ακέραιοι: 95, 200, 100, 50, 20, 10) για να αποφύγουμε σφάλματα στρογγυλοποίησης των πραγματικών αριθμών· τα κέρματα σε λίστα ταξινομημένη φθίνουσα.

• # Ρέστα με το ελάχιστο πλήθος κερμάτων (άπληστος αλγόριθμος) - υπολογισμοί σε λεπτά
  timi = 95                                   # 0.95 ευρώ σε λεπτά
  kermata = [200, 100, 50, 20, 10]            # 2, 1, 0.50, 0.20, 0.10 ευρώ (φθίνουσα σειρά)
  poso = input('Ποσό που πληρώνει ο πελάτης (ευρώ): ')
  resta = int(round(poso * 100)) - timi       # ρέστα σε λεπτά
  if resta < 0:
      print 'Το ποσό δεν επαρκεί'
  else:
      print 'Ρέστα:', resta / 100.0, 'ευρώ'
      for kerma in kermata:
          plithos = resta / kerma             # ακέραια διαίρεση: πόσα τέτοια κέρματα χωρούν
          resta = resta % kerma               # ό,τι απομένει
          if plithos > 0:
              print plithos, 'x', kerma / 100.0, 'ευρώ'
      if resta > 0:
          print 'Υπόλοιπο', resta / 100.0, 'ευρώ δεν μπορεί να δοθεί με τα διαθέσιμα κέρματα'

• Παράδειγμα (επαληθευμένο): πληρωμή 5 € → ρέστα 4,05 € → 2 × 2 € (υπόλοιπο 0,05 € μη αποδοτέο)· πληρωμή 2 € → 1,05 € → 1 × 1 € + 0,05 μη αποδοτέο· πληρωμή 1 € → 0,05 € → κανένα κέρμα, μη αποδοτέο. Αν το εισιτήριο κόστιζε 0,90 € ή αν υπήρχε κέρμα 0,05 €, το υπόλοιπο θα μηδενιζόταν πάντα — γι' αυτό το μηχάνημα στην πράξη θα έπρεπε να δέχεται και να δίνει 0,05 €.
• Ανακεφαλαίωση/συζήτηση — βελτιστοποίηση: ο άπληστος αλγόριθμος είναι αποδοτικός (ένα πέρασμα στη λίστα των κερμάτων, πολυπλοκότητα ανάλογη του πλήθους των ειδών) και βέλτιστος για το σύστημα κερμάτων του ευρώ· σε ένα «περίεργο» σύστημα (π.χ. κέρματα 1, 3, 4 και ρέστα 6) ο άπληστος δίνει 4+1+1 (3 κέρματα) ενώ το βέλτιστο είναι 3+3 (2) — τότε χρειάζεται εξαντλητική αναζήτηση/δυναμικός προγραμματισμός. Γενίκευση: ο ίδιος αλγόριθμος με άλλη λίστα κερμάτων (και χαρτονομισμάτων) ή άλλη τιμή· η αξιολόγηση της λύσης περιλαμβάνει και τον έλεγχο των ακραίων περιπτώσεων (ανεπαρκές ποσό, μη αποδοτέο υπόλοιπο, εξάντληση κερμάτων στο μηχάνημα).

Σύνοψη: Άπληστος αλγόριθμος: ρέστα = ποσό − 0,95 (σε λεπτά), για κάθε κέρμα από το μεγαλύτερο (200, 100, 50, 20, 10) πλήθος = ρέστα // κέρμα, ρέστα = ρέστα % κέρμα· επισήμανση μη αποδοτέου υπολοίπου < 0,10 (δεν υπάρχει 0,05)· π.χ. 5 € → 2 × 2 € + 0,05. Βέλτιστος για τα κέρματα του ευρώ.

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

• Δομή κατανόησης-πλάνου + κώδικας άπληστου αλγορίθμου σε λεπτά + παράδειγμα + σχόλιο βελτιστοποίησης.

Δραστηριότητα 2 (Γενίκευση) — Σε πόσα χρόνια τα αυτοκίνητα θα ξεπεράσουν τις 160000

Ερώτηση: Ο σημερινός αριθμός αυτοκινήτων που κυκλοφορούν σε μια πόλη είναι 90000. Αν ο αριθμός αυτός αυξάνεται με ετήσιο ρυθμό 5%, να γραφεί σενάριο σε Python που υπολογίζει σε πόσα χρόνια ο αριθμός των αυτοκινήτων θα ξεπεράσει τις 160000. Να εμφανίζει πόσα θα είναι τότε τα αυτοκίνητα. Γενικεύστε το πρόγραμμα για Arith_Aytok αυτοκίνητα, που αυξάνονται με ετήσιο ρυθμό (Rythmos) και ξεπερνούν ένα δοσμένο όριο (Orio). Τέλος, να οπτικοποιηθεί ο κώδικας στο pythontutor.com.

Απάντηση:

• Ανάλυση: κάθε χρόνο τα αυτοκίνητα γίνονται 1,05 φορές τα περσινά (αύξηση 5%). Δεν ξέρουμε εκ των προτέρων πόσες επαναλήψεις χρειάζονται → δομή while με συνθήκη «όσο τα αυτοκίνητα δεν ξεπερνούν το όριο»· σε κάθε επανάληψη αυξάνουμε τα αυτοκίνητα και μετράμε ένα έτος.

• # Συγκεκριμένο πρόβλημα
  aytokinita = 90000.0
  xronia = 0
  while aytokinita <= 160000:
      aytokinita = aytokinita * 1.05       # αύξηση 5% ανά έτος
      xronia = xronia + 1
  print 'Τα αυτοκίνητα θα ξεπεράσουν τις 160000 σε', xronia, 'χρόνια'
  print 'Τότε θα είναι', int(aytokinita), 'αυτοκίνητα'

• Αποτέλεσμα (επαληθευμένο): σε 12 χρόνια, οπότε θα είναι 161627 αυτοκίνητα (90000 × 1,05¹² ≈ 161627,1· στα 11 χρόνια είναι 153930 < 160000).

• Γενίκευση — τα τρία δεδομένα γίνονται παράμετροι (συνάρτηση ή είσοδος από τον χρήστη), ώστε το ίδιο πρόγραμμα να λύνει κάθε πρόβλημα «εκθετικής αύξησης μέχρι ένα όριο» (πληθυσμός, κεφάλαιο με τόκο, βακτήρια):

• def xronia_gia_orio(Arith_Aytok, Rythmos, Orio):
      # Επιστρέφει (χρόνια, τελικό πλήθος) μέχρι το Arith_Aytok να ξεπεράσει το Orio
      # με ετήσιο ρυθμό αύξησης Rythmos (ποσοστό %)
      xronia = 0
      plithos = float(Arith_Aytok)
      while plithos <= Orio:
          plithos = plithos * (1 + Rythmos / 100.0)
          xronia = xronia + 1
      return xronia, plithos
  
  Arith_Aytok = input('Σημερινός αριθμός αυτοκινήτων: ')
  Rythmos = input('Ετήσιος ρυθμός αύξησης (%): ')
  Orio = input('Όριο: ')
  xronia, plithos = xronia_gia_orio(Arith_Aytok, Rythmos, Orio)
  print 'Το όριο', Orio, 'ξεπερνιέται σε', xronia, 'χρόνια, με', int(plithos), 'αυτοκίνητα'

• Έλεγχος: xronia_gia_orio(90000, 5, 160000) → (12, 161627.1) — ίδιο με το συγκεκριμένο πρόγραμμα. Προσοχή: αν ο ρυθμός είναι 0 ή αρνητικός και το όριο μεγαλύτερο του αρχικού πλήθους, ο βρόχος δεν τερματίζει — μια ολοκληρωμένη λύση ελέγχει Rythmos > 0. Η οπτικοποίηση στο pythontutor.com γίνεται επικολλώντας τον κώδικα (επιλογή Python 2.7) και πατώντας «Visualize Execution»: βήμα-βήμα φαίνονται οι τιμές των aytokinita/xronia σε κάθε επανάληψη — ενέργεια για την τάξη, δεν αποτυπώνεται εδώ.

Σύνοψη: while aytokinita <= 160000: aytokinita = 1.05; xronia += 1 → 12 χρόνια, 161627 αυτοκίνητα. Γενίκευση: συνάρτηση xronia_gia_orio(Arith_Aytok, Rythmos, Orio) με while plithos <= Orio: plithos = (1 + Rythmos/100.0)· είσοδος από τον χρήστη.

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

• Σωστό αποτέλεσμα (12 / 161627) + γενικευμένο πρόγραμμα με παραμέτρους.

Δραστηριότητα 3 (Γενίκευση) — Οι πύργοι του Ανόι: 3 δίσκοι, 4 δίσκοι, γενίκευση

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

Απάντηση:

• Το πρόβλημα: τρεις στύλοι Α (αρχικός), Β (βοηθητικός), Γ (τελικός) και n δίσκοι διαφορετικού μεγέθους στοιβαγμένοι στον Α, ο μεγαλύτερος κάτω. Ζητείται να μεταφερθούν όλοι στον Γ με κανόνες: ένας δίσκος τη φορά (ο πάνω-πάνω κάποιου στύλου) και ποτέ μεγαλύτερος πάνω σε μικρότερο.

• Τρεις δίσκοι (μικρός 1, μεσαίος 2, μεγάλος 3) — 7 κινήσεις σε φυσική γλώσσα: ① τον δίσκο 1 από Α στον Γ· ② τον 2 από Α στον Β· ③ τον 1 από Γ στον Β (τώρα ο Β έχει 1 πάνω στο 2)· ④ τον 3 από Α στον Γ (ο μεγάλος στη θέση του)· ⑤ τον 1 από Β στον Α· ⑥ τον 2 από Β στον Γ· ⑦ τον 1 από Α στον Γ. Παρατήρηση (αναγνώριση προτύπου): οι κινήσεις ①-③ μεταφέρουν τους δύο μικρότερους δίσκους στον βοηθητικό Β, η ④ μεταφέρει τον μεγαλύτερο, και οι ⑤-⑦ μεταφέρουν ξανά τους δύο μικρότερους από τον Β πάνω στον Γ — δηλαδή η λύση για 3 δίσκους χρησιμοποιεί δύο φορές τη λύση για 2 δίσκους (που είναι 3 κινήσεις).

• Τέσσερις δίσκοι — αξιοποίηση της λύσης των 3: ① μεταφέρουμε τους τρεις μικρότερους από τον Α στον Β (με τη λύση των 3 δίσκων, 7 κινήσεις, χρησιμοποιώντας τον Γ ως βοηθητικό)· ② μεταφέρουμε τον δίσκο 4 από τον Α στον Γ (1 κίνηση)· ③ μεταφέρουμε τους τρεις μικρότερους από τον Β στον Γ (πάλι 7 κινήσεις, με τον Α βοηθητικό). Σύνολο 7 + 1 + 7 = 15 κινήσεις.

• Γενίκευση για n δίσκους (διάσπαση σε υποπροβλήματα — αναδρομή): «Για να μεταφέρεις n δίσκους από τον Α στον Γ με βοηθητικό τον Β: αν n = 1, μετέφερε τον δίσκο απευθείας· αλλιώς μετέφερε τους n−1 πάνω δίσκους από Α στον Β (βοηθητικός ο Γ), μετά τον n-οστό από Α στον Γ, και τέλος τους n−1 από Β στον Γ (βοηθητικός ο Α)». Πλήθος κινήσεων: K(1) = 1, K(n) = 2·K(n−1) + 1 → 1, 3, 7, 15, 31, … = 2ⁿ − 1 (για 10 δίσκους 1023, για 64 δίσκους ≈ 1,8·10¹⁹ — ο θρύλος των μοναχών). Η ίδια διαδικασία εφαρμόζεται σε οποιοδήποτε πλήθος δίσκων — μεταφορά της λύσης (γενίκευση).

• def hanoi(n, apo, pros, voithitikos):
      # Μεταφέρει n δίσκους από τον στύλο apo στον pros με βοηθητικό τον voithitikos
      if n == 1:
          print 'Δίσκος 1 από', apo, 'στον', pros
      else:
          hanoi(n - 1, apo, voithitikos, pros)     # οι n-1 μικρότεροι στον βοηθητικό
          print 'Δίσκος', n, 'από', apo, 'στον', pros
          hanoi(n - 1, voithitikos, pros, apo)     # οι n-1 μικρότεροι πάνω στον μεγάλο
  
  hanoi(3, 'A', 'Γ', 'B')     # 7 κινήσεις - επαληθευμένο

• Το πρόγραμμα για n = 3 τυπώνει ακριβώς τις 7 κινήσεις της φυσικής γλώσσας (1: Α→Γ, 2: Α→Β, 1: Γ→Β, 3: Α→Γ, 1: Β→Α, 2: Β→Γ, 1: Α→Γ) και για n = 4 τις 15 (επαληθεύτηκε με εκτέλεση). Η οπτικοποίηση του Φωτόδεντρου βοηθά να δούμε τη διάσπαση «n−1 + 1 + n−1» — ενέργεια στην τάξη.

Σύνοψη: 3 δίσκοι: 7 κινήσεις (1 Α→Γ, 2 Α→Β, 1 Γ→Β, 3 Α→Γ, 1 Β→Α, 2 Β→Γ, 1 Α→Γ) = λύση 2 δίσκων προς Β, ο μεγάλος στον Γ, λύση 2 δίσκων προς Γ. 4 δίσκοι: 3 δίσκοι στον Β (7), δίσκος 4 στον Γ (1), 3 δίσκοι στον Γ (7) = 15. Γενικά: n−1 στον βοηθητικό, ο n-οστός στον τελικό, n−1 στον τελικό — 2ⁿ − 1 κινήσεις (αναδρομική συνάρτηση hanoi).

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

• Λύση 3 δίσκων σε φυσική γλώσσα + χρήση της για 4 + γενικός κανόνας/τύπος 2ⁿ − 1.

Ερώτηση 1 — Πέντε βασικά χαρακτηριστικά της υπολογιστικής σκέψης

Ερώτηση: Να αναφερθούν πέντε βασικά χαρακτηριστικά της υπολογιστικής σκέψης.

Απάντηση:

• Από τη λίστα της ενότητας 12.2 (σελ. 229-230) — πέντε βασικά χαρακτηριστικά: ① Μορφοποίηση προβλημάτων με τρόπο που επιτρέπει τη χρήση υπολογιστή και άλλων εργαλείων για την επίλυσή τους. ② Εννοιολογική αφαίρεση και επιλογή της απαραίτητης πληροφορίας για την αντιμετώπιση της πολυπλοκότητας των σύνθετων προβλημάτων. ③ Διάσπαση ενός προβλήματος σε απλούστερα υποπροβλήματα. ④ Αυτοματοποίηση των λύσεων μέσα από την περιγραφή τους με αλγοριθμικό τρόπο. ⑤ Γενίκευση και μεταφορά της διαδικασίας επίλυσης σε ευρύτερη ποικιλία προβλημάτων.
• Άλλα χαρακτηριστικά της ίδιας λίστας: λογική οργάνωση και ανάλυση δεδομένων· αναπαράσταση δεδομένων μέσα από μοντέλα και προσομοιώσεις· αναγνώριση, ανάλυση και υλοποίηση πιθανών λύσεων (αποτελεσματικότεροι/αποδοτικότεροι συνδυασμοί βημάτων και πόρων)· αξιολόγηση του αλγορίθμου και της λύσης· κατανόηση της ανθρώπινης συμπεριφοράς κατά την αντιμετώπιση προβλήματος. Επίσης (σελ. 227): αναπαράσταση δεδομένων μέσω αφαιρέσεων, βελτιστοποίηση λύσης.

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

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

• Πέντε χαρακτηριστικά από τη λίστα του βιβλίου, με σύντομη εξήγηση.

Ερώτηση 2 — Τρία καθημερινά παραδείγματα υπολογιστικής σκέψης

Ερώτηση: Να αναφερθούν τρία καθημερινά παραδείγματα υπολογιστικής σκέψης.

Απάντηση:

• Από τα παραδείγματα του βιβλίου (σελ. 228-229): ① Εύρεση της συντομότερης διαδρομής από το σπίτι στο σχολείο: μορφοποίηση του προβλήματος, αφαίρεση των περιττών στοιχείων, επισήμανση των βασικών κόμβων των εναλλακτικών διαδρομών στον χάρτη, χάραξη κάθε διαδρομής (μοντελοποίηση) και αναπαράστασή της με κατάλληλη δομή δεδομένων. ② Η ουρά στο ταμείο του supermarket: ανάλυση του τρόπου εξυπηρέτησης, αναγνώριση των βασικών λειτουργιών εισαγωγής/εξαγωγής (FIFO), μοντελοποίηση και αλγοριθμική περιγραφή. ③ Εύρεση λήμματος σε πολυσέλιδη εγκυκλοπαίδεια (ή ονόματος σε κατάλογο): σειριακή έναντι δυαδικής αναζήτησης, επιλογή της αποδοτικότερης και γενίκευση σε παρόμοια προβλήματα αναζήτησης.
• Επίσης από το βιβλίο: ο προγραμματισμός εκπαιδευτικού ρομπότ για έξοδο από λαβύρινθο (κανόνας δεξιού/αριστερού χεριού)· η σχεδίαση σπιτιού με γεωμετρικά σχήματα (αφαίρεση σε τετράγωνο/τρίγωνο, επαναλαμβανόμενες διαδικασίες, υλοποίηση με turtle)· η διανομή γάλακτος σε μια πόλη ή η πρόγνωση φυσικού φαινομένου με μοντέλα. Άλλα καθημερινά: η συνταγή μαγειρικής ως αλγόριθμος με διάσπαση σε βήματα· το πακετάρισμα βαλίτσας (επιλογή απαραίτητων — αφαίρεση, οργάνωση χώρου — βελτιστοποίηση)· ο προγραμματισμός της ημέρας (διάσπαση εργασιών, προτεραιότητες).

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

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

• Τρία παραδείγματα με το χαρακτηριστικό ΥΣ που αναδεικνύει καθένα.

Ερώτηση 3 — Η λειτουργία της Αφαίρεσης για την κατανόηση σύνθετων προβλημάτων

Ερώτηση: Να περιγραφεί σύντομα η λειτουργία της Αφαίρεσης για την κατανόηση σύνθετων προβλημάτων.

Απάντηση:

• Αφαίρεση (abstraction) είναι η νοητική ικανότητα εντοπισμού των βασικών χαρακτηριστικών ενός αντικειμένου ή, γενικότερα, μιας κατάστασης (σελ. 230). Για να αναλύσουμε ένα σύνθετο πρόβλημα και να εντοπίσουμε τα δομικά/κύρια στοιχεία του, το μορφοποιούμε ώστε να απαλλαγεί από τις περιττές λεπτομέρειες που αυξάνουν χωρίς λόγο τον όγκο των στοιχείων που πρέπει να διαχειριστούμε — κρατάμε μόνο την απαραίτητη πληροφορία (εννοιολογική αφαίρεση, χαρακτηριστικό ② της ΥΣ).
• Αξία: επιτρέπει την κριτική επεξεργασία των δεδομένων και την ανακάλυψη σχέσεων μεταξύ αντικειμένων ή καταστάσεων· είναι απαραίτητη για τη σωστή ανάλυση σε απλούστερα υποπροβλήματα και τη σαφή διατύπωση της δομής του προβλήματος. Η σύλληψη εννοιών απαιτεί σκέψη σε πολλαπλά επίπεδα αφαίρεσης. Παραδείγματα (σελ. 231): στον υπολογισμό του χρόνου μετάβασης ενός οχήματος το χρώμα του δεν είναι βασικό χαρακτηριστικό, ενώ η ταχύτητα και οι εναλλακτικές διαδρομές είναι· η αφαίρεση μας επιτρέπει να θεωρήσουμε ότι ένα όχημα Φόρμουλα 1 και ένα τετρακίνητο τζιπ είναι και τα δύο αυτοκίνητα· στα Μαθηματικά, η απόδοση του αγνώστου στο Χ είναι αφαιρετική διαδικασία. Στον προγραμματισμό, οι συναρτήσεις (και οι κλάσεις) προσφέρουν υψηλό επίπεδο αφαίρεσης — χρησιμοποιούμε τη λειτουργία χωρίς τις λεπτομέρειες υλοποίησης.

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

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

• Ορισμός + αξία + ένα παράδειγμα.

Ερώτηση 4 — Η λειτουργία της Γενίκευσης της διαδικασίας επίλυσης προβλήματος

Ερώτηση: Να περιγραφεί σύντομα η λειτουργία της Γενίκευσης της διαδικασίας επίλυσης προβλήματος.

Απάντηση:

• Γενίκευση είναι η μεταφορά της διαδικασίας επίλυσης ενός συγκεκριμένου προβλήματος σε μια ευρύτερη ποικιλία προβλημάτων (χαρακτηριστικό ⑨ της ΥΣ, σελ. 230· «γενίκευση και μεταφορά μιας διαδικασίας επίλυσης σε ποικιλία προβλημάτων», σελ. 227). Αφού λύσουμε ένα πρόβλημα, αναγνωρίζουμε ποια στοιχεία της λύσης είναι ουσιώδη και ποια ήταν απλώς τα συγκεκριμένα δεδομένα (αριθμοί, ονόματα, μεγέθη), και αντικαθιστούμε τα τελευταία με παραμέτρους — έτσι η λύση γίνεται γενική μέθοδος (αλγόριθμος/συνάρτηση) που λύνει όλα τα προβλήματα της ίδιας κατηγορίας, χωρίς να ξαναρχίζουμε από την αρχή.
• Παραδείγματα από το βιβλίο: η εύρεση εξόδου σε λαβυρίνθους διαφορετικού σχήματος με τον ίδιο κανόνα (δεξιού χεριού)· η λύση της αναζήτησης λήμματος (δυαδική αναζήτηση) που γενικεύεται σε κάθε πρόβλημα αναζήτησης σε ταξινομημένα δεδομένα· στις δραστηριότητες του κεφαλαίου, το πρόγραμμα των 90000 αυτοκινήτων που γενικεύεται σε συνάρτηση με παραμέτρους (αρχικό πλήθος, ρυθμός, όριο) και λύνει κάθε πρόβλημα εκθετικής αύξησης, οι πύργοι του Ανόι από 3 δίσκους σε n (2ⁿ − 1 κινήσεις), το πρόβλημα της χειραψίας από 20 σε Ν ανθρώπους. Η γενίκευση συνδέεται με την αφαίρεση (τι είναι ουσιώδες) και με την επαναχρησιμοποίηση κώδικα μέσω συναρτήσεων με παραμέτρους (σελ. 231).

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

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

• Ορισμός + μηχανισμός (παράμετροι) + παράδειγμα.