Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/14099
Title: Ανάλυση και σύνθεση κατευθυνόμενων ακυκλικών γραφημάτων στη τοπολογική ταξινόμηση
Other Titles: Analysis and synthesis of directed acyclic graphs in topological sorting
Authors: Σπυρόπουλος, Βασίλειος
Keywords: Τοπολογική ταξινόμηση
Ακυκλικό κατευθυνόμενο γράφημα
Keywords (translated): Topological sorting
DAG
Abstract: Σε ολόκληρη τη ζωή μας χρησιμοποιούμε πληθώρα ταξινομήσεων για να μπορούμε ευκολότερα και πιο άμεσα να έχουμε το επιθυμητό αποτέλεσμα. Οι ταξινομήσεις χωρίζονται σε δυο διακριτές έννοιες, τις σειρές και τη κατηγοριοποίηση. Η τακτοποίηση αντικειμένων σε μια ακολουθία που έχει ταξινομηθεί με βάση κάποιο κριτήριο λέμε ότι είναι μια σειρά. Η ομαδοποίηση αντικειμένων με παρόμοιες ιδιότητες ονομάζεται κατηγοριοποίηση. Στην επιστήμη των υπολογιστών ωστόσο, ταξινόμηση καλείται η τακτοποίηση σε μια διατεταγμένη ακολουθία. Ιστορικά, η ταξινόμηση είναι ένα από τα θέματα που απασχόλησε και απασχολεί τους επιστήμονες, ιδιαίτερα στην επιστήμη των υπολογιστών. Σημαντικά παραδείγματα στη προσφορά της μελέτης της ταξινόμησης, έχουμε ήδη από τη δεκαετία του 1960, με τη τεχνική του προγραμματισμού PERT. Ακολουθούν ο Hamiltonian κύκλος καθώς και το Icosian game. Κύρια μελέτη της ταξινόμησης στην επιστήμη των υπολογισμών γίνεται μέσω των γράφων. Υπάρχουν διάφοροι τύποι γραφημάτων καθώς και διάφοροι αλγόριθμοι ταξινόμησης οι οποίοι αναλύονται ως προς την υλοποίησή τους και την αποδοτικότητά τους, παρακάτω. Η βασική ανάλυση που ακολουθεί γίνεται πάνω στη σύνθεση κατευθυνόμενων ακυκλικών γραφημάτων στη τοπολογική ταξινόμηση, καθώς και η σύνθεση κώδικα σε γλώσσα python, όπου για είσοδο ένα κατευθυνόμενο ακυκλικό γράφημα δίνει ως έξοδο μια πιθανή τοπολογική ταξινόμηση.
Abstract (translated): Throughout our lives we use a variety of sortings so that we can more easily and directly have the desired result. The sortings are divided into two distinct concepts, series and categorization. Arranging objects in a sequence that has been sorted by some criterion is said to be a series. Grouping objects with similar properties is called categorization. In computer science, however, sorting is called ordering in an ordered sequence. Historically, sorting has been one of the topics of concern to scientists, especially computer science. Significant examples in the sorting study have been around since the 1960s, with the PERT programming technique. The Hamiltonian cycle and the Icosian game followed. The main study of sorting in the science of calculations is done through graphs. There are several types of graphs as well as various sorting algorithms which are analyzed in terms of their implementation and efficiency, below. The following basic analysis is based on the synthesis of directional acyclic graphs in the topological sorting, as well as the synthesis of code in python language, where to enter a directed acyclic graph gives as an output a possible topological sorting.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΕ)

Files in This Item:
File Description SizeFormat 
Thesis_Spyropoulos_Vasileios_5426.pdf1.7 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.