Khảo sát cơ sở của ánh xạ đóng

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/

1

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

PHẠM KHÁNH TOÀN

KHẢO SÁT CƠ SỞ CỦA ÁNH XẠ ĐÓNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - 2013

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/

1

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

PHẠM KHÁNH TOÀN

KHẢO SÁT CƠ SỞ CỦA ÁNH XẠ ĐÓNG

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: PGS.TSKH Nguyễn Xuân Huy

THÁI NGUYÊN - 2013

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/

i

LỜI CAM ĐOAN

Tôi xin cam đoan, kết quả của luận văn hoàn toàn là kết quả của tự

bản thân tôi tìm hiểu, nghiên cứu và thực hiện theo sự hướng dẫn khoa

học của PGS.TSKH. Nguyễn Xuân Huy.

Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ.

Thái Nguyên, ngày 10 tháng 11 năm 2013

Tác giả

Phạm Khánh Toàn

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/

i

LỜI CẢM ƠN

Học viên xin được bày tỏ lòng biết ơn chân thành và sâu sắc nhất đến

thầy giáo PGS.TSKH. Nguyễn Xuân Huy, người đã tận tình hướng dẫn và tạo

mọi điều kiện tốt nhất để có thể hoàn thành luận văn này.

Xin chân thành cảm ơn các thầy giáo, cô giáo Trường Đại học Công

nghệ thông tin và Truyền thông - Đại học Thái Nguyên, Viện Công nghệ

Thông tin - Viện Khoa học và Công nghệ Việt Nam đã trực tiếp giảng dạy,

giúp đỡ và tạo mọi điều kiện thuận lợi trong quá trình học tập và nghiên cứu.

Trân trọng cảm ơn các thầy cô giáo, gia đình, các bạn lớp cao học Khoa

học máy tính CK10C và các bạn đồng nghiệp đã luôn quan tâm, hỗ trợ,

khuyến khích học viên trong suốt thời gian học tập và thực hiện đề tài.

Xin chân thành cám ơn!

Học viên

Phạm Khánh Toàn

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/

i

MỤC LỤC

Trang phụ bìa

Lời cam đoan

Lời cảm ơn

MỤC LỤC................................................................................................................... i

DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT............................................. iii

DANH MỤC CÁC BẢNG........................................................................................ iv

DANH MỤC HÌNH VẼ............................................................................................ iv

MỞ ĐẦU ....................................................................................................................1

1. Lý do chọn đề tài.....................................................................................................1

1.1. Cơ sở lí luận ....................................................................................................1

1.2. Cơ sở thực tiễn ................................................................................................1

2. Đối tượng và phạm vi nghiên cứu...........................................................................1

2.1. Đối tượng nghiên cứu......................................................................................1

2.2. Phạm vi nghiên cứu.........................................................................................2

3. Nhiệm vụ nghiên cứu ..............................................................................................2

4. Hướng nghiên cứu...................................................................................................2

5. Phương pháp nghiên cứu.........................................................................................2

6. Ý nghĩa lý luận và thực tiễn ....................................................................................3

7. Cấu trúc của luận văn..............................................................................................3

Chƣơng 1. CÁC KHÁI NIỆM CƠ SỞ ....................................................................4

1.1. Ánh xạ đóng .........................................................................................................4

1.2. Một số tính chất của ánh xạ đóng ........................................................................5

1.3. Hội các ánh xạ đóng.............................................................................................6

1.4. Điểm bất động của ánh xạ đóng...........................................................................6

1.5. Hạn chế trên ánh xạ đóng.....................................................................................7

1.6. Cơ sở của ánh xạ đóng [3]....................................................................................7

1.7. Hệ sinh ánh xạ đóng.............................................................................................8

Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/

ii

1.7.1. Định nghĩa hệ sinh [2].......................................................................................... 8

1.7.2. Định lý hệ sinh cho ánh xạ đóng [2]................................................................... 9

1.8. Thu gọn hệ sinh ánh xạ đóng .............................................................................10

1.8.1. Định nghĩa [2]..................................................................................................... 10

1.8.2. Định lý về công thức biểu diễn ánh xạ đóng theo phép thu gọn hệ sinh........... 11

1.8.3. Hệ quả về công thức tính ảnh cho một tập ....................................................... 11

1.9. Biểu diễn cơ sở hệ sinh ánh xạ đóng..................................................................12

1.9.1. Cơ sở của hệ sinh ............................................................................................... 12

1.9.2. Hai dạng biểu diễn cơ sở của hệ sinh ánh xạ đóng............................................ 13

1.9.3. Thuật toán tìm cơ sở của hệ sinh ánh xạ đóng................................................... 18

1.10. Kết luận chương 1 ............................................................................................20

Chƣơng 2. HỆ SUY DẪN VÀ ỨNG DỤNG..........................................................21

2.1. Hệ suy dẫn..........................................................................................................21

2.1.1. Định nghĩa .......................................................................................................... 21

2.1.2. Các quy tắc suy dẫn............................................................................................ 21

2.2. Các dạng toán của một hệ suy dẫn.....................................................................21

2.2.1. Dạng toán 1......................................................................................................... 21

2.2.2. Dạng toán 2......................................................................................................... 22

2.2.3. Các thí dụ............................................................................................................ 23

Chƣơng 3. CÀI ĐẶT CHƢƠNG TRÌNH..............................................................38

3.1. Giới thiệu ............................................................................................................... 38

3.2. Các lớp đối tượng của chương trình..................................................................... 38

3.3. Giao diện của chương trình................................................................................... 39

3.4. Kiểm thử, đánh giá.............................................................................................43

KẾT LUẬN VÀ ĐỀ NGHỊ.....................................................................................58

1. Kết luận .................................................................................................................58

2. Đề nghị..................................................................................................................58

TÀI LIỆU THAM KHẢO ......................................................................................59