Τεχνικές Εκτίμησης Υπολογιστικών Συστημάτων και Δικτύων — Ιούνιος 2015 — Επί διπλώματι φοιτητές¶
Μεταγραφή από το αρχείο iounios_15.pdf (2 σελίδες, 3 θέματα).
iounios_15.pdf¶
Δ' & Ε' ΕΤΟΣ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ
ΤΕΧΝΙΚΕΣ ΕΚΤΙΜΗΣΗΣ ΥΠΟΛΟΓΙΣΤΙΚΩΝ ΣΥΣΤΗΜΑΤΩΝ
Εξέταση Ιουνίου 2015 – Επί διπλώματι φοιτητές
ΘΕΜΑ 1 (30%)¶
Δίνονται οι παρακάτω πίνακες μεταβάσεων τεσσάρων αλυσίδων Markov διακριτού χρόνου:
(a) \(\vec{P}_1 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\)
(b) \(\vec{P}_2 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\)
(c) \(\vec{P}_3 = \begin{bmatrix} 0.75 & 0.25 \\ 0.5 & 0.5 \end{bmatrix}\)
(d) \(\vec{P}_4 = \begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}\)
Για κάθε μία από τις τέσσερις αλυσίδες, να απαντήσετε στα παρακάτω ερωτήματα: (1) Να σχεδιάσετε το διάγραμμα καταστάσεων – πιθανοτήτων μεταβάσεων. (2) Να χαρακτηρίσετε το είδος της αλυσίδας τις καταστάσεις της. (3) Έχει λύση μόνιμης κατάστασης \(\vec{\pi}\) η αλυσίδα; Αιτιολογείστε την απάντησή σας. (4) Σε περίπτωση θετικής απάντησης στο ερώτημα (3), να βρείτε τη λύση αυτή.
ΘΕΜΑ 2 (30%)¶
Σε έναν τηλεφωνικό θάλαμο οι αφίξεις πελατών είναι Poisson με μέσο ρυθμό 4 πελάτες/ώρα. Η διάρκεια μιας τηλεφωνικής κλήσης ακολουθεί την εκθετική κατανομή, με μέση τιμή τα 5 λεπτά/κλήση. Θεωρούμε ότι μπορούν να περιμένουν έξω από το θάλαμο, όσοι πελάτες φθάσουν.
(a) Ποιος είναι ο μέσος χρόνος απόκρισης \(T\) ενός πελάτη; (b) Ποιος είναι ο μέσος αριθμός πελατών που περιμένουν έξω από το θάλαμο; (c) Θεωρήστε ότι ο χρόνος κλήσης είναι σταθερός (και όχι εκθετικός), ίσος με 5 λεπτά/κλήση. Στην περίπτωση αυτή, ποιος είναι ο μέσος χρόνος απόκρισης \(T\) και ο μέσος αριθμός πελατών που περιμένουν έξω από το θάλαμο; Συγκρίνετε και σχολιάστε με τα αποτελέσματα των (a) και (b).
ΣΗΜΕΙΩΣΗ: Στο σύστημα αναμονής \(M/D/1\), ο μέσος αριθμός πελατών στο σύστημα, είναι: $\(\rho + \frac{\rho^2}{2(1-\rho)}\)$
ΘΕΜΑ 3 (40%)¶
Σας δίνεται το παρακάτω κλειστό δίκτυο τεσσάρων Συστημάτων Αναμονής ΣΑ1, ΣΑ2, ΣΑ3, ΣΑ4, στο οποίο υπάρχουν \(N = 2\) εργασίες.
[Σχήμα: Κλειστό δίκτυο τεσσάρων συστημάτων αναμονής (ΣΑ1, ΣΑ2, ΣΑ3, ΣΑ4).
Μετά το ΣΑ4, η ροή διακλαδίζεται με πιθανότητες: - $r_{41} = $ [δυσανάγνωστο] προς το ΣΑ1 (ρυθμός εξυπηρέτησης \(\mu\)) - \(r_{42} = 1/2\) προς το ΣΑ2 (ρυθμός εξυπηρέτησης \(2\mu\)).
Η έξοδος του ΣΑ2 οδηγεί στο ΣΑ3 (ρυθμός εξυπηρέτησης \(2\mu\)).
Οι έξοδοι των ΣΑ1 και ΣΑ3 ενώνονται και οδηγούν στην ουρά του ΣΑ4 (ρυθμός εξυπηρέτησης \(\mu\)).
Κάθε σύστημα αναμονής απεικονίζεται με ορθογώνια ουρά και κυκλικό εξυπηρετητή.]
Δίνεται: \(\mu = 1 \text{ εργασία/sec}\). Επίσης, οι εξυπηρετήσεις είναι εκθετικές, ενώ όλες οι ουρές έχουν πρακτικά άπειρο μήκος.
Ζητούνται τα παρακάτω: (a) Ποιο από τα τέσσερα ΣΑ είναι σημείο συμφόρησης (bottleneck) του δικτύου και γιατί; (b) Ποια είναι η πιθανότητα να βρίσκονται όλες οι εργασίες στο ΣΑ4 και ποια η πιθανότητα να είναι όλες στο ΣΑ2; (c) Ποια είναι η χρησιμοποίηση (utilization) του ΣΑ1; (d) Απαντήστε στα παραπάνω ερωτήματα (a), (b), (c) αν υπάρχει μόνο μια εργασία στο δίκτυο (\(N = 1\)). Πως αξιοποιείτε τη διαδικασία επίλυσης που χρησιμοποιήσατε για \(N = 2\);
ΚΑΛΗ ΕΠΙΤΥΧΙΑ!!!
- Απαντήστε σε όλα τα θέματα
- Τα θέματα επιστρέφονται με το γραπτό
- Η διάρκεια της εξέτασης είναι 2 ώρες
2
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2015-06¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Στα διαγράμματα, “\(i\to j:p\)” σημαίνει μετάβαση από την κατάσταση \(i\) στην \(j\) με πιθανότητα \(p\).
(a) \(\vec P_1=\begin{bmatrix}1&0\\0&1\end{bmatrix}\)
(1) Διάγραμμα: \(1\to1:1\) και \(2\to2:1\).
(2) Υπάρχουν δύο κλειστές κλάσεις \(\{1\}\) και \(\{2\}\)· κάθε κατάσταση είναι απορροφούσα, θετικά επαναληπτική και απεριοδική. Η αλυσίδα είναι αναγωγίσιμη (reducible).
(3) Ναι, έχει λύση μόνιμης κατάστασης, αλλά όχι μοναδική. Από \(\vec\pi=\vec\pi \vec P_1\) προκύπτει ταυτότητα.
(4) Όλες οι λύσεις είναι [ \vec\pi=(a,1-a),\qquad 0\le a\le 1. ] Αν ζητείται γνήσια θετική λύση, \(0<a<1\). Η οριακή κατανομή εξαρτάται από την αρχική κατανομή.
(b) \(\vec P_2=\begin{bmatrix}0&1\\1&0\end{bmatrix}\)
(1) Διάγραμμα: \(1\to2:1\) και \(2\to1:1\).
(2) Η αλυσίδα είναι μία κλειστή κλάση \(\{1,2\}\), άρα μη αναγωγίσιμη (irreducible). Είναι περιοδική με περίοδο \(2\) και θετικά επαναληπτική.
(3) Ναι, έχει μοναδική λύση μόνιμης κατάστασης. Εξισώσεις: \(\pi_1=\pi_2\), \(\pi_1+\pi_2=1\).
(4) [ \vec\pi=\left(\frac12,\frac12\right). ] Λόγω περιοδικότητας δεν συγκλίνει γενικά η \(P_2^n\) σε αυτήν, αλλά η στάσιμη κατανομή υπάρχει.
(c) \(\vec P_3=\begin{bmatrix}0.75&0.25\\0.5&0.5\end{bmatrix}\)
(1) Διάγραμμα: \(1\to1:0.75\), \(1\to2:0.25\), \(2\to1:0.5\), \(2\to2:0.5\).
(2) Η αλυσίδα είναι μη αναγωγίσιμη, απεριοδική (υπάρχουν αυτομεταβάσεις με θετική πιθανότητα) και θετικά επαναληπτική· είναι εργοδική.
(3) Ναι, έχει μοναδική λύση μόνιμης κατάστασης.
(4) Από \(\pi_1=0.75\pi_1+0.5\pi_2\) προκύπτει \(0.25\pi_1=0.5\pi_2\), άρα \(\pi_1=2\pi_2\). Με \(\pi_1+\pi_2=1\): [ \vec\pi=\left(\frac23,\frac13\right). ]
(d) \(\vec P_4=\begin{bmatrix}0&1\\0&1\end{bmatrix}\)
(1) Διάγραμμα: \(1\to2:1\) και \(2\to2:1\).
(2) Η κατάσταση \(2\) είναι απορροφούσα και θετικά επαναληπτική· η κατάσταση \(1\) είναι μεταβατική. Η αλυσίδα είναι αναγωγίσιμη (reducible).
(3) Ναι, έχει μοναδική λύση μόνιμης κατάστασης. Από \(\vec\pi=\vec\pi \vec P_4\): \(\pi_1=0\), \(\pi_2=\pi_1+\pi_2\), άρα \(\pi_1=0\), \(\pi_2=1\).
(4) [ \vec\pi=(0,1). ] Από οποιαδήποτε αρχική κατανομή με \(\pi_1(0)>0\), τελικά η αλυσίδα απορροφάται στην κατάσταση \(2\).
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Δίνονται [ \lambda=4\ \text{πελάτες/ώρα},\qquad E[S]=5\ \text{min}=\frac1{12}\ \text{h}, ] άρα [ \mu=\frac{1}{E[S]}=12\ \text{πελάτες/ώρα},\qquad \rho=\frac{\lambda}{\mu}=\frac{4}{12}=\frac13. ]
(a) Για \(M/M/1\) ο μέσος χρόνος απόκρισης είναι [ T=\frac{1}{\mu-\lambda} =\frac{1}{12-4} =\frac18\ \text{h} =7.5\ \text{min}. ]
(b) Ο μέσος αριθμός πελατών που περιμένουν έξω είναι [ L_q=\frac{\rho^2}{1-\rho} =\frac{(1/3)^2}{1-1/3} =\frac{1}{6}\approx 0.1667\ \text{πελάτες}. ]
(c) Για \(M/D/1\) με \(\rho=1/3\) και σταθερό χρόνο εξυπηρέτησης \(5\) min, ο μέσος αριθμός στο σύστημα είναι [ L=\rho+\frac{\rho^2}{2(1-\rho)} =\frac13+\frac{(1/3)^2}{2(1-1/3)} =\frac13+\frac{1}{12} =\frac{5}{12}. ] Άρα [ T=\frac{L}{\lambda} =\frac{5/12}{4}\ \text{h} =\frac{5}{48}\ \text{h} =6.25\ \text{min}. ] Ο μέσος αριθμός πελατών που περιμένουν έξω είναι [ L_q=L-\rho=\frac{5}{12}-\frac13=\frac{1}{12}\approx 0.0833. ]
Σύγκριση: με σταθερό χρόνο εξυπηρέτησης, ο μέσος χρόνος απόκρισης μειώνεται από \(7.5\) min σε \(6.25\) min και ο μέσος αριθμός αναμονής υποδιπλασιάζεται από \(1/6\) σε \(1/12\). Η μείωση οφείλεται στη μικρότερη μεταβλητότητα του χρόνου εξυπηρέτησης, ενώ η χρησιμοποίηση \(\rho=1/3\) μένει ίδια.
Θέμα 3¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Από την κανονικοποίηση των πιθανοτήτων διακλάδωσης μετά το ΣΑ4, [ r_{41}+r_{42}=1,\qquad r_{42}=\frac12, ] άρα λαμβάνω \(r_{41}=\frac12\).
Οι σχετικοί ρυθμοί επισκέψεων \(v_i\) ικανοποιούν \(v_i=\sum_j v_j r_{ji}\). Επιλέγοντας \(v_4=2\), προκύπτει [ (v_1,v_2,v_3,v_4)=(1,1,1,2). ] Οι ρυθμοί εξυπηρέτησης είναι [ (\mu_1,\mu_2,\mu_3,\mu_4)=(1,2,2,1). ] Άρα τα σχετικά φορτία ανά επίσκεψη είναι [ \alpha_i=\frac{v_i}{\mu_i} =\left(1,\frac12,\frac12,2\right). ]
(a) Το σημείο συμφόρησης είναι το \(\mathrm{ΣΑ}4\), διότι [ \alpha_4=2=\max_i \alpha_i. ] Δηλαδή το ΣΑ4 έχει τη μεγαλύτερη σχετική απαίτηση εξυπηρέτησης και θα κορεσθεί πρώτο καθώς αυξάνεται το φορτίο.
Για \(N=2\), η στάσιμη κατανομή του κλειστού δικτύου είναι [ \pi(n_1,n_2,n_3,n_4) =\frac{1}{G_2}\prod_{i=1}^4 \alpha_i^{n_i}, \qquad \sum_{i=1}^4 n_i=2, ] όπου [ G_2=h_2\left(1,\frac12,\frac12,2\right)=\frac{43}{4}. ]
(b) Η πιθανότητα να βρίσκονται και οι δύο εργασίες στο ΣΑ4 είναι [ \pi(0,0,0,2) =\frac{\alpha_4^2}{G_2} =\frac{2^2}{43/4} =\frac{16}{43}. ] Η πιθανότητα να βρίσκονται και οι δύο εργασίες στο ΣΑ2 είναι [ \pi(0,2,0,0) =\frac{\alpha_2^2}{G_2} =\frac{(1/2)^2}{43/4} =\frac{1}{43}. ]
(c) Για το ΣΑ1, επειδή είναι ένας εξυπηρετητής, [ U_1=P(n_1>0)=1-P(n_1=0). ] Υπολογίζω το βάρος για \(n_1=0\): [ h_2\left(\frac12,\frac12,2\right) =\frac{27}{4}. ] Άρα [ P(n_1=0)=\frac{27/4}{43/4}=\frac{27}{43}, ] και επομένως [ U_1=1-\frac{27}{43}=\frac{16}{43}. ]
(d) Για \(N=1\):
Οι σχετικοί ρυθμοί επισκέψεων και τα \(\alpha_i\) μένουν ίδια. Τώρα [ G_1=\sum_{i=1}^4 \alpha_i =1+\frac12+\frac12+2=4. ] Η πιθανότητα η μοναδική εργασία να βρίσκεται στο ΣΑ\(i\) είναι \(\alpha_i/G_1\).
-
Το σημείο συμφόρησης παραμένει το \(\mathrm{ΣΑ}4\), αφού \(\alpha_4=2\) είναι το μέγιστο. Για \(N=1\) δεν υπάρχουν πραγματικές ουρές αναμονής, αλλά το ΣΑ4 έχει τη μεγαλύτερη πιθανότητα κατάληψης/χρησιμοποίηση: [ U_4=\frac{\alpha_4}{G_1}=\frac{2}{4}=\frac12. ] Οι υπόλοιπες χρησιμοποιήσεις είναι \(U_1=1/4\), \(U_2=1/8\), \(U_3=1/8\).
-
Πιθανότητα να είναι η εργασία στο ΣΑ4: [ P(n_4=1)=\frac{\alpha_4}{G_1}=\frac{2}{4}=\frac12. ] Πιθανότητα να είναι στο ΣΑ2: [ P(n_2=1)=\frac{\alpha_2}{G_1} =\frac{1/2}{4}=\frac18. ]
-
Χρησιμοποίηση του ΣΑ1: [ U_1=P(n_1=1)=\frac{\alpha_1}{G_1}=\frac14. ]
Η ίδια διαδικασία για \(N=2\) αξιοποιεί τη λύση για \(N=1\) είτε μέσω της αναδρομής MVA, όπου χρειάζονται τα μέσα πλήθη \(N_i(1)\) για δίκτυο με μία εργασία, είτε μέσω της συνέλιξης/συνάρτησης κανονικοποίησης \(G_N\): υπολογίζεται πρώτα το \(G_1\) και στη συνέχεια το \(G_2\) από τα ίδια \(\alpha_i\).