Το λήμμα δεν περιέχει πηγές ή αυτές που περιέχει δεν επαρκούν.Μπορείτε να βοηθήσετε προσθέτοντας την κατάλληλη τεκμηρίωση. Υλικό που είναι ατεκμηρίωτο μπορεί να αμφισβητηθεί καινα αφαιρεθεί. Η σήμανση τοποθετήθηκε στις 21/05/2015.
Μία καλλιτεχνική αποτύπωση της Μηχανής Τούρινγκ. Οι μηχανές Τούρινγκ χρησιμοποιούνται γιατην μοντελοποίηση υπολογιστικών συσκευών.
Δεν είναι εύκολο να οριοθετηθούν οι θεωρητικοί τομείς επακριβώς καιη Ομάδα Ειδικού Ενδιαφέροντος για Αλγορίθμους και Θεωρία Υπολογισμού (SIGACT) της ACM περιγράφει ότι αποστολή της είναι η προώθηση της θεωρητικής επιστήμης των υπολογιστών και σημειώνει ότι:[1]
Στον παραπάνω κατάλογο, το περιοδικό της ACM Transactions on Computation Theory προσθέτει τηθεωρία κωδικοποίησης, τηνυπολογιστική θεωρία μάθησηςκαι τις θεωρητικές πτυχές της επιστήμης των υπολογιστών σε τομείς όπως οιβάσεις δεδομένων, ηανάκτηση πληροφοριών, τα οικονομικά μοντέλα καιταδίκτυα.[2] Παρά το ευρύ πεδίο εφαρμογής , οι "θεωρητικοί" στην επιστήμη των υπολογιστών αυτοπροσδιορίζονται ως διαφορετικοί από τους "ειδικούς εφαρμογών". Κάποιοι αυτοχαρακτηρίζονται ότι εφαρμόζουν «(τηνπιο θεμελιώδη) επιστήμη (ες) που κρύβεται πίσω από το πεδίο της υπολογιστικής».[3] Άλλοι «θεωρητικοί – ειδικοί εφαρμογών » προτείνουν ότι είναι αδύνατο να διαχωριστεί η θεωρία από την πρακτική εφαρμογή . Αυτό σημαίνει ότι οι αναφερόμενοι ως «θεωρητικοί» χρησιμοποιούν τακτικά την πειραματική επιστήμη (ες) σε λιγότερο θεωρητικούς τομείς όπως η έρευνα λογισμικού συστήματος . Αυτό σημαίνει επίσης ότι υπάρχει περισσότερη συνεργασία παρά ανταγωνισμός αλληλοαναίρεσης μεταξύ θεωρίας και εφαρμογής.
Ενώ η επίσημοι αλγόριθμοι υπάρχουν για χιλιετίες (οΕυκλείδειος αλγόριθμοςγιατον καθορισμό τουμέγιστου κοινού διαιρέτη δύο αριθμών εξακολουθεί να χρησιμοποιείται στους υπολογισμούς), δεν ήταν μέχρι το 1936 που οιΆλαν Τούρινγκ, Αλόνζο ΤσερτςκαιΣτίβεν Κλέινι επισημοποίησαν τον ορισμό ενός αλγορίθμου σε σχέση με τους υπολογισμούς. Ενώ τα δυαδικά καιλογικά συστήματατων μαθηματικών υπήρχαν πριν από το 1703, ήταν οΓκότφριντ Βίλχελμ Λάιμπνιτςπου όρισε την λογική με δυαδικές τιμές γιατοαληθέςκαιτοψευδές. Ενώ η λογική επαγωγή και μαθηματική απόδειξη υπήρχαν από την αρχαιότητα, το 1931 οΚουρτ Γκέντελ απέδειξε μετοθεώρημα της μη πληρότητας ότι υπήρχαν θεμελιώδεις περιορισμοί σχετικά μετοτι θεωρήματα θα μπορούσαν να αποδειχθούν ή να απορρηφθούν.
Αυτές οι εξελίξεις οδήγησαν στη σύγχρονη μελέτη της λογικής και της υπολογισιμότητας, και μάλιστα στον τομέα της επιστήμης της Θεωρητικής Πληροφορικής σαν ολότητα. Ηθεωρία της Πληροφορίας προστέθηκε σε αυτό το πεδίο το 1948 μετην μαθηματική θεωρία της επικοινωνίας τουΚλοντ Σάνον. Την ίδια δεκαετία, οΝτόναλντ Χεμπ εισήγαγε το μαθηματικό μοντέλο της μάθησηςτου εγκεφάλου. Μετην ενσωμάτωση βιολογικών δεδομένων τα οποία υποστηρίζουν αυτήν την υπόθεση καιμε κάποιες τροποποιήσεις, το πεδίο τωννευρωνικών δικτύωνκαιπαράλληλης κατανεμημένες επεξεργασίας θεσπίστηκαν. Το 1971, οΣτίβεν κουκκαιοΛεονίντ Λέβιν, που δούλευαν ανεξάρτητα, απέδειξαν ότι υπάρχουν πρακτικά σχετικά προβλήματα τα οποία είναι NP-πλήρης – ένα σημείο αναφοράς το οποίο είχε σαν αποτέλεσμα τηνθεωρία της πολυπλοκότητας.
Μετην ανάπτυξη της κβαντικής Μηχανικής στις αρχές του 20ου αιώνα θεμελιώθηκε η ιδέα ότι οι μαθηματικές πράξεις μπορούν να εκτελούνται σε ολόκληρη την κυματοσυνάρτηση σωματιδίων. Με άλλα λόγια, θα μπορούσε κανείς να υπολογίσει τις λειτουργίες σε πολλαπλές καταστάσεις ταυτόχρονα. Αυτό οδήγησε στην ιδέα τουκβαντικού υπολογιστήστο επόμενο μισό του 20ου αιώνα, η οποία απογειώθηκε (απέκτησε θεωρητική βάση) στη δεκαετία του 1990, όταν οΠίτερ Σορ έδειξε ότι τέτοιες μέθοδοι θα μπορούσαν να χρησιμοποιηθούν γιατην παραγοντοποίηση μεγάλων αριθμών σεπολυωνυμικό χρόνο, η οποία, αν εφαρμοστεί, θα καθιστούσε ταπιο σύγχρονα συστήματα κρυπτογραφίας δημόσιου κλειδιού άχρηστα και ανασφαλή.[εκκρεμεί παραπομπή]
Η σύγχρονη θεωρητική έρευνα στην επιστήμη των υπολογιστών βασίζεται σε αυτές τις βασικές εξελίξεις, αλλά περιλαμβάνει πολλά άλλα μαθηματικά και διεπιστημονικά προβλήματα που έχουν τεθεί.
Ένας αλγόριθμος είναι μιααποτελεσματική μέθοδοπου εκφράζεται ως μιαπεπερασμένη λίστα[4] από καλώς-ορισμένες οδηγίες[5]γιατον υπολογισμό μιας συνάρτησης.[6] Ξεκινώντας από μια αρχική κατάσταση καιμε αρχικές εισόδους (οι οποίες μπορεί να είναι κενές),[7]οι οδηγίες περιγράφουν έναν υπολογισμόο οποίος, όταν εκτελείται, προχωρά μέσω ενός πεπερασμένου[8] αριθμού καλώς-ορισμένων διαδοχικών καταστάσεων, οι οποίες τελικά παράγουν "έξοδο"[9]και τερματίζεται σεμια τελική κατάσταση. Η μετάβαση από μια κατάσταση στην επόμενη δεν είναι αναγκαστικά ντετερμινιστική; ορισμένοι αλγόριθμοι, γνωστοί ως πιθανοτικοί αλγόριθμοι, ενσωματώνουν τυχαία είσοδο.[10]
Διαφορετικά είδη δομών δεδομένων είναι κατάλληλα για διαφορετικά είδη εφαρμογών, και μερικά είναι άκρως εξειδικευμένα για συγκεκριμένες εργασίες. Για παράδειγμα, οι βάσεις δεδομένων χρησιμοποιούν 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
Υπολογιστική Βιολογία είναι διαφορετική από τονβιολογικό υπολογισμό, ο οποίος είναι ένα υποπεδίο της επιστήμης των υπολογιστών και της μηχανικής υπολογιστών χρησιμοποιώντας βιομηχανολογίακαιβιολογίαγιατην κατασκευή υπολογιστών , αλλά είναι παρόμοια μετηνβιοπληροφορική, η οποία είναι μια διεπιστημονική επιστήμη που χρησιμοποιούν υπολογιστές γιατην αποθήκευση καιτην επεξεργασία βιολογικών δεδομένων.
Ηυπολογιστική γεωμετρία είναι ένας κλάδος της επιστήμης των υπολογιστών που αφιερώνεται στη μελέτη των αλγορίθμων που μπορεί να δηλωθεί από την άποψη της γεωμετρίας. Μερικά καθαρά γεωμετρικά προβλήματα προκύπτουν από τη μελέτη των υπολογιστικών αλγορίθμων γεωμετρικής, καιτα προβλήματα αυτά θεωρούνται επίσης να είναι μέρος της υπολογιστικής γεωμετρίας. Ενώ η σύγχρονη υπολογιστική γεωμετρία είναι μια πρόσφατη εξέλιξη, είναι ένας από τους παλαιότερους τομείς της πληροφορικής με ιστορία που εκτείνεται πίσω στην αρχαιότητα. Ένα αρχαίο πρόδρομο είναι ησανσκριτική πραγματεία 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μάτων'', καθώς καιτα υπολογιστικά προβλήματα που μπορούν να επιλυθούν μετη χρήση αυτών. Είναι μια θεωρία στη θεωρητική επιστήμη των υπολογιστών, με Διακριτά Μαθηματικά (ένα τμήμα των Μαθηματικών καθώς επίσης και της Επιστήμης Υπολογιστών). Η λέξη ''αυτόματα'' προέρχεται από την ελληνική λέξη αὐτόματα, που σημαίνει "αυτενεργό".
Η θεωρία αυτομάτων είναι η μελέτη της αυτο-λειτουργίας των εικονικών μηχανών γιανα βοηθήσουν στην κατανόηση της λογικής διεργασίας εισόδου και εξόδου, με ή χωρίς ενδιάμεσο στάδιο(α) του υπολογισμού (ή οποιαδήποτε λειτουργία / διαδικασία).
Η θεωρία κωδικοποίησης είναι η μελέτη των ιδιοτήτων και της καταλληλότητας των κωδικών γιαμια συγκεκριμένη εφαρμογή. Οι κωδικοί χρησιμοποιούνται γιατη συμπίεση δεδομένων, κρυπτογραφία, διόρθωσης σφαλμάτων και, πιο πρόσφατα, γιατην κωδικοποίηση του δικτύου. Οι κωδικοί μελετώνται από διάφορους επιστημονικούς κλάδους, όπως η θεωρία της πληροφορίας, ηλεκτρονική μηχανική, μαθηματικών και από την πληροφορική, με σκοπό την σχεδίαση και υλοποίηση αποδοτικών και αξιόπιστων μεθόδων μετάδοσης δεδομένων. Αυτό συνήθως περιλαμβάνει την αφαίρεση των πλεονασμών καιτη διόρθωση (ή ανίχνευσης) των σφαλμάτων στα μεταδιδόμενα δεδομένα.
Τα θεωρητικά αποτελέσματα στην μηχανική μάθηση ασχολούνται κυρίως με έναν τύπο της επαγωγικής μάθησης που ονομάζεται εποπτευόμενη μάθηση. Στην επιβλεπόμενη μάθηση, ένας αλγόριθμος δίνει δείγματα που επισημαίνονται με κάποιο χρήσιμο τρόπο. Για παράδειγμα, τα δείγματα θα μπορούσανε να είναι περιγραφές των μανιταριών καιοι ετικέτες να δείχνουν εάν τα μανιτάρια είναι φαγώσιμα ή όχι. Ο αλγόριθμος παίρνει αυτά τα προηγουμένως επισημασμένα δείγματα καιτα χρησιμοποιεί γιανα φτιάξει έναν ταξινομητή. Αυτός ο ταξινομητής είναι μια λειτουργία που εκχωρεί ετικέτες στα δείγματα, συμπεριλαμβανομένων των δειγμάτων πουδεν έχουν ποτέ παρατηρηθεί προηγουμένως από τον αλγόριθμο. Ο στόχος του εποπτευόμενου αλγόριθμου μάθησης είναι η βελτιστοποίηση ως ενός σημείου της απόδοσης, όπως την ελαχιστοποίηση του αριθμού των λαθών που έγιναν σε νέα δείγματα.
↑"Κάθε κλασσικός μαθηματικός αλγόριθμος, για παράδειγμα, μπορεί να περιγραφεί με μία πεπερασμένη ακολουθία αγγλικών λέξεων" (Rogers 1987:2).
↑Καλώς-ορισμένες όσον αφορά τον εκτελεστή του αλγορίθμου: "Υπάρχει ένας υπολογιστικός εκτελεστής, συνήθως άνθρωπος, ο οποίος μπορεί να αντιδράσει στις οδηγίες καινα τις εκτελέσει" (Rogers 1987:2).
↑"ένας αλγόριθμος είναι μία διαδικασία γιατον υπολογισμό μίας συνάρτησης (για κάποια ορισμένη αναπαράσταση των ακεραίων) ... αυτός ο περιορισμός (στις αριθμητικές συναρτήσεις) δεν επηρεάζει τη γενικότητα", (Rogers 1987:1).
↑"Ένας αλγόριθμος έχει μηδέν ή παραπάνω εισόδους, δηλαδή ποσότητες που δίνονται σε αυτόν αρχικά, πριν ξεκινήσει ο αλγόριθμος" (Knuth 1973:5).
↑"Μία διαδικασία που έχει όλα τα χαρακτηριστικά ενός αλγορίθμου εκτός ότι πιθανόν υστερεί της πεπερατότητας, μπορεί να ονομαστεί 'υπολογιστική μέθοδος'" (Knuth 1973:5).
↑"Ένας αλγόριθμος έχει ένα ή παραπάνω εξόδους, δηλαδή ποσότητες που ορίζονται σε σχέση με τις εισόδος" (Knuth 1973:5).
↑
Κατά πόσο μία διαδικασία με πιθανοτικές εσωτερικές διαδικασίες (χωρίς να συμπεριλαμβάνεται η είσοδος) συνιστά αλγόριθμο είναι συζητήσιμο. Ο Rogers λέει ότι: "ένας υπολογισμός που εκτελείται σε διακριτά βήματα, χωρίς συνεχείς μεθόδους ή αναλογικές συσκευές ... εκετελείται ντετερμινιστιικά, χωρίς την χρήση πιθανοτικών μεθόδων ή συσκευών, όπως ένα ζάρι" (Rogers 1987:2).
↑ 13,013,1George Coulouris· Jean Dollimore· Tim Kindberg· Gordon Blair (2011). Κατανεμημένα Συστήματα: Έννοιες και Σχεδιασμός (5η έκδοση). Boston: Addison-Wesley. ISBN0-132-14301-1.
↑S.V. Adve κ.α. (Νοέμβριος 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda"Αρχειοθετήθηκε 2008-12-09 στοWayback Machine. (PDF). Parallel@Illinois, Πανεπιστήμιο της Illinois στην πεδιάδα της Urbana. "Οι κύριες τεχνικές για αυτά τα πλεονεκτήματα απόδοσης – αυξημένη συχνότητα ρολογιού καιπιο έξυπνη, αλλά όλο καιπιο πολύπλοκες αρχιτεκτονικές – χτυπούν τώτα το λεγόμενο τείχος εξουσίας. Η βιομηχανία των υπολογιστών έχει δεχθεί ότι η μελλοντική αύξηση της απόδοσης πρέπει να προέρχεται σε μεγάλο βαθμό από την αύξηση του αριθμού των επεξεργαστών (ή πυρήνες) σε έναν κύβο, αντί να κάνει ένα ενιαίο πυρήνα πάει πιο γρήγορα."
↑Asanovic κ.α . Η παλιά [συμβατική σοφία]: Η δύναμη είναι δωρεάν, αλλά τα τρανζίστορ είναι ακριβά. Η νέα [συμβατική σοφία] είναι [οτι] η δύναμη είναι ακριβή,αλλά τα τρανζίστορ είναι "δωρεάν".
↑Asanovic, Krste κ.α. (Δεκέμβριος 18, 2006). "The Landscape of Parallel Computing Research: A View from Berkeley" (PDF). Πανεπιστήμιο της California, Berkeley. Τεχνικη Εκθεση No. UCB/EECS-2006-183. "Παλιά [συμβατική σοφία]: Η αύξηση της συχνότητας του ρολογιού είναι η κύρια μέθοδος γιατη βελτίωση της απόδοσης του επεξεργαστή. Νέα [συμβατική σοφία]: Η αύξηση του παραλληλισμού είναι η κύρια μέθοδος γιατη βελτίωση της απόδοσης του επεξεργαστή ... Ακόμη και εκπρόσωποι από την Intel, μια εταιρεία που σχετίζεται γενικά μετην «υψηλότερη ταχύτητα ρολογιου είναι καλύτερη» άποψη, προειδοποίησε ότι οι παραδοσιακές προσεγγίσεις γιατη μεγιστοποίηση της απόδοσης μέσω της μεγιστοποίησης της ταχύτητας ρολογιού του έχει ωθήσει στα όριά τους."
↑Wernick, Yang, Brankov, Yourganov and Strother, Machine Learning in Medical Imaging, IEEE Signal Processing Magazine, vol. 27, no. 4, Ιούλιος 2010, pp. 25-38
↑Mannila, Heikki (1996). «Data mining: machine learning, statistics, and databases». Int'l Conf. Scientific and Statistical Database Management. IEEE Computer Society.
↑Jerome H. Friedman (1998). «Data Mining and Statistics: What's the connection?». Computing Science and Statistics29 (1): 3–9.
↑«About the CCMB». Center for Computational Molecular Biology. Ανακτήθηκε στις 18 Αυγούστου 2012.
↑F. Rieke· D. Warland· R Ruyter van Steveninck· W Bialek (1997). Spikes: Exploring the Neural Code. The MIT press. ISBN978-0262681087.
↑cf. Huelsenbeck, J. P., F. Ronquist, R. Nielsen and J. P. Bollback (2001) Bayesian inference of phylogeny and its impact on evolutionary biology, Science294:2310-2314
↑Rando Allikmets, Wyeth W. Wasserman, Amy Hutchinson, Philip Smallwood, Jeremy Nathans, Peter K. Rogan, Thomas D. SchneiderΑρχειοθετήθηκε 2008-08-21 στοWayback Machine., Michael Dean (1998) Organization of the ABCR gene: analysis of promoter and splice junction sequences, Gene215:1, 111-122
↑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.
↑Manin, Yu. I. (1980). Vychislimoe i nevychislimoe [Computable and Noncomputable] (στα Ρωσικά). Sov.Radio. σελίδες 13–15. Αρχειοθετήθηκε από το πρωτότυπο στις 10 Μαΐου 2013. Ανακτήθηκε στις 4 Μαρτίου 2013.
↑David Finkelstein (1968). «Space-Time Structure in High Energy Interactions». Στο: T. Gudehus· G. Kaiser. Fundamental Interactions at High Energy. New York: Gordon & Breach.
