Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
[Giới thiệu] Lý thuyết Automata (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - [Giới thiệu] Lý thuyết Automata
#471
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
[Giới thiệu] Lý thuyết Automata 12 năm, 9 tháng trước   (+0)
Lý thuyết Automata

Lý thuyết Automata là bộ môn nghiên cứu về các thiết bị tính toán trừu tượng (machines). Trước khi máy tính ra đời, vào thập niên 1930, A. Turing đã nghiên cứu một cỗ máy trừu tượng có đầy đủ khả năng tính toán như máy tính ngày nay. Mục tiêu của Turing là chỉ ra chính xác biên giới giữa những gì máy tính có thể và không thể làm. Kết luận của ông không chỉ áp dụng cho cỗ máy Turing trừu tượng mà còn cho tất cả các máy tính ngày nay.
Trong các thập niên 1940 và 1950, các cỗ máy đơn giản hơn, mà ngày này chúng ta gọi là automata hữu hạn (finite automata) được nghiên cứu bởi một số nhà khoa học. Những automata này, ban đầu được đề xuất để mô hình hóa các chức năng của bộ não, trở nên rất hữu ích cho nhiều mục đích khác. Vào cuối thập niên 1950, nhà ngôn ngữ học N. Chomsky bắt đầu nghiên cứu các văn phạm (grammars) chính quy. Mặc dù không phải là các cỗ máy, những văn phạm này có quan hệ gần gũi với các automata trừu tượng. Ngày nay, các văn phạm đóng vai trò nền tảng trong một số bộ phần của phần mềm máy tính, bao gồm trình biên dịch.
Vào năm 1969, S. Cook mở rộng lý thuyết của Turing về vấn đề có thể và không thể tính toán được. Cook đã chia ra những bài toán có thể giải quyết hiệu quả bằng máy tính và những bài toán có thể giải được trên lý thuyết, nhưng trên thực tế cần nhiều thời gian đến nỗi máy tính cũng trở nên không hữu dụng, trừ cho một số trường hợp nhỏ. Lớp các bài toán này được gọi là khó xử lý (intractable) hay “NP-hard”. Ngay cả nếu trong tương lai, tốc độ của máy tính tăng theo hàm mũ (định luật Moore), cũng không mở rộng được đáng kể khả năng giải quyết các bài toán này.

(Trích Introduction to Automata Theory, Languages and Computation – 2nd edition)

Thuật ngữ:
Máy trừu tượng: abstract machine
Máy Turing: Turing machine
Văn phạm chính quy: formal grammar
Automata hữu hạn: finite automata
Khó xử lý: intractable

Lý thuyết Automata là nội dung của bộ môn Theory of Computation, một bộ môn trong chương trình ở bậc đại học ngày nay.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#567
msn (Thành viên)
Biết code binary-indexed tree
Bài viết: 26
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: [Giới thiệu] Lý thuyết Automata 12 năm, 9 tháng trước   (+0)
Automata có khả năng nhận biết được các regular languages. Vì thế nó được sử dụng để làm tokenizer với độ phức tạp O(1) trong các compiler.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#8200
ldt116 (Thành viên)
ldt
Super fast coder
Bài viết: 56
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: [Giới thiệu] Lý thuyết Automata 12 năm, 2 tháng trước   (+0)
nếu muốn học về Automata có thể kím cuốn này: An introduction to formal languages and automata của Peter Linz.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS