Ανασκόπηση βασικών εννοιών της θεωρίας πολυπλοκότητας αλγορίθμων

Abstract

Στην παρούσα πτυχιακή εργασία γίνεται ανάλυση των βασικών εννοιών της θεωρίας υπολογιστικής πολυπλοκότητας. Η θεωρία της πολυπλοκότητας είναι το μέρος εκείνο της θεωρίας υπολογισμού, το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος. Επομένως η θεωρία πολυπλοκότητας αποτελεί βασικό δομικό λίθο της ανάλυσης αλγορίθμων και κεντρικό γνωστικό πεδίο της επιστήμης υπολογιστών. Στο πρώτο κεφάλαιο αναφέρονται οι βασικές έννοιες του υπολογιστικού προβλήματος, του στιγμιότυπου ενός προβλήματος και του αλγόριθμου. Στο δεύτερο κεφάλαιο περιγράφονται δύο βασικοί πόροι για την ανάλυση της πολυπλοκότητας που είναι η χρονική και η χωρική πολυπλοκότητα των αλγορίθμων. To τρίτο κεφάλαιο αναφέρεται στην ασυμπτωτική εκτίμηση των αλγορίθμων, η οποία προσδιορίζει την τάξη μεγέθους του χρόνου εκτέλεσής τους. Επίσης αναλύεται ο ασυμπτωτικός συμβολισμός και συγκεκριμένα οι συμβολισμοί Θ, Ο, Ω, ω, ο. Στο τέταρτο κεφάλαιο περιγράφονται οι αναδρομικοί αλγόριθμοι, οι αλγόριθμοι τύπου «διαίρει και βασίλευε» καθώς και οι «άπληστοι» αλγόριθμοι. Το πέμπτο κεφάλαιο παρουσιάζει τον δυναμικό προγραμματισμό και τη θεωρία των γραφημάτων. Το έκτο και τελευταίο κεφάλαιο περιγράφει τους αποδοτικούς αλγόριθμους και αναλύει τις κλάσεις πολυπλοκότητας P και NP.