Science Wiki
Advertisement

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

Complex systems Theory


Επίπεδα Πολυπλοκότητας

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

Κλιματική Αλλαγή
Κλίμα
Πολυπλοκότητα

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

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

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

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

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

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

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

Προοπτική
Εικονική Πραγματικότητα
Άποψη
Επίπεδο Πολυπλοκότητας

Ετυμολογία[]

Η ονομασία "Πολυπλοκοθεωρία" σχετίζεται ετυμολογικά με την λέξη '"Πολυπλοκότητα".

Εισαγωγή[]

Οι συνηθέστεροι πόροι για τους οποίους ενδιαφερόμαστε είναι ο χρόνος, οπότε αναφερόμαστε για τη χρονική πλοκή του αλγορίθμου, δηλαδή πόσα βήματα χρειάζεται ο αλγόριθμος, και ο χώρος, οπότε μιλάμε για τη χωρική πλοκή, δηλαδή πόσο χώρο, δηλ. μνήμη, χρειάζεται ο αλγόριθμος.

Εκτός από αυτούς τους πόρους, κατά περίπτωση, μπορεί να ενδιαφερόμαστε και για άλλους, όπως για παράδειγμα πόσοι παράλληλοι επεξεργαστές χρειάζονται για να λυθεί ένα πρόβλημα παράλληλα.

Θεματολογία[]

  • Η έννοια του αλγορίθμου
  • Η έννοια της πολυπλοκότητας.
  • Πολυπλοκότητα κατά μέσο όρο και
  • πολυπλοκότητα στη χείριστη περίπτωση.
  • Αναδρομικοί αλγόριθμοι και αναδρομικές εξισώσεις. *Σωροί και ουρές προτεραιότητας.
  • Τεχνικές αναζήτησης:
    • δένδρα αναζήτησης,
    • μετασχηματισμός κλειδιού (hashing)-πολυπλοκότητα κατά μέσο όρο,
    • Union and Find.
  • Τεχνικές διάσχισης σε γράφους:
  • 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.

Υποσημειώσεις[]

Εσωτερική Αρθρογραφία[]

Βιβλιογραφία[]

Ιστογραφία[]


Ikl.jpg Κίνδυνοι ΧρήσηςIkl.jpg

Αν και θα βρείτε εξακριβωμένες πληροφορίες
σε αυτήν την εγκυκλοπαίδεια
ωστόσο, παρακαλούμε να λάβετε σοβαρά υπ' όψη ότι
η "Sciencepedia" δεν μπορεί να εγγυηθεί, από καμιά άποψη,
την εγκυρότητα των πληροφοριών που περιλαμβάνει.

"Οι πληροφορίες αυτές μπορεί πρόσφατα
να έχουν αλλοιωθεί, βανδαλισθεί ή μεταβληθεί από κάποιο άτομο,
η άποψη του οποίου δεν συνάδει με το "επίπεδο γνώσης"
του ιδιαίτερου γνωστικού τομέα που σας ενδιαφέρει."

Πρέπει να λάβετε υπ' όψη ότι
όλα τα άρθρα μπορεί να είναι ακριβή, γενικώς,
και για μακρά χρονική περίοδο,
αλλά να υποστούν κάποιο βανδαλισμό ή ακατάλληλη επεξεργασία,
ελάχιστο χρονικό διάστημα, πριν τα δείτε.



Επίσης,
Οι διάφοροι "Εξωτερικοί Σύνδεσμοι (Links)"
(όχι μόνον, της Sciencepedia
αλλά και κάθε διαδικτυακού ιστότοπου (ή αλλιώς site)),
αν και άκρως απαραίτητοι,
είναι αδύνατον να ελεγχθούν
(λόγω της ρευστής φύσης του Web),
και επομένως είναι ενδεχόμενο να οδηγήσουν
σε παραπλανητικό, κακόβουλο ή άσεμνο περιεχόμενο.
Ο αναγνώστης πρέπει να είναι
εξαιρετικά προσεκτικός όταν τους χρησιμοποιεί.

- Μην κάνετε χρήση του περιεχομένου της παρούσας εγκυκλοπαίδειας
αν διαφωνείτε με όσα αναγράφονται σε αυτήν

IonnKorr-System-00-goog.png



>>Διαμαρτυρία προς την wikia<<

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


Advertisement