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

Περίληψη

ΣΤΗΝ ΠΑΡΟΥΣΑ ΔΙΑΤΡΙΒΗ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΝΕΕΣ ΤΕΧΝΙΚΕΣ ΓΙΑ ΤΟ ΣΧΕΔΙΑΣΜΟ ΚΑΙ ΤΗΝ ΑΝΑΛΥΣΗ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΚΑΙ ΤΗΝ ΕΦΑΡΜΟΓΗ ΤΟΥ ΣΕ ΠΡΟΒΛΗΜΑΤΑ ΓΡΑΦΩΝ. ΠΙΟ ΣΥΓΚΕΚΡΙΜΕΝΑ: 1. ΠΑΡΟΥΣΙΑΖΕΤΑΙ ΜΙΑ ΝΤΕΤΕΡΜΙΝΙΣΤΙΚΗ ΤΕΧΝΙΚΗ ΠΟΥ ΒΑΣΙΖΕΤΑΙ ΣΤΗ ΔΙΑΣΠΑΣΗΕΝΟΣ ΕΠΙΠΕΔΟΥ ΚΑΤΕΥΘΥΝΟΜΕΝΟΥ ΓΡΑΦΟΥ ΣΤΟΥΣ ΕΙΔΙΚΟΥΣ ΕΞΩΕΠΙΠΕΔΟΥΣ ΥΠΟΓΡΑΦΟΥΣ ΤΟΥ. 2. ΑΝΑΠΤΥΣΣΕΤΑΙ ΜΙΑ ΠΙΘΑΝΟΤΙΚΗ ΤΕΧΝΙΚΗ ΓΙΑ ΤΗΝ ΕΥΡΕΣΗ ΠΑΡΑΛΛΗΛΩΝ ΠΡΟΣΕΓΓΙΣΤΙΚΩΝ ΛΥΣΕΩΝ ΣΕ ΝΡ-ΔΥΣΚΟΛΑ ΠΡΟΒΛΗΜΑΤΑ. 3. ΠΑΡΟΥΣΙΑΖΟΝΤΑΙ ΝΕΕΣ "ΠΡΟΣΑΡΜΟΖΟΜΕΝΕΣ" ΠΙΘΑΝΟΤΙΚΕΣ ΤΕΧΝΙΚΕΣ ΓΙΑ ΤΗΝ ΑΝΑΛΥΣΗ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΠΡΟΚΕΙΜΕΝΟΥ ΝΑ ΠΡΟΣΔΙΟΡΙΣΘΕΙ Η ΚΑΤΑ ΜΕΣΗ ΤΙΜΗ ΣΥΜΠΕΡΙΦΟΡΑ ΤΟΥΣ. ΧΡΗΣΙΜΟΠΟΙΟΥΜΕ ΤΙΣ ΠΑΡΑΠΑΝΩ ΤΕΧΝΙΚΕΣ ΓΙΑ ΤΟ ΣΧΕΔΙΑΣΜΟ ΚΑΙ ΤΗΝ ΑΝΑΛΥΣΗ ΑΠΟΔΟΤΙΚΩΝ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ ΓΙΑ ΤΑ ΕΞΗΣ ΠΡΟΒΛΗΜΑΤΑ: 1. ΥΠΟΛΟΓΙΣΤΕΣ ΣΥΝΤΟΜΟΤΕΡΩΝ ΜΟΝΟΠΑΤΙΩΝ ΚΑΙ ΑΠΟΣΤΑΣΕΩΝ ΣΕ ΕΠΙΠΕΔΟΥΣ ΚΑΤΕΥΘΥΝΟΜΕΝΟΥΣ ΓΡΑΦΟΥΣ. 2. ΕΥΡΕΣΗ ΠΡΟΣΕΓΓΙΣΤΙΚΗΣ ΛΥΣΗΣ ΓΙΑ ΤΗΝ ΕΚΔΟΣΗ ΑΠΑΡΙΘΜΗΣΗΣ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ ΤΗΣ ΜΕΓΙΣΤΗΣ ΤΟΜΗΣ. 3. ΧΡΩΜΑΤΙΣΜΟΣ ΤΥΧΑΙΩΝ ΓΡΑΦΩΝ.

Περίληψη σε άλλη γλώσσα

IN THIS THESIS, WE PROVIDE NEW TECHNIQUES FOR THE DESIGN AND ANALYSIS OF PARALLEL ALGORITHMS AND THEIR APPLICATION TO GRAPH PROBLEMS. MORE PRECISELY: 1. WE PRESENT A DETERMINISTIC TECHNIQUE BASED ON THE DECOMPOSITION OF A PLANAR DIGRAPH INTO SPECIAL OUTERPLANAR SUBGRAPHS CALLED HAMMOCKS. 2. WE PRESENT A PROBABILISTIC TECHNIQUE FOR FINDING PARALLEL APPROXIMATION SOLUTIONS FOR NP-HARD PROBLEMS.3. NEW "ADAPTIVE" PROBABILISTIC TECHNIQUES ARE PRESENTED FOR THE AVERAGE-CASE ANALYSIS OF PARALLEL ALGORITHMS. WE USE THE ABOVE TECHNIQUES FOR THE DESIGN ANDANALYSIS OF EFFICIENT PARALLEL ALGORITHMS FOR THE FOLLOWING PROBLEMS: 1. FINDING SHORTEST PATHS AND DISTANCES IN PLANAR DIGRAPH. 2. FINDING AN APPROXIMATION SOLUTION FOR THE ENUMERATION VERSION OF THE MAX CUT PROBLEM. 3. COLORING OF RANDOM GRAPHS.
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/1667
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/1667
Εναλλακτικός τίτλος
TECHNIQUES FOR THE DESIGN OF PARALLEL ALGORITHS AND THEIR APPLICATION TO GRAPH PROBLEMS
Συγγραφέας
ΠΑΝΤΖΙΟΥ, ΓΡΑΜΜΑΤΗ
Ημερομηνία
1991
Ίδρυμα
Πανεπιστήμιο Πατρών. Σχολή Πολυτεχνική. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Εξεταστική επιτροπή
ΣΠΥΡΑΚΗΣ ΠΑΥΛΟΣ
ΠΑΠΑΘΕΟΔΩΡΟΥ ΘΕΟΔΩΡΟΣ
ΤΣΑΚΑΛΙΔΗΣ ΑΘΑΝΑΣΙΟΣ
ΖΑΧΟΣ ΕΥΣΤΑΘΙΟΣ
ΚΥΡΟΥΣΗΣ ΕΛΕΥΘΕΡΙΟΣ
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Επιστήμες Ηλεκτρονικών Υπολογιστών & Πληροφορικής
Μηχανική & Τεχνολογία
Επιστήμες Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού & Μηχανικού Η/Υ
Λέξεις-κλειδιά
PRAM ΑΛΓΟΡΙΘΜΟΣ; ΑΠΟΣΤΑΣΕΙΣ ΣΕ ΕΠΙΠΕΔΟΥΣ ΓΡΑΦΟΥΣ; ΕΙΔΙΚΟΙ ΕΞΩΕΠΙΠΕΔΟΙ ΥΠΟΓΡΑΦΟΙ; ΚΑΤΑ ΜΕΣΗ ΤΙΜΗ ΣΥΜΠΕΡΙΦΟΡΑ ΑΛΓΟΡΙΘΜΩΝ; ΠΡΟΒΛΗΜΑ ΜΕΓΙΣΤΗΣ ΤΟΜΗΣ; ΠΡΟΣΑΡΜΟΖΟΜΕΝΕΣ ΠΙΘΑΝΟΤΙΚΕΣ ΤΕΧΝΙΚΕΣ; ΠΡΟΣΕΓΓΙΣΤΙΚΗ ΛΥΣΗ; ΣΥΝΤΟΜΟΤΕΡΑ ΜΟΝΟΠΑΤΙΑ; ΤΕΧΝΙΚΕΣ ΣΧΕΔΙΑΣΜΟΥ ΠΑΡΑΛΛΗΛΩΝ ΑΛΓΟΡΙΘΜΩΝ; ΧΡΩΜΑΤΙΣΜΟΣ ΤΥΧΑΙΟΥ ΓΡΑΦΟΥ
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά