Πολυπλοκότητα & Μηχανές Turing
Σε αυτό το κεφάλαιο παρουσιάζουμε τις βασικές έννοιες της θεωρίας πολυπλοκότητας. Ξεκινάμε με τον ορισμό της μηχανής Turing και κατόπιν δίνουμε τους ορισμούς των βασικών κλάσεων πολυπλοκότητας P, NP, NP-complete, PSPACE κλπ. Επίσης, διατυπώνουμε ένα βασικό πρόβλημα που έχει μεγάλο ενδιαφέρον στην κρ...
| Κύριοι συγγραφείς: | , |
|---|---|
| Μορφή: | 7 |
| Γλώσσα: | Greek |
| Έκδοση: |
2022
|
| Διαθέσιμο Online: | http://repository.kallipos.gr/handle/11419/8188 |
| id |
kallipos-11419-8188 |
|---|---|
| record_format |
dspace |
| spelling |
kallipos-11419-81882022-03-16T15:57:36Z Πολυπλοκότητα & Μηχανές Turing Complexity & Turing Machines Δραζιώτης, Κωνσταντίνος Draziotis, Konstantinos Σε αυτό το κεφάλαιο παρουσιάζουμε τις βασικές έννοιες της θεωρίας πολυπλοκότητας. Ξεκινάμε με τον ορισμό της μηχανής Turing και κατόπιν δίνουμε τους ορισμούς των βασικών κλάσεων πολυπλοκότητας P, NP, NP-complete, PSPACE κλπ. Επίσης, διατυπώνουμε ένα βασικό πρόβλημα που έχει μεγάλο ενδιαφέρον στην κρυπτογραφία: το πρόβλημα της παραγοντοποίησης. ΄Οπως θα δούμε, αυτό το πρόβλημα ανήκει στην τομή των κλάσεων P και NP. Στο κλασικό μοντέλο υπολογισμού, δηλαδή τη μηχανή Turing, πιστεύουμε ότι το πρόβλημα είναι δύσκολο κατά μέσο όρο. Αν όμως έχουμε στην κατοχή μας έναν κβαντικό υπολογιστή, με αρκετά μεγάλη μνήμη, τότε ο αλγόριθμος του Shor μπορεί να λύσει το πρόβλημα της παραγοντοποίησης σε πολυωνυμικό χρόνο. Σε αυτό το κεφάλαιο παρουσιάζουμε τις βασικές έννοιες της θεωρίας πολυπλοκότητας. Ξεκινάμε με τον ορισμό της μηχανής Turing και κατόπιν δίνουμε τους ορισμούς των βασικών κλάσεων πολυπλοκότητας P, NP, NP-complete, PSPACE κλπ. Επίσης, διατυπώνουμε ένα βασικό πρόβλημα που έχει μεγάλο ενδιαφέρον στην κρυπτογραφία: το πρόβλημα της παραγοντοποίησης. ΄Οπως θα δούμε, αυτό το πρόβλημα ανήκει στην τομή των κλάσεων P και NP. Στο κλασικό μοντέλο υπολογισμού, δηλαδή τη μηχανή Turing, πιστεύουμε ότι το πρόβλημα είναι δύσκολο κατά μέσο όρο. Αν όμως έχουμε στην κατοχή μας έναν κβαντικό υπολογιστή, με αρκετά μεγάλη μνήμη, τότε ο αλγόριθμος του Shor μπορεί να λύσει το πρόβλημα της παραγοντοποίησης σε πολυωνυμικό χρόνο. 2022-03-16T14:52:34Z 2022-03-16T14:52:34Z 7 http://repository.kallipos.gr/handle/11419/8188 el 1 application/pdf |
| institution |
Kallipos |
| collection |
DSpace |
| language |
Greek |
| description |
Σε αυτό το κεφάλαιο παρουσιάζουμε τις βασικές έννοιες της θεωρίας πολυπλοκότητας. Ξεκινάμε με τον ορισμό της μηχανής Turing και κατόπιν δίνουμε τους ορισμούς των βασικών κλάσεων πολυπλοκότητας P, NP, NP-complete, PSPACE κλπ. Επίσης, διατυπώνουμε ένα βασικό πρόβλημα που έχει μεγάλο ενδιαφέρον στην κρυπτογραφία: το πρόβλημα της παραγοντοποίησης. ΄Οπως θα δούμε, αυτό το πρόβλημα ανήκει στην τομή των κλάσεων P και NP. Στο κλασικό μοντέλο υπολογισμού, δηλαδή τη μηχανή Turing, πιστεύουμε ότι το πρόβλημα είναι δύσκολο κατά μέσο όρο. Αν όμως έχουμε στην κατοχή μας έναν κβαντικό υπολογιστή, με αρκετά μεγάλη μνήμη, τότε ο αλγόριθμος του Shor μπορεί να λύσει το πρόβλημα της παραγοντοποίησης σε πολυωνυμικό χρόνο. |
| format |
7 |
| author |
Δραζιώτης, Κωνσταντίνος Draziotis, Konstantinos |
| spellingShingle |
Δραζιώτης, Κωνσταντίνος Draziotis, Konstantinos Πολυπλοκότητα & Μηχανές Turing |
| author_facet |
Δραζιώτης, Κωνσταντίνος Draziotis, Konstantinos |
| author_sort |
Δραζιώτης, Κωνσταντίνος |
| title |
Πολυπλοκότητα & Μηχανές Turing |
| title_short |
Πολυπλοκότητα & Μηχανές Turing |
| title_full |
Πολυπλοκότητα & Μηχανές Turing |
| title_fullStr |
Πολυπλοκότητα & Μηχανές Turing |
| title_full_unstemmed |
Πολυπλοκότητα & Μηχανές Turing |
| title_sort |
πολυπλοκότητα & μηχανές turing |
| publishDate |
2022 |
| url |
http://repository.kallipos.gr/handle/11419/8188 |
| work_keys_str_mv |
AT draziōtēskōnstantinos polyplokotētamēchanesturing AT draziotiskonstantinos polyplokotētamēchanesturing AT draziōtēskōnstantinos complexityturingmachines AT draziotiskonstantinos complexityturingmachines |
| _version_ |
1771301334758195200 |
