Link tải luận văn miễn phí cho ae Kết nối
Nghiên cứu các đặc trưng tính toán trên máy Blum-shub-smale làm việc với số thực. Nghiên cứu một số đặc trưng đoán nhận ngôn ngữ và độ phức tạp theo mô hình mở rộng trên cấu trúc đại số
Data KHCN Thư mục kỉ niệm 100 năm Đại Học Quốc GiaHN
Chứng minh 2 định lý tổng quát về tính đoán nhận ngôn ngữ theo luật logic và luật De Morgan trên mô hình cấu trúc đại số
Chứng minh một vài tính chất kết hợp giữa 2 phép toán là hợp và giao trong đoán nhận ngôn ngữ
ĐHKHTN Khoa Toán - Cơ - Tin học

5. M ục tiêu và nội dung nghiên cứu
a) M ục tiêu nghiên cứu
M ô hình tính toán trên s ố thực được đưa ra bởi ba nhà khoa h ọc MỸ là L .B lum .
M .Shub, S.Sm ale vào nãm 19 8 9 và thường được g ọ i là m áyB SS.
- M ột trong những m ụ c tiêu chính theo cách tiếp cặn của B lu m -S h u b -S m a le là
phải x ây dựng lý thuyết độ phức tạp tính toán m ột cách phù hợp {c o n fo r m )
n hằm giải quyết cá c vấn đề dựa trẽn nền tảng c ơ bản là tính giải tích, tính tó-pô.
và chỉ ra m ột s ố vấn đề thực sự k h ó trong tính toán với bản chất là cá c s ố thực
bất kỳ được x ử lv như là m ột thực thể thực sự.
- M ộ t s ố khái n iệm và kết quả quan trọng của lý thuvết độ phức tạp c ổ đ iển được
ch u y ển san g m ỏ hình B S S -đơn định trong thời gian đa thức (ký hiệu ì à P r) và
m ô hình BSS-kìiâní' đơ n định cũ n g trong thời gian đa thức (ký hiệu là N P r ).
M ô hình tổn g quát hơn là m ô hình tính toán trẽn cấu trúc đại s ố được
A .H e m m e r lin g ( U n iversity G reifsw ald, F e d e ra l G e r m a n y ) n eh ié n cứu từ nhrrni
nãm 1995 tới nay về L ý thuyết độ phức tạp tính toán, kha n ãn c đoán nhãn nL:on
n g ữ và m ộ t s ố kết quá ch o các bài toán N P -đ ầ v đú.
PGS.TS.ĐỖ Trung Tuấn

b) Nội dung nghiên cứu
- N g h iên cứu cá c đặc trưng tính toán trên m á v BSS làm việc với s ố thực
* N g h iê n cưú m ộ t s ố đặc trưng đoán nhận ngôn ngữ và độ phức tạp theo m õ hình
m ở rộng trên cấu trúc đại sỏ
KÊT LƯẶN
Trên c ơ s ở lý thuyết Tin h ọ c. cá c khái niệm về khả năng tính được, đ ộ phức tạp
tính toán, và khả năng đoán nhận n g ó n n gữ trên m á y BSS và trên cấu trúc đại số. Chuns
tỏi đã n gh iên cứu th êm m ột sô tính chất cơ bản của hai m ô hình nói trên và đưa ra
được 2 định lý tổn g quát về tính đoán nhận n gón ngữ theo luật lo g ic và luật D e M o rsa n
trên cấu trúc đại số. Đ ổ n g thời áp dụng luật đã nêu ch o m ỏ hình cấu trúc đại số. một
có n g cụ rất hữu hiệu trong quá trình xử lý xâu ký tự dựa trên cấu trúc đại s ố như nhữne
kết quả truyền th ốn g trên m ó hình m á y Turing, đảm bảo tót tính hiệu quả và khá năng
đoán nhận của hai m ó hình theo tư tưởng lý thuyết độ phức tạp m ột cách đ ó n g đéu
(u n ifo r m ) từ m ột hình thức hoá này đến m ột hình thức hoá khác.
C ác kết quả đạt được của đề tài vừa m an g V nghĩa lv thuvết vừa m a n s V nghĩa
ihực tiễn, nhất là trong thời đại c ô n g n ghệ thông tin đã và đang phát triển m ột cách
m ạnh m ẽ như n g à y nay trẽn th ế giới.


/uc?export=down ... 2lhY0ZGaVE

---