Βασικά Στοιχεία Πολυπλοκότητας

• Main Authors: Tsichlas, Konstantinos, Gounaris, Anastasios, Manolopoulos, Ioannis, Τσίχλας, Κωνσταντίνος, Γούναρης, Αναστάσιος, Μανωλόπουλος, Ιωάννης
• Format: 7
• Language: Greek
• Published: 2016
• Subjects: ΑΣΥΜΠΤΩΤΙΚΕΣ ΕΚΤΙΜΗΣΕΙΣ; ΑΝΑΔΡΟΜΙΚΕΣ ΣΧΕΣΕΙΣ; ΓΕΝΝΗΤΡΙΕΣ ΣΥΝΑΡΤΗΣΕΙΣ; ΑΠΛΗΣΤΙΑ; ΔΥΝΑΜΙΚΟΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ; ΟΠΙΣΘΟΔΡΟΜΗΣΗ; ΔΙΑΚΛΑΔΩΣΗ ΜΕ ΠΕΡΙΟΡΙΣΜΟ; ΑΛΓΟΡΙΘΜΟΙ ΑΝΑΖΗΤΗΣΗΣ; ΑΛΓΟΡΙΘΜΟΙ ΤΑΞΙΜΟΜΗΣΗΣ; ΕΠΙΜΕΡΙΣΜΕΝΗ ΑΝΑΛΥΣΗ; ΑΝΤΑΓΩΝΙΣΤΙΚΗ ΑΝΑΛΥΣΗ; ΤΥΧΑΙΟΠΟΙΗΜΕΝΟΙ ΑΛΓΟΡΙΘΜΟΙ; ΑΛΓΟΡΙΘΜΟΙ ΓΡΑΦΗΜΑΤΩΝ; ΑΛΓΟΡΙΘΜΟΙ ΣΥΜΒΟΛΟΣΕΙΡΩΝ; ΠΡΟΣΕΓΓΙΣΤΙΚΟΙ ΑΛΓΟΡΙΘΜΟΙ; Asymptotic Notation; Recursions; Generating Functions; Greedy Algorithms; Dynamic Programming; Backtracking; Branch And Bound; Searching Algorithms; Sorting Algorithms; Amortized Analysis; Competitive Analysis; Approximation Algorithms; Randomized Algorithms; Graph Algorithms; String Algorithms

Η έννοια της κλάσης πολυπλοκότητας. Η έννοια της αιτιοκρατίας και της ανταιτιοκρατίας. Η αιτιοκρατική πολυωνυμική κλάση πολυπλοκότητας P και η ανταιτιοκρατική πολυωνυμική κλάση πολυπλοκότητας NP. Η έννοια της NP πληρότητας και γενικά της πληρότητας για μία κλάση πολυπλοκόπτητας. Μετασχηματισμοί και αναγωγές για απόδειξη της δυσκολίας προβλημάτων. Μικρή λίστα σημαντικών NP-πλήρων προβλημάτων.