Khoa học máy tính lý thuyết

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm

Khoa học máy tính lý thuyết là một tập hợp con của khoa học máy tínhtoán học tập trung vào nhiều chủ đề toán học hơn của điện toán và bao gồm lý thuyết của sự tính toán.

Khó để mô tả lĩnh vực lý thuyết này. Dự án ACM SIGACT của ACM đã cung cấp một định nghĩa như sau:[1] "Khoa học máy tính lý thuyết bao quát một vùng lớn các chủ đề gồm thuật toán, cấu trúc dữ liệu, sự phức tạp điện toán, sự tính toán song song và được phân bổ, điện toán xác suất, điện toán lượng tử , lý thuyết máy tự động, lý thuyết thông tin, mật mã, ngữ nghĩa học chương trìnhxác nhận chương trình, học máy, sinh học điện toán, kinh tế điện toán, hình học điện toán, lý thuyết số điện toánsố học. Những công trình nghiên cứu của lĩnh vực này được phan biệt bằng tầm quan trọng của nó đối với kỹ thuật toán học và sự khắt khe.

Lịch sử[sửa | sửa mã nguồn]

Khi logic là sự suy luận và các bằng chứng toán học đã xuất hiện từ trước, vào năm 1931, Kurt Gödel đã chứng minh bằng định luật bất toàn rằng có một giới hạn cơ sở trên cái mà những tuyên bố có thể được chứng minh hoặc không được chứng minh.

Những phát triển này đã dẫn dắt nghiên cứu hiện đại về logickhả năng tính toán và cả khoa học máy tính lý thuyết trên toàn bộ. Lý thuyết thông tin được thêm vào lĩnh vực khoa học máy tính lý thuyết với một lý thuyết toán học vào năm 1948 bởi Claude Shannon. Cùng trong thập kỷ, Donald Hebb giới thiệu một mô hình toán học của học trong não. Với việc gắn dữ liệu sinh học hỗ trợ giả thuyết này với một số sửa đổi, các lĩnh vực về mạng lưới neuronequá trình được sắp xếp song song được thiết lập. Trong năm 1971, Stephen CookLeonid Levin, làm việc độc lập với nhau, đã chứng minh có những vấn đề thích đáng một cách thực tiễn. Đó là NP-complete một kết quả bước ngoặt của lý thuyết phức tạp tính toán.

Với sự phát triển của cơ học lượng tử trong đầu thế kỷ 20 trở thành khái niệm rằng các quá trình toán học có thể được biểu diễn trên một hàm sóng hạt tổng thể. Hoặc có thể nói, lĩnh vực đó có thể tính toán hàm trên những ký hiệu phức tạp một cách đồng thời. Điều này đã dẫn đến khái niệm về máy tính lượng tử trong nửa sau của thế kỷ 20. Cụ thể là vào thập niên 1990, Peter Shor đã chỉ ra rằng các phương pháp cho những số lớn thừa số trong thời gian đa thức, cái mà nếu được bổ sung sẽ làm cho những hệ thống mật mã khóa phổ thống hiện đại nhất trở nên không an toàn.

Khoa học máy tính lý thuyết hiện đại dựa trên những sự phát triển cơ bản này, nhưng bao gồm nhiều vấn đề toán học và thuộc nhiều lĩnh vực học thuât đã được đặt ra, được trình bày ở dưới đây:

DFAexample.svg Elliptic curve simple.png 6n-graf.svg Wang tiles.svg P = NP ?
Logic toán học Lý thuyết máy tự động Lý thuyết số Lý thuyết đồ thị Lý thuyết khả năng tính toán Lý thuyết phức tạp tính toán
GNITIRW-TERCES Commutative diagram for morphism.svg SimplexRangeSearching.svg TSP Deutschland 3.png Blochsphere.svg
Cryptography Lý thuyết mẫu Lý thuyết thể loại Hình học tính toán Tối ưu hóa kết hợp Máy tính lượng tử

Xem thêm[sửa | sửa mã nguồn]

Chú thích[sửa | sửa mã nguồn]

  1. ^ “SIGACT”. Truy cập ngày 19 tháng 1 năm 2017. 

Đọc thêm[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]

Bản mẫu:Khoa học máy tính