Πολυπλοκοθεωρία

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

Complex systems Theory

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

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

Μαθηματικό Χάος
Πολυπλοκότητα
Περιπλοκότητα
Απλότητα

<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.

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

• Αλγόριθμος
• πολυπλοκότητα
• Επίπεδο Πολυπλοκότητας

Ιστογραφία

• Ομώνυμο άρθρο στην Βικιπαίδεια
• Ομώνυμο άρθρο στην Livepedia
• utopia.duth.gr

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

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

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

---

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

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

---