Εισαγωγή στους Αλγόριθμους — Φεβρουάριος 2021 — Ερώτηση 1 (απόσπασμα)¶
Μεταγραφή από το στιγμιότυπο unknown.png.
unknown.png¶
Ερώτηση 1 (Ταίριασμα — 1 βαθμός)
Έστω \(G = (V, E)\) ένα μη κατευθυνόμενο συνεκτικό γράφημα και έστω \(T\) το δένδρο αναζήτησης πρώτα κατά πλάτος (BFS) με ρίζα μια κορυφή \(s \in V\). Η αναζήτηση πρώτα κατά πλάτος (BFS) υπολογίζει αποστάσεις \(d(v)\), \(\forall v \in V\), από την \(s\). Χαρακτηρίστε τις ακόλουθες προτάσεις ως προς την ορθότητά τους.
| Στήλη Α | Κάντε την αντιστοιχία | Στήλη Β |
|---|---|---|
| 1. Για μια ακμή \((u,w) \in E\), με \(d(u) < d(w)\), ισχύει ότι \(d(w) \leq d(u) + 1\) | [ -- ▾ ] | Α. Σωστό |
| 2. Για μια ακμή \((u,w) \in E\), με \(d(u) < d(w)\), ισχύει ότι \(d(w) > d(u) + 1\) | [ -- ▾ ] | Β. Λάθος |
| 3. Αν για μια ακμή \((u,w) \in E\) ισχύει ότι \(d(w) = d(u) + 1\), τότε \((u,w) \in T\) | [ -- ▾ ] | |
| 4. Αν για μια ακμή \((u,w) \in E\) ισχύει ότι \(d(w) = d(u)\), τότε \((u,w) \in T\) | [ -- ▾ ] | |
| 5. Αν για μια ακμή \((u,w) \in E\) ισχύει ότι \(d(w) = d(u)\), τότε \((u,w) \notin T\) | [ -- ▾ ] |
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-02¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1 (Ταίριασμα BFS)¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Βασικές ιδιότητες του BFS σε μη κατευθυνόμενο γράφημα: για κάθε ακμή \((u,w)\) ισχύει \(|d(u)-d(w)|\le1\), και οι ακμές του δένδρου \(T\) συνδέουν επίπεδα που διαφέρουν κατά ακριβώς 1 (κάθε κορυφή έχει ένα μόνο γονέα).
- \(d(u)<d(w)\) ⇒ \(d(w)\le d(u)+1\) (αλλιώς η \(w\) θα είχε βρεθεί νωρίτερα μέσω του \(u\)): Σωστό (Α).
- \(d(w)>d(u)+1\) αντίφαση με το 1: Λάθος (Β).
- \(d(w)=d(u)+1\) δεν σημαίνει ότι η ακμή ανήκει στο \(T\): η \(w\) μπορεί να έχει γονέα άλλη κορυφή του ίδιου επιπέδου με την \(u\) (π.χ. τετράγωνο \(s\)–\(u\), \(s\)–\(v\), \(u\)–\(w\), \(v\)–\(w\): μόνο η μία από τις δύο ακμές προς τη \(w\) μπαίνει στο \(T\)): Λάθος (Β).
- Ακμή ανάμεσα σε κορυφές ίδιου επιπέδου δεν μπορεί να είναι ακμή δένδρου (οι ακμές δένδρου αυξάνουν την απόσταση κατά 1): Λάθος (Β).
- Από το 4: Σωστό (Α).
Απαντήσεις: 1-Α, 2-Β, 3-Β, 4-Β, 5-Α