Εισαγωγή στους Αλγόριθμους — Ιούλιος 2024¶
Μεταγραφή από τις φωτογραφίες της 3/7/2024 με τη σειρά των θεμάτων (1, 2).
20240703_203338.jpg¶
ΘΕΜΑ 1 (1 μονάδα). Θεωρήστε το παρακάτω κατευθυνόμενο γράφημα, στο οποίο οι αριθμοί που συσχετίζονται με τις ακμές του αναπαριστούν κόστος, και θεωρήστε την εκτέλεση του αλγορίθμου Dijkstra με αρχική κορυφή την s.
[Σχήμα: Κατευθυνόμενο γράφημα με κόμβους s, a, b, y, x, t. Ακμές και βάρη: s -> a (400), s -> y (80), s -> b (480) y -> a (40), y -> x (280), y -> b (200) a -> x (280), a -> t (280) x -> b (160), x -> t (40) b -> t (120)]
Ο αλγόριθμος Dijkstra υπολογίζει τις αποστάσεις (κόστη συντομότερων διαδρομών) από την κορυφή s προς όλες τις υπόλοιπες κορυφές, εργαζόμενος επαναληπτικά και οριστικοποιώντας σε κάθε επανάληψη την ετικέτα d(w) μιας κορυφής w, αρχίζοντας από την s. Η επανάληψη κατά την οποία οριστικοποιείται η ετικέτα μιας κορυφής w ονομάζεται σειρά (ή διάταξη) οριστικοποίησης της w (η s έχει σειρά οριστικοποίησης 1).
(α) [0.7] Στο παραπάνω γράφημα υπάρχουν τρεις συντομότερες διαδρομές \(\Sigma\Delta(s,t)\) από την κορυφή s προς την t: (s,y,[δυσανάγνωστο],t), (s,y,a,t) και (s,y,b,t). Ποια από αυτές θα υπολογίσει ο αλγόριθμος Dijkstra ως την \(\Sigma\Delta(s,t)\); Αιτιολογήστε την απάντησή σας (μη αιτιολογημένες απαντήσεις θα βαθμολογούνται με μηδέν). (β) [0.3] Ποια είναι η σειρά οριστικοποίησης της κορυφής x;
Απάντηση:
Σημείωση: η φωτογραφία περιέχει χειρόγραφη σημείωση φοιτητή.
20240703_182902.jpg¶
ΘΕΜΑ 2 (2 μονάδες). Μια ομάδα μηχανικών υπολογιστών εργάζεται για την επίλυση δύο υπολογιστικών προβλημάτων \(\Pi_1\) και \(\Pi_2\), για καθένα από τα οποία έχει δημιουργήσει έναν αλγόριθμο «διαίρει και βασίλευε». Συγκεκριμένα: - Τον αλγόριθμο \(A_1\) που διασπά το αρχικό πρόβλημα μεγέθους \(n\) σε 4 υποπροβλήματα μεγέθους \(n/2\), τα επιλύει και στη συνέχεια συνθέτει τις λύσεις τους σε χρόνο \(8 \cdot n^2\). - Τον αλγόριθμο \(A_2\) που περιορίζει τη λύση του αρχικού προβλήματος μεγέθους \(n\) στα \(13/14\) ενός υποπροβλήματος μεγέθους \(n/9\), το επιλύει και στη συνέχεια συνθέτει τη λύση σε χρόνο \(14 \cdot \log^{(7/13)} n\). (α) [1.4] Να διατυπώσετε τις αναδρομικές εξισώσεις που δίνουν τον χρόνο εκτέλεσης των αλγορίθμων \(A_1\) και \(A_2\), και στη συνέχεια με εφαρμογή του Βασικού Θεωρήματος των αναδρομών να βρείτε τον κλειστό τύπο κάθε αναδρομής σε ασυμπτωτικό συμβολισμό εξηγώντας αναλυτικά την εφαρμογή του. (β) [0.6] Χρησιμοποιώντας την απάντηση του (α) σαν πρόβλεψη, να αποδείξετε τον κλειστό τύπο του αλγορίθμου \(A_1\) με επαγωγή (μέθοδος αντικατάστασης ή σωστής πρόβλεψης) προσδιορίζοντας επακριβώς τις σταθερές. Ως αρχική συνθήκη, ισχύει ότι \(T(x) = 1, \forall x < 1\).
Απάντηση:
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2024-07.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):20240703_182903.jpg
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2024-07¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη
Dijkstra από την s. Οριστικοποιήσεις: s(0), y(80), a(120 = 80+40), b(280 = 80+200), x(360 = 80+280), t(400).
(α) Και οι τρεις διαδρομές έχουν κόστος 400: (s,y,a,t) = 80+40+280, (s,y,b,t) = 80+200+120, (s,y,x,t) = 80+280+40. Η \(d(t)\) ενημερώνεται (με αυστηρή βελτίωση) την πρώτη φορά που οριστικοποιείται κορυφή-προκάτοχος με άθροισμα 400, δηλαδή όταν οριστικοποιείται η a (3η) και \(d(t)=120+280=400\). Όταν οριστικοποιούνται η b και η x δίνουν πάλι 400, που δεν είναι μικρότερο, άρα ο προκάτοχος του t μένει η a. Επιλέγεται η (s,y,a,t). (Υπόθεση: ισοπαλία δεν αλλάζει την ετικέτα.)
(β) Σειρά οριστικοποίησης: s=1, y=2, a=3, b=4, x=5, t=6.
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη
(α) Α₁: \(T(n)=4T(n/2)+8n^2\). \(n^{\log_2 4}=n^2\), \(f=\Theta(n^2)\): περίπτωση 2, \(T(n)=\Theta(n^2\log n)\).
Α₂: \(T(n)=\tfrac{13}{14}T(n/9)+14\log^{7/13}n\). Εδώ \(a=13/14<1\), οπότε το Βασικό Θεώρημα με \(a\ge1\) δεν εφαρμόζεται αυστηρά· με τη γενίκευσή του \(n^{\log_9(13/14)}=n^{-\delta}\) (\(\delta>0\) μικρό), και \(f=\Omega(n^{-\delta+\varepsilon})\), περίπτωση 3. Συνθήκη κανονικότητας: \(\tfrac{13}{14}\cdot14\log^{7/13}(n/9)\le\tfrac{13}{14}\cdot14\log^{7/13}n\), δηλ. \(c=13/14<1\) ισχύει. Άρα \(T(n)=\Theta(\log^{7/13}n)\). Ισοδύναμα με ξετύλιγμα: \(\sum_i(13/14)^i\,14\log^{7/13}(n/9^i)=\Theta(\log^{7/13}n)\) (γεωμετρική σειρά).
(β) Για \(T(n)=4T(n/2)+8n^2\), \(n\ge1\), \(T(x)=1\) για \(x<1\). Ισχυρισμός: \(8n^2\log_2 n\le T(n)\le 8n^2\log_2 n+12n^2\) για \(n\ge1\).
Βάση (\(1\le n<2\)): \(T(n)=4+8n^2\). Άνω: \(4+8n^2\le12n^2\) (\(n^2\ge1\)). Κάτω: \(4+8n^2\ge8n^2\log_2 n\) (\(\log_2 n<1\)).
Βήμα (\(n\ge2\)): \(T(n)\le4\left[8\tfrac{n^2}{4}(\log_2 n-1)+12\tfrac{n^2}{4}\right]+8n^2=8n^2\log_2 n-8n^2+12n^2+8n^2\) \(=8n^2\log_2 n+12n^2\) (το \(-8n^2\) και το \(+8n^2\) αλληλοαναιρούνται). Κάτω: \(T(n)\ge4\cdot8\tfrac{n^2}{4}(\log_2 n-1)+8n^2=8n^2\log_2 n\) ✓.
Άρα \(c=8\), \(d=12\) και \(T(n)=\Theta(n^2\log n)\).