Θεωρία Πολυπλοκότητας



Πολυπλοκότητα
Περιπλοκότητα
Απλότητα

<centerΒιολογική Πολυπλοκότητα</center

Κλίμα
Πολυπλοκότητα






Η Θεωρία Πολυπλοκότητας είναι το μέρος εκείνο της Θεωρίας Υπολογισμού, το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος.

Εικονική Πραγματικότητα
Άποψη
Επίπεδο Πολυπλοκότητας
Ετυμολογία[]
Η ονομασία "Πολυπλοκοθεωρία" σχετίζεται ετυμολογικά με την λέξη '"Πολυπλοκότητα".
Εισαγωγή[]
Οι συνηθέστεροι πόροι για τους οποίους ενδιαφερόμαστε είναι ο χρόνος, οπότε αναφερόμαστε για τη χρονική πλοκή του αλγορίθμου, δηλαδή πόσα βήματα χρειάζεται ο αλγόριθμος, και ο χώρος, οπότε μιλάμε για τη χωρική πλοκή, δηλαδή πόσο χώρο, δηλ. μνήμη, χρειάζεται ο αλγόριθμος.
Εκτός από αυτούς τους πόρους, κατά περίπτωση, μπορεί να ενδιαφερόμαστε και για άλλους, όπως για παράδειγμα πόσοι παράλληλοι επεξεργαστές χρειάζονται για να λυθεί ένα πρόβλημα παράλληλα.
Θεματολογία[]
- Η έννοια του αλγορίθμου
- Η έννοια της πολυπλοκότητας.
- Πολυπλοκότητα κατά μέσο όρο και
- πολυπλοκότητα στη χείριστη περίπτωση.
- Αναδρομικοί αλγόριθμοι και αναδρομικές εξισώσεις. *Σωροί και ουρές προτεραιότητας.
- Τεχνικές αναζήτησης:
- δένδρα αναζήτησης,
- μετασχηματισμός κλειδιού (hashing)-πολυπλοκότητα κατά μέσο όρο,
- Union and Find.
- Τεχνικές διάσχισης σε γράφους:
- εξερεύνηση κατά πλάτος (Breadth First Search), **εξερεύνηση κατά βάθος (Depth First Search). *Τεχνικές σχεδίασης αλγορίθμων.
- Divide and conquer:
- αλγόριθμοι ταξινόμησης και επιλογής (πολυπλοκότητα κατά μέσο όρο),
- δυαδική αναζήτηση (binary search).
- Άπληστοι (greedy) αλγόριθμοι:
- Αλγόριθμος Ελάχιστου Κόστους
- συνδετικό δένδρο (minimum cost spanning tree), **βέλτιστα μονοπάτια σε γράφους (αλγόριθμος Dijkstra),
- το συνεχές πρόβλημα του σακκιδίου (knapsack problem),
- 0-1 knapsack,
- επικάλυψη συνόλου (set cover).
- Δυναμικός Προγραμματισμός:
- βέλτιστα μονοπάτια σε γράφους
- αλγόριθμος Bellman
- πρόβλημα βέλτιστου τεμαχισμού (cutting stock problem).
- Δενδροειδείς αλγόριθμοι:
- το πρόβλημα των κ-βασιλισσών.
- Αυξητικοί αλγόριθμοι (incremental algorithms): **εύρεση συνεκτικών συνιστωσών,
- ελάχιστου κόστους συνδετικό δένδρο.
- προβλήματα συνδυαστικής βελτιστοποίησης,
- προβλήματα απόφασης,
- οι κλάσεις P και NP,
- προβλήματα NP-complete και NP-hard.
- Μηχανή Turing,
- Μέθοδος Διαγωνοποίησης,
- Αποφασίσιμες και Μη αποφασίσιμες γλώσσες
- Θεώρημα Rice,
- Θεώρημα Αναδρομής,
- Θεώρημα Smn.
- Μέτρηση πολυπλοκότητας (χρόνος και χώρος),
- Περιορισμοί στους πόρους υπολογισμού,
- Κλάσεις P, NP, PSPACE, και NSPACE,
- Θεώρημα Savitch,
- Σχέσεις μεταξύ κλάσεων πολυπλοκότητας,
- Ιεραρχία κλάσεων DSPACE και DTIME.
- θεώρημα Cook,
- Πολυωνυμική Ιεραρχία Χρόνου,
- Πρόβλημα QBF,
- Αλγόριθμος Monte Carlo,
- Αλγόριθμος Las Vegas.
Υποσημειώσεις[]
Εσωτερική Αρθρογραφία[]
Βιβλιογραφία[]
Ιστογραφία[]
![]() ![]() |
---|
Αν και θα βρείτε εξακριβωμένες πληροφορίες "Οι πληροφορίες αυτές μπορεί πρόσφατα Πρέπει να λάβετε υπ' όψη ότι Επίσης, |
- Μην κάνετε χρήση του περιεχομένου της παρούσας εγκυκλοπαίδειας
αν διαφωνείτε με όσα αναγράφονται σε αυτήν

- Όχι, στις διαφημίσεις που περιέχουν απαράδεκτο περιεχόμενο (άσεμνες εικόνες, ροζ αγγελίες κλπ.)