Προβολή πηγαίου κώδικα για τη σελίδα Θεωρητική Πληροφορική

{{πηγές|21|05|2015}}
[[Αρχείο:Maquina.png|thumb|Μία καλλιτεχνική αποτύπωση της Μηχανής Τούρινγκ. Οι μηχανές Τούρινγκ χρησιμοποιούνται για την μοντελοποίηση υπολογιστικών συσκευών.|εναλλ.=Μία καλλιτεχνική αποτύπωση της Μηχανής Τούρινγκ. Οι μηχανές Τούρινγκ χρησιμοποιούνται για την μοντελοποίηση υπολογιστικών συσκευών]]
'''Η Θεωρητική πληροφορική''' είναι ένα τμήμα ή υποσύνολο της γενικής  [[επιστήμη των υπολογιστών|επιστήμης των υπολογιστών]] και των [[Μαθηματικά|μαθηματικών]] που επικεντρώνεται σε πιο αφηρημένες έννοιες ή μαθηματικές πτυχές της πληροφορικής και περιλαμβάνει την [[Θεωρία υπολογισμού|θεωρία του υπολογισμού]].

Δεν είναι εύκολο να οριοθετηθούν οι θεωρητικοί τομείς επακριβώς και η Ομάδα Ειδικού Ενδιαφέροντος για Αλγορίθμους και Θεωρία Υπολογισμού (SIGACT) της [[Association for Computing Machinery|ACM]] περιγράφει ότι αποστολή της είναι η προώθηση της θεωρητικής επιστήμης των υπολογιστών και σημειώνει ότι:<ref>{{cite web | title =  SIGACT | url =  http://sigact.acm.org | accessdate =  2009-03-29 | archive-date =  2010-03-12 | archive-url =  https://web.archive.org/web/20100312214141/http://sigact.acm.org/ | url-status =  dead }}</ref>

{{"|Το πεδίο της θεωρητικής επιστήμης των υπολογιστών ερμηνεύεται γενικά, ώστε να περιλαμβάνει [[αλγόριθμος|αλγορίθμους]], [[δομές δεδομένων]], [[θεωρία πολυπλοκότητας]], [[Παράλληλα και κατανεμημένα συστήματα|κατανεμημένο υπολογισμό]], [[Παράλληλα και κατανεμημένα συστήματα|παράλληλο υπολογισμό]], [[VLSI]], [[μηχανική μάθηση]], [[υπολογιστική βιολογία]], [[υπολογιστική γεωμετρία]], [[θεωρία της πληροφορίας]], [[κρυπτογραφία]], [[Κβαντικός υπολογισμός|κβαντικό υπολογισμό]], [[Αλγοριθμική Θεωρία Αριθμών|υπολογιστική θεωρία αριθμών]] και [[άλγεβρα]]ς, [[Τυπική σημασιολογία των γλωσσών προγραμματισμού|σημασιολογία των γλωσσών προγραμματισμού]] και [[Τυπική επαλήθευση|επαλήθευση]], [[θεωρία αυτομάτων]], καθώς και τη μελέτη της [[πιθανοτικός αλγόριθμος|τυχαιότητα]]ς. Οι εργασίες στον τομέα αυτό διακρίνονται συχνά από την έμφαση στην μαθηματική τεχνική και στην [[rigor#Mathematical rigour|αυστηρότητα]].}}

Στον παραπάνω κατάλογο, το περιοδικό της ACM Transactions on Computation Theory προσθέτει τη [[θεωρία κωδικοποίησης]], την [[υπολογιστική θεωρία μάθησης]] και τις θεωρητικές πτυχές της επιστήμης των υπολογιστών σε τομείς όπως οι  [[βάσεις δεδομένων]], η [[ανάκτηση πληροφοριών]], τα οικονομικά μοντέλα και τα [[Δίκτυο υπολογιστών|δίκτυα]].<ref>{{cite web| title =  ToCT| url =  http://toct.acm.org/journal.html| accessdate =  2010-06-09| archiveurl =  https://web.archive.org/web/20101104004846/http://toct.acm.org/journal.html| archivedate =  2010-11-04| url-status =  dead}}</ref> Παρά το ευρύ πεδίο εφαρμογής , οι "θεωρητικοί" στην επιστήμη των υπολογιστών αυτοπροσδιορίζονται ως διαφορετικοί από τους "ειδικούς εφαρμογών". Κάποιοι αυτοχαρακτηρίζονται ότι εφαρμόζουν «(την πιο θεμελιώδη) επιστήμη (ες) που κρύβεται πίσω από το πεδίο της υπολογιστικής».<ref>{{cite web|url=https://www.sigact.org/Docs/challenges_tcs.html|title=Challenges for Theoretical Computer Science: Theory as the Scientific Foundation of Computing|last=David Johnson|first=|date=Ιανουάριος 2000 |website=Researchgate.net |archiveurl=https://web.archive.org/web/20110821043851/http://www.research.att.com/~dsj/nsflist.html |archivedate=2011-08-21 |accessdate=2018-01-27}}</ref> Άλλοι «θεωρητικοί – ειδικοί εφαρμογών » προτείνουν ότι είναι αδύνατο να διαχωριστεί η θεωρία από την πρακτική εφαρμογή . Αυτό σημαίνει ότι οι αναφερόμενοι ως «θεωρητικοί» χρησιμοποιούν τακτικά την πειραματική επιστήμη (ες) σε λιγότερο θεωρητικούς τομείς όπως η έρευνα λογισμικού συστήματος . Αυτό σημαίνει επίσης ότι υπάρχει περισσότερη συνεργασία παρά ανταγωνισμός αλληλοαναίρεσης μεταξύ θεωρίας και εφαρμογής.

== Ιστορία ==
Ενώ η επίσημοι αλγόριθμοι υπάρχουν για χιλιετίες (ο [[Ευκλείδειος αλγόριθμος]] για τον καθορισμό του [[μέγιστου κοινού διαιρέτη]] δύο αριθμών εξακολουθεί να χρησιμοποιείται στους υπολογισμούς), δεν ήταν μέχρι το 1936 που οι [[Άλαν Τούρινγκ]], [[Αλόνζο Τσερτς]] και [[Στίβεν Κλέινι]] επισημοποίησαν τον ορισμό ενός αλγορίθμου σε σχέση με τους υπολογισμούς. Ενώ τα δυαδικά και [[Τυπικό σύστημα|λογικά συστήματα]] των μαθηματικών υπήρχαν πριν από το 1703, ήταν ο [[Γκότφριντ Βίλχελμ Λάιμπνιτς]] που όρισε την λογική με δυαδικές τιμές για το ''αληθές'' και το ''ψευδές''. Ενώ η λογική επαγωγή και μαθηματική απόδειξη υπήρχαν από την αρχαιότητα, το 1931 ο [[Κουρτ Γκέντελ]] απέδειξε με το [[Θεωρήματα μη πληρότητας του Γκέντελ|θεώρημα της μη πληρότητας]] ότι υπήρχαν θεμελιώδεις περιορισμοί σχετικά με το τι θεωρήματα θα μπορούσαν να αποδειχθούν ή να απορρηφθούν.

Αυτές οι εξελίξεις οδήγησαν στη σύγχρονη μελέτη της λογικής και της [[υπολογισιμότητας]], και μάλιστα στον τομέα της επιστήμης της  Θεωρητικής Πληροφορικής σαν ολότητα. Η [[θεωρία της Πληροφορίας]] προστέθηκε σε αυτό το πεδίο το 1948 με την μαθηματική θεωρία της επικοινωνίας του [[Κλοντ Σάνον]]. Την ίδια δεκαετία, ο [[Ντόναλντ Χεμπ]] εισήγαγε το μαθηματικό μοντέλο της [[μάθηση]]ς του εγκεφάλου. Με την ενσωμάτωση βιολογικών δεδομένων τα οποία υποστηρίζουν αυτήν την υπόθεση και με κάποιες τροποποιήσεις, το πεδίο των [[Νευρωνικά Δίκτυα|νευρωνικών δικτύων]] και [[αράλληλα και κατανεμημένα συστήματα|παράλληλης κατανεμημένες επεξεργασίας]] θεσπίστηκαν. Το 1971, ο [[Στίβεν κουκ]] και ο [[Λεονίντ Λέβιν]], που δούλευαν ανεξάρτητα, απέδειξαν ότι υπάρχουν πρακτικά σχετικά προβλήματα τα οποία είναι [[NP-completeness|NP-πλήρης]] &ndash; ένα σημείο αναφοράς το οποίο είχε σαν αποτέλεσμα την [[Θεωρία πολυπλοκότητας|θεωρία της πολυπλοκότητας]].

Με την ανάπτυξη της [[κβαντική μηχανική|κβαντικής Μηχανικής]] στις αρχές του 20ου αιώνα θεμελιώθηκε η ιδέα ότι οι μαθηματικές πράξεις μπορούν να εκτελούνται σε ολόκληρη την κυματοσυνάρτηση σωματιδίων. Με άλλα λόγια, θα μπορούσε κανείς να υπολογίσει τις λειτουργίες σε πολλαπλές καταστάσεις ταυτόχρονα. Αυτό οδήγησε στην ιδέα του [[Κβαντικός υπολογιστής|κβαντικού υπολογιστή]] στο επόμενο μισό του 20ου αιώνα, η οποία απογειώθηκε (απέκτησε θεωρητική βάση) στη δεκαετία του 1990, όταν ο [[Πίτερ Σορ]] έδειξε ότι τέτοιες μέθοδοι θα μπορούσαν να χρησιμοποιηθούν για την παραγοντοποίηση μεγάλων αριθμών σε [[πολυωνυμικό χρόνο]], η οποία, αν εφαρμοστεί, θα καθιστούσε τα πιο σύγχρονα συστήματα κρυπτογραφίας δημόσιου κλειδιού άχρηστα και ανασφαλή.{{citation needed|reason=Your explanation here|date=October 2014}}

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

{| style="border:1px solid #ddd; text-align:center;  margin: 0 auto;" cellspacing="15"
|-
| <math> P \rightarrow Q \,</math>
| [[File:DFAexample.svg|96px]]
| [[File:Elliptic curve simple.png|96px]]
| [[File:6n-graf.svg|96px]]
| [[File:Wang tiles.svg|96px]]
| '''P = NP''' ?
|-
| [[Μαθηματική λογική]]
| [[Θεωρία αυτομάτων]]
| [[Θεωρία αριθμών]]
| [[Θεωρία γράφων]]
| [[Θεωρία υπολογισιμότητας]]
| [[Θεωρία πολυπλοκότητας]]
|-
| '''GNITIRW-TERCES'''
| <math>\Gamma\vdash x : \mathrm{Int}</math>
| [[File:Commutative diagram for morphism.svg|96px]]
| [[File:SimplexRangeSearching.png|96px]]
| [[File:TSP Deutschland 3.png|96px]]
| [[File:Blochsphere.svg|96px]]
|-
| [[Κρυπτογραφία]]
| [[Θεωρία τύπων]]
| [[Θεωρία κατηγοριών]]
| [[Υπολογιστική γεωμετρία]]
| [[Συνδυαστική βελτιστοποίηση]]
| [[Quantum computer|Κβαντική θεωρία πληροφορικής]]
|}

== Ενότητες ==

===Αλγόριθμοι===
{{main|αλγόριθμος}}
Ένας [[αλγόριθμος]] είναι μια βήμα προς βήμα διαδικασία υπολογισμών.  Οι αλγόριθμοι χρησιμοποιούνται για [[υπολογισμός|υπολογισμού]], [[επεξεργασία δεδομένων]], και για [[αυτοματοποιημένη συλλογιστική]].

Ένας αλγόριθμος είναι μια [[αποτελεσματική μέθοδο]] που εκφράζεται ως μια [[Πεπερασμένο σύνολο|πεπερασμένη]] λίστα<ref>"Κάθε κλασσικός μαθηματικός αλγόριθμος, για παράδειγμα, μπορεί να περιγραφεί με μία πεπερασμένη ακολουθία αγγλικών λέξεων" (Rogers 1987:2).</ref> από καλώς-ορισμένες οδηγίες<ref>Καλώς-ορισμένες όσον αφορά τον εκτελεστή του αλγορίθμου: "Υπάρχει ένας υπολογιστικός εκτελεστής, συνήθως άνθρωπος, ο οποίος μπορεί να αντιδράσει στις οδηγίες και να τις εκτελέσει" (Rogers 1987:2).</ref> για τον υπολογισμό μιας [[συνάρτηση]]ς.<ref>"ένας αλγόριθμος είναι μία διαδικασία για τον υπολογισμό μίας ''συνάρτησης'' (για κάποια ορισμένη αναπαράσταση των ακεραίων) ... αυτός ο περιορισμός (στις αριθμητικές συναρτήσεις) δεν επηρεάζει τη γενικότητα", (Rogers 1987:1).</ref>  Ξεκινώντας από μια αρχική κατάσταση και με αρχικές εισόδους (οι οποίες μπορεί να είναι [[κενή συμβολοσειρά|κενές]]),<ref>"Ένας αλγόριθμος έχει [[μηδέν]] ή παραπάνω εισόδους, δηλαδή ποσότητες που δίνονται σε αυτόν αρχικά, πριν ξεκινήσει ο αλγόριθμος" (Knuth 1973:5).</ref> οι οδηγίες περιγράφουν έναν [[υπολογισμό]] ο οποίος, όταν εκτελείται, προχωρά μέσω ενός πεπερασμένου<ref>"Μία διαδικασία που έχει όλα τα χαρακτηριστικά ενός αλγορίθμου εκτός ότι πιθανόν υστερεί της πεπερατότητας, μπορεί να ονομαστεί 'υπολογιστική μέθοδος'" (Knuth 1973:5).</ref> αριθμού καλώς-ορισμένων διαδοχικών καταστάσεων, οι οποίες τελικά παράγουν "έξοδο"<ref>"Ένας αλγόριθμος έχει ένα ή παραπάνω εξόδους, δηλαδή ποσότητες που ορίζονται σε σχέση με τις εισόδος" (Knuth 1973:5).</ref> και τερματίζεται σε μια τελική κατάσταση. Η μετάβαση από μια κατάσταση στην επόμενη δεν είναι αναγκαστικά [[ντετερμινιστική]]; ορισμένοι αλγόριθμοι, γνωστοί ως [[πιθανοτικός αλγόριθμος|πιθανοτικοί αλγόριθμοι]], ενσωματώνουν τυχαία είσοδο.<ref>
Κατά πόσο μία διαδικασία με πιθανοτικές εσωτερικές διαδικασίες (χωρίς να συμπεριλαμβάνεται η είσοδος) συνιστά αλγόριθμο είναι συζητήσιμο. Ο Rogers λέει ότι: "ένας υπολογισμός που εκτελείται σε διακριτά βήματα, χωρίς συνεχείς μεθόδους ή αναλογικές συσκευές ... εκετελείται ντετερμινιστιικά, χωρίς την χρήση πιθανοτικών μεθόδων ή συσκευών, όπως ένα ζάρι" (Rogers 1987:2).</ref>

===Δομές δεδομένων===
{{main|Δομές δεδομένων}}
Μια [[δομή δεδομένων]] είναι ένας συγκεκριμένος τρόπος οργάνωσης [[δεδομένα|δεδομένων]] σε έναν υπολογιστή έτσι ώστε να μπορούν να χρησιμοποιηθούν [[algorithmic efficiency|αποδοτικότητα]].<ref>Paul E. Black (ed.), entry for ''data structure'' in ''[[:en:Dictionary of Algorithms and Data Structures|Dictionary of Algorithms and Data Structure]]. U.S. [[:en:National Institute of Standards and Technology|National Institute of Standards and Technology]]. 15 December 2004. [http://xlinux.nist.gov/dads/HTML/datastructur.html Online version] Accessed May 21, 2009.''</ref><ref>{{cite encyclopedia |title=data structure |encyclopedia=Encyclopædia Britannica |date= |year=2009 |last= |first= |publisher= |location= |id= |url=http://www.britannica.com/EBchecked/topic/152190/data-structure |access-date=21 May 2009 }}</ref>

Διαφορετικά είδη δομών δεδομένων είναι κατάλληλα για διαφορετικά είδη εφαρμογών, και μερικά είναι άκρως εξειδικευμένα για συγκεκριμένες εργασίες. Για παράδειγμα, οι βάσεις δεδομένων χρησιμοποιούν [[Β-δένδρα|B-δενδροειδή]] ευρετήρια για μικρά ποσοστά ανάκτησης δεδομένων και οι [[Μεταγλωττιστής (υπολογιστές)|μεταγλωττιστές]] και οι βάσεις δεδομένων χρησιμοποιούν δυναμικούς [[Πίνακας κατακερματισμού|πίνακες κατακερματισμού]] σαν πίνακες αναφοράς.

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

===Θεωρία πολυπλοκότητας===
{{main|Θεωρία πολυπλοκότητας}}
[[Θεωρία πολυπλοκότητας]] είναι κλάδος της [[θεωρία υπολογισμού|θεωρίας υπολογισμού]] που εστιάζει στην ταξινόμηση [[υπολογιστικό πρόβλημα|υπολογιστικών προβλημάτων]] ανάλογα με εγγενή δυσκολία τους, και συσχετίζει αυτές τις [[κλάση πολυπλοκότητας|κλάσεις]] μεταξύ τους. Σαν υπολογιστικό πρόβλημα νοείται μια εργασία η οποία κατ 'αρχήν είναι δυνατόν να λυθεί από έναν υπολογιστή, η οποία είναι ισοδύναμη με τη δήλωση ότι το πρόβλημα μπορεί να λυθεί με τη μηχανική εφαρμογή μαθηματικών βημάτων, όπως ένας [[αλγόριθμος]].

Ένα πρόβλημα θεωρείται ότι είναι δύσκολο, αν η λύση του απαιτεί σημαντικούς (υπολογιστικούς) πόρους, ανεξάρτητα από τον [[αλγόριθμος|αλγόριθμο]] που χρησιμοποιείται. Η θεωρία τυποποιεί αυτή τηn διαίσθηση, με την εισαγωγή μαθηματικών υπολογιστικών μοντέλων για την μελέτη τέτοιων προβλημάτων και υπολογίζει το σύνολο των πόρων που απαιτούνται για την επίλυσή τους, όπως ο χρόνος επεξεργασίας και ο όγκος των δεδομένων που αποθηκεύονται. Άλλα μέσα για την μέτρηση της [[υπολογιστική πολυπλοκότητα|πολυπλοκότητας]] επίσης χρησιμοποιούνται, όπως το ύψος της επικοινωνίας (το οποίο χρησιμοποιείται στην [[πολυπλοκότητα της επικοινωνίας]]), ο αριθμός των [[Λογική πύλη|λογικών πυλών]] σε ένα (ολοκληρωμένο) κύκλωμα (που χρησιμοποιείται στην [[πολυπλοκότητα κυκλώματος]]) και ο αριθμός των επεξεργαστών (που χρησιμοποιείται στην [[παράλληλη υπολογιστική]]). Ένας από τους ρόλους της θεωρία της πολυπλοκότητας είναι να καθορίσει τα πρακτικά όρια σχετικά με το τι οι [[υπολογιστής|υπολογιστές]] μπορούν και δεν μπορούν να κάνουν.
===Κατανεμημένος υπολογισμός===
{{Κύριο|Παράλληλα και κατανεμημένα συστήματα}}
Ο [[Παράλληλα και κατανεμημένα συστήματα|κατανεμημένος υπολογισμός]] μελετά κατανεμημένα συστήματα. Ένα κατανεμημένο σύστημα είναι ένα σύστημα λογισμικού στο οποίο τα συστατικά βρίσκονται σε [[computer network|δικτυωμένους υπολογιστές]] επικοινωνούν και συντονίσουν τις δράσεις τους [[message passing|περνώντας μηνύματα]].<ref name="Coulouris">{{cite book|author1=George Coulouris |author2=Jean Dollimore |author3=Tim Kindberg |author4=Gordon Blair |title=Κατανεμημένα Συστήματα: Έννοιες και Σχεδιασμός |edition=5η |publisher = Addison-Wesley |year=2011 |location=Boston |isbn=0-132-14301-1}}</ref> Τα συστατικά αλληλεπιδρούν μεταξύ τους, προκειμένου να επιτευχθεί ένας κοινός στόχος. Τρία σημαντικά χαρακτηριστικά των κατανεμημένων συστημάτων είναι: συγχρονισμός των στοιχείων, η έλλειψη ενός παγκόσμιου ρολογιού, και ανεξάρτητη αποτυχία των συνιστωσών.<ref name="Coulouris"/> Παραδείγματα κατανεμημένων συστημάτων ποικίλλουν από [[Service-oriented architecture|SOA-συστήματα]] που βασίζονται σε [[μαζικά multiplayer online παιχνίδια]] σε [[eer-to-peer]] εφαρμογές.

Ένα [[πρόγραμμα υπολογιστή]] που τρέχει σε ένα κατανεμημένο σύστημα ονομάζεται  '''κατανεμημένο πρόγραμμα''', και κατανεμημένος προγραμματισμός είναι η διαδικασία της γραφής αυτών των προγραμμάτων.<ref>{{harvtxt|Andrews|2000}}. {{harvtxt|Dolev|2000}}. {{harvtxt|Ghosh|2007}}, p. 10.</ref> Υπάρχουν πολλές εναλλακτικές λύσεις για το μήνυμα που περνά μηχανισμό, συμπεριλαμβανομένου του [[Remote procedure call|RPC-όπως]] συνδέσεις και [[Message-oriented middleware|ουρές μηνυμάτων]].  Ένας σημαντικός στόχος και πρόκληση των κατανεμημένων συστημάτων είναι [[η τοποθεσία διαφάνειας]].

===Παράλληλος Υπολογισμός===
{{Κύριο|Παράλληλα και κατανεμημένα συστήματα}}
Ο [[Παράλληλα και κατανεμημένα συστήματα|παράλληλος υπολογισμός]] είναι μια μορφή [[υπολογισμός|υπολογισμού]] στην οποία πολλοί υπολογισμοί πραγματοποιούνται ταυτόχρονα,<ref>{{cite book|author1=Allan Gottlieb |title=Υψηλός Παράλληλος Υπολογισμός |year=1989 |publisher=Benjamin/Cummings |location=Redwood City, California |isbn=0-8053-0177-1|url=http://dl.acm.org/citation.cfm?id=160438|author2=George S. Almasi}}</ref> που λειτουργούν με βάση την αρχή ότι τα μεγάλα προβλήματα μπορούν συχνά να διαιρεθούν σε μικρότερα, τα οποία μετά θα λυθούν [[Ταυτοχρονισμός|ταυτόχρονα]] ("παράλληλα"). Υπάρχουν πολλές διαφορετικές μορφές του παράλληλου υπολογισμού: στο [[Bit-level parallelism|επίπεδο των bit]], στο [[Instruction-level parallelism|επίπεδο των εντολών]], [[data parallelism|των δεδομένων]], και [[των διεργασιών]]. Ο παραλληλισμός έχει χρησιμοποιηθεί για πολλά χρόνια, κυρίως σε υψηλών επιδόσεων υπολογιστές, αλλά ενδιαφέρον έχει αυξηθεί τον τελευταίο καιρό λόγω των φυσικών περιορισμών πρόληψης στην [[κλιμάκωση συχνότητας]].<ref>S.V. Adve κ.α. (Νοέμβριος 2008). [http://www.upcrc.illinois.edu/documents/UPCRC_Whitepaper.pdf "Parallel Computing Research at Illinois: The UPCRC Agenda"] {{Webarchive|url=https://web.archive.org/web/20081209154000/http://www.upcrc.illinois.edu/documents/UPCRC_Whitepaper.pdf |date=2008-12-09 }} (PDF). Parallel@Illinois, Πανεπιστήμιο της Illinois στην πεδιάδα της Urbana. "Οι κύριες τεχνικές για αυτά τα πλεονεκτήματα απόδοσης&nbsp;– αυξημένη συχνότητα ρολογιού και πιο έξυπνη, αλλά όλο και πιο πολύπλοκες αρχιτεκτονικές&nbsp;– χτυπούν τώτα το λεγόμενο τείχος εξουσίας. Η βιομηχανία των υπολογιστών έχει δεχθεί ότι η μελλοντική αύξηση της απόδοσης πρέπει να προέρχεται σε μεγάλο βαθμό από την αύξηση του αριθμού των επεξεργαστών (ή πυρήνες) σε έναν κύβο, αντί να κάνει ένα ενιαίο πυρήνα πάει πιο γρήγορα."</ref> Καθώς η κατανάλωση ενέργειας (και συνεπώς η παραγωγή θερμότητας) από τους υπολογιστές έχει γίνει μια ανησυχία κατά τα τελευταία χρόνια,<ref>Asanovic κ.α . Η παλιά [συμβατική σοφία]: Η δύναμη είναι δωρεάν, αλλά τα τρανζίστορ είναι ακριβά. Η νέα [συμβατική σοφία] είναι [οτι] η δύναμη είναι ακριβή,αλλά τα τρανζίστορ είναι "δωρεάν".</ref> Ο παράλληλος υπολογισμός έχει γίνει κυρίαρχο πρότυπο στην [[αρχιτεκρονική των υπολογιστών]], κυρίως με τη μορφή του [[multi-core επεξεργαστή]]s.<ref name="View-Power">Asanovic, Krste κ.α. (Δεκέμβριος 18, 2006). [http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.pdf "The Landscape of Parallel Computing Research: A View from Berkeley"] (PDF). Πανεπιστήμιο της California, Berkeley. Τεχνικη Εκθεση No. UCB/EECS-2006-183. "Παλιά [συμβατική σοφία]: Η αύξηση της συχνότητας του ρολογιού είναι η κύρια μέθοδος για τη βελτίωση της απόδοσης του επεξεργαστή. Νέα [συμβατική σοφία]: Η αύξηση του παραλληλισμού είναι η κύρια μέθοδος για τη βελτίωση της απόδοσης του επεξεργαστή&nbsp;... Ακόμη και εκπρόσωποι από την Intel, μια εταιρεία που σχετίζεται γενικά με την «υψηλότερη ταχύτητα ρολογιου είναι καλύτερη» άποψη, προειδοποίησε ότι οι παραδοσιακές προσεγγίσεις για τη μεγιστοποίηση της απόδοσης μέσω της μεγιστοποίησης της ταχύτητας ρολογιού του έχει ωθήσει στα όριά τους."</ref>

Τα προγράμματα παράλληλου υπολογισμού είναι πιο δύσκολο να γραφούν από ό,τι τα αντίστοιχα σειριακά προγράμματα,<ref>{{cite book|author1=John L. Hennessy |title=Computer organization and design : the hardware/software interface |url=https://archive.org/details/computerorganiz000henn |year=1999 |publisher=Kaufmann |location=San Francisco |isbn=1-55860-428-6 |edition=2η |author2=David A. Patterson |author3=James R. Larus }}</ref> επειδή ο συγχρονισμός εισάγει αρκετές νέες κατηγορίες των πιθανών [[Software bug|σφαλμάτων του λογισμικού]], εκ των οποίων η [[συνθήκη ανταγωνισμού]] είναι πιο κοινή. Η [[Δίκτυο υπολογιστών|επικοινωνία]] και ο [[Ταυτοχρονισμός|συγχρονισμός]] μεταξύ των διαφόρων δευτερεύουσων εργασιών είναι συνήθως μερικά από τα μεγαλύτερα εμπόδια για να έχει καλή απόδοση ένα παράλληλο πρόγραμμα.

Η μέγιστη δυνατή [[speedup|επιτάχυνση]] ενός ενιαίου προγράμματος ως αποτέλεσμα παραλληλοποίησης είναι γνωστή ως [[νόμος του Amdahl]].

===Πολύ-μεγάλης κλίμακας ολοκλήρωση===
{{main|VLSI}}
Η πολύ μεγάλης κλίμακας ολοκλήρωση ('''[[VLSI]]''') είναι η διαδικασία της δημιουργίας ενός [[ολοκληρωμένου κυκλώματος]] (IC) συνδυάζοντας χιλιάδες [[τρανζίστορ]] σε ένα ενιαίο τσιπ. VLSI ξεκίνησε τη δεκαετία του 1970, όταν πολύπλοκoi [[ημιαγωγοί]] και τεχνολογίες [[επικοινωνίας]] αναπτύχθηκαν. Ο [[μικροεπεξεργαστής]] είναι μια VLSI συσκευή. Πριν από την εισαγωγή της τεχνολογίας VLSI πιο ICs είχε ένα περιορισμένο σύνολο λειτουργιών που θα μπορούσε να εκτελέσει. Ένα [[ηλεκτρονικό κύκλωμα]] μπορεί να αποτελείται από ένα [[κεντρική μονάδα επεξεργασίας|CPU]], [[Μνήμη μόνο για ανάγνωση|ROM]], [[Μνήμη Τυχαίας Προσπέλασης|RAM]] και άλλα [[glue logic]]. Το VLSI επιτρέπει σε IC κατασκευαστές να προσθέτονται όλα αυτά σε ένα τσιπ.

===Μηχανική μάθηση===
{{Κύριο|Μηχανική μάθηση}}
Η [[μηχανική μάθηση]] είναι ένας [[Κλάδοι της επιστήμης|επιστημονικός κλάδος]] που ασχολείται με την δημιουργία και την ανάλυση [[αλγόριθμος|αλγορίθμων]] οι οποίοι μπορούν να μάθουν απο τα δεδομένα.<ref>{{cite journal |title=Glossary of terms |author1=Ron Kovahi |author2=Foster Provost |journal=Machine Learning |volume=30 |pages=271–274 |year=1998 |url=http://ai.stanford.edu/~ronnyk/glossary.html}}</ref> Τέτοιοι αλγόριθμοι λειτουργούν με την δημιουργία ενός [[στατιστικό μοντέλο|μοντέλου]] βασισμένου στα δεδομένα εισόδου <ref name="bishop">{{cite book |author=C. M. Bishop |year=2006 |title=Pattern Recognition and Machine Learning |url=https://archive.org/details/patternrecogniti0000bish |publisher=Springer |isbn=0-387-31073-8}}</ref>{{rp|2}} και χρησιμοποιούν αυτά για να κάνουν προβλέψεις ή αποφάσεις, αντί να ακολουθούν ρητά μία ακολουθία από προγραμματισμένες οδηγίες.

Η μηχανική μάθηση μπορεί να θεωρηθεί ως υποπεδίο της επιστήμης των υπολογιστών και της [[στατιστική|στατιστικής]]. Έχει ισχυρούς δεσμούς με την [[τεχνητή νοημοσύνη]] και την [[βελτιστοποίηση]], οι οποίες παρέχουν τις μεθόδους, τη θεωρία και τομείς εφαρμογής στον κλάδο. Η μηχανή μάθησης χρησιμοποιείται σε μια σειρά υπολογιστικών εργασιών όπου σχεδιάσμένοι και προγραμματισμένοι σαφής, με βάση κανόνες [[αλγόριθμοι]] δεν είναι αρκετά αποδοτικοί ή ακόμα και ανέφικτοι. Παραδείγματα εφαρμογών περιλαμβάνουν [[φίλτρο spam]], [[Οπτική Αναγνώριση Χαρακτήρων|οπτική αναγνώριση χαρακτήρων]] (OCR),<ref name="Wernick-Signal-Proc-July-2010">Wernick, Yang, Brankov, Yourganov and Strother, Machine Learning in Medical Imaging, ''[[IEEE Signal Processing Society|IEEE Signal Processing Magazine]]'', vol. 27, no. 4, Ιούλιος 2010, pp. 25-38</ref> [[Learning to rank|μηχανές αναζήτησης]] και [[υπολογιστική όραση]]. Η μηχανή μάθησης μερικές φορές συγχέεται με [[εξόρυξη δεδομένων]],<ref>{{cite conference| last=Mannila |first=Heikki |title=Data mining: machine learning, statistics, and databases |conference=Int'l Conf. Scientific and Statistical Database Management |publisher=IEEE Computer Society |year=1996}}</ref> 
παρόλο που εστιάζει περισσότερο στην διερευνητική ανάλυση δεδομένων.<ref>{{cite journal |author=Jerome H. Friedman |title=Data Mining and Statistics: What's the connection? |journal=Computing Science and Statistics |volume=29 |issue=1 |year=1998 |pages=3–9}}</ref> Η μηχανή μάθησης και [[ανάγνωσης σχεδίου]] "μπορεί να θεωρηθεί ως διπλή όψη του ίδιου πεδίου." <ref name="bishop"/>{{rp|vii}}

===Υπολογιστική Βιολογία===
Η [[υπολογιστική βιολογία]] περιλαμβάνει την ανάπτυξη και την εφαρμογή των αναλυτικών στοιχείων και θεωρητικών μεθόδων, μαθηματικών μοντέλων και υπολογιστικών τεχνικών προσομοίωσης για τη μελέτη των βιολογικών, συμπεριφορικών και κοινωνικών συστημάτων.<ref name="nih">{{cite web
 |url         = http://www.bisti.nih.gov/docs/compubiodef.pdf
 |title       = NIH working definition of bioinformatics and computational biology
 |date        = 2000-07-17
 |accessdate  = 2012-08-18
 |publisher   = Biomedical Information Science and Technology Initiative
 |archiveurl  = https://web.archive.org/web/20120905155331/http://www.bisti.nih.gov/docs/CompuBioDef.pdf
 |archivedate = 2012-09-05
 |url-status  = dead
}}</ref> Το πεδίο είναι γενικώς ορισμένο και περιλαμβάνει θεμελιώδεις έννοιες της [[πληροφορική|πληροφορικής]], των [[Εφαρμοσμένα μαθηματικά|εφαρμοσμένων μαθηματικών]], του [[animation]], της [[στατιστική|στατιστικής]], της [[βιοχημεία|βιοχημείας]], της [[χημεία|χημείας]], της [[βιοφυσική|βιοφυσικής]], της [[Μοριακή βιολογία|μοριακής βιολογίας]], της [[γενετική|γενετικής]], της [[Γονιδιωματική|γονιδιωματικής]], της [[οικολογία|οικολογίας]], της [[εξέλιξη|εξέλιξης]], της [[ανατομία|ανατομίας]], της [[νευροεπιστήμη|νευροεπιστήμης]], και της [[επιστημονικής οπτικοποίησης|οπτικοποίησης]].<ref name="brown">
{{cite web
| url          = http://www.brown.edu/research/projects/computational-molecular-biology/
| title        = About the CCMB
| accessdate   = 2012-08-18
| publisher    = Center for Computational Molecular Biology
}}
</ref>

Υπολογιστική Βιολογία είναι διαφορετική από τον [[βιολογικό υπολογισμό]], ο οποίος είναι ένα υποπεδίο της επιστήμης των υπολογιστών και της [[μηχανικής υπολογιστών]] χρησιμοποιώντας [[βιομηχανολογία]] και [[βιολογία]] για την κατασκευή [[υπολογιστών]] , αλλά είναι παρόμοια με την [[βιοπληροφορική]], η οποία είναι μια διεπιστημονική επιστήμη που χρησιμοποιούν υπολογιστές για την αποθήκευση και την επεξεργασία βιολογικών δεδομένων.

===Υπολογιστική γεωμετρία===
{{Κύριο|Υπολογιστική γεωμετρία}}

Η [[υπολογιστική γεωμετρία]] είναι ένας κλάδος της επιστήμης των υπολογιστών που αφιερώνεται στη μελέτη των αλγορίθμων που μπορεί να δηλωθεί από την άποψη της [[Γεωμετρία|γεωμετρίας]]. Μερικά καθαρά γεωμετρικά προβλήματα προκύπτουν από τη μελέτη των υπολογιστικών αλγορίθμων γεωμετρικής, και τα προβλήματα αυτά θεωρούνται επίσης να είναι μέρος της υπολογιστικής γεωμετρίας. Ενώ η σύγχρονη υπολογιστική γεωμετρία είναι μια πρόσφατη εξέλιξη, είναι ένας από τους παλαιότερους τομείς της πληροφορικής με ιστορία που εκτείνεται πίσω στην αρχαιότητα. Ένα αρχαίο πρόδρομο είναι η [[σανσκριτική]] πραγματεία [[Shulba Σούτρες]], ή «οι κανόνες της χορδής», ότι είναι ένα βιβλίο των αλγορίθμων γραμμένο στα 800 π.Χ.. Το βιβλίο ορίζει βήμα-βήμα τις διαδικασίες για την κατασκευή γεωμετρικών αντικειμένων όπως βωμούς χρησιμοποιώντας ένα πάσσαλο και χορδή.

Η κύρια ώθηση για την ανάπτυξη της υπολογιστικής γεωμετρίας ως επιστήμη ήταν η πρόοδος στα [[γραφικά υπολογιστών]] με τη βοήθεια υπολογιστών σχεδιασμού και την κατασκευή ([[CAD]] / [[αυτοματοποιημένη παραγωγή|CAM]]), αλλά και πολλά προβλήματα στην υπολογιστική γεωμετρία είναι κλασικά στη φύση, και μπορεί να προέρχονται από [[μαθηματική απεικόνιση]].
Άλλες σημαντικές εφαρμογές της υπολογιστικής γεωμετρίας περιλαμβάνουν [[ρομποτική]] (προγραμματισμό κινήσεων και προβλήματα ορατότητας), [[σύστημα γεωγραφικών πληροφοριών]] (GIS) (την γεωμετρική θέση και την αναζήτηση, τον σχεδιασμό της διαδρομής), [[ολοκληρωμένο κύκλωμα]] και τον σχεδιασμό (IC γεωμετρία σχεδιασμού και ελέγχου), με τη βοήθεια υπολογιστών μηχανικής (CAE) (πλέγμα γενιά), [[υπολογιστής όρασης]] (3D ανακατασκευή).

===Θεωρία της Πληροφορίας===
{{main|Θεωρία της πληροφορίας}}
Η θεωρία της πληροφορίας είναι ένας κλάδος των εφαρμοσμένων μαθηματικών , των ηλεκτρολόγων μηχανικών και της επιστήμης των υπολογιστών που αφορούν την ποσοτικοποίηση των πληροφοριών . Η θεωρία της πληροφορίας αναπτύχθηκε από τον Claude E. Shannon που βρήκε τα θεμελιώδη όρια σχετικά με την λειτουργία  επεξεργασίας σήματος, όπως συμπίεση των δεδομένων,την αξιοπιστία της αποθήκευσης και την επικοινωνία δεδομένων . Από την ίδρυσή της έχει διευρυνθεί  να βρει εφαρμογές σε πολλούς άλλους τομείς  συμπεριλαμβανομένων στατιστική συμπερασματολογία , επεξεργασία φυσικής γλώσσας , κρυπτογραφία , νευροβιολογία<ref>{{cite book|author1=F. Rieke |author2=D. Warland |author3=R Ruyter van Steveninck |author4=W Bialek |title=Spikes: Exploring the Neural Code |publisher=The MIT press |year=1997 |isbn=978-0262681087}}</ref> ,  εξέλιξη<ref>cf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, ''Science'' '''294''':2310-2314</ref> και τη λειτουργία<ref>Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, [http://alum.mit.edu/www/toms/ Thomas D. Schneider] {{Webarchive|url=https://web.archive.org/web/20080821124201/http://alum.mit.edu/www/toms |date=2008-08-21 }}, Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, ''Gene'' '''215''':1, 111-122</ref>  των μοριακών κωδικών , την επιλογή μοντέλου στην οικολογία ,<ref>Burnham, K. P. and Anderson D. R. (2002) ''Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Second Edition'' (Springer Science, New York) ISBN 978-0-387-95364-9.</ref> Θερμοδυναμικής,<ref>Jaynes, E. T. (1957) [http://bayes.wustl.edu/ Information Theory and Statistical Mechanics], ''Phys. Rev.'' '''106''':620</ref>  κβαντικών υπολογιστών , γλωσσολογία , εντοπισμού λογοκλοπής,<ref>Charles H. Bennett, Ming Li, and Bin Ma (2003) [http://sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=08B64096-0772-4904-9D48227D5C9FAC75 Chain Letters and Evolutionary Histories] {{Webarchive|url=https://web.archive.org/web/20071007041539/http://www.sciamdigital.com/index.cfm?fa=Products.ViewIssuePreview&ARTICLEID_CHAR=08B64096-0772-4904-9D48227D5C9FAC75 |date=2007-10-07 }}, ''Scientific American'' '''288''':6, 76-81</ref>  την αναγνώριση προτύπων , την ανίχνευση ανωμαλιών και άλλων μορφών ανάλυσης δεδομένων.<ref>{{Cite web|url=http://aicanderson2.home.comcast.net/~aicanderson2/home.pdf|title=Some background on why people in the empirical sciences may want to better understand the information-theoretic methods|date=2003-11-01|format=pdf|accessdate=2010-06-23|author=David R. Anderson|archive-date=2012-03-08|archive-url=https://web.archive.org/web/20120308114246/http://aicanderson2.home.comcast.net/~aicanderson2/home.pdf|url-status=}}</ref>

Οι εφαρμογές των θεμελιωδών θεμάτων της θεωρίας πληροφοριών περιλαμβάνουν την συμπίεση δεδομένων χωρίς απώλειες (π.χ. αρχεία ZIP),την  συμπίεση δεδομένων με απώλειες (π.χ. [[MP3]]s και αρχεία [[JPEG]]s), και την κωδικοποίηση καναλιού (π.χ. για την ψηφιακή συνδρομητική γραμμή (DSL)). Το πεδίο είναι η διασταύρωση των μαθηματικών, της στατιστικής, της επιστήμης των υπολογιστών, της φυσικής, της νευροβιολογίας και των μηχανολόγων μηχανικών. Ο αντίκτυπός της ήταν ζωτικής σημασίας για την επιτυχία των αποστολών Voyager στο μακριπρόθεσμο διάστημα, της εφεύρεσης του Compact Disc, της σκοπιμότητας των κινητών τηλεφώνων, της ανάπτυξης του Διαδικτύου, της μελέτης της γλωσσολογίας και της ανθρώπινης αντίληψης, της κατανόησης των μαύρων τρυπών και πολλά άλλα πεδία. Σημαντικοί υπο-τομείς της θεωρίας της πληροφορίας είναι η κωδικοποίηση της πηγής, η κωδικοποίηση του καναλιού, η αλγοριθμική θεωρία της πολυπλοκότητας, η αλγοριθμική θεωρία της πληροφορίας, οι πληροφορίες θεωρίας της ασφάλειας, καθώς και τα μέτρα των πληροφοριών.

===Κρυπτογραφία===
{{main|Κρυπτογραφία}}
Κρυπτογραφία είναι η πρακτική και η μελέτη των τεχνικών για την ασφαλή επικοινωνία με την παρουσία τρίτων (που ονομάζονται αντίπαλοι).<ref name="rivest90">{{cite book|author=Ronald L. Rivest|editor=J. Van Leeuwen|title=Handbook of Theoretical Computer Science|chapter=Cryptology|volume=1|publisher=Elsevier|year=1990}}</ref> Γενικότερα, πρόκειται για την κατασκευή και την ανάλυση των πρωτοκόλλων που ξεπερνούν την επιρροή των αντιπάλων<ref name="modern-crypto">{{Cite book|author1=Mihir Bellare |author2=Phillip Rogaway |title=Introduction to Modern Cryptography |chapter=Introduction|page=10|date= 2005-09-21}}</ref>  και τα οποία σχετίζονται με διάφορες πτυχές της ασφάλειας των πληροφοριών, όπως το απόρρητο των δεδομένων, την ακεραιότητα των δεδομένων, την πιστοποίηση και τη μη αποκήρυξη.<ref name="hac">{{cite book |author1=A. J. Menezes |author2=P. C. van Oorschot |author3=S. A. Vanstone |url=http://www.cacr.math.uwaterloo.ca/hac/ |title=Handbook of Applied Cryptography |publisher= |isbn=0-8493-8523-7 |access-date=2015-05-24 |archive-date=2005-03-07 |archive-url=https://web.archive.org/web/20050307081354/http://www.cacr.math.uwaterloo.ca/hac/ |url-status=unfit }}</ref>  Η σύγχρονη κρυπτογραφία τέμνει τις επιστήμες των μαθηματικών, της επιστήμης των υπολογιστών και των ηλεκτρολόγων μηχανικών.Οι εφαρμογές της κρυπτογραφίας περιλαμβάνουν κάρτες ΑΤΜ,  κωδικούς πρόσβασης του υπολογιστή και το ηλεκτρονικό εμπόριο.

Η σύγχρονη κρυπτογραφία βασίζεται σε μεγάλο βαθμό στην μαθηματική θεωρία και την πρακτικη επιστήμη των υπολογιστών . Οι κρυπτογραφικοί αλγόριθμοι σχεδιάστηκαν γύρω από την υπολογιστικές σκληρές παραδοχές, κατασκευάζοντας  τέτοιους αλγορίθμους που  είναι δύσκολο να σπάσουν στην πράξη από οποιονδήποτε αντίπαλο. Είναι θεωρητικά δυνατό να σπάσει ένα τέτοιο σύστημα, αλλά αυτό είναι ανέφικτο να το συμβεί  από οποιοδήποτε γνωστό πρακτικό μέσο. Ως εκ τούτου, τα συστήματα αυτά ονομάζονται υπολογιστικά ασφαλής.Οι θεωρητικές εξελίξεις π.χ. οι βελτιώσεις στη παραγοντοποίηση των ακεραίων αλγορίθμων  και η ταχύτερη τεχνολογία των υπολογιστών απαιτούν αυτές τις  λύσεις και πρέπει να προσαρμόζονται συνεχώς. Υπάρχουν συστήματα πληροφοριών θεωρητικά ασφαλείς που Πρότυπου: Δεν είναι τυπογραφικό λάθος δεν μπορεί να σπάσει ακόμη και με απεριόριστη υπολογιστική δύναμη—ένα παράδειγμα είναι το one-time pad—αλλά τα συστήματα αυτά είναι πιο δύσκολο να εφαρμοστούν από τις καλύτερα θεωρητικά εύθραυστα αλλά υπολογιστικά ασφαλείς μηχανισμούς.

===Κβαντικός υπολογισμός===
{{main|Κβαντικός υπολογισμός}}
Ένας [[κβαντικός υπολογιστής]] είναι ένα σύστημα [[Υπολογισμός|υπολογισμού]] το οποίο κάνει άμεση χρήση [[Κβαντική κατάσταση|κβαντικών]] φαινομένων, όπως η [[υπέρθεση]] και η [[εμπλοκή]], ώστε να επεξεργαστεί [[δεδομένα]].<ref>"[http://cba.mit.edu/docs/papers/98.06.sciqc.pdf Quantum Computing with Molecules]" article in ''[[Scientific American]]'' by [[Neil Gershenfeld]] and [[Isaac L. Chuang]]</ref> Οι κβαντικοί υπολογιστές διαφέρουν από τους ψηφιακούς υπολογιστές που βασίζονται σε [[τρανζίστορ]]. Ενώ οι ψηφιακοί υπολογιστές απαιτούν τα δεδομένα να είναι κωδικοποιημένα σε δυαδική μορφή ψηφίων ([[bit]]s), καθένα από τα οποία παίρνουν πάντα μία από τις δύο καθορισμένες καταστάσεις (0 ή 1), οι κβαντικοί υπολογιστές χρησιμοποιούν [[Κβαντικός αριθμός|qubits]] (κβαντικά bits), τα οποία μπορούν να παίρνουν πολλές καταστάσεις. Ένα θεωρητικό μοντέλο κβαντικής μηχανής είναι η [[μηχανή Τούρινγκ]], γνωστή και ως η καθολική κβαντική μηχανή.  Οι κβαντικοί υπολογιστές μοιράζονται θεωρητικές ομοιότητες με τους [[μη-προσδιοριστούς]] και [[πιθανοτικούς]] υπολογιστές· ένα παράδειγμα είναι η δυνατότητα να βρίσκεται ταυτόχρονα σε περισσότερες από μία κατάσταση. Ο κλάδος των κβαντικών υπολογιστών εισήχθη για πρώτη φορά από τον από τον [[Yuri Manin]] το 1980<ref name="manin1980vychislimoe">{{cite book| author=Manin, Yu. I.| title=Vychislimoe i nevychislimoe| trans-title=Computable and Noncomputable| year=1980| publisher=Sov.Radio| url=http://publ.lib.ru/ARCHIVES/M/MANIN_Yuriy_Ivanovich/Manin_Yu.I._Vychislimoe_i_nevychislimoe.(1980).%5Bdjv%5D.zip| pages=13–15| language=ρωσικά | accessdate= 2013-03-04| first=| location=| page=| archiveurl=https://web.archive.org/web/20130510173823/http://publ.lib.ru/ARCHIVES/M/MANIN_Yuriy_Ivanovich/Manin_Yu.I._Vychislimoe_i_nevychislimoe.(1980).%5Bdjv%5D.zip| archivedate=2013-05-10| url-status=dead}}</ref> και τον [[Richard Feynman]] το 1982.<ref name="Feynman82">{{cite journal |author=R.P. Feynman |title=Simulating physics with computers |journal=[[International Journal of Theoretical Physics]] |year=1982 |volume=21 |issue=6 |pages=467–488 |doi=10.1007/BF02650179 }}</ref><ref>{{cite journal |title=Quantum computation |author=David Deutsch |journal=Physics World |date=1992-01-06 }}</ref> Ένας κβαντικός υπολογιστής με περιστροφές ως κβαντικά bits, επίσης σχεδιάστηκε για χρήση ως ένα κβαντικό [[Χωροχρόνος|χωροχρόνο]] το 1968.<ref>{{cite book |author=David Finkelstein |chapter=Space-Time Structure in High Energy Interactions |title=Fundamental Interactions at High Energy |editor1=T. Gudehus |editor2=G. Kaiser |location=New York |publisher=Gordon & Breach |year=1968 }}</ref>

Το 2014, η κβαντική πληροφορική βρίσκεται ακόμα στο ξεκίνημα αλλά έχουν διεξαχθεί πειράματα στα οποία εκτελέστηκαν κβαντικοί υπολογισμοί σε έναν πολύ μικρό αριθμό qubits.<ref>{{cite web|url=http://phys.org/news/2013-01-qubit-bodes-future-quantum.html|title=New qubit control bodes well for future of quantum computing|publisher=|accessdate= 2014-10-26}}</ref> Η πρακτική και η θεωρητική έρευνα συνεχίζεται, και πολλές εθνικές κυβερνήσεις και στρατιωτικές υπηρεσίες τις χρηματοδωτούν, στηρίζοντας έτσι την κβαντική υπολογιστική έρευνα για την ανάπτυξη κβαντικών υπολογιστών, τόσο για πολιτικούς όσο και για λόγους εθνικής ασφαλείας, όπως κρυπτανάλυσης.<ref>[http://qist.lanl.gov/qcomp_map.shtml Quantum Information Science and Technology Roadmap] {{Webarchive|url=https://web.archive.org/web/20110810190657/http://qist.lanl.gov/qcomp_map.shtml |date=2011-08-10 }} for a sense of where the research is heading.</ref>

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

===Συμβολικός υπολογισμός===
Η άλγεβρα υπολογιστών, αποκαλούμενη επίσης ως  συμβολικός υπολογισμός ή αλγεβρικός υπολογισμός είναι μια επιστημονική περιοχή η οποία αναφέρεται στη μελέτη και την ανάπτυξη των αλγορίθμων και του λογισμικού για το χειρισμό των μαθηματικών εκφράσεων και άλλων μαθηματικών αντικειμένων. Αν και, μιλώντας κατάλληλα, η άλγεβρα υπολογιστών πρέπει να είναι υποπεδίο  του επιστημονικού υπολογισμού ,θεωρούνται γενικά ως ευδιάκριτοι τομείς  επειδή  ο επιστημονικός υπολογισμός είναι συνήθως βασισμένος στον αριθμητικό υπολογισμό με τους κατά προσέγγιση αριθμούς κινητής υποδιαστολής, ενώ ο συμβολικός  υπολογισμός υπογραμμίζει  τον ακριβή υπολογισμό με τις εκφράσεις περιέχοντας τις μεταβλητές που δεν έχουν οποιαδήποτε δεδομένη αξία και χειρίζονται έτσι ως σύμβολα (επομένως  το όνομα  του  συμβολικού  υπολογισμού).

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

=== Σημασιολογία προγράμματος ===
Στη θεωρία γλώσσας προγραμματισμού, η σημασιολογία είναι ο τομέας ενδιαφερόμενος για την αυστηρή μαθηματική μελέτη της έννοιας των γλωσσών προγραμματισμού .Κάνει έτσι  με την  αξιολόγηση της έννοιας των συντακτικά νομικών σειρών που καθορίζεται από μια συγκεκριμένη γλώσσα προγραμματισμού, παρουσιάζοντας τον υπολογισμό σχετικό. Σε αυτή την περίπτωση ότι η αξιολόγηση θα ήταν συντακτικά παράνομων σειρών, το αποτέλεσμα θα ήταν μη-υπολογίσιμο.Η σημασιολογία περιγράφει τις διαδικασίες που ένας υπολογιστής ακολουθεί κατά εκτέλεση ενός προγράμματος σε εκείνη την συγκεκριμένη γλώσσα.Αυτό μπορεί να παρουσιαστεί με την  περιγραφή της σχέσης μεταξύ της εισαγωγής και της παραγωγής ενός προγράμματος  ή μια εξήγηση για το πώς το πρόγραμμα θα εκτελέσει σε μια ορισμένη πλατφόρμα, ως εκ τού του δημιουργώντας  ένα πρότυπο του υπολογισμού.

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

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

=== Θεωρία αυτομάτων ===
{{main|Θεωρία αυτομάτων}}

Η θεωρία αυτομάτων είναι η μελέτη της <nowiki>''αφηρημένης μηχανικής'' και των ''αυτoμάτων'', καθώς και τα υπολογιστικά προβλήματα που μπορούν να επιλυθούν με τη χρήση αυτών. Είναι μια θεωρία στη θεωρητική επιστήμη των υπολογιστών, με Διακριτά Μαθηματικά (ένα τμήμα των Μαθηματικών καθώς επίσης και της Επιστήμης Υπολογιστών). Η λέξη ''αυτόματα''</nowiki> προέρχεται από την ελληνική λέξη αὐτόματα, που σημαίνει "αυτενεργό".

Η θεωρία αυτομάτων είναι η μελέτη της αυτο-λειτουργίας των εικονικών μηχανών για να βοηθήσουν στην κατανόηση της λογικής διεργασίας εισόδου και εξόδου, με ή χωρίς ενδιάμεσο στάδιο(α) του υπολογισμού (ή οποιαδήποτε λειτουργία / διαδικασία).

=== Θεωρία Κωδικοποίησης ===
Η θεωρία κωδικοποίησης είναι η μελέτη των ιδιοτήτων και της καταλληλότητας των κωδικών για μια συγκεκριμένη εφαρμογή. Οι κωδικοί χρησιμοποιούνται για τη συμπίεση δεδομένων, κρυπτογραφία, διόρθωσης σφαλμάτων και, πιο πρόσφατα, για την κωδικοποίηση του δικτύου. Οι κωδικοί μελετώνται από διάφορους επιστημονικούς κλάδους, όπως η θεωρία της πληροφορίας, ηλεκτρονική μηχανική, μαθηματικών και από την πληροφορική, με σκοπό την σχεδίαση και υλοποίηση αποδοτικών και αξιόπιστων μεθόδων μετάδοσης δεδομένων. Αυτό συνήθως περιλαμβάνει την αφαίρεση των πλεονασμών και τη διόρθωση (ή ανίχνευσης) των σφαλμάτων στα μεταδιδόμενα δεδομένα.

=== Υπολογιστική Θεωρία Μάθησης ===
Τα θεωρητικά αποτελέσματα στην μηχανική μάθηση ασχολούνται κυρίως με έναν τύπο της επαγωγικής μάθησης που ονομάζεται εποπτευόμενη μάθηση. Στην επιβλεπόμενη μάθηση, ένας αλγόριθμος δίνει δείγματα που επισημαίνονται με κάποιο χρήσιμο τρόπο. Για παράδειγμα, τα δείγματα θα μπορούσανε να είναι περιγραφές των μανιταριών και οι ετικέτες να δείχνουν εάν τα μανιτάρια είναι φαγώσιμα ή όχι. Ο αλγόριθμος παίρνει αυτά τα προηγουμένως επισημασμένα δείγματα και τα χρησιμοποιεί για να φτιάξει έναν ταξινομητή. Αυτός ο ταξινομητής είναι μια λειτουργία που εκχωρεί ετικέτες στα δείγματα, συμπεριλαμβανομένων των δειγμάτων που δεν έχουν ποτέ παρατηρηθεί προηγουμένως από τον αλγόριθμο. Ο στόχος του εποπτευόμενου αλγόριθμου μάθησης είναι η βελτιστοποίηση ως ενός σημείου της απόδοσης, όπως την ελαχιστοποίηση του αριθμού των λαθών που έγιναν σε νέα δείγματα.

== Περαιτέρω ανάγνωση ==

=== Εξωτερικοί σύνδεσμοι ===
* [https://theory.report/ Theory of Computing Report]
* [https://cs.uni-koeln.de/dmanet Δίκτυο διακριτών μαθηματικών και αλγορίθμων]
* [http://www.lix.polytechnique.fr/~hermann/conf.php Λίστα συνεδρίων στην θεωρητική πληροφορική]
* [http://cstheory.stackexchange.com/ Theoretical Computer Science - StackExchange], ένα site εωρτήσεων και απαντήσεων για τους ερευνητές στη θεωρητική πληροφορική
* [https://web.archive.org/web/20170715101741/http://www.sigact.org/webpages.php SIGACT directory of additional theory links]
* [https://web.archive.org/web/20170619133754/http://theorymatters.org/ Theory Matters Wiki] Θεωρητική Πληροφορική (TCS) Υπεράσπιση Wiki
* [news://comp.theory Usenet comp.theory]{{Dead link|date=Σεπτέμβριος 2019 }}
* [http://www.csanimated.com/browse.php Computer Science Animated]
* http://theory.csail.mit.edu/   @ [[Τεχνολογικό Ινστιτούτο Μασαχουσέτης|Massachusetts Institute of Technology]]

=== Οργανισμοί ===
* [[ACM]]
* [[SIAM]]
* [[Ευρωπαϊκή Ένωση για τη Θεωρητική Επιστήμη των Υπολογιστών]]
* [[SIGACT]]

== Παραπομπές ==
<references/>

{{DEFAULTSORT:Θεωρητική πληροφορική}}
[[Κατηγορία:Θεωρητική πληροφορική| ]]
[[Κατηγορία:Τυπικές επιστήμες]]