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

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

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

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

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

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

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

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

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

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

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

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

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

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