δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο



Αλγόριθμοι αναζήτησης σε γράφους

ΚΑΛΛΕΣ, ΔΗΜΗΤΡΗΣ (ΜΕΛΟΣ Σ.Ε.Π., ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ)

ΣΚΟΔΡΑΣ, ΑΘΑΝΑΣΙΟΣ (ΚΑΘΗΓΗΤΗΣ, ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ, ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ)
ΠΙΕΡΡΑΚΕΑΣ, ΧΡΗΣΤΟΣ (ΜΕΛΟΣ Σ.Ε.Π., ΕΛΛΗΝΙΚΟ ΑΝΟΙΚΤΟ ΠΑΝΕΠΙΣΤΗΜΙΟ, ΥΠΕΥΘΥΝΟΣ ΕΕΥΕΜ)
ΒΕΣΚΟΥΚΗΣ, ΒΑΣΙΛΕΙΟΣ (ΕΠΙΚΟΥΡΟΣ ΚΑΘΗΓΗΤΗΣ, ΕΘΝΙΚΟ ΜΕΤΣΟΒΙΟ ΠΟΛΥΤΕΧΝΕΙΟ)

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

Hypertext

γράφος, αναζήτηση-σε-βάθος, αναζήτηση-σε-πλάτος, graph, depth-first-search, breadth-first-search

Ελληνικό Ανοικτό Πανεπιστήμιο (EL)
Hellenic Open University (EN)

2008
2009-02-27T10:12:41Z
2013-12-13T11:28:16Z


Οι παράγραφοι 1.2 και 1.3 απαιτούν περίπου 1 ώρα η καθεμία. Η παράγραφος 1.4 απαιτεί περίπου 2 ώρες. (9 Σελίδες + 6 Εικόνες)



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.