upatras eclass | GFBM_2.2C Πληροφοριακά Συστήματα...

GFBM_2.2C Πληροφοριακά Συστήματα Διοίκησης

DEAPT148 - Γρηγόριος Μπεληγιάννης

2η Διάλεξη - 1η Άσκηση

Ερώτηση 1 (Αντιστοίχιση — 15 βαθμοί)

Ποιος αλγόριθμος είναι κατάλληλος για κάθε διαφορετικό τύπο γραφήματος;

Στήλη Α	Κάντε την αντιστοιχία	Στήλη B
1. Κατευθυνόμενος γράφος με θετικά και αρνητικά κόστη		A. Αλγόριθμος Dijkstra
2. Κατευθυνόμενος άκυκλος γράφος με θετικά και αρνητικά κόστη		B. Αλγόριθμος Bellman-Ford
3. Κατευθυνόμενος γράφος με θετικά κόστη		C. Αλγόριθμος DAG

Ερώτηση 2 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός)

Το πρόβλημα του ελάχιστου ζευγνύοντος δέντρου επιλύεται από τον αλγόριθμο του

Watson

Dijkstra

Prim

Ερώτηση 3 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός)

Ο αλγόριθμος του Prim βασίζεται

στις ακμές.

στους κόμβους.

Ερώτηση 4 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 1 βαθμός)

Το πρόβλημα της συντομότερης διαδρομής επιλύεται από τν αλγόριθμο του

Prim

Dijkstra

Kruskal

Ερώτηση 5 (Συμπλήρωση Κενών (Αυστηρή Ταυτοποίηση) — 1 βαθμός)

Συμπληρώστε τα κενά:

Στον αλγόριθμο του Dijkstra sε κάθε επανάληψη ανιχνεύεται ένας κόμβος για τον οποίο η διαδρομή από την αφετηρία μέχρι αυτόν δε μπορεί να βελτιωθεί περαιτέρω. Ο κόμβος αυτός ονομάζεται ή .

Μάθημα : GFBM_2.2C Πληροφοριακά Συστήματα Διοίκησης

Κωδικός : DEAPT148