Η Θεωρητική πληροφορική είναι ένα τμήμα ή υποσύνολο της γενικής επιστήμης των υπολογιστών και των μαθηματικών που επικεντρώνεται σε πιο αφηρημένες έννοιες ή μαθηματικές πτυχές της πληροφορικής και περιλαμβάνει την θεωρία του υπολογισμού.
![]() |
Το λήμμα δεν περιέχει πηγές ή αυτές που περιέχει δεν επαρκούν. |
![Μία καλλιτεχνική αποτύπωση της Μηχανής Τούρινγκ. Οι μηχανές Τούρινγκ χρησιμοποιούνται για την μοντελοποίηση υπολογιστικών συσκευών](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/640px-Maquina.png)
Δεν είναι εύκολο να οριοθετηθούν οι θεωρητικοί τομείς επακριβώς και η Ομάδα Ειδικού Ενδιαφέροντος για Αλγορίθμους και Θεωρία Υπολογισμού (SIGACT) της ACM περιγράφει ότι αποστολή της είναι η προώθηση της θεωρητικής επιστήμης των υπολογιστών και σημειώνει ότι:[1]
Το πεδίο της θεωρητικής επιστήμης των υπολογιστών ερμηνεύεται γενικά, ώστε να περιλαμβάνει αλγορίθμους, δομές δεδομένων, θεωρία πολυπλοκότητας, κατανεμημένο υπολογισμό, παράλληλο υπολογισμό, VLSI, μηχανική μάθηση, υπολογιστική βιολογία, υπολογιστική γεωμετρία, θεωρία της πληροφορίας, κρυπτογραφία, κβαντικό υπολογισμό, υπολογιστική θεωρία αριθμών και άλγεβρας, σημασιολογία των γλωσσών προγραμματισμού και επαλήθευση, θεωρία αυτομάτων, καθώς και τη μελέτη της τυχαιότητας. Οι εργασίες στον τομέα αυτό διακρίνονται συχνά από την έμφαση στην μαθηματική τεχνική και στην αυστηρότητα.
Στον παραπάνω κατάλογο, το περιοδικό της ACM Transactions on Computation Theory προσθέτει τη θεωρία κωδικοποίησης, την υπολογιστική θεωρία μάθησης και τις θεωρητικές πτυχές της επιστήμης των υπολογιστών σε τομείς όπως οι βάσεις δεδομένων, η ανάκτηση πληροφοριών, τα οικονομικά μοντέλα και τα δίκτυα.[2] Παρά το ευρύ πεδίο εφαρμογής , οι "θεωρητικοί" στην επιστήμη των υπολογιστών αυτοπροσδιορίζονται ως διαφορετικοί από τους "ειδικούς εφαρμογών". Κάποιοι αυτοχαρακτηρίζονται ότι εφαρμόζουν «(την πιο θεμελιώδη) επιστήμη (ες) που κρύβεται πίσω από το πεδίο της υπολογιστικής».[3] Άλλοι «θεωρητικοί – ειδικοί εφαρμογών » προτείνουν ότι είναι αδύνατο να διαχωριστεί η θεωρία από την πρακτική εφαρμογή . Αυτό σημαίνει ότι οι αναφερόμενοι ως «θεωρητικοί» χρησιμοποιούν τακτικά την πειραματική επιστήμη (ες) σε λιγότερο θεωρητικούς τομείς όπως η έρευνα λογισμικού συστήματος . Αυτό σημαίνει επίσης ότι υπάρχει περισσότερη συνεργασία παρά ανταγωνισμός αλληλοαναίρεσης μεταξύ θεωρίας και εφαρμογής.
Ιστορία
Ενώ η επίσημοι αλγόριθμοι υπάρχουν για χιλιετίες (ο Ευκλείδειος αλγόριθμος για τον καθορισμό του μέγιστου κοινού διαιρέτη δύο αριθμών εξακολουθεί να χρησιμοποιείται στους υπολογισμούς), δεν ήταν μέχρι το 1936 που οι Άλαν Τούρινγκ, Αλόνζο Τσερτς και Στίβεν Κλέινι επισημοποίησαν τον ορισμό ενός αλγορίθμου σε σχέση με τους υπολογισμούς. Ενώ τα δυαδικά και λογικά συστήματα των μαθηματικών υπήρχαν πριν από το 1703, ήταν ο Γκότφριντ Βίλχελμ Λάιμπνιτς που όρισε την λογική με δυαδικές τιμές για το αληθές και το ψευδές. Ενώ η λογική επαγωγή και μαθηματική απόδειξη υπήρχαν από την αρχαιότητα, το 1931 ο Κουρτ Γκέντελ απέδειξε με το θεώρημα της μη πληρότητας ότι υπήρχαν θεμελιώδεις περιορισμοί σχετικά με το τι θεωρήματα θα μπορούσαν να αποδειχθούν ή να απορρηφθούν.
Αυτές οι εξελίξεις οδήγησαν στη σύγχρονη μελέτη της λογικής και της υπολογισιμότητας, και μάλιστα στον τομέα της επιστήμης της Θεωρητικής Πληροφορικής σαν ολότητα. Η θεωρία της Πληροφορίας προστέθηκε σε αυτό το πεδίο το 1948 με την μαθηματική θεωρία της επικοινωνίας του Κλοντ Σάνον. Την ίδια δεκαετία, ο Ντόναλντ Χεμπ εισήγαγε το μαθηματικό μοντέλο της μάθησης του εγκεφάλου. Με την ενσωμάτωση βιολογικών δεδομένων τα οποία υποστηρίζουν αυτήν την υπόθεση και με κάποιες τροποποιήσεις, το πεδίο των νευρωνικών δικτύων και παράλληλης κατανεμημένες επεξεργασίας θεσπίστηκαν. Το 1971, ο Στίβεν κουκ και ο Λεονίντ Λέβιν, που δούλευαν ανεξάρτητα, απέδειξαν ότι υπάρχουν πρακτικά σχετικά προβλήματα τα οποία είναι NP-πλήρης – ένα σημείο αναφοράς το οποίο είχε σαν αποτέλεσμα την θεωρία της πολυπλοκότητας.
Με την ανάπτυξη της κβαντικής Μηχανικής στις αρχές του 20ου αιώνα θεμελιώθηκε η ιδέα ότι οι μαθηματικές πράξεις μπορούν να εκτελούνται σε ολόκληρη την κυματοσυνάρτηση σωματιδίων. Με άλλα λόγια, θα μπορούσε κανείς να υπολογίσει τις λειτουργίες σε πολλαπλές καταστάσεις ταυτόχρονα. Αυτό οδήγησε στην ιδέα του κβαντικού υπολογιστή στο επόμενο μισό του 20ου αιώνα, η οποία απογειώθηκε (απέκτησε θεωρητική βάση) στη δεκαετία του 1990, όταν ο Πίτερ Σορ έδειξε ότι τέτοιες μέθοδοι θα μπορούσαν να χρησιμοποιηθούν για την παραγοντοποίηση μεγάλων αριθμών σε πολυωνυμικό χρόνο, η οποία, αν εφαρμοστεί, θα καθιστούσε τα πιο σύγχρονα συστήματα κρυπτογραφίας δημόσιου κλειδιού άχρηστα και ανασφαλή.[εκκρεμεί παραπομπή]
Η σύγχρονη θεωρητική έρευνα στην επιστήμη των υπολογιστών βασίζεται σε αυτές τις βασικές εξελίξεις, αλλά περιλαμβάνει πολλά άλλα μαθηματικά και διεπιστημονικά προβλήματα που έχουν τεθεί.
![]() |
![]() |
![]() |
![]() |
P = NP ? | |
Μαθηματική λογική | Θεωρία αυτομάτων | Θεωρία αριθμών | Θεωρία γράφων | Θεωρία υπολογισιμότητας | Θεωρία πολυπλοκότητας |
GNITIRW-TERCES | ![]() |
![]() |
![]() |
![]() | |
Κρυπτογραφία | Θεωρία τύπων | Θεωρία κατηγοριών | Υπολογιστική γεωμετρία | Συνδυαστική βελτιστοποίηση | Κβαντική θεωρία πληροφορικής |
Ενότητες
Αλγόριθμοι
Ένας αλγόριθμος είναι μια βήμα προς βήμα διαδικασία υπολογισμών. Οι αλγόριθμοι χρησιμοποιούνται για υπολογισμού, επεξεργασία δεδομένων, και για αυτοματοποιημένη συλλογιστική.
Ένας αλγόριθμος είναι μια αποτελεσματική μέθοδο που εκφράζεται ως μια πεπερασμένη λίστα[4] από καλώς-ορισμένες οδηγίες[5] για τον υπολογισμό μιας συνάρτησης.[6] Ξεκινώντας από μια αρχική κατάσταση και με αρχικές εισόδους (οι οποίες μπορεί να είναι κενές),[7] οι οδηγίες περιγράφουν έναν υπολογισμό ο οποίος, όταν εκτελείται, προχωρά μέσω ενός πεπερασμένου[8] αριθμού καλώς-ορισμένων διαδοχικών καταστάσεων, οι οποίες τελικά παράγουν "έξοδο"[9] και τερματίζεται σε μια τελική κατάσταση. Η μετάβαση από μια κατάσταση στην επόμενη δεν είναι αναγκαστικά ντετερμινιστική; ορισμένοι αλγόριθμοι, γνωστοί ως πιθανοτικοί αλγόριθμοι, ενσωματώνουν τυχαία είσοδο.[10]
Δομές δεδομένων
Μια δομή δεδομένων είναι ένας συγκεκριμένος τρόπος οργάνωσης δεδομένων σε έναν υπολογιστή έτσι ώστε να μπορούν να χρησιμοποιηθούν αποδοτικότητα.[11][12]
Διαφορετικά είδη δομών δεδομένων είναι κατάλληλα για διαφορετικά είδη εφαρμογών, και μερικά είναι άκρως εξειδικευμένα για συγκεκριμένες εργασίες. Για παράδειγμα, οι βάσεις δεδομένων χρησιμοποιούν B-δενδροειδή ευρετήρια για μικρά ποσοστά ανάκτησης δεδομένων και οι μεταγλωττιστές και οι βάσεις δεδομένων χρησιμοποιούν δυναμικούς πίνακες κατακερματισμού σαν πίνακες αναφοράς.
Οι δομές δεδομένων παρέχουν ένα μέσο για την αποτελεσματική διαχείριση μεγάλης ποσότητας δεδομένων για χρήσεις όπως μεγάλες βάσεις δεδομένων και υπηρεσίες δημιουργίας διαδικτυακού ευρετηρίου. Συνήθως, οι αποδοτικές δομές δεδομένων είναι το κλειδί για τον σχεδιασμό αποτελεσματικών αλγορίθμων. Κάποιες τυπικές μέθοδοι σχεδιασμού και γλώσσες προγραμματισμού τονίζουν τις δομές δεδομένων, παρά τους αλγόριθμους, ως βασικό παράγοντα για την οργάνωση στον σχεδιασμό λογισμικού. Η αποθήκευση και ανάκτηση μπορεί να πραγματοποιηθεί σε δεδομένα αποθηκευμένα και στην κύρια μνήμη και στην δευτερεύουσα μνήμη.
Θεωρία πολυπλοκότητας
Θεωρία πολυπλοκότητας είναι κλάδος της θεωρίας υπολογισμού που εστιάζει στην ταξινόμηση υπολογιστικών προβλημάτων ανάλογα με εγγενή δυσκολία τους, και συσχετίζει αυτές τις κλάσεις μεταξύ τους. Σαν υπολογιστικό πρόβλημα νοείται μια εργασία η οποία κατ 'αρχήν είναι δυνατόν να λυθεί από έναν υπολογιστή, η οποία είναι ισοδύναμη με τη δήλωση ότι το πρόβλημα μπορεί να λυθεί με τη μηχανική εφαρμογή μαθηματικών βημάτων, όπως ένας αλγόριθμος.
Ένα πρόβλημα θεωρείται ότι είναι δύσκολο, αν η λύση του απαιτεί σημαντικούς (υπολογιστικούς) πόρους, ανεξάρτητα από τον αλγόριθμο που χρησιμοποιείται. Η θεωρία τυποποιεί αυτή τηn διαίσθηση, με την εισαγωγή μαθηματικών υπολογιστικών μοντέλων για την μελέτη τέτοιων προβλημάτων και υπολογίζει το σύνολο των πόρων που απαιτούνται για την επίλυσή τους, όπως ο χρόνος επεξεργασίας και ο όγκος των δεδομένων που αποθηκεύονται. Άλλα μέσα για την μέτρηση της πολυπλοκότητας επίσης χρησιμοποιούνται, όπως το ύψος της επικοινωνίας (το οποίο χρησιμοποιείται στην πολυπλοκότητα της επικοινωνίας), ο αριθμός των λογικών πυλών σε ένα (ολοκληρωμένο) κύκλωμα (που χρησιμοποιείται στην πολυπλοκότητα κυκλώματος) και ο αριθμός των επεξεργαστών (που χρησιμοποιείται στην παράλληλη υπολογιστική). Ένας από τους ρόλους της θεωρία της πολυπλοκότητας είναι να καθορίσει τα πρακτικά όρια σχετικά με το τι οι υπολογιστές μπορούν και δεν μπορούν να κάνουν.
Κατανεμημένος υπολογισμός
Ο κατανεμημένος υπολογισμός μελετά κατανεμημένα συστήματα. Ένα κατανεμημένο σύστημα είναι ένα σύστημα λογισμικού στο οποίο τα συστατικά βρίσκονται σε δικτυωμένους υπολογιστές επικοινωνούν και συντονίσουν τις δράσεις τους περνώντας μηνύματα.[13] Τα συστατικά αλληλεπιδρούν μεταξύ τους, προκειμένου να επιτευχθεί ένας κοινός στόχος. Τρία σημαντικά χαρακτηριστικά των κατανεμημένων συστημάτων είναι: συγχρονισμός των στοιχείων, η έλλειψη ενός παγκόσμιου ρολογιού, και ανεξάρτητη αποτυχία των συνιστωσών.[13] Παραδείγματα κατανεμημένων συστημάτων ποικίλλουν από SOA-συστήματα που βασίζονται σε μαζικά multiplayer online παιχνίδια σε eer-to-peer εφαρμογές.
Ένα πρόγραμμα υπολογιστή που τρέχει σε ένα κατανεμημένο σύστημα ονομάζεται κατανεμημένο πρόγραμμα, και κατανεμημένος προγραμματισμός είναι η διαδικασία της γραφής αυτών των προγραμμάτων.[14] Υπάρχουν πολλές εναλλακτικές λύσεις για το μήνυμα που περνά μηχανισμό, συμπεριλαμβανομένου του RPC-όπως συνδέσεις και ουρές μηνυμάτων. Ένας σημαντικός στόχος και πρόκληση των κατανεμημένων συστημάτων είναι η τοποθεσία διαφάνειας.
Παράλληλος Υπολογισμός
Ο παράλληλος υπολογισμός είναι μια μορφή υπολογισμού στην οποία πολλοί υπολογισμοί πραγματοποιούνται ταυτόχρονα,[15] που λειτουργούν με βάση την αρχή ότι τα μεγάλα προβλήματα μπορούν συχνά να διαιρεθούν σε μικρότερα, τα οποία μετά θα λυθούν ταυτόχρονα ("παράλληλα"). Υπάρχουν πολλές διαφορετικές μορφές του παράλληλου υπολογισμού: στο επίπεδο των bit, στο επίπεδο των εντολών, των δεδομένων, και των διεργασιών. Ο παραλληλισμός έχει χρησιμοποιηθεί για πολλά χρόνια, κυρίως σε υψηλών επιδόσεων υπολογιστές, αλλά ενδιαφέρον έχει αυξηθεί τον τελευταίο καιρό λόγω των φυσικών περιορισμών πρόληψης στην κλιμάκωση συχνότητας.[16] Καθώς η κατανάλωση ενέργειας (και συνεπώς η παραγωγή θερμότητας) από τους υπολογιστές έχει γίνει μια ανησυχία κατά τα τελευταία χρόνια,[17] Ο παράλληλος υπολογισμός έχει γίνει κυρίαρχο πρότυπο στην αρχιτεκρονική των υπολογιστών, κυρίως με τη μορφή του multi-core επεξεργαστήs.[18]
Τα προγράμματα παράλληλου υπολογισμού είναι πιο δύσκολο να γραφούν από ό,τι τα αντίστοιχα σειριακά προγράμματα,[19] επειδή ο συγχρονισμός εισάγει αρκετές νέες κατηγορίες των πιθανών σφαλμάτων του λογισμικού, εκ των οποίων η συνθήκη ανταγωνισμού είναι πιο κοινή. Η επικοινωνία και ο συγχρονισμός μεταξύ των διαφόρων δευτερεύουσων εργασιών είναι συνήθως μερικά από τα μεγαλύτερα εμπόδια για να έχει καλή απόδοση ένα παράλληλο πρόγραμμα.
Η μέγιστη δυνατή επιτάχυνση ενός ενιαίου προγράμματος ως αποτέλεσμα παραλληλοποίησης είναι γνωστή ως νόμος του Amdahl.
Πολύ-μεγάλης κλίμακας ολοκλήρωση
Η πολύ μεγάλης κλίμακας ολοκλήρωση (VLSI) είναι η διαδικασία της δημιουργίας ενός ολοκληρωμένου κυκλώματος (IC) συνδυάζοντας χιλιάδες τρανζίστορ σε ένα ενιαίο τσιπ. VLSI ξεκίνησε τη δεκαετία του 1970, όταν πολύπλοκoi ημιαγωγοί και τεχνολογίες επικοινωνίας αναπτύχθηκαν. Ο μικροεπεξεργαστής είναι μια VLSI συσκευή. Πριν από την εισαγωγή της τεχνολογίας VLSI πιο ICs είχε ένα περιορισμένο σύνολο λειτουργιών που θα μπορούσε να εκτελέσει. Ένα ηλεκτρονικό κύκλωμα μπορεί να αποτελείται από ένα CPU, ROM, RAM και άλλα glue logic. Το VLSI επιτρέπει σε IC κατασκευαστές να προσθέτονται όλα αυτά σε ένα τσιπ.
Μηχανική μάθηση
Η μηχανική μάθηση είναι ένας επιστημονικός κλάδος που ασχολείται με την δημιουργία και την ανάλυση αλγορίθμων οι οποίοι μπορούν να μάθουν απο τα δεδομένα.[20] Τέτοιοι αλγόριθμοι λειτουργούν με την δημιουργία ενός μοντέλου βασισμένου στα δεδομένα εισόδου [21]:2 και χρησιμοποιούν αυτά για να κάνουν προβλέψεις ή αποφάσεις, αντί να ακολουθούν ρητά μία ακολουθία από προγραμματισμένες οδηγίες.
Η μηχανική μάθηση μπορεί να θεωρηθεί ως υποπεδίο της επιστήμης των υπολογιστών και της στατιστικής. Έχει ισχυρούς δεσμούς με την τεχνητή νοημοσύνη και την βελτιστοποίηση, οι οποίες παρέχουν τις μεθόδους, τη θεωρία και τομείς εφαρμογής στον κλάδο. Η μηχανή μάθησης χρησιμοποιείται σε μια σειρά υπολογιστικών εργασιών όπου σχεδιάσμένοι και προγραμματισμένοι σαφής, με βάση κανόνες αλγόριθμοι δεν είναι αρκετά αποδοτικοί ή ακόμα και ανέφικτοι. Παραδείγματα εφαρμογών περιλαμβάνουν φίλτρο spam, οπτική αναγνώριση χαρακτήρων (OCR),[22] μηχανές αναζήτησης και υπολογιστική όραση. Η μηχανή μάθησης μερικές φορές συγχέεται με εξόρυξη δεδομένων,[23] παρόλο που εστιάζει περισσότερο στην διερευνητική ανάλυση δεδομένων.[24] Η μηχανή μάθησης και ανάγνωσης σχεδίου "μπορεί να θεωρηθεί ως διπλή όψη του ίδιου πεδίου." [21]:vii
Υπολογιστική Βιολογία
Η υπολογιστική βιολογία περιλαμβάνει την ανάπτυξη και την εφαρμογή των αναλυτικών στοιχείων και θεωρητικών μεθόδων, μαθηματικών μοντέλων και υπολογιστικών τεχνικών προσομοίωσης για τη μελέτη των βιολογικών, συμπεριφορικών και κοινωνικών συστημάτων.[25] Το πεδίο είναι γενικώς ορισμένο και περιλαμβάνει θεμελιώδεις έννοιες της πληροφορικής, των εφαρμοσμένων μαθηματικών, του animation, της στατιστικής, της βιοχημείας, της χημείας, της βιοφυσικής, της μοριακής βιολογίας, της γενετικής, της γονιδιωματικής, της οικολογίας, της εξέλιξης, της ανατομίας, της νευροεπιστήμης, και της οπτικοποίησης.[26]
Υπολογιστική Βιολογία είναι διαφορετική από τον βιολογικό υπολογισμό, ο οποίος είναι ένα υποπεδίο της επιστήμης των υπολογιστών και της μηχανικής υπολογιστών χρησιμοποιώντας βιομηχανολογία και βιολογία για την κατασκευή υπολογιστών , αλλά είναι παρόμοια με την βιοπληροφορική, η οποία είναι μια διεπιστημονική επιστήμη που χρησιμοποιούν υπολογιστές για την αποθήκευση και την επεξεργασία βιολογικών δεδομένων.
Υπολογιστική γεωμετρία
Η υπολογιστική γεωμετρία είναι ένας κλάδος της επιστήμης των υπολογιστών που αφιερώνεται στη μελέτη των αλγορίθμων που μπορεί να δηλωθεί από την άποψη της γεωμετρίας. Μερικά καθαρά γεωμετρικά προβλήματα προκύπτουν από τη μελέτη των υπολογιστικών αλγορίθμων γεωμετρικής, και τα προβλήματα αυτά θεωρούνται επίσης να είναι μέρος της υπολογιστικής γεωμετρίας. Ενώ η σύγχρονη υπολογιστική γεωμετρία είναι μια πρόσφατη εξέλιξη, είναι ένας από τους παλαιότερους τομείς της πληροφορικής με ιστορία που εκτείνεται πίσω στην αρχαιότητα. Ένα αρχαίο πρόδρομο είναι η σανσκριτική πραγματεία Shulba Σούτρες, ή «οι κανόνες της χορδής», ότι είναι ένα βιβλίο των αλγορίθμων γραμμένο στα 800 π.Χ.. Το βιβλίο ορίζει βήμα-βήμα τις διαδικασίες για την κατασκευή γεωμετρικών αντικειμένων όπως βωμούς χρησιμοποιώντας ένα πάσσαλο και χορδή.
Η κύρια ώθηση για την ανάπτυξη της υπολογιστικής γεωμετρίας ως επιστήμη ήταν η πρόοδος στα γραφικά υπολογιστών με τη βοήθεια υπολογιστών σχεδιασμού και την κατασκευή (CAD / CAM), αλλά και πολλά προβλήματα στην υπολογιστική γεωμετρία είναι κλασικά στη φύση, και μπορεί να προέρχονται από μαθηματική απεικόνιση. Άλλες σημαντικές εφαρμογές της υπολογιστικής γεωμετρίας περιλαμβάνουν ρομποτική (προγραμματισμό κινήσεων και προβλήματα ορατότητας), σύστημα γεωγραφικών πληροφοριών (GIS) (την γεωμετρική θέση και την αναζήτηση, τον σχεδιασμό της διαδρομής), ολοκληρωμένο κύκλωμα και τον σχεδιασμό (IC γεωμετρία σχεδιασμού και ελέγχου), με τη βοήθεια υπολογιστών μηχανικής (CAE) (πλέγμα γενιά), υπολογιστής όρασης (3D ανακατασκευή).
Θεωρία της Πληροφορίας
Η θεωρία της πληροφορίας είναι ένας κλάδος των εφαρμοσμένων μαθηματικών , των ηλεκτρολόγων μηχανικών και της επιστήμης των υπολογιστών που αφορούν την ποσοτικοποίηση των πληροφοριών . Η θεωρία της πληροφορίας αναπτύχθηκε από τον Claude E. Shannon που βρήκε τα θεμελιώδη όρια σχετικά με την λειτουργία επεξεργασίας σήματος, όπως συμπίεση των δεδομένων,την αξιοπιστία της αποθήκευσης και την επικοινωνία δεδομένων . Από την ίδρυσή της έχει διευρυνθεί να βρει εφαρμογές σε πολλούς άλλους τομείς συμπεριλαμβανομένων στατιστική συμπερασματολογία , επεξεργασία φυσικής γλώσσας , κρυπτογραφία , νευροβιολογία[27] , εξέλιξη[28] και τη λειτουργία[29] των μοριακών κωδικών , την επιλογή μοντέλου στην οικολογία ,[30] Θερμοδυναμικής,[31] κβαντικών υπολογιστών , γλωσσολογία , εντοπισμού λογοκλοπής,[32] την αναγνώριση προτύπων , την ανίχνευση ανωμαλιών και άλλων μορφών ανάλυσης δεδομένων.[33]
Οι εφαρμογές των θεμελιωδών θεμάτων της θεωρίας πληροφοριών περιλαμβάνουν την συμπίεση δεδομένων χωρίς απώλειες (π.χ. αρχεία ZIP),την συμπίεση δεδομένων με απώλειες (π.χ. MP3s και αρχεία JPEGs), και την κωδικοποίηση καναλιού (π.χ. για την ψηφιακή συνδρομητική γραμμή (DSL)). Το πεδίο είναι η διασταύρωση των μαθηματικών, της στατιστικής, της επιστήμης των υπολογιστών, της φυσικής, της νευροβιολογίας και των μηχανολόγων μηχανικών. Ο αντίκτυπός της ήταν ζωτικής σημασίας για την επιτυχία των αποστολών Voyager στο μακριπρόθεσμο διάστημα, της εφεύρεσης του Compact Disc, της σκοπιμότητας των κινητών τηλεφώνων, της ανάπτυξης του Διαδικτύου, της μελέτης της γλωσσολογίας και της ανθρώπινης αντίληψης, της κατανόησης των μαύρων τρυπών και πολλά άλλα πεδία. Σημαντικοί υπο-τομείς της θεωρίας της πληροφορίας είναι η κωδικοποίηση της πηγής, η κωδικοποίηση του καναλιού, η αλγοριθμική θεωρία της πολυπλοκότητας, η αλγοριθμική θεωρία της πληροφορίας, οι πληροφορίες θεωρίας της ασφάλειας, καθώς και τα μέτρα των πληροφοριών.
Κρυπτογραφία
Κρυπτογραφία είναι η πρακτική και η μελέτη των τεχνικών για την ασφαλή επικοινωνία με την παρουσία τρίτων (που ονομάζονται αντίπαλοι).[34] Γενικότερα, πρόκειται για την κατασκευή και την ανάλυση των πρωτοκόλλων που ξεπερνούν την επιρροή των αντιπάλων[35] και τα οποία σχετίζονται με διάφορες πτυχές της ασφάλειας των πληροφοριών, όπως το απόρρητο των δεδομένων, την ακεραιότητα των δεδομένων, την πιστοποίηση και τη μη αποκήρυξη.[36] Η σύγχρονη κρυπτογραφία τέμνει τις επιστήμες των μαθηματικών, της επιστήμης των υπολογιστών και των ηλεκτρολόγων μηχανικών.Οι εφαρμογές της κρυπτογραφίας περιλαμβάνουν κάρτες ΑΤΜ, κωδικούς πρόσβασης του υπολογιστή και το ηλεκτρονικό εμπόριο.
Η σύγχρονη κρυπτογραφία βασίζεται σε μεγάλο βαθμό στην μαθηματική θεωρία και την πρακτικη επιστήμη των υπολογιστών . Οι κρυπτογραφικοί αλγόριθμοι σχεδιάστηκαν γύρω από την υπολογιστικές σκληρές παραδοχές, κατασκευάζοντας τέτοιους αλγορίθμους που είναι δύσκολο να σπάσουν στην πράξη από οποιονδήποτε αντίπαλο. Είναι θεωρητικά δυνατό να σπάσει ένα τέτοιο σύστημα, αλλά αυτό είναι ανέφικτο να το συμβεί από οποιοδήποτε γνωστό πρακτικό μέσο. Ως εκ τούτου, τα συστήματα αυτά ονομάζονται υπολογιστικά ασφαλής.Οι θεωρητικές εξελίξεις π.χ. οι βελτιώσεις στη παραγοντοποίηση των ακεραίων αλγορίθμων και η ταχύτερη τεχνολογία των υπολογιστών απαιτούν αυτές τις λύσεις και πρέπει να προσαρμόζονται συνεχώς. Υπάρχουν συστήματα πληροφοριών θεωρητικά ασφαλείς που Πρότυπου: Δεν είναι τυπογραφικό λάθος δεν μπορεί να σπάσει ακόμη και με απεριόριστη υπολογιστική δύναμη—ένα παράδειγμα είναι το one-time pad—αλλά τα συστήματα αυτά είναι πιο δύσκολο να εφαρμοστούν από τις καλύτερα θεωρητικά εύθραυστα αλλά υπολογιστικά ασφαλείς μηχανισμούς.
Κβαντικός υπολογισμός
Ένας κβαντικός υπολογιστής είναι ένα σύστημα υπολογισμού το οποίο κάνει άμεση χρήση κβαντικών φαινομένων, όπως η υπέρθεση και η εμπλοκή, ώστε να επεξεργαστεί δεδομένα.[37] Οι κβαντικοί υπολογιστές διαφέρουν από τους ψηφιακούς υπολογιστές που βασίζονται σε τρανζίστορ. Ενώ οι ψηφιακοί υπολογιστές απαιτούν τα δεδομένα να είναι κωδικοποιημένα σε δυαδική μορφή ψηφίων (bits), καθένα από τα οποία παίρνουν πάντα μία από τις δύο καθορισμένες καταστάσεις (0 ή 1), οι κβαντικοί υπολογιστές χρησιμοποιούν qubits (κβαντικά bits), τα οποία μπορούν να παίρνουν πολλές καταστάσεις. Ένα θεωρητικό μοντέλο κβαντικής μηχανής είναι η μηχανή Τούρινγκ, γνωστή και ως η καθολική κβαντική μηχανή. Οι κβαντικοί υπολογιστές μοιράζονται θεωρητικές ομοιότητες με τους μη-προσδιοριστούς και πιθανοτικούς υπολογιστές· ένα παράδειγμα είναι η δυνατότητα να βρίσκεται ταυτόχρονα σε περισσότερες από μία κατάσταση. Ο κλάδος των κβαντικών υπολογιστών εισήχθη για πρώτη φορά από τον από τον Yuri Manin το 1980[38] και τον Richard Feynman το 1982.[39][40] Ένας κβαντικός υπολογιστής με περιστροφές ως κβαντικά bits, επίσης σχεδιάστηκε για χρήση ως ένα κβαντικό χωροχρόνο το 1968.[41]
Το 2014, η κβαντική πληροφορική βρίσκεται ακόμα στο ξεκίνημα αλλά έχουν διεξαχθεί πειράματα στα οποία εκτελέστηκαν κβαντικοί υπολογισμοί σε έναν πολύ μικρό αριθμό qubits.[42] Η πρακτική και η θεωρητική έρευνα συνεχίζεται, και πολλές εθνικές κυβερνήσεις και στρατιωτικές υπηρεσίες τις χρηματοδωτούν, στηρίζοντας έτσι την κβαντική υπολογιστική έρευνα για την ανάπτυξη κβαντικών υπολογιστών, τόσο για πολιτικούς όσο και για λόγους εθνικής ασφαλείας, όπως κρυπτανάλυσης.[43]
Υπολογιστική θεωρία αριθμού
Η υπολογιστική θεωρία αριθμού, επίσης γνωστή ως αλγοριθμική θεωρία αριθμού, είναι η μελέτη των αλγορίθμων για τους θεωρητικούς υπολογισμούς αριθμού. Το πιό γνωστό πρόβλημα στον τομέα είναι η παραγοντοποίηση ακέραιων αριθμών.
Συμβολικός υπολογισμός
Η άλγεβρα υπολογιστών, αποκαλούμενη επίσης ως συμβολικός υπολογισμός ή αλγεβρικός υπολογισμός είναι μια επιστημονική περιοχή η οποία αναφέρεται στη μελέτη και την ανάπτυξη των αλγορίθμων και του λογισμικού για το χειρισμό των μαθηματικών εκφράσεων και άλλων μαθηματικών αντικειμένων. Αν και, μιλώντας κατάλληλα, η άλγεβρα υπολογιστών πρέπει να είναι υποπεδίο του επιστημονικού υπολογισμού ,θεωρούνται γενικά ως ευδιάκριτοι τομείς επειδή ο επιστημονικός υπολογισμός είναι συνήθως βασισμένος στον αριθμητικό υπολογισμό με τους κατά προσέγγιση αριθμούς κινητής υποδιαστολής, ενώ ο συμβολικός υπολογισμός υπογραμμίζει τον ακριβή υπολογισμό με τις εκφράσεις περιέχοντας τις μεταβλητές που δεν έχουν οποιαδήποτε δεδομένη αξία και χειρίζονται έτσι ως σύμβολα (επομένως το όνομα του συμβολικού υπολογισμού).
Οι εφαρμογές λογισμικού που εκτελούν τους συμβολικούς υπολογισμούς καλούνται συστήματα άλγεβρας υπολογιστών, με το σύστημα όρου που υπαινίσσεται στην πολυπλοκότητα των κύριων εφαρμογών που περιλαμβάνει, τουλάχιστον, μια μέθοδο για να αντιπροσωπεύσει τα μαθηματικά στοιχεία σε έναν υπολογιστή, μια γλώσσα προγραμματισμού χρηστών συνήθως διαφορετικός από τη γλώσσα που χρησιμοποιείται για την εφαρμογή), ένας αφιερωμένος διευθυντής μνήμης, ένα ενδιάμεσο με τον χρήστη για τον εισόδου-εξόδου από τις μαθηματικές εκφράσεις, ένα μεγάλο σύνολο ρουτινών για να εκτελέσει τις συνηθισμένες διαδικασίες, όπως την απλοποίηση των εκφράσεων, τη διαφοροποίηση που χρησιμοποιούν τον κανόνα αλυσίδων, την πολυωνυμική παραγοντοποίηση, την αόριστη ολοκλήρωση,κ.λ.π.
Σημασιολογία προγράμματος
Στη θεωρία γλώσσας προγραμματισμού, η σημασιολογία είναι ο τομέας ενδιαφερόμενος για την αυστηρή μαθηματική μελέτη της έννοιας των γλωσσών προγραμματισμού .Κάνει έτσι με την αξιολόγηση της έννοιας των συντακτικά νομικών σειρών που καθορίζεται από μια συγκεκριμένη γλώσσα προγραμματισμού, παρουσιάζοντας τον υπολογισμό σχετικό. Σε αυτή την περίπτωση ότι η αξιολόγηση θα ήταν συντακτικά παράνομων σειρών, το αποτέλεσμα θα ήταν μη-υπολογίσιμο.Η σημασιολογία περιγράφει τις διαδικασίες που ένας υπολογιστής ακολουθεί κατά εκτέλεση ενός προγράμματος σε εκείνη την συγκεκριμένη γλώσσα.Αυτό μπορεί να παρουσιαστεί με την περιγραφή της σχέσης μεταξύ της εισαγωγής και της παραγωγής ενός προγράμματος ή μια εξήγηση για το πώς το πρόγραμμα θα εκτελέσει σε μια ορισμένη πλατφόρμα, ως εκ τού του δημιουργώντας ένα πρότυπο του υπολογισμού.
Επίσημες μέθοδοι
Οι επίσημες μέθοδοι είναι ένα ιδιαίτερο είδος βασισμένων στα μαθηματικά τεχνικών για την προδιαγραφή, την ανάπτυξη και την επαλήθευση του λογισμικού και των συστημάτων υλικού. Η χρήση των επίσημων μεθόδων για το σχέδιο λογισμικού και υλικού παρακινείται από την προσδοκία που, όπως σε άλλες ειδικότητες εφαρμοσμένης μηχανικής, που εκτελούν την κατάλληλη μαθηματική ανάλυση μπορεί να συμβάλει στην αξιοπιστία και την ευρωστία ενός σχεδίου.
Οι επίσημες μέθοδοι περιγράφονται καλύτερα ως εφαρμογή ενός αρκετά ευρέος φάσματος των θεωρητικών βασικών αρχών πληροφορικής,ιδίως υπολογισμοί λογικής, επίσημες γλώσσες,θεωρία αυτομάτων, και σημασιολογία προγράμματος, αλλά και συστήματα τύπων και αλγεβρικοί τύποι στοιχείων στα προβλήματα στο λογισμικό και την προδιαγραφή και την επαλήθευση υλικού.
Θεωρία αυτομάτων
Η θεωρία αυτομάτων είναι η μελέτη της ''αφηρημένης μηχανικής'' και των ''αυτoμάτων'', καθώς και τα υπολογιστικά προβλήματα που μπορούν να επιλυθούν με τη χρήση αυτών. Είναι μια θεωρία στη θεωρητική επιστήμη των υπολογιστών, με Διακριτά Μαθηματικά (ένα τμήμα των Μαθηματικών καθώς επίσης και της Επιστήμης Υπολογιστών). Η λέξη ''αυτόματα'' προέρχεται από την ελληνική λέξη αὐτόματα, που σημαίνει "αυτενεργό".
Η θεωρία αυτομάτων είναι η μελέτη της αυτο-λειτουργίας των εικονικών μηχανών για να βοηθήσουν στην κατανόηση της λογικής διεργασίας εισόδου και εξόδου, με ή χωρίς ενδιάμεσο στάδιο(α) του υπολογισμού (ή οποιαδήποτε λειτουργία / διαδικασία).
Θεωρία Κωδικοποίησης
Η θεωρία κωδικοποίησης είναι η μελέτη των ιδιοτήτων και της καταλληλότητας των κωδικών για μια συγκεκριμένη εφαρμογή. Οι κωδικοί χρησιμοποιούνται για τη συμπίεση δεδομένων, κρυπτογραφία, διόρθωσης σφαλμάτων και, πιο πρόσφατα, για την κωδικοποίηση του δικτύου. Οι κωδικοί μελετώνται από διάφορους επιστημονικούς κλάδους, όπως η θεωρία της πληροφορίας, ηλεκτρονική μηχανική, μαθηματικών και από την πληροφορική, με σκοπό την σχεδίαση και υλοποίηση αποδοτικών και αξιόπιστων μεθόδων μετάδοσης δεδομένων. Αυτό συνήθως περιλαμβάνει την αφαίρεση των πλεονασμών και τη διόρθωση (ή ανίχνευσης) των σφαλμάτων στα μεταδιδόμενα δεδομένα.
Υπολογιστική Θεωρία Μάθησης
Τα θεωρητικά αποτελέσματα στην μηχανική μάθηση ασχολούνται κυρίως με έναν τύπο της επαγωγικής μάθησης που ονομάζεται εποπτευόμενη μάθηση. Στην επιβλεπόμενη μάθηση, ένας αλγόριθμος δίνει δείγματα που επισημαίνονται με κάποιο χρήσιμο τρόπο. Για παράδειγμα, τα δείγματα θα μπορούσανε να είναι περιγραφές των μανιταριών και οι ετικέτες να δείχνουν εάν τα μανιτάρια είναι φαγώσιμα ή όχι. Ο αλγόριθμος παίρνει αυτά τα προηγουμένως επισημασμένα δείγματα και τα χρησιμοποιεί για να φτιάξει έναν ταξινομητή. Αυτός ο ταξινομητής είναι μια λειτουργία που εκχωρεί ετικέτες στα δείγματα, συμπεριλαμβανομένων των δειγμάτων που δεν έχουν ποτέ παρατηρηθεί προηγουμένως από τον αλγόριθμο. Ο στόχος του εποπτευόμενου αλγόριθμου μάθησης είναι η βελτιστοποίηση ως ενός σημείου της απόδοσης, όπως την ελαχιστοποίηση του αριθμού των λαθών που έγιναν σε νέα δείγματα.
Περαιτέρω ανάγνωση
Εξωτερικοί σύνδεσμοι
- Theory of Computing Report
- Δίκτυο διακριτών μαθηματικών και αλγορίθμων
- Λίστα συνεδρίων στην θεωρητική πληροφορική
- Theoretical Computer Science - StackExchange, ένα site εωρτήσεων και απαντήσεων για τους ερευνητές στη θεωρητική πληροφορική
- SIGACT directory of additional theory links
- Theory Matters Wiki Θεωρητική Πληροφορική (TCS) Υπεράσπιση Wiki
- Usenet comp.theory[νεκρός σύνδεσμος]
- Computer Science Animated
- http://theory.csail.mit.edu/ @ Massachusetts Institute of Technology
Οργανισμοί
- ACM
- SIAM
- Ευρωπαϊκή Ένωση για τη Θεωρητική Επιστήμη των Υπολογιστών
- SIGACT
Παραπομπές
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.