Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Σεπτέμβριος 2023 — Θέματα 4–6¶

Μεταγραφή από τη φωτογραφία IMG_20230921_150229.jpg (το SEP_23_3.jpg είναι αντίγραφο). [Λείπει από τη φωτογραφία: Θέματα 1–3 της συνεδρίας]

IMG_20230921_150229.jpg¶

ΘΕΜΑ 4 – Μεταβλητές και Διαχείριση Μνήμης (20%)¶

(a) Ποιες είναι οι τιμές των μεταβλητών var1, var2, flag, c μετά την εκτέλεση των παρακάτω εντολών; Αιτιολογήστε την απάντησή σας.

int var1 = 1, var2 = 2, flag = -1, c = -1;
c += (++flag) ? (var1-=10) : (var2+=20);

(b) Ο παρακάτω κώδικας (αριστερά) αρχικοποιεί τον πίνακα ακεραίων Α, διάστασης Ν, και μετά υπολογίζει το άθροισμα των στοιχείων του με ένα for loop. Συμπληρώστε την αναδρομική συνάρτηση recursive_sum στο δεξιό κώδικα, ώστε να υπολογίζει το άθροισμα των στοιχείων του πίνακα με αναδρομή.

// Αριστερός κώδικας
int A[N];
int total = 0;

init(A, N);
for (int i = 0; i < N; i++) total += A[i];

// Δεξιός κώδικας
int recursive_sum(int *A, int N)
{
    ...
}

int A[N];
int total = 0;

init(A, N);
total = recursive_sum(A, N);

ΘΕΜΑ 5 – Python (15%)¶

Δημιουργήστε πρόγραμμα σε Python σχετικά με την παραγγελιοληψία σε ένα εστιατόριο. Τα ζητούμενα του προγράμματος είναι τα εξής: 1. Λίστα με τα διαθέσιμα πιάτα και τις τιμές τους. 2. Να μπορεί ο χρήστης να επιλέξει ποια πιάτα θέλει να παραγγείλει και τις ποσότητες τους. 3. Να υπολογίζεται το συνολικό κόστος της παραγγελίας. 4. Να εκτυπώνεται η απόδειξη της παραγγελίας με τα πιάτα, τις ποσότητες και το συνολικό κόστος.

ΘΕΜΑ 6 – Functional Programming (15%)¶

Σε μία γλώσσα συναρτησιακού προγραμματισμού, θεωρείστε τους κάτωθι κανόνες αναγωγής (reduction rules). - Built-in rules: addition, substraction, multiplication, division - User supplied rules:

square x = x * x
double x = x + x
sum [ ] = 0
sum (x:xs) = x + sum [x+1:xs]

Δώστε όλα τα ενδιάμεσα βήματα αναγωγής μέχρι την τελική αποτίμηση της έκφρασης square (sum [1:10]) με πρόθυμη (eager evaluation) και οκνηρή (lazy evaluation) στρατηγική αποτίμησης. Πόσα βήματα (reductions) απαιτεί η κάθε στρατηγική; Ποια είναι η πιο αποδοτική;

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: migrated from previous_exams.md (Antigravity, 2026-10)

Προσοχή

Θέμα 5: ο κώδικας της λύσης δεν είναι έγκυρη Python (αλλαγές γραμμής μέσα σε συμβολοσειρές στις εντολές print) και χρησιμοποιεί σταθερή παραγγελία αντί για είσοδο από τον χρήστη, όπως ζητά η εκφώνηση. Θέμα 6: η λύση χρησιμοποιεί τον κανόνα sum (x:xs) = x + sum xs, ενώ η εκφώνηση έχει sum (x:xs) = x + sum [x+1:xs]. Τα βήματα και το πλήθος των αναγωγών πρέπει να ελεγχθούν ξανά με τον κανόνα της εκφώνησης.

Λύσεις — Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Σεπτέμβριος 2023¶

Λύσεις που μεταφέρθηκαν από το παλιό συγκεντρωτικό αρχείο. Δεν έχουν επαληθευτεί· οι ασυμφωνίες με την εκφώνηση σημειώνονται στα warnings του αρχείου.

(α) Τελεστής Προσαύξησης & Τριαδικός Τελεστής:

Ανάλυση:
++flag: Η τιμή του flag αυξάνεται από -1 σε 0.
Στη C, το \(0\) αντιστοιχεί σε λογικό false.
Άρα εκτελείται ο δεύτερος κλάδος του τριαδικού τελεστή: (var2 += 20).
var2 γίνεται \(2 + 20 = \mathbf{22}\).
Ο πρώτος κλάδος (var1 -= 10) δεν αποτιμάται (short-circuit), άρα var1 = \mathbf{1}.
Η έκφραση επιστρέφει \(22\), οπότε c += 22 \(\implies c = -1 + 22 = \mathbf{21}\).
Τελικές τιμές: var1 = 1, var2 = 22, flag = 0, c = 21.

(β) Μετατροπή For Loop σε Αναδρομική Συνάρτηση:

int recursive_sum(int *A, int N) {
    if (N <= 0) {
        return 0;
    }
    return A[N - 1] + recursive_sum(A, N - 1);
}

# Μενού διαθέσιμων πιάτων και τιμών
menu = {
    "Χωριάτικη Σαλάτα": 6.5,
    "Μουσακάς": 9.0,
    "Σουβλάκι Μερίδα": 8.5,
    "Μπριζόλα": 10.0,
    "Αναψυκτικό": 2.0
}

order = {}
print("=== ΜΕΝΟΥ ΕΣΤΙΑΤΟΡΙΟΥ ===")
for item, price in menu.items():
    print(f"{item}: {price:.2f}€")

# Παράδειγμα παραγγελίας
order["Μουσακάς"] = 2
order["Χωριάτικη Σαλάτα"] = 1
order["Αναψυκτικό"] = 2

# Υπολογισμός και εκτύπωση απόδειξης
total_cost = 0.0
print("
=== ΑΠΟΔΕΙΞΗ ΠΑΡΑΓΓΕΛΙΑΣ ===")
for item, qty in order.items():
    cost = qty * menu[item]
    total_cost += cost
    print(f"{item} x {qty} = {cost:.2f}€")
print(f"---------------------------
ΣΥΝΟΛΙΚΟ ΚΟΣΤΟΣ: {total_cost:.2f}€")

Πρόθυμη Αποτίμηση (Eager / Applicative-Order Evaluation):
Πρώτα αποτιμάται το όρισμα της square, δηλαδή το sum [1:10].
sum [1:10] \(\to 1 + \text{sum}[2:10] \to \dots \to 1 + 2 + \dots + 10 = 55\). (Απαιτεί 10 βήματα αναγωγής του sum + 9 προσθέσεις = 19 βήματα).
Στη συνέχεια: square 55 \(\to 55 * 55 = 3025\). (1 βήμα πολλαπλασιασμού).
Σύνολο: Το sum υπολογίζεται μόνο μία φορά. Πολύ αποδοτική στρατηγική!
Οκνηρή Αποτίμηση (Lazy / Normal-Order Evaluation χωρίς μοίρασμα/memoization):
Πρώτα αναπτύσσεται ο εξωτερικός κανόνας της square: square (sum [1:10]) \(\to (\text{sum } [1:10]) * (\text{sum } [1:10])\).
Τώρα το sum [1:10] εμφανίζεται δύο φορές!
Αν δεν υπάρχει sharing (call-by-need), το άθροισμα \(1+2+\dots+10\) θα υπολογιστεί δύο φορές, διπλασιάζοντας τον αριθμό των βημάτων αναγωγής.
Με Call-by-Need (Lazy Evaluation with Graph Reduction / Sharing): Ο κόμβος sum [1:10] αποτιμάται μία φορά και η τιμή \(55\) διαμοιράζεται και στους δύο παράγοντες, επιστρέφοντας \(3025\).
Συμπέρασμα αποδοτικότητας: Η πρόθυμη αποτίμηση (ή η οκνηρή με μοίρασμα) είναι σαφώς πιο αποδοτική από την απλή οκνηρή αποτίμηση χωρίς memoization.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή