This item is provided by the institution :

Repository :
Institutional Repository of the Hellenic Open University
see the original item page
in the repository's web site and access all digital files if the item*
share



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

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

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

Ο φοιτητής θα κατανοήσει ότι ένας αλγόριθμος αναζήτησης σε γράφους μπορεί να έχει παραπάνω από μία μορφή, ανάλογα με το βάθος της συμπληρωματικής πληροφορίας που επιθυμούμε να αντλήσουμε από το γράφο. Στο υπάρχον εκπαιδευτικό υλικό δίνεται μία (η τελική) μορφή των αλγορίθμων μόνο. Παρουσιάζει το σκεπτικό με το οποίο θα μπορούσε κανείς να σχεδιάσει μία σύνθετη υλοποίηση ενός αλγορίθμου, ξεκινώντας από βασικά σημεία μόνο και προχωρώντας σε επίπεδα. Συνοδεύει και αναλύει σε μεγαλύτερο βάθος το κεφάλαιο 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 Εικόνες)



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)