δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Ο φοιτητής θα κατανοήσει ότι ένας αλγόριθμος αναζήτησης σε γράφους μπορεί να έχει παραπάνω από μία μορφή, ανάλογα με το βάθος της συμπληρωματικής πληροφορίας που επιθυμούμε να αντλήσουμε από το γράφο. Στο υπάρχον εκπαιδευτικό υλικό δίνεται μία (η τελική) μορφή των αλγορίθμων μόνο. Παρουσιάζει το σκεπτικό με το οποίο θα μπορούσε κανείς να σχεδιάσει μία σύνθετη υλοποίηση ενός αλγορίθμου, ξεκινώντας από βασικά σημεία μόνο και προχωρώντας σε επίπεδα. Συνοδεύει και αναλύει σε μεγαλύτερο βάθος το κεφάλαιο 22 (“Elementary Graph Algorithms”) του βιβλίου “Introduction to Algorithms” (1). Επιπλέον συνοδεύει το κεφάλαιο 8 (“Sorting in Linear Time”) του ίδιου βιβλίου, καθώς συσχετίζει τη μελέτη του προβλήματος της διάταξης με την αναζήτηση σε γράφους. Θα πρέπει να το μελετήσει επειδή δείχνει πως ένας βασικός αλγόριθμος μπορεί να υποστεί παραλλαγές και, επιπλέον, αναδεικνύει τη φύση της αναζήτησης-σε-βάθος και της αναζήτησης-σε-πλάτος ως εξαντλητικών μεθόδων αναζήτησης.
Στο παρόν υλικό υπερκειμένου και συνοδευτικών ασκήσεων θα μελετήσουμε την εφαρμογή αλγορίθμων αναζήτησης σε γράφους, με παράλληλο στόχο την κατανόηση του πως μία κατ’ αρχήν απλή υλοποίηση αυτών των αλγορίθμων μπορεί να επεκτείνεται σταδιακά ώστε να μπορούμε να υπολογίσουμε ενδιαφέρουσες ιδιότητες μέσα στους γράφους που μελετάμε καθώς και πώς μέσα από αυτούς τους φαινομενικά απλούς αλγορίθμους μπορούμε να μελετήσουμε πιο σύνθετα προβλήματα.
Οι παράγραφοι 1.2 και 1.3 απαιτούν περίπου 1 ώρα η καθεμία. Η παράγραφος 1.4 απαιτεί περίπου 2 ώρες. (9 Σελίδες + 6 Εικόνες)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
