Giáo trình Toán rời rạc: Phần 1 - Đỗ Đức Giáo

Phần 1 giáo trình "Toán rời rạc" sau đây gồm nội dung 5 chương đầu: Chương 1 - Khái niệm thuật toán - Phương pháp quy nạp, phương pháp đệ quy; chương 2 - Quan hệ, chương 3 - Đồ thị hữu hạn, chương 4 - Cây, chương 5 - Nhập môn về văn phạm và ngôn ngữ hình thức.
Nội dung trích xuất từ tài liệu:
Giáo trình Toán rời rạc: Phần 1 - Đỗ Đức Giáo - , T ĐẠI HỌC VINH THƯ VIỆN ĐÔ ĐỨC GIÁO W 511 Ế ĐO-G/00 DT. 000489 - ọ KỊ Ha N ú i NHÀ XUÂT BÁN ĐAI HOC QUÔC GIA HÀ NÔI Chiu trách nhiêm xuất ban: Giam đốc NGUYỄN VÀN THOA Tổng biên tập NGUYEN THIỆN GIÁP Người nhận xét: TS NGUYEN TUỆ TS HÀ QUANG THỤY Biên tập và sửa bản in: Đ ỗ Hữu PHÚ Trình bày bìa: NGỌC ANH TOÁN RỜI RẠC Mã số : 01 64.ĐH2000 - 55.2000 In 1000 bản, tại Nhà in Đại học Quốc gia Hà NÓI Số xuất bản: 39/55/CXB. Số trích ngang 171 KH/XB. In xong và nõp lưu chiểu Quý IV năm 2000. L Ờ I NÓI Đ Ầ U Nhằm đáp ứng nhu cầu phục vụ học tập của đông đảo sinh viên ngành Tin học và Công nghệ thông tin ở các trường đại học. Chúng tôi biên soạn giáo trình Toán rời rác theo hướng : sắp xếp nội dung tinh giản, hợp lý, đửng thời bảo đảm khôi kiên thức tôi thiểu về cơ sở Toán cho Tin học đê sinh viên có điều kiện tiếp thu tốt các môn chuyên ngành trong chương trình đào tạo cử nhân Tin học và Công nghệ thông tin ở giai đoạn li. Với khôi kiến thức được đề cập trong giáo trình này, sinh viên có thê tự học, tự đọc không mấy khó khăn cấc tài liệu chuyên sâu trong lĩnh vực Tin học lý thuyết. Nội dung chính của giáo trình bao gửm : Chương 1: Khái niệm thuật toán - Phương pháp quy nạp- Phương pháp đệ quy. Chương 2: Quan hệ. Chương 3: Đử thị hữu hạn. Chương 4: Cây. Chương 5: Nhập môn về văn phạm và ngôn ngữ hình thức. Chương 6: Ôtômat hữu hạn đoán nhận ngôn ngữ chính quy. Chưởng 7: Otômat đấy xuống đoán nhận ngôn ngữ phi ngữ cảnh Chương 8: Lôgic toán. Chương 9: Đại sốboole. 3 Trong mỗi chương chúng tôi chi đề cập những khái niệm cơ bản nhất, đông thời đưa ra một sô ví dụ minh họa giúp bạn đọc hiểu rõ bản chất của vân đề, cuối mỗi chương là phần bài tập đê bạn đọc củng cô kiên thức đã tiếp thu đưực từ phản lý thuyết. Tác giả xin chân thành cảm ơn các bạn đồng nghiệp, Khoa Công nghệ thống tin Trường đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã động viên, kích lệ chúng tôi biên soạn giáo trình này. Cảm ơn TS Nguyễn Tuệ, TS Hà Quang Thụy, TS Đinh Mạnh Tường, TS Vũ Ngọc Loàn đã đọc bản thảo và đóng góp nhiều ý kiến quý báu. cảm ơn Nhà xuất bản đại học Quác gia Hà Nội đã tạo điều kiện đê cuốn sách sớm đến tay bạn đọc. Cuốn sách xuất bản lần hai, chắc không tránh khỏi những thiếu sót, chúng tôi chân thành cảm ơn và tiếp thu ý kiên của bạn đọc đê lần xuất bản sau đưực hoàn thiện hơn. Tác giả 4 Chương Ì KHÁI N I Ệ M THUẬT TOÁN - PHƯƠNG PHÁP QUY NẠP - PHƯƠNG PHÁP ĐỆ QUY |1. KHÁI NIỆM THUẬT TOÁN 1.1. T h u ậ t t o á n là gì Thuật toán là một khái niệm quan trọng của toán học. Nói đến thuật toán là nói đèn một dãy các quy tắc. nhằm xác định một dãy các thao tác trên các đôi tượng, sao cho sau một sô hữu hạn bước thực hiện các thao tác. ta đạt được mảc tiêu cần làm. 1.2. C á c đ ặ c t r ư n g của t h u ậ t t o á n - Tính dừng: Sau một sô hữu hạn bước thuật toán phải dừng. - Tính xác định: ơ mỗi bước. các bước thao tác phải hết sức rõ ràng. không gây liên sự nhập nhằng. Nói rõ hơn. trong cùng một điều kiện hai bộ xử lý cùng thực hiện một bước của thuật toán phải cho những kết quả như nhau. - Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi chia dữ liệu vào thuật toán hoạt động và đưa ra kết quả như ý muốn. 5 • Tính phô dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lốp các bài toán. Cụ thể là thuật toán có thê có các đầu vào là các bộ dữ liệu khác nhau trong một miên xác định. - Yếu tố vào ra: Đối với một thuật toán luôn có một đối tượng vào (input) và đối tượng ra (output). 1.3. N g ô n ngữ thuật t o á n - Ngôn ngữ dùng để miêu tả thuật toán gọi là ngôn ngữ thuật toán. - Thuật toán thường được mô tả bặng một dãy các lệnh. Bộ xử lý sẽ thực hiện các lệnh đó theo một trật tự nhất định cho đến khi gặp lệnh dừng thì kết thúc. - Ngôn ngữ thuật toán bao gồm : + Ngôn ngữ liệt kê từng bước; + Sơ đồ khối; + Ngôn ngữ lập trình. a) Ngôn ngữ Hét kê từng bước nội dung như sau: 1. Thuật toán: Tên thuật toán và chức năng. 2. Vào: Các dữ liệu vào vói tên kiểu. 3. Ra: Các dữ liệu ra vối tên kiểu. 4. Biến phụ (nếu có) gồm tên kiểu. õ. Hà ...