Μετάβαση στο περιεχόμενο

Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Ιούνιος 2026

Μεταγραφή από τις σελίδες IMG_2424.jpg και IMG_2425.jpg.

IMG_2424.jpg

ΑΡΧΕΣ ΓΛΩΣΣΩΝ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ ΚΑΙ ΜΕΤΑΦΡΑΣΤΩΝ Εξέταση Περιόδου Ιουνίου 2026

ΘΕΜΑ 1 – Συντακτική Ανάλυση (25%)

Δίνεται η παρακάτω απλή BNF γραμματική, με τερματικά σύμβολα τα: 0 1

\[<S> ::= 0<A>0\]
\[<A> ::= 1<A>1 \mid 1011\]

(α) Τι τύπου είναι η γραμματική στην ιεραρχία Chomsky και γιατί;

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

(γ) Ελέγξτε αν η συμβολοσειρά 01101110 είναι μέλος της γλώσσας, παρουσιάζοντας τη Στοίβα Ταιριάσματος – Πρόβλεψης Top-Down συντακτικής ανάλυσης.

(δ) Είναι ή όχι η γραμματική LL(1) και γιατί; Αν όχι, μετασχηματίστε την σε μια ισοδύναμη LL(1) γραμματική. Τι παρατηρείτε στη νέα LL(1) γραμματική;

ΘΕΜΑ 2 – Λεξική Ανάλυση (15%)

(α) Να παρουσιάσετε το διάγραμμα καταστάσεων – μεταβάσεων για το ντετερμινιστικό πεπερασμένο αυτόματο που αναγνωρίζει όλους τους δυαδικούς αριθμούς οι οποίοι: (i) περιέχουν ένα τουλάχιστον 1 και (ii) τα 0 (αν υπάρχουν) εμφανίζονται ένα τη φορά, έχοντας δεξιά και αριστερά τους ένα ή περισσότερα 1. Π.χ. οι αριθμοί 11 110111101.

(β) Γράψετε μια κανονική έκφραση που αντιστοιχεί στο παραπάνω αυτόματο.

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

Ποιες θα είναι οι τελικές τιμές του πίνακα data που θα τυπώσει το παρακάτω πρόγραμμα. Αναφέρετε και εξηγήστε τους υπολογισμούς σας.

void main() {
  int *p, data[] = {6, 12, 18, 24};
  p = &data[2];
  *(p - 2) = *p / 3 + 1;
  p--;
  *(p + 2) = *p * 2 - 1;
  *p += p[1] / 3;
  *(p + 1) = *(p + 2) - *p;
  printf("%d %d %d %d\n", data[0], data[1], data[2], data[3]);
}

ΘΕΜΑ 4 – Εμβέλεια και Μεταβίβαση Παραμέτρων (20%)

Δίνεται το παρακάτω πρόγραμμα σε μια γλώσσα τύπου Pascal στην οποία ισχύει ο στατικός κανόνας εμβέλειας:

program MAIN;
  var b: array[1..3] of integer; k, m: integer;

  procedure Q(u: integer; v: integer);
  begin
    b[1] := b[1] + u;
    b[2] := b[2] + v;
    m := 3;
    u := u + 1;
    b[3] := b[3] + u;
    v := v + u;
  end;

begin
  b[1] := 1; b[2] := 2; b[3] := 3;
  k := 1; m := 2;
  Q(b[m], b[k]);
  writeln('output:', b[1], ' ', b[2], ' ', b[3]);
end

Μορφή εξόδου του προγράμματος: output: b_1 b_2 b_3

Πίνακας αποτελεσμάτων

Κλήση με b[1] b[2] b[3]
1. τιμή
2. αναφορά
3. τιμή-αποτέλεσμα
4. όνομα

(a) Ποια είναι τα περιβάλλοντα αναφοράς όλων των τμημάτων του προγράμματος;

(b) Ποιες τιμές θα τυπωθούν στο τέλος για τα b[1], b[2] και b[3] στις παρακάτω περιπτώσεις μεταβίβασης παραμέτρων; Συμπληρώστε τον πίνακα (στην κόλα σας) και παρουσιάστε συνοπτικά τους υπολογισμούς σας.

  1. Κλήση με τιμή (call by value)
  2. Κλήση με αναφορά (call by reference)
  3. Κλήση με τιμή-αποτέλεσμα (call by value-result)
  4. Κλήση με όνομα (call by name)

IMG_2425.jpg

[Λείπει από τη φωτογραφία: αρχή της επικεφαλίδας του Θέματος 5, η οποία είναι κομμένη από την πάνω άκρη· διακρίνεται μόνο το τέλος «…ython (15%)»]

Ένα μετεωρολογικό κέντρο συλλέγει δεδομένα θερμοκρασίας από σταθμούς. Διαθέτει δύο λεξικά με μετρήσεις για δύο διαφορετικές ημέρες και ένα τρίτο λεξικό με τις γεωγραφικές πληροφορίες των σταθμών:

day1_data = {
    'Κωδικός': ['S1', 'S2', 'S3'],
    'Θερμοκρασία': [32.5, 29.0, 34.2]
}
day2_data = {
    'Κωδικός': ['S1', 'S2', 'S4'],
    'Θερμοκρασία': [31.0, 30.2, 28.5]
}
stations_info = {
    'Σταθμός_ID': ['S1', 'S2', 'S3', 'S4'],
    'Πόλη': ['Αθήνα', 'Πάτρα', 'Θεσσαλονίκη', 'Λάρισα'],
    'Υψόμετρο': [20, 15, 5, 75]
}

Γράψτε κώδικες Python, χρησιμοποιώντας τις κατάλληλες μεθόδους, ώστε να εκτελέσετε τα παρακάτω βήματα:

(α) Να δημιουργήσετε τα DataFrames df_d1 και df_d2 από τα αντίστοιχα λεξικά των ημερών και να τα συνενώσετε κάθετα σε ένα ενιαίο DataFrame με όνομα df_all_measurements.

(β) Να δημιουργήσετε το DataFrame df_stations από το λεξικό stations_info. Στη συνέχεια, να συγχωνεύσετε το df_all_measurements με το df_stations σε ένα τελικό DataFrame df_final.

(γ) Στο df_final, να διαγράψετε οριστικά τη στήλη 'Υψόμετρο'.

(δ) Χρησιμοποιώντας τη συνάρτηση iterrows(), να γράψετε ένα βρόχο επανάληψης που προσπελαύνει το df_final ανά γραμμή και εμφανίζει στην οθόνη για κάθε εγγραφή το μήνυμα: Πόλη: <τιμή> | Θερμοκρασία: <τιμή>.

ΘΕΜΑ 6 – Functional Programming και Γλώσσες ΒΔ (25%)

(Α) Δίνονται σε γλώσσα Prolog οι παρακάτω 8 προτάσεις (facts) καθώς και ένας κανόνας (rule):

Facts: studies(Charlie, csc135), studies(Olivia, csc135), studies(Jack, csc131), studies(Arthur, csc134), teaches(Sioutas, csc135), teaches(Garofalakis, csc131), teaches(Hadjidoukas, csc171), teaches(Vonitsanos, csc134)

Rules: professor(X, Y) :- teaches(X, C), studies(Y, C).

(α) Σχεδιάστε τις δομές δεδομένων (δέντρα) για τις παραπάνω 8 προτάσεις. Πώς «διαβάζονται» οι παραπάνω προτάσεις;

(β) Οι κανόνες είναι θεωρήματα που επιτρέπουν στο διερμηνέα να συναγάγει την αλήθεια προτάσεων. Πως διαβάζεται ο παραπάνω κανόνας;

(γ) Γράψτε σε γλώσσα Prolog τα ακόλουθα ερωτήματα: (γ1) Τι μελετάει ο Charlie //charlie studies what?// (γ2) Ποιοι είναι οι μαθητές του Καθηγητή Garofalakis // Who are the students of professor Garofalakis?//

(B) Έστω μία βάση δεδομένων με δύο πίνακες (σχέσεις) R1(A,B,C) και R2(C, E, F) οι οποίοι συσχετίζονται στην κοινή στήλη (γνώρισμα) C και έστω ο παρακάτω κώδικας σε γλώσσα SQL:

Select A
From R1,R2
Where R1.C=R2.C and C<400

Περιγράψτε όλα τα ενδιάμεσα πλάνα εκτέλεσης που παράγει ο SQL Compiler για το παραπάνω ερώτημα μέχρι την εύρεση του τελικού πλάνου που είναι και το βέλτιστο. Θυμίζουμε την ύπαρξη ενσωματωμένου βελτιστοποιητή (embedded optimizer) ο οποίος μετατρέπει τον SQL κώδικα σε ισοδύναμη μορφή σχεσιακής άλγεβρας και στη συνέχεια εφαρμόζει τους γνωστούς ευριστικούς κανόνες βελτιστοποίησης. Σημειώνουμε ότι η στήλη C δέχεται αριθμητικές τιμές.

(Γ) (α) Κάνοντας χρήση της Python lambda map function, γράψτε πρόγραμμα το οποίο με μία και μόνο βασική εντολή, θα υπολογίζει (και τυπώνει) το άθροισμα των κύβων των ακέραιων αριθμών μιας λίστας L.

(β) Κάνοντας χρήση της Python lambda reduce function, γράψτε πρόγραμμα το οποίο με μία και μόνο βασική εντολή, θα υπολογίζει (και τυπώνει) το άθροισμα των τετραγώνων των ακέραιων αριθμών μιας λίστας L.

(γ) Στον λ-λογισμό, μπορούμε να αναπαραστήσουμε τις λογικές τιμές true και false ως εξής:

\[true \equiv \lambda x.\, \lambda y.\, X, \qquad false \equiv \lambda x.\, \lambda y.\, Y\]

Η αναπαράσταση του λογικού τελεστή not με την έκφραση \(not \equiv \lambda z.\, z\; false\; true\), επιφέρει το επιθυμητό αποτέλεσμα;

(Σημείωση: αρκεί να αποδείξετε ότι not true = false και not false = true)

(Δ) Σε μία γλώσσα συναρτησιακού προγραμματισμού, θεωρείστε τους κάτωθι κανόνες αναγωγής (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:100]) με πρόθυμη στρατηγική αποτίμησης (eager evaluation), οκνηρή στρατηγική αποτίμησης (lazy evaluation) και Γραφο-Υβριδική (Outer-Most Graph Reduction) στρατηγική αποτίμησης. Πόσα βήματα (reductions) απαιτεί η κάθε στρατηγική; Ποια είναι η πιο αποδοτική;

Υποσημείωση εξέτασης: Τα θέματα επιστρέφονται μαζί με το γραπτό. Απαντήστε σε όλα τα θέματα. Η διάρκεια της εξέτασης είναι 2,5 ώρες. ΚΑΛΗ ΕΠΙΤΥΧΙΑ!!!

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

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2026-06

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

Θέμα 1

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Γραμματική: \(S\to0A0\), \(A\to1A1\mid1011\).

(α) Όλοι οι κανόνες έχουν ένα μη τερματικό από τη μία πλευρά (αριστερό μέλος: ένα μη τερματικό) ⇒ context-free, Τύπου 2. Δεν είναι Τύπου 3: ο \(A\to1A1\) έχει το μη τερματικό ανάμεσα σε τερματικά (όχι δεξιά ή αριστερά γραμμικός), και η γλώσσα δεν είναι κανονική, γιατί απαιτεί αντιστοίχιση του πλήθους των 1 δεξιά και αριστερά (απαιτεί μέτρημα).

(β) Εφαρμόζοντας \(n\) φορές τον \(A\to1A1\) και μετά \(A\to1011\): \(A\Rightarrow^* 1^n\,1011\,1^n\). Άρα η γλώσσα είναι \(L=\{\,0\,1^n\,1011\,1^n\,0 \mid n\ge0\,\}\): αρχίζει και τελειώνει με 0, ενδιάμεσα έχει τον πυρήνα 1011 με ίδιο πλήθος 1 εκατέρωθεν. Παραδείγματα: 010110 (\(n=0\)), 01101110 (\(n=1\)), 0111011110 (\(n=2\)). Τα δύο μικρότερα μέλη: 010110 (μήκος 6) και 01101110 (μήκος 8).

(γ) Η 01101110 έχει τη μορφή \(0\,1\,1011\,1\,0\) ⇒ \(n=1\) ⇒ μέλος. Στοίβα ταιριάσματος – πρόβλεψης (κορυφή αριστερά). Στον \(A\) η επιλογή \(A\to1A1\) ή \(A\to1011\) δεν προκύπτει από ένα σύμβολο (και οι δύο ξεκινούν με 1)· χρειάζεται κοίταγμα 2 συμβόλων (11 ⇒ \(1A1\), 10 ⇒ \(1011\)).

Στοίβα Είσοδος Ενέργεια
S$ 01101110$ \(S\to0A0\)
0A0$ 01101110$ ταίριασμα 0
A0$ 1101110$ (11) \(A\to1A1\)
1A10$ 1101110$ ταίριασμα 1
A10$ 101110$ (10) \(A\to1011\)
101110$ 101110$ ταίριασμα 1, 0, 1, 1
10$ 10$ ταίριασμα 1
0$ 0$ ταίριασμα 0
$ $ αποδοχή

Η 01101110 ανήκει στη γλώσσα.

(δ) Δεν είναι LL(1): οι \(A\to1A1\) και \(A\to1011\) έχουν FIRST = {1} και οι δύο (κοινό πρόθεμα 1) ⇒ σύγκρουση. Αριστερή παραγοντοποίηση:

\(S\to0A0\), \(A\to1A'\), \(A'\to A1\mid011\)

Έλεγχος: FIRST(\(A1\))={1}, FIRST(\(011\))={0}, ξένα ⇒ LL(1).

Παρατηρήσεις στη νέα γραμματική: (i) δεν έχει ε-κανόνες ούτε αριστερή αναδρομή· (ii) η γλώσσα είναι η ίδια, μένει context-free μη κανονική (η αναδρομή στο κέντρο παραμένει), (iii) η προηγούμενη ανάγκη κοιτάγματος 2 συμβόλων (LL(2)) έγινε LL(1) με την παραγοντοποίηση, αφού ο \(A'\) διαλέγει με το επόμενο σύμβολο (1 ⇒ συνέχεια της αναδρομής, 0 ⇒ ο πυρήνας 011).

Θέμα 2

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Η γλώσσα: τουλάχιστον ένα 1· κάθε 0 μόνο του και με 1 εκατέρωθεν (δηλ. χωρίς 00, χωρίς 0 στην αρχή ή στο τέλος). Παραδείγματα: 1, 11, 110111101.

(α) Διάγραμμα καταστάσεων – μεταβάσεων (q0 αρχική, q1 τελική, ν νεκρή):

Κατάσταση Σημασία με 1 με 0 Τελική
q0 αρχή q1 ν όχι
q1 τελευταίο σύμβολο 1 q1 q2 ναι
q2 μόλις διαβάστηκε 0 (περιμένουμε 1) q1 ν όχι
ν νεκρή ν ν όχι

Διάγραμμα: q0 —1→ q1, q1 —1→ q1 (βρόχος), q1 —0→ q2, q2 —1→ q1, όλες οι υπόλοιπες μεταβάσεις στη νεκρή (q0 —0→ ν, q2 —0→ ν).

(β) Κανονική έκφραση:

\[1^+\,(\,0\,1^+\,)^*\;=\;1(1)^*\,(01(1)^*)^*\]

Έλεγχος: ταιριάζει στο 110111101 (\(11\cdot01111\cdot01\) δηλ. 11,0,1111,0,1).

Θέμα 3

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Αρχικά \(data=\{6,12,18,24\}\), \(p=\&data[2]\). 1. *(p-2) = *p/3 + 1 ⇒ \(data[0]=18/3+1=7\). 2. p-- ⇒ p στο \(data[1]\). 3. *(p+2) = *p*2 - 1 ⇒ \(data[3]=12\cdot2-1=23\). 4. *p += p[1]/3 ⇒ \(data[1]=12+data[2]/3=12+18/3=12+6=18\). 5. *(p+1) = *(p+2) - *p ⇒ \(data[2]=data[3]-data[1]=23-18=5\).

Έξοδος: 7 18 5 23 (επαληθεύτηκε με πρόγραμμα).

Θέμα 4

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

(a) Περιβάλλοντα αναφοράς (στατικός κανόνας): - MAIN: τοπικά {b, k, m, Q}· μη τοπικά κανένα· καθολικά {b, k, m, Q}. - Q: τοπικά {u, v}· μη τοπικά {b, k, m, Q}· καθολικά {b, k, m, Q}.

(b) Αρχικά \(b=(1,2,3)\), \(k=1\), \(m=2\), κλήση Q(b[m], b[k]) = Q(b[2], b[1]).

  1. Τιμή: \(u=2\), \(v=1\) (αντίγραφα). \(b[1]=1+2=3\). \(b[2]=2+1=3\). \(m:=3\). \(u:=3\). \(b[3]=3+3=6\). \(v:=1+3=4\) (τοπικό). b = 3 3 6.

  2. Αναφορά: \(u\)≡\(b[2]\), \(v\)≡\(b[1]\) (διευθύνσεις στην κλήση, με \(m=2\), \(k=1\)). \(b[1]:=b[1]+u=1+2=3\) (το \(v\) είναι τώρα 3). \(b[2]:=b[2]+v=2+3=5\) (το \(u\) είναι 5). \(m:=3\) (δεν επηρεάζει το \(u\)). \(u:=u+1\) ⇒ \(b[2]=6\). \(b[3]:=b[3]+u=3+6=9\). \(v:=v+u\) ⇒ \(b[1]=3+6=9\). b = 9 6 9.

  3. Τιμή–αποτέλεσμα: \(u=2\), \(v=1\). Όπως στην τιμή: \(b[1]=3\), \(b[2]=3\), \(m=3\), \(u=3\), \(b[3]=6\), \(v=4\). Στην έξοδο: \(u\to b[2]\) ⇒ \(b[2]=3\), \(v\to b[1]\) ⇒ \(b[1]=4\) (οι διευθύνσεις καθορίστηκαν στην κλήση με \(m=2\)). b = 4 3 6. (Αν η διεύθυνση του \(u\) υπολογιζόταν στην έξοδο με \(m=3\) θα έβγαινε \(b[3]=3\) και \(b = 4\ 3\ 3\)· η συνήθης σύμβαση είναι στην κλήση.)

  4. Όνομα: \(u\equiv b[m]\), \(v\equiv b[k]\), αποτιμώνται κάθε φορά. \(b[1]:=b[1]+b[m]\), \(m=2\) ⇒ \(1+2=3\). \(b[2]:=b[2]+b[k]=2+b[1]=2+3=5\). \(m:=3\). \(u:=u+1\) ⇒ \(b[m]=b[3]:=3+1=4\). \(b[3]:=b[3]+u=4+b[m]=4+4=8\). \(v:=v+u\) ⇒ \(b[k]=b[1]:=3+b[3]=3+8=11\). b = 11 5 8.

Πίνακας αποτελεσμάτων:

Κλήση με b[1] b[2] b[3]
1. τιμή 3 3 6
2. αναφορά 9 6 9
3. τιμή-αποτέλεσμα 4 3 6
4. όνομα 11 5 8

Θέμα 5

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν

import pandas as pd

# (α)
df_d1 = pd.DataFrame(day1_data)
df_d2 = pd.DataFrame(day2_data)
df_all_measurements = pd.concat([df_d1, df_d2], ignore_index=True)   # κάθετη συνένωση

# (β)
df_stations = pd.DataFrame(stations_info)
df_final = pd.merge(df_all_measurements, df_stations,
                    left_on='Κωδικός', right_on='Σταθμός_ID', how='inner')

# (γ)
df_final.drop(columns='Υψόμετρο', inplace=True)   # οριστική διαγραφή της στήλης

# (δ)
for index, row in df_final.iterrows():
    print(f"Πόλη: {row['Πόλη']} | Θερμοκρασία: {row['Θερμοκρασία']}")

Σχόλια: η concat με ignore_index=True δίνει νέα αρίθμηση 0..5. Η merge συγχωνεύει με τον κωδικό σταθμού (Κωδικός = Σταθμός_ID). Και οι 6 μετρήσεις έχουν αντίστοιχο σταθμό (S1, S2, S3, S4 υπάρχουν στο stations_info), άρα το inner δεν χάνει γραμμές. Έξοδος (σειρά γραμμών): Αθήνα 32.5, Πάτρα 29.0, Θεσσαλονίκη 34.2, Αθήνα 31.0, Πάτρα 30.2, Λάρισα 28.5.

Θέμα 6

Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: μέτρια

(Α) Prolog

Στην Prolog τα ονόματα που αρχίζουν με κεφαλαίο (Charlie, Olivia, Jack…) είναι μεταβλητές, όχι σταθερές· για σταθερές γράφουμε charlie, garofalakis κ.λπ. Παρακάτω χρησιμοποιώ πεζά.

(α) Κάθε πρόταση (fact) είναι ένα δέντρο με ρίζα το όνομα του κατηγορήματος και παιδιά τα ορίσματα:

   studies          studies          studies          studies
   /     \          /     \          /     \          /     \
charlie csc135   olivia csc135    jack  csc131    arthur csc134

   teaches          teaches          teaches          teaches
   /     \          /     \          /     \          /     \
sioutas csc135  garofalakis csc131 hadjidoukas csc171 vonitsanos csc134

Ανάγνωση: «ο charlie σπουδάζει (παρακολουθεί) το csc135», «η olivia παρακολουθεί το csc135», «ο jack το csc131», «ο arthur το csc134»· «ο sioutas διδάσκει το csc135», «ο garofalakis το csc131», «ο hadjidoukas το csc171», «ο vonitsanos το csc134».

(β) Ο κανόνας professor(X,Y) :- teaches(X,C), studies(Y,C). διαβάζεται: «ο X είναι καθηγητής του Y αν υπάρχει μάθημα C τέτοιο ώστε ο X διδάσκει το C και ο Y σπουδάζει το C» (το :- σημαίνει «αν», το κόμμα σημαίνει «και»).

(γ1) ?- studies(charlie, What). ⇒ What = csc135.

(γ2) ?- professor(garofalakis, Student). ⇒ Student = jack. (ο garofalakis διδάσκει το csc131, το οποίο σπουδάζει ο jack).

(Β) SQL και βελτιστοποίηση

Επισήμανση: το C<400 είναι ασαφές (το C υπάρχει και στους δύο πίνακες)· λόγω της συνθήκης σύνδεσης \(R1.C=R2.C\) ισχύει το ίδιο για τις δύο στήλες.

  1. Αρχική μετάφραση σε σχεσιακή άλγεβρα: \(\pi_A\big(\sigma_{R1.C=R2.C\,\wedge\,C<400}(R1\times R2)\big)\)
  2. Διάσπαση σύζευξης επιλογών: \(\pi_A\big(\sigma_{R1.C=R2.C}(\sigma_{C<400}(R1\times R2))\big)\)
  3. Προώθηση της επιλογής προς τα φύλλα: η \(\sigma_{C<400}\) εφαρμόζεται στους πίνακες πριν το γινόμενο: \(\pi_A\big(\sigma_{R1.C=R2.C}(\sigma_{C<400}(R1)\times R2)\big)\) (και αφού \(R1.C=R2.C\), ισχύει και για το \(R2\): \(\sigma_{C<400}(R2)\))
  4. Συνδυασμός καρτεσιανού γινομένου και επιλογής σε join: \(\pi_A\big(\sigma_{C<400}(R1)\bowtie_{R1.C=R2.C}\sigma_{C<400}(R2)\big)\)
  5. Προώθηση προβολών (κρατάμε μόνο τις απαραίτητες στήλες):
\[\pi_A\Big(\,\pi_{A,C}\big(\sigma_{C<400}(R1)\big)\;\bowtie_{R1.C=R2.C}\;\pi_{C}\big(\sigma_{C<400}(R2)\big)\Big)\]

Αυτό είναι το τελικό (βέλτιστο) πλάνο: επιλογές πρώτα (λιγότερες πλειάδες), προβολές νωρίς (στενότερες πλειάδες), join αντί για καρτεσιανό γινόμενο. Οι κανόνες που εφαρμόστηκαν είναι οι ευριστικοί: επιλογές κάτω, προβολές κάτω, αντικατάσταση × + σ με ⋈.

(Γ) Python και λ-λογισμός

(α) print(sum(map(lambda x: x**3, L))) (π.χ. για L=[1,2,3] δίνει 36).

(β) from functools import reduce και print(reduce(lambda a, b: a + b**2, L, 0)) (π.χ. για [1,2,3] δίνει 14). Η αρχική τιμή 0 είναι απαραίτητη, αλλιώς το πρώτο στοιχείο δεν θα υψωνόταν στο τετράγωνο.

(γ) Στην εκφώνηση τα σώματα γράφονται με κεφαλαία X, Y· θεωρώ ότι είναι τυπογραφικό και εννοούνται \(true=\lambda x.\lambda y.x\), \(false=\lambda x.\lambda y.y\). Τότε: - \(not\;true=(\lambda z.\,z\,false\,true)\,true\to true\;false\;true=(\lambda x.\lambda y.x)\,false\,true\to(\lambda y.\,false)\,true\to false\) ✓ - \(not\;false=false\;false\;true=(\lambda x.\lambda y.y)\,false\,true\to(\lambda y.y)\,true\to true\) ✓

Ναι, η αναπαράσταση δίνει το επιθυμητό αποτέλεσμα.

(Δ) Στρατηγικές αποτίμησης για square(sum [1:100])

Η εκφώνηση ορίζει \(sum(x{:}xs)=x+sum[x{+}1{:}xs]\). Ερμηνεύω το \([m{:}n]\) ως τη λίστα ακεραίων από \(m\) έως \(n\) και \(sum[m{:}n]=m+sum[m{+}1{:}n]\), με \(sum=0\) όταν \(m>n\) (αλλιώς δεν τερματίζει). Η ερμηνεία είναι αβέβαιη και ο ακριβής αριθμός βημάτων εξαρτάται από τη σύμβαση μέτρησης ⇒ χαμηλή βεβαιότητα στους αριθμούς.

Σύμβαση: κάθε εφαρμογή κανόνα (χρήστη ή ενσωματωμένου +, *) είναι μία αναγωγή. Ο υπολογισμός του \(S=sum[1{:}100]\) κοστίζει 100 εφαρμογές του \(sum\) + 100 υπολογισμούς \(m+1\) + 1 τερματισμό + 100 προσθέσεις = 301. Αποτέλεσμα 5050, και \(5050^2=25\,502\,500\).

  • Πρόθυμη (innermost): πρώτα το όρισμα: \(sum[1{:}100]\to1+sum[2{:}100]\to1+(2+sum[3{:}100])\to\cdots\to1+(2+\cdots+(100+0))\to\cdots\to5050\) (301)· μετά \(square\,5050\to5050*5050\to25502500\) (2). Σύνολο 303.
  • Οκνηρή (outermost, χωρίς διαμοιρασμό): \(square\,(sum[1{:}100])\to sum[1{:}100]*sum[1{:}100]\) (1)· το όρισμα αντιγράφεται, άρα το \(sum\) υπολογίζεται δύο φορές (2·301)· τέλος ο πολλαπλασιασμός (1). Σύνολο 604.
  • Γραφο-υβριδική (outermost graph reduction): η ίδια οκνηρή σειρά, αλλά το όρισμα είναι κοινός κόμβος του γράφου, οπότε το \(sum\) υπολογίζεται μία φορά: 1 + 301 + 1 = 303.

Πιο αποδοτικές: η πρόθυμη και η γραφο-υβριδική (303 αναγωγές). Η οκνηρή χωρίς διαμοιρασμό είναι η χειρότερη (604), γιατί αντιγράφει το όρισμα και επαναλαμβάνει τον ίδιο υπολογισμό.

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

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