DIỄN ĐÀN TOÁN TIN
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.



 
CỔNG ĐHQGHN  XEM ĐIỂM  Trang ChínhTrang Chính  Latest imagesLatest images  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  
Bài gửi sau cùng
Bài gửiNgười gửiThời gian
Happy new year 2013 Sat Dec 29, 2012 3:45 pm
Lâu rùi anh không thấy chú nào vào diễn đàn nữa Mon May 07, 2012 9:26 am
Happy new year 2012. Mon Jan 30, 2012 5:05 am
[color=red]Tin "Cực Hot" cho tất cả các bạn và người thân[/color] Wed Oct 05, 2011 4:44 am
Cách đổi lịch âm dương Mon Oct 03, 2011 2:24 am
lâu lâu rùi không lên diễn đàn lớp mình chém gió Fri Sep 30, 2011 9:44 am
TRIỂN LÃM DU HỌC NHẬT BẢN 2010 Vừa học vừa làm thu nhập 1700USD/1 tháng Wed Sep 28, 2011 8:00 am
Vừa đi làm, vừa làm cộng tác viên kiếm tiền... Sun Aug 07, 2011 11:37 am
:(((((((((((((((((((((((((((((((((((((((((((((((((((((((( Sat Aug 06, 2011 5:05 am
Khánh thành website học tiếng anh của Chiến Fri Aug 05, 2011 10:30 am
Funy : Counter strike =)) Mon Jul 25, 2011 10:43 am
Lịch học hè Fri Jul 08, 2011 4:11 pm
Tổng hợp ảnh 24/06/2011 - Lễ tốt nghiệp Wed Jul 06, 2011 9:17 am
Câu lạc bộ tiếng anh của Chiến - cơ hội giao lưu người bản xứ Tue Jun 28, 2011 9:41 pm
[K52A3] CÔNG BỐ TÀI CHÍNH QUỸ LỚP (10/03/2011) Thu Jun 23, 2011 5:35 pm
[VPK] DANH SÁCH TỐT NGHIỆP CHÍNH THỨC Thu Jun 23, 2011 5:31 pm
[VPK] LỄ TRAO BẰNG TỐT NGHIỆP Wed Jun 22, 2011 11:59 am
Pic 21/06 (new and hot) Wed Jun 22, 2011 10:28 am
Gameloft Hà Nội tuyển dụng Mon Jun 20, 2011 8:18 pm
[ CTCTSV ] 21 THÁNG 6 ĐI LẤY HỒ SƠ TỐT NGHIỆP Sat Jun 18, 2011 9:38 am

 

 Hàm đệ qui nguyên thuỷ

Go down 
Tác giảThông điệp
chien2311
Enterprise Admin
Enterprise Admin
chien2311


Tổng số bài gửi : 1224
Sinh nhật : 23/11/1988

Hàm đệ qui nguyên thuỷ Empty
Bài gửiTiêu đề: Hàm đệ qui nguyên thuỷ   Hàm đệ qui nguyên thuỷ EmptyThu Mar 25, 2010 9:03 pm

HÀM ĐỆ QUY:


một cách khái quát, HĐQ là những hàm tính được theo từng bước qua các giá trị tính được ở các bước trước đó.
Một cách chính xác, cho các hàm số f(x1,…xn, y), φ (x1,..., xn) vày (x1,..., xn, y, z) với giá trị của các biến số và các hàm số là những số nguyên không âm, ta nói hàm số f(x1,... xn, y) nhận được từ φ (x1,..., xn) và ψ (x1,..., xn, y, z) bằng phép đệ quy nguyên thuỷ nếu
f(x1,..., xn, 0) = φ (x1,..., xn)
f(x1,..., xn, y + 1) = ψ(x1,..., xn, y, f(x1,...,xn, y)).
Ta nói φ (x1,..., xn) nhận được từ f(x1,..., xn, y) bằng phép toán tối tiểu hoá nếu nó được xác định và bằng y khi và chỉ khi f(x1,..., xn, 0),..., f(x1,..., xn, y - 1) xác định và có giá trị khác 0, còn f(x1,...,xn, y) = 0.
Hàm số gọi là HĐQ nguyên thuỷ nếu nó có thể nhận được từ các hàm đơn giản nhất (O(x) = 0, S(x) = x + 1, Imn (x1,..., xn) = xm) bằng các phép lấy hàm hợp
và phép đệ quy nguyên thuỷ. Hàm số gọi là HĐQ bộ phận nếu nó nhận được
từ các hàm đơn giản nhất, bằng phép lấy hàm hợp, phép đệ quy nguyên
thuỷ và phép tối tiểu hoá. HĐQ bộ phận gọi là HĐQ hoàn toàn nếu nó xác
định khắp nơi.


Đây là một khái niệm quan trọng trong toán lôgic và tin học lí thuyết.
Định đề Chơt nói rằng: lớp các HĐQ trùng với lớp các hàm "tính được"
(theo một cách xây dựng nào đó). Chẳng hạn, lớp HĐQ bộ phận trùng với
lớp hàm tính được bằng máy Turinh (Turing).



Nguồn : © Bản quyền 2005 thuộc Viện Từ điển học và Bách khoa thư Việt Nam - Phát triển bởi: 3CSoft
Về Đầu Trang Go down
 
Hàm đệ qui nguyên thuỷ
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Con đường tình yêu - Thùy chi
» Cỗ quan tài thủy tinh
» Hoàng Thuỳ Linh - 2 bài hát tuyệt vời
» NGUYỄN CHIẾN's than thở
» Ngôi Sao Bay -NGUYỄN CHIẾN

Permissions in this forum:Bạn không có quyền trả lời bài viết
DIỄN ĐÀN TOÁN TIN :: CÁC VẤN ĐỀ CHUNG :: KÌ HỌC 2 NĂM THỨ III :: THIẾT KẾ & ĐÁNH GIÁ THUẬT TOÁN-
Chuyển đến 
Create a forum on Forumotion | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất